2 * Copyright 2012 Google Inc.
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
7 #include "SkIntersections.h"
8 #include "SkOpContour.h"
9 #include "SkOpSegment.h"
10 #include "SkPathWriter.h"
13 #define F (false) // discard the edge
14 #define T (true) // keep the edge
16 static const bool gUnaryActiveEdge[2][2] = {
22 static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = {
24 // miTo=0 miTo=1 miTo=0 miTo=1
25 // suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1
26 // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1
27 {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
28 {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
29 {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
30 {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
37 kOutsideTrackedTCount = 16, // FIXME: determine what this should be
38 kMissingSpanCount = 4, // FIXME: determine what this should be
41 const SkOpAngle* SkOpSegment::activeAngle(int index, int* start, int* end, bool* done,
42 bool* sortable) const {
43 if (const SkOpAngle* result = activeAngleInner(index, start, end, done, sortable)) {
46 double referenceT = fTs[index].fT;
49 && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
50 if (const SkOpAngle* result = activeAngleOther(lesser, start, end, done, sortable)) {
55 if (const SkOpAngle* result = activeAngleOther(index, start, end, done, sortable)) {
58 if (++index == fTs.count()) {
61 if (fTs[index - 1].fTiny) {
62 referenceT = fTs[index].fT;
65 } while (precisely_negative(fTs[index].fT - referenceT));
69 const SkOpAngle* SkOpSegment::activeAngleInner(int index, int* start, int* end, bool* done,
70 bool* sortable) const {
71 int next = nextExactSpan(index, 1);
73 const SkOpSpan& upSpan = fTs[index];
74 if (upSpan.fWindValue || upSpan.fOppValue) {
80 if (upSpan.fWindSum != SK_MinS32) {
81 return spanToAngle(index, next);
86 SkASSERT(upSpan.fDone);
89 int prev = nextExactSpan(index, -1);
90 // edge leading into junction
92 const SkOpSpan& downSpan = fTs[prev];
93 if (downSpan.fWindValue || downSpan.fOppValue) {
98 if (!downSpan.fDone) {
99 if (downSpan.fWindSum != SK_MinS32) {
100 return spanToAngle(index, prev);
105 SkASSERT(downSpan.fDone);
111 const SkOpAngle* SkOpSegment::activeAngleOther(int index, int* start, int* end, bool* done,
112 bool* sortable) const {
113 const SkOpSpan* span = &fTs[index];
114 SkOpSegment* other = span->fOther;
115 int oIndex = span->fOtherIndex;
116 return other->activeAngleInner(oIndex, start, end, done, sortable);
119 SkPoint SkOpSegment::activeLeftTop(int* firstT) const {
121 SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
122 int count = fTs.count();
123 // see if either end is not done since we want smaller Y of the pair
124 bool lastDone = true;
126 for (int index = 0; index < count; ++index) {
127 const SkOpSpan& span = fTs[index];
128 if (span.fDone && lastDone) {
131 if (approximately_negative(span.fT - lastT)) {
135 const SkPoint& xy = xyAtT(&span);
136 if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
142 if (fVerb != SkPath::kLine_Verb && !lastDone) {
143 SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT, span.fT);
144 if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
145 && topPt.fX > curveTop.fX)) {
155 lastDone = span.fDone;
160 bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op) {
161 int sumMiWinding = updateWinding(endIndex, index);
162 int sumSuWinding = updateOppWinding(endIndex, index);
164 SkTSwap<int>(sumMiWinding, sumSuWinding);
166 return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding);
169 bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
170 int* sumMiWinding, int* sumSuWinding) {
171 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
172 setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
173 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
179 miFrom = (oppMaxWinding & xorMiMask) != 0;
180 miTo = (oppSumWinding & xorMiMask) != 0;
181 suFrom = (maxWinding & xorSuMask) != 0;
182 suTo = (sumWinding & xorSuMask) != 0;
184 miFrom = (maxWinding & xorMiMask) != 0;
185 miTo = (sumWinding & xorMiMask) != 0;
186 suFrom = (oppMaxWinding & xorSuMask) != 0;
187 suTo = (oppSumWinding & xorSuMask) != 0;
189 bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
191 SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n",
192 __FUNCTION__, debugID(), span(index).fT, span(endIndex).fT,
193 SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
198 bool SkOpSegment::activeWinding(int index, int endIndex) {
199 int sumWinding = updateWinding(endIndex, index);
200 return activeWinding(index, endIndex, &sumWinding);
203 bool SkOpSegment::activeWinding(int index, int endIndex, int* sumWinding) {
205 setUpWinding(index, endIndex, &maxWinding, sumWinding);
206 bool from = maxWinding != 0;
207 bool to = *sumWinding != 0;
208 bool result = gUnaryActiveEdge[from][to];
212 void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt,
213 SkOpSegment* other) {
215 int tCount = fTs.count();
217 int oCount = other->fTs.count();
220 } while (startPt != fTs[tIndex].fPt && tIndex < tCount);
221 int tIndexStart = tIndex;
224 } while (endPt != other->fTs[oIndex].fPt && oIndex < oCount);
225 int oIndexStart = oIndex;
226 const SkPoint* nextPt;
228 nextPt = &fTs[++tIndex].fPt;
229 SkASSERT(fTs[tIndex].fT < 1 || startPt != *nextPt);
230 } while (startPt == *nextPt);
231 double nextT = fTs[tIndex].fT;
232 const SkPoint* oNextPt;
234 oNextPt = &other->fTs[++oIndex].fPt;
235 SkASSERT(other->fTs[oIndex].fT < 1 || endPt != *oNextPt);
236 } while (endPt == *oNextPt);
237 double oNextT = other->fTs[oIndex].fT;
238 // at this point, spans before and after are at:
239 // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
240 // if tIndexStart == 0, no prior span
241 // if nextT == 1, no following span
243 // advance the span with zero winding
244 // if the following span exists (not past the end, non-zero winding)
245 // connect the two edges
246 if (!fTs[tIndexStart].fWindValue) {
247 if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
249 SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
250 __FUNCTION__, fID, other->fID, tIndexStart - 1,
251 fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
252 xyAtT(tIndexStart).fY);
254 addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false,
255 fTs[tIndexStart].fPt);
257 if (nextT < 1 && fTs[tIndex].fWindValue) {
259 SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
260 __FUNCTION__, fID, other->fID, tIndex,
261 fTs[tIndex].fT, xyAtT(tIndex).fX,
264 addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
267 SkASSERT(!other->fTs[oIndexStart].fWindValue);
268 if (oIndexStart > 0 && other->fTs[oIndexStart - 1].fWindValue) {
270 SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
271 __FUNCTION__, fID, other->fID, oIndexStart - 1,
272 other->fTs[oIndexStart].fT, other->xyAtT(oIndexStart).fX,
273 other->xyAtT(oIndexStart).fY);
274 other->debugAddTPair(other->fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
277 if (oNextT < 1 && other->fTs[oIndex].fWindValue) {
279 SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
280 __FUNCTION__, fID, other->fID, oIndex,
281 other->fTs[oIndex].fT, other->xyAtT(oIndex).fX,
282 other->xyAtT(oIndex).fY);
283 other->debugAddTPair(other->fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
289 void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt,
290 SkOpSegment* other) {
291 // walk this to startPt
292 // walk other to startPt
293 // if either is > 0, add a pointer to the other, copying adjacent winding
298 } while (startPt != fTs[tIndex].fPt);
299 int ttIndex = tIndex;
300 bool checkOtherTMatch = false;
302 const SkOpSpan& span = fTs[ttIndex];
303 if (startPt != span.fPt) {
306 if (span.fOther == other && span.fPt == startPt) {
307 checkOtherTMatch = true;
310 } while (++ttIndex < count());
313 } while (startPt != other->fTs[oIndex].fPt);
314 bool skipAdd = false;
315 if (checkOtherTMatch) {
316 int ooIndex = oIndex;
318 const SkOpSpan& oSpan = other->fTs[ooIndex];
319 if (startPt != oSpan.fPt) {
322 if (oSpan.fT == fTs[ttIndex].fOtherT) {
326 } while (++ooIndex < other->count());
328 if ((tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) && !skipAdd) {
329 addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt);
331 SkPoint nextPt = startPt;
333 const SkPoint* workPt;
335 workPt = &fTs[++tIndex].fPt;
336 } while (nextPt == *workPt);
337 const SkPoint* oWorkPt;
339 oWorkPt = &other->fTs[++oIndex].fPt;
340 } while (nextPt == *oWorkPt);
342 double tStart = fTs[tIndex].fT;
343 double oStart = other->fTs[oIndex].fT;
344 if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) {
347 if (*workPt == *oWorkPt) {
348 addTPair(tStart, other, oStart, false, nextPt);
350 } while (endPt != nextPt);
353 void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
354 init(pts, SkPath::kCubic_Verb, operand, evenOdd);
355 fBounds.setCubicBounds(pts);
358 void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active) const {
361 int lastT = fTs.count() - 1;
362 if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
365 // OPTIMIZE? if not active, skip remainder and return xyAtT(end)
366 subDivide(start, end, edge);
370 bool reverse = ePtr == fPts && start != 0;
372 path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
374 case SkPath::kLine_Verb:
375 path->deferredLine(ePtr[0]);
377 case SkPath::kQuad_Verb:
378 path->quadTo(ePtr[1], ePtr[0]);
380 case SkPath::kCubic_Verb:
381 path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
388 path->deferredMoveLine(ePtr[0]);
390 case SkPath::kLine_Verb:
391 path->deferredLine(ePtr[1]);
393 case SkPath::kQuad_Verb:
394 path->quadTo(ePtr[1], ePtr[2]);
396 case SkPath::kCubic_Verb:
397 path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
404 // return ePtr[SkPathOpsVerbToPoints(fVerb)];
407 void SkOpSegment::addEndSpan(int endIndex) {
408 SkASSERT(span(endIndex).fT == 1 || (span(endIndex).fTiny
409 && approximately_greater_than_one(span(endIndex).fT)));
410 int spanCount = fTs.count();
411 int startIndex = endIndex - 1;
412 while (fTs[startIndex].fT == 1 || fTs[startIndex].fTiny) {
414 SkASSERT(startIndex > 0);
417 SkOpAngle& angle = fAngles.push_back();
418 angle.set(this, spanCount - 1, startIndex);
420 debugCheckPointsEqualish(endIndex, spanCount);
422 setFromAngle(endIndex, &angle);
425 void SkOpSegment::setFromAngle(int endIndex, SkOpAngle* angle) {
426 int spanCount = fTs.count();
428 fTs[endIndex].fFromAngle = angle;
429 } while (++endIndex < spanCount);
432 void SkOpSegment::addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
433 init(pts, SkPath::kLine_Verb, operand, evenOdd);
437 // add 2 to edge or out of range values to get T extremes
438 void SkOpSegment::addOtherT(int index, double otherT, int otherIndex) {
439 SkOpSpan& span = fTs[index];
440 if (precisely_zero(otherT)) {
442 } else if (precisely_equal(otherT, 1)) {
445 span.fOtherT = otherT;
446 span.fOtherIndex = otherIndex;
449 void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
450 init(pts, SkPath::kQuad_Verb, operand, evenOdd);
451 fBounds.setQuadBounds(pts);
454 SkOpAngle* SkOpSegment::addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** anglePtr) {
455 int spanIndex = count() - 1;
456 int startIndex = nextExactSpan(spanIndex, -1);
457 SkASSERT(startIndex >= 0);
458 SkOpAngle& angle = fAngles.push_back();
460 angle.set(this, spanIndex, startIndex);
461 setFromAngle(spanIndex, &angle);
463 int oStartIndex, oEndIndex;
465 const SkOpSpan& span = fTs[spanIndex];
466 SkASSERT(span.fT > 0);
468 oStartIndex = span.fOtherIndex;
469 oEndIndex = other->nextExactSpan(oStartIndex, 1);
470 if (oEndIndex > 0 && other->span(oStartIndex).fWindValue) {
473 oEndIndex = oStartIndex;
474 oStartIndex = other->nextExactSpan(oEndIndex, -1);
476 } while (oStartIndex < 0 || !other->span(oStartIndex).fWindSum);
477 SkOpAngle& oAngle = other->fAngles.push_back();
478 oAngle.set(other, oStartIndex, oEndIndex);
479 other->setToAngle(oEndIndex, &oAngle);
484 SkOpAngle* SkOpSegment::addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** anglePtr) {
485 int endIndex = nextExactSpan(0, 1);
486 SkASSERT(endIndex > 0);
487 SkOpAngle& angle = fAngles.push_back();
489 angle.set(this, 0, endIndex);
490 setToAngle(endIndex, &angle);
493 int oStartIndex, oEndIndex;
495 const SkOpSpan& span = fTs[spanIndex];
496 SkASSERT(span.fT < 1);
498 oEndIndex = span.fOtherIndex;
499 oStartIndex = other->nextExactSpan(oEndIndex, -1);
500 if (oStartIndex >= 0 && other->span(oStartIndex).fWindValue) {
503 oStartIndex = oEndIndex;
504 oEndIndex = other->nextExactSpan(oStartIndex, 1);
506 } while (oEndIndex < 0 || !other->span(oStartIndex).fWindValue);
507 SkOpAngle& oAngle = other->fAngles.push_back();
508 oAngle.set(other, oEndIndex, oStartIndex);
509 other->setFromAngle(oEndIndex, &oAngle);
514 SkOpAngle* SkOpSegment::addSingletonAngles(int step) {
516 SkOpAngle* angle, * otherAngle;
518 otherAngle = addSingletonAngleUp(&other, &angle);
520 otherAngle = addSingletonAngleDown(&other, &angle);
522 angle->insert(otherAngle);
526 void SkOpSegment::addStartSpan(int endIndex) {
528 SkOpAngle& angle = fAngles.push_back();
529 angle.set(this, index, endIndex);
531 debugCheckPointsEqualish(index, endIndex);
533 setToAngle(endIndex, &angle);
536 void SkOpSegment::setToAngle(int endIndex, SkOpAngle* angle) {
539 fTs[index].fToAngle = angle;
540 } while (++index < endIndex);
543 // Defer all coincident edge processing until
544 // after normal intersections have been computed
546 // no need to be tricky; insert in normal T order
547 // resolve overlapping ts when considering coincidence later
549 // add non-coincident intersection. Resulting edges are sorted in T.
550 int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) {
551 SkASSERT(this != other || fVerb == SkPath::kCubic_Verb);
552 #if 0 // this needs an even rougher association to be useful
553 SkASSERT(SkDPoint::RoughlyEqual(ptAtT(newT), pt));
555 const SkPoint& firstPt = fPts[0];
556 const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
557 SkASSERT(newT == 0 || !precisely_zero(newT));
558 SkASSERT(newT == 1 || !precisely_equal(newT, 1));
559 // FIXME: in the pathological case where there is a ton of intercepts,
562 int tCount = fTs.count();
563 for (int index = 0; index < tCount; ++index) {
564 // OPTIMIZATION: if there are three or more identical Ts, then
565 // the fourth and following could be further insertion-sorted so
566 // that all the edges are clockwise or counterclockwise.
567 // This could later limit segment tests to the two adjacent
568 // neighbors, although it doesn't help with determining which
569 // circular direction to go in.
570 const SkOpSpan& span = fTs[index];
571 if (newT < span.fT) {
575 if (newT == span.fT) {
576 if (pt == span.fPt) {
580 if ((pt == firstPt && newT == 0) || (span.fPt == lastPt && newT == 1)) {
587 if (insertedAt >= 0) {
588 span = fTs.insert(insertedAt);
595 span->fOther = other;
598 // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
599 SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
600 && approximately_equal(xyAtT(newT).fY, pt.fY));
602 span->fFromAngle = NULL;
603 span->fToAngle = NULL;
604 span->fWindSum = SK_MinS32;
605 span->fOppSum = SK_MinS32;
606 span->fWindValue = 1;
608 span->fChased = false;
609 span->fCoincident = false;
612 span->fMultiple = false;
613 span->fSmall = false;
615 if ((span->fDone = newT == 1)) {
619 // FIXME: note that this relies on spans being a continguous array
620 // find range of spans with nearly the same point as this one
621 while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) {
622 if (fVerb == SkPath::kCubic_Verb) {
623 double tInterval = newT - span[less].fT;
624 double tMid = newT - tInterval / 2;
625 SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
626 if (!midPt.approximatelyEqual(xyAtT(span))) {
633 while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, pt)) {
634 if (fVerb == SkPath::kCubic_Verb) {
635 double tEndInterval = span[more].fT - newT;
636 double tMid = newT - tEndInterval / 2;
637 SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
638 if (!midEndPt.approximatelyEqual(xyAtT(span))) {
646 while (more - 1 > less && span[more].fPt == span[more - 1].fPt
647 && span[more].fT == span[more - 1].fT) {
653 if (precisely_negative(span[more].fT - span[less].fT)) {
656 // if the total range of t values is big enough, mark all tiny
657 bool tiny = span[less].fPt == span[more].fPt;
660 fSmall = span[index].fSmall = true;
661 fTiny |= span[index].fTiny = tiny;
662 if (!span[index].fDone) {
663 span[index].fDone = true;
666 } while (++index < more);
670 // set spans from start to end to decrement by one
671 // note this walks other backwards
672 // FIXME: there's probably an edge case that can be constructed where
673 // two span in one segment are separated by float epsilon on one span but
674 // not the other, if one segment is very small. For this
675 // case the counts asserted below may or may not be enough to separate the
676 // spans. Even if the counts work out, what if the spans aren't correctly
677 // sorted? It feels better in such a case to match the span's other span
678 // pointer since both coincident segments must contain the same spans.
679 // FIXME? It seems that decrementing by one will fail for complex paths that
680 // have three or more coincident edges. Shouldn't this subtract the difference
681 // between the winding values?
683 this 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4
684 other 2<<<<1<<<<0 2<<<<1<<<<0 2<<<<1<<<<0
686 startPt endPt test/oTest first pos test/oTest final pos
688 void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) {
689 bool binary = fOperand != other->fOperand;
691 while (startPt != fTs[index].fPt) {
692 SkASSERT(index < fTs.count());
695 while (index > 0 && precisely_equal(fTs[index].fT, fTs[index - 1].fT)) {
698 bool oFoundEnd = false;
699 int oIndex = other->fTs.count();
700 while (startPt != other->fTs[--oIndex].fPt) { // look for startPt match
701 SkASSERT(oIndex > 0);
703 double oStartT = other->fTs[oIndex].fT;
704 // look for first point beyond match
705 while (startPt == other->fTs[--oIndex].fPt || precisely_equal(oStartT, other->fTs[oIndex].fT)) {
706 SkASSERT(oIndex > 0);
708 SkOpSpan* test = &fTs[index];
709 SkOpSpan* oTest = &other->fTs[oIndex];
710 SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
711 SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
712 bool decrement, track, bigger;
713 int originalWindValue;
714 const SkPoint* testPt;
715 const SkPoint* oTestPt;
717 SkASSERT(test->fT < 1);
718 SkASSERT(oTest->fT < 1);
719 decrement = test->fWindValue && oTest->fWindValue;
720 track = test->fWindValue || oTest->fWindValue;
721 bigger = test->fWindValue >= oTest->fWindValue;
723 double testT = test->fT;
724 oTestPt = &oTest->fPt;
725 double oTestT = oTest->fT;
728 if (binary && bigger) {
734 TrackOutsidePair(&outsidePts, *testPt, *oTestPt);
736 SkASSERT(index < fTs.count() - 1);
737 test = &fTs[++index];
738 } while (*testPt == test->fPt || precisely_equal(testT, test->fT));
739 originalWindValue = oTest->fWindValue;
741 SkASSERT(oTest->fT < 1);
742 SkASSERT(originalWindValue == oTest->fWindValue);
744 if (binary && !bigger) {
747 other->decrementSpan(oTest);
750 TrackOutsidePair(&oOutsidePts, *oTestPt, *testPt);
755 oFoundEnd |= endPt == oTest->fPt;
756 oTest = &other->fTs[--oIndex];
757 } while (*oTestPt == oTest->fPt || precisely_equal(oTestT, oTest->fT));
758 } while (endPt != test->fPt && test->fT < 1);
759 // FIXME: determine if canceled edges need outside ts added
761 for (int oIdx2 = oIndex; oIdx2 >= 0; --oIdx2) {
762 SkOpSpan* oTst2 = &other->fTs[oIdx2];
763 if (originalWindValue != oTst2->fWindValue) {
764 goto skipAdvanceOtherCancel;
766 if (!oTst2->fWindValue) {
767 goto skipAdvanceOtherCancel;
769 if (endPt == other->fTs[oIdx2].fPt) {
774 SkASSERT(originalWindValue == oTest->fWindValue);
776 if (binary && !bigger) {
779 other->decrementSpan(oTest);
782 TrackOutsidePair(&oOutsidePts, *oTestPt, *testPt);
787 oTest = &other->fTs[--oIndex];
788 oFoundEnd |= endPt == oTest->fPt;
789 } while (!oFoundEnd || endPt == oTest->fPt);
791 skipAdvanceOtherCancel:
792 int outCount = outsidePts.count();
793 if (!done() && outCount) {
794 addCancelOutsides(outsidePts[0], outsidePts[1], other);
796 addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other);
799 if (!other->done() && oOutsidePts.count()) {
800 other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this);
802 setCoincidentRange(startPt, endPt, other);
803 other->setCoincidentRange(startPt, endPt, this);
806 int SkOpSegment::addSelfT(const SkPoint& pt, double newT) {
807 // if the tail nearly intersects itself but not quite, the caller records this separately
808 int result = addT(this, pt, newT);
809 SkOpSpan* span = &fTs[result];
810 fLoop = span->fLoop = true;
814 // find the starting or ending span with an existing loop of angles
815 // FIXME? replicate for all identical starting/ending spans?
816 // OPTIMIZE? remove the spans pointing to windValue==0 here or earlier?
817 // FIXME? assert that only one other span has a valid windValue or oppValue
818 void SkOpSegment::addSimpleAngle(int index) {
819 SkOpSpan* span = &fTs[index];
826 if (span->fToAngle) {
827 SkASSERT(span->fToAngle->loopCount() == 2);
828 SkASSERT(!span->fFromAngle);
829 span->fFromAngle = span->fToAngle->next();
833 } while (span->fT == 0);
834 SkASSERT(!fTs[0].fTiny && fTs[idx].fT > 0);
842 if (span->fFromAngle) {
843 SkASSERT(span->fFromAngle->loopCount() == 2);
844 SkASSERT(!span->fToAngle);
845 span->fToAngle = span->fFromAngle->next();
849 } while (span->fT == 1);
850 SkASSERT(!fTs[idx].fTiny && fTs[idx].fT < 1);
860 other = span->fOther;
861 int oFrom = span->fOtherIndex;
862 oSpan = &other->fTs[oFrom];
863 if (oSpan->fT < 1 && oSpan->fWindValue) {
866 if (oSpan->fT == 0) {
869 oFrom = other->nextExactSpan(oFrom, -1);
870 SkOpSpan* oFromSpan = &other->fTs[oFrom];
871 SkASSERT(oFromSpan->fT < 1);
872 if (oFromSpan->fWindValue) {
875 } while (++index < end);
876 SkOpAngle* angle, * oAngle;
878 SkASSERT(span->fOtherIndex - 1 >= 0);
879 SkASSERT(span->fOtherT == 1);
880 SkDEBUGCODE(int oPriorIndex = other->nextExactSpan(span->fOtherIndex, -1));
881 SkDEBUGCODE(const SkOpSpan& oPrior = other->span(oPriorIndex));
882 SkASSERT(!oPrior.fTiny && oPrior.fT < 1);
883 other->addEndSpan(span->fOtherIndex);
884 angle = span->fToAngle;
885 oAngle = oSpan->fFromAngle;
887 SkASSERT(span->fOtherIndex + 1 < other->count());
888 SkASSERT(span->fOtherT == 0);
889 SkASSERT(!oSpan->fTiny && (other->fTs[span->fOtherIndex + 1].fT > 0
890 || (other->fTs[span->fOtherIndex + 1].fFromAngle == NULL
891 && other->fTs[span->fOtherIndex + 1].fToAngle == NULL)));
894 const SkOpSpan& osSpan = other->span(oIndex);
895 if (osSpan.fFromAngle || osSpan.fT > 0) {
899 SkASSERT(oIndex < other->count());
901 other->addStartSpan(oIndex);
902 angle = span->fFromAngle;
903 oAngle = oSpan->fToAngle;
905 angle->insert(oAngle);
908 void SkOpSegment::alignMultiples(SkTDArray<AlignedSpan>* alignedArray) {
910 int count = this->count();
911 for (int index = 0; index < count; ++index) {
912 SkOpSpan& span = fTs[index];
913 if (!span.fMultiple) {
916 int end = nextExactSpan(index, 1);
917 SkASSERT(end > index + 1);
918 const SkPoint& thisPt = span.fPt;
919 while (index < end - 1) {
920 SkOpSegment* other1 = span.fOther;
921 int oCnt = other1->count();
922 for (int idx2 = index + 1; idx2 < end; ++idx2) {
923 SkOpSpan& span2 = fTs[idx2];
924 SkOpSegment* other2 = span2.fOther;
925 for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
926 SkOpSpan& oSpan = other1->fTs[oIdx];
927 if (oSpan.fOther != other2) {
930 if (oSpan.fPt == thisPt) {
931 goto skipExactMatches;
934 for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
935 SkOpSpan& oSpan = other1->fTs[oIdx];
936 if (oSpan.fOther != other2) {
939 if (SkDPoint::RoughlyEqual(oSpan.fPt, thisPt)) {
940 SkOpSpan& oSpan2 = other2->fTs[oSpan.fOtherIndex];
941 if (zero_or_one(span.fOtherT) || zero_or_one(oSpan.fT)
942 || zero_or_one(span2.fOtherT) || zero_or_one(oSpan2.fT)) {
945 if (!way_roughly_equal(span.fOtherT, oSpan.fT)
946 || !way_roughly_equal(span2.fOtherT, oSpan2.fT)
947 || !way_roughly_equal(span2.fOtherT, oSpan.fOtherT)
948 || !way_roughly_equal(span.fOtherT, oSpan2.fOtherT)) {
951 alignSpan(thisPt, span.fOtherT, other1, span2.fOtherT,
952 other2, &oSpan, alignedArray);
953 alignSpan(thisPt, span2.fOtherT, other2, span.fOtherT,
954 other1, &oSpan2, alignedArray);
967 void SkOpSegment::alignSpan(const SkPoint& newPt, double newT, const SkOpSegment* other,
968 double otherT, const SkOpSegment* other2, SkOpSpan* oSpan,
969 SkTDArray<AlignedSpan>* alignedArray) {
970 AlignedSpan* aligned = alignedArray->append();
971 aligned->fOldPt = oSpan->fPt;
972 aligned->fPt = newPt;
973 aligned->fOldT = oSpan->fT;
975 aligned->fSegment = this; // OPTIMIZE: may be unused, can remove
976 aligned->fOther1 = other;
977 aligned->fOther2 = other2;
978 SkASSERT(SkDPoint::RoughlyEqual(oSpan->fPt, newPt));
980 // SkASSERT(way_roughly_equal(oSpan->fT, newT));
982 // SkASSERT(way_roughly_equal(oSpan->fOtherT, otherT));
983 oSpan->fOtherT = otherT;
986 bool SkOpSegment::alignSpan(int index, double thisT, const SkPoint& thisPt) {
987 bool aligned = false;
988 SkOpSpan* span = &fTs[index];
989 SkOpSegment* other = span->fOther;
990 int oIndex = span->fOtherIndex;
991 SkOpSpan* oSpan = &other->fTs[oIndex];
992 if (span->fT != thisT) {
994 oSpan->fOtherT = thisT;
997 if (span->fPt != thisPt) {
1002 double oT = oSpan->fT;
1006 int oStart = other->nextSpan(oIndex, -1) + 1;
1007 oSpan = &other->fTs[oStart];
1008 int otherIndex = oStart;
1011 while (oSpan->fPt == thisPt && oSpan->fT != 1) {
1012 oSpan->fTiny = true;
1019 int oEnd = other->nextSpan(oIndex, 1);
1020 bool oAligned = false;
1021 if (oSpan->fPt != thisPt) {
1022 oAligned |= other->alignSpan(oStart, oT, thisPt);
1024 while (++otherIndex < oEnd) {
1025 SkOpSpan* oNextSpan = &other->fTs[otherIndex];
1026 if (oNextSpan->fT != oT || oNextSpan->fPt != thisPt) {
1027 oAligned |= other->alignSpan(otherIndex, oT, thisPt);
1031 other->alignSpanState(oStart, oEnd);
1036 void SkOpSegment::alignSpanState(int start, int end) {
1037 SkOpSpan* lastSpan = &fTs[--end];
1038 bool allSmall = lastSpan->fSmall;
1039 bool allTiny = lastSpan->fTiny;
1040 bool allDone = lastSpan->fDone;
1041 SkDEBUGCODE(int winding = lastSpan->fWindValue);
1042 SkDEBUGCODE(int oppWinding = lastSpan->fOppValue);
1044 while (index < end) {
1045 SkOpSpan* span = &fTs[index];
1046 span->fSmall = allSmall;
1047 span->fTiny = allTiny;
1048 if (span->fDone != allDone) {
1049 span->fDone = allDone;
1050 fDoneSpans += allDone ? 1 : -1;
1052 SkASSERT(span->fWindValue == winding);
1053 SkASSERT(span->fOppValue == oppWinding);
1058 void SkOpSegment::blindCancel(const SkCoincidence& coincidence, SkOpSegment* other) {
1059 bool binary = fOperand != other->fOperand;
1061 int last = this->count();
1063 SkOpSpan& span = this->fTs[--last];
1064 if (span.fT != 1 && !span.fSmall) {
1067 span.fCoincident = true;
1069 int oIndex = other->count();
1071 SkOpSpan& oSpan = other->fTs[--oIndex];
1072 if (oSpan.fT != 1 && !oSpan.fSmall) {
1075 oSpan.fCoincident = true;
1078 SkOpSpan* test = &this->fTs[index];
1079 int baseWind = test->fWindValue;
1080 int baseOpp = test->fOppValue;
1081 int endIndex = index;
1082 while (++endIndex <= last) {
1083 SkOpSpan* endSpan = &this->fTs[endIndex];
1084 SkASSERT(endSpan->fT < 1);
1085 if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) {
1088 endSpan->fCoincident = true;
1090 SkOpSpan* oTest = &other->fTs[oIndex];
1091 int oBaseWind = oTest->fWindValue;
1092 int oBaseOpp = oTest->fOppValue;
1093 int oStartIndex = oIndex;
1094 while (--oStartIndex >= 0) {
1095 SkOpSpan* oStartSpan = &other->fTs[oStartIndex];
1096 if (oStartSpan->fWindValue != oBaseWind || oStartSpan->fOppValue != oBaseOpp) {
1099 oStartSpan->fCoincident = true;
1101 bool decrement = baseWind && oBaseWind;
1102 bool bigger = baseWind >= oBaseWind;
1104 SkASSERT(test->fT < 1);
1106 if (binary && bigger) {
1109 decrementSpan(test);
1112 test->fCoincident = true;
1113 test = &fTs[++index];
1114 } while (index < endIndex);
1116 SkASSERT(oTest->fT < 1);
1118 if (binary && !bigger) {
1121 other->decrementSpan(oTest);
1124 oTest->fCoincident = true;
1125 oTest = &other->fTs[--oIndex];
1126 } while (oIndex > oStartIndex);
1127 } while (index <= last && oIndex >= 0);
1128 SkASSERT(index > last);
1129 SkASSERT(oIndex < 0);
1132 void SkOpSegment::blindCoincident(const SkCoincidence& coincidence, SkOpSegment* other) {
1133 bool binary = fOperand != other->fOperand;
1135 int last = this->count();
1137 SkOpSpan& span = this->fTs[--last];
1138 if (span.fT != 1 && !span.fSmall) {
1141 span.fCoincident = true;
1144 int oLast = other->count();
1146 SkOpSpan& oSpan = other->fTs[--oLast];
1147 if (oSpan.fT != 1 && !oSpan.fSmall) {
1150 oSpan.fCoincident = true;
1153 SkOpSpan* test = &this->fTs[index];
1154 int baseWind = test->fWindValue;
1155 int baseOpp = test->fOppValue;
1156 int endIndex = index;
1158 while (++endIndex <= last) {
1159 endSpan = &this->fTs[endIndex];
1160 SkASSERT(endSpan->fT < 1);
1161 if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) {
1164 endSpan->fCoincident = true;
1166 SkOpSpan* oTest = &other->fTs[oIndex];
1167 int oBaseWind = oTest->fWindValue;
1168 int oBaseOpp = oTest->fOppValue;
1169 int oEndIndex = oIndex;
1171 while (++oEndIndex <= oLast) {
1172 oEndSpan = &this->fTs[oEndIndex];
1173 SkASSERT(oEndSpan->fT < 1);
1174 if (oEndSpan->fWindValue != oBaseWind || oEndSpan->fOppValue != oBaseOpp) {
1177 oEndSpan->fCoincident = true;
1179 // consolidate the winding count even if done
1180 if ((test->fWindValue || test->fOppValue) && (oTest->fWindValue || oTest->fOppValue)) {
1181 if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1182 bumpCoincidentBlind(binary, index, endIndex);
1183 other->bumpCoincidentOBlind(oIndex, oEndIndex);
1185 other->bumpCoincidentBlind(binary, oIndex, oEndIndex);
1186 bumpCoincidentOBlind(index, endIndex);
1191 } while (index <= last && oIndex <= oLast);
1192 SkASSERT(index > last);
1193 SkASSERT(oIndex > oLast);
1196 void SkOpSegment::bumpCoincidentBlind(bool binary, int index, int endIndex) {
1197 const SkOpSpan& oTest = fTs[index];
1198 int oWindValue = oTest.fWindValue;
1199 int oOppValue = oTest.fOppValue;
1201 SkTSwap<int>(oWindValue, oOppValue);
1204 (void) bumpSpan(&fTs[index], oWindValue, oOppValue);
1205 } while (++index < endIndex);
1208 void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr,
1209 SkTArray<SkPoint, true>* outsideTs) {
1210 int index = *indexPtr;
1211 int oWindValue = oTest.fWindValue;
1212 int oOppValue = oTest.fOppValue;
1214 SkTSwap<int>(oWindValue, oOppValue);
1216 SkOpSpan* const test = &fTs[index];
1217 SkOpSpan* end = test;
1218 const SkPoint& oStartPt = oTest.fPt;
1220 if (bumpSpan(end, oWindValue, oOppValue)) {
1221 TrackOutside(outsideTs, oStartPt);
1223 end = &fTs[++index];
1224 } while ((end->fPt == test->fPt || precisely_equal(end->fT, test->fT)) && end->fT < 1);
1228 void SkOpSegment::bumpCoincidentOBlind(int index, int endIndex) {
1230 zeroSpan(&fTs[index]);
1231 } while (++index < endIndex);
1234 // because of the order in which coincidences are resolved, this and other
1235 // may not have the same intermediate points. Compute the corresponding
1236 // intermediate T values (using this as the master, other as the follower)
1237 // and walk other conditionally -- hoping that it catches up in the end
1238 void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
1239 SkTArray<SkPoint, true>* oOutsidePts) {
1240 int oIndex = *oIndexPtr;
1241 SkOpSpan* const oTest = &fTs[oIndex];
1242 SkOpSpan* oEnd = oTest;
1243 const SkPoint& oStartPt = oTest->fPt;
1244 double oStartT = oTest->fT;
1245 #if 0 // FIXME : figure out what disabling this breaks
1246 const SkPoint& startPt = test.fPt;
1247 // this is always true since oEnd == oTest && oStartPt == oTest->fPt -- find proper condition
1248 if (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
1249 TrackOutside(oOutsidePts, startPt);
1252 while (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
1254 oEnd = &fTs[++oIndex];
1256 *oIndexPtr = oIndex;
1259 // FIXME: need to test this case:
1260 // contourA has two segments that are coincident
1261 // contourB has two segments that are coincident in the same place
1262 // each ends up with +2/0 pairs for winding count
1263 // since logic below doesn't transfer count (only increments/decrements) can this be
1264 // resolved to +4/0 ?
1266 // set spans from start to end to increment the greater by one and decrement
1268 bool SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
1269 SkOpSegment* other) {
1270 bool binary = fOperand != other->fOperand;
1272 while (startPt != fTs[index].fPt) {
1273 SkASSERT(index < fTs.count());
1276 double startT = fTs[index].fT;
1277 while (index > 0 && precisely_equal(fTs[index - 1].fT, startT)) {
1281 while (startPt != other->fTs[oIndex].fPt) {
1282 SkASSERT(oIndex < other->fTs.count());
1285 double oStartT = other->fTs[oIndex].fT;
1286 while (oIndex > 0 && precisely_equal(other->fTs[oIndex - 1].fT, oStartT)) {
1289 SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
1290 SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
1291 SkOpSpan* test = &fTs[index];
1292 const SkPoint* testPt = &test->fPt;
1293 double testT = test->fT;
1294 SkOpSpan* oTest = &other->fTs[oIndex];
1295 const SkPoint* oTestPt = &oTest->fPt;
1296 // paths with extreme data will fail this test and eject out of pathops altogether later on
1297 // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1299 SkASSERT(test->fT < 1);
1300 if (oTest->fT == 1) {
1301 // paths with extreme data may be so mismatched that we fail here
1305 // consolidate the winding count even if done
1306 if ((test->fWindValue == 0 && test->fOppValue == 0)
1307 || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
1308 SkDEBUGCODE(int firstWind = test->fWindValue);
1309 SkDEBUGCODE(int firstOpp = test->fOppValue);
1311 SkASSERT(firstWind == fTs[index].fWindValue);
1312 SkASSERT(firstOpp == fTs[index].fOppValue);
1314 SkASSERT(index < fTs.count());
1315 } while (*testPt == fTs[index].fPt);
1316 SkDEBUGCODE(firstWind = oTest->fWindValue);
1317 SkDEBUGCODE(firstOpp = oTest->fOppValue);
1319 SkASSERT(firstWind == other->fTs[oIndex].fWindValue);
1320 SkASSERT(firstOpp == other->fTs[oIndex].fOppValue);
1322 SkASSERT(oIndex < other->fTs.count());
1323 } while (*oTestPt == other->fTs[oIndex].fPt);
1325 if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1326 bumpCoincidentThis(*oTest, binary, &index, &outsidePts);
1327 other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
1329 other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
1330 bumpCoincidentOther(*oTest, &index, &outsidePts);
1334 testPt = &test->fPt;
1336 oTest = &other->fTs[oIndex];
1337 oTestPt = &oTest->fPt;
1338 if (endPt == *testPt || precisely_equal(endT, testT)) {
1341 // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1342 } while (endPt != *oTestPt);
1343 // in rare cases, one may have ended before the other
1344 if (endPt != *testPt && !precisely_equal(endT, testT)) {
1345 int lastWind = test[-1].fWindValue;
1346 int lastOpp = test[-1].fOppValue;
1347 bool zero = lastWind == 0 && lastOpp == 0;
1349 if (test->fWindValue || test->fOppValue) {
1350 test->fWindValue = lastWind;
1351 test->fOppValue = lastOpp;
1357 test = &fTs[++index];
1358 testPt = &test->fPt;
1359 } while (endPt != *testPt);
1361 if (endPt != *oTestPt) {
1362 // look ahead to see if zeroing more spans will allows us to catch up
1363 int oPeekIndex = oIndex;
1364 bool success = true;
1366 int oCount = other->count();
1368 oPeek = &other->fTs[oPeekIndex];
1369 if (++oPeekIndex == oCount) {
1373 } while (endPt != oPeek->fPt);
1375 // make sure the matching point completes the coincidence span
1378 if (oPeek->fOther == this) {
1382 if (++oPeekIndex == oCount) {
1385 oPeek = &other->fTs[oPeekIndex];
1386 } while (endPt == oPeek->fPt);
1390 if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1391 other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
1393 other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
1395 oTest = &other->fTs[oIndex];
1396 oTestPt = &oTest->fPt;
1397 } while (endPt != *oTestPt);
1400 int outCount = outsidePts.count();
1401 if (!done() && outCount) {
1402 addCoinOutsides(outsidePts[0], endPt, other);
1404 if (!other->done() && oOutsidePts.count()) {
1405 other->addCoinOutsides(oOutsidePts[0], endPt, this);
1407 setCoincidentRange(startPt, endPt, other);
1408 other->setCoincidentRange(startPt, endPt, this);
1412 // FIXME: this doesn't prevent the same span from being added twice
1413 // fix in caller, SkASSERT here?
1414 const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
1415 const SkPoint& pt, const SkPoint& pt2) {
1416 int tCount = fTs.count();
1417 for (int tIndex = 0; tIndex < tCount; ++tIndex) {
1418 const SkOpSpan& span = fTs[tIndex];
1419 if (!approximately_negative(span.fT - t)) {
1422 if (approximately_negative(span.fT - t) && span.fOther == other
1423 && approximately_equal(span.fOtherT, otherT)) {
1424 #if DEBUG_ADD_T_PAIR
1425 SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
1426 __FUNCTION__, fID, t, other->fID, otherT);
1431 #if DEBUG_ADD_T_PAIR
1432 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
1433 __FUNCTION__, fID, t, other->fID, otherT);
1435 int insertedAt = addT(other, pt, t);
1436 int otherInsertedAt = other->addT(this, pt2, otherT);
1437 addOtherT(insertedAt, otherT, otherInsertedAt);
1438 other->addOtherT(otherInsertedAt, t, insertedAt);
1439 matchWindingValue(insertedAt, t, borrowWind);
1440 other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
1441 SkOpSpan& span = this->fTs[insertedAt];
1444 SkOpSpan& oSpan = other->fTs[otherInsertedAt];
1450 const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
1451 const SkPoint& pt) {
1452 return addTPair(t, other, otherT, borrowWind, pt, pt);
1455 bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
1456 const SkPoint midPt = ptAtT(midT);
1457 SkPathOpsBounds bounds;
1458 bounds.set(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
1460 return bounds.almostContains(midPt);
1463 bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const {
1464 if (lesser > greater) {
1465 SkTSwap<int>(lesser, greater);
1467 return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
1470 // in extreme cases (like the buffer overflow test) return false to abort
1471 // for now, if one t value represents two different points, then the values are too extreme
1472 // to generate meaningful results
1473 bool SkOpSegment::calcAngles() {
1474 int spanCount = fTs.count();
1475 if (spanCount <= 2) {
1476 return spanCount == 2;
1479 const SkOpSpan* firstSpan = &fTs[index];
1480 int activePrior = checkSetAngle(0);
1481 const SkOpSpan* span = &fTs[0];
1482 if (firstSpan->fT == 0 || span->fTiny || span->fOtherT != 1 || span->fOther->multipleEnds()) {
1483 index = findStartSpan(0); // curve start intersects
1484 if (fTs[index].fT == 0) {
1487 SkASSERT(index > 0);
1488 if (activePrior >= 0) {
1489 addStartSpan(index);
1493 int endIndex = spanCount - 1;
1494 span = &fTs[endIndex - 1];
1495 if ((addEnd = span->fT == 1 || span->fTiny)) { // if curve end intersects
1496 endIndex = findEndSpan(endIndex);
1497 SkASSERT(endIndex > 0);
1499 addEnd = fTs[endIndex].fOtherT != 0 || fTs[endIndex].fOther->multipleStarts();
1501 SkASSERT(endIndex >= index);
1503 while (index < endIndex) {
1504 const SkOpSpan& fromSpan = fTs[index]; // for each intermediate intersection
1505 const SkOpSpan* lastSpan;
1510 span = &fTs[++index];
1511 SkASSERT(index < spanCount);
1512 if (!precisely_negative(span->fT - lastSpan->fT) && !lastSpan->fTiny) {
1515 if (!SkDPoint::ApproximatelyEqual(lastSpan->fPt, span->fPt)) {
1519 SkOpAngle* angle = NULL;
1520 SkOpAngle* priorAngle;
1521 if (activePrior >= 0) {
1522 int pActive = firstActive(prior);
1523 SkASSERT(pActive < start);
1524 priorAngle = &fAngles.push_back();
1525 priorAngle->set(this, start, pActive);
1527 int active = checkSetAngle(start);
1529 SkASSERT(active < index);
1530 angle = &fAngles.push_back();
1531 angle->set(this, active, index);
1534 debugCheckPointsEqualish(start, index);
1538 const SkOpSpan* startSpan = &fTs[start - 1];
1539 if (!startSpan->fSmall || isCanceled(start - 1) || startSpan->fFromAngle
1540 || startSpan->fToAngle) {
1544 } while (start > 0);
1546 if (activePrior >= 0) {
1547 SkASSERT(fTs[start].fFromAngle == NULL);
1548 fTs[start].fFromAngle = priorAngle;
1551 SkASSERT(fTs[start].fToAngle == NULL);
1552 fTs[start].fToAngle = angle;
1554 } while (++start < index);
1555 activePrior = active;
1557 if (addEnd && activePrior >= 0) {
1558 addEndSpan(endIndex);
1563 int SkOpSegment::checkSetAngle(int tIndex) const {
1564 const SkOpSpan* span = &fTs[tIndex];
1565 while (span->fTiny /* || span->fSmall */) {
1566 span = &fTs[++tIndex];
1568 return isCanceled(tIndex) ? -1 : tIndex;
1571 // at this point, the span is already ordered, or unorderable
1572 int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType) {
1573 SkASSERT(includeType != SkOpAngle::kUnaryXor);
1574 SkOpAngle* firstAngle = spanToAngle(endIndex, startIndex);
1575 if (NULL == firstAngle) {
1578 // if all angles have a computed winding,
1579 // or if no adjacent angles are orderable,
1580 // or if adjacent orderable angles have no computed winding,
1581 // there's nothing to do
1582 // if two orderable angles are adjacent, and both are next to orderable angles,
1583 // and one has winding computed, transfer to the other
1584 SkOpAngle* baseAngle = NULL;
1585 bool tryReverse = false;
1586 // look for counterclockwise transfers
1587 SkOpAngle* angle = firstAngle->previous();
1588 SkOpAngle* next = angle->next();
1591 SkOpAngle* prior = angle;
1593 next = angle->next();
1594 SkASSERT(prior->next() == angle);
1595 SkASSERT(angle->next() == next);
1596 if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
1600 int testWinding = angle->segment()->windSum(angle);
1601 if (SK_MinS32 != testWinding) {
1607 ComputeOneSum(baseAngle, angle, includeType);
1608 baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
1610 } while (next != firstAngle);
1611 if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(firstAngle)) {
1612 firstAngle = baseAngle;
1617 SkOpAngle* prior = firstAngle;
1620 prior = angle->previous();
1621 SkASSERT(prior->next() == angle);
1622 next = angle->next();
1623 if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
1627 int testWinding = angle->segment()->windSum(angle);
1628 if (SK_MinS32 != testWinding) {
1633 ComputeOneSumReverse(baseAngle, angle, includeType);
1634 baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
1636 } while (prior != firstAngle);
1638 int minIndex = SkMin32(startIndex, endIndex);
1639 return windSum(minIndex);
1642 void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1643 SkOpAngle::IncludeType includeType) {
1644 const SkOpSegment* baseSegment = baseAngle->segment();
1645 int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
1647 bool binary = includeType >= SkOpAngle::kBinarySingle;
1649 sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
1650 if (baseSegment->operand()) {
1651 SkTSwap<int>(sumMiWinding, sumSuWinding);
1654 SkOpSegment* nextSegment = nextAngle->segment();
1655 int maxWinding, sumWinding;
1658 int oppMaxWinding, oppSumWinding;
1659 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1660 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1661 last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1664 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
1665 &maxWinding, &sumWinding);
1666 last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1668 nextAngle->setLastMarked(last);
1671 void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
1672 SkOpAngle::IncludeType includeType) {
1673 const SkOpSegment* baseSegment = baseAngle->segment();
1674 int sumMiWinding = baseSegment->updateWinding(baseAngle);
1676 bool binary = includeType >= SkOpAngle::kBinarySingle;
1678 sumSuWinding = baseSegment->updateOppWinding(baseAngle);
1679 if (baseSegment->operand()) {
1680 SkTSwap<int>(sumMiWinding, sumSuWinding);
1683 SkOpSegment* nextSegment = nextAngle->segment();
1684 int maxWinding, sumWinding;
1687 int oppMaxWinding, oppSumWinding;
1688 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1689 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
1690 last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
1693 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
1694 &maxWinding, &sumWinding);
1695 last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
1697 nextAngle->setLastMarked(last);
1700 bool SkOpSegment::containsPt(const SkPoint& pt, int index, int endIndex) const {
1701 int step = index < endIndex ? 1 : -1;
1703 const SkOpSpan& span = this->span(index);
1704 if (span.fPt == pt) {
1705 const SkOpSpan& endSpan = this->span(endIndex);
1706 return span.fT == endSpan.fT && pt != endSpan.fPt;
1709 } while (index != endIndex);
1713 bool SkOpSegment::containsT(double t, const SkOpSegment* other, double otherT) const {
1714 int count = this->count();
1715 for (int index = 0; index < count; ++index) {
1716 const SkOpSpan& span = fTs[index];
1721 if (other != span.fOther) {
1724 if (other->fVerb != SkPath::kCubic_Verb) {
1727 if (!other->fLoop) {
1730 double otherMidT = (otherT + span.fOtherT) / 2;
1731 SkPoint otherPt = other->ptAtT(otherMidT);
1732 return SkDPoint::ApproximatelyEqual(span.fPt, otherPt);
1738 int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
1739 bool* hitSomething, double mid, bool opp, bool current) const {
1740 SkScalar bottom = fBounds.fBottom;
1741 int bestTIndex = -1;
1742 if (bottom <= *bestY) {
1745 SkScalar top = fBounds.fTop;
1746 if (top >= basePt.fY) {
1749 if (fBounds.fLeft > basePt.fX) {
1752 if (fBounds.fRight < basePt.fX) {
1755 if (fBounds.fLeft == fBounds.fRight) {
1756 // if vertical, and directly above test point, wait for another one
1757 return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
1759 // intersect ray starting at basePt with edge
1760 SkIntersections intersections;
1761 // OPTIMIZE: use specialty function that intersects ray with curve,
1762 // returning t values only for curve (we don't care about t on ray)
1763 intersections.allowNear(false);
1764 int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
1765 (fPts, top, bottom, basePt.fX, false);
1766 if (pts == 0 || (current && pts == 1)) {
1772 double closest = fabs(intersections[0][0] - mid);
1773 for (int idx = 1; idx < pts; ++idx) {
1774 double test = fabs(intersections[0][idx] - mid);
1775 if (closest > test) {
1780 intersections.quickRemoveOne(closestIdx, --pts);
1783 for (int index = 0; index < pts; ++index) {
1784 double foundT = intersections[0][index];
1785 if (approximately_less_than_zero(foundT)
1786 || approximately_greater_than_one(foundT)) {
1789 SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fY;
1790 if (approximately_negative(testY - *bestY)
1791 || approximately_negative(basePt.fY - testY)) {
1794 if (pts > 1 && fVerb == SkPath::kLine_Verb) {
1795 return SK_MinS32; // if the intersection is edge on, wait for another one
1797 if (fVerb > SkPath::kLine_Verb) {
1798 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fX;
1799 if (approximately_zero(dx)) {
1800 return SK_MinS32; // hit vertical, wait for another one
1809 SkASSERT(bestT >= 0);
1810 SkASSERT(bestT <= 1);
1815 end = nextSpan(start, 1);
1816 } while (fTs[end].fT < bestT);
1817 // FIXME: see next candidate for a better pattern to find the next start/end pair
1818 while (start + 1 < end && fTs[start].fDone) {
1821 if (!isCanceled(start)) {
1824 *hitSomething = true;
1829 bool SkOpSegment::decrementSpan(SkOpSpan* span) {
1830 SkASSERT(span->fWindValue > 0);
1831 if (--(span->fWindValue) == 0) {
1832 if (!span->fOppValue && !span->fDone) {
1841 bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
1842 SkASSERT(!span->fDone || span->fTiny || span->fSmall);
1843 span->fWindValue += windDelta;
1844 SkASSERT(span->fWindValue >= 0);
1845 span->fOppValue += oppDelta;
1846 SkASSERT(span->fOppValue >= 0);
1848 span->fWindValue &= 1;
1851 span->fOppValue &= 1;
1853 if (!span->fWindValue && !span->fOppValue) {
1861 const SkOpSpan& SkOpSegment::firstSpan(const SkOpSpan& thisSpan) const {
1862 const SkOpSpan* firstSpan = &thisSpan; // rewind to the start
1863 const SkOpSpan* beginSpan = fTs.begin();
1864 const SkPoint& testPt = thisSpan.fPt;
1865 while (firstSpan > beginSpan && firstSpan[-1].fPt == testPt) {
1871 const SkOpSpan& SkOpSegment::lastSpan(const SkOpSpan& thisSpan) const {
1872 const SkOpSpan* endSpan = fTs.end() - 1; // last can't be small
1873 const SkOpSpan* lastSpan = &thisSpan; // find the end
1874 const SkPoint& testPt = thisSpan.fPt;
1875 while (lastSpan < endSpan && lastSpan[1].fPt == testPt) {
1881 // with a loop, the comparison is move involved
1882 // scan backwards and forwards to count all matching points
1883 // (verify that there are twp scans marked as loops)
1884 // compare that against 2 matching scans for loop plus other results
1885 bool SkOpSegment::calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts) {
1886 const SkOpSpan& firstSpan = this->firstSpan(thisSpan); // rewind to the start
1887 const SkOpSpan& lastSpan = this->lastSpan(thisSpan); // find the end
1888 double firstLoopT = -1, lastLoopT = -1;
1889 const SkOpSpan* testSpan = &firstSpan - 1;
1890 while (++testSpan <= &lastSpan) {
1891 if (testSpan->fLoop) {
1892 firstLoopT = testSpan->fT;
1896 testSpan = &lastSpan + 1;
1897 while (--testSpan >= &firstSpan) {
1898 if (testSpan->fLoop) {
1899 lastLoopT = testSpan->fT;
1903 SkASSERT((firstLoopT == -1) == (lastLoopT == -1));
1904 if (firstLoopT == -1) {
1907 SkASSERT(firstLoopT < lastLoopT);
1908 testSpan = &firstSpan - 1;
1909 smallCounts[0] = smallCounts[1] = 0;
1910 while (++testSpan <= &lastSpan) {
1911 SkASSERT(approximately_equal(testSpan->fT, firstLoopT) +
1912 approximately_equal(testSpan->fT, lastLoopT) == 1);
1913 smallCounts[approximately_equal(testSpan->fT, lastLoopT)]++;
1918 double SkOpSegment::calcMissingTEnd(const SkOpSegment* ref, double loEnd, double min, double max,
1919 double hiEnd, const SkOpSegment* other, int thisStart) {
1923 int end = findOtherT(hiEnd, ref);
1927 double tHi = span(end).fT;
1929 if (thisStart >= 0) {
1930 tLo = span(thisStart).fT;
1933 int start1 = findOtherT(loEnd, ref);
1934 SkASSERT(start1 >= 0);
1935 tLo = span(start1).fT;
1938 double missingT = (max - refLo) / (hiEnd - refLo);
1939 missingT = tLo + missingT * (tHi - tLo);
1943 double SkOpSegment::calcMissingTStart(const SkOpSegment* ref, double loEnd, double min, double max,
1944 double hiEnd, const SkOpSegment* other, int thisEnd) {
1948 int start = findOtherT(loEnd, ref);
1952 double tLo = span(start).fT;
1955 tHi = span(thisEnd).fT;
1958 int end1 = findOtherT(hiEnd, ref);
1962 tHi = span(end1).fT;
1965 double missingT = (min - loEnd) / (refHi - loEnd);
1966 missingT = tLo + missingT * (tHi - tLo);
1970 // see if spans with two or more intersections have the same number on the other end
1971 void SkOpSegment::checkDuplicates() {
1973 SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
1979 endIndex = nextExactSpan(index, 1);
1980 if ((endFound = endIndex < 0)) {
1983 int dupCount = endIndex - index;
1988 const SkOpSpan* thisSpan = &fTs[index];
1989 if (thisSpan->fNear) {
1992 SkOpSegment* other = thisSpan->fOther;
1993 int oIndex = thisSpan->fOtherIndex;
1994 int oStart = other->nextExactSpan(oIndex, -1) + 1;
1995 int oEnd = other->nextExactSpan(oIndex, 1);
1997 oEnd = other->count();
1999 int oCount = oEnd - oStart;
2000 // force the other to match its t and this pt if not on an end point
2001 if (oCount != dupCount) {
2002 MissingSpan& missing = missingSpans.push_back();
2003 missing.fOther = NULL;
2004 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2005 missing.fPt = thisSpan->fPt;
2006 const SkOpSpan& oSpan = other->span(oIndex);
2007 if (oCount > dupCount) {
2008 missing.fSegment = this;
2009 missing.fT = thisSpan->fT;
2010 other->checkLinks(&oSpan, &missingSpans);
2012 missing.fSegment = other;
2013 missing.fT = oSpan.fT;
2014 checkLinks(thisSpan, &missingSpans);
2016 if (!missingSpans.back().fOther) {
2017 missingSpans.pop_back();
2020 } while (++index < endIndex);
2021 } while (!endFound);
2022 int missingCount = missingSpans.count();
2023 if (missingCount == 0) {
2026 SkSTArray<kMissingSpanCount, MissingSpan, true> missingCoincidence;
2027 for (index = 0; index < missingCount; ++index) {
2028 MissingSpan& missing = missingSpans[index];
2029 SkOpSegment* missingOther = missing.fOther;
2030 if (missing.fSegment == missing.fOther) {
2033 #if 0 // FIXME: this eliminates spurious data from skpwww_argus_presse_fr_41 but breaks
2034 // skpwww_fashionscandal_com_94 -- calcAngles complains, but I don't understand why
2035 if (missing.fSegment->containsT(missing.fT, missing.fOther, missing.fOtherT)) {
2036 #if DEBUG_DUPLICATES
2037 SkDebugf("skip 1 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fSegment->fID,
2038 missing.fT, missing.fOther->fID, missing.fOtherT);
2042 if (missing.fOther->containsT(missing.fOtherT, missing.fSegment, missing.fT)) {
2043 #if DEBUG_DUPLICATES
2044 SkDebugf("skip 2 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fOther->fID,
2045 missing.fOtherT, missing.fSegment->fID, missing.fT);
2050 // skip if adding would insert point into an existing coincindent span
2051 if (missing.fSegment->inCoincidentSpan(missing.fT, missingOther)
2052 && missingOther->inCoincidentSpan(missing.fOtherT, this)) {
2055 // skip if the created coincident spans are small
2056 if (missing.fSegment->coincidentSmall(missing.fPt, missing.fT, missingOther)
2057 && missingOther->coincidentSmall(missing.fPt, missing.fOtherT, missing.fSegment)) {
2060 const SkOpSpan* added = missing.fSegment->addTPair(missing.fT, missingOther,
2061 missing.fOtherT, false, missing.fPt);
2062 if (added && added->fSmall) {
2063 missing.fSegment->checkSmallCoincidence(*added, &missingCoincidence);
2066 for (index = 0; index < missingCount; ++index) {
2067 MissingSpan& missing = missingSpans[index];
2068 missing.fSegment->fixOtherTIndex();
2069 missing.fOther->fixOtherTIndex();
2071 for (index = 0; index < missingCoincidence.count(); ++index) {
2072 MissingSpan& missing = missingCoincidence[index];
2073 missing.fSegment->fixOtherTIndex();
2078 // look to see if the curve end intersects an intermediary that intersects the other
2079 void SkOpSegment::checkEnds() {
2081 SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2082 int count = fTs.count();
2083 for (int index = 0; index < count; ++index) {
2084 const SkOpSpan& span = fTs[index];
2085 double otherT = span.fOtherT;
2086 if (otherT != 0 && otherT != 1) { // only check ends
2089 const SkOpSegment* other = span.fOther;
2090 // peek start/last describe the range of spans that match the other t of this span
2091 int peekStart = span.fOtherIndex;
2092 while (--peekStart >= 0 && other->fTs[peekStart].fT == otherT)
2094 int otherCount = other->fTs.count();
2095 int peekLast = span.fOtherIndex;
2096 while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT)
2098 if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do
2101 // t start/last describe the range of spans that match the t of this span
2103 double tBottom = -1;
2106 bool lastSmall = false;
2108 for (int inner = 0; inner < count; ++inner) {
2109 double innerT = fTs[inner].fT;
2110 if (innerT <= t && innerT > tBottom) {
2111 if (innerT < t || !lastSmall) {
2116 if (innerT > afterT) {
2117 if (t == afterT && lastSmall) {
2124 lastSmall = innerT <= t ? fTs[inner].fSmall : false;
2126 for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
2127 if (peekIndex == span.fOtherIndex) { // skip the other span pointed to by this span
2130 const SkOpSpan& peekSpan = other->fTs[peekIndex];
2131 SkOpSegment* match = peekSpan.fOther;
2132 if (match->done()) {
2133 continue; // if the edge has already been eaten (likely coincidence), ignore it
2135 const double matchT = peekSpan.fOtherT;
2136 // see if any of the spans match the other spans
2137 for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) {
2138 const SkOpSpan& tSpan = fTs[tIndex];
2139 if (tSpan.fOther == match) {
2140 if (tSpan.fOtherT == matchT) {
2143 double midT = (tSpan.fOtherT + matchT) / 2;
2144 if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
2149 if (missingSpans.count() > 0) {
2150 const MissingSpan& lastMissing = missingSpans.back();
2151 if (lastMissing.fT == t
2152 && lastMissing.fOther == match
2153 && lastMissing.fOtherT == matchT) {
2154 SkASSERT(lastMissing.fPt == peekSpan.fPt);
2158 #if DEBUG_CHECK_ENDS
2159 SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n",
2160 __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY);
2162 // this segment is missing a entry that the other contains
2163 // remember so we can add the missing one and recompute the indices
2165 MissingSpan& missing = missingSpans.push_back();
2166 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2168 missing.fOther = match;
2169 missing.fOtherT = matchT;
2170 missing.fPt = peekSpan.fPt;
2177 if (missingSpans.count() == 0) {
2182 int missingCount = missingSpans.count();
2183 for (int index = 0; index < missingCount; ++index) {
2184 MissingSpan& missing = missingSpans[index];
2185 if (this != missing.fOther) {
2186 addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
2190 // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
2192 for (int index = 0; index < missingCount; ++index) {
2193 missingSpans[index].fOther->fixOtherTIndex();
2198 void SkOpSegment::checkLinks(const SkOpSpan* base,
2199 SkTArray<MissingSpan, true>* missingSpans) const {
2200 const SkOpSpan* first = fTs.begin();
2201 const SkOpSpan* last = fTs.end() - 1;
2202 SkASSERT(base >= first && last >= base);
2203 const SkOpSegment* other = base->fOther;
2204 const SkOpSpan* oFirst = other->fTs.begin();
2205 const SkOpSpan* oLast = other->fTs.end() - 1;
2206 const SkOpSpan* oSpan = &other->fTs[base->fOtherIndex];
2207 const SkOpSpan* test = base;
2208 const SkOpSpan* missing = NULL;
2209 while (test > first && (--test)->fPt == base->fPt) {
2210 CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
2213 while (test < last && (++test)->fPt == base->fPt) {
2214 CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
2218 // see if spans with two or more intersections all agree on common t and point values
2219 void SkOpSegment::checkMultiples() {
2223 while (fTs[++end].fT == 0)
2225 while (fTs[end].fT < 1) {
2226 int start = index = end;
2227 end = nextExactSpan(index, 1);
2229 return; // buffer overflow example triggers this
2231 if (index + 1 == end) {
2234 // force the duplicates to agree on t and pt if not on the end
2235 SkOpSpan& span = fTs[index];
2236 double thisT = span.fT;
2237 const SkPoint& thisPt = span.fPt;
2238 span.fMultiple = true;
2239 bool aligned = false;
2240 while (++index < end) {
2241 aligned |= alignSpan(index, thisT, thisPt);
2244 alignSpanState(start, end);
2251 void SkOpSegment::CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan,
2252 const SkOpSpan* oFirst, const SkOpSpan* oLast, const SkOpSpan** missingPtr,
2253 SkTArray<MissingSpan, true>* missingSpans) {
2254 SkASSERT(oSpan->fPt == test->fPt);
2255 const SkOpSpan* oTest = oSpan;
2256 while (oTest > oFirst && (--oTest)->fPt == test->fPt) {
2257 if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) {
2262 while (oTest < oLast && (++oTest)->fPt == test->fPt) {
2263 if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) {
2268 missingSpans->push_back();
2270 MissingSpan& lastMissing = missingSpans->back();
2272 lastMissing = missingSpans->end()[-2];
2275 lastMissing.fOther = test->fOther;
2276 lastMissing.fOtherT = test->fOtherT;
2279 bool SkOpSegment::checkSmall(int index) const {
2280 if (fTs[index].fSmall) {
2283 double tBase = fTs[index].fT;
2284 while (index > 0 && precisely_negative(tBase - fTs[--index].fT))
2286 return fTs[index].fSmall;
2289 // a pair of curves may turn into coincident lines -- small may be a hint that that happened
2290 // if a cubic contains a loop, the counts must be adjusted
2291 void SkOpSegment::checkSmall() {
2292 SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2293 const SkOpSpan* beginSpan = fTs.begin();
2294 const SkOpSpan* thisSpan = beginSpan - 1;
2295 const SkOpSpan* endSpan = fTs.end() - 1; // last can't be small
2296 while (++thisSpan < endSpan) {
2297 if (!thisSpan->fSmall) {
2300 if (!thisSpan->fWindValue) {
2303 const SkOpSpan& firstSpan = this->firstSpan(*thisSpan);
2304 const SkOpSpan& lastSpan = this->lastSpan(*thisSpan);
2305 const SkOpSpan* nextSpan = &firstSpan + 1;
2306 ptrdiff_t smallCount = &lastSpan - &firstSpan + 1;
2307 SkASSERT(1 <= smallCount && smallCount < count());
2308 if (smallCount <= 1 && !nextSpan->fSmall) {
2309 SkASSERT(1 == smallCount);
2310 checkSmallCoincidence(firstSpan, NULL);
2313 // at this point, check for missing computed intersections
2314 const SkPoint& testPt = firstSpan.fPt;
2315 thisSpan = &firstSpan - 1;
2316 SkOpSegment* other = NULL;
2317 while (++thisSpan <= &lastSpan) {
2318 other = thisSpan->fOther;
2319 if (other != this) {
2323 SkASSERT(other != this);
2324 int oIndex = thisSpan->fOtherIndex;
2325 const SkOpSpan& oSpan = other->span(oIndex);
2326 const SkOpSpan& oFirstSpan = other->firstSpan(oSpan);
2327 const SkOpSpan& oLastSpan = other->lastSpan(oSpan);
2328 ptrdiff_t oCount = &oLastSpan - &oFirstSpan + 1;
2331 SkASSERT(!other->fLoop); // FIXME: we need more complicated logic for pair of loops
2332 if (calcLoopSpanCount(*thisSpan, smallCounts)) {
2333 if (smallCounts[0] && oCount != smallCounts[0]) {
2334 SkASSERT(0); // FIXME: need a working test case to properly code & debug
2336 if (smallCounts[1] && oCount != smallCounts[1]) {
2337 SkASSERT(0); // FIXME: need a working test case to properly code & debug
2339 goto nextSmallCheck;
2344 if (other->calcLoopSpanCount(other->span(oIndex), otherCounts)) {
2345 if (otherCounts[0] && otherCounts[0] != smallCount) {
2346 SkASSERT(0); // FIXME: need a working test case to properly code & debug
2348 if (otherCounts[1] && otherCounts[1] != smallCount) {
2349 SkASSERT(0); // FIXME: need a working test case to properly code & debug
2351 goto nextSmallCheck;
2354 if (oCount != smallCount) { // check if number of pts in this match other
2355 MissingSpan& missing = missingSpans.push_back();
2356 missing.fOther = NULL;
2357 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2358 missing.fPt = testPt;
2359 const SkOpSpan& oSpan = other->span(oIndex);
2360 if (oCount > smallCount) {
2361 missing.fSegment = this;
2362 missing.fT = thisSpan->fT;
2363 other->checkLinks(&oSpan, &missingSpans);
2365 missing.fSegment = other;
2366 missing.fT = oSpan.fT;
2367 checkLinks(thisSpan, &missingSpans);
2369 if (!missingSpans.back().fOther || missing.fSegment->done()) {
2370 missingSpans.pop_back();
2374 thisSpan = &lastSpan;
2376 int missingCount = missingSpans.count();
2377 for (int index = 0; index < missingCount; ++index) {
2378 MissingSpan& missing = missingSpans[index];
2379 SkOpSegment* missingOther = missing.fOther;
2380 // note that add t pair may edit span arrays, so prior pointers to spans are no longer valid
2381 if (!missing.fSegment->addTPair(missing.fT, missingOther, missing.fOtherT, false,
2385 int otherTIndex = missingOther->findT(missing.fOtherT, missing.fPt, missing.fSegment);
2386 const SkOpSpan& otherSpan = missingOther->span(otherTIndex);
2387 if (otherSpan.fSmall) {
2388 const SkOpSpan* nextSpan = &otherSpan;
2391 } while (nextSpan->fSmall);
2392 SkAssertResult(missing.fSegment->addTCoincident(missing.fPt, nextSpan->fPt,
2393 nextSpan->fT, missingOther));
2394 } else if (otherSpan.fT > 0) {
2395 const SkOpSpan* priorSpan = &otherSpan;
2398 } while (priorSpan->fT == otherSpan.fT);
2399 if (priorSpan->fSmall) {
2400 missing.fSegment->addTCancel(missing.fPt, priorSpan->fPt, missingOther);
2404 // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
2406 for (int index = 0; index < missingCount; ++index) {
2407 MissingSpan& missing = missingSpans[index];
2408 missing.fSegment->fixOtherTIndex();
2409 missing.fOther->fixOtherTIndex();
2414 void SkOpSegment::checkSmallCoincidence(const SkOpSpan& span,
2415 SkTArray<MissingSpan, true>* checkMultiple) {
2416 SkASSERT(span.fSmall);
2417 if (0 && !span.fWindValue) {
2420 SkASSERT(&span < fTs.end() - 1);
2421 const SkOpSpan* next = &span + 1;
2422 SkASSERT(!next->fSmall || checkMultiple);
2423 if (checkMultiple) {
2424 while (next->fSmall) {
2426 SkASSERT(next < fTs.end());
2429 SkOpSegment* other = span.fOther;
2430 while (other != next->fOther) {
2431 if (!checkMultiple) {
2434 const SkOpSpan* test = next + 1;
2435 if (test == fTs.end()) {
2438 if (test->fPt != next->fPt || !precisely_equal(test->fT, next->fT)) {
2443 SkASSERT(span.fT < next->fT);
2444 int oStartIndex = other->findExactT(span.fOtherT, this);
2445 int oEndIndex = other->findExactT(next->fOtherT, this);
2446 // FIXME: be overly conservative by limiting this to the caller that allows multiple smalls
2447 if (!checkMultiple || fVerb != SkPath::kLine_Verb || other->fVerb != SkPath::kLine_Verb) {
2448 SkPoint mid = ptAtT((span.fT + next->fT) / 2);
2449 const SkOpSpan& oSpanStart = other->fTs[oStartIndex];
2450 const SkOpSpan& oSpanEnd = other->fTs[oEndIndex];
2451 SkPoint oMid = other->ptAtT((oSpanStart.fT + oSpanEnd.fT) / 2);
2452 if (!SkDPoint::ApproximatelyEqual(mid, oMid)) {
2456 // FIXME: again, be overly conservative to avoid breaking existing tests
2457 const SkOpSpan& oSpan = oStartIndex < oEndIndex ? other->fTs[oStartIndex]
2458 : other->fTs[oEndIndex];
2459 if (checkMultiple && !oSpan.fSmall) {
2462 SkASSERT(oSpan.fSmall);
2463 if (oStartIndex < oEndIndex) {
2464 SkAssertResult(addTCoincident(span.fPt, next->fPt, next->fT, other));
2466 addTCancel(span.fPt, next->fPt, other);
2468 if (!checkMultiple) {
2471 // check to see if either segment is coincident with a third segment -- if it is, and if
2472 // the opposite segment is not already coincident with the third, make it so
2473 // OPTIMIZE: to make this check easier, add coincident and cancel could set a coincident bit
2474 if (span.fWindValue != 1 || span.fOppValue != 0) {
2476 // iterate through the spans, looking for the third coincident case
2477 // if we find one, we need to return state to the caller so that the indices can be fixed
2478 // this also suggests that all of this function is fragile since it relies on a valid index
2480 // probably should make this a common function rather than copy/paste code
2481 if (oSpan.fWindValue != 1 || oSpan.fOppValue != 0) {
2482 const SkOpSpan* oTest = &oSpan;
2483 while (--oTest >= other->fTs.begin()) {
2484 if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) {
2487 SkOpSegment* testOther = oTest->fOther;
2488 SkASSERT(testOther != this);
2489 // look in both directions to see if there is a coincident span
2490 const SkOpSpan* tTest = testOther->fTs.begin();
2491 for (int testIndex = 0; testIndex < testOther->count(); ++testIndex) {
2492 if (tTest->fPt != span.fPt) {
2496 if (testOther->verb() != SkPath::kLine_Verb
2497 || other->verb() != SkPath::kLine_Verb) {
2498 SkPoint mid = ptAtT((span.fT + next->fT) / 2);
2499 SkPoint oMid = other->ptAtT((oTest->fOtherT + tTest->fT) / 2);
2500 if (!SkDPoint::ApproximatelyEqual(mid, oMid)) {
2505 SkDebugf("%s coincident found=%d %1.9g %1.9g\n", __FUNCTION__, testOther->fID,
2506 oTest->fOtherT, tTest->fT);
2508 if (tTest->fT < oTest->fOtherT) {
2509 SkAssertResult(addTCoincident(span.fPt, next->fPt, next->fT, testOther));
2511 addTCancel(span.fPt, next->fPt, testOther);
2513 MissingSpan missing;
2514 missing.fSegment = testOther;
2515 checkMultiple->push_back(missing);
2520 while (++oTest < other->fTs.end()) {
2521 if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) {
2529 // if pair of spans on either side of tiny have the same end point and mid point, mark
2531 void SkOpSegment::checkTiny() {
2532 SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2533 SkOpSpan* thisSpan = fTs.begin() - 1;
2534 const SkOpSpan* endSpan = fTs.end() - 1; // last can't be tiny
2535 while (++thisSpan < endSpan) {
2536 if (!thisSpan->fTiny) {
2539 SkOpSpan* nextSpan = thisSpan + 1;
2540 double thisT = thisSpan->fT;
2541 double nextT = nextSpan->fT;
2542 if (thisT == nextT) {
2545 SkASSERT(thisT < nextT);
2546 SkASSERT(thisSpan->fPt == nextSpan->fPt);
2547 SkOpSegment* thisOther = thisSpan->fOther;
2548 SkOpSegment* nextOther = nextSpan->fOther;
2549 int oIndex = thisSpan->fOtherIndex;
2550 for (int oStep = -1; oStep <= 1; oStep += 2) {
2551 int oEnd = thisOther->nextExactSpan(oIndex, oStep);
2555 const SkOpSpan& oSpan = thisOther->span(oEnd);
2556 int nIndex = nextSpan->fOtherIndex;
2557 for (int nStep = -1; nStep <= 1; nStep += 2) {
2558 int nEnd = nextOther->nextExactSpan(nIndex, nStep);
2562 const SkOpSpan& nSpan = nextOther->span(nEnd);
2563 if (oSpan.fPt != nSpan.fPt) {
2566 double oMidT = (thisSpan->fOtherT + oSpan.fT) / 2;
2567 const SkPoint& oPt = thisOther->ptAtT(oMidT);
2568 double nMidT = (nextSpan->fOtherT + nSpan.fT) / 2;
2569 const SkPoint& nPt = nextOther->ptAtT(nMidT);
2570 if (!AlmostEqualUlps(oPt, nPt)) {
2573 #if DEBUG_CHECK_TINY
2574 SkDebugf("%s [%d] add coincidence [%d] [%d]\n", __FUNCTION__, fID,
2575 thisOther->fID, nextOther->fID);
2577 // this segment is missing a entry that the other contains
2578 // remember so we can add the missing one and recompute the indices
2579 MissingSpan& missing = missingSpans.push_back();
2580 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2581 missing.fSegment = thisOther;
2582 missing.fT = thisSpan->fOtherT;
2583 missing.fOther = nextOther;
2584 missing.fOtherT = nextSpan->fOtherT;
2585 missing.fPt = thisSpan->fPt;
2589 int missingCount = missingSpans.count();
2590 if (!missingCount) {
2593 for (int index = 0; index < missingCount; ++index) {
2594 MissingSpan& missing = missingSpans[index];
2595 if (missing.fSegment != missing.fOther) {
2596 missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false,
2600 // OPTIMIZE: consolidate to avoid multiple calls to fix index
2601 for (int index = 0; index < missingCount; ++index) {
2602 MissingSpan& missing = missingSpans[index];
2603 missing.fSegment->fixOtherTIndex();
2604 missing.fOther->fixOtherTIndex();
2608 bool SkOpSegment::coincidentSmall(const SkPoint& pt, double t, const SkOpSegment* other) const {
2609 int count = this->count();
2610 for (int index = 0; index < count; ++index) {
2611 const SkOpSpan& span = this->span(index);
2612 if (span.fOther != other) {
2615 if (span.fPt == pt) {
2618 if (!AlmostEqualUlps(span.fPt, pt)) {
2621 if (fVerb != SkPath::kCubic_Verb) {
2624 double tInterval = t - span.fT;
2625 double tMid = t - tInterval / 2;
2626 SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
2627 return midPt.approximatelyEqual(xyAtT(t));
2632 bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart,
2633 int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const {
2634 SkASSERT(span->fT == 0 || span->fT == 1);
2635 SkASSERT(span->fOtherT == 0 || span->fOtherT == 1);
2636 const SkOpSpan* otherSpan = &other->span(oEnd);
2637 double refT = otherSpan->fT;
2638 const SkPoint& refPt = otherSpan->fPt;
2639 const SkOpSpan* lastSpan = &other->span(step > 0 ? other->count() - 1 : 0);
2641 const SkOpSegment* match = span->fOther;
2642 if (match == otherSpan->fOther) {
2643 // find start of respective spans and see if both have winding
2644 int startIndex, endIndex;
2645 if (span->fOtherT == 1) {
2646 endIndex = span->fOtherIndex;
2647 startIndex = match->nextExactSpan(endIndex, -1);
2649 startIndex = span->fOtherIndex;
2650 endIndex = match->nextExactSpan(startIndex, 1);
2652 const SkOpSpan& startSpan = match->span(startIndex);
2653 if (startSpan.fWindValue != 0) {
2654 // draw ray from endSpan.fPt perpendicular to end tangent and measure distance
2655 // to other segment.
2656 const SkOpSpan& endSpan = match->span(endIndex);
2659 if (span->fOtherT == 1) {
2660 ray.fPts[0].set(startSpan.fPt);
2661 dxdy = match->dxdy(startIndex);
2663 ray.fPts[0].set(endSpan.fPt);
2664 dxdy = match->dxdy(endIndex);
2666 ray.fPts[1].fX = ray.fPts[0].fX + dxdy.fY;
2667 ray.fPts[1].fY = ray.fPts[0].fY - dxdy.fX;
2669 int roots = (i.*CurveRay[SkPathOpsVerbToPoints(other->verb())])(other->pts(), ray);
2670 for (int index = 0; index < roots; ++index) {
2671 if (ray.fPts[0].approximatelyEqual(i.pt(index))) {
2672 double matchMidT = (match->span(startIndex).fT
2673 + match->span(endIndex).fT) / 2;
2674 SkPoint matchMidPt = match->ptAtT(matchMidT);
2675 double otherMidT = (i[0][index] + other->span(oStart).fT) / 2;
2676 SkPoint otherMidPt = other->ptAtT(otherMidT);
2677 if (SkDPoint::ApproximatelyEqual(matchMidPt, otherMidPt)) {
2678 *startPt = startSpan.fPt;
2679 *endPt = endSpan.fPt;
2688 if (otherSpan == lastSpan) {
2692 } while (otherSpan->fT == refT || otherSpan->fPt == refPt);
2696 int SkOpSegment::findEndSpan(int endIndex) const {
2697 const SkOpSpan* span = &fTs[--endIndex];
2698 const SkPoint& lastPt = span->fPt;
2699 double endT = span->fT;
2701 span = &fTs[--endIndex];
2702 } while (SkDPoint::ApproximatelyEqual(span->fPt, lastPt) && (span->fT == endT || span->fTiny));
2703 return endIndex + 1;
2707 The M and S variable name parts stand for the operators.
2708 Mi stands for Minuend (see wiki subtraction, analogous to difference)
2709 Su stands for Subtrahend
2710 The Opp variable name part designates that the value is for the Opposite operator.
2711 Opposite values result from combining coincident spans.
2713 SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
2714 bool* unsortable, SkPathOp op, const int xorMiMask,
2715 const int xorSuMask) {
2716 const int startIndex = *nextStart;
2717 const int endIndex = *nextEnd;
2718 SkASSERT(startIndex != endIndex);
2719 SkDEBUGCODE(const int count = fTs.count());
2720 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2721 int step = SkSign32(endIndex - startIndex);
2722 *nextStart = startIndex;
2723 SkOpSegment* other = isSimple(nextStart, &step);
2726 // mark the smaller of startIndex, endIndex done, and all adjacent
2727 // spans with the same T value (but not 'other' spans)
2729 SkDebugf("%s simple\n", __FUNCTION__);
2731 int min = SkMin32(startIndex, endIndex);
2732 if (fTs[min].fDone) {
2735 markDoneBinary(min);
2736 double startT = other->fTs[*nextStart].fT;
2737 *nextEnd = *nextStart;
2740 } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
2741 SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
2742 if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
2748 const int end = nextExactSpan(startIndex, step);
2750 SkASSERT(startIndex - endIndex != 0);
2751 SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2752 // more than one viable candidate -- measure angles to find best
2754 int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp);
2755 bool sortable = calcWinding != SK_NaN32;
2758 markDoneBinary(SkMin32(startIndex, endIndex));
2761 SkOpAngle* angle = spanToAngle(end, startIndex);
2762 if (angle->unorderable()) {
2764 markDoneBinary(SkMin32(startIndex, endIndex));
2768 SkDebugf("%s\n", __FUNCTION__);
2771 int sumMiWinding = updateWinding(endIndex, startIndex);
2772 if (sumMiWinding == SK_MinS32) {
2774 markDoneBinary(SkMin32(startIndex, endIndex));
2777 int sumSuWinding = updateOppWinding(endIndex, startIndex);
2779 SkTSwap<int>(sumMiWinding, sumSuWinding);
2781 SkOpAngle* nextAngle = angle->next();
2782 const SkOpAngle* foundAngle = NULL;
2783 bool foundDone = false;
2784 // iterate through the angle, and compute everyone's winding
2785 SkOpSegment* nextSegment;
2786 int activeCount = 0;
2788 nextSegment = nextAngle->segment();
2789 bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
2790 nextAngle->end(), op, &sumMiWinding, &sumSuWinding);
2793 if (!foundAngle || (foundDone && activeCount & 1)) {
2794 if (nextSegment->isTiny(nextAngle)) {
2796 markDoneBinary(SkMin32(startIndex, endIndex));
2799 foundAngle = nextAngle;
2800 foundDone = nextSegment->done(nextAngle);
2803 if (nextSegment->done()) {
2806 if (nextSegment->isTiny(nextAngle)) {
2810 (void) nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
2812 SkOpSpan* last = nextAngle->lastMarked();
2814 SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
2815 *chase->append() = last;
2817 SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
2818 last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
2822 } while ((nextAngle = nextAngle->next()) != angle);
2825 foundAngle->debugSameAs(foundAngle);
2829 markDoneBinary(SkMin32(startIndex, endIndex));
2833 *nextStart = foundAngle->start();
2834 *nextEnd = foundAngle->end();
2835 nextSegment = foundAngle->segment();
2837 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2838 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
2843 SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart,
2844 int* nextEnd, bool* unsortable) {
2845 const int startIndex = *nextStart;
2846 const int endIndex = *nextEnd;
2847 SkASSERT(startIndex != endIndex);
2848 SkDEBUGCODE(const int count = fTs.count());
2849 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2850 int step = SkSign32(endIndex - startIndex);
2851 *nextStart = startIndex;
2852 SkOpSegment* other = isSimple(nextStart, &step);
2855 // mark the smaller of startIndex, endIndex done, and all adjacent
2856 // spans with the same T value (but not 'other' spans)
2858 SkDebugf("%s simple\n", __FUNCTION__);
2860 int min = SkMin32(startIndex, endIndex);
2861 if (fTs[min].fDone) {
2865 double startT = other->fTs[*nextStart].fT;
2866 *nextEnd = *nextStart;
2869 } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
2870 SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
2871 if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
2877 const int end = nextExactSpan(startIndex, step);
2879 SkASSERT(startIndex - endIndex != 0);
2880 SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2881 // more than one viable candidate -- measure angles to find best
2883 int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding);
2884 bool sortable = calcWinding != SK_NaN32;
2887 markDoneUnary(SkMin32(startIndex, endIndex));
2890 SkOpAngle* angle = spanToAngle(end, startIndex);
2892 SkDebugf("%s\n", __FUNCTION__);
2895 int sumWinding = updateWinding(endIndex, startIndex);
2896 SkOpAngle* nextAngle = angle->next();
2897 const SkOpAngle* foundAngle = NULL;
2898 bool foundDone = false;
2899 SkOpSegment* nextSegment;
2900 int activeCount = 0;
2902 nextSegment = nextAngle->segment();
2903 bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
2907 if (!foundAngle || (foundDone && activeCount & 1)) {
2908 if (nextSegment->isTiny(nextAngle)) {
2910 markDoneUnary(SkMin32(startIndex, endIndex));
2913 foundAngle = nextAngle;
2914 foundDone = nextSegment->done(nextAngle);
2917 if (nextSegment->done()) {
2920 if (nextSegment->isTiny(nextAngle)) {
2924 nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end());
2926 SkOpSpan* last = nextAngle->lastMarked();
2928 SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
2929 *chase->append() = last;
2931 SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
2932 last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
2936 } while ((nextAngle = nextAngle->next()) != angle);
2937 markDoneUnary(SkMin32(startIndex, endIndex));
2941 *nextStart = foundAngle->start();
2942 *nextEnd = foundAngle->end();
2943 nextSegment = foundAngle->segment();
2945 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
2946 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
2951 SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsortable) {
2952 const int startIndex = *nextStart;
2953 const int endIndex = *nextEnd;
2954 SkASSERT(startIndex != endIndex);
2955 SkDEBUGCODE(int count = fTs.count());
2956 SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
2957 int step = SkSign32(endIndex - startIndex);
2958 // Detect cases where all the ends canceled out (e.g.,
2959 // there is no angle) and therefore there's only one valid connection
2960 *nextStart = startIndex;
2961 SkOpSegment* other = isSimple(nextStart, &step);
2965 SkDebugf("%s simple\n", __FUNCTION__);
2967 int min = SkMin32(startIndex, endIndex);
2968 if (fTs[min].fDone) {
2972 double startT = other->fTs[*nextStart].fT;
2973 // FIXME: I don't know why the logic here is difference from the winding case
2974 SkDEBUGCODE(bool firstLoop = true;)
2975 if ((approximately_less_than_zero(startT) && step < 0)
2976 || (approximately_greater_than_one(startT) && step > 0)) {
2978 SkDEBUGCODE(firstLoop = false;)
2981 *nextEnd = *nextStart;
2984 } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
2985 if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) {
2988 SkASSERT(firstLoop);
2989 SkDEBUGCODE(firstLoop = false;)
2992 SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
2995 SkASSERT(startIndex - endIndex != 0);
2996 SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
2997 // parallel block above with presorted version
2998 int end = nextExactSpan(startIndex, step);
3000 SkOpAngle* angle = spanToAngle(end, startIndex);
3003 SkDebugf("%s\n", __FUNCTION__);
3006 SkOpAngle* nextAngle = angle->next();
3007 const SkOpAngle* foundAngle = NULL;
3008 bool foundDone = false;
3009 SkOpSegment* nextSegment;
3010 int activeCount = 0;
3012 nextSegment = nextAngle->segment();
3014 if (!foundAngle || (foundDone && activeCount & 1)) {
3015 if (nextSegment->isTiny(nextAngle)) {
3019 foundAngle = nextAngle;
3020 if (!(foundDone = nextSegment->done(nextAngle))) {
3024 nextAngle = nextAngle->next();
3025 } while (nextAngle != angle);
3026 markDone(SkMin32(startIndex, endIndex), 1);
3030 *nextStart = foundAngle->start();
3031 *nextEnd = foundAngle->end();
3032 nextSegment = foundAngle->segment();
3034 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
3035 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
3040 int SkOpSegment::findStartSpan(int startIndex) const {
3041 int index = startIndex;
3042 const SkOpSpan* span = &fTs[index];
3043 const SkPoint& firstPt = span->fPt;
3044 double firstT = span->fT;
3045 const SkOpSpan* prior;
3048 span = &fTs[++index];
3049 } while (SkDPoint::ApproximatelyEqual(span->fPt, firstPt)
3050 && (span->fT == firstT || prior->fTiny));
3054 int SkOpSegment::findExactT(double t, const SkOpSegment* match) const {
3055 int count = this->count();
3056 for (int index = 0; index < count; ++index) {
3057 const SkOpSpan& span = fTs[index];
3058 if (span.fT == t && span.fOther == match) {
3066 int SkOpSegment::findOtherT(double t, const SkOpSegment* match) const {
3067 int count = this->count();
3068 for (int index = 0; index < count; ++index) {
3069 const SkOpSpan& span = fTs[index];
3070 if (span.fOtherT == t && span.fOther == match) {
3077 int SkOpSegment::findT(double t, const SkPoint& pt, const SkOpSegment* match) const {
3078 int count = this->count();
3079 // prefer exact matches over approximate matches
3080 for (int index = 0; index < count; ++index) {
3081 const SkOpSpan& span = fTs[index];
3082 if (span.fT == t && span.fOther == match) {
3086 for (int index = 0; index < count; ++index) {
3087 const SkOpSpan& span = fTs[index];
3088 if (approximately_equal_orderable(span.fT, t) && span.fOther == match) {
3092 // Usually, the pair of ts are an exact match. It's possible that the t values have
3093 // been adjusted to make multiple intersections align. In this rare case, look for a
3094 // matching point / match pair instead.
3095 for (int index = 0; index < count; ++index) {
3096 const SkOpSpan& span = fTs[index];
3097 if (span.fPt == pt && span.fOther == match) {
3105 SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable,
3107 // iterate through T intersections and return topmost
3108 // topmost tangent from y-min to first pt is closer to horizontal
3111 /* SkPoint topPt = */ activeLeftTop(&firstT);
3113 *unsortable = !firstPass;
3115 while (fTs[firstT].fDone) {
3116 SkASSERT(firstT < fTs.count());
3119 *tIndexPtr = firstT;
3120 *endIndexPtr = nextExactSpan(firstT, 1);
3123 // sort the edges to find the leftmost
3126 if (span(firstT).fDone || (end = nextSpan(firstT, step)) == -1) {
3128 end = nextSpan(firstT, step);
3129 SkASSERT(end != -1);
3131 // if the topmost T is not on end, or is three-way or more, find left
3132 // look for left-ness from tLeft to firstT (matching y of other)
3133 SkASSERT(firstT - end != 0);
3134 SkOpAngle* markAngle = spanToAngle(firstT, end);
3136 markAngle = addSingletonAngles(step);
3138 markAngle->markStops();
3139 const SkOpAngle* baseAngle = markAngle->next() == markAngle && !isVertical() ? markAngle
3140 : markAngle->findFirst();
3142 return NULL; // nothing to do
3144 SkScalar top = SK_ScalarMax;
3145 const SkOpAngle* firstAngle = NULL;
3146 const SkOpAngle* angle = baseAngle;
3148 if (!angle->unorderable()) {
3149 SkOpSegment* next = angle->segment();
3150 SkPathOpsBounds bounds;
3151 next->subDivideBounds(angle->end(), angle->start(), &bounds);
3152 if (approximately_greater(top, bounds.fTop)) {
3157 angle = angle->next();
3158 } while (angle != baseAngle);
3159 SkASSERT(firstAngle);
3161 SkDebugf("%s\n", __FUNCTION__);
3162 firstAngle->debugLoop();
3164 // skip edges that have already been processed
3166 SkOpSegment* leftSegment = NULL;
3167 bool looped = false;
3169 *unsortable = angle->unorderable();
3170 if (firstPass || !*unsortable) {
3171 leftSegment = angle->segment();
3172 *tIndexPtr = angle->end();
3173 *endIndexPtr = angle->start();
3174 if (!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone) {
3178 angle = angle->next();
3180 } while (angle != firstAngle);
3181 if (angle == firstAngle && looped) {
3184 if (leftSegment->verb() >= SkPath::kQuad_Verb) {
3185 const int tIndex = *tIndexPtr;
3186 const int endIndex = *endIndexPtr;
3188 if (!leftSegment->clockwise(tIndex, endIndex, &swap)) {
3190 SkDebugf("%s swap=%d inflections=%d serpentine=%d controlledbyends=%d monotonic=%d\n",
3192 swap, leftSegment->debugInflections(tIndex, endIndex),
3193 leftSegment->serpentine(tIndex, endIndex),
3194 leftSegment->controlsContainedByEnds(tIndex, endIndex),
3195 leftSegment->monotonicInY(tIndex, endIndex));
3198 // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first
3199 // sorted but merely the first not already processed (i.e., not done)
3200 SkTSwap(*tIndexPtr, *endIndexPtr);
3204 SkASSERT(!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fTiny);
3208 int SkOpSegment::firstActive(int tIndex) const {
3209 while (fTs[tIndex].fTiny) {
3210 SkASSERT(!isCanceled(tIndex));
3216 // FIXME: not crazy about this
3217 // when the intersections are performed, the other index is into an
3218 // incomplete array. As the array grows, the indices become incorrect
3219 // while the following fixes the indices up again, it isn't smart about
3220 // skipping segments whose indices are already correct
3221 // assuming we leave the code that wrote the index in the first place
3222 // FIXME: if called after remove, this needs to correct tiny
3223 void SkOpSegment::fixOtherTIndex() {
3224 int iCount = fTs.count();
3225 for (int i = 0; i < iCount; ++i) {
3226 SkOpSpan& iSpan = fTs[i];
3227 double oT = iSpan.fOtherT;
3228 SkOpSegment* other = iSpan.fOther;
3229 int oCount = other->fTs.count();
3230 SkDEBUGCODE(iSpan.fOtherIndex = -1);
3231 for (int o = 0; o < oCount; ++o) {
3232 SkOpSpan& oSpan = other->fTs[o];
3233 if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) {
3234 iSpan.fOtherIndex = o;
3235 oSpan.fOtherIndex = i;
3239 SkASSERT(iSpan.fOtherIndex >= 0);
3243 bool SkOpSegment::inCoincidentSpan(double t, const SkOpSegment* other) const {
3245 int count = this->count();
3246 for (int index = 0; index < count; ++index) {
3247 const SkOpSpan& span = this->span(index);
3248 if (span.fCoincident) {
3249 foundEnds |= (span.fOther == other) << ((t > span.fT) + (t >= span.fT));
3252 SkASSERT(foundEnds != 7);
3253 return foundEnds == 0x3 || foundEnds == 0x5 || foundEnds == 0x6; // two bits set
3256 void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
3262 fLoop = fMultiples = fSmall = fTiny = false;
3265 void SkOpSegment::initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType) {
3266 int local = spanSign(start, end);
3267 if (angleIncludeType == SkOpAngle::kBinarySingle) {
3268 int oppLocal = oppSign(start, end);
3269 (void) markAndChaseWinding(start, end, local, oppLocal);
3270 // OPTIMIZATION: the reverse mark and chase could skip the first marking
3271 (void) markAndChaseWinding(end, start, local, oppLocal);
3273 (void) markAndChaseWinding(start, end, local);
3274 // OPTIMIZATION: the reverse mark and chase could skip the first marking
3275 (void) markAndChaseWinding(end, start, local);
3280 when we start with a vertical intersect, we try to use the dx to determine if the edge is to
3281 the left or the right of vertical. This determines if we need to add the span's
3282 sign or not. However, this isn't enough.
3283 If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
3284 If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
3285 from has the same x direction as this span, the winding should change. If the dx is opposite, then
3286 the same winding is shared by both.
3288 void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkScalar hitDx,
3289 int oppWind, SkScalar hitOppDx) {
3290 SkASSERT(hitDx || !winding);
3291 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
3293 int windVal = windValue(SkMin32(start, end));
3294 #if DEBUG_WINDING_AT_T
3295 SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, debugID(), winding,
3296 hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
3298 int sideWind = winding + (dx < 0 ? windVal : -windVal);
3299 if (abs(winding) < abs(sideWind)) {
3302 SkDEBUGCODE(int oppLocal = oppSign(start, end));
3303 SkASSERT(hitOppDx || !oppWind || !oppLocal);
3304 int oppWindVal = oppValue(SkMin32(start, end));
3306 oppWind = dx < 0 ? oppWindVal : -oppWindVal;
3307 } else if (hitOppDx * dx >= 0) {
3308 int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
3309 if (abs(oppWind) < abs(oppSideWind)) {
3310 oppWind = oppSideWind;
3313 #if DEBUG_WINDING_AT_T
3314 SkDebugf(" winding=%d oppWind=%d\n", winding, oppWind);
3316 (void) markAndChaseWinding(start, end, winding, oppWind);
3317 // OPTIMIZATION: the reverse mark and chase could skip the first marking
3318 (void) markAndChaseWinding(end, start, winding, oppWind);
3321 bool SkOpSegment::inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const {
3322 if (!baseAngle->inLoop()) {
3325 int index = *indexPtr;
3326 SkOpAngle* from = fTs[index].fFromAngle;
3327 SkOpAngle* to = fTs[index].fToAngle;
3328 while (++index < spanCount) {
3329 SkOpAngle* nextFrom = fTs[index].fFromAngle;
3330 SkOpAngle* nextTo = fTs[index].fToAngle;
3331 if (from != nextFrom || to != nextTo) {
3339 // OPTIMIZE: successive calls could start were the last leaves off
3340 // or calls could specialize to walk forwards or backwards
3341 bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const {
3342 int tCount = fTs.count();
3343 for (int index = 0; index < tCount; ++index) {
3344 const SkOpSpan& span = fTs[index];
3345 if (approximately_zero(startT - span.fT) && pt == span.fPt) {
3353 SkOpSegment* SkOpSegment::isSimple(int* end, int* step) {
3354 return nextChase(end, step, NULL, NULL);
3357 bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
3358 int start = angle->start();
3359 int end = angle->end();
3360 const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
3364 bool SkOpSegment::isTiny(int index) const {
3365 return fTs[index].fTiny;
3368 // look pair of active edges going away from coincident edge
3369 // one of them should be the continuation of other
3370 // if both are active, look to see if they both the connect to another coincident pair
3371 // if at least one is a line, then make the pair coincident
3372 // if neither is a line, test for coincidence
3373 bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, const SkPoint& otherPt,
3374 int step, bool cancel) {
3375 int otherTIndex = other->findT(otherT, otherPt, this);
3376 int next = other->nextExactSpan(otherTIndex, step);
3377 int otherMin = SkMin32(otherTIndex, next);
3378 int otherWind = other->span(otherMin).fWindValue;
3379 if (otherWind == 0) {
3382 SkASSERT(next >= 0);
3385 SkOpSpan* test = &fTs[tIndex];
3386 SkASSERT(test->fT == 0);
3387 if (test->fOther == other || test->fOtherT != 1) {
3390 SkPoint startPt, endPt;
3392 if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
3393 SkOpSegment* match = test->fOther;
3395 match->addTCancel(startPt, endPt, other);
3397 SkAssertResult(match->addTCoincident(startPt, endPt, endT, other));
3401 } while (fTs[++tIndex].fT == 0);
3405 // this span is excluded by the winding rule -- chase the ends
3406 // as long as they are unambiguous to mark connections as done
3407 // and give them the same winding value
3409 SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) {
3410 int step = SkSign32(endIndex - index);
3411 int min = SkMin32(index, endIndex);
3412 markDoneBinary(min);
3413 SkOpSpan* last = NULL;
3414 SkOpSegment* other = this;
3415 while ((other = other->nextChase(&index, &step, &min, &last))) {
3416 if (other->done()) {
3420 other->markDoneBinary(min);
3425 SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) {
3426 int step = SkSign32(endIndex - index);
3427 int min = SkMin32(index, endIndex);
3429 SkOpSpan* last = NULL;
3430 SkOpSegment* other = this;
3431 while ((other = other->nextChase(&index, &step, &min, &last))) {
3432 if (other->done()) {
3436 other->markDoneUnary(min);
3441 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding) {
3442 int index = angle->start();
3443 int endIndex = angle->end();
3444 int step = SkSign32(endIndex - index);
3445 int min = SkMin32(index, endIndex);
3446 markWinding(min, winding);
3447 SkOpSpan* last = NULL;
3448 SkOpSegment* other = this;
3449 while ((other = other->nextChase(&index, &step, &min, &last))) {
3450 if (other->fTs[min].fWindSum != SK_MinS32) {
3451 // SkASSERT(other->fTs[min].fWindSum == winding);
3455 other->markWinding(min, winding);
3460 SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding) {
3461 int min = SkMin32(index, endIndex);
3462 int step = SkSign32(endIndex - index);
3463 markWinding(min, winding);
3464 SkOpSpan* last = NULL;
3465 SkOpSegment* other = this;
3466 while ((other = other->nextChase(&index, &step, &min, &last))) {
3467 if (other->fTs[min].fWindSum != SK_MinS32) {
3468 SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
3472 other->markWinding(min, winding);
3477 SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
3478 int min = SkMin32(index, endIndex);
3479 int step = SkSign32(endIndex - index);
3480 markWinding(min, winding, oppWinding);
3481 SkOpSpan* last = NULL;
3482 SkOpSegment* other = this;
3483 while ((other = other->nextChase(&index, &step, &min, &last))) {
3484 if (other->fTs[min].fWindSum != SK_MinS32) {
3486 if (!other->fTs[min].fLoop) {
3487 if (fOperand == other->fOperand) {
3488 // FIXME: this is probably a bug -- rects4 asserts here
3489 // SkASSERT(other->fTs[min].fWindSum == winding);
3490 // FIXME: this is probably a bug -- rects3 asserts here
3491 // SkASSERT(other->fTs[min].fOppSum == oppWinding);
3493 SkASSERT(other->fTs[min].fWindSum == oppWinding);
3494 // FIXME: this is probably a bug -- skpwww_joomla_org_23 asserts here
3495 // SkASSERT(other->fTs[min].fOppSum == winding);
3502 if (fOperand == other->fOperand) {
3503 other->markWinding(min, winding, oppWinding);
3505 other->markWinding(min, oppWinding, winding);
3511 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding) {
3512 int start = angle->start();
3513 int end = angle->end();
3514 return markAndChaseWinding(start, end, winding, oppWinding);
3517 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
3518 SkASSERT(angle->segment() == this);
3519 if (UseInnerWinding(maxWinding, sumWinding)) {
3520 maxWinding = sumWinding;
3522 SkOpSpan* last = markAndChaseWinding(angle, maxWinding);
3525 SkDebugf("%s last id=%d windSum=", __FUNCTION__,
3526 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
3527 SkPathOpsDebug::WindingPrintf(last->fWindSum);
3528 SkDebugf(" small=%d\n", last->fSmall);
3534 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
3535 int oppSumWinding, const SkOpAngle* angle) {
3536 SkASSERT(angle->segment() == this);
3537 if (UseInnerWinding(maxWinding, sumWinding)) {
3538 maxWinding = sumWinding;
3540 if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
3541 oppMaxWinding = oppSumWinding;
3543 SkOpSpan* last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
3546 SkDebugf("%s last id=%d windSum=", __FUNCTION__,
3547 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
3548 SkPathOpsDebug::WindingPrintf(last->fWindSum);
3549 SkDebugf(" small=%d\n", last->fSmall);
3555 // FIXME: this should also mark spans with equal (x,y)
3556 // This may be called when the segment is already marked done. While this
3557 // wastes time, it shouldn't do any more than spin through the T spans.
3558 // OPTIMIZATION: abort on first done found (assuming that this code is
3559 // always called to mark segments done).
3560 void SkOpSegment::markDone(int index, int winding) {
3561 // SkASSERT(!done());
3563 double referenceT = fTs[index].fT;
3565 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3566 markOneDone(__FUNCTION__, lesser, winding);
3569 markOneDone(__FUNCTION__, index, winding);
3570 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3574 void SkOpSegment::markDoneBinary(int index) {
3575 double referenceT = fTs[index].fT;
3577 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3578 markOneDoneBinary(__FUNCTION__, lesser);
3581 markOneDoneBinary(__FUNCTION__, index);
3582 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3586 void SkOpSegment::markDoneUnary(int index) {
3587 double referenceT = fTs[index].fT;
3589 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3590 markOneDoneUnary(__FUNCTION__, lesser);
3593 markOneDoneUnary(__FUNCTION__, index);
3594 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3598 void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) {
3599 SkOpSpan* span = markOneWinding(funName, tIndex, winding);
3600 if (!span || span->fDone) {
3607 void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) {
3608 SkOpSpan* span = verifyOneWinding(funName, tIndex);
3612 SkASSERT(!span->fDone);
3617 void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) {
3618 SkOpSpan* span = verifyOneWindingU(funName, tIndex);
3622 if (span->fWindSum == SK_MinS32) {
3623 SkDebugf("%s uncomputed\n", __FUNCTION__);
3625 SkASSERT(!span->fDone);
3630 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding) {
3631 SkOpSpan& span = fTs[tIndex];
3632 if (span.fDone && !span.fSmall) {
3636 debugShowNewWinding(funName, span, winding);
3638 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3639 #if DEBUG_LIMIT_WIND_SUM
3640 SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
3642 span.fWindSum = winding;
3646 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding,
3648 SkOpSpan& span = fTs[tIndex];
3649 if (span.fDone && !span.fSmall) {
3653 debugShowNewWinding(funName, span, winding, oppWinding);
3655 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
3656 #if DEBUG_LIMIT_WIND_SUM
3657 SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
3659 span.fWindSum = winding;
3660 SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
3661 #if DEBUG_LIMIT_WIND_SUM
3662 SkASSERT(abs(oppWinding) <= DEBUG_LIMIT_WIND_SUM);
3664 span.fOppSum = oppWinding;
3669 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
3670 bool SkOpSegment::clockwise(int tStart, int tEnd, bool* swap) const {
3671 SkASSERT(fVerb != SkPath::kLine_Verb);
3673 subDivide(tStart, tEnd, edge);
3674 int points = SkPathOpsVerbToPoints(fVerb);
3675 double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
3676 bool sumSet = false;
3677 if (fVerb == SkPath::kCubic_Verb) {
3680 double inflectionTs[2];
3681 int inflections = cubic.findInflections(inflectionTs);
3682 // FIXME: this fixes cubicOp114 and breaks cubicOp58d
3683 // the trouble is that cubics with inflections confuse whether the curve breaks towards
3684 // or away, which in turn is used to determine if it is on the far right or left.
3685 // Probably a totally different approach is in order. At one time I tried to project a
3686 // horizontal ray to determine winding, but was confused by how to map the vertically
3687 // oriented winding computation over.
3688 if (0 && inflections) {
3689 double tLo = this->span(tStart).fT;
3690 double tHi = this->span(tEnd).fT;
3691 double tLoStart = tLo;
3692 for (int index = 0; index < inflections; ++index) {
3693 if (between(tLo, inflectionTs[index], tHi)) {
3694 tLo = inflectionTs[index];
3697 if (tLo != tLoStart && tLo != tHi) {
3699 sub[0] = cubic.ptAtT(tLo);
3700 sub[1].set(edge[3]);
3702 SkDCubic::SubDivide(fPts, sub[0], sub[1], tLo, tHi, ctrl);
3703 edge[0] = sub[0].asSkPoint();
3704 edge[1] = ctrl[0].asSkPoint();
3705 edge[2] = ctrl[1].asSkPoint();
3706 sum = (edge[0].fX - edge[3].fX) * (edge[0].fY + edge[3].fY);
3709 SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY);
3710 if (edge[1].fY < lesser && edge[2].fY < lesser) {
3711 SkDLine tangent1 = {{ {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1].fY} }};
3712 SkDLine tangent2 = {{ {edge[2].fX, edge[2].fY}, {edge[3].fX, edge[3].fY} }};
3713 if (SkIntersections::Test(tangent1, tangent2)) {
3714 SkPoint topPt = cubic_top(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3715 sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY);
3716 sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY);
3722 for (int idx = 0; idx < points; ++idx){
3723 sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
3726 if (fVerb == SkPath::kCubic_Verb) {
3729 *swap = sum > 0 && !cubic.monotonicInY() && !cubic.serpentine();
3733 *swap = sum > 0 && !quad.monotonicInY();
3738 bool SkOpSegment::monotonicInY(int tStart, int tEnd) const {
3739 SkASSERT(fVerb != SkPath::kLine_Verb);
3740 if (fVerb == SkPath::kQuad_Verb) {
3741 SkDQuad dst = SkDQuad::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3742 return dst.monotonicInY();
3744 SkASSERT(fVerb == SkPath::kCubic_Verb);
3745 SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3746 return dst.monotonicInY();
3749 bool SkOpSegment::serpentine(int tStart, int tEnd) const {
3750 if (fVerb != SkPath::kCubic_Verb) {
3753 SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
3754 return dst.serpentine();
3757 SkOpSpan* SkOpSegment::verifyOneWinding(const char* funName, int tIndex) {
3758 SkOpSpan& span = fTs[tIndex];
3763 debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
3765 // If the prior angle in the sort is unorderable, the winding sum may not be computable.
3766 // To enable the assert, the 'prior is unorderable' state could be
3767 // piped down to this test, but not sure it's worth it.
3768 // (Once the sort order is stored in the span, this test may be feasible.)
3769 // SkASSERT(span.fWindSum != SK_MinS32);
3770 // SkASSERT(span.fOppSum != SK_MinS32);
3774 SkOpSpan* SkOpSegment::verifyOneWindingU(const char* funName, int tIndex) {
3775 SkOpSpan& span = fTs[tIndex];
3780 debugShowNewWinding(funName, span, span.fWindSum);
3782 // If the prior angle in the sort is unorderable, the winding sum may not be computable.
3783 // To enable the assert, the 'prior is unorderable' state could be
3784 // piped down to this test, but not sure it's worth it.
3785 // (Once the sort order is stored in the span, this test may be feasible.)
3786 // SkASSERT(span.fWindSum != SK_MinS32);
3790 void SkOpSegment::markWinding(int index, int winding) {
3791 // SkASSERT(!done());
3793 double referenceT = fTs[index].fT;
3795 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3796 markOneWinding(__FUNCTION__, lesser, winding);
3799 markOneWinding(__FUNCTION__, index, winding);
3800 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3804 void SkOpSegment::markWinding(int index, int winding, int oppWinding) {
3805 // SkASSERT(!done());
3806 SkASSERT(winding || oppWinding);
3807 double referenceT = fTs[index].fT;
3809 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3810 markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
3813 markOneWinding(__FUNCTION__, index, winding, oppWinding);
3814 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
3818 void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) {
3819 int nextDoorWind = SK_MaxS32;
3820 int nextOppWind = SK_MaxS32;
3821 // prefer exact matches
3823 const SkOpSpan& below = fTs[tIndex - 1];
3824 if (below.fT == t) {
3825 nextDoorWind = below.fWindValue;
3826 nextOppWind = below.fOppValue;
3829 if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
3830 const SkOpSpan& above = fTs[tIndex + 1];
3831 if (above.fT == t) {
3832 nextDoorWind = above.fWindValue;
3833 nextOppWind = above.fOppValue;
3836 if (nextDoorWind == SK_MaxS32 && tIndex > 0) {
3837 const SkOpSpan& below = fTs[tIndex - 1];
3838 if (approximately_negative(t - below.fT)) {
3839 nextDoorWind = below.fWindValue;
3840 nextOppWind = below.fOppValue;
3843 if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
3844 const SkOpSpan& above = fTs[tIndex + 1];
3845 if (approximately_negative(above.fT - t)) {
3846 nextDoorWind = above.fWindValue;
3847 nextOppWind = above.fOppValue;
3850 if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
3851 const SkOpSpan& below = fTs[tIndex - 1];
3852 nextDoorWind = below.fWindValue;
3853 nextOppWind = below.fOppValue;
3855 if (nextDoorWind != SK_MaxS32) {
3856 SkOpSpan& newSpan = fTs[tIndex];
3857 newSpan.fWindValue = nextDoorWind;
3858 newSpan.fOppValue = nextOppWind;
3859 if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
3860 newSpan.fDone = true;
3866 bool SkOpSegment::nextCandidate(int* start, int* end) const {
3867 while (fTs[*end].fDone) {
3868 if (fTs[*end].fT == 1) {
3874 *end = nextExactSpan(*start, 1);
3878 static SkOpSegment* set_last(SkOpSpan** last, SkOpSpan* endSpan) {
3879 if (last && !endSpan->fSmall) {
3885 SkOpSegment* SkOpSegment::nextChase(int* indexPtr, int* stepPtr, int* minPtr, SkOpSpan** last) {
3886 int origIndex = *indexPtr;
3887 int step = *stepPtr;
3888 int end = nextExactSpan(origIndex, step);
3890 SkOpSpan& endSpan = fTs[end];
3891 SkOpAngle* angle = step > 0 ? endSpan.fFromAngle : endSpan.fToAngle;
3895 if (angle == NULL) {
3896 if (endSpan.fT != 0 && endSpan.fT != 1) {
3899 other = endSpan.fOther;
3900 foundIndex = endSpan.fOtherIndex;
3901 otherEnd = other->nextExactSpan(foundIndex, step);
3903 int loopCount = angle->loopCount();
3904 if (loopCount > 2) {
3905 return set_last(last, &endSpan);
3907 const SkOpAngle* next = angle->next();
3908 if (angle->sign() != next->sign()) {
3910 SkDebugf("%s mismatched signs\n", __FUNCTION__);
3912 // return set_last(last, &endSpan);
3914 other = next->segment();
3915 foundIndex = end = next->start();
3916 otherEnd = next->end();
3918 int foundStep = foundIndex < otherEnd ? 1 : -1;
3919 if (*stepPtr != foundStep) {
3920 return set_last(last, &endSpan);
3922 SkASSERT(*indexPtr >= 0);
3923 SkASSERT(otherEnd >= 0);
3925 int origMin = origIndex + (step < 0 ? step : 0);
3926 const SkOpSpan& orig = this->span(origMin);
3928 int foundMin = SkMin32(foundIndex, otherEnd);
3930 const SkOpSpan& found = other->span(foundMin);
3931 if (found.fWindValue != orig.fWindValue || found.fOppValue != orig.fOppValue) {
3932 return set_last(last, &endSpan);
3935 *indexPtr = foundIndex;
3936 *stepPtr = foundStep;
3943 // This has callers for two different situations: one establishes the end
3944 // of the current span, and one establishes the beginning of the next span
3945 // (thus the name). When this is looking for the end of the current span,
3946 // coincidence is found when the beginning Ts contain -step and the end
3947 // contains step. When it is looking for the beginning of the next, the
3948 // first Ts found can be ignored and the last Ts should contain -step.
3949 // OPTIMIZATION: probably should split into two functions
3950 int SkOpSegment::nextSpan(int from, int step) const {
3951 const SkOpSpan& fromSpan = fTs[from];
3952 int count = fTs.count();
3954 while (step > 0 ? ++to < count : --to >= 0) {
3955 const SkOpSpan& span = fTs[to];
3956 if (approximately_zero(span.fT - fromSpan.fT)) {
3965 // this returns at any difference in T, vs. a preset minimum. It may be
3966 // that all callers to nextSpan should use this instead.
3967 int SkOpSegment::nextExactSpan(int from, int step) const {
3970 const SkOpSpan& fromSpan = fTs[from];
3972 const SkOpSpan& span = fTs[to];
3973 if (precisely_negative(fromSpan.fT - span.fT) || span.fTiny) {
3979 while (fTs[from].fTiny) {
3982 const SkOpSpan& fromSpan = fTs[from];
3983 int count = fTs.count();
3984 while (++to < count) {
3985 const SkOpSpan& span = fTs[to];
3986 if (precisely_negative(span.fT - fromSpan.fT)) {
3995 void SkOpSegment::pinT(const SkPoint& pt, double* t) {
3996 if (pt == fPts[0]) {
3999 int count = SkPathOpsVerbToPoints(fVerb);
4000 if (pt == fPts[count]) {
4005 bool SkOpSegment::reversePoints(const SkPoint& p1, const SkPoint& p2) const {
4007 int spanCount = count();
4008 int p1IndexMin = -1;
4009 int p2IndexMax = spanCount;
4010 for (int index = 0; index < spanCount; ++index) {
4011 const SkOpSpan& span = fTs[index];
4012 if (span.fPt == p1) {
4013 if (p1IndexMin < 0) {
4016 } else if (span.fPt == p2) {
4020 return p1IndexMin > p2IndexMax;
4023 void SkOpSegment::setCoincidentRange(const SkPoint& startPt, const SkPoint& endPt,
4024 SkOpSegment* other) {
4025 int count = this->count();
4026 for (int index = 0; index < count; ++index) {
4027 SkOpSpan &span = fTs[index];
4028 if ((startPt == span.fPt || endPt == span.fPt) && other == span.fOther) {
4029 span.fCoincident = true;
4034 void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
4035 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
4036 int deltaSum = spanSign(index, endIndex);
4037 int oppDeltaSum = oppSign(index, endIndex);
4039 *maxWinding = *sumSuWinding;
4040 *sumWinding = *sumSuWinding -= deltaSum;
4041 *oppMaxWinding = *sumMiWinding;
4042 *oppSumWinding = *sumMiWinding -= oppDeltaSum;
4044 *maxWinding = *sumMiWinding;
4045 *sumWinding = *sumMiWinding -= deltaSum;
4046 *oppMaxWinding = *sumSuWinding;
4047 *oppSumWinding = *sumSuWinding -= oppDeltaSum;
4049 #if DEBUG_LIMIT_WIND_SUM
4050 SkASSERT(abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
4051 SkASSERT(abs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
4055 void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding,
4056 int* maxWinding, int* sumWinding) {
4057 int deltaSum = spanSign(index, endIndex);
4058 *maxWinding = *sumMiWinding;
4059 *sumWinding = *sumMiWinding -= deltaSum;
4060 #if DEBUG_LIMIT_WIND_SUM
4061 SkASSERT(abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
4065 void SkOpSegment::sortAngles() {
4066 int spanCount = fTs.count();
4067 if (spanCount <= 2) {
4072 SkOpAngle* fromAngle = fTs[index].fFromAngle;
4073 SkOpAngle* toAngle = fTs[index].fToAngle;
4074 if (!fromAngle && !toAngle) {
4078 SkOpAngle* baseAngle = NULL;
4080 baseAngle = fromAngle;
4081 if (inLoop(baseAngle, spanCount, &index)) {
4086 bool wroteAfterHeader = false;
4090 baseAngle = toAngle;
4091 if (inLoop(baseAngle, spanCount, &index)) {
4095 SkDEBUGCODE(int newIndex = index);
4096 SkASSERT(!inLoop(baseAngle, spanCount, &newIndex) && newIndex == index);
4098 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
4100 wroteAfterHeader = true;
4102 baseAngle->insert(toAngle);
4105 SkOpAngle* nextFrom, * nextTo;
4106 int firstIndex = index;
4108 SkOpSpan& span = fTs[index];
4109 SkOpSegment* other = span.fOther;
4110 SkOpSpan& oSpan = other->fTs[span.fOtherIndex];
4111 SkOpAngle* oAngle = oSpan.fFromAngle;
4114 if (!wroteAfterHeader) {
4115 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
4117 wroteAfterHeader = true;
4120 if (!oAngle->loopContains(*baseAngle)) {
4121 baseAngle->insert(oAngle);
4124 oAngle = oSpan.fToAngle;
4127 if (!wroteAfterHeader) {
4128 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
4130 wroteAfterHeader = true;
4133 if (!oAngle->loopContains(*baseAngle)) {
4134 baseAngle->insert(oAngle);
4137 if (++index == spanCount) {
4140 nextFrom = fTs[index].fFromAngle;
4141 nextTo = fTs[index].fToAngle;
4142 } while (fromAngle == nextFrom && toAngle == nextTo);
4143 if (baseAngle && baseAngle->loopCount() == 1) {
4146 SkOpSpan& span = fTs[index];
4147 span.fFromAngle = span.fToAngle = NULL;
4148 if (++index == spanCount) {
4151 nextFrom = fTs[index].fFromAngle;
4152 nextTo = fTs[index].fToAngle;
4153 } while (fromAngle == nextFrom && toAngle == nextTo);
4157 SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
4159 } while (index < spanCount);
4162 // return true if midpoints were computed
4163 bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
4164 SkASSERT(start != end);
4165 edge[0] = fTs[start].fPt;
4166 int points = SkPathOpsVerbToPoints(fVerb);
4167 edge[points] = fTs[end].fPt;
4168 if (fVerb == SkPath::kLine_Verb) {
4171 double startT = fTs[start].fT;
4172 double endT = fTs[end].fT;
4173 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
4174 // don't compute midpoints if we already have them
4175 if (fVerb == SkPath::kQuad_Verb) {
4179 SkASSERT(fVerb == SkPath::kCubic_Verb);
4189 const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
4190 if (fVerb == SkPath::kQuad_Verb) {
4191 edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
4193 SkASSERT(fVerb == SkPath::kCubic_Verb);
4195 SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
4196 edge[1] = ctrl[0].asSkPoint();
4197 edge[2] = ctrl[1].asSkPoint();
4202 // return true if midpoints were computed
4203 bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
4204 SkASSERT(start != end);
4205 (*result)[0].set(fTs[start].fPt);
4206 int points = SkPathOpsVerbToPoints(fVerb);
4207 (*result)[points].set(fTs[end].fPt);
4208 if (fVerb == SkPath::kLine_Verb) {
4211 double startT = fTs[start].fT;
4212 double endT = fTs[end].fT;
4213 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
4214 // don't compute midpoints if we already have them
4215 if (fVerb == SkPath::kQuad_Verb) {
4216 (*result)[1].set(fPts[1]);
4219 SkASSERT(fVerb == SkPath::kCubic_Verb);
4221 (*result)[1].set(fPts[1]);
4222 (*result)[2].set(fPts[2]);
4225 (*result)[1].set(fPts[2]);
4226 (*result)[2].set(fPts[1]);
4229 if (fVerb == SkPath::kQuad_Verb) {
4230 (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
4232 SkASSERT(fVerb == SkPath::kCubic_Verb);
4233 SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
4238 void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
4240 subDivide(start, end, edge);
4241 (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
4244 void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt,
4245 const SkPoint& startPt) {
4246 int outCount = outsidePts->count();
4247 if (outCount == 0 || endPt != (*outsidePts)[outCount - 2]) {
4248 outsidePts->push_back(endPt);
4249 outsidePts->push_back(startPt);
4253 void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoint& startPt) {
4254 int outCount = outsidePts->count();
4255 if (outCount == 0 || startPt != (*outsidePts)[outCount - 1]) {
4256 outsidePts->push_back(startPt);
4260 void SkOpSegment::undoneSpan(int* start, int* end) {
4261 int tCount = fTs.count();
4263 for (index = 0; index < tCount; ++index) {
4264 if (!fTs[index].fDone) {
4268 SkASSERT(index < tCount - 1);
4270 double startT = fTs[index].fT;
4271 while (approximately_negative(fTs[++index].fT - startT))
4272 SkASSERT(index < tCount);
4273 SkASSERT(index < tCount);
4277 int SkOpSegment::updateOppWinding(int index, int endIndex) const {
4278 int lesser = SkMin32(index, endIndex);
4279 int oppWinding = oppSum(lesser);
4280 int oppSpanWinding = oppSign(index, endIndex);
4281 if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
4282 && oppWinding != SK_MaxS32) {
4283 oppWinding -= oppSpanWinding;
4288 int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
4289 int startIndex = angle->start();
4290 int endIndex = angle->end();
4291 return updateOppWinding(endIndex, startIndex);
4294 int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
4295 int startIndex = angle->start();
4296 int endIndex = angle->end();
4297 return updateOppWinding(startIndex, endIndex);
4300 int SkOpSegment::updateWinding(int index, int endIndex) const {
4301 int lesser = SkMin32(index, endIndex);
4302 int winding = windSum(lesser);
4303 if (winding == SK_MinS32) {
4306 int spanWinding = spanSign(index, endIndex);
4307 if (winding && UseInnerWinding(winding - spanWinding, winding)
4308 && winding != SK_MaxS32) {
4309 winding -= spanWinding;
4314 int SkOpSegment::updateWinding(const SkOpAngle* angle) const {
4315 int startIndex = angle->start();
4316 int endIndex = angle->end();
4317 return updateWinding(endIndex, startIndex);
4320 int SkOpSegment::updateWindingReverse(int index, int endIndex) const {
4321 int lesser = SkMin32(index, endIndex);
4322 int winding = windSum(lesser);
4323 int spanWinding = spanSign(endIndex, index);
4324 if (winding && UseInnerWindingReverse(winding - spanWinding, winding)
4325 && winding != SK_MaxS32) {
4326 winding -= spanWinding;
4331 int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const {
4332 int startIndex = angle->start();
4333 int endIndex = angle->end();
4334 return updateWindingReverse(endIndex, startIndex);
4337 // OPTIMIZATION: does the following also work, and is it any faster?
4338 // return outerWinding * innerWinding > 0
4339 // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
4340 bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
4341 SkASSERT(outerWinding != SK_MaxS32);
4342 SkASSERT(innerWinding != SK_MaxS32);
4343 int absOut = abs(outerWinding);
4344 int absIn = abs(innerWinding);
4345 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
4349 bool SkOpSegment::UseInnerWindingReverse(int outerWinding, int innerWinding) {
4350 SkASSERT(outerWinding != SK_MaxS32);
4351 SkASSERT(innerWinding != SK_MaxS32);
4352 int absOut = abs(outerWinding);
4353 int absIn = abs(innerWinding);
4354 bool result = absOut == absIn ? true : absOut < absIn;
4358 int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const {
4359 if (approximately_zero(tHit - t(tIndex))) { // if we hit the end of a span, disregard
4362 int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);
4363 SkASSERT(winding != SK_MinS32);
4364 int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
4365 #if DEBUG_WINDING_AT_T
4366 SkDebugf("%s id=%d opp=%d tHit=%1.9g t=%1.9g oldWinding=%d windValue=%d", __FUNCTION__,
4367 debugID(), crossOpp, tHit, t(tIndex), winding, windVal);
4369 // see if a + change in T results in a +/- change in X (compute x'(T))
4370 *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
4371 if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) {
4372 *dx = fPts[2].fX - fPts[1].fX - *dx;
4375 #if DEBUG_WINDING_AT_T
4376 SkDebugf(" dx=0 winding=SK_MinS32\n");
4380 if (windVal < 0) { // reverse sign if opp contour traveled in reverse
4383 if (winding * *dx > 0) { // if same signs, result is negative
4384 winding += *dx > 0 ? -windVal : windVal;
4386 #if DEBUG_WINDING_AT_T
4387 SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding);
4392 int SkOpSegment::windSum(const SkOpAngle* angle) const {
4393 int start = angle->start();
4394 int end = angle->end();
4395 int index = SkMin32(start, end);
4396 return windSum(index);
4399 void SkOpSegment::zeroSpan(SkOpSpan* span) {
4400 SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
4401 span->fWindValue = 0;
4402 span->fOppValue = 0;
4403 if (span->fTiny || span->fSmall) {
4406 SkASSERT(!span->fDone);