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
13 #include <utility>
14
findChaseOp(SkTDArray<SkOpSpanBase * > & chase,SkOpSpanBase ** startPtr,SkOpSpanBase ** endPtr,SkOpSegment ** result)15 static bool findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
16 SkOpSpanBase** endPtr, SkOpSegment** result) {
17 while (chase.count()) {
18 SkOpSpanBase* span;
19 chase.pop(&span);
20 // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
21 *startPtr = span->ptT()->prev()->span();
22 SkOpSegment* segment = (*startPtr)->segment();
23 bool done = true;
24 *endPtr = nullptr;
25 if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
26 *startPtr = last->start();
27 *endPtr = last->end();
28 #if TRY_ROTATE
29 *chase.insert(0) = span;
30 #else
31 *chase.append() = span;
32 #endif
33 *result = last->segment();
34 return true;
35 }
36 if (done) {
37 continue;
38 }
39 int winding;
40 bool sortable;
41 const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
42 if (!angle) {
43 *result = nullptr;
44 return true;
45 }
46 if (winding == SK_MinS32) {
47 continue;
48 }
49 int sumMiWinding, sumSuWinding;
50 if (sortable) {
51 segment = angle->segment();
52 sumMiWinding = segment->updateWindingReverse(angle);
53 if (sumMiWinding == SK_MinS32) {
54 SkASSERT(segment->globalState()->debugSkipAssert());
55 *result = nullptr;
56 return true;
57 }
58 sumSuWinding = segment->updateOppWindingReverse(angle);
59 if (sumSuWinding == SK_MinS32) {
60 SkASSERT(segment->globalState()->debugSkipAssert());
61 *result = nullptr;
62 return true;
63 }
64 if (segment->operand()) {
65 using std::swap;
66 swap(sumMiWinding, sumSuWinding);
67 }
68 }
69 SkOpSegment* first = nullptr;
70 const SkOpAngle* firstAngle = angle;
71 while ((angle = angle->next()) != firstAngle) {
72 segment = angle->segment();
73 SkOpSpanBase* start = angle->start();
74 SkOpSpanBase* end = angle->end();
75 int maxWinding = 0, sumWinding = 0, oppMaxWinding = 0, oppSumWinding = 0;
76 if (sortable) {
77 segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
78 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
79 }
80 if (!segment->done(angle)) {
81 if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
82 first = segment;
83 *startPtr = start;
84 *endPtr = end;
85 }
86 // OPTIMIZATION: should this also add to the chase?
87 if (sortable) {
88 if (!segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
89 oppSumWinding, angle, nullptr)) {
90 return false;
91 }
92 }
93 }
94 }
95 if (first) {
96 #if TRY_ROTATE
97 *chase.insert(0) = span;
98 #else
99 *chase.append() = span;
100 #endif
101 *result = first;
102 return true;
103 }
104 }
105 *result = nullptr;
106 return true;
107 }
108
bridgeOp(SkOpContourHead * contourList,const SkPathOp op,const int xorMask,const int xorOpMask,SkPathWriter * writer)109 static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
110 const int xorMask, const int xorOpMask, SkPathWriter* writer) {
111 bool unsortable = false;
112 bool lastSimple = false;
113 bool simple = false;
114 do {
115 SkOpSpan* span = FindSortableTop(contourList);
116 if (!span) {
117 break;
118 }
119 SkOpSegment* current = span->segment();
120 SkOpSpanBase* start = span->next();
121 SkOpSpanBase* end = span;
122 SkTDArray<SkOpSpanBase*> chase;
123 do {
124 if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
125 do {
126 if (!unsortable && current->done()) {
127 break;
128 }
129 SkASSERT(unsortable || !current->done());
130 SkOpSpanBase* nextStart = start;
131 SkOpSpanBase* nextEnd = end;
132 lastSimple = simple;
133 SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
134 &unsortable, &simple, op, xorMask, xorOpMask);
135 if (!next) {
136 if (!unsortable && writer->hasMove()
137 && current->verb() != SkPath::kLine_Verb
138 && !writer->isClosed()) {
139 if (!current->addCurveTo(start, end, writer)) {
140 return false;
141 }
142 if (!writer->isClosed()) {
143 SkPathOpsDebug::ShowActiveSpans(contourList);
144 }
145 } else if (lastSimple) {
146 if (!current->addCurveTo(start, end, writer)) {
147 return false;
148 }
149 }
150 break;
151 }
152 #if DEBUG_FLOW
153 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
154 current->debugID(), start->pt().fX, start->pt().fY,
155 end->pt().fX, end->pt().fY);
156 #endif
157 if (!current->addCurveTo(start, end, writer)) {
158 return false;
159 }
160 current = next;
161 start = nextStart;
162 end = nextEnd;
163 } while (!writer->isClosed() && (!unsortable || !start->starter(end)->done()));
164 if (current->activeWinding(start, end) && !writer->isClosed()) {
165 SkOpSpan* spanStart = start->starter(end);
166 if (!spanStart->done()) {
167 if (!current->addCurveTo(start, end, writer)) {
168 return false;
169 }
170 current->markDone(spanStart);
171 }
172 }
173 writer->finishContour();
174 } else {
175 SkOpSpanBase* last;
176 if (!current->markAndChaseDone(start, end, &last)) {
177 return false;
178 }
179 if (last && !last->chased()) {
180 last->setChased(true);
181 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
182 *chase.append() = last;
183 #if DEBUG_WINDING
184 SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
185 if (!last->final()) {
186 SkDebugf(" windSum=%d", last->upCast()->windSum());
187 }
188 SkDebugf("\n");
189 #endif
190 }
191 }
192 if (!findChaseOp(chase, &start, &end, ¤t)) {
193 return false;
194 }
195 SkPathOpsDebug::ShowActiveSpans(contourList);
196 if (!current) {
197 break;
198 }
199 } while (true);
200 } while (true);
201 return true;
202 }
203
204 // diagram of why this simplifcation is possible is here:
205 // https://skia.org/dev/present/pathops link at bottom of the page
206 // https://drive.google.com/file/d/0BwoLUwz9PYkHLWpsaXd0UDdaN00/view?usp=sharing
207 static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
208 // inside minuend outside minuend
209 // inside subtrahend outside subtrahend inside subtrahend outside subtrahend
210 {{ kDifference_SkPathOp, kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
211 {{ kIntersect_SkPathOp, kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
212 {{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp, kIntersect_SkPathOp }},
213 {{ kXOR_SkPathOp, kXOR_SkPathOp }, { kXOR_SkPathOp, kXOR_SkPathOp }},
214 {{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp, kDifference_SkPathOp }},
215 };
216
217 static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
218 {{ false, false }, { true, false }}, // diff
219 {{ false, false }, { false, true }}, // sect
220 {{ false, true }, { true, true }}, // union
221 {{ false, true }, { true, false }}, // xor
222 {{ false, true }, { false, false }}, // rev diff
223 };
224
225 #if DEBUG_T_SECT_LOOP_COUNT
226
227 #include "SkMutex.h"
228
229 SK_DECLARE_STATIC_MUTEX(debugWorstLoop);
230
231 SkOpGlobalState debugWorstState(nullptr, nullptr SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr));
232
ReportPathOpsDebugging()233 void ReportPathOpsDebugging() {
234 debugWorstState.debugLoopReport();
235 }
236
237 extern void (*gVerboseFinalize)();
238
239 #endif
240
OpDebug(const SkPath & one,const SkPath & two,SkPathOp op,SkPath * result SkDEBUGPARAMS (bool skipAssert)SkDEBUGPARAMS (const char * testName))241 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result
242 SkDEBUGPARAMS(bool skipAssert) SkDEBUGPARAMS(const char* testName)) {
243 #if DEBUG_DUMP_VERIFY
244 #ifndef SK_DEBUG
245 const char* testName = "release";
246 #endif
247 if (SkPathOpsDebug::gDumpOp) {
248 SkPathOpsDebug::DumpOp(one, two, op, testName);
249 }
250 #endif
251 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
252 bool inverseFill = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()];
253 SkPath::FillType fillType = inverseFill ? SkPath::kInverseEvenOdd_FillType :
254 SkPath::kEvenOdd_FillType;
255 SkRect rect1, rect2;
256 if (kIntersect_SkPathOp == op && one.isRect(&rect1) && two.isRect(&rect2)) {
257 result->reset();
258 result->setFillType(fillType);
259 if (rect1.intersect(rect2)) {
260 result->addRect(rect1);
261 }
262 return true;
263 }
264 if (one.isEmpty() || two.isEmpty()) {
265 SkPath work;
266 switch (op) {
267 case kIntersect_SkPathOp:
268 break;
269 case kUnion_SkPathOp:
270 case kXOR_SkPathOp:
271 work = one.isEmpty() ? two : one;
272 break;
273 case kDifference_SkPathOp:
274 if (!one.isEmpty()) {
275 work = one;
276 }
277 break;
278 case kReverseDifference_SkPathOp:
279 if (!two.isEmpty()) {
280 work = two;
281 }
282 break;
283 default:
284 SkASSERT(0); // unhandled case
285 }
286 if (inverseFill != work.isInverseFillType()) {
287 work.toggleInverseFillType();
288 }
289 return Simplify(work, result);
290 }
291 SkSTArenaAlloc<4096> allocator; // FIXME: add a constant expression here, tune
292 SkOpContour contour;
293 SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
294 SkOpGlobalState globalState(contourList, &allocator
295 SkDEBUGPARAMS(skipAssert) SkDEBUGPARAMS(testName));
296 SkOpCoincidence coincidence(&globalState);
297 const SkPath* minuend = &one;
298 const SkPath* subtrahend = &two;
299 if (op == kReverseDifference_SkPathOp) {
300 using std::swap;
301 swap(minuend, subtrahend);
302 op = kDifference_SkPathOp;
303 }
304 #if DEBUG_SORT
305 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
306 #endif
307 // turn path into list of segments
308 SkOpEdgeBuilder builder(*minuend, contourList, &globalState);
309 if (builder.unparseable()) {
310 return false;
311 }
312 const int xorMask = builder.xorMask();
313 builder.addOperand(*subtrahend);
314 if (!builder.finish()) {
315 return false;
316 }
317 #if DEBUG_DUMP_SEGMENTS
318 contourList->dumpSegments("seg", op);
319 #endif
320
321 const int xorOpMask = builder.xorMask();
322 if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
323 xorOpMask == kEvenOdd_PathOpsMask)) {
324 result->reset();
325 result->setFillType(fillType);
326 return true;
327 }
328 // find all intersections between segments
329 SkOpContour* current = contourList;
330 do {
331 SkOpContour* next = current;
332 while (AddIntersectTs(current, next, &coincidence)
333 && (next = next->next()))
334 ;
335 } while ((current = current->next()));
336 #if DEBUG_VALIDATE
337 globalState.setPhase(SkOpPhase::kWalking);
338 #endif
339 bool success = HandleCoincidence(contourList, &coincidence);
340 #if DEBUG_COIN
341 globalState.debugAddToGlobalCoinDicts();
342 #endif
343 if (!success) {
344 return false;
345 }
346 #if DEBUG_ALIGNMENT
347 contourList->dumpSegments("aligned");
348 #endif
349 // construct closed contours
350 SkPath original = *result;
351 result->reset();
352 result->setFillType(fillType);
353 SkPathWriter wrapper(*result);
354 if (!bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper)) {
355 *result = original;
356 return false;
357 }
358 wrapper.assemble(); // if some edges could not be resolved, assemble remaining
359 #if DEBUG_T_SECT_LOOP_COUNT
360 {
361 SkAutoMutexAcquire autoM(debugWorstLoop);
362 if (!gVerboseFinalize) {
363 gVerboseFinalize = &ReportPathOpsDebugging;
364 }
365 debugWorstState.debugDoYourWorst(&globalState);
366 }
367 #endif
368 return true;
369 }
370
Op(const SkPath & one,const SkPath & two,SkPathOp op,SkPath * result)371 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
372 #if DEBUG_DUMP_VERIFY
373 if (SkPathOpsDebug::gVerifyOp) {
374 if (!OpDebug(one, two, op, result SkDEBUGPARAMS(false) SkDEBUGPARAMS(nullptr))) {
375 SkPathOpsDebug::ReportOpFail(one, two, op);
376 return false;
377 }
378 SkPathOpsDebug::VerifyOp(one, two, op, *result);
379 return true;
380 }
381 #endif
382 return OpDebug(one, two, op, result SkDEBUGPARAMS(true) SkDEBUGPARAMS(nullptr));
383 }
384