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 "SkOpEdgeBuilder.h"
9 #include "SkPathOpsCommon.h"
10 #include "SkPathWriter.h"
11
findChaseOp(SkTDArray<SkOpSpan * > & chase,int * tIndex,int * endIndex)12 static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) {
13 while (chase.count()) {
14 SkOpSpan* span;
15 chase.pop(&span);
16 const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
17 SkOpSegment* segment = backPtr.fOther;
18 *tIndex = backPtr.fOtherIndex;
19 bool sortable = true;
20 bool done = true;
21 *endIndex = -1;
22 if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
23 &sortable)) {
24 if (last->unorderable()) {
25 continue;
26 }
27 *tIndex = last->start();
28 *endIndex = last->end();
29 #if TRY_ROTATE
30 *chase.insert(0) = span;
31 #else
32 *chase.append() = span;
33 #endif
34 return last->segment();
35 }
36 if (done) {
37 continue;
38 }
39 if (!sortable) {
40 continue;
41 }
42 // find first angle, initialize winding to computed fWindSum
43 const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
44 if (!angle) {
45 continue;
46 }
47 const SkOpAngle* firstAngle = angle;
48 SkDEBUGCODE(bool loop = false);
49 int winding;
50 do {
51 angle = angle->next();
52 SkASSERT(angle != firstAngle || !loop);
53 SkDEBUGCODE(loop |= angle == firstAngle);
54 segment = angle->segment();
55 winding = segment->windSum(angle);
56 } while (winding == SK_MinS32);
57 int sumMiWinding = segment->updateWindingReverse(angle);
58 int sumSuWinding = segment->updateOppWindingReverse(angle);
59 if (segment->operand()) {
60 SkTSwap<int>(sumMiWinding, sumSuWinding);
61 }
62 SkOpSegment* first = NULL;
63 while ((angle = angle->next()) != firstAngle) {
64 segment = angle->segment();
65 int start = angle->start();
66 int end = angle->end();
67 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
68 segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
69 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
70 if (!segment->done(angle)) {
71 if (!first) {
72 first = segment;
73 *tIndex = start;
74 *endIndex = end;
75 }
76 // OPTIMIZATION: should this also add to the chase?
77 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
78 oppSumWinding, angle);
79 }
80 }
81 if (first) {
82 #if TRY_ROTATE
83 *chase.insert(0) = span;
84 #else
85 *chase.append() = span;
86 #endif
87 return first;
88 }
89 }
90 return NULL;
91 }
92
93 /*
94 static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
95 bool windingIsOp, PathOp op) {
96 bool active = windingIsActive(winding, spanWinding);
97 if (!active) {
98 return false;
99 }
100 if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
101 switch (op) {
102 case kIntersect_Op:
103 case kUnion_Op:
104 return true;
105 case kDifference_Op: {
106 int absSpan = abs(spanWinding);
107 int absOpp = abs(oppSpanWinding);
108 return windingIsOp ? absSpan < absOpp : absSpan > absOpp;
109 }
110 case kXor_Op:
111 return spanWinding != oppSpanWinding;
112 default:
113 SkASSERT(0);
114 }
115 }
116 bool opActive = oppWinding != 0;
117 return gOpLookup[op][opActive][windingIsOp];
118 }
119 */
120
bridgeOp(SkTArray<SkOpContour *,true> & contourList,const SkPathOp op,const int xorMask,const int xorOpMask,SkPathWriter * simple)121 static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op,
122 const int xorMask, const int xorOpMask, SkPathWriter* simple) {
123 bool firstContour = true;
124 bool unsortable = false;
125 bool topUnsortable = false;
126 bool firstPass = true;
127 SkPoint lastTopLeft;
128 SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
129 do {
130 int index, endIndex;
131 bool topDone;
132 bool onlyVertical = false;
133 lastTopLeft = topLeft;
134 SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
135 &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
136 if (!current) {
137 if ((!topUnsortable || firstPass) && !topDone) {
138 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
139 if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) {
140 if (firstPass) {
141 firstPass = false;
142 } else {
143 break;
144 }
145 }
146 topLeft.fX = topLeft.fY = SK_ScalarMin;
147 continue;
148 }
149 break;
150 } else if (onlyVertical) {
151 break;
152 }
153 firstPass = !topUnsortable || lastTopLeft != topLeft;
154 SkTDArray<SkOpSpan*> chase;
155 do {
156 if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
157 do {
158 if (!unsortable && current->done()) {
159 break;
160 }
161 SkASSERT(unsortable || !current->done());
162 int nextStart = index;
163 int nextEnd = endIndex;
164 SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
165 &unsortable, op, xorMask, xorOpMask);
166 if (!next) {
167 if (!unsortable && simple->hasMove()
168 && current->verb() != SkPath::kLine_Verb
169 && !simple->isClosed()) {
170 current->addCurveTo(index, endIndex, simple, true);
171 #if DEBUG_ACTIVE_SPANS
172 if (!simple->isClosed()) {
173 DebugShowActiveSpans(contourList);
174 }
175 #endif
176 // SkASSERT(simple->isClosed());
177 }
178 break;
179 }
180 #if DEBUG_FLOW
181 SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
182 current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
183 current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
184 #endif
185 current->addCurveTo(index, endIndex, simple, true);
186 current = next;
187 index = nextStart;
188 endIndex = nextEnd;
189 } while (!simple->isClosed() && (!unsortable
190 || !current->done(SkMin32(index, endIndex))));
191 if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
192 // FIXME : add to simplify, xor cpaths
193 int min = SkMin32(index, endIndex);
194 if (!unsortable && !simple->isEmpty()) {
195 unsortable = current->checkSmall(min);
196 }
197 if (!current->done(min)) {
198 current->addCurveTo(index, endIndex, simple, true);
199 current->markDoneBinary(min);
200 }
201 }
202 simple->close();
203 } else {
204 SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
205 if (last && !last->fChased && !last->fLoop) {
206 last->fChased = true;
207 SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
208 *chase.append() = last;
209 #if DEBUG_WINDING
210 SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
211 last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum,
212 last->fSmall);
213 #endif
214 }
215 }
216 current = findChaseOp(chase, &index, &endIndex);
217 #if DEBUG_ACTIVE_SPANS
218 DebugShowActiveSpans(contourList);
219 #endif
220 if (!current) {
221 break;
222 }
223 } while (true);
224 } while (true);
225 return simple->someAssemblyRequired();
226 }
227
228 // pretty picture:
229 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
230 static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = {
231 // inside minuend outside minuend
232 // inside subtrahend outside subtrahend inside subtrahend outside subtrahend
233 {{ kDifference_PathOp, kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }},
234 {{ kIntersect_PathOp, kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }},
235 {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp, kIntersect_PathOp }},
236 {{ kXOR_PathOp, kXOR_PathOp }, { kXOR_PathOp, kXOR_PathOp }},
237 {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp, kDifference_PathOp }},
238 };
239
240 static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
241 {{ false, false }, { true, false }}, // diff
242 {{ false, false }, { false, true }}, // sect
243 {{ false, true }, { true, true }}, // union
244 {{ false, true }, { true, false }}, // xor
245 {{ false, true }, { false, false }}, // rev diff
246 };
247
Op(const SkPath & one,const SkPath & two,SkPathOp op,SkPath * result)248 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
249 #if DEBUG_SHOW_TEST_NAME
250 char* debugName = DEBUG_FILENAME_STRING;
251 if (debugName && debugName[0]) {
252 SkPathOpsDebug::BumpTestName(debugName);
253 SkPathOpsDebug::ShowPath(one, two, op, debugName);
254 }
255 #endif
256 op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
257 SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
258 ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
259 const SkPath* minuend = &one;
260 const SkPath* subtrahend = &two;
261 if (op == kReverseDifference_PathOp) {
262 minuend = &two;
263 subtrahend = &one;
264 op = kDifference_PathOp;
265 }
266 #if DEBUG_SORT || DEBUG_SWAP_TOP
267 SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
268 #endif
269 // turn path into list of segments
270 SkTArray<SkOpContour> contours;
271 // FIXME: add self-intersecting cubics' T values to segment
272 SkOpEdgeBuilder builder(*minuend, contours);
273 const int xorMask = builder.xorMask();
274 builder.addOperand(*subtrahend);
275 if (!builder.finish()) {
276 return false;
277 }
278 result->reset();
279 result->setFillType(fillType);
280 const int xorOpMask = builder.xorMask();
281 SkTArray<SkOpContour*, true> contourList;
282 MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask,
283 xorOpMask == kEvenOdd_PathOpsMask);
284 SkOpContour** currentPtr = contourList.begin();
285 if (!currentPtr) {
286 return true;
287 }
288 SkOpContour** listEnd = contourList.end();
289 // find all intersections between segments
290 do {
291 SkOpContour** nextPtr = currentPtr;
292 SkOpContour* current = *currentPtr++;
293 if (current->containsCubics()) {
294 AddSelfIntersectTs(current);
295 }
296 SkOpContour* next;
297 do {
298 next = *nextPtr++;
299 } while (AddIntersectTs(current, next) && nextPtr != listEnd);
300 } while (currentPtr != listEnd);
301 // eat through coincident edges
302
303 int total = 0;
304 int index;
305 for (index = 0; index < contourList.count(); ++index) {
306 total += contourList[index]->segments().count();
307 }
308 if (!HandleCoincidence(&contourList, total)) {
309 return false;
310 }
311 // construct closed contours
312 SkPathWriter wrapper(*result);
313 bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
314 { // if some edges could not be resolved, assemble remaining fragments
315 SkPath temp;
316 temp.setFillType(fillType);
317 SkPathWriter assembled(temp);
318 Assemble(wrapper, &assembled);
319 *result = *assembled.nativePath();
320 result->setFillType(fillType);
321 }
322 return true;
323 }
324