Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(3)

Side by Side Diff: src/pathops/SkPathOpsOp.cpp

Issue 2128633003: pathops coincidence and security rewrite (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: require resulting t to be between 0 and 1 Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
1 /* 1 /*
2 * Copyright 2012 Google Inc. 2 * Copyright 2012 Google Inc.
3 * 3 *
4 * Use of this source code is governed by a BSD-style license that can be 4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file. 5 * found in the LICENSE file.
6 */ 6 */
7 #include "SkAddIntersections.h" 7 #include "SkAddIntersections.h"
8 #include "SkOpCoincidence.h" 8 #include "SkOpCoincidence.h"
9 #include "SkOpEdgeBuilder.h" 9 #include "SkOpEdgeBuilder.h"
10 #include "SkPathOpsCommon.h" 10 #include "SkPathOpsCommon.h"
(...skipping 70 matching lines...) Expand 10 before | Expand all | Expand 10 after
81 #else 81 #else
82 *chase.append() = span; 82 *chase.append() = span;
83 #endif 83 #endif
84 return first; 84 return first;
85 } 85 }
86 } 86 }
87 return nullptr; 87 return nullptr;
88 } 88 }
89 89
90 static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op, 90 static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
91 const int xorMask, const int xorOpMask, SkPathWriter* simple, SkChunkAll oc* allocator) { 91 const int xorMask, const int xorOpMask, SkPathWriter* simple) {
92 bool unsortable = false; 92 bool unsortable = false;
93 do { 93 do {
94 SkOpSpan* span = FindSortableTop(contourList); 94 SkOpSpan* span = FindSortableTop(contourList);
95 if (!span) { 95 if (!span) {
96 break; 96 break;
97 } 97 }
98 SkOpSegment* current = span->segment(); 98 SkOpSegment* current = span->segment();
99 SkOpSpanBase* start = span->next(); 99 SkOpSpanBase* start = span->next();
100 SkOpSpanBase* end = span; 100 SkOpSpanBase* end = span;
101 SkTDArray<SkOpSpanBase*> chase; 101 SkTDArray<SkOpSpanBase*> chase;
102 do { 102 do {
103 if (current->activeOp(start, end, xorMask, xorOpMask, op)) { 103 if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
104 do { 104 do {
105 if (!unsortable && current->done()) { 105 if (!unsortable && current->done()) {
106 break; 106 break;
107 } 107 }
108 SkASSERT(unsortable || !current->done()); 108 SkASSERT(unsortable || !current->done());
109 SkOpSpanBase* nextStart = start; 109 SkOpSpanBase* nextStart = start;
110 SkOpSpanBase* nextEnd = end; 110 SkOpSpanBase* nextEnd = end;
111 SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd, 111 SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
112 &unsortable, op, xorMask, xorOpMask); 112 &unsortable, op, xorMask, xorOpMask);
113 if (!next) { 113 if (!next) {
114 if (!unsortable && simple->hasMove() 114 if (!unsortable && simple->hasMove()
115 && current->verb() != SkPath::kLine_Verb 115 && current->verb() != SkPath::kLine_Verb
116 && !simple->isClosed()) { 116 && !simple->isClosed()) {
117 if (!current->addCurveTo(start, end, simple)) { 117 if (!current->addCurveTo(start, end, simple)) {
118 return false; 118 return false;
119 } 119 }
120 #if DEBUG_ACTIVE_SPANS
121 if (!simple->isClosed()) { 120 if (!simple->isClosed()) {
122 DebugShowActiveSpans(contourList); 121 SkPathOpsDebug::ShowActiveSpans(contourList);
123 } 122 }
124 #endif
125 } 123 }
126 break; 124 break;
127 } 125 }
128 #if DEBUG_FLOW 126 #if DEBUG_FLOW
129 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9 g)\n", __FUNCTION__, 127 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9 g)\n", __FUNCTION__,
130 current->debugID(), start->pt().fX, start->pt().fY, 128 current->debugID(), start->pt().fX, start->pt().fY,
131 end->pt().fX, end->pt().fY); 129 end->pt().fX, end->pt().fY);
132 #endif 130 #endif
133 if (!current->addCurveTo(start, end, simple)) { 131 if (!current->addCurveTo(start, end, simple)) {
134 return false; 132 return false;
(...skipping 21 matching lines...) Expand all
156 #if DEBUG_WINDING 154 #if DEBUG_WINDING
157 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segmen t()->debugID()); 155 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segmen t()->debugID());
158 if (!last->final()) { 156 if (!last->final()) {
159 SkDebugf(" windSum=%d", last->upCast()->windSum()); 157 SkDebugf(" windSum=%d", last->upCast()->windSum());
160 } 158 }
161 SkDebugf("\n"); 159 SkDebugf("\n");
162 #endif 160 #endif
163 } 161 }
164 } 162 }
165 current = findChaseOp(chase, &start, &end); 163 current = findChaseOp(chase, &start, &end);
166 #if DEBUG_ACTIVE_SPANS 164 SkPathOpsDebug::ShowActiveSpans(contourList);
167 DebugShowActiveSpans(contourList);
168 #endif
169 if (!current) { 165 if (!current) {
170 break; 166 break;
171 } 167 }
172 } while (true); 168 } while (true);
173 } while (true); 169 } while (true);
174 return simple->someAssemblyRequired(); 170 return simple->someAssemblyRequired();
175 } 171 }
176 172
177 // pretty picture: 173 // pretty picture:
178 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b -7vD9JP2V-kn9Ss/edit?usp=sharing 174 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b -7vD9JP2V-kn9Ss/edit?usp=sharing
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after
219 ++dumpID); 215 ++dumpID);
220 fprintf(file, " SkPath path;\n"); 216 fprintf(file, " SkPath path;\n");
221 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", one.getFillT ype()); 217 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", one.getFillT ype());
222 dump_path(file, one, false, true); 218 dump_path(file, one, false, true);
223 fprintf(file, " SkPath path1(path);\n"); 219 fprintf(file, " SkPath path1(path);\n");
224 fprintf(file, " path.reset();\n"); 220 fprintf(file, " path.reset();\n");
225 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", two.getFillT ype()); 221 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", two.getFillT ype());
226 dump_path(file, two, false, true); 222 dump_path(file, two, false, true);
227 fprintf(file, " SkPath path2(path);\n"); 223 fprintf(file, " SkPath path2(path);\n");
228 fprintf(file, " testPathOp(reporter, path1, path2, (SkPathOp) %d, filenam e);\n", op); 224 fprintf(file, " testPathOp(reporter, path1, path2, (SkPathOp) %d, filenam e);\n", op);
229 fprintf(file, "}\n"); 225 fprintf(file, "}\n");
230 fclose(file); 226 fclose(file);
231 } 227 }
232 #endif 228 #endif
233 229
234 230
235 #if DEBUG_T_SECT_LOOP_COUNT 231 #if DEBUG_T_SECT_LOOP_COUNT
236 232
237 #include "SkMutex.h" 233 #include "SkMutex.h"
238 234
239 SK_DECLARE_STATIC_MUTEX(debugWorstLoop); 235 SK_DECLARE_STATIC_MUTEX(debugWorstLoop);
240 236
241 SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(nullptr)); 237 SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(nullptr));
242 238
243 void ReportPathOpsDebugging() { 239 void ReportPathOpsDebugging() {
244 debugWorstState.debugLoopReport(); 240 debugWorstState.debugLoopReport();
245 } 241 }
246 242
247 extern void (*gVerboseFinalize)(); 243 extern void (*gVerboseFinalize)();
248 244
249 #endif 245 #endif
250 246
251 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result 247 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result
252 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) { 248 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
253 SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tun e 249 SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tun e
254 SkOpContour contour; 250 SkOpContour contour;
255 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour); 251 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
256 SkOpCoincidence coincidence; 252 SkOpGlobalState globalState(contourList, &allocator
257 SkOpGlobalState globalState(&coincidence, contourList 253 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
258 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName)); 254 SkOpCoincidence coincidence(&globalState);
259 #if DEBUGGING_PATHOPS_FROM_HOST 255 #if DEBUGGING_PATHOPS_FROM_HOST
260 dump_op(one, two, op); 256 dump_op(one, two, op);
261 #endif
262 #if 0 && DEBUG_SHOW_TEST_NAME
263 char* debugName = DEBUG_FILENAME_STRING;
264 if (debugName && debugName[0]) {
265 SkPathOpsDebug::BumpTestName(debugName);
266 SkPathOpsDebug::ShowPath(one, two, op, debugName);
267 }
268 #endif 257 #endif
269 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()]; 258 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
270 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isI nverseFillType()] 259 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isI nverseFillType()]
271 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType; 260 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
272 const SkPath* minuend = &one; 261 SkScalar scaleFactor = SkTMax(ScaleFactor(one), ScaleFactor(two));
273 const SkPath* subtrahend = &two; 262 SkPath scaledOne, scaledTwo;
263 const SkPath* minuend, * subtrahend;
264 if (scaleFactor > SK_Scalar1) {
265 ScalePath(one, 1.f / scaleFactor, &scaledOne);
266 minuend = &scaledOne;
267 ScalePath(two, 1.f / scaleFactor, &scaledTwo);
268 subtrahend = &scaledTwo;
269 } else {
270 minuend = &one;
271 subtrahend = &two;
272 }
274 if (op == kReverseDifference_SkPathOp) { 273 if (op == kReverseDifference_SkPathOp) {
275 minuend = &two; 274 SkTSwap(minuend, subtrahend);
276 subtrahend = &one;
277 op = kDifference_SkPathOp; 275 op = kDifference_SkPathOp;
278 } 276 }
279 #if DEBUG_SORT 277 #if DEBUG_SORT
280 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault; 278 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
281 #endif 279 #endif
282 // turn path into list of segments 280 // turn path into list of segments
283 SkOpEdgeBuilder builder(*minuend, &contour, &allocator, &globalState); 281 SkOpEdgeBuilder builder(*minuend, &contour, &globalState);
284 if (builder.unparseable()) { 282 if (builder.unparseable()) {
285 return false; 283 return false;
286 } 284 }
287 const int xorMask = builder.xorMask(); 285 const int xorMask = builder.xorMask();
288 builder.addOperand(*subtrahend); 286 builder.addOperand(*subtrahend);
289 if (!builder.finish(&allocator)) { 287 if (!builder.finish()) {
290 return false; 288 return false;
291 } 289 }
292 #if DEBUG_DUMP_SEGMENTS 290 #if DEBUG_DUMP_SEGMENTS
293 contourList->dumpSegments("seg", op); 291 contourList->dumpSegments("seg", op);
294 #endif 292 #endif
295 293
296 const int xorOpMask = builder.xorMask(); 294 const int xorOpMask = builder.xorMask();
297 if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask, 295 if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
298 xorOpMask == kEvenOdd_PathOpsMask)) { 296 xorOpMask == kEvenOdd_PathOpsMask)) {
299 result->reset(); 297 result->reset();
300 result->setFillType(fillType); 298 result->setFillType(fillType);
301 return true; 299 return true;
302 } 300 }
303 // find all intersections between segments 301 // find all intersections between segments
304 SkOpContour* current = contourList; 302 SkOpContour* current = contourList;
305 do { 303 do {
306 SkOpContour* next = current; 304 SkOpContour* next = current;
307 while (AddIntersectTs(current, next, &coincidence, &allocator) 305 while (AddIntersectTs(current, next, &coincidence)
308 && (next = next->next())) 306 && (next = next->next()))
309 ; 307 ;
310 } while ((current = current->next())); 308 } while ((current = current->next()));
311 #if DEBUG_VALIDATE 309 #if DEBUG_VALIDATE
312 globalState.setPhase(SkOpGlobalState::kWalking); 310 globalState.setPhase(SkOpGlobalState::kWalking);
313 #endif 311 #endif
314 if (!HandleCoincidence(contourList, &coincidence, &allocator)) { 312 if (!HandleCoincidence(contourList, &coincidence)) {
315 return false; 313 return false;
316 } 314 }
317 #if DEBUG_ALIGNMENT 315 #if DEBUG_ALIGNMENT
318 contourList->dumpSegments("aligned"); 316 contourList->dumpSegments("aligned");
319 #endif 317 #endif
320 // construct closed contours 318 // construct closed contours
321 result->reset(); 319 result->reset();
322 result->setFillType(fillType); 320 result->setFillType(fillType);
323 SkPathWriter wrapper(*result); 321 SkPathWriter wrapper(*result);
324 bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper, &allocator); 322 bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
325 { // if some edges could not be resolved, assemble remaining fragments 323 { // if some edges could not be resolved, assemble remaining fragments
326 SkPath temp; 324 SkPath temp;
327 temp.setFillType(fillType); 325 temp.setFillType(fillType);
328 SkPathWriter assembled(temp); 326 SkPathWriter assembled(temp);
329 Assemble(wrapper, &assembled); 327 Assemble(wrapper, &assembled);
330 *result = *assembled.nativePath(); 328 *result = *assembled.nativePath();
331 result->setFillType(fillType); 329 result->setFillType(fillType);
332 } 330 }
333 #if DEBUG_T_SECT_LOOP_COUNT 331 #if DEBUG_T_SECT_LOOP_COUNT
334 { 332 {
335 SkAutoMutexAcquire autoM(debugWorstLoop); 333 SkAutoMutexAcquire autoM(debugWorstLoop);
336 if (!gVerboseFinalize) { 334 if (!gVerboseFinalize) {
337 gVerboseFinalize = &ReportPathOpsDebugging; 335 gVerboseFinalize = &ReportPathOpsDebugging;
338 } 336 }
339 debugWorstState.debugDoYourWorst(&globalState); 337 debugWorstState.debugDoYourWorst(&globalState);
340 } 338 }
341 #endif 339 #endif
340 if (scaleFactor > 1) {
341 ScalePath(*result, scaleFactor, result);
342 }
342 return true; 343 return true;
343 } 344 }
344 345
345 #define DEBUG_VERIFY 0 346 #define DEBUG_VERIFY 0
346 347
347 #if DEBUG_VERIFY 348 #if DEBUG_VERIFY
348 #include "SkBitmap.h" 349 #include "SkBitmap.h"
349 #include "SkCanvas.h" 350 #include "SkCanvas.h"
350 #include "SkPaint.h" 351 #include "SkPaint.h"
351 352
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after
451 const int MAX_ERRORS = 9; 452 const int MAX_ERRORS = 9;
452 if (errors > MAX_ERRORS) { 453 if (errors > MAX_ERRORS) {
453 SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one. getFillType()); 454 SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one. getFillType());
454 one.dumpHex(); 455 one.dumpHex();
455 SkDebugf("two: fill=%d\n", two.getFillType()); 456 SkDebugf("two: fill=%d\n", two.getFillType());
456 two.dumpHex(); 457 two.dumpHex();
457 SkASSERT(0); 458 SkASSERT(0);
458 } 459 }
459 return true; 460 return true;
460 #else 461 #else
461 return OpDebug(one, two, op, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(null ptr)); 462 return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullp tr));
462 #endif 463 #endif
463 } 464 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698