OLD | NEW |
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 Loading... |
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 Loading... |
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 Loading... |
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 Loading... |
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 } |
OLD | NEW |