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 = NULL;
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 = NULL;
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 NULL;
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                             current->addCurveTo(start, end, simple, true);
115                     #if DEBUG_ACTIVE_SPANS
116                             if (!simple->isClosed()) {
117                                 DebugShowActiveSpans(contourList);
118                             }
119                     #endif
120                         }
121                         break;
122                     }
123         #if DEBUG_FLOW
124                     SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
125                             current->debugID(), start->pt().fX, start->pt().fY,
126                             end->pt().fX, end->pt().fY);
127         #endif
128                     current->addCurveTo(start, end, simple, true);
129                     current = next;
130                     start = nextStart;
131                     end = nextEnd;
132                 } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
133                 if (current->activeWinding(start, end) && !simple->isClosed()) {
134                     SkOpSpan* spanStart = start->starter(end);
135                     if (!spanStart->done()) {
136                         current->addCurveTo(start, end, simple, true);
137                         current->markDone(spanStart);
138                     }
139                 }
140                 simple->close();
141             } else {
142                 SkOpSpanBase* last = current->markAndChaseDone(start, end);
143                 if (last && !last->chased()) {
144                     last->setChased(true);
145                     SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
146                     *chase.append() = last;
147 #if DEBUG_WINDING
148                     SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
149                     if (!last->final()) {
150                          SkDebugf(" windSum=%d", last->upCast()->windSum());
151                     }
152                     SkDebugf("\n");
153 #endif
154                 }
155             }
156             current = findChaseOp(chase, &start, &end);
157         #if DEBUG_ACTIVE_SPANS
158             DebugShowActiveSpans(contourList);
159         #endif
160             if (!current) {
161                 break;
162             }
163         } while (true);
164     } while (true);
165     return simple->someAssemblyRequired();
166 }
167 
168 // pretty picture:
169 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
170 static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
171 //                  inside minuend                               outside minuend
172 //     inside subtrahend     outside subtrahend      inside subtrahend     outside subtrahend
173 {{ kDifference_SkPathOp,   kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
174 {{ kIntersect_SkPathOp,   kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
175 {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp,   kIntersect_SkPathOp }},
176 {{ kXOR_SkPathOp,                 kXOR_SkPathOp }, { kXOR_SkPathOp,                kXOR_SkPathOp }},
177 {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp,   kDifference_SkPathOp }},
178 };
179 
180 static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
181     {{ false, false }, { true, false }},  // diff
182     {{ false, false }, { false, true }},  // sect
183     {{ false, true }, { true, true }},    // union
184     {{ false, true }, { true, false }},   // xor
185     {{ false, true }, { false, false }},  // rev diff
186 };
187 
188 #define DEBUGGING_PATHOPS_FROM_HOST 0  // enable to debug svg in chrome -- note path hardcoded below
189 #if DEBUGGING_PATHOPS_FROM_HOST
190 #include "SkData.h"
191 #include "SkStream.h"
192 
dump_path(FILE * file,const SkPath & path,bool force,bool dumpAsHex)193 static void dump_path(FILE* file, const SkPath& path, bool force, bool dumpAsHex) {
194     SkDynamicMemoryWStream wStream;
195     path.dump(&wStream, force, dumpAsHex);
196     SkAutoDataUnref data(wStream.copyToData());
197     fprintf(file, "%.*s\n", (int) data->size(), data->data());
198 }
199 
200 static int dumpID = 0;
201 
dump_op(const SkPath & one,const SkPath & two,SkPathOp op)202 static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) {
203 #if SK_BUILD_FOR_MAC
204     FILE* file = fopen("/Users/caryclark/Documents/svgop.txt", "w");
205 #else
206     FILE* file = fopen("/usr/local/google/home/caryclark/Documents/svgop.txt", "w");
207 #endif
208     fprintf(file,
209             "\nstatic void fuzz763_%d(skiatest::Reporter* reporter, const char* filename) {\n",
210             ++dumpID);
211     fprintf(file, "    SkPath path;\n");
212     fprintf(file, "    path.setFillType((SkPath::FillType) %d);\n", one.getFillType());
213     dump_path(file, one, false, true);
214     fprintf(file, "    SkPath path1(path);\n");
215     fprintf(file, "    path.reset();\n");
216     fprintf(file, "    path.setFillType((SkPath::FillType) %d);\n", two.getFillType());
217     dump_path(file, two, false, true);
218     fprintf(file, "    SkPath path2(path);\n");
219     fprintf(file, "    testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op);
220     fprintf(file, "}\n");
221     fclose(file);
222 }
223 #endif
224 
OpDebug(const SkPath & one,const SkPath & two,SkPathOp op,SkPath * result,bool expectSuccess)225 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result,
226         bool expectSuccess) {
227     SkChunkAlloc allocator(4096);  // FIXME: add a constant expression here, tune
228     SkOpContour contour;
229     SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
230     SkOpCoincidence coincidence;
231     SkOpGlobalState globalState(&coincidence, contourList);
232 #if DEBUGGING_PATHOPS_FROM_HOST
233     dump_op(one, two, op);
234 #endif
235 #if 0 && DEBUG_SHOW_TEST_NAME
236     char* debugName = DEBUG_FILENAME_STRING;
237     if (debugName && debugName[0]) {
238         SkPathOpsDebug::BumpTestName(debugName);
239         SkPathOpsDebug::ShowPath(one, two, op, debugName);
240     }
241 #endif
242     op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
243     SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
244             ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
245     const SkPath* minuend = &one;
246     const SkPath* subtrahend = &two;
247     if (op == kReverseDifference_SkPathOp) {
248         minuend = &two;
249         subtrahend = &one;
250         op = kDifference_SkPathOp;
251     }
252 #if DEBUG_SORT
253     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
254 #endif
255     // turn path into list of segments
256     SkOpEdgeBuilder builder(*minuend, &contour, &allocator, &globalState);
257     if (builder.unparseable()) {
258         return false;
259     }
260     const int xorMask = builder.xorMask();
261     builder.addOperand(*subtrahend);
262     if (!builder.finish(&allocator)) {
263         return false;
264     }
265 #if DEBUG_DUMP_SEGMENTS
266     contour.dumpSegments(op);
267 #endif
268 
269     const int xorOpMask = builder.xorMask();
270     if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
271             xorOpMask == kEvenOdd_PathOpsMask)) {
272         result->reset();
273         result->setFillType(fillType);
274         return true;
275     }
276     // find all intersections between segments
277     SkOpContour* current = contourList;
278     do {
279         SkOpContour* next = current;
280         while (AddIntersectTs(current, next, &coincidence, &allocator)
281                 && (next = next->next()))
282             ;
283     } while ((current = current->next()));
284 #if DEBUG_VALIDATE
285     globalState.setPhase(SkOpGlobalState::kWalking);
286 #endif
287     if (!HandleCoincidence(contourList, &coincidence, &allocator)) {
288         return false;
289     }
290     // construct closed contours
291     result->reset();
292     result->setFillType(fillType);
293     SkPathWriter wrapper(*result);
294     bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper, &allocator);
295     {  // if some edges could not be resolved, assemble remaining fragments
296         SkPath temp;
297         temp.setFillType(fillType);
298         SkPathWriter assembled(temp);
299         Assemble(wrapper, &assembled);
300         *result = *assembled.nativePath();
301         result->setFillType(fillType);
302     }
303     return true;
304 }
305 
Op(const SkPath & one,const SkPath & two,SkPathOp op,SkPath * result)306 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
307     return OpDebug(one, two, op, result, true);
308 }
309