1 /*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7 #include "SkAddIntersections.h"
8 #include "SkOpCoincidence.h"
9 #include "SkOpEdgeBuilder.h"
10 #include "SkPathOpsCommon.h"
11 #include "SkPathWriter.h"
12
findChaseOp(SkTDArray<SkOpSpanBase * > & chase,SkOpSpanBase ** startPtr,SkOpSpanBase ** endPtr)13 static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
14 SkOpSpanBase** endPtr) {
15 while (chase.count()) {
16 SkOpSpanBase* span;
17 chase.pop(&span);
18 // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
19 *startPtr = span->ptT()->prev()->span();
20 SkOpSegment* segment = (*startPtr)->segment();
21 bool done = true;
22 *endPtr = nullptr;
23 if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
24 *startPtr = last->start();
25 *endPtr = last->end();
26 #if TRY_ROTATE
27 *chase.insert(0) = span;
28 #else
29 *chase.append() = span;
30 #endif
31 return last->segment();
32 }
33 if (done) {
34 continue;
35 }
36 int winding;
37 bool sortable;
38 const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
39 if (!angle) {
40 return nullptr;
41 }
42 if (winding == SK_MinS32) {
43 continue;
44 }
45 int sumMiWinding, sumSuWinding;
46 if (sortable) {
47 segment = angle->segment();
48 sumMiWinding = segment->updateWindingReverse(angle);
49 if (sumMiWinding == SK_MinS32) {
50 SkASSERT(segment->globalState()->debugSkipAssert());
51 return nullptr;
52 }
53 sumSuWinding = segment->updateOppWindingReverse(angle);
54 if (sumSuWinding == SK_MinS32) {
55 SkASSERT(segment->globalState()->debugSkipAssert());
56 return nullptr;
57 }
58 if (segment->operand()) {
59 SkTSwap<int>(sumMiWinding, sumSuWinding);
60 }
61 }
62 SkOpSegment* first = nullptr;
63 const SkOpAngle* firstAngle = angle;
64 while ((angle = angle->next()) != firstAngle) {
65 segment = angle->segment();
66 SkOpSpanBase* start = angle->start();
67 SkOpSpanBase* end = angle->end();
68 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
69 if (sortable) {
70 segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
71 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
72 }
73 if (!segment->done(angle)) {
74 if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
75 first = segment;
76 *startPtr = start;
77 *endPtr = end;
78 }
79 // OPTIMIZATION: should this also add to the chase?
80 if (sortable) {
81 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
82 oppSumWinding, angle);
83 }
84 }
85 }
86 if (first) {
87 #if TRY_ROTATE
88 *chase.insert(0) = span;
89 #else
90 *chase.append() = span;
91 #endif
92 return first;
93 }
94 }
95 return nullptr;
96 }
97
bridgeOp(SkOpContourHead * contourList,const SkPathOp op,const int xorMask,const int xorOpMask,SkPathWriter * simple)98 static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
99 const int xorMask, const int xorOpMask, SkPathWriter* simple) {
100 bool unsortable = false;
101 do {
102 SkOpSpan* span = FindSortableTop(contourList);
103 if (!span) {
104 break;
105 }
106 SkOpSegment* current = span->segment();
107 SkOpSpanBase* start = span->next();
108 SkOpSpanBase* end = span;
109 SkTDArray<SkOpSpanBase*> chase;
110 do {
111 if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
112 do {
113 if (!unsortable && current->done()) {
114 break;
115 }
116 SkASSERT(unsortable || !current->done());
117 SkOpSpanBase* nextStart = start;
118 SkOpSpanBase* nextEnd = end;
119 SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
120 &unsortable, op, xorMask, xorOpMask);
121 if (!next) {
122 if (!unsortable && simple->hasMove()
123 && current->verb() != SkPath::kLine_Verb
124 && !simple->isClosed()) {
125 if (!current->addCurveTo(start, end, simple)) {
126 return false;
127 }
128 if (!simple->isClosed()) {
129 SkPathOpsDebug::ShowActiveSpans(contourList);
130 }
131 }
132 break;
133 }
134 #if DEBUG_FLOW
135 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
136 current->debugID(), start->pt().fX, start->pt().fY,
137 end->pt().fX, end->pt().fY);
138 #endif
139 if (!current->addCurveTo(start, end, simple)) {
140 return false;
141 }
142 current = next;
143 start = nextStart;
144 end = nextEnd;
145 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
146 if (current->activeWinding(start, end) && !simple->isClosed()) {
147 SkOpSpan* spanStart = start->starter(end);
148 if (!spanStart->done()) {
149 if (!current->addCurveTo(start, end, simple)) {
150 return false;
151 }
152 current->markDone(spanStart);
153 }
154 }
155 simple->finishContour();
156 } else {
157 SkOpSpanBase* last = current->markAndChaseDone(start, end);
158 if (last && !last->chased()) {
159 last->setChased(true);
160 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
161 *chase.append() = last;
162 #if DEBUG_WINDING
163 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
164 if (!last->final()) {
165 SkDebugf(" windSum=%d", last->upCast()->windSum());
166 }
167 SkDebugf("\n");
168 #endif
169 }
170 }
171 current = findChaseOp(chase, &start, &end);
172 SkPathOpsDebug::ShowActiveSpans(contourList);
173 if (!current) {
174 break;
175 }
176 } while (true);
177 } while (true);
178 return true;
179 }
180
181 // pretty picture:
182 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
183 static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
184 // inside minuend outside minuend
185 // inside subtrahend outside subtrahend inside subtrahend outside subtrahend
186 {{ kDifference_SkPathOp, kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
187 {{ kIntersect_SkPathOp, kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
188 {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp, kIntersect_SkPathOp }},
189 {{ kXOR_SkPathOp, kXOR_SkPathOp }, { kXOR_SkPathOp, kXOR_SkPathOp }},
190 {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp, kDifference_SkPathOp }},
191 };
192
193 static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
194 {{ false, false }, { true, false }}, // diff
195 {{ false, false }, { false, true }}, // sect
196 {{ false, true }, { true, true }}, // union
197 {{ false, true }, { true, false }}, // xor
198 {{ false, true }, { false, false }}, // rev diff
199 };
200
201 #define DEBUGGING_PATHOPS_FROM_HOST 0 // enable to debug svg in chrome -- note path hardcoded below
202 #if DEBUGGING_PATHOPS_FROM_HOST
203 #include "SkData.h"
204 #include "SkStream.h"
205
dump_path(FILE * file,const SkPath & path,bool force,bool dumpAsHex)206 static void dump_path(FILE* file, const SkPath& path, bool force, bool dumpAsHex) {
207 SkDynamicMemoryWStream wStream;
208 path.dump(&wStream, force, dumpAsHex);
209 sk_sp<SkData> data(wStream.detachAsData());
210 fprintf(file, "%.*s\n", (int) data->size(), (char*) data->data());
211 }
212
213 static int dumpID = 0;
214
dump_op(const SkPath & one,const SkPath & two,SkPathOp op)215 static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) {
216 #if SK_BUILD_FOR_MAC
217 FILE* file = fopen("/Users/caryclark/Documents/svgop.txt", "w");
218 #else
219 FILE* file = fopen("/usr/local/google/home/caryclark/Documents/svgop.txt", "w");
220 #endif
221 fprintf(file,
222 "\nstatic void fuzz763_%d(skiatest::Reporter* reporter, const char* filename) {\n",
223 ++dumpID);
224 fprintf(file, " SkPath path;\n");
225 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", one.getFillType());
226 dump_path(file, one, false, true);
227 fprintf(file, " SkPath path1(path);\n");
228 fprintf(file, " path.reset();\n");
229 fprintf(file, " path.setFillType((SkPath::FillType) %d);\n", two.getFillType());
230 dump_path(file, two, false, true);
231 fprintf(file, " SkPath path2(path);\n");
232 fprintf(file, " testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op);
233 fprintf(file, "}\n");
234 fclose(file);
235 }
236 #endif
237
238
239 #if DEBUG_T_SECT_LOOP_COUNT
240
241 #include "SkMutex.h"
242
243 SK_DECLARE_STATIC_MUTEX(debugWorstLoop);
244
245 SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr)
246 SkDEBUGPARAMS(nullptr));
247
ReportPathOpsDebugging()248 void ReportPathOpsDebugging() {
249 debugWorstState.debugLoopReport();
250 }
251
252 extern void (*gVerboseFinalize)();
253
254 #endif
255
OpDebug(const SkPath & one,const SkPath & two,SkPathOp op,SkPath * result SkDEBUGPARAMS (bool skipAssert)SkDEBUGPARAMS (const char * testName))256 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result
257 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
258 SkChunkAlloc allocator(4096); // FIXME: add a constant expression here, tune
259 SkOpContour contour;
260 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
261 SkOpGlobalState globalState(contourList, &allocator
262 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
263 SkOpCoincidence coincidence(&globalState);
264 #if DEBUGGING_PATHOPS_FROM_HOST
265 dump_op(one, two, op);
266 #endif
267 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
268 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
269 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
270 SkScalar scaleFactor = SkTMax(ScaleFactor(one), ScaleFactor(two));
271 SkPath scaledOne, scaledTwo;
272 const SkPath* minuend, * subtrahend;
273 if (scaleFactor > SK_Scalar1) {
274 ScalePath(one, 1.f / scaleFactor, &scaledOne);
275 minuend = &scaledOne;
276 ScalePath(two, 1.f / scaleFactor, &scaledTwo);
277 subtrahend = &scaledTwo;
278 } else {
279 minuend = &one;
280 subtrahend = &two;
281 }
282 if (op == kReverseDifference_SkPathOp) {
283 SkTSwap(minuend, subtrahend);
284 op = kDifference_SkPathOp;
285 }
286 #if DEBUG_SORT
287 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
288 #endif
289 // turn path into list of segments
290 SkOpEdgeBuilder builder(*minuend, contourList, &globalState);
291 if (builder.unparseable()) {
292 return false;
293 }
294 const int xorMask = builder.xorMask();
295 builder.addOperand(*subtrahend);
296 if (!builder.finish()) {
297 return false;
298 }
299 #if DEBUG_DUMP_SEGMENTS
300 contourList->dumpSegments("seg", op);
301 #endif
302
303 const int xorOpMask = builder.xorMask();
304 if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
305 xorOpMask == kEvenOdd_PathOpsMask)) {
306 result->reset();
307 result->setFillType(fillType);
308 return true;
309 }
310 // find all intersections between segments
311 SkOpContour* current = contourList;
312 do {
313 SkOpContour* next = current;
314 while (AddIntersectTs(current, next, &coincidence)
315 && (next = next->next()))
316 ;
317 } while ((current = current->next()));
318 #if DEBUG_VALIDATE
319 globalState.setPhase(SkOpPhase::kWalking);
320 #endif
321 bool success = HandleCoincidence(contourList, &coincidence);
322 #if DEBUG_COIN
323 globalState.debugAddToGlobalCoinDicts();
324 #endif
325 if (!success) {
326 return false;
327 }
328 #if DEBUG_ALIGNMENT
329 contourList->dumpSegments("aligned");
330 #endif
331 // construct closed contours
332 result->reset();
333 result->setFillType(fillType);
334 SkPathWriter wrapper(*result);
335 if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
336 return false;
337 }
338 wrapper.assemble(); // if some edges could not be resolved, assemble remaining
339 #if DEBUG_T_SECT_LOOP_COUNT
340 {
341 SkAutoMutexAcquire autoM(debugWorstLoop);
342 if (!gVerboseFinalize) {
343 gVerboseFinalize = &ReportPathOpsDebugging;
344 }
345 debugWorstState.debugDoYourWorst(&globalState);
346 }
347 #endif
348 if (scaleFactor > 1) {
349 ScalePath(*result, scaleFactor, result);
350 }
351 return true;
352 }
353
354 #define DEBUG_VERIFY 0
355
356 #if DEBUG_VERIFY
357 #include "SkBitmap.h"
358 #include "SkCanvas.h"
359 #include "SkPaint.h"
360
361 const int bitWidth = 64;
362 const int bitHeight = 64;
363
debug_scale_matrix(const SkPath & one,const SkPath & two,SkMatrix & scale)364 static void debug_scale_matrix(const SkPath& one, const SkPath& two, SkMatrix& scale) {
365 SkRect larger = one.getBounds();
366 larger.join(two.getBounds());
367 SkScalar largerWidth = larger.width();
368 if (largerWidth < 4) {
369 largerWidth = 4;
370 }
371 SkScalar largerHeight = larger.height();
372 if (largerHeight < 4) {
373 largerHeight = 4;
374 }
375 SkScalar hScale = (bitWidth - 2) / largerWidth;
376 SkScalar vScale = (bitHeight - 2) / largerHeight;
377 scale.reset();
378 scale.preScale(hScale, vScale);
379 larger.fLeft *= hScale;
380 larger.fRight *= hScale;
381 larger.fTop *= vScale;
382 larger.fBottom *= vScale;
383 SkScalar dx = -16000 > larger.fLeft ? -16000 - larger.fLeft
384 : 16000 < larger.fRight ? 16000 - larger.fRight : 0;
385 SkScalar dy = -16000 > larger.fTop ? -16000 - larger.fTop
386 : 16000 < larger.fBottom ? 16000 - larger.fBottom : 0;
387 scale.preTranslate(dx, dy);
388 }
389
debug_paths_draw_the_same(const SkPath & one,const SkPath & two,SkBitmap & bits)390 static int debug_paths_draw_the_same(const SkPath& one, const SkPath& two, SkBitmap& bits) {
391 if (bits.width() == 0) {
392 bits.allocN32Pixels(bitWidth * 2, bitHeight);
393 }
394 SkCanvas canvas(bits);
395 canvas.drawColor(SK_ColorWHITE);
396 SkPaint paint;
397 canvas.save();
398 const SkRect& bounds1 = one.getBounds();
399 canvas.translate(-bounds1.fLeft + 1, -bounds1.fTop + 1);
400 canvas.drawPath(one, paint);
401 canvas.restore();
402 canvas.save();
403 canvas.translate(-bounds1.fLeft + 1 + bitWidth, -bounds1.fTop + 1);
404 canvas.drawPath(two, paint);
405 canvas.restore();
406 int errors = 0;
407 for (int y = 0; y < bitHeight - 1; ++y) {
408 uint32_t* addr1 = bits.getAddr32(0, y);
409 uint32_t* addr2 = bits.getAddr32(0, y + 1);
410 uint32_t* addr3 = bits.getAddr32(bitWidth, y);
411 uint32_t* addr4 = bits.getAddr32(bitWidth, y + 1);
412 for (int x = 0; x < bitWidth - 1; ++x) {
413 // count 2x2 blocks
414 bool err = addr1[x] != addr3[x];
415 if (err) {
416 errors += addr1[x + 1] != addr3[x + 1]
417 && addr2[x] != addr4[x] && addr2[x + 1] != addr4[x + 1];
418 }
419 }
420 }
421 return errors;
422 }
423
424 #endif
425
Op(const SkPath & one,const SkPath & two,SkPathOp op,SkPath * result)426 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
427 #if DEBUG_VERIFY
428 if (!OpDebug(one, two, op, result SkDEBUGPARAMS(nullptr))) {
429 SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one.getFillType());
430 one.dumpHex();
431 SkDebugf("two: fill=%d\n", two.getFillType());
432 two.dumpHex();
433 SkASSERT(0);
434 return false;
435 }
436 SkPath pathOut, scaledPathOut;
437 SkRegion rgnA, rgnB, openClip, rgnOut;
438 openClip.setRect(-16000, -16000, 16000, 16000);
439 rgnA.setPath(one, openClip);
440 rgnB.setPath(two, openClip);
441 rgnOut.op(rgnA, rgnB, (SkRegion::Op) op);
442 rgnOut.getBoundaryPath(&pathOut);
443 SkMatrix scale;
444 debug_scale_matrix(one, two, scale);
445 SkRegion scaledRgnA, scaledRgnB, scaledRgnOut;
446 SkPath scaledA, scaledB;
447 scaledA.addPath(one, scale);
448 scaledA.setFillType(one.getFillType());
449 scaledB.addPath(two, scale);
450 scaledB.setFillType(two.getFillType());
451 scaledRgnA.setPath(scaledA, openClip);
452 scaledRgnB.setPath(scaledB, openClip);
453 scaledRgnOut.op(scaledRgnA, scaledRgnB, (SkRegion::Op) op);
454 scaledRgnOut.getBoundaryPath(&scaledPathOut);
455 SkBitmap bitmap;
456 SkPath scaledOut;
457 scaledOut.addPath(*result, scale);
458 scaledOut.setFillType(result->getFillType());
459 int errors = debug_paths_draw_the_same(scaledPathOut, scaledOut, bitmap);
460 const int MAX_ERRORS = 9;
461 if (errors > MAX_ERRORS) {
462 SkDebugf("%s did not expect failure\none: fill=%d\n", __FUNCTION__, one.getFillType());
463 one.dumpHex();
464 SkDebugf("two: fill=%d\n", two.getFillType());
465 two.dumpHex();
466 SkASSERT(0);
467 }
468 return true;
469 #else
470 return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
471 #endif
472 }
473