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