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 #if DEBUG_T_SECT_LOOP_COUNT
202
203 #include "SkMutex.h"
204
205 SK_DECLARE_STATIC_MUTEX(debugWorstLoop);
206
207 SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr)
208 SkDEBUGPARAMS(nullptr));
209
ReportPathOpsDebugging()210 void ReportPathOpsDebugging() {
211 debugWorstState.debugLoopReport();
212 }
213
214 extern void (*gVerboseFinalize)();
215
216 #endif
217
OpDebug(const SkPath & one,const SkPath & two,SkPathOp op,SkPath * result SkDEBUGPARAMS (bool skipAssert)SkDEBUGPARAMS (const char * testName))218 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result
219 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
220 SkSTArenaAlloc<4096> allocator; // FIXME: add a constant expression here, tune
221 SkOpContour contour;
222 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
223 SkOpGlobalState globalState(contourList, &allocator
224 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
225 SkOpCoincidence coincidence(&globalState);
226 #if DEBUG_DUMP_VERIFY
227 #ifndef SK_DEBUG
228 const char* testName = "release";
229 #endif
230 if (SkPathOpsDebug::gDumpOp) {
231 SkPathOpsDebug::DumpOp(one, two, op, testName);
232 }
233 #endif
234 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
235 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
236 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
237 SkScalar scaleFactor = SkTMax(ScaleFactor(one), ScaleFactor(two));
238 SkPath scaledOne, scaledTwo;
239 const SkPath* minuend, * subtrahend;
240 if (scaleFactor > SK_Scalar1) {
241 ScalePath(one, 1.f / scaleFactor, &scaledOne);
242 minuend = &scaledOne;
243 ScalePath(two, 1.f / scaleFactor, &scaledTwo);
244 subtrahend = &scaledTwo;
245 } else {
246 minuend = &one;
247 subtrahend = &two;
248 }
249 if (op == kReverseDifference_SkPathOp) {
250 SkTSwap(minuend, subtrahend);
251 op = kDifference_SkPathOp;
252 }
253 #if DEBUG_SORT
254 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
255 #endif
256 // turn path into list of segments
257 SkOpEdgeBuilder builder(*minuend, contourList, &globalState);
258 if (builder.unparseable()) {
259 return false;
260 }
261 const int xorMask = builder.xorMask();
262 builder.addOperand(*subtrahend);
263 if (!builder.finish()) {
264 return false;
265 }
266 #if DEBUG_DUMP_SEGMENTS
267 contourList->dumpSegments("seg", op);
268 #endif
269
270 const int xorOpMask = builder.xorMask();
271 if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
272 xorOpMask == kEvenOdd_PathOpsMask)) {
273 result->reset();
274 result->setFillType(fillType);
275 return true;
276 }
277 // find all intersections between segments
278 SkOpContour* current = contourList;
279 do {
280 SkOpContour* next = current;
281 while (AddIntersectTs(current, next, &coincidence)
282 && (next = next->next()))
283 ;
284 } while ((current = current->next()));
285 #if DEBUG_VALIDATE
286 globalState.setPhase(SkOpPhase::kWalking);
287 #endif
288 bool success = HandleCoincidence(contourList, &coincidence);
289 #if DEBUG_COIN
290 globalState.debugAddToGlobalCoinDicts();
291 #endif
292 if (!success) {
293 return false;
294 }
295 #if DEBUG_ALIGNMENT
296 contourList->dumpSegments("aligned");
297 #endif
298 // construct closed contours
299 result->reset();
300 result->setFillType(fillType);
301 SkPathWriter wrapper(*result);
302 if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
303 return false;
304 }
305 wrapper.assemble(); // if some edges could not be resolved, assemble remaining
306 #if DEBUG_T_SECT_LOOP_COUNT
307 {
308 SkAutoMutexAcquire autoM(debugWorstLoop);
309 if (!gVerboseFinalize) {
310 gVerboseFinalize = &ReportPathOpsDebugging;
311 }
312 debugWorstState.debugDoYourWorst(&globalState);
313 }
314 #endif
315 if (scaleFactor > 1) {
316 ScalePath(*result, scaleFactor, result);
317 }
318 return true;
319 }
320
Op(const SkPath & one,const SkPath & two,SkPathOp op,SkPath * result)321 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
322 #if DEBUG_DUMP_VERIFY
323 if (SkPathOpsDebug::gVerifyOp) {
324 if (!OpDebug(one, two, op, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
325 SkPathOpsDebug::ReportOpFail(one, two, op);
326 return false;
327 }
328 SkPathOpsDebug::VerifyOp(one, two, op, *result);
329 return true;
330 }
331 #endif
332 return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
333 }
334