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 "SkIntersections.h"
8 #include "SkOpSegment.h"
9 #include "SkPathWriter.h"
10 #include "SkTSort.h"
11
12 #define F (false) // discard the edge
13 #define T (true) // keep the edge
14
15 static const bool gUnaryActiveEdge[2][2] = {
16 // from=0 from=1
17 // to=0,1 to=0,1
18 {F, T}, {T, F},
19 };
20
21 static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = {
22 // miFrom=0 miFrom=1
23 // miTo=0 miTo=1 miTo=0 miTo=1
24 // suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1
25 // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1
26 {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
27 {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
28 {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
29 {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
30 };
31
32 #undef F
33 #undef T
34
35 enum {
36 kOutsideTrackedTCount = 16, // FIXME: determine what this should be
37 kMissingSpanCount = 4, // FIXME: determine what this should be
38 };
39
40 // note that this follows the same logic flow as build angles
activeAngle(int index,int * done,SkTArray<SkOpAngle,true> * angles)41 bool SkOpSegment::activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
42 if (activeAngleInner(index, done, angles)) {
43 return true;
44 }
45 double referenceT = fTs[index].fT;
46 int lesser = index;
47 while (--lesser >= 0
48 && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
49 if (activeAngleOther(lesser, done, angles)) {
50 return true;
51 }
52 }
53 do {
54 if (activeAngleOther(index, done, angles)) {
55 return true;
56 }
57 if (++index == fTs.count()) {
58 break;
59 }
60 if (fTs[index - 1].fTiny) {
61 referenceT = fTs[index].fT;
62 continue;
63 }
64 } while (precisely_negative(fTs[index].fT - referenceT));
65 return false;
66 }
67
activeAngleOther(int index,int * done,SkTArray<SkOpAngle,true> * angles)68 bool SkOpSegment::activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
69 SkOpSpan* span = &fTs[index];
70 SkOpSegment* other = span->fOther;
71 int oIndex = span->fOtherIndex;
72 return other->activeAngleInner(oIndex, done, angles);
73 }
74
activeAngleInner(int index,int * done,SkTArray<SkOpAngle,true> * angles)75 bool SkOpSegment::activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
76 int next = nextExactSpan(index, 1);
77 if (next > 0) {
78 SkOpSpan& upSpan = fTs[index];
79 if (upSpan.fWindValue || upSpan.fOppValue) {
80 addAngle(angles, index, next);
81 if (upSpan.fDone || upSpan.fUnsortableEnd) {
82 (*done)++;
83 } else if (upSpan.fWindSum != SK_MinS32) {
84 return true;
85 }
86 } else if (!upSpan.fDone) {
87 upSpan.fDone = true;
88 fDoneSpans++;
89 }
90 }
91 int prev = nextExactSpan(index, -1);
92 // edge leading into junction
93 if (prev >= 0) {
94 SkOpSpan& downSpan = fTs[prev];
95 if (downSpan.fWindValue || downSpan.fOppValue) {
96 addAngle(angles, index, prev);
97 if (downSpan.fDone) {
98 (*done)++;
99 } else if (downSpan.fWindSum != SK_MinS32) {
100 return true;
101 }
102 } else if (!downSpan.fDone) {
103 downSpan.fDone = true;
104 fDoneSpans++;
105 }
106 }
107 return false;
108 }
109
activeLeftTop(bool onlySortable,int * firstT) const110 SkPoint SkOpSegment::activeLeftTop(bool onlySortable, int* firstT) const {
111 SkASSERT(!done());
112 SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
113 int count = fTs.count();
114 // see if either end is not done since we want smaller Y of the pair
115 bool lastDone = true;
116 bool lastUnsortable = false;
117 double lastT = -1;
118 for (int index = 0; index < count; ++index) {
119 const SkOpSpan& span = fTs[index];
120 if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
121 goto next;
122 }
123 if (span.fDone && lastDone) {
124 goto next;
125 }
126 if (approximately_negative(span.fT - lastT)) {
127 goto next;
128 }
129 {
130 const SkPoint& xy = xyAtT(&span);
131 if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
132 topPt = xy;
133 if (firstT) {
134 *firstT = index;
135 }
136 }
137 if (fVerb != SkPath::kLine_Verb && !lastDone) {
138 SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT, span.fT);
139 if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
140 && topPt.fX > curveTop.fX)) {
141 topPt = curveTop;
142 if (firstT) {
143 *firstT = index;
144 }
145 }
146 }
147 lastT = span.fT;
148 }
149 next:
150 lastDone = span.fDone;
151 lastUnsortable = span.fUnsortableEnd;
152 }
153 return topPt;
154 }
155
activeOp(int index,int endIndex,int xorMiMask,int xorSuMask,SkPathOp op)156 bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op) {
157 int sumMiWinding = updateWinding(endIndex, index);
158 int sumSuWinding = updateOppWinding(endIndex, index);
159 if (fOperand) {
160 SkTSwap<int>(sumMiWinding, sumSuWinding);
161 }
162 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
163 return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding,
164 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
165 }
166
activeOp(int xorMiMask,int xorSuMask,int index,int endIndex,SkPathOp op,int * sumMiWinding,int * sumSuWinding,int * maxWinding,int * sumWinding,int * oppMaxWinding,int * oppSumWinding)167 bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
168 int* sumMiWinding, int* sumSuWinding,
169 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
170 setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
171 maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
172 bool miFrom;
173 bool miTo;
174 bool suFrom;
175 bool suTo;
176 if (operand()) {
177 miFrom = (*oppMaxWinding & xorMiMask) != 0;
178 miTo = (*oppSumWinding & xorMiMask) != 0;
179 suFrom = (*maxWinding & xorSuMask) != 0;
180 suTo = (*sumWinding & xorSuMask) != 0;
181 } else {
182 miFrom = (*maxWinding & xorMiMask) != 0;
183 miTo = (*sumWinding & xorMiMask) != 0;
184 suFrom = (*oppMaxWinding & xorSuMask) != 0;
185 suTo = (*oppSumWinding & xorSuMask) != 0;
186 }
187 bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
188 #if DEBUG_ACTIVE_OP
189 SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__,
190 SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
191 #endif
192 return result;
193 }
194
activeWinding(int index,int endIndex)195 bool SkOpSegment::activeWinding(int index, int endIndex) {
196 int sumWinding = updateWinding(endIndex, index);
197 int maxWinding;
198 return activeWinding(index, endIndex, &maxWinding, &sumWinding);
199 }
200
activeWinding(int index,int endIndex,int * maxWinding,int * sumWinding)201 bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding) {
202 setUpWinding(index, endIndex, maxWinding, sumWinding);
203 bool from = *maxWinding != 0;
204 bool to = *sumWinding != 0;
205 bool result = gUnaryActiveEdge[from][to];
206 return result;
207 }
208
addAngle(SkTArray<SkOpAngle,true> * anglesPtr,int start,int end) const209 void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const {
210 SkASSERT(start != end);
211 SkOpAngle& angle = anglesPtr->push_back();
212 angle.set(this, start, end);
213 }
214
addCancelOutsides(const SkPoint & startPt,const SkPoint & endPt,SkOpSegment * other)215 void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt,
216 SkOpSegment* other) {
217 int tIndex = -1;
218 int tCount = fTs.count();
219 int oIndex = -1;
220 int oCount = other->fTs.count();
221 do {
222 ++tIndex;
223 } while (startPt != fTs[tIndex].fPt && tIndex < tCount);
224 int tIndexStart = tIndex;
225 do {
226 ++oIndex;
227 } while (endPt != other->fTs[oIndex].fPt && oIndex < oCount);
228 int oIndexStart = oIndex;
229 const SkPoint* nextPt;
230 do {
231 nextPt = &fTs[++tIndex].fPt;
232 SkASSERT(fTs[tIndex].fT < 1 || startPt != *nextPt);
233 } while (startPt == *nextPt);
234 double nextT = fTs[tIndex].fT;
235 const SkPoint* oNextPt;
236 do {
237 oNextPt = &other->fTs[++oIndex].fPt;
238 SkASSERT(other->fTs[oIndex].fT < 1 || endPt != *oNextPt);
239 } while (endPt == *oNextPt);
240 double oNextT = other->fTs[oIndex].fT;
241 // at this point, spans before and after are at:
242 // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
243 // if tIndexStart == 0, no prior span
244 // if nextT == 1, no following span
245
246 // advance the span with zero winding
247 // if the following span exists (not past the end, non-zero winding)
248 // connect the two edges
249 if (!fTs[tIndexStart].fWindValue) {
250 if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
251 #if DEBUG_CONCIDENT
252 SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
253 __FUNCTION__, fID, other->fID, tIndexStart - 1,
254 fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
255 xyAtT(tIndexStart).fY);
256 #endif
257 addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false,
258 fTs[tIndexStart].fPt);
259 }
260 if (nextT < 1 && fTs[tIndex].fWindValue) {
261 #if DEBUG_CONCIDENT
262 SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
263 __FUNCTION__, fID, other->fID, tIndex,
264 fTs[tIndex].fT, xyAtT(tIndex).fX,
265 xyAtT(tIndex).fY);
266 #endif
267 addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
268 }
269 } else {
270 SkASSERT(!other->fTs[oIndexStart].fWindValue);
271 if (oIndexStart > 0 && other->fTs[oIndexStart - 1].fWindValue) {
272 #if DEBUG_CONCIDENT
273 SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
274 __FUNCTION__, fID, other->fID, oIndexStart - 1,
275 other->fTs[oIndexStart].fT, other->xyAtT(oIndexStart).fX,
276 other->xyAtT(oIndexStart).fY);
277 other->debugAddTPair(other->fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
278 #endif
279 }
280 if (oNextT < 1 && other->fTs[oIndex].fWindValue) {
281 #if DEBUG_CONCIDENT
282 SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
283 __FUNCTION__, fID, other->fID, oIndex,
284 other->fTs[oIndex].fT, other->xyAtT(oIndex).fX,
285 other->xyAtT(oIndex).fY);
286 other->debugAddTPair(other->fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
287 #endif
288 }
289 }
290 }
291
addCoinOutsides(const SkPoint & startPt,const SkPoint & endPt,SkOpSegment * other)292 void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt,
293 SkOpSegment* other) {
294 // walk this to startPt
295 // walk other to startPt
296 // if either is > 0, add a pointer to the other, copying adjacent winding
297 int tIndex = -1;
298 int oIndex = -1;
299 do {
300 ++tIndex;
301 } while (startPt != fTs[tIndex].fPt);
302 do {
303 ++oIndex;
304 } while (startPt != other->fTs[oIndex].fPt);
305 if (tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) {
306 addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt);
307 }
308 SkPoint nextPt = startPt;
309 do {
310 const SkPoint* workPt;
311 do {
312 workPt = &fTs[++tIndex].fPt;
313 } while (nextPt == *workPt);
314 do {
315 workPt = &other->fTs[++oIndex].fPt;
316 } while (nextPt == *workPt);
317 nextPt = *workPt;
318 double tStart = fTs[tIndex].fT;
319 double oStart = other->fTs[oIndex].fT;
320 if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) {
321 break;
322 }
323 addTPair(tStart, other, oStart, false, nextPt);
324 } while (endPt != nextPt);
325 }
326
addCubic(const SkPoint pts[4],bool operand,bool evenOdd)327 void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
328 init(pts, SkPath::kCubic_Verb, operand, evenOdd);
329 fBounds.setCubicBounds(pts);
330 }
331
addCurveTo(int start,int end,SkPathWriter * path,bool active) const332 void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active) const {
333 SkPoint edge[4];
334 const SkPoint* ePtr;
335 int lastT = fTs.count() - 1;
336 if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
337 ePtr = fPts;
338 } else {
339 // OPTIMIZE? if not active, skip remainder and return xyAtT(end)
340 subDivide(start, end, edge);
341 ePtr = edge;
342 }
343 if (active) {
344 bool reverse = ePtr == fPts && start != 0;
345 if (reverse) {
346 path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
347 switch (fVerb) {
348 case SkPath::kLine_Verb:
349 path->deferredLine(ePtr[0]);
350 break;
351 case SkPath::kQuad_Verb:
352 path->quadTo(ePtr[1], ePtr[0]);
353 break;
354 case SkPath::kCubic_Verb:
355 path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
356 break;
357 default:
358 SkASSERT(0);
359 }
360 // return ePtr[0];
361 } else {
362 path->deferredMoveLine(ePtr[0]);
363 switch (fVerb) {
364 case SkPath::kLine_Verb:
365 path->deferredLine(ePtr[1]);
366 break;
367 case SkPath::kQuad_Verb:
368 path->quadTo(ePtr[1], ePtr[2]);
369 break;
370 case SkPath::kCubic_Verb:
371 path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
372 break;
373 default:
374 SkASSERT(0);
375 }
376 }
377 }
378 // return ePtr[SkPathOpsVerbToPoints(fVerb)];
379 }
380
addLine(const SkPoint pts[2],bool operand,bool evenOdd)381 void SkOpSegment::addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
382 init(pts, SkPath::kLine_Verb, operand, evenOdd);
383 fBounds.set(pts, 2);
384 }
385
386 // add 2 to edge or out of range values to get T extremes
addOtherT(int index,double otherT,int otherIndex)387 void SkOpSegment::addOtherT(int index, double otherT, int otherIndex) {
388 SkOpSpan& span = fTs[index];
389 if (precisely_zero(otherT)) {
390 otherT = 0;
391 } else if (precisely_equal(otherT, 1)) {
392 otherT = 1;
393 }
394 span.fOtherT = otherT;
395 span.fOtherIndex = otherIndex;
396 }
397
addQuad(const SkPoint pts[3],bool operand,bool evenOdd)398 void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
399 init(pts, SkPath::kQuad_Verb, operand, evenOdd);
400 fBounds.setQuadBounds(pts);
401 }
402
403 // Defer all coincident edge processing until
404 // after normal intersections have been computed
405
406 // no need to be tricky; insert in normal T order
407 // resolve overlapping ts when considering coincidence later
408
409 // add non-coincident intersection. Resulting edges are sorted in T.
addT(SkOpSegment * other,const SkPoint & pt,double newT)410 int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) {
411 if (precisely_zero(newT)) {
412 newT = 0;
413 } else if (precisely_equal(newT, 1)) {
414 newT = 1;
415 }
416 // FIXME: in the pathological case where there is a ton of intercepts,
417 // binary search?
418 int insertedAt = -1;
419 size_t tCount = fTs.count();
420 const SkPoint& firstPt = fPts[0];
421 const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
422 for (size_t index = 0; index < tCount; ++index) {
423 // OPTIMIZATION: if there are three or more identical Ts, then
424 // the fourth and following could be further insertion-sorted so
425 // that all the edges are clockwise or counterclockwise.
426 // This could later limit segment tests to the two adjacent
427 // neighbors, although it doesn't help with determining which
428 // circular direction to go in.
429 const SkOpSpan& span = fTs[index];
430 if (newT < span.fT) {
431 insertedAt = index;
432 break;
433 }
434 if (newT == span.fT) {
435 if (pt == span.fPt) {
436 insertedAt = index;
437 break;
438 }
439 if ((pt == firstPt && newT == 0) || (span.fPt == lastPt && newT == 1)) {
440 insertedAt = index;
441 break;
442 }
443 }
444 }
445 SkOpSpan* span;
446 if (insertedAt >= 0) {
447 span = fTs.insert(insertedAt);
448 } else {
449 insertedAt = tCount;
450 span = fTs.append();
451 }
452 span->fT = newT;
453 span->fOther = other;
454 span->fPt = pt;
455 #if 0
456 // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
457 SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
458 && approximately_equal(xyAtT(newT).fY, pt.fY));
459 #endif
460 span->fWindSum = SK_MinS32;
461 span->fOppSum = SK_MinS32;
462 span->fWindValue = 1;
463 span->fOppValue = 0;
464 span->fSmall = false;
465 span->fTiny = false;
466 span->fLoop = false;
467 if ((span->fDone = newT == 1)) {
468 ++fDoneSpans;
469 }
470 span->fUnsortableStart = false;
471 span->fUnsortableEnd = false;
472 int less = -1;
473 while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, span->fPt)) {
474 if (span[less].fDone) {
475 break;
476 }
477 double tInterval = newT - span[less].fT;
478 if (precisely_negative(tInterval)) {
479 break;
480 }
481 if (fVerb == SkPath::kCubic_Verb) {
482 double tMid = newT - tInterval / 2;
483 SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
484 if (!midPt.approximatelyEqual(xyAtT(span))) {
485 break;
486 }
487 }
488 span[less].fSmall = true;
489 bool tiny = span[less].fPt == span->fPt;
490 span[less].fTiny = tiny;
491 span[less].fDone = true;
492 if (approximately_negative(newT - span[less].fT) && tiny) {
493 if (approximately_greater_than_one(newT)) {
494 SkASSERT(&span[less] - fTs.begin() < fTs.count());
495 span[less].fUnsortableStart = true;
496 if (&span[less - 1] - fTs.begin() >= 0) {
497 span[less - 1].fUnsortableEnd = true;
498 }
499 }
500 if (approximately_less_than_zero(span[less].fT)) {
501 SkASSERT(&span[less + 1] - fTs.begin() < fTs.count());
502 SkASSERT(&span[less] - fTs.begin() >= 0);
503 span[less + 1].fUnsortableStart = true;
504 span[less].fUnsortableEnd = true;
505 }
506 }
507 ++fDoneSpans;
508 --less;
509 }
510 int more = 1;
511 while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, span->fPt)) {
512 if (span[more - 1].fDone) {
513 break;
514 }
515 double tEndInterval = span[more].fT - newT;
516 if (precisely_negative(tEndInterval)) {
517 if ((span->fTiny = span[more].fTiny)) {
518 span->fDone = true;
519 ++fDoneSpans;
520 }
521 break;
522 }
523 if (fVerb == SkPath::kCubic_Verb) {
524 double tMid = newT - tEndInterval / 2;
525 SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
526 if (!midEndPt.approximatelyEqual(xyAtT(span))) {
527 break;
528 }
529 }
530 span[more - 1].fSmall = true;
531 bool tiny = span[more].fPt == span->fPt;
532 span[more - 1].fTiny = tiny;
533 span[more - 1].fDone = true;
534 if (approximately_negative(span[more].fT - newT) && tiny) {
535 if (approximately_greater_than_one(span[more].fT)) {
536 span[more + 1].fUnsortableStart = true;
537 span[more].fUnsortableEnd = true;
538 }
539 if (approximately_less_than_zero(newT)) {
540 span[more].fUnsortableStart = true;
541 span[more - 1].fUnsortableEnd = true;
542 }
543 }
544 ++fDoneSpans;
545 ++more;
546 }
547 return insertedAt;
548 }
549
550 // set spans from start to end to decrement by one
551 // note this walks other backwards
552 // FIXME: there's probably an edge case that can be constructed where
553 // two span in one segment are separated by float epsilon on one span but
554 // not the other, if one segment is very small. For this
555 // case the counts asserted below may or may not be enough to separate the
556 // spans. Even if the counts work out, what if the spans aren't correctly
557 // sorted? It feels better in such a case to match the span's other span
558 // pointer since both coincident segments must contain the same spans.
559 // FIXME? It seems that decrementing by one will fail for complex paths that
560 // have three or more coincident edges. Shouldn't this subtract the difference
561 // between the winding values?
562 /* |--> |-->
563 this 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4
564 other 2<<<<1<<<<0 2<<<<1<<<<0 2<<<<1<<<<0
565 ^ ^ <--| <--|
566 startPt endPt test/oTest first pos test/oTest final pos
567 */
addTCancel(const SkPoint & startPt,const SkPoint & endPt,SkOpSegment * other)568 void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) {
569 bool binary = fOperand != other->fOperand;
570 int index = 0;
571 while (startPt != fTs[index].fPt) {
572 SkASSERT(index < fTs.count());
573 ++index;
574 }
575 while (index > 0 && fTs[index].fT == fTs[index - 1].fT) {
576 --index;
577 }
578 int oIndex = other->fTs.count();
579 while (startPt != other->fTs[--oIndex].fPt) { // look for startPt match
580 SkASSERT(oIndex > 0);
581 }
582 double oStartT = other->fTs[oIndex].fT;
583 // look for first point beyond match
584 while (startPt == other->fTs[--oIndex].fPt || oStartT == other->fTs[oIndex].fT) {
585 SkASSERT(oIndex > 0);
586 }
587 SkOpSpan* test = &fTs[index];
588 SkOpSpan* oTest = &other->fTs[oIndex];
589 SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
590 SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
591 do {
592 SkASSERT(test->fT < 1);
593 SkASSERT(oTest->fT < 1);
594 bool decrement = test->fWindValue && oTest->fWindValue;
595 bool track = test->fWindValue || oTest->fWindValue;
596 bool bigger = test->fWindValue >= oTest->fWindValue;
597 const SkPoint& testPt = test->fPt;
598 double testT = test->fT;
599 const SkPoint& oTestPt = oTest->fPt;
600 double oTestT = oTest->fT;
601 do {
602 if (decrement) {
603 if (binary && bigger) {
604 test->fOppValue--;
605 } else {
606 decrementSpan(test);
607 }
608 } else if (track) {
609 TrackOutsidePair(&outsidePts, testPt, oTestPt);
610 }
611 SkASSERT(index < fTs.count() - 1);
612 test = &fTs[++index];
613 } while (testPt == test->fPt || testT == test->fT);
614 SkDEBUGCODE(int originalWindValue = oTest->fWindValue);
615 do {
616 SkASSERT(oTest->fT < 1);
617 SkASSERT(originalWindValue == oTest->fWindValue);
618 if (decrement) {
619 if (binary && !bigger) {
620 oTest->fOppValue--;
621 } else {
622 other->decrementSpan(oTest);
623 }
624 } else if (track) {
625 TrackOutsidePair(&oOutsidePts, oTestPt, testPt);
626 }
627 if (!oIndex) {
628 break;
629 }
630 oTest = &other->fTs[--oIndex];
631 } while (oTestPt == oTest->fPt || oTestT == oTest->fT);
632 } while (endPt != test->fPt && test->fT < 1);
633 // FIXME: determine if canceled edges need outside ts added
634 int outCount = outsidePts.count();
635 if (!done() && outCount) {
636 addCancelOutsides(outsidePts[0], outsidePts[1], other);
637 if (outCount > 2) {
638 addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other);
639 }
640 }
641 if (!other->done() && oOutsidePts.count()) {
642 other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this);
643 }
644 }
645
addSelfT(SkOpSegment * other,const SkPoint & pt,double newT)646 int SkOpSegment::addSelfT(SkOpSegment* other, const SkPoint& pt, double newT) {
647 // if the tail nearly intersects itself but not quite, the caller records this separately
648 int result = addT(other, pt, newT);
649 SkOpSpan* span = &fTs[result];
650 span->fLoop = true;
651 return result;
652 }
653
bumpCoincidentThis(const SkOpSpan & oTest,bool binary,int * indexPtr,SkTArray<SkPoint,true> * outsideTs)654 void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr,
655 SkTArray<SkPoint, true>* outsideTs) {
656 int index = *indexPtr;
657 int oWindValue = oTest.fWindValue;
658 int oOppValue = oTest.fOppValue;
659 if (binary) {
660 SkTSwap<int>(oWindValue, oOppValue);
661 }
662 SkOpSpan* const test = &fTs[index];
663 SkOpSpan* end = test;
664 const SkPoint& oStartPt = oTest.fPt;
665 do {
666 if (bumpSpan(end, oWindValue, oOppValue)) {
667 TrackOutside(outsideTs, oStartPt);
668 }
669 end = &fTs[++index];
670 } while ((end->fPt == test->fPt || end->fT == test->fT) && end->fT < 1);
671 *indexPtr = index;
672 }
673
674 // because of the order in which coincidences are resolved, this and other
675 // may not have the same intermediate points. Compute the corresponding
676 // intermediate T values (using this as the master, other as the follower)
677 // and walk other conditionally -- hoping that it catches up in the end
bumpCoincidentOther(const SkOpSpan & test,int * oIndexPtr,SkTArray<SkPoint,true> * oOutsidePts)678 void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
679 SkTArray<SkPoint, true>* oOutsidePts) {
680 int oIndex = *oIndexPtr;
681 SkOpSpan* const oTest = &fTs[oIndex];
682 SkOpSpan* oEnd = oTest;
683 const SkPoint& startPt = test.fPt;
684 const SkPoint& oStartPt = oTest->fPt;
685 double oStartT = oTest->fT;
686 if (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
687 TrackOutside(oOutsidePts, startPt);
688 }
689 while (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
690 zeroSpan(oEnd);
691 oEnd = &fTs[++oIndex];
692 }
693 *oIndexPtr = oIndex;
694 }
695
696 // FIXME: need to test this case:
697 // contourA has two segments that are coincident
698 // contourB has two segments that are coincident in the same place
699 // each ends up with +2/0 pairs for winding count
700 // since logic below doesn't transfer count (only increments/decrements) can this be
701 // resolved to +4/0 ?
702
703 // set spans from start to end to increment the greater by one and decrement
704 // the lesser
addTCoincident(const SkPoint & startPt,const SkPoint & endPt,double endT,SkOpSegment * other)705 void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
706 SkOpSegment* other) {
707 bool binary = fOperand != other->fOperand;
708 int index = 0;
709 while (startPt != fTs[index].fPt) {
710 SkASSERT(index < fTs.count());
711 ++index;
712 }
713 double startT = fTs[index].fT;
714 while (index > 0 && fTs[index - 1].fT == startT) {
715 --index;
716 }
717 int oIndex = 0;
718 while (startPt != other->fTs[oIndex].fPt) {
719 SkASSERT(oIndex < other->fTs.count());
720 ++oIndex;
721 }
722 double oStartT = other->fTs[oIndex].fT;
723 while (oIndex > 0 && other->fTs[oIndex - 1].fT == oStartT) {
724 --oIndex;
725 }
726 SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
727 SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
728 SkOpSpan* test = &fTs[index];
729 const SkPoint* testPt = &test->fPt;
730 double testT = test->fT;
731 SkOpSpan* oTest = &other->fTs[oIndex];
732 const SkPoint* oTestPt = &oTest->fPt;
733 SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
734 do {
735 SkASSERT(test->fT < 1);
736 SkASSERT(oTest->fT < 1);
737 #if 0
738 if (test->fDone || oTest->fDone) {
739 #else // consolidate the winding count even if done
740 if ((test->fWindValue == 0 && test->fOppValue == 0)
741 || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
742 #endif
743 SkDEBUGCODE(int firstWind = test->fWindValue);
744 SkDEBUGCODE(int firstOpp = test->fOppValue);
745 do {
746 SkASSERT(firstWind == fTs[index].fWindValue);
747 SkASSERT(firstOpp == fTs[index].fOppValue);
748 ++index;
749 SkASSERT(index < fTs.count());
750 } while (*testPt == fTs[index].fPt);
751 SkDEBUGCODE(firstWind = oTest->fWindValue);
752 SkDEBUGCODE(firstOpp = oTest->fOppValue);
753 do {
754 SkASSERT(firstWind == other->fTs[oIndex].fWindValue);
755 SkASSERT(firstOpp == other->fTs[oIndex].fOppValue);
756 ++oIndex;
757 SkASSERT(oIndex < other->fTs.count());
758 } while (*oTestPt == other->fTs[oIndex].fPt);
759 } else {
760 if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
761 bumpCoincidentThis(*oTest, binary, &index, &outsidePts);
762 other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
763 } else {
764 other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
765 bumpCoincidentOther(*oTest, &index, &outsidePts);
766 }
767 }
768 test = &fTs[index];
769 testPt = &test->fPt;
770 testT = test->fT;
771 if (endPt == *testPt || endT == testT) {
772 break;
773 }
774 oTest = &other->fTs[oIndex];
775 oTestPt = &oTest->fPt;
776 SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
777 } while (endPt != *oTestPt);
778 if (endPt != *testPt && endT != testT) { // in rare cases, one may have ended before the other
779 int lastWind = test[-1].fWindValue;
780 int lastOpp = test[-1].fOppValue;
781 bool zero = lastWind == 0 && lastOpp == 0;
782 do {
783 if (test->fWindValue || test->fOppValue) {
784 test->fWindValue = lastWind;
785 test->fOppValue = lastOpp;
786 if (zero) {
787 test->fDone = true;
788 ++fDoneSpans;
789 }
790 }
791 test = &fTs[++index];
792 testPt = &test->fPt;
793 } while (endPt != *testPt);
794 }
795 int outCount = outsidePts.count();
796 if (!done() && outCount) {
797 addCoinOutsides(outsidePts[0], endPt, other);
798 }
799 if (!other->done() && oOutsidePts.count()) {
800 other->addCoinOutsides(oOutsidePts[0], endPt, this);
801 }
802 }
803
804 // FIXME: this doesn't prevent the same span from being added twice
805 // fix in caller, SkASSERT here?
806 void SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
807 const SkPoint& pt) {
808 int tCount = fTs.count();
809 for (int tIndex = 0; tIndex < tCount; ++tIndex) {
810 const SkOpSpan& span = fTs[tIndex];
811 if (!approximately_negative(span.fT - t)) {
812 break;
813 }
814 if (approximately_negative(span.fT - t) && span.fOther == other
815 && approximately_equal(span.fOtherT, otherT)) {
816 #if DEBUG_ADD_T_PAIR
817 SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
818 __FUNCTION__, fID, t, other->fID, otherT);
819 #endif
820 return;
821 }
822 }
823 #if DEBUG_ADD_T_PAIR
824 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
825 __FUNCTION__, fID, t, other->fID, otherT);
826 #endif
827 int insertedAt = addT(other, pt, t);
828 int otherInsertedAt = other->addT(this, pt, otherT);
829 addOtherT(insertedAt, otherT, otherInsertedAt);
830 other->addOtherT(otherInsertedAt, t, insertedAt);
831 matchWindingValue(insertedAt, t, borrowWind);
832 other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
833 }
834
835 void SkOpSegment::addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const {
836 // add edge leading into junction
837 int min = SkMin32(end, start);
838 if (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0) {
839 addAngle(angles, end, start);
840 }
841 // add edge leading away from junction
842 int step = SkSign32(end - start);
843 int tIndex = nextExactSpan(end, step);
844 min = SkMin32(end, tIndex);
845 if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0)) {
846 addAngle(angles, end, tIndex);
847 }
848 }
849
850 bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
851 const SkPoint midPt = ptAtT(midT);
852 SkPathOpsBounds bounds;
853 bounds.set(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
854 bounds.sort();
855 return bounds.almostContains(midPt);
856 }
857
858 bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const {
859 if (lesser > greater) {
860 SkTSwap<int>(lesser, greater);
861 }
862 return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
863 }
864
865 // note that this follows the same logic flow as active angle
866 bool SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool allowOpp) const {
867 double referenceT = fTs[index].fT;
868 const SkPoint& referencePt = fTs[index].fPt;
869 int lesser = index;
870 while (--lesser >= 0 && (allowOpp || fTs[lesser].fOther->fOperand == fOperand)
871 && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
872 buildAnglesInner(lesser, angles);
873 }
874 do {
875 buildAnglesInner(index, angles);
876 if (++index == fTs.count()) {
877 break;
878 }
879 if (!allowOpp && fTs[index].fOther->fOperand != fOperand) {
880 break;
881 }
882 if (fTs[index - 1].fTiny) {
883 referenceT = fTs[index].fT;
884 continue;
885 }
886 if (!precisely_negative(fTs[index].fT - referenceT) && fTs[index].fPt == referencePt) {
887 // FIXME
888 // testQuad8 generates the wrong output unless false is returned here. Other tests will
889 // take this path although they aren't required to. This means that many go much slower
890 // because of this sort fail.
891 // SkDebugf("!!!\n");
892 return false;
893 }
894 } while (precisely_negative(fTs[index].fT - referenceT));
895 return true;
896 }
897
898 void SkOpSegment::buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const {
899 const SkOpSpan* span = &fTs[index];
900 SkOpSegment* other = span->fOther;
901 // if there is only one live crossing, and no coincidence, continue
902 // in the same direction
903 // if there is coincidence, the only choice may be to reverse direction
904 // find edge on either side of intersection
905 int oIndex = span->fOtherIndex;
906 // if done == -1, prior span has already been processed
907 int step = 1;
908 int next = other->nextExactSpan(oIndex, step);
909 if (next < 0) {
910 step = -step;
911 next = other->nextExactSpan(oIndex, step);
912 }
913 // add candidate into and away from junction
914 other->addTwoAngles(next, oIndex, angles);
915 }
916
917 int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
918 SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted) {
919 addTwoAngles(startIndex, endIndex, angles);
920 if (!buildAngles(endIndex, angles, includeType == SkOpAngle::kBinaryOpp)) {
921 return SK_NaN32;
922 }
923 int angleCount = angles->count();
924 // abort early before sorting if an unsortable (not an unorderable) angle is found
925 if (includeType != SkOpAngle::kUnaryXor) {
926 int firstIndex = -1;
927 while (++firstIndex < angleCount) {
928 const SkOpAngle& angle = (*angles)[firstIndex];
929 if (angle.segment()->windSum(&angle) != SK_MinS32) {
930 break;
931 }
932 }
933 if (firstIndex == angleCount) {
934 return SK_MinS32;
935 }
936 }
937 bool sortable = SortAngles2(*angles, sorted);
938 #if DEBUG_SORT_RAW
939 if (sorted->count() > 0) {
940 (*sorted)[0]->segment()->debugShowSort(__FUNCTION__, *sorted, 0, 0, 0, sortable);
941 }
942 #endif
943 if (!sortable) {
944 return SK_NaN32;
945 }
946 if (includeType == SkOpAngle::kUnaryXor) {
947 return SK_MinS32;
948 }
949 // if all angles have a computed winding,
950 // or if no adjacent angles are orderable,
951 // or if adjacent orderable angles have no computed winding,
952 // there's nothing to do
953 // if two orderable angles are adjacent, and one has winding computed, transfer to the other
954 const SkOpAngle* baseAngle = NULL;
955 int last = angleCount;
956 int finalInitialOrderable = -1;
957 bool tryReverse = false;
958 // look for counterclockwise transfers
959 do {
960 int index = 0;
961 do {
962 SkOpAngle* testAngle = (*sorted)[index];
963 int testWinding = testAngle->segment()->windSum(testAngle);
964 if (SK_MinS32 != testWinding && !testAngle->unorderable()) {
965 baseAngle = testAngle;
966 continue;
967 }
968 if (testAngle->unorderable()) {
969 baseAngle = NULL;
970 tryReverse = true;
971 continue;
972 }
973 if (baseAngle) {
974 ComputeOneSum(baseAngle, testAngle, includeType);
975 baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
976 : NULL;
977 tryReverse |= !baseAngle;
978 continue;
979 }
980 if (finalInitialOrderable + 1 == index) {
981 finalInitialOrderable = index;
982 }
983 } while (++index != last);
984 if (finalInitialOrderable < 0) {
985 break;
986 }
987 last = finalInitialOrderable + 1;
988 finalInitialOrderable = -2; // make this always negative the second time through
989 } while (baseAngle);
990 if (tryReverse) {
991 baseAngle = NULL;
992 last = 0;
993 finalInitialOrderable = angleCount;
994 do {
995 int index = angleCount;
996 while (--index >= last) {
997 SkOpAngle* testAngle = (*sorted)[index];
998 int testWinding = testAngle->segment()->windSum(testAngle);
999 if (SK_MinS32 != testWinding) {
1000 baseAngle = testAngle;
1001 continue;
1002 }
1003 if (testAngle->unorderable()) {
1004 baseAngle = NULL;
1005 continue;
1006 }
1007 if (baseAngle) {
1008 ComputeOneSumReverse(baseAngle, testAngle, includeType);
1009 baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
1010 : NULL;
1011 continue;
1012 }
1013 if (finalInitialOrderable - 1 == index) {
1014 finalInitialOrderable = index;
1015 }
1016 }
1017 if (finalInitialOrderable >= angleCount) {
1018 break;
1019 }
1020 last = finalInitialOrderable;
1021 finalInitialOrderable = angleCount + 1; // make this inactive 2nd time through
1022 } while (baseAngle);
1023 }
1024 int minIndex = SkMin32(startIndex, endIndex);
1025 return windSum(minIndex);
1026 }
1027
1028 void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1029 SkOpAngle::IncludeType includeType) {
1030 const SkOpSegment* baseSegment = baseAngle->segment();
1031 int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
1032 int sumSuWinding;
1033 bool binary = includeType >= SkOpAngle::kBinarySingle;
1034 if (binary) {
1035 sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
1036 if (baseSegment->operand()) {
1037 SkTSwap<int>(sumMiWinding, sumSuWinding);
1038 }
1039 }
1040 SkOpSegment* nextSegment = nextAngle->segment();
1041 int maxWinding, sumWinding;
1042 SkOpSpan* last;
1043 if (binary) {
1044 int oppMaxWinding, oppSumWinding;
1045 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1046 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1047 last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1048 nextAngle);
1049 } else {
1050 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1051 &maxWinding, &sumWinding);
1052 last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1053 }
1054 nextAngle->setLastMarked(last);
1055 }
1056
1057 void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1058 SkOpAngle::IncludeType includeType) {
1059 const SkOpSegment* baseSegment = baseAngle->segment();
1060 int sumMiWinding = baseSegment->updateWinding(baseAngle);
1061 int sumSuWinding;
1062 bool binary = includeType >= SkOpAngle::kBinarySingle;
1063 if (binary) {
1064 sumSuWinding = baseSegment->updateOppWinding(baseAngle);
1065 if (baseSegment->operand()) {
1066 SkTSwap<int>(sumMiWinding, sumSuWinding);
1067 }
1068 }
1069 SkOpSegment* nextSegment = nextAngle->segment();
1070 int maxWinding, sumWinding;
1071 SkOpSpan* last;
1072 if (binary) {
1073 int oppMaxWinding, oppSumWinding;
1074 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1075 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1076 last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1077 nextAngle);
1078 } else {
1079 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1080 &maxWinding, &sumWinding);
1081 last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1082 }
1083 nextAngle->setLastMarked(last);
1084 }
1085
1086 int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
1087 bool* hitSomething, double mid, bool opp, bool current) const {
1088 SkScalar bottom = fBounds.fBottom;
1089 int bestTIndex = -1;
1090 if (bottom <= *bestY) {
1091 return bestTIndex;
1092 }
1093 SkScalar top = fBounds.fTop;
1094 if (top >= basePt.fY) {
1095 return bestTIndex;
1096 }
1097 if (fBounds.fLeft > basePt.fX) {
1098 return bestTIndex;
1099 }
1100 if (fBounds.fRight < basePt.fX) {
1101 return bestTIndex;
1102 }
1103 if (fBounds.fLeft == fBounds.fRight) {
1104 // if vertical, and directly above test point, wait for another one
1105 return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
1106 }
1107 // intersect ray starting at basePt with edge
1108 SkIntersections intersections;
1109 // OPTIMIZE: use specialty function that intersects ray with curve,
1110 // returning t values only for curve (we don't care about t on ray)
1111 intersections.allowNear(false);
1112 int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
1113 (fPts, top, bottom, basePt.fX, false);
1114 if (pts == 0 || (current && pts == 1)) {
1115 return bestTIndex;
1116 }
1117 if (current) {
1118 SkASSERT(pts > 1);
1119 int closestIdx = 0;
1120 double closest = fabs(intersections[0][0] - mid);
1121 for (int idx = 1; idx < pts; ++idx) {
1122 double test = fabs(intersections[0][idx] - mid);
1123 if (closest > test) {
1124 closestIdx = idx;
1125 closest = test;
1126 }
1127 }
1128 intersections.quickRemoveOne(closestIdx, --pts);
1129 }
1130 double bestT = -1;
1131 for (int index = 0; index < pts; ++index) {
1132 double foundT = intersections[0][index];
1133 if (approximately_less_than_zero(foundT)
1134 || approximately_greater_than_one(foundT)) {
1135 continue;
1136 }
1137 SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fY;
1138 if (approximately_negative(testY - *bestY)
1139 || approximately_negative(basePt.fY - testY)) {
1140 continue;
1141 }
1142 if (pts > 1 && fVerb == SkPath::kLine_Verb) {
1143 return SK_MinS32; // if the intersection is edge on, wait for another one
1144 }
1145 if (fVerb > SkPath::kLine_Verb) {
1146 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fX;
1147 if (approximately_zero(dx)) {
1148 return SK_MinS32; // hit vertical, wait for another one
1149 }
1150 }
1151 *bestY = testY;
1152 bestT = foundT;
1153 }
1154 if (bestT < 0) {
1155 return bestTIndex;
1156 }
1157 SkASSERT(bestT >= 0);
1158 SkASSERT(bestT <= 1);
1159 int start;
1160 int end = 0;
1161 do {
1162 start = end;
1163 end = nextSpan(start, 1);
1164 } while (fTs[end].fT < bestT);
1165 // FIXME: see next candidate for a better pattern to find the next start/end pair
1166 while (start + 1 < end && fTs[start].fDone) {
1167 ++start;
1168 }
1169 if (!isCanceled(start)) {
1170 *hitT = bestT;
1171 bestTIndex = start;
1172 *hitSomething = true;
1173 }
1174 return bestTIndex;
1175 }
1176
1177 bool SkOpSegment::decrementSpan(SkOpSpan* span) {
1178 SkASSERT(span->fWindValue > 0);
1179 if (--(span->fWindValue) == 0) {
1180 if (!span->fOppValue && !span->fDone) {
1181 span->fDone = true;
1182 ++fDoneSpans;
1183 return true;
1184 }
1185 }
1186 return false;
1187 }
1188
1189 bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
1190 SkASSERT(!span->fDone || span->fTiny || span->fSmall);
1191 span->fWindValue += windDelta;
1192 SkASSERT(span->fWindValue >= 0);
1193 span->fOppValue += oppDelta;
1194 SkASSERT(span->fOppValue >= 0);
1195 if (fXor) {
1196 span->fWindValue &= 1;
1197 }
1198 if (fOppXor) {
1199 span->fOppValue &= 1;
1200 }
1201 if (!span->fWindValue && !span->fOppValue) {
1202 span->fDone = true;
1203 ++fDoneSpans;
1204 return true;
1205 }
1206 return false;
1207 }
1208
1209 // look to see if the curve end intersects an intermediary that intersects the other
1210 void SkOpSegment::checkEnds() {
1211 debugValidate();
1212 SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
1213 int count = fTs.count();
1214 for (int index = 0; index < count; ++index) {
1215 const SkOpSpan& span = fTs[index];
1216 double otherT = span.fOtherT;
1217 if (otherT != 0 && otherT != 1) { // only check ends
1218 continue;
1219 }
1220 const SkOpSegment* other = span.fOther;
1221 // peek start/last describe the range of spans that match the other t of this span
1222 int peekStart = span.fOtherIndex;
1223 while (--peekStart >= 0 && other->fTs[peekStart].fT == otherT)
1224 ;
1225 int otherCount = other->fTs.count();
1226 int peekLast = span.fOtherIndex;
1227 while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT)
1228 ;
1229 if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do
1230 continue;
1231 }
1232 // t start/last describe the range of spans that match the t of this span
1233 double t = span.fT;
1234 double tBottom = -1;
1235 int tStart = -1;
1236 int tLast = count;
1237 bool lastSmall = false;
1238 double afterT = t;
1239 for (int inner = 0; inner < count; ++inner) {
1240 double innerT = fTs[inner].fT;
1241 if (innerT <= t && innerT > tBottom) {
1242 if (innerT < t || !lastSmall) {
1243 tStart = inner - 1;
1244 }
1245 tBottom = innerT;
1246 }
1247 if (innerT > afterT) {
1248 if (t == afterT && lastSmall) {
1249 afterT = innerT;
1250 } else {
1251 tLast = inner;
1252 break;
1253 }
1254 }
1255 lastSmall = innerT <= t ? fTs[inner].fSmall : false;
1256 }
1257 for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
1258 if (peekIndex == span.fOtherIndex) { // skip the other span pointed to by this span
1259 continue;
1260 }
1261 const SkOpSpan& peekSpan = other->fTs[peekIndex];
1262 SkOpSegment* match = peekSpan.fOther;
1263 if (match->done()) {
1264 continue; // if the edge has already been eaten (likely coincidence), ignore it
1265 }
1266 const double matchT = peekSpan.fOtherT;
1267 // see if any of the spans match the other spans
1268 for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) {
1269 const SkOpSpan& tSpan = fTs[tIndex];
1270 if (tSpan.fOther == match) {
1271 if (tSpan.fOtherT == matchT) {
1272 goto nextPeekIndex;
1273 }
1274 double midT = (tSpan.fOtherT + matchT) / 2;
1275 if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
1276 goto nextPeekIndex;
1277 }
1278 }
1279 }
1280 if (missingSpans.count() > 0) {
1281 const MissingSpan& lastMissing = missingSpans.back();
1282 if (lastMissing.fT == t
1283 && lastMissing.fOther == match
1284 && lastMissing.fOtherT == matchT) {
1285 SkASSERT(lastMissing.fPt == peekSpan.fPt);
1286 continue;
1287 }
1288 }
1289 #if DEBUG_CHECK_ENDS
1290 SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n",
1291 __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY);
1292 #endif
1293 // this segment is missing a entry that the other contains
1294 // remember so we can add the missing one and recompute the indices
1295 {
1296 MissingSpan& missing = missingSpans.push_back();
1297 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
1298 missing.fT = t;
1299 missing.fOther = match;
1300 missing.fOtherT = matchT;
1301 missing.fPt = peekSpan.fPt;
1302 }
1303 break;
1304 nextPeekIndex:
1305 ;
1306 }
1307 }
1308 if (missingSpans.count() == 0) {
1309 debugValidate();
1310 return;
1311 }
1312 debugValidate();
1313 int missingCount = missingSpans.count();
1314 for (int index = 0; index < missingCount; ++index) {
1315 MissingSpan& missing = missingSpans[index];
1316 addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
1317 }
1318 fixOtherTIndex();
1319 // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
1320 // avoid this
1321 for (int index = 0; index < missingCount; ++index) {
1322 missingSpans[index].fOther->fixOtherTIndex();
1323 }
1324 debugValidate();
1325 }
1326
1327 bool SkOpSegment::checkSmall(int index) const {
1328 if (fTs[index].fSmall) {
1329 return true;
1330 }
1331 double tBase = fTs[index].fT;
1332 while (index > 0 && precisely_negative(tBase - fTs[--index].fT))
1333 ;
1334 return fTs[index].fSmall;
1335 }
1336
1337 // if pair of spans on either side of tiny have the same end point and mid point, mark
1338 // them as parallel
1339 // OPTIMIZATION : mark the segment to note that some span is tiny
1340 void SkOpSegment::checkTiny() {
1341 SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
1342 SkOpSpan* thisSpan = fTs.begin() - 1;
1343 const SkOpSpan* endSpan = fTs.end() - 1; // last can't be tiny
1344 while (++thisSpan < endSpan) {
1345 if (!thisSpan->fTiny) {
1346 continue;
1347 }
1348 SkOpSpan* nextSpan = thisSpan + 1;
1349 double thisT = thisSpan->fT;
1350 double nextT = nextSpan->fT;
1351 if (thisT == nextT) {
1352 continue;
1353 }
1354 SkASSERT(thisT < nextT);
1355 SkASSERT(thisSpan->fPt == nextSpan->fPt);
1356 SkOpSegment* thisOther = thisSpan->fOther;
1357 SkOpSegment* nextOther = nextSpan->fOther;
1358 int oIndex = thisSpan->fOtherIndex;
1359 for (int oStep = -1; oStep <= 1; oStep += 2) {
1360 int oEnd = thisOther->nextExactSpan(oIndex, oStep);
1361 if (oEnd < 0) {
1362 continue;
1363 }
1364 const SkOpSpan& oSpan = thisOther->span(oEnd);
1365 int nIndex = nextSpan->fOtherIndex;
1366 for (int nStep = -1; nStep <= 1; nStep += 2) {
1367 int nEnd = nextOther->nextExactSpan(nIndex, nStep);
1368 if (nEnd < 0) {
1369 continue;
1370 }
1371 const SkOpSpan& nSpan = nextOther->span(nEnd);
1372 if (oSpan.fPt != nSpan.fPt) {
1373 continue;
1374 }
1375 double oMidT = (thisSpan->fOtherT + oSpan.fT) / 2;
1376 const SkPoint& oPt = thisOther->ptAtT(oMidT);
1377 double nMidT = (nextSpan->fOtherT + nSpan.fT) / 2;
1378 const SkPoint& nPt = nextOther->ptAtT(nMidT);
1379 if (!AlmostEqualUlps(oPt, nPt)) {
1380 continue;
1381 }
1382 #if DEBUG_CHECK_TINY
1383 SkDebugf("%s [%d] add coincidence [%d] [%d]\n", __FUNCTION__, fID,
1384 thisOther->fID, nextOther->fID);
1385 #endif
1386 // this segment is missing a entry that the other contains
1387 // remember so we can add the missing one and recompute the indices
1388 MissingSpan& missing = missingSpans.push_back();
1389 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
1390 missing.fSegment = thisOther;
1391 missing.fT = thisSpan->fOtherT;
1392 missing.fOther = nextOther;
1393 missing.fOtherT = nextSpan->fOtherT;
1394 missing.fPt = thisSpan->fPt;
1395 }
1396 }
1397 }
1398 int missingCount = missingSpans.count();
1399 if (!missingCount) {
1400 return;
1401 }
1402 for (int index = 0; index < missingCount; ++index) {
1403 MissingSpan& missing = missingSpans[index];
1404 missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
1405 }
1406 for (int index = 0; index < missingCount; ++index) {
1407 MissingSpan& missing = missingSpans[index];
1408 missing.fSegment->fixOtherTIndex();
1409 missing.fOther->fixOtherTIndex();
1410 }
1411 }
1412
1413 bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart,
1414 int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const {
1415 SkASSERT(span->fT == 0 || span->fT == 1);
1416 SkASSERT(span->fOtherT == 0 || span->fOtherT == 1);
1417 const SkOpSpan* otherSpan = &other->span(oEnd);
1418 double refT = otherSpan->fT;
1419 const SkPoint& refPt = otherSpan->fPt;
1420 const SkOpSpan* lastSpan = &other->span(step > 0 ? other->count() - 1 : 0);
1421 do {
1422 const SkOpSegment* match = span->fOther;
1423 if (match == otherSpan->fOther) {
1424 // find start of respective spans and see if both have winding
1425 int startIndex, endIndex;
1426 if (span->fOtherT == 1) {
1427 endIndex = span->fOtherIndex;
1428 startIndex = match->nextExactSpan(endIndex, -1);
1429 } else {
1430 startIndex = span->fOtherIndex;
1431 endIndex = match->nextExactSpan(startIndex, 1);
1432 }
1433 const SkOpSpan& startSpan = match->span(startIndex);
1434 if (startSpan.fWindValue != 0) {
1435 // draw ray from endSpan.fPt perpendicular to end tangent and measure distance
1436 // to other segment.
1437 const SkOpSpan& endSpan = match->span(endIndex);
1438 SkDLine ray;
1439 SkVector dxdy;
1440 if (span->fOtherT == 1) {
1441 ray.fPts[0].set(startSpan.fPt);
1442 dxdy = match->dxdy(startIndex);
1443 } else {
1444 ray.fPts[0].set(endSpan.fPt);
1445 dxdy = match->dxdy(endIndex);
1446 }
1447 ray.fPts[1].fX = ray.fPts[0].fX + dxdy.fY;
1448 ray.fPts[1].fY = ray.fPts[0].fY - dxdy.fX;
1449 SkIntersections i;
1450 int roots = (i.*CurveRay[SkPathOpsVerbToPoints(other->verb())])(other->pts(), ray);
1451 for (int index = 0; index < roots; ++index) {
1452 if (ray.fPts[0].approximatelyEqual(i.pt(index))) {
1453 double matchMidT = (match->span(startIndex).fT
1454 + match->span(endIndex).fT) / 2;
1455 SkPoint matchMidPt = match->ptAtT(matchMidT);
1456 double otherMidT = (i[0][index] + other->span(oStart).fT) / 2;
1457 SkPoint otherMidPt = other->ptAtT(otherMidT);
1458 if (SkDPoint::ApproximatelyEqual(matchMidPt, otherMidPt)) {
1459 *startPt = startSpan.fPt;
1460 *endPt = endSpan.fPt;
1461 *endT = endSpan.fT;
1462 return true;
1463 }
1464 }
1465 }
1466 }
1467 return false;
1468 }
1469 if (otherSpan == lastSpan) {
1470 break;
1471 }
1472 otherSpan += step;
1473 } while (otherSpan->fT == refT || otherSpan->fPt == refPt);
1474 return false;
1475 }
1476
1477 /*
1478 The M and S variable name parts stand for the operators.
1479 Mi stands for Minuend (see wiki subtraction, analogous to difference)
1480 Su stands for Subtrahend
1481 The Opp variable name part designates that the value is for the Opposite operator.
1482 Opposite values result from combining coincident spans.
1483 */
1484 SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
1485 bool* unsortable, SkPathOp op, const int xorMiMask,
1486 const int xorSuMask) {
1487 const int startIndex = *nextStart;
1488 const int endIndex = *nextEnd;
1489 SkASSERT(startIndex != endIndex);
1490 SkDEBUGCODE(const int count = fTs.count());
1491 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
1492 const int step = SkSign32(endIndex - startIndex);
1493 const int end = nextExactSpan(startIndex, step);
1494 SkASSERT(end >= 0);
1495 SkOpSpan* endSpan = &fTs[end];
1496 SkOpSegment* other;
1497 if (isSimple(end)) {
1498 // mark the smaller of startIndex, endIndex done, and all adjacent
1499 // spans with the same T value (but not 'other' spans)
1500 #if DEBUG_WINDING
1501 SkDebugf("%s simple\n", __FUNCTION__);
1502 #endif
1503 int min = SkMin32(startIndex, endIndex);
1504 if (fTs[min].fDone) {
1505 return NULL;
1506 }
1507 markDoneBinary(min);
1508 other = endSpan->fOther;
1509 *nextStart = endSpan->fOtherIndex;
1510 double startT = other->fTs[*nextStart].fT;
1511 *nextEnd = *nextStart;
1512 do {
1513 *nextEnd += step;
1514 } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
1515 SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
1516 if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
1517 *unsortable = true;
1518 return NULL;
1519 }
1520 return other;
1521 }
1522 // more than one viable candidate -- measure angles to find best
1523 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1524 SkASSERT(startIndex - endIndex != 0);
1525 SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
1526 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1527 int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp, &angles, &sorted);
1528 bool sortable = calcWinding != SK_NaN32;
1529 if (sortable && sorted.count() == 0) {
1530 // if no edge has a computed winding sum, we can go no further
1531 *unsortable = true;
1532 return NULL;
1533 }
1534 int angleCount = angles.count();
1535 int firstIndex = findStartingEdge(sorted, startIndex, end);
1536 SkASSERT(!sortable || firstIndex >= 0);
1537 #if DEBUG_SORT
1538 debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
1539 #endif
1540 if (!sortable) {
1541 *unsortable = true;
1542 return NULL;
1543 }
1544 SkASSERT(sorted[firstIndex]->segment() == this);
1545 #if DEBUG_WINDING
1546 SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
1547 sorted[firstIndex]->sign());
1548 #endif
1549 int sumMiWinding = updateWinding(endIndex, startIndex);
1550 int sumSuWinding = updateOppWinding(endIndex, startIndex);
1551 if (operand()) {
1552 SkTSwap<int>(sumMiWinding, sumSuWinding);
1553 }
1554 int nextIndex = firstIndex + 1;
1555 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1556 const SkOpAngle* foundAngle = NULL;
1557 bool foundDone = false;
1558 // iterate through the angle, and compute everyone's winding
1559 SkOpSegment* nextSegment;
1560 int activeCount = 0;
1561 do {
1562 SkASSERT(nextIndex != firstIndex);
1563 if (nextIndex == angleCount) {
1564 nextIndex = 0;
1565 }
1566 const SkOpAngle* nextAngle = sorted[nextIndex];
1567 nextSegment = nextAngle->segment();
1568 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
1569 bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
1570 nextAngle->end(), op, &sumMiWinding, &sumSuWinding,
1571 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1572 if (activeAngle) {
1573 ++activeCount;
1574 if (!foundAngle || (foundDone && activeCount & 1)) {
1575 if (nextSegment->isTiny(nextAngle)) {
1576 *unsortable = true;
1577 return NULL;
1578 }
1579 foundAngle = nextAngle;
1580 foundDone = nextSegment->done(nextAngle);
1581 }
1582 }
1583 if (nextSegment->done()) {
1584 continue;
1585 }
1586 if (nextSegment->isTiny(nextAngle)) {
1587 continue;
1588 }
1589 if (!activeAngle) {
1590 nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
1591 }
1592 SkOpSpan* last = nextAngle->lastMarked();
1593 if (last) {
1594 *chase->append() = last;
1595 #if DEBUG_WINDING
1596 SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
1597 last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
1598 last->fSmall);
1599 #endif
1600 }
1601 } while (++nextIndex != lastIndex);
1602 markDoneBinary(SkMin32(startIndex, endIndex));
1603 if (!foundAngle) {
1604 return NULL;
1605 }
1606 *nextStart = foundAngle->start();
1607 *nextEnd = foundAngle->end();
1608 nextSegment = foundAngle->segment();
1609 #if DEBUG_WINDING
1610 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
1611 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
1612 #endif
1613 return nextSegment;
1614 }
1615
1616 SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart,
1617 int* nextEnd, bool* unsortable) {
1618 const int startIndex = *nextStart;
1619 const int endIndex = *nextEnd;
1620 SkASSERT(startIndex != endIndex);
1621 SkDEBUGCODE(const int count = fTs.count());
1622 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
1623 const int step = SkSign32(endIndex - startIndex);
1624 const int end = nextExactSpan(startIndex, step);
1625 SkASSERT(end >= 0);
1626 SkOpSpan* endSpan = &fTs[end];
1627 SkOpSegment* other;
1628 if (isSimple(end)) {
1629 // mark the smaller of startIndex, endIndex done, and all adjacent
1630 // spans with the same T value (but not 'other' spans)
1631 #if DEBUG_WINDING
1632 SkDebugf("%s simple\n", __FUNCTION__);
1633 #endif
1634 int min = SkMin32(startIndex, endIndex);
1635 if (fTs[min].fDone) {
1636 return NULL;
1637 }
1638 markDoneUnary(min);
1639 other = endSpan->fOther;
1640 *nextStart = endSpan->fOtherIndex;
1641 double startT = other->fTs[*nextStart].fT;
1642 *nextEnd = *nextStart;
1643 do {
1644 *nextEnd += step;
1645 } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
1646 SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
1647 if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
1648 *unsortable = true;
1649 return NULL;
1650 }
1651 return other;
1652 }
1653 // more than one viable candidate -- measure angles to find best
1654 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1655 SkASSERT(startIndex - endIndex != 0);
1656 SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
1657 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1658 int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding, &angles, &sorted);
1659 bool sortable = calcWinding != SK_NaN32;
1660 int angleCount = angles.count();
1661 int firstIndex = findStartingEdge(sorted, startIndex, end);
1662 SkASSERT(!sortable || firstIndex >= 0);
1663 #if DEBUG_SORT
1664 debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
1665 #endif
1666 if (!sortable) {
1667 *unsortable = true;
1668 return NULL;
1669 }
1670 SkASSERT(sorted[firstIndex]->segment() == this);
1671 #if DEBUG_WINDING
1672 SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
1673 sorted[firstIndex]->sign());
1674 #endif
1675 int sumWinding = updateWinding(endIndex, startIndex);
1676 int nextIndex = firstIndex + 1;
1677 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1678 const SkOpAngle* foundAngle = NULL;
1679 bool foundDone = false;
1680 // iterate through the angle, and compute everyone's winding
1681 SkOpSegment* nextSegment;
1682 int activeCount = 0;
1683 do {
1684 SkASSERT(nextIndex != firstIndex);
1685 if (nextIndex == angleCount) {
1686 nextIndex = 0;
1687 }
1688 const SkOpAngle* nextAngle = sorted[nextIndex];
1689 nextSegment = nextAngle->segment();
1690 int maxWinding;
1691 bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
1692 &maxWinding, &sumWinding);
1693 if (activeAngle) {
1694 ++activeCount;
1695 if (!foundAngle || (foundDone && activeCount & 1)) {
1696 if (nextSegment->isTiny(nextAngle)) {
1697 *unsortable = true;
1698 return NULL;
1699 }
1700 foundAngle = nextAngle;
1701 foundDone = nextSegment->done(nextAngle);
1702 }
1703 }
1704 if (nextSegment->done()) {
1705 continue;
1706 }
1707 if (nextSegment->isTiny(nextAngle)) {
1708 continue;
1709 }
1710 if (!activeAngle) {
1711 nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end());
1712 }
1713 SkOpSpan* last = nextAngle->lastMarked();
1714 if (last) {
1715 *chase->append() = last;
1716 #if DEBUG_WINDING
1717 SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
1718 last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
1719 last->fSmall);
1720 #endif
1721 }
1722 } while (++nextIndex != lastIndex);
1723 markDoneUnary(SkMin32(startIndex, endIndex));
1724 if (!foundAngle) {
1725 return NULL;
1726 }
1727 *nextStart = foundAngle->start();
1728 *nextEnd = foundAngle->end();
1729 nextSegment = foundAngle->segment();
1730 #if DEBUG_WINDING
1731 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
1732 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
1733 #endif
1734 return nextSegment;
1735 }
1736
1737 SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsortable) {
1738 const int startIndex = *nextStart;
1739 const int endIndex = *nextEnd;
1740 SkASSERT(startIndex != endIndex);
1741 SkDEBUGCODE(int count = fTs.count());
1742 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
1743 int step = SkSign32(endIndex - startIndex);
1744 int end = nextExactSpan(startIndex, step);
1745 SkASSERT(end >= 0);
1746 SkOpSpan* endSpan = &fTs[end];
1747 SkOpSegment* other;
1748 if (isSimple(end)) {
1749 #if DEBUG_WINDING
1750 SkDebugf("%s simple\n", __FUNCTION__);
1751 #endif
1752 int min = SkMin32(startIndex, endIndex);
1753 if (fTs[min].fDone) {
1754 return NULL;
1755 }
1756 markDone(min, 1);
1757 other = endSpan->fOther;
1758 *nextStart = endSpan->fOtherIndex;
1759 double startT = other->fTs[*nextStart].fT;
1760 // FIXME: I don't know why the logic here is difference from the winding case
1761 SkDEBUGCODE(bool firstLoop = true;)
1762 if ((approximately_less_than_zero(startT) && step < 0)
1763 || (approximately_greater_than_one(startT) && step > 0)) {
1764 step = -step;
1765 SkDEBUGCODE(firstLoop = false;)
1766 }
1767 do {
1768 *nextEnd = *nextStart;
1769 do {
1770 *nextEnd += step;
1771 } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
1772 if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) {
1773 break;
1774 }
1775 SkASSERT(firstLoop);
1776 SkDEBUGCODE(firstLoop = false;)
1777 step = -step;
1778 } while (true);
1779 SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
1780 return other;
1781 }
1782 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1783 SkASSERT(startIndex - endIndex != 0);
1784 SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
1785 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1786 int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryXor, &angles, &sorted);
1787 bool sortable = calcWinding != SK_NaN32;
1788 int angleCount = angles.count();
1789 int firstIndex = findStartingEdge(sorted, startIndex, end);
1790 SkASSERT(!sortable || firstIndex >= 0);
1791 #if DEBUG_SORT
1792 debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable);
1793 #endif
1794 if (!sortable) {
1795 *unsortable = true;
1796 return NULL;
1797 }
1798 SkASSERT(sorted[firstIndex]->segment() == this);
1799 #if DEBUG_WINDING
1800 SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
1801 sorted[firstIndex]->sign());
1802 #endif
1803 int nextIndex = firstIndex + 1;
1804 int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1805 const SkOpAngle* foundAngle = NULL;
1806 bool foundDone = false;
1807 SkOpSegment* nextSegment;
1808 int activeCount = 0;
1809 do {
1810 SkASSERT(nextIndex != firstIndex);
1811 if (nextIndex == angleCount) {
1812 nextIndex = 0;
1813 }
1814 const SkOpAngle* nextAngle = sorted[nextIndex];
1815 nextSegment = nextAngle->segment();
1816 ++activeCount;
1817 if (!foundAngle || (foundDone && activeCount & 1)) {
1818 if (nextSegment->isTiny(nextAngle)) {
1819 *unsortable = true;
1820 return NULL;
1821 }
1822 foundAngle = nextAngle;
1823 foundDone = nextSegment->done(nextAngle);
1824 }
1825 if (nextSegment->done()) {
1826 continue;
1827 }
1828 } while (++nextIndex != lastIndex);
1829 markDone(SkMin32(startIndex, endIndex), 1);
1830 if (!foundAngle) {
1831 return NULL;
1832 }
1833 *nextStart = foundAngle->start();
1834 *nextEnd = foundAngle->end();
1835 nextSegment = foundAngle->segment();
1836 #if DEBUG_WINDING
1837 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
1838 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
1839 #endif
1840 return nextSegment;
1841 }
1842
1843 int SkOpSegment::findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end) {
1844 int angleCount = sorted.count();
1845 int firstIndex = -1;
1846 for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
1847 const SkOpAngle* angle = sorted[angleIndex];
1848 if (angle->segment() == this && angle->start() == end &&
1849 angle->end() == start) {
1850 firstIndex = angleIndex;
1851 break;
1852 }
1853 }
1854 return firstIndex;
1855 }
1856
1857 int SkOpSegment::findT(double t, const SkOpSegment* match) const {
1858 int count = this->count();
1859 for (int index = 0; index < count; ++index) {
1860 const SkOpSpan& span = fTs[index];
1861 if (span.fT == t && span.fOther == match) {
1862 return index;
1863 }
1864 }
1865 SkASSERT(0);
1866 return -1;
1867 }
1868
1869 // FIXME: either:
1870 // a) mark spans with either end unsortable as done, or
1871 // b) rewrite findTop / findTopSegment / findTopContour to iterate further
1872 // when encountering an unsortable span
1873
1874 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
1875 // and use more concise logic like the old edge walker code?
1876 // FIXME: this needs to deal with coincident edges
1877 SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable,
1878 bool onlySortable) {
1879 // iterate through T intersections and return topmost
1880 // topmost tangent from y-min to first pt is closer to horizontal
1881 SkASSERT(!done());
1882 int firstT = -1;
1883 /* SkPoint topPt = */ activeLeftTop(onlySortable, &firstT);
1884 if (firstT < 0) {
1885 *unsortable = true;
1886 firstT = 0;
1887 while (fTs[firstT].fDone) {
1888 SkASSERT(firstT < fTs.count());
1889 ++firstT;
1890 }
1891 *tIndexPtr = firstT;
1892 *endIndexPtr = nextExactSpan(firstT, 1);
1893 return this;
1894 }
1895 // sort the edges to find the leftmost
1896 int step = 1;
1897 int end = nextSpan(firstT, step);
1898 if (end == -1) {
1899 step = -1;
1900 end = nextSpan(firstT, step);
1901 SkASSERT(end != -1);
1902 }
1903 // if the topmost T is not on end, or is three-way or more, find left
1904 // look for left-ness from tLeft to firstT (matching y of other)
1905 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1906 SkASSERT(firstT - end != 0);
1907 addTwoAngles(end, firstT, &angles);
1908 if (!buildAngles(firstT, &angles, true) && onlySortable) {
1909 // *unsortable = true;
1910 // return NULL;
1911 }
1912 SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1913 bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind);
1914 if (onlySortable && !sortable) {
1915 *unsortable = true;
1916 return NULL;
1917 }
1918 int first = SK_MaxS32;
1919 SkScalar top = SK_ScalarMax;
1920 int count = sorted.count();
1921 for (int index = 0; index < count; ++index) {
1922 const SkOpAngle* angle = sorted[index];
1923 if (onlySortable && angle->unorderable()) {
1924 continue;
1925 }
1926 SkOpSegment* next = angle->segment();
1927 SkPathOpsBounds bounds;
1928 next->subDivideBounds(angle->end(), angle->start(), &bounds);
1929 if (approximately_greater(top, bounds.fTop)) {
1930 top = bounds.fTop;
1931 first = index;
1932 }
1933 }
1934 SkASSERT(first < SK_MaxS32);
1935 #if DEBUG_SORT // || DEBUG_SWAP_TOP
1936 sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable);
1937 #endif
1938 // skip edges that have already been processed
1939 firstT = first - 1;
1940 SkOpSegment* leftSegment;
1941 do {
1942 if (++firstT == count) {
1943 firstT = 0;
1944 }
1945 const SkOpAngle* angle = sorted[firstT];
1946 SkASSERT(!onlySortable || !angle->unsortable());
1947 leftSegment = angle->segment();
1948 *tIndexPtr = angle->end();
1949 *endIndexPtr = angle->start();
1950 } while (leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone);
1951 if (leftSegment->verb() >= SkPath::kQuad_Verb) {
1952 const int tIndex = *tIndexPtr;
1953 const int endIndex = *endIndexPtr;
1954 if (!leftSegment->clockwise(tIndex, endIndex)) {
1955 bool swap = !leftSegment->monotonicInY(tIndex, endIndex)
1956 && !leftSegment->serpentine(tIndex, endIndex);
1957 #if DEBUG_SWAP_TOP
1958 SkDebugf("%s swap=%d serpentine=%d containedByEnds=%d monotonic=%d\n", __FUNCTION__,
1959 swap,
1960 leftSegment->serpentine(tIndex, endIndex),
1961 leftSegment->controlsContainedByEnds(tIndex, endIndex),
1962 leftSegment->monotonicInY(tIndex, endIndex));
1963 #endif
1964 if (swap) {
1965 // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first
1966 // sorted but merely the first not already processed (i.e., not done)
1967 SkTSwap(*tIndexPtr, *endIndexPtr);
1968 }
1969 }
1970 }
1971 SkASSERT(!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fTiny);
1972 return leftSegment;
1973 }
1974
1975 // FIXME: not crazy about this
1976 // when the intersections are performed, the other index is into an
1977 // incomplete array. As the array grows, the indices become incorrect
1978 // while the following fixes the indices up again, it isn't smart about
1979 // skipping segments whose indices are already correct
1980 // assuming we leave the code that wrote the index in the first place
1981 // FIXME: if called after remove, this needs to correct tiny
1982 void SkOpSegment::fixOtherTIndex() {
1983 int iCount = fTs.count();
1984 for (int i = 0; i < iCount; ++i) {
1985 SkOpSpan& iSpan = fTs[i];
1986 double oT = iSpan.fOtherT;
1987 SkOpSegment* other = iSpan.fOther;
1988 int oCount = other->fTs.count();
1989 SkDEBUGCODE(iSpan.fOtherIndex = -1);
1990 for (int o = 0; o < oCount; ++o) {
1991 SkOpSpan& oSpan = other->fTs[o];
1992 if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) {
1993 iSpan.fOtherIndex = o;
1994 oSpan.fOtherIndex = i;
1995 break;
1996 }
1997 }
1998 SkASSERT(iSpan.fOtherIndex >= 0);
1999 }
2000 }
2001
2002 void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
2003 fDoneSpans = 0;
2004 fOperand = operand;
2005 fXor = evenOdd;
2006 fPts = pts;
2007 fVerb = verb;
2008 }
2009
2010 void SkOpSegment::initWinding(int start, int end) {
2011 int local = spanSign(start, end);
2012 int oppLocal = oppSign(start, end);
2013 (void) markAndChaseWinding(start, end, local, oppLocal);
2014 // OPTIMIZATION: the reverse mark and chase could skip the first marking
2015 (void) markAndChaseWinding(end, start, local, oppLocal);
2016 }
2017
2018 /*
2019 when we start with a vertical intersect, we try to use the dx to determine if the edge is to
2020 the left or the right of vertical. This determines if we need to add the span's
2021 sign or not. However, this isn't enough.
2022 If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
2023 If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
2024 from has the same x direction as this span, the winding should change. If the dx is opposite, then
2025 the same winding is shared by both.
2026 */
2027 void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkScalar hitDx,
2028 int oppWind, SkScalar hitOppDx) {
2029 SkASSERT(hitDx || !winding);
2030 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
2031 SkASSERT(dx);
2032 int windVal = windValue(SkMin32(start, end));
2033 #if DEBUG_WINDING_AT_T
2034 SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding,
2035 hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
2036 #endif
2037 if (!winding) {
2038 winding = dx < 0 ? windVal : -windVal;
2039 } else if (winding * dx < 0) {
2040 int sideWind = winding + (dx < 0 ? windVal : -windVal);
2041 if (abs(winding) < abs(sideWind)) {
2042 winding = sideWind;
2043 }
2044 }
2045 #if DEBUG_WINDING_AT_T
2046 SkDebugf(" winding=%d\n", winding);
2047 #endif
2048 SkDEBUGCODE(int oppLocal = oppSign(start, end));
2049 SkASSERT(hitOppDx || !oppWind || !oppLocal);
2050 int oppWindVal = oppValue(SkMin32(start, end));
2051 if (!oppWind) {
2052 oppWind = dx < 0 ? oppWindVal : -oppWindVal;
2053 } else if (hitOppDx * dx >= 0) {
2054 int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
2055 if (abs(oppWind) < abs(oppSideWind)) {
2056 oppWind = oppSideWind;
2057 }
2058 }
2059 (void) markAndChaseWinding(start, end, winding, oppWind);
2060 // OPTIMIZATION: the reverse mark and chase could skip the first marking
2061 (void) markAndChaseWinding(end, start, winding, oppWind);
2062 }
2063
2064 // OPTIMIZE: successive calls could start were the last leaves off
2065 // or calls could specialize to walk forwards or backwards
2066 bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const {
2067 size_t tCount = fTs.count();
2068 for (size_t index = 0; index < tCount; ++index) {
2069 const SkOpSpan& span = fTs[index];
2070 if (approximately_zero(startT - span.fT) && pt == span.fPt) {
2071 return false;
2072 }
2073 }
2074 return true;
2075 }
2076
2077 bool SkOpSegment::isSimple(int end) const {
2078 int count = fTs.count();
2079 if (count == 2) {
2080 return true;
2081 }
2082 double t = fTs[end].fT;
2083 if (approximately_less_than_zero(t)) {
2084 return !approximately_less_than_zero(fTs[1].fT);
2085 }
2086 if (approximately_greater_than_one(t)) {
2087 return !approximately_greater_than_one(fTs[count - 2].fT);
2088 }
2089 return false;
2090 }
2091
2092 bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
2093 int start = angle->start();
2094 int end = angle->end();
2095 const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
2096 return mSpan.fTiny;
2097 }
2098
2099 bool SkOpSegment::isTiny(int index) const {
2100 return fTs[index].fTiny;
2101 }
2102
2103 // look pair of active edges going away from coincident edge
2104 // one of them should be the continuation of other
2105 // if both are active, look to see if they both the connect to another coincident pair
2106 // if one at least one is a line, then make the pair coincident
2107 // if neither is a line, test for coincidence
2108 bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, int step,
2109 bool cancel) {
2110 int otherTIndex = other->findT(otherT, this);
2111 int next = other->nextExactSpan(otherTIndex, step);
2112 int otherMin = SkTMin(otherTIndex, next);
2113 int otherWind = other->span(otherMin).fWindValue;
2114 if (otherWind == 0) {
2115 return false;
2116 }
2117 SkASSERT(next >= 0);
2118 int tIndex = 0;
2119 do {
2120 SkOpSpan* test = &fTs[tIndex];
2121 SkASSERT(test->fT == 0);
2122 if (test->fOther == other || test->fOtherT != 1) {
2123 continue;
2124 }
2125 SkPoint startPt, endPt;
2126 double endT;
2127 if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
2128 SkOpSegment* match = test->fOther;
2129 if (cancel) {
2130 match->addTCancel(startPt, endPt, other);
2131 } else {
2132 match->addTCoincident(startPt, endPt, endT, other);
2133 }
2134 return true;
2135 }
2136 } while (fTs[++tIndex].fT == 0);
2137 return false;
2138 }
2139
2140 // this span is excluded by the winding rule -- chase the ends
2141 // as long as they are unambiguous to mark connections as done
2142 // and give them the same winding value
2143
2144 SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) {
2145 int step = SkSign32(endIndex - index);
2146 int min = SkMin32(index, endIndex);
2147 markDoneBinary(min);
2148 SkOpSpan* last;
2149 SkOpSegment* other = this;
2150 while ((other = other->nextChase(&index, step, &min, &last))) {
2151 if (other->done()) {
2152 return NULL;
2153 }
2154 other->markDoneBinary(min);
2155 }
2156 return last;
2157 }
2158
2159 SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) {
2160 int step = SkSign32(endIndex - index);
2161 int min = SkMin32(index, endIndex);
2162 markDoneUnary(min);
2163 SkOpSpan* last;
2164 SkOpSegment* other = this;
2165 while ((other = other->nextChase(&index, step, &min, &last))) {
2166 if (other->done()) {
2167 return NULL;
2168 }
2169 other->markDoneUnary(min);
2170 }
2171 return last;
2172 }
2173
2174 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, const int winding) {
2175 int index = angle->start();
2176 int endIndex = angle->end();
2177 int step = SkSign32(endIndex - index);
2178 int min = SkMin32(index, endIndex);
2179 markWinding(min, winding);
2180 SkOpSpan* last;
2181 SkOpSegment* other = this;
2182 while ((other = other->nextChase(&index, step, &min, &last))) {
2183 if (other->fTs[min].fWindSum != SK_MinS32) {
2184 SkASSERT(other->fTs[min].fWindSum == winding);
2185 return NULL;
2186 }
2187 other->markWinding(min, winding);
2188 }
2189 return last;
2190 }
2191
2192 SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
2193 int min = SkMin32(index, endIndex);
2194 int step = SkSign32(endIndex - index);
2195 markWinding(min, winding, oppWinding);
2196 SkOpSpan* last;
2197 SkOpSegment* other = this;
2198 while ((other = other->nextChase(&index, step, &min, &last))) {
2199 if (other->fTs[min].fWindSum != SK_MinS32) {
2200 SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
2201 return NULL;
2202 }
2203 other->markWinding(min, winding, oppWinding);
2204 }
2205 return last;
2206 }
2207
2208 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding) {
2209 int start = angle->start();
2210 int end = angle->end();
2211 return markAndChaseWinding(start, end, winding, oppWinding);
2212 }
2213
2214 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
2215 SkASSERT(angle->segment() == this);
2216 if (UseInnerWinding(maxWinding, sumWinding)) {
2217 maxWinding = sumWinding;
2218 }
2219 SkOpSpan* last = markAndChaseWinding(angle, maxWinding);
2220 #if DEBUG_WINDING
2221 if (last) {
2222 SkDebugf("%s last id=%d windSum=", __FUNCTION__,
2223 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
2224 SkPathOpsDebug::WindingPrintf(last->fWindSum);
2225 SkDebugf(" small=%d\n", last->fSmall);
2226 }
2227 #endif
2228 return last;
2229 }
2230
2231 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
2232 int oppSumWinding, const SkOpAngle* angle) {
2233 SkASSERT(angle->segment() == this);
2234 if (UseInnerWinding(maxWinding, sumWinding)) {
2235 maxWinding = sumWinding;
2236 }
2237 if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
2238 oppMaxWinding = oppSumWinding;
2239 }
2240 SkOpSpan* last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
2241 #if DEBUG_WINDING
2242 if (last) {
2243 SkDebugf("%s last id=%d windSum=", __FUNCTION__,
2244 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
2245 SkPathOpsDebug::WindingPrintf(last->fWindSum);
2246 SkDebugf(" small=%d\n", last->fSmall);
2247 }
2248 #endif
2249 return last;
2250 }
2251
2252 // FIXME: this should also mark spans with equal (x,y)
2253 // This may be called when the segment is already marked done. While this
2254 // wastes time, it shouldn't do any more than spin through the T spans.
2255 // OPTIMIZATION: abort on first done found (assuming that this code is
2256 // always called to mark segments done).
2257 void SkOpSegment::markDone(int index, int winding) {
2258 // SkASSERT(!done());
2259 SkASSERT(winding);
2260 double referenceT = fTs[index].fT;
2261 int lesser = index;
2262 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
2263 markOneDone(__FUNCTION__, lesser, winding);
2264 }
2265 do {
2266 markOneDone(__FUNCTION__, index, winding);
2267 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
2268 }
2269
2270 void SkOpSegment::markDoneBinary(int index) {
2271 double referenceT = fTs[index].fT;
2272 int lesser = index;
2273 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
2274 markOneDoneBinary(__FUNCTION__, lesser);
2275 }
2276 do {
2277 markOneDoneBinary(__FUNCTION__, index);
2278 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
2279 }
2280
2281 void SkOpSegment::markDoneUnary(int index) {
2282 double referenceT = fTs[index].fT;
2283 int lesser = index;
2284 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
2285 markOneDoneUnary(__FUNCTION__, lesser);
2286 }
2287 do {
2288 markOneDoneUnary(__FUNCTION__, index);
2289 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
2290 }
2291
2292 void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) {
2293 SkOpSpan* span = markOneWinding(funName, tIndex, winding);
2294 if (!span) {
2295 return;
2296 }
2297 span->fDone = true;
2298 fDoneSpans++;
2299 }
2300
2301 void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) {
2302 SkOpSpan* span = verifyOneWinding(funName, tIndex);
2303 if (!span) {
2304 return;
2305 }
2306 span->fDone = true;
2307 fDoneSpans++;
2308 }
2309
2310 void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) {
2311 SkOpSpan* span = verifyOneWindingU(funName, tIndex);
2312 if (!span) {
2313 return;
2314 }
2315 span->fDone = true;
2316 fDoneSpans++;
2317 }
2318
2319 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding) {
2320 SkOpSpan& span = fTs[tIndex];
2321 if (span.fDone) {
2322 return NULL;
2323 }
2324 #if DEBUG_MARK_DONE
2325 debugShowNewWinding(funName, span, winding);
2326 #endif
2327 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
2328 SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
2329 span.fWindSum = winding;
2330 return &span;
2331 }
2332
2333 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding,
2334 int oppWinding) {
2335 SkOpSpan& span = fTs[tIndex];
2336 if (span.fDone && !span.fSmall) {
2337 return NULL;
2338 }
2339 #if DEBUG_MARK_DONE
2340 debugShowNewWinding(funName, span, winding, oppWinding);
2341 #endif
2342 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
2343 SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
2344 span.fWindSum = winding;
2345 SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
2346 SkASSERT(abs(oppWinding) <= SkPathOpsDebug::gMaxWindSum);
2347 span.fOppSum = oppWinding;
2348 return &span;
2349 }
2350
2351 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
2352 bool SkOpSegment::clockwise(int tStart, int tEnd) const {
2353 SkASSERT(fVerb != SkPath::kLine_Verb);
2354 SkPoint edge[4];
2355 subDivide(tStart, tEnd, edge);
2356 int points = SkPathOpsVerbToPoints(fVerb);
2357 double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
2358 if (fVerb == SkPath::kCubic_Verb) {
2359 SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY);
2360 if (edge[1].fY < lesser && edge[2].fY < lesser) {
2361 SkDLine tangent1 = {{ {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1].fY} }};
2362 SkDLine tangent2 = {{ {edge[2].fX, edge[2].fY}, {edge[3].fX, edge[3].fY} }};
2363 if (SkIntersections::Test(tangent1, tangent2)) {
2364 SkPoint topPt = cubic_top(fPts, fTs[tStart].fT, fTs[tEnd].fT);
2365 sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY);
2366 sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY);
2367 return sum <= 0;
2368 }
2369 }
2370 }
2371 for (int idx = 0; idx < points; ++idx){
2372 sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
2373 }
2374 return sum <= 0;
2375 }
2376
2377 bool SkOpSegment::monotonicInY(int tStart, int tEnd) const {
2378 if (fVerb == SkPath::kLine_Verb) {
2379 return false;
2380 }
2381 if (fVerb == SkPath::kQuad_Verb) {
2382 SkDQuad dst = SkDQuad::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
2383 return dst.monotonicInY();
2384 }
2385 SkASSERT(fVerb == SkPath::kCubic_Verb);
2386 SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
2387 return dst.monotonicInY();
2388 }
2389
2390 bool SkOpSegment::serpentine(int tStart, int tEnd) const {
2391 if (fVerb != SkPath::kCubic_Verb) {
2392 return false;
2393 }
2394 SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
2395 return dst.serpentine();
2396 }
2397
2398 SkOpSpan* SkOpSegment::verifyOneWinding(const char* funName, int tIndex) {
2399 SkOpSpan& span = fTs[tIndex];
2400 if (span.fDone) {
2401 return NULL;
2402 }
2403 #if DEBUG_MARK_DONE
2404 debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
2405 #endif
2406 // If the prior angle in the sort is unorderable, the winding sum may not be computable.
2407 // To enable the assert, the 'prior is unorderable' state could be
2408 // piped down to this test, but not sure it's worth it.
2409 // (Once the sort order is stored in the span, this test may be feasible.)
2410 // SkASSERT(span.fWindSum != SK_MinS32);
2411 // SkASSERT(span.fOppSum != SK_MinS32);
2412 return &span;
2413 }
2414
2415 SkOpSpan* SkOpSegment::verifyOneWindingU(const char* funName, int tIndex) {
2416 SkOpSpan& span = fTs[tIndex];
2417 if (span.fDone) {
2418 return NULL;
2419 }
2420 #if DEBUG_MARK_DONE
2421 debugShowNewWinding(funName, span, span.fWindSum);
2422 #endif
2423 // If the prior angle in the sort is unorderable, the winding sum may not be computable.
2424 // To enable the assert, the 'prior is unorderable' state could be
2425 // piped down to this test, but not sure it's worth it.
2426 // (Once the sort order is stored in the span, this test may be feasible.)
2427 // SkASSERT(span.fWindSum != SK_MinS32);
2428 return &span;
2429 }
2430
2431 // note that just because a span has one end that is unsortable, that's
2432 // not enough to mark it done. The other end may be sortable, allowing the
2433 // span to be added.
2434 // FIXME: if abs(start - end) > 1, mark intermediates as unsortable on both ends
2435 void SkOpSegment::markUnsortable(int start, int end) {
2436 SkOpSpan* span = &fTs[start];
2437 if (start < end) {
2438 #if DEBUG_UNSORTABLE
2439 debugShowNewWinding(__FUNCTION__, *span, 0);
2440 #endif
2441 span->fUnsortableStart = true;
2442 } else {
2443 --span;
2444 #if DEBUG_UNSORTABLE
2445 debugShowNewWinding(__FUNCTION__, *span, 0);
2446 #endif
2447 span->fUnsortableEnd = true;
2448 }
2449 if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) {
2450 return;
2451 }
2452 span->fDone = true;
2453 fDoneSpans++;
2454 }
2455
2456 void SkOpSegment::markWinding(int index, int winding) {
2457 // SkASSERT(!done());
2458 SkASSERT(winding);
2459 double referenceT = fTs[index].fT;
2460 int lesser = index;
2461 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
2462 markOneWinding(__FUNCTION__, lesser, winding);
2463 }
2464 do {
2465 markOneWinding(__FUNCTION__, index, winding);
2466 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
2467 }
2468
2469 void SkOpSegment::markWinding(int index, int winding, int oppWinding) {
2470 // SkASSERT(!done());
2471 SkASSERT(winding || oppWinding);
2472 double referenceT = fTs[index].fT;
2473 int lesser = index;
2474 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
2475 markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
2476 }
2477 do {
2478 markOneWinding(__FUNCTION__, index, winding, oppWinding);
2479 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
2480 }
2481
2482 void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) {
2483 int nextDoorWind = SK_MaxS32;
2484 int nextOppWind = SK_MaxS32;
2485 if (tIndex > 0) {
2486 const SkOpSpan& below = fTs[tIndex - 1];
2487 if (approximately_negative(t - below.fT)) {
2488 nextDoorWind = below.fWindValue;
2489 nextOppWind = below.fOppValue;
2490 }
2491 }
2492 if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
2493 const SkOpSpan& above = fTs[tIndex + 1];
2494 if (approximately_negative(above.fT - t)) {
2495 nextDoorWind = above.fWindValue;
2496 nextOppWind = above.fOppValue;
2497 }
2498 }
2499 if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
2500 const SkOpSpan& below = fTs[tIndex - 1];
2501 nextDoorWind = below.fWindValue;
2502 nextOppWind = below.fOppValue;
2503 }
2504 if (nextDoorWind != SK_MaxS32) {
2505 SkOpSpan& newSpan = fTs[tIndex];
2506 newSpan.fWindValue = nextDoorWind;
2507 newSpan.fOppValue = nextOppWind;
2508 if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
2509 newSpan.fDone = true;
2510 ++fDoneSpans;
2511 }
2512 }
2513 }
2514
2515 // return span if when chasing, two or more radiating spans are not done
2516 // OPTIMIZATION: ? multiple spans is detected when there is only one valid
2517 // candidate and the remaining spans have windValue == 0 (canceled by
2518 // coincidence). The coincident edges could either be removed altogether,
2519 // or this code could be more complicated in detecting this case. Worth it?
2520 bool SkOpSegment::multipleSpans(int end) const {
2521 return end > 0 && end < fTs.count() - 1;
2522 }
2523
2524 bool SkOpSegment::nextCandidate(int* start, int* end) const {
2525 while (fTs[*end].fDone) {
2526 if (fTs[*end].fT == 1) {
2527 return false;
2528 }
2529 ++(*end);
2530 }
2531 *start = *end;
2532 *end = nextExactSpan(*start, 1);
2533 return true;
2534 }
2535
2536 SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSpan** last) {
2537 int end = nextExactSpan(*index, step);
2538 SkASSERT(end >= 0);
2539 if (fTs[end].fSmall) {
2540 *last = NULL;
2541 return NULL;
2542 }
2543 if (multipleSpans(end)) {
2544 *last = &fTs[end];
2545 return NULL;
2546 }
2547 const SkOpSpan& endSpan = fTs[end];
2548 SkOpSegment* other = endSpan.fOther;
2549 *index = endSpan.fOtherIndex;
2550 SkASSERT(*index >= 0);
2551 int otherEnd = other->nextExactSpan(*index, step);
2552 SkASSERT(otherEnd >= 0);
2553 *min = SkMin32(*index, otherEnd);
2554 if (other->fTs[*min].fSmall) {
2555 *last = NULL;
2556 return NULL;
2557 }
2558 return other;
2559 }
2560
2561 // This has callers for two different situations: one establishes the end
2562 // of the current span, and one establishes the beginning of the next span
2563 // (thus the name). When this is looking for the end of the current span,
2564 // coincidence is found when the beginning Ts contain -step and the end
2565 // contains step. When it is looking for the beginning of the next, the
2566 // first Ts found can be ignored and the last Ts should contain -step.
2567 // OPTIMIZATION: probably should split into two functions
2568 int SkOpSegment::nextSpan(int from, int step) const {
2569 const SkOpSpan& fromSpan = fTs[from];
2570 int count = fTs.count();
2571 int to = from;
2572 while (step > 0 ? ++to < count : --to >= 0) {
2573 const SkOpSpan& span = fTs[to];
2574 if (approximately_zero(span.fT - fromSpan.fT)) {
2575 continue;
2576 }
2577 return to;
2578 }
2579 return -1;
2580 }
2581
2582 // FIXME
2583 // this returns at any difference in T, vs. a preset minimum. It may be
2584 // that all callers to nextSpan should use this instead.
2585 int SkOpSegment::nextExactSpan(int from, int step) const {
2586 int to = from;
2587 if (step < 0) {
2588 const SkOpSpan& fromSpan = fTs[from];
2589 while (--to >= 0) {
2590 const SkOpSpan& span = fTs[to];
2591 if (precisely_negative(fromSpan.fT - span.fT) || span.fTiny) {
2592 continue;
2593 }
2594 return to;
2595 }
2596 } else {
2597 while (fTs[from].fTiny) {
2598 from++;
2599 }
2600 const SkOpSpan& fromSpan = fTs[from];
2601 int count = fTs.count();
2602 while (++to < count) {
2603 const SkOpSpan& span = fTs[to];
2604 if (precisely_negative(span.fT - fromSpan.fT)) {
2605 continue;
2606 }
2607 return to;
2608 }
2609 }
2610 return -1;
2611 }
2612
2613 void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
2614 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
2615 int deltaSum = spanSign(index, endIndex);
2616 int oppDeltaSum = oppSign(index, endIndex);
2617 if (operand()) {
2618 *maxWinding = *sumSuWinding;
2619 *sumWinding = *sumSuWinding -= deltaSum;
2620 *oppMaxWinding = *sumMiWinding;
2621 *oppSumWinding = *sumMiWinding -= oppDeltaSum;
2622 } else {
2623 *maxWinding = *sumMiWinding;
2624 *sumWinding = *sumMiWinding -= deltaSum;
2625 *oppMaxWinding = *sumSuWinding;
2626 *oppSumWinding = *sumSuWinding -= oppDeltaSum;
2627 }
2628 SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
2629 SkASSERT(abs(*oppSumWinding) <= SkPathOpsDebug::gMaxWindSum);
2630 }
2631
2632 void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding,
2633 int* maxWinding, int* sumWinding) {
2634 int deltaSum = spanSign(index, endIndex);
2635 *maxWinding = *sumMiWinding;
2636 *sumWinding = *sumMiWinding -= deltaSum;
2637 SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
2638 }
2639
2640 // This marks all spans unsortable so that this info is available for early
2641 // exclusion in find top and others. This could be optimized to only mark
2642 // adjacent spans that unsortable. However, this makes it difficult to later
2643 // determine starting points for edge detection in find top and the like.
2644 bool SkOpSegment::SortAngles(const SkTArray<SkOpAngle, true>& angles,
2645 SkTArray<SkOpAngle*, true>* angleList,
2646 SortAngleKind orderKind) {
2647 bool sortable = true;
2648 int angleCount = angles.count();
2649 int angleIndex;
2650 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
2651 const SkOpAngle& angle = angles[angleIndex];
2652 angleList->push_back(const_cast<SkOpAngle*>(&angle));
2653 #if DEBUG_ANGLE
2654 (*(angleList->end() - 1))->setID(angleIndex);
2655 #endif
2656 sortable &= !(angle.unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
2657 && angle.unorderable()));
2658 }
2659 if (sortable) {
2660 SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
2661 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
2662 if (angles[angleIndex].unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
2663 && angles[angleIndex].unorderable())) {
2664 sortable = false;
2665 break;
2666 }
2667 }
2668 }
2669 if (!sortable) {
2670 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
2671 const SkOpAngle& angle = angles[angleIndex];
2672 angle.segment()->markUnsortable(angle.start(), angle.end());
2673 }
2674 }
2675 return sortable;
2676 }
2677
2678 // set segments to unsortable if angle is unsortable, but do not set all angles
2679 // note that for a simple 4 way crossing, two of the edges may be orderable even though
2680 // two edges are too short to be orderable.
2681 // perhaps some classes of unsortable angles should make all shared angles unsortable, but
2682 // simple lines that have tiny crossings are always sortable on the large ends
2683 // OPTIMIZATION: check earlier when angles are added to input if any are unsortable
2684 // may make sense then to mark all segments in angle sweep as unsortableStart/unsortableEnd
2685 // solely for the purpose of short-circuiting future angle building around this center
2686 bool SkOpSegment::SortAngles2(const SkTArray<SkOpAngle, true>& angles,
2687 SkTArray<SkOpAngle*, true>* angleList) {
2688 int angleCount = angles.count();
2689 int angleIndex;
2690 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
2691 const SkOpAngle& angle = angles[angleIndex];
2692 if (angle.unsortable()) {
2693 return false;
2694 }
2695 angleList->push_back(const_cast<SkOpAngle*>(&angle));
2696 #if DEBUG_ANGLE
2697 (*(angleList->end() - 1))->setID(angleIndex);
2698 #endif
2699 }
2700 SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
2701 // at this point angles are sorted but individually may not be orderable
2702 // this means that only adjcent orderable segments may transfer winding
2703 return true;
2704 }
2705
2706 // return true if midpoints were computed
2707 bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
2708 SkASSERT(start != end);
2709 edge[0] = fTs[start].fPt;
2710 int points = SkPathOpsVerbToPoints(fVerb);
2711 edge[points] = fTs[end].fPt;
2712 if (fVerb == SkPath::kLine_Verb) {
2713 return false;
2714 }
2715 double startT = fTs[start].fT;
2716 double endT = fTs[end].fT;
2717 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
2718 // don't compute midpoints if we already have them
2719 if (fVerb == SkPath::kQuad_Verb) {
2720 edge[1] = fPts[1];
2721 return false;
2722 }
2723 SkASSERT(fVerb == SkPath::kCubic_Verb);
2724 if (start < end) {
2725 edge[1] = fPts[1];
2726 edge[2] = fPts[2];
2727 return false;
2728 }
2729 edge[1] = fPts[2];
2730 edge[2] = fPts[1];
2731 return false;
2732 }
2733 const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
2734 if (fVerb == SkPath::kQuad_Verb) {
2735 edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
2736 } else {
2737 SkASSERT(fVerb == SkPath::kCubic_Verb);
2738 SkDPoint ctrl[2];
2739 SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
2740 edge[1] = ctrl[0].asSkPoint();
2741 edge[2] = ctrl[1].asSkPoint();
2742 }
2743 return true;
2744 }
2745
2746 // return true if midpoints were computed
2747 bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
2748 SkASSERT(start != end);
2749 (*result)[0].set(fTs[start].fPt);
2750 int points = SkPathOpsVerbToPoints(fVerb);
2751 (*result)[points].set(fTs[end].fPt);
2752 if (fVerb == SkPath::kLine_Verb) {
2753 return false;
2754 }
2755 double startT = fTs[start].fT;
2756 double endT = fTs[end].fT;
2757 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
2758 // don't compute midpoints if we already have them
2759 if (fVerb == SkPath::kQuad_Verb) {
2760 (*result)[1].set(fPts[1]);
2761 return false;
2762 }
2763 SkASSERT(fVerb == SkPath::kCubic_Verb);
2764 if (start < end) {
2765 (*result)[1].set(fPts[1]);
2766 (*result)[2].set(fPts[2]);
2767 return false;
2768 }
2769 (*result)[1].set(fPts[2]);
2770 (*result)[2].set(fPts[1]);
2771 return false;
2772 }
2773 if (fVerb == SkPath::kQuad_Verb) {
2774 (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
2775 } else {
2776 SkASSERT(fVerb == SkPath::kCubic_Verb);
2777 SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
2778 }
2779 return true;
2780 }
2781
2782 void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
2783 SkPoint edge[4];
2784 subDivide(start, end, edge);
2785 (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
2786 }
2787
2788 void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt,
2789 const SkPoint& startPt) {
2790 int outCount = outsidePts->count();
2791 if (outCount == 0 || endPt != (*outsidePts)[outCount - 2]) {
2792 outsidePts->push_back(endPt);
2793 outsidePts->push_back(startPt);
2794 }
2795 }
2796
2797 void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoint& startPt) {
2798 int outCount = outsidePts->count();
2799 if (outCount == 0 || startPt != (*outsidePts)[outCount - 1]) {
2800 outsidePts->push_back(startPt);
2801 }
2802 }
2803
2804 void SkOpSegment::undoneSpan(int* start, int* end) {
2805 size_t tCount = fTs.count();
2806 size_t index;
2807 for (index = 0; index < tCount; ++index) {
2808 if (!fTs[index].fDone) {
2809 break;
2810 }
2811 }
2812 SkASSERT(index < tCount - 1);
2813 *start = index;
2814 double startT = fTs[index].fT;
2815 while (approximately_negative(fTs[++index].fT - startT))
2816 SkASSERT(index < tCount);
2817 SkASSERT(index < tCount);
2818 *end = index;
2819 }
2820
2821 int SkOpSegment::updateOppWinding(int index, int endIndex) const {
2822 int lesser = SkMin32(index, endIndex);
2823 int oppWinding = oppSum(lesser);
2824 int oppSpanWinding = oppSign(index, endIndex);
2825 if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
2826 && oppWinding != SK_MaxS32) {
2827 oppWinding -= oppSpanWinding;
2828 }
2829 return oppWinding;
2830 }
2831
2832 int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
2833 int startIndex = angle->start();
2834 int endIndex = angle->end();
2835 return updateOppWinding(endIndex, startIndex);
2836 }
2837
2838 int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
2839 int startIndex = angle->start();
2840 int endIndex = angle->end();
2841 return updateOppWinding(startIndex, endIndex);
2842 }
2843
2844 int SkOpSegment::updateWinding(int index, int endIndex) const {
2845 int lesser = SkMin32(index, endIndex);
2846 int winding = windSum(lesser);
2847 int spanWinding = spanSign(index, endIndex);
2848 if (winding && UseInnerWinding(winding - spanWinding, winding)
2849 && winding != SK_MaxS32) {
2850 winding -= spanWinding;
2851 }
2852 return winding;
2853 }
2854
2855 int SkOpSegment::updateWinding(const SkOpAngle* angle) const {
2856 int startIndex = angle->start();
2857 int endIndex = angle->end();
2858 return updateWinding(endIndex, startIndex);
2859 }
2860
2861 int SkOpSegment::updateWindingReverse(int index, int endIndex) const {
2862 int lesser = SkMin32(index, endIndex);
2863 int winding = windSum(lesser);
2864 int spanWinding = spanSign(endIndex, index);
2865 if (winding && UseInnerWindingReverse(winding - spanWinding, winding)
2866 && winding != SK_MaxS32) {
2867 winding -= spanWinding;
2868 }
2869 return winding;
2870 }
2871
2872 int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const {
2873 int startIndex = angle->start();
2874 int endIndex = angle->end();
2875 return updateWindingReverse(endIndex, startIndex);
2876 }
2877
2878 // OPTIMIZATION: does the following also work, and is it any faster?
2879 // return outerWinding * innerWinding > 0
2880 // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
2881 bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
2882 SkASSERT(outerWinding != SK_MaxS32);
2883 SkASSERT(innerWinding != SK_MaxS32);
2884 int absOut = abs(outerWinding);
2885 int absIn = abs(innerWinding);
2886 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
2887 return result;
2888 }
2889
2890 bool SkOpSegment::UseInnerWindingReverse(int outerWinding, int innerWinding) {
2891 SkASSERT(outerWinding != SK_MaxS32);
2892 SkASSERT(innerWinding != SK_MaxS32);
2893 int absOut = abs(outerWinding);
2894 int absIn = abs(innerWinding);
2895 bool result = absOut == absIn ? true : absOut < absIn;
2896 return result;
2897 }
2898
2899 int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const {
2900 if (approximately_zero(tHit - t(tIndex))) { // if we hit the end of a span, disregard
2901 return SK_MinS32;
2902 }
2903 int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);
2904 SkASSERT(winding != SK_MinS32);
2905 int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
2906 #if DEBUG_WINDING_AT_T
2907 SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal);
2908 #endif
2909 // see if a + change in T results in a +/- change in X (compute x'(T))
2910 *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
2911 if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) {
2912 *dx = fPts[2].fX - fPts[1].fX - *dx;
2913 }
2914 if (*dx == 0) {
2915 #if DEBUG_WINDING_AT_T
2916 SkDebugf(" dx=0 winding=SK_MinS32\n");
2917 #endif
2918 return SK_MinS32;
2919 }
2920 if (windVal < 0) { // reverse sign if opp contour traveled in reverse
2921 *dx = -*dx;
2922 }
2923 if (winding * *dx > 0) { // if same signs, result is negative
2924 winding += *dx > 0 ? -windVal : windVal;
2925 }
2926 #if DEBUG_WINDING_AT_T
2927 SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding);
2928 #endif
2929 return winding;
2930 }
2931
2932 int SkOpSegment::windSum(const SkOpAngle* angle) const {
2933 int start = angle->start();
2934 int end = angle->end();
2935 int index = SkMin32(start, end);
2936 return windSum(index);
2937 }
2938
2939 void SkOpSegment::zeroSpan(SkOpSpan* span) {
2940 SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
2941 span->fWindValue = 0;
2942 span->fOppValue = 0;
2943 if (span->fTiny || span->fSmall) {
2944 return;
2945 }
2946 SkASSERT(!span->fDone);
2947 span->fDone = true;
2948 ++fDoneSpans;
2949 }
2950
2951 #if DEBUG_SWAP_TOP
2952 bool SkOpSegment::controlsContainedByEnds(int tStart, int tEnd) const {
2953 if (fVerb != SkPath::kCubic_Verb) {
2954 return false;
2955 }
2956 SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
2957 return dst.controlsContainedByEnds();
2958 }
2959 #endif
2960
2961 #if DEBUG_CONCIDENT
2962 // SkASSERT if pair has not already been added
2963 void SkOpSegment::debugAddTPair(double t, const SkOpSegment& other, double otherT) const {
2964 for (int i = 0; i < fTs.count(); ++i) {
2965 if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) {
2966 return;
2967 }
2968 }
2969 SkASSERT(0);
2970 }
2971 #endif
2972
2973 #if DEBUG_CONCIDENT
2974 void SkOpSegment::debugShowTs(const char* prefix) const {
2975 SkDebugf("%s %s id=%d", __FUNCTION__, prefix, fID);
2976 int lastWind = -1;
2977 int lastOpp = -1;
2978 double lastT = -1;
2979 int i;
2980 for (i = 0; i < fTs.count(); ++i) {
2981 bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue
2982 || lastOpp != fTs[i].fOppValue;
2983 if (change && lastWind >= 0) {
2984 SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
2985 lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
2986 }
2987 if (change) {
2988 SkDebugf(" [o=%d", fTs[i].fOther->fID);
2989 lastWind = fTs[i].fWindValue;
2990 lastOpp = fTs[i].fOppValue;
2991 lastT = fTs[i].fT;
2992 } else {
2993 SkDebugf(",%d", fTs[i].fOther->fID);
2994 }
2995 }
2996 if (i <= 0) {
2997 return;
2998 }
2999 SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
3000 lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
3001 if (fOperand) {
3002 SkDebugf(" operand");
3003 }
3004 if (done()) {
3005 SkDebugf(" done");
3006 }
3007 SkDebugf("\n");
3008 }
3009 #endif
3010
3011 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
3012 void SkOpSegment::debugShowActiveSpans() const {
3013 debugValidate();
3014 if (done()) {
3015 return;
3016 }
3017 #if DEBUG_ACTIVE_SPANS_SHORT_FORM
3018 int lastId = -1;
3019 double lastT = -1;
3020 #endif
3021 for (int i = 0; i < fTs.count(); ++i) {
3022 if (fTs[i].fDone) {
3023 continue;
3024 }
3025 SkASSERT(i < fTs.count() - 1);
3026 #if DEBUG_ACTIVE_SPANS_SHORT_FORM
3027 if (lastId == fID && lastT == fTs[i].fT) {
3028 continue;
3029 }
3030 lastId = fID;
3031 lastT = fTs[i].fT;
3032 #endif
3033 SkDebugf("%s id=%d", __FUNCTION__, fID);
3034 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
3035 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
3036 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
3037 }
3038 const SkOpSpan* span = &fTs[i];
3039 SkDebugf(") t=%1.9g (%1.9g,%1.9g)", span->fT, xAtT(span), yAtT(span));
3040 int iEnd = i + 1;
3041 while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd].fT)) {
3042 ++iEnd;
3043 }
3044 SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT);
3045 const SkOpSegment* other = fTs[i].fOther;
3046 SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",
3047 other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);
3048 if (fTs[i].fWindSum == SK_MinS32) {
3049 SkDebugf("?");
3050 } else {
3051 SkDebugf("%d", fTs[i].fWindSum);
3052 }
3053 SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue);
3054 }
3055 }
3056 #endif
3057
3058
3059 #if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
3060 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding) {
3061 const SkPoint& pt = xyAtT(&span);
3062 SkDebugf("%s id=%d", fun, fID);
3063 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
3064 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
3065 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
3066 }
3067 SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
3068 fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
3069 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d windSum=",
3070 span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
3071 (&span)[1].fT, winding);
3072 if (span.fWindSum == SK_MinS32) {
3073 SkDebugf("?");
3074 } else {
3075 SkDebugf("%d", span.fWindSum);
3076 }
3077 SkDebugf(" windValue=%d\n", span.fWindValue);
3078 }
3079
3080 void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding,
3081 int oppWinding) {
3082 const SkPoint& pt = xyAtT(&span);
3083 SkDebugf("%s id=%d", fun, fID);
3084 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
3085 for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
3086 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
3087 }
3088 SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
3089 fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
3090 SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d newOppSum=%d oppSum=",
3091 span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
3092 (&span)[1].fT, winding, oppWinding);
3093 if (span.fOppSum == SK_MinS32) {
3094 SkDebugf("?");
3095 } else {
3096 SkDebugf("%d", span.fOppSum);
3097 }
3098 SkDebugf(" windSum=");
3099 if (span.fWindSum == SK_MinS32) {
3100 SkDebugf("?");
3101 } else {
3102 SkDebugf("%d", span.fWindSum);
3103 }
3104 SkDebugf(" windValue=%d\n", span.fWindValue);
3105 }
3106 #endif
3107
3108 #if DEBUG_SORT || DEBUG_SWAP_TOP
3109 void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
3110 int first, const int contourWinding,
3111 const int oppContourWinding, bool sortable) const {
3112 if (--SkPathOpsDebug::gSortCount < 0) {
3113 return;
3114 }
3115 if (!sortable) {
3116 if (angles.count() == 0) {
3117 return;
3118 }
3119 if (first < 0) {
3120 first = 0;
3121 }
3122 }
3123 SkASSERT(angles[first]->segment() == this);
3124 SkASSERT(!sortable || angles.count() > 1);
3125 int lastSum = contourWinding;
3126 int oppLastSum = oppContourWinding;
3127 const SkOpAngle* firstAngle = angles[first];
3128 int windSum = lastSum - spanSign(firstAngle);
3129 int oppoSign = oppSign(firstAngle);
3130 int oppWindSum = oppLastSum - oppoSign;
3131 #define WIND_AS_STRING(x) char x##Str[12]; \
3132 if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \
3133 else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
3134 WIND_AS_STRING(contourWinding);
3135 WIND_AS_STRING(oppContourWinding);
3136 SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__,
3137 contourWindingStr, oppContourWindingStr, spanSign(angles[first]));
3138 int index = first;
3139 bool firstTime = true;
3140 do {
3141 const SkOpAngle& angle = *angles[index];
3142 const SkOpSegment& segment = *angle.segment();
3143 int start = angle.start();
3144 int end = angle.end();
3145 const SkOpSpan& sSpan = segment.fTs[start];
3146 const SkOpSpan& eSpan = segment.fTs[end];
3147 const SkOpSpan& mSpan = segment.fTs[SkMin32(start, end)];
3148 bool opp = segment.fOperand ^ fOperand;
3149 if (!firstTime) {
3150 oppoSign = segment.oppSign(&angle);
3151 if (opp) {
3152 oppLastSum = oppWindSum;
3153 oppWindSum -= segment.spanSign(&angle);
3154 if (oppoSign) {
3155 lastSum = windSum;
3156 windSum -= oppoSign;
3157 }
3158 } else {
3159 lastSum = windSum;
3160 windSum -= segment.spanSign(&angle);
3161 if (oppoSign) {
3162 oppLastSum = oppWindSum;
3163 oppWindSum -= oppoSign;
3164 }
3165 }
3166 }
3167 SkDebugf("%s [%d] %s", __FUNCTION__, index,
3168 angle.unsortable() ? "*** UNSORTABLE *** " : "");
3169 #if DEBUG_SORT_COMPACT
3170 SkDebugf("id=%d %s start=%d (%1.9g,%1.9g) end=%d (%1.9g,%1.9g)",
3171 segment.fID, kLVerbStr[SkPathOpsVerbToPoints(segment.fVerb)],
3172 start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
3173 segment.xAtT(&eSpan), segment.yAtT(&eSpan));
3174 #else
3175 switch (segment.fVerb) {
3176 case SkPath::kLine_Verb:
3177 SkDebugf(LINE_DEBUG_STR, LINE_DEBUG_DATA(segment.fPts));
3178 break;
3179 case SkPath::kQuad_Verb:
3180 SkDebugf(QUAD_DEBUG_STR, QUAD_DEBUG_DATA(segment.fPts));
3181 break;
3182 case SkPath::kCubic_Verb:
3183 SkDebugf(CUBIC_DEBUG_STR, CUBIC_DEBUG_DATA(segment.fPts));
3184 break;
3185 default:
3186 SkASSERT(0);
3187 }
3188 SkDebugf(" tStart=%1.9g tEnd=%1.9g", sSpan.fT, eSpan.fT);
3189 #endif
3190 SkDebugf(" sign=%d windValue=%d windSum=", angle.sign(), mSpan.fWindValue);
3191 SkPathOpsDebug::WindingPrintf(mSpan.fWindSum);
3192 int last, wind;
3193 if (opp) {
3194 last = oppLastSum;
3195 wind = oppWindSum;
3196 } else {
3197 last = lastSum;
3198 wind = windSum;
3199 }
3200 bool useInner = SkPathOpsDebug::ValidWind(last) && SkPathOpsDebug::ValidWind(wind)
3201 && UseInnerWinding(last, wind);
3202 WIND_AS_STRING(last);
3203 WIND_AS_STRING(wind);
3204 WIND_AS_STRING(lastSum);
3205 WIND_AS_STRING(oppLastSum);
3206 WIND_AS_STRING(windSum);
3207 WIND_AS_STRING(oppWindSum);
3208 #undef WIND_AS_STRING
3209 if (!oppoSign) {
3210 SkDebugf(" %s->%s (max=%s)", lastStr, windStr, useInner ? windStr : lastStr);
3211 } else {
3212 SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr,
3213 opp ? windSumStr : oppWindSumStr);
3214 }
3215 SkDebugf(" done=%d unord=%d small=%d tiny=%d opp=%d\n",
3216 mSpan.fDone, angle.unorderable(), mSpan.fSmall, mSpan.fTiny, opp);
3217 ++index;
3218 if (index == angles.count()) {
3219 index = 0;
3220 }
3221 if (firstTime) {
3222 firstTime = false;
3223 }
3224 } while (index != first);
3225 }
3226
3227 void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
3228 int first, bool sortable) {
3229 if (!sortable) {
3230 if (angles.count() == 0) {
3231 return;
3232 }
3233 if (first < 0) {
3234 first = 0;
3235 }
3236 }
3237 const SkOpAngle* firstAngle = angles[first];
3238 const SkOpSegment* segment = firstAngle->segment();
3239 int winding = segment->updateWinding(firstAngle);
3240 int oppWinding = segment->updateOppWinding(firstAngle);
3241 debugShowSort(fun, angles, first, winding, oppWinding, sortable);
3242 }
3243
3244 #endif
3245
3246 #if DEBUG_SHOW_WINDING
3247 int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const {
3248 if (!(1 << fID & ofInterest)) {
3249 return 0;
3250 }
3251 int sum = 0;
3252 SkTArray<char, true> slots(slotCount * 2);
3253 memset(slots.begin(), ' ', slotCount * 2);
3254 for (int i = 0; i < fTs.count(); ++i) {
3255 // if (!(1 << fTs[i].fOther->fID & ofInterest)) {
3256 // continue;
3257 // }
3258 sum += fTs[i].fWindValue;
3259 slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue);
3260 sum += fTs[i].fOppValue;
3261 slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue);
3262 }
3263 SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount,
3264 slots.begin() + slotCount);
3265 return sum;
3266 }
3267 #endif
3268
3269 void SkOpSegment::debugValidate() const {
3270 #if DEBUG_VALIDATE
3271 int count = fTs.count();
3272 SkASSERT(count >= 2);
3273 SkASSERT(fTs[0].fT == 0);
3274 SkASSERT(fTs[count - 1].fT == 1);
3275 int done = 0;
3276 double t = -1;
3277 for (int i = 0; i < count; ++i) {
3278 const SkOpSpan& span = fTs[i];
3279 SkASSERT(t <= span.fT);
3280 t = span.fT;
3281 int otherIndex = span.fOtherIndex;
3282 const SkOpSegment* other = span.fOther;
3283 const SkOpSpan& otherSpan = other->fTs[otherIndex];
3284 SkASSERT(otherSpan.fPt == span.fPt);
3285 SkASSERT(otherSpan.fOtherT == t);
3286 SkASSERT(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]);
3287 done += span.fDone;
3288 }
3289 SkASSERT(done == fDoneSpans);
3290 #endif
3291 }
3292
3293 #ifdef SK_DEBUG
3294 void SkOpSegment::dumpPts() const {
3295 int last = SkPathOpsVerbToPoints(fVerb);
3296 SkDebugf("{{");
3297 int index = 0;
3298 do {
3299 SkDPoint::dump(fPts[index]);
3300 SkDebugf(", ");
3301 } while (++index < last);
3302 SkDPoint::dump(fPts[index]);
3303 SkDebugf("}}\n");
3304 }
3305
3306 void SkOpSegment::dumpDPts() const {
3307 int count = SkPathOpsVerbToPoints(fVerb);
3308 SkDebugf("{{");
3309 int index = 0;
3310 do {
3311 SkDPoint dPt = {fPts[index].fX, fPts[index].fY};
3312 dPt.dump();
3313 if (index != count) {
3314 SkDebugf(", ");
3315 }
3316 } while (++index <= count);
3317 SkDebugf("}}\n");
3318 }
3319
3320 void SkOpSegment::dumpSpans() const {
3321 int count = this->count();
3322 for (int index = 0; index < count; ++index) {
3323 const SkOpSpan& span = this->span(index);
3324 SkDebugf("[%d] ", index);
3325 span.dump();
3326 }
3327 }
3328 #endif
3329