michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #include "SkIntersections.h"
michael@0: #include "SkOpSegment.h"
michael@0: #include "SkPathWriter.h"
michael@0: #include "SkTSort.h"
michael@0: 
michael@0: #define F (false)      // discard the edge
michael@0: #define T (true)       // keep the edge
michael@0: 
michael@0: static const bool gUnaryActiveEdge[2][2] = {
michael@0: //  from=0  from=1
michael@0: //  to=0,1  to=0,1
michael@0:     {F, T}, {T, F},
michael@0: };
michael@0: 
michael@0: static const bool gActiveEdge[kXOR_PathOp + 1][2][2][2][2] = {
michael@0: //                 miFrom=0                              miFrom=1
michael@0: //         miTo=0            miTo=1              miTo=0             miTo=1
michael@0: //    suFrom=0    1     suFrom=0     1      suFrom=0    1      suFrom=0    1
michael@0: //   suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1  suTo=0,1 suTo=0,1
michael@0:     {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}},  // mi - su
michael@0:     {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}},  // mi & su
michael@0:     {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}},  // mi | su
michael@0:     {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}},  // mi ^ su
michael@0: };
michael@0: 
michael@0: #undef F
michael@0: #undef T
michael@0: 
michael@0: enum {
michael@0:     kOutsideTrackedTCount = 16,  // FIXME: determine what this should be
michael@0:     kMissingSpanCount = 4,  // FIXME: determine what this should be
michael@0: };
michael@0: 
michael@0: // note that this follows the same logic flow as build angles
michael@0: bool SkOpSegment::activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
michael@0:     if (activeAngleInner(index, done, angles)) {
michael@0:         return true;
michael@0:     }
michael@0:     double referenceT = fTs[index].fT;
michael@0:     int lesser = index;
michael@0:     while (--lesser >= 0
michael@0:             && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
michael@0:         if (activeAngleOther(lesser, done, angles)) {
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0:     do {
michael@0:         if (activeAngleOther(index, done, angles)) {
michael@0:             return true;
michael@0:         }
michael@0:         if (++index == fTs.count()) {
michael@0:             break;
michael@0:         }
michael@0:         if (fTs[index - 1].fTiny) {
michael@0:             referenceT = fTs[index].fT;
michael@0:             continue;
michael@0:         }
michael@0:     } while (precisely_negative(fTs[index].fT - referenceT));
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
michael@0:     SkOpSpan* span = &fTs[index];
michael@0:     SkOpSegment* other = span->fOther;
michael@0:     int oIndex = span->fOtherIndex;
michael@0:     return other->activeAngleInner(oIndex, done, angles);
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
michael@0:     int next = nextExactSpan(index, 1);
michael@0:     if (next > 0) {
michael@0:         SkOpSpan& upSpan = fTs[index];
michael@0:         if (upSpan.fWindValue || upSpan.fOppValue) {
michael@0:             addAngle(angles, index, next);
michael@0:             if (upSpan.fDone || upSpan.fUnsortableEnd) {
michael@0:                 (*done)++;
michael@0:             } else if (upSpan.fWindSum != SK_MinS32) {
michael@0:                 return true;
michael@0:             }
michael@0:         } else if (!upSpan.fDone) {
michael@0:             upSpan.fDone = true;
michael@0:             fDoneSpans++;
michael@0:         }
michael@0:     }
michael@0:     int prev = nextExactSpan(index, -1);
michael@0:     // edge leading into junction
michael@0:     if (prev >= 0) {
michael@0:         SkOpSpan& downSpan = fTs[prev];
michael@0:         if (downSpan.fWindValue || downSpan.fOppValue) {
michael@0:             addAngle(angles, index, prev);
michael@0:             if (downSpan.fDone) {
michael@0:                 (*done)++;
michael@0:              } else if (downSpan.fWindSum != SK_MinS32) {
michael@0:                 return true;
michael@0:             }
michael@0:         } else if (!downSpan.fDone) {
michael@0:             downSpan.fDone = true;
michael@0:             fDoneSpans++;
michael@0:         }
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: SkPoint SkOpSegment::activeLeftTop(bool onlySortable, int* firstT) const {
michael@0:     SkASSERT(!done());
michael@0:     SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
michael@0:     int count = fTs.count();
michael@0:     // see if either end is not done since we want smaller Y of the pair
michael@0:     bool lastDone = true;
michael@0:     bool lastUnsortable = false;
michael@0:     double lastT = -1;
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         const SkOpSpan& span = fTs[index];
michael@0:         if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
michael@0:             goto next;
michael@0:         }
michael@0:         if (span.fDone && lastDone) {
michael@0:             goto next;
michael@0:         }
michael@0:         if (approximately_negative(span.fT - lastT)) {
michael@0:             goto next;
michael@0:         }
michael@0:         {
michael@0:             const SkPoint& xy = xyAtT(&span);
michael@0:             if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
michael@0:                 topPt = xy;
michael@0:                 if (firstT) {
michael@0:                     *firstT = index;
michael@0:                 }
michael@0:             }
michael@0:             if (fVerb != SkPath::kLine_Verb && !lastDone) {
michael@0:                 SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT, span.fT);
michael@0:                 if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
michael@0:                         && topPt.fX > curveTop.fX)) {
michael@0:                     topPt = curveTop;
michael@0:                     if (firstT) {
michael@0:                         *firstT = index;
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0:             lastT = span.fT;
michael@0:         }
michael@0: next:
michael@0:         lastDone = span.fDone;
michael@0:         lastUnsortable = span.fUnsortableEnd;
michael@0:     }
michael@0:     return topPt;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op) {
michael@0:     int sumMiWinding = updateWinding(endIndex, index);
michael@0:     int sumSuWinding = updateOppWinding(endIndex, index);
michael@0:     if (fOperand) {
michael@0:         SkTSwap<int>(sumMiWinding, sumSuWinding);
michael@0:     }
michael@0:     int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
michael@0:     return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding,
michael@0:             &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
michael@0:         int* sumMiWinding, int* sumSuWinding,
michael@0:         int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
michael@0:     setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
michael@0:             maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
michael@0:     bool miFrom;
michael@0:     bool miTo;
michael@0:     bool suFrom;
michael@0:     bool suTo;
michael@0:     if (operand()) {
michael@0:         miFrom = (*oppMaxWinding & xorMiMask) != 0;
michael@0:         miTo = (*oppSumWinding & xorMiMask) != 0;
michael@0:         suFrom = (*maxWinding & xorSuMask) != 0;
michael@0:         suTo = (*sumWinding & xorSuMask) != 0;
michael@0:     } else {
michael@0:         miFrom = (*maxWinding & xorMiMask) != 0;
michael@0:         miTo = (*sumWinding & xorMiMask) != 0;
michael@0:         suFrom = (*oppMaxWinding & xorSuMask) != 0;
michael@0:         suTo = (*oppSumWinding & xorSuMask) != 0;
michael@0:     }
michael@0:     bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
michael@0: #if DEBUG_ACTIVE_OP
michael@0:     SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__,
michael@0:             SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
michael@0: #endif
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::activeWinding(int index, int endIndex) {
michael@0:     int sumWinding = updateWinding(endIndex, index);
michael@0:     int maxWinding;
michael@0:     return activeWinding(index, endIndex, &maxWinding, &sumWinding);
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding) {
michael@0:     setUpWinding(index, endIndex, maxWinding, sumWinding);
michael@0:     bool from = *maxWinding != 0;
michael@0:     bool to = *sumWinding  != 0;
michael@0:     bool result = gUnaryActiveEdge[from][to];
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const {
michael@0:     SkASSERT(start != end);
michael@0:     SkOpAngle& angle = anglesPtr->push_back();
michael@0:     angle.set(this, start, end);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt,
michael@0:         SkOpSegment* other) {
michael@0:     int tIndex = -1;
michael@0:     int tCount = fTs.count();
michael@0:     int oIndex = -1;
michael@0:     int oCount = other->fTs.count();
michael@0:     do {
michael@0:         ++tIndex;
michael@0:     } while (startPt != fTs[tIndex].fPt && tIndex < tCount);
michael@0:     int tIndexStart = tIndex;
michael@0:     do {
michael@0:         ++oIndex;
michael@0:     } while (endPt != other->fTs[oIndex].fPt && oIndex < oCount);
michael@0:     int oIndexStart = oIndex;
michael@0:     const SkPoint* nextPt;
michael@0:     do {
michael@0:         nextPt = &fTs[++tIndex].fPt;
michael@0:         SkASSERT(fTs[tIndex].fT < 1 || startPt != *nextPt);
michael@0:     } while (startPt == *nextPt);
michael@0:     double nextT = fTs[tIndex].fT;
michael@0:     const SkPoint* oNextPt;
michael@0:     do {
michael@0:         oNextPt = &other->fTs[++oIndex].fPt;
michael@0:         SkASSERT(other->fTs[oIndex].fT < 1 || endPt != *oNextPt);
michael@0:     } while (endPt == *oNextPt);
michael@0:     double oNextT = other->fTs[oIndex].fT;
michael@0:     // at this point, spans before and after are at:
michael@0:     //  fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
michael@0:     // if tIndexStart == 0, no prior span
michael@0:     // if nextT == 1, no following span
michael@0: 
michael@0:     // advance the span with zero winding
michael@0:     // if the following span exists (not past the end, non-zero winding)
michael@0:     // connect the two edges
michael@0:     if (!fTs[tIndexStart].fWindValue) {
michael@0:         if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
michael@0: #if DEBUG_CONCIDENT
michael@0:             SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
michael@0:                     __FUNCTION__, fID, other->fID, tIndexStart - 1,
michael@0:                     fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
michael@0:                     xyAtT(tIndexStart).fY);
michael@0: #endif
michael@0:             addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false,
michael@0:                     fTs[tIndexStart].fPt);
michael@0:         }
michael@0:         if (nextT < 1 && fTs[tIndex].fWindValue) {
michael@0: #if DEBUG_CONCIDENT
michael@0:             SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
michael@0:                     __FUNCTION__, fID, other->fID, tIndex,
michael@0:                     fTs[tIndex].fT, xyAtT(tIndex).fX,
michael@0:                     xyAtT(tIndex).fY);
michael@0: #endif
michael@0:             addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
michael@0:         }
michael@0:     } else {
michael@0:         SkASSERT(!other->fTs[oIndexStart].fWindValue);
michael@0:         if (oIndexStart > 0 && other->fTs[oIndexStart - 1].fWindValue) {
michael@0: #if DEBUG_CONCIDENT
michael@0:             SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
michael@0:                     __FUNCTION__, fID, other->fID, oIndexStart - 1,
michael@0:                     other->fTs[oIndexStart].fT, other->xyAtT(oIndexStart).fX,
michael@0:                     other->xyAtT(oIndexStart).fY);
michael@0:             other->debugAddTPair(other->fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
michael@0: #endif
michael@0:         }
michael@0:         if (oNextT < 1 && other->fTs[oIndex].fWindValue) {
michael@0: #if DEBUG_CONCIDENT
michael@0:             SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
michael@0:                     __FUNCTION__, fID, other->fID, oIndex,
michael@0:                     other->fTs[oIndex].fT, other->xyAtT(oIndex).fX,
michael@0:                     other->xyAtT(oIndex).fY);
michael@0:             other->debugAddTPair(other->fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
michael@0: #endif
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt,
michael@0:         SkOpSegment* other) {
michael@0:     // walk this to startPt
michael@0:     // walk other to startPt
michael@0:     // if either is > 0, add a pointer to the other, copying adjacent winding
michael@0:     int tIndex = -1;
michael@0:     int oIndex = -1;
michael@0:     do {
michael@0:         ++tIndex;
michael@0:     } while (startPt != fTs[tIndex].fPt);
michael@0:     do {
michael@0:         ++oIndex;
michael@0:     } while (startPt != other->fTs[oIndex].fPt);
michael@0:     if (tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) {
michael@0:         addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt);
michael@0:     }
michael@0:     SkPoint nextPt = startPt;
michael@0:     do {
michael@0:         const SkPoint* workPt;
michael@0:         do {
michael@0:             workPt = &fTs[++tIndex].fPt;
michael@0:         } while (nextPt == *workPt);
michael@0:         do {
michael@0:             workPt = &other->fTs[++oIndex].fPt;
michael@0:         } while (nextPt == *workPt);
michael@0:         nextPt = *workPt;
michael@0:         double tStart = fTs[tIndex].fT;
michael@0:         double oStart = other->fTs[oIndex].fT;
michael@0:         if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) {
michael@0:             break;
michael@0:         }
michael@0:         addTPair(tStart, other, oStart, false, nextPt);
michael@0:     } while (endPt != nextPt);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
michael@0:     init(pts, SkPath::kCubic_Verb, operand, evenOdd);
michael@0:     fBounds.setCubicBounds(pts);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::addCurveTo(int start, int end, SkPathWriter* path, bool active) const {
michael@0:     SkPoint edge[4];
michael@0:     const SkPoint* ePtr;
michael@0:     int lastT = fTs.count() - 1;
michael@0:     if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
michael@0:         ePtr = fPts;
michael@0:     } else {
michael@0:     // OPTIMIZE? if not active, skip remainder and return xyAtT(end)
michael@0:         subDivide(start, end, edge);
michael@0:         ePtr = edge;
michael@0:     }
michael@0:     if (active) {
michael@0:         bool reverse = ePtr == fPts && start != 0;
michael@0:         if (reverse) {
michael@0:             path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
michael@0:             switch (fVerb) {
michael@0:                 case SkPath::kLine_Verb:
michael@0:                     path->deferredLine(ePtr[0]);
michael@0:                     break;
michael@0:                 case SkPath::kQuad_Verb:
michael@0:                     path->quadTo(ePtr[1], ePtr[0]);
michael@0:                     break;
michael@0:                 case SkPath::kCubic_Verb:
michael@0:                     path->cubicTo(ePtr[2], ePtr[1], ePtr[0]);
michael@0:                     break;
michael@0:                 default:
michael@0:                     SkASSERT(0);
michael@0:             }
michael@0:    //         return ePtr[0];
michael@0:        } else {
michael@0:             path->deferredMoveLine(ePtr[0]);
michael@0:             switch (fVerb) {
michael@0:                 case SkPath::kLine_Verb:
michael@0:                     path->deferredLine(ePtr[1]);
michael@0:                     break;
michael@0:                 case SkPath::kQuad_Verb:
michael@0:                     path->quadTo(ePtr[1], ePtr[2]);
michael@0:                     break;
michael@0:                 case SkPath::kCubic_Verb:
michael@0:                     path->cubicTo(ePtr[1], ePtr[2], ePtr[3]);
michael@0:                     break;
michael@0:                 default:
michael@0:                     SkASSERT(0);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:   //  return ePtr[SkPathOpsVerbToPoints(fVerb)];
michael@0: }
michael@0: 
michael@0: void SkOpSegment::addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
michael@0:     init(pts, SkPath::kLine_Verb, operand, evenOdd);
michael@0:     fBounds.set(pts, 2);
michael@0: }
michael@0: 
michael@0: // add 2 to edge or out of range values to get T extremes
michael@0: void SkOpSegment::addOtherT(int index, double otherT, int otherIndex) {
michael@0:     SkOpSpan& span = fTs[index];
michael@0:     if (precisely_zero(otherT)) {
michael@0:         otherT = 0;
michael@0:     } else if (precisely_equal(otherT, 1)) {
michael@0:         otherT = 1;
michael@0:     }
michael@0:     span.fOtherT = otherT;
michael@0:     span.fOtherIndex = otherIndex;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
michael@0:     init(pts, SkPath::kQuad_Verb, operand, evenOdd);
michael@0:     fBounds.setQuadBounds(pts);
michael@0: }
michael@0: 
michael@0:     // Defer all coincident edge processing until
michael@0:     // after normal intersections have been computed
michael@0: 
michael@0: // no need to be tricky; insert in normal T order
michael@0: // resolve overlapping ts when considering coincidence later
michael@0: 
michael@0:     // add non-coincident intersection. Resulting edges are sorted in T.
michael@0: int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) {
michael@0:     if (precisely_zero(newT)) {
michael@0:         newT = 0;
michael@0:     } else if (precisely_equal(newT, 1)) {
michael@0:         newT = 1;
michael@0:     }
michael@0:     // FIXME: in the pathological case where there is a ton of intercepts,
michael@0:     //  binary search?
michael@0:     int insertedAt = -1;
michael@0:     size_t tCount = fTs.count();
michael@0:     const SkPoint& firstPt = fPts[0];
michael@0:     const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
michael@0:     for (size_t index = 0; index < tCount; ++index) {
michael@0:         // OPTIMIZATION: if there are three or more identical Ts, then
michael@0:         // the fourth and following could be further insertion-sorted so
michael@0:         // that all the edges are clockwise or counterclockwise.
michael@0:         // This could later limit segment tests to the two adjacent
michael@0:         // neighbors, although it doesn't help with determining which
michael@0:         // circular direction to go in.
michael@0:         const SkOpSpan& span = fTs[index];
michael@0:         if (newT < span.fT) {
michael@0:             insertedAt = index;
michael@0:             break;
michael@0:         }
michael@0:         if (newT == span.fT) {
michael@0:             if (pt == span.fPt) {
michael@0:                 insertedAt = index;
michael@0:                 break;
michael@0:             }
michael@0:             if ((pt == firstPt && newT == 0) || (span.fPt == lastPt && newT == 1)) {
michael@0:                 insertedAt = index;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     SkOpSpan* span;
michael@0:     if (insertedAt >= 0) {
michael@0:         span = fTs.insert(insertedAt);
michael@0:     } else {
michael@0:         insertedAt = tCount;
michael@0:         span = fTs.append();
michael@0:     }
michael@0:     span->fT = newT;
michael@0:     span->fOther = other;
michael@0:     span->fPt = pt;
michael@0: #if 0
michael@0:     // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
michael@0:     SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
michael@0:             && approximately_equal(xyAtT(newT).fY, pt.fY));
michael@0: #endif
michael@0:     span->fWindSum = SK_MinS32;
michael@0:     span->fOppSum = SK_MinS32;
michael@0:     span->fWindValue = 1;
michael@0:     span->fOppValue = 0;
michael@0:     span->fSmall = false;
michael@0:     span->fTiny = false;
michael@0:     span->fLoop = false;
michael@0:     if ((span->fDone = newT == 1)) {
michael@0:         ++fDoneSpans;
michael@0:     }
michael@0:     span->fUnsortableStart = false;
michael@0:     span->fUnsortableEnd = false;
michael@0:     int less = -1;
michael@0:     while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, span->fPt)) {
michael@0:         if (span[less].fDone) {
michael@0:             break;
michael@0:         }
michael@0:         double tInterval = newT - span[less].fT;
michael@0:         if (precisely_negative(tInterval)) {
michael@0:             break;
michael@0:         }
michael@0:         if (fVerb == SkPath::kCubic_Verb) {
michael@0:             double tMid = newT - tInterval / 2;
michael@0:             SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
michael@0:             if (!midPt.approximatelyEqual(xyAtT(span))) {
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:         span[less].fSmall = true;
michael@0:         bool tiny = span[less].fPt == span->fPt;
michael@0:         span[less].fTiny = tiny;
michael@0:         span[less].fDone = true;
michael@0:         if (approximately_negative(newT - span[less].fT) && tiny) {
michael@0:             if (approximately_greater_than_one(newT)) {
michael@0:                 SkASSERT(&span[less] - fTs.begin() < fTs.count());
michael@0:                 span[less].fUnsortableStart = true;
michael@0:                 if (&span[less - 1] - fTs.begin() >= 0) {
michael@0:                     span[less - 1].fUnsortableEnd = true;
michael@0:                 }
michael@0:             }
michael@0:             if (approximately_less_than_zero(span[less].fT)) {
michael@0:                 SkASSERT(&span[less + 1] - fTs.begin() < fTs.count());
michael@0:                 SkASSERT(&span[less] - fTs.begin() >= 0);
michael@0:                 span[less + 1].fUnsortableStart = true;
michael@0:                 span[less].fUnsortableEnd = true;
michael@0:             }
michael@0:         }
michael@0:         ++fDoneSpans;
michael@0:         --less;
michael@0:     }
michael@0:     int more = 1;
michael@0:     while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, span->fPt)) {
michael@0:         if (span[more - 1].fDone) {
michael@0:             break;
michael@0:         }
michael@0:         double tEndInterval = span[more].fT - newT;
michael@0:         if (precisely_negative(tEndInterval)) {
michael@0:             if ((span->fTiny = span[more].fTiny)) {
michael@0:                 span->fDone = true;
michael@0:                 ++fDoneSpans;
michael@0:             }
michael@0:             break;
michael@0:         }
michael@0:         if (fVerb == SkPath::kCubic_Verb) {
michael@0:             double tMid = newT - tEndInterval / 2;
michael@0:             SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
michael@0:             if (!midEndPt.approximatelyEqual(xyAtT(span))) {
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:         span[more - 1].fSmall = true;
michael@0:         bool tiny = span[more].fPt == span->fPt;
michael@0:         span[more - 1].fTiny = tiny;
michael@0:         span[more - 1].fDone = true;
michael@0:         if (approximately_negative(span[more].fT - newT) && tiny) {
michael@0:             if (approximately_greater_than_one(span[more].fT)) {
michael@0:                 span[more + 1].fUnsortableStart = true;
michael@0:                 span[more].fUnsortableEnd = true;
michael@0:             }
michael@0:             if (approximately_less_than_zero(newT)) {
michael@0:                 span[more].fUnsortableStart = true;
michael@0:                 span[more - 1].fUnsortableEnd = true;
michael@0:             }
michael@0:         }
michael@0:         ++fDoneSpans;
michael@0:         ++more;
michael@0:     }
michael@0:     return insertedAt;
michael@0: }
michael@0: 
michael@0: // set spans from start to end to decrement by one
michael@0: // note this walks other backwards
michael@0: // FIXME: there's probably an edge case that can be constructed where
michael@0: // two span in one segment are separated by float epsilon on one span but
michael@0: // not the other, if one segment is very small. For this
michael@0: // case the counts asserted below may or may not be enough to separate the
michael@0: // spans. Even if the counts work out, what if the spans aren't correctly
michael@0: // sorted? It feels better in such a case to match the span's other span
michael@0: // pointer since both coincident segments must contain the same spans.
michael@0: // FIXME? It seems that decrementing by one will fail for complex paths that
michael@0: // have three or more coincident edges. Shouldn't this subtract the difference
michael@0: // between the winding values?
michael@0: /*                                      |-->                           |-->
michael@0: this     0>>>>1>>>>2>>>>3>>>4      0>>>>1>>>>2>>>>3>>>4      0>>>>1>>>>2>>>>3>>>4
michael@0: other         2<<<<1<<<<0               2<<<<1<<<<0               2<<<<1<<<<0
michael@0:               ^         ^                 <--|                           <--|
michael@0:            startPt    endPt        test/oTest first pos      test/oTest final pos
michael@0: */
michael@0: void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) {
michael@0:     bool binary = fOperand != other->fOperand;
michael@0:     int index = 0;
michael@0:     while (startPt != fTs[index].fPt) {
michael@0:         SkASSERT(index < fTs.count());
michael@0:         ++index;
michael@0:     }
michael@0:     while (index > 0 && fTs[index].fT == fTs[index - 1].fT) {
michael@0:         --index;
michael@0:     }
michael@0:     int oIndex = other->fTs.count();
michael@0:     while (startPt != other->fTs[--oIndex].fPt) {  // look for startPt match
michael@0:         SkASSERT(oIndex > 0);
michael@0:     }
michael@0:     double oStartT = other->fTs[oIndex].fT;
michael@0:     // look for first point beyond match
michael@0:     while (startPt == other->fTs[--oIndex].fPt || oStartT == other->fTs[oIndex].fT) {
michael@0:         SkASSERT(oIndex > 0);
michael@0:     }
michael@0:     SkOpSpan* test = &fTs[index];
michael@0:     SkOpSpan* oTest = &other->fTs[oIndex];
michael@0:     SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
michael@0:     SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
michael@0:     do {
michael@0:         SkASSERT(test->fT < 1);
michael@0:         SkASSERT(oTest->fT < 1);
michael@0:         bool decrement = test->fWindValue && oTest->fWindValue;
michael@0:         bool track = test->fWindValue || oTest->fWindValue;
michael@0:         bool bigger = test->fWindValue >= oTest->fWindValue;
michael@0:         const SkPoint& testPt = test->fPt;
michael@0:         double testT = test->fT;
michael@0:         const SkPoint& oTestPt = oTest->fPt;
michael@0:         double oTestT = oTest->fT;
michael@0:         do {
michael@0:             if (decrement) {
michael@0:                 if (binary && bigger) {
michael@0:                     test->fOppValue--;
michael@0:                 } else {
michael@0:                     decrementSpan(test);
michael@0:                 }
michael@0:             } else if (track) {
michael@0:                 TrackOutsidePair(&outsidePts, testPt, oTestPt);
michael@0:             }
michael@0:             SkASSERT(index < fTs.count() - 1);
michael@0:             test = &fTs[++index];
michael@0:         } while (testPt == test->fPt || testT == test->fT);
michael@0:         SkDEBUGCODE(int originalWindValue = oTest->fWindValue);
michael@0:         do {
michael@0:             SkASSERT(oTest->fT < 1);
michael@0:             SkASSERT(originalWindValue == oTest->fWindValue);
michael@0:             if (decrement) {
michael@0:                 if (binary && !bigger) {
michael@0:                     oTest->fOppValue--;
michael@0:                 } else {
michael@0:                     other->decrementSpan(oTest);
michael@0:                 }
michael@0:             } else if (track) {
michael@0:                 TrackOutsidePair(&oOutsidePts, oTestPt, testPt);
michael@0:             }
michael@0:             if (!oIndex) {
michael@0:                 break;
michael@0:             }
michael@0:             oTest = &other->fTs[--oIndex];
michael@0:         } while (oTestPt == oTest->fPt || oTestT == oTest->fT);
michael@0:     } while (endPt != test->fPt && test->fT < 1);
michael@0:     // FIXME: determine if canceled edges need outside ts added
michael@0:     int outCount = outsidePts.count();
michael@0:     if (!done() && outCount) {
michael@0:         addCancelOutsides(outsidePts[0], outsidePts[1], other);
michael@0:         if (outCount > 2) {
michael@0:             addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other);
michael@0:         }
michael@0:     }
michael@0:     if (!other->done() && oOutsidePts.count()) {
michael@0:         other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this);
michael@0:     }
michael@0: }
michael@0: 
michael@0: int SkOpSegment::addSelfT(SkOpSegment* other, const SkPoint& pt, double newT) {
michael@0:     // if the tail nearly intersects itself but not quite, the caller records this separately
michael@0:     int result = addT(other, pt, newT);
michael@0:     SkOpSpan* span = &fTs[result];
michael@0:     span->fLoop = true;
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr,
michael@0:         SkTArray<SkPoint, true>* outsideTs) {
michael@0:     int index = *indexPtr;
michael@0:     int oWindValue = oTest.fWindValue;
michael@0:     int oOppValue = oTest.fOppValue;
michael@0:     if (binary) {
michael@0:         SkTSwap<int>(oWindValue, oOppValue);
michael@0:     }
michael@0:     SkOpSpan* const test = &fTs[index];
michael@0:     SkOpSpan* end = test;
michael@0:     const SkPoint& oStartPt = oTest.fPt;
michael@0:     do {
michael@0:         if (bumpSpan(end, oWindValue, oOppValue)) {
michael@0:             TrackOutside(outsideTs, oStartPt);
michael@0:         }
michael@0:         end = &fTs[++index];
michael@0:     } while ((end->fPt == test->fPt || end->fT == test->fT) && end->fT < 1);
michael@0:     *indexPtr = index;
michael@0: }
michael@0: 
michael@0: // because of the order in which coincidences are resolved, this and other
michael@0: // may not have the same intermediate points. Compute the corresponding
michael@0: // intermediate T values (using this as the master, other as the follower)
michael@0: // and walk other conditionally -- hoping that it catches up in the end
michael@0: void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
michael@0:         SkTArray<SkPoint, true>* oOutsidePts) {
michael@0:     int oIndex = *oIndexPtr;
michael@0:     SkOpSpan* const oTest = &fTs[oIndex];
michael@0:     SkOpSpan* oEnd = oTest;
michael@0:     const SkPoint& startPt = test.fPt;
michael@0:     const SkPoint& oStartPt = oTest->fPt;
michael@0:     double oStartT = oTest->fT;
michael@0:     if (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
michael@0:         TrackOutside(oOutsidePts, startPt);
michael@0:     }
michael@0:     while (oStartPt == oEnd->fPt || oStartT == oEnd->fT) {
michael@0:         zeroSpan(oEnd);
michael@0:         oEnd = &fTs[++oIndex];
michael@0:     }
michael@0:     *oIndexPtr = oIndex;
michael@0: }
michael@0: 
michael@0: // FIXME: need to test this case:
michael@0: // contourA has two segments that are coincident
michael@0: // contourB has two segments that are coincident in the same place
michael@0: // each ends up with +2/0 pairs for winding count
michael@0: // since logic below doesn't transfer count (only increments/decrements) can this be
michael@0: // resolved to +4/0 ?
michael@0: 
michael@0: // set spans from start to end to increment the greater by one and decrement
michael@0: // the lesser
michael@0: void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT,
michael@0:         SkOpSegment* other) {
michael@0:     bool binary = fOperand != other->fOperand;
michael@0:     int index = 0;
michael@0:     while (startPt != fTs[index].fPt) {
michael@0:         SkASSERT(index < fTs.count());
michael@0:         ++index;
michael@0:     }
michael@0:     double startT = fTs[index].fT;
michael@0:     while (index > 0 && fTs[index - 1].fT == startT) {
michael@0:         --index;
michael@0:     }
michael@0:     int oIndex = 0;
michael@0:     while (startPt != other->fTs[oIndex].fPt) {
michael@0:         SkASSERT(oIndex < other->fTs.count());
michael@0:         ++oIndex;
michael@0:     }
michael@0:     double oStartT = other->fTs[oIndex].fT;
michael@0:     while (oIndex > 0 && other->fTs[oIndex - 1].fT == oStartT) {
michael@0:         --oIndex;
michael@0:     }
michael@0:     SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
michael@0:     SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
michael@0:     SkOpSpan* test = &fTs[index];
michael@0:     const SkPoint* testPt = &test->fPt;
michael@0:     double testT = test->fT;
michael@0:     SkOpSpan* oTest = &other->fTs[oIndex];
michael@0:     const SkPoint* oTestPt = &oTest->fPt;
michael@0:     SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
michael@0:     do {
michael@0:         SkASSERT(test->fT < 1);
michael@0:         SkASSERT(oTest->fT < 1);
michael@0: #if 0
michael@0:         if (test->fDone || oTest->fDone) {
michael@0: #else  // consolidate the winding count even if done
michael@0:         if ((test->fWindValue == 0 && test->fOppValue == 0)
michael@0:                 || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
michael@0: #endif
michael@0:             SkDEBUGCODE(int firstWind = test->fWindValue);
michael@0:             SkDEBUGCODE(int firstOpp = test->fOppValue);
michael@0:             do {
michael@0:                 SkASSERT(firstWind == fTs[index].fWindValue);
michael@0:                 SkASSERT(firstOpp == fTs[index].fOppValue);
michael@0:                 ++index;
michael@0:                 SkASSERT(index < fTs.count());
michael@0:             } while (*testPt == fTs[index].fPt);
michael@0:             SkDEBUGCODE(firstWind = oTest->fWindValue);
michael@0:             SkDEBUGCODE(firstOpp = oTest->fOppValue);
michael@0:             do {
michael@0:                 SkASSERT(firstWind == other->fTs[oIndex].fWindValue);
michael@0:                 SkASSERT(firstOpp == other->fTs[oIndex].fOppValue);
michael@0:                 ++oIndex;
michael@0:                 SkASSERT(oIndex < other->fTs.count());
michael@0:             } while (*oTestPt == other->fTs[oIndex].fPt);
michael@0:         } else {
michael@0:             if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
michael@0:                 bumpCoincidentThis(*oTest, binary, &index, &outsidePts);
michael@0:                 other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
michael@0:             } else {
michael@0:                 other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
michael@0:                 bumpCoincidentOther(*oTest, &index, &outsidePts);
michael@0:             }
michael@0:         }
michael@0:         test = &fTs[index];
michael@0:         testPt = &test->fPt;
michael@0:         testT = test->fT;
michael@0:         if (endPt == *testPt || endT == testT) {
michael@0:             break;
michael@0:         }
michael@0:         oTest = &other->fTs[oIndex];
michael@0:         oTestPt = &oTest->fPt;
michael@0:         SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
michael@0:     } while (endPt != *oTestPt);
michael@0:     if (endPt != *testPt && endT != testT) {  // in rare cases, one may have ended before the other
michael@0:         int lastWind = test[-1].fWindValue;
michael@0:         int lastOpp = test[-1].fOppValue;
michael@0:         bool zero = lastWind == 0 && lastOpp == 0;
michael@0:         do {
michael@0:             if (test->fWindValue || test->fOppValue) {
michael@0:                 test->fWindValue = lastWind;
michael@0:                 test->fOppValue = lastOpp;
michael@0:                 if (zero) {
michael@0:                     test->fDone = true;
michael@0:                     ++fDoneSpans;
michael@0:                 }
michael@0:             }
michael@0:             test = &fTs[++index];
michael@0:             testPt = &test->fPt;
michael@0:         } while (endPt != *testPt);
michael@0:    }
michael@0:     int outCount = outsidePts.count();
michael@0:     if (!done() && outCount) {
michael@0:         addCoinOutsides(outsidePts[0], endPt, other);
michael@0:     }
michael@0:     if (!other->done() && oOutsidePts.count()) {
michael@0:         other->addCoinOutsides(oOutsidePts[0], endPt, this);
michael@0:     }
michael@0: }
michael@0: 
michael@0: // FIXME: this doesn't prevent the same span from being added twice
michael@0: // fix in caller, SkASSERT here?
michael@0: void SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
michael@0:                            const SkPoint& pt) {
michael@0:     int tCount = fTs.count();
michael@0:     for (int tIndex = 0; tIndex < tCount; ++tIndex) {
michael@0:         const SkOpSpan& span = fTs[tIndex];
michael@0:         if (!approximately_negative(span.fT - t)) {
michael@0:             break;
michael@0:         }
michael@0:         if (approximately_negative(span.fT - t) && span.fOther == other
michael@0:                 && approximately_equal(span.fOtherT, otherT)) {
michael@0: #if DEBUG_ADD_T_PAIR
michael@0:             SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
michael@0:                     __FUNCTION__, fID, t, other->fID, otherT);
michael@0: #endif
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0: #if DEBUG_ADD_T_PAIR
michael@0:     SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
michael@0:             __FUNCTION__, fID, t, other->fID, otherT);
michael@0: #endif
michael@0:     int insertedAt = addT(other, pt, t);
michael@0:     int otherInsertedAt = other->addT(this, pt, otherT);
michael@0:     addOtherT(insertedAt, otherT, otherInsertedAt);
michael@0:     other->addOtherT(otherInsertedAt, t, insertedAt);
michael@0:     matchWindingValue(insertedAt, t, borrowWind);
michael@0:     other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const {
michael@0:     // add edge leading into junction
michael@0:     int min = SkMin32(end, start);
michael@0:     if (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0) {
michael@0:         addAngle(angles, end, start);
michael@0:     }
michael@0:     // add edge leading away from junction
michael@0:     int step = SkSign32(end - start);
michael@0:     int tIndex = nextExactSpan(end, step);
michael@0:     min = SkMin32(end, tIndex);
michael@0:     if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0)) {
michael@0:         addAngle(angles, end, tIndex);
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
michael@0:     const SkPoint midPt = ptAtT(midT);
michael@0:     SkPathOpsBounds bounds;
michael@0:     bounds.set(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
michael@0:     bounds.sort();
michael@0:     return bounds.almostContains(midPt);
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const {
michael@0:     if (lesser > greater) {
michael@0:         SkTSwap<int>(lesser, greater);
michael@0:     }
michael@0:     return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
michael@0: }
michael@0: 
michael@0: // note that this follows the same logic flow as active angle
michael@0: bool SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool allowOpp) const {
michael@0:     double referenceT = fTs[index].fT;
michael@0:     const SkPoint& referencePt = fTs[index].fPt;
michael@0:     int lesser = index;
michael@0:     while (--lesser >= 0 && (allowOpp || fTs[lesser].fOther->fOperand == fOperand)
michael@0:             && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
michael@0:         buildAnglesInner(lesser, angles);
michael@0:     }
michael@0:     do {
michael@0:         buildAnglesInner(index, angles);
michael@0:         if (++index == fTs.count()) {
michael@0:             break;
michael@0:         }
michael@0:         if (!allowOpp && fTs[index].fOther->fOperand != fOperand) {
michael@0:             break;
michael@0:         }
michael@0:         if (fTs[index - 1].fTiny) {
michael@0:             referenceT = fTs[index].fT;
michael@0:             continue;
michael@0:         }
michael@0:         if (!precisely_negative(fTs[index].fT - referenceT) && fTs[index].fPt == referencePt) {
michael@0:             // FIXME
michael@0:             // testQuad8 generates the wrong output unless false is returned here. Other tests will
michael@0:             // take this path although they aren't required to. This means that many go much slower
michael@0:             // because of this sort fail.
michael@0:  //           SkDebugf("!!!\n");
michael@0:             return false;
michael@0:         }
michael@0:     } while (precisely_negative(fTs[index].fT - referenceT));
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const {
michael@0:     const SkOpSpan* span = &fTs[index];
michael@0:     SkOpSegment* other = span->fOther;
michael@0: // if there is only one live crossing, and no coincidence, continue
michael@0: // in the same direction
michael@0: // if there is coincidence, the only choice may be to reverse direction
michael@0:     // find edge on either side of intersection
michael@0:     int oIndex = span->fOtherIndex;
michael@0:     // if done == -1, prior span has already been processed
michael@0:     int step = 1;
michael@0:     int next = other->nextExactSpan(oIndex, step);
michael@0:    if (next < 0) {
michael@0:         step = -step;
michael@0:         next = other->nextExactSpan(oIndex, step);
michael@0:     }
michael@0:     // add candidate into and away from junction
michael@0:     other->addTwoAngles(next, oIndex, angles);
michael@0: }
michael@0: 
michael@0: int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
michael@0:         SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted) {
michael@0:     addTwoAngles(startIndex, endIndex, angles);
michael@0:     if (!buildAngles(endIndex, angles, includeType == SkOpAngle::kBinaryOpp)) {
michael@0:         return SK_NaN32;
michael@0:     }
michael@0:     int angleCount = angles->count();
michael@0:     // abort early before sorting if an unsortable (not an unorderable) angle is found
michael@0:     if (includeType != SkOpAngle::kUnaryXor) {
michael@0:         int firstIndex = -1;
michael@0:         while (++firstIndex < angleCount) {
michael@0:             const SkOpAngle& angle = (*angles)[firstIndex];
michael@0:             if (angle.segment()->windSum(&angle) != SK_MinS32) {
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:         if (firstIndex == angleCount) {
michael@0:             return SK_MinS32;
michael@0:         }
michael@0:     }
michael@0:     bool sortable = SortAngles2(*angles, sorted);
michael@0: #if DEBUG_SORT_RAW
michael@0:     if (sorted->count() > 0) {
michael@0:         (*sorted)[0]->segment()->debugShowSort(__FUNCTION__, *sorted, 0, 0, 0, sortable);
michael@0:     }
michael@0: #endif
michael@0:     if (!sortable) {
michael@0:         return SK_NaN32;
michael@0:     }
michael@0:     if (includeType == SkOpAngle::kUnaryXor) {
michael@0:         return SK_MinS32;
michael@0:     }
michael@0:     // if all angles have a computed winding,
michael@0:     //  or if no adjacent angles are orderable,
michael@0:     //  or if adjacent orderable angles have no computed winding,
michael@0:     //  there's nothing to do
michael@0:     // if two orderable angles are adjacent, and one has winding computed, transfer to the other
michael@0:     const SkOpAngle* baseAngle = NULL;
michael@0:     int last = angleCount;
michael@0:     int finalInitialOrderable = -1;
michael@0:     bool tryReverse = false;
michael@0:     // look for counterclockwise transfers
michael@0:     do {
michael@0:         int index = 0;
michael@0:         do {
michael@0:             SkOpAngle* testAngle = (*sorted)[index];
michael@0:             int testWinding = testAngle->segment()->windSum(testAngle);
michael@0:             if (SK_MinS32 != testWinding && !testAngle->unorderable()) {
michael@0:                 baseAngle = testAngle;
michael@0:                 continue;
michael@0:             }
michael@0:             if (testAngle->unorderable()) {
michael@0:                 baseAngle = NULL;
michael@0:                 tryReverse = true;
michael@0:                 continue;
michael@0:             }
michael@0:             if (baseAngle) {
michael@0:                 ComputeOneSum(baseAngle, testAngle, includeType);
michael@0:                 baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
michael@0:                         : NULL;
michael@0:                 tryReverse |= !baseAngle;
michael@0:                 continue;
michael@0:             }
michael@0:             if (finalInitialOrderable + 1 == index) {
michael@0:                 finalInitialOrderable = index;
michael@0:             }
michael@0:         } while (++index != last);
michael@0:         if (finalInitialOrderable < 0) {
michael@0:             break;
michael@0:         }
michael@0:         last = finalInitialOrderable + 1;
michael@0:         finalInitialOrderable = -2;  // make this always negative the second time through
michael@0:     } while (baseAngle);
michael@0:     if (tryReverse) {
michael@0:         baseAngle = NULL;
michael@0:         last = 0;
michael@0:         finalInitialOrderable = angleCount;
michael@0:         do {
michael@0:             int index = angleCount;
michael@0:             while (--index >= last) {
michael@0:                 SkOpAngle* testAngle = (*sorted)[index];
michael@0:                 int testWinding = testAngle->segment()->windSum(testAngle);
michael@0:                 if (SK_MinS32 != testWinding) {
michael@0:                     baseAngle = testAngle;
michael@0:                     continue;
michael@0:                 }
michael@0:                 if (testAngle->unorderable()) {
michael@0:                     baseAngle = NULL;
michael@0:                     continue;
michael@0:                 }
michael@0:                 if (baseAngle) {
michael@0:                     ComputeOneSumReverse(baseAngle, testAngle, includeType);
michael@0:                     baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
michael@0:                             : NULL;
michael@0:                     continue;
michael@0:                 }
michael@0:                 if (finalInitialOrderable - 1 == index) {
michael@0:                     finalInitialOrderable = index;
michael@0:                 }
michael@0:             }
michael@0:             if (finalInitialOrderable >= angleCount) {
michael@0:                 break;
michael@0:             }
michael@0:             last = finalInitialOrderable;
michael@0:             finalInitialOrderable = angleCount + 1;  // make this inactive 2nd time through
michael@0:         } while (baseAngle);
michael@0:     }
michael@0:     int minIndex = SkMin32(startIndex, endIndex);
michael@0:     return windSum(minIndex);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
michael@0:         SkOpAngle::IncludeType includeType) {
michael@0:     const SkOpSegment* baseSegment = baseAngle->segment();
michael@0:     int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
michael@0:     int sumSuWinding;
michael@0:     bool binary = includeType >= SkOpAngle::kBinarySingle;
michael@0:     if (binary) {
michael@0:         sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
michael@0:         if (baseSegment->operand()) {
michael@0:             SkTSwap<int>(sumMiWinding, sumSuWinding);
michael@0:         }
michael@0:     }
michael@0:     SkOpSegment* nextSegment = nextAngle->segment();
michael@0:     int maxWinding, sumWinding;
michael@0:     SkOpSpan* last;
michael@0:     if (binary) {
michael@0:         int oppMaxWinding, oppSumWinding;
michael@0:         nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
michael@0:                 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
michael@0:         last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
michael@0:                 nextAngle);
michael@0:     } else {
michael@0:         nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
michael@0:                 &maxWinding, &sumWinding);
michael@0:         last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
michael@0:     }
michael@0:     nextAngle->setLastMarked(last);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
michael@0:         SkOpAngle::IncludeType includeType) {
michael@0:     const SkOpSegment* baseSegment = baseAngle->segment();
michael@0:     int sumMiWinding = baseSegment->updateWinding(baseAngle);
michael@0:     int sumSuWinding;
michael@0:     bool binary = includeType >= SkOpAngle::kBinarySingle;
michael@0:     if (binary) {
michael@0:         sumSuWinding = baseSegment->updateOppWinding(baseAngle);
michael@0:         if (baseSegment->operand()) {
michael@0:             SkTSwap<int>(sumMiWinding, sumSuWinding);
michael@0:         }
michael@0:     }
michael@0:     SkOpSegment* nextSegment = nextAngle->segment();
michael@0:     int maxWinding, sumWinding;
michael@0:     SkOpSpan* last;
michael@0:     if (binary) {
michael@0:         int oppMaxWinding, oppSumWinding;
michael@0:         nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
michael@0:                 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
michael@0:         last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
michael@0:                 nextAngle);
michael@0:     } else {
michael@0:         nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
michael@0:                 &maxWinding, &sumWinding);
michael@0:         last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle);
michael@0:     }
michael@0:     nextAngle->setLastMarked(last);
michael@0: }
michael@0: 
michael@0: int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
michael@0:                               bool* hitSomething, double mid, bool opp, bool current) const {
michael@0:     SkScalar bottom = fBounds.fBottom;
michael@0:     int bestTIndex = -1;
michael@0:     if (bottom <= *bestY) {
michael@0:         return bestTIndex;
michael@0:     }
michael@0:     SkScalar top = fBounds.fTop;
michael@0:     if (top >= basePt.fY) {
michael@0:         return bestTIndex;
michael@0:     }
michael@0:     if (fBounds.fLeft > basePt.fX) {
michael@0:         return bestTIndex;
michael@0:     }
michael@0:     if (fBounds.fRight < basePt.fX) {
michael@0:         return bestTIndex;
michael@0:     }
michael@0:     if (fBounds.fLeft == fBounds.fRight) {
michael@0:         // if vertical, and directly above test point, wait for another one
michael@0:         return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
michael@0:     }
michael@0:     // intersect ray starting at basePt with edge
michael@0:     SkIntersections intersections;
michael@0:     // OPTIMIZE: use specialty function that intersects ray with curve,
michael@0:     // returning t values only for curve (we don't care about t on ray)
michael@0:     intersections.allowNear(false);
michael@0:     int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
michael@0:             (fPts, top, bottom, basePt.fX, false);
michael@0:     if (pts == 0 || (current && pts == 1)) {
michael@0:         return bestTIndex;
michael@0:     }
michael@0:     if (current) {
michael@0:         SkASSERT(pts > 1);
michael@0:         int closestIdx = 0;
michael@0:         double closest = fabs(intersections[0][0] - mid);
michael@0:         for (int idx = 1; idx < pts; ++idx) {
michael@0:             double test = fabs(intersections[0][idx] - mid);
michael@0:             if (closest > test) {
michael@0:                 closestIdx = idx;
michael@0:                 closest = test;
michael@0:             }
michael@0:         }
michael@0:         intersections.quickRemoveOne(closestIdx, --pts);
michael@0:     }
michael@0:     double bestT = -1;
michael@0:     for (int index = 0; index < pts; ++index) {
michael@0:         double foundT = intersections[0][index];
michael@0:         if (approximately_less_than_zero(foundT)
michael@0:                     || approximately_greater_than_one(foundT)) {
michael@0:             continue;
michael@0:         }
michael@0:         SkScalar testY = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fY;
michael@0:         if (approximately_negative(testY - *bestY)
michael@0:                 || approximately_negative(basePt.fY - testY)) {
michael@0:             continue;
michael@0:         }
michael@0:         if (pts > 1 && fVerb == SkPath::kLine_Verb) {
michael@0:             return SK_MinS32;  // if the intersection is edge on, wait for another one
michael@0:         }
michael@0:         if (fVerb > SkPath::kLine_Verb) {
michael@0:             SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, foundT).fX;
michael@0:             if (approximately_zero(dx)) {
michael@0:                 return SK_MinS32;  // hit vertical, wait for another one
michael@0:             }
michael@0:         }
michael@0:         *bestY = testY;
michael@0:         bestT = foundT;
michael@0:     }
michael@0:     if (bestT < 0) {
michael@0:         return bestTIndex;
michael@0:     }
michael@0:     SkASSERT(bestT >= 0);
michael@0:     SkASSERT(bestT <= 1);
michael@0:     int start;
michael@0:     int end = 0;
michael@0:     do {
michael@0:         start = end;
michael@0:         end = nextSpan(start, 1);
michael@0:     } while (fTs[end].fT < bestT);
michael@0:     // FIXME: see next candidate for a better pattern to find the next start/end pair
michael@0:     while (start + 1 < end && fTs[start].fDone) {
michael@0:         ++start;
michael@0:     }
michael@0:     if (!isCanceled(start)) {
michael@0:         *hitT = bestT;
michael@0:         bestTIndex = start;
michael@0:         *hitSomething = true;
michael@0:     }
michael@0:     return bestTIndex;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::decrementSpan(SkOpSpan* span) {
michael@0:     SkASSERT(span->fWindValue > 0);
michael@0:     if (--(span->fWindValue) == 0) {
michael@0:         if (!span->fOppValue && !span->fDone) {
michael@0:             span->fDone = true;
michael@0:             ++fDoneSpans;
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
michael@0:     SkASSERT(!span->fDone || span->fTiny || span->fSmall);
michael@0:     span->fWindValue += windDelta;
michael@0:     SkASSERT(span->fWindValue >= 0);
michael@0:     span->fOppValue += oppDelta;
michael@0:     SkASSERT(span->fOppValue >= 0);
michael@0:     if (fXor) {
michael@0:         span->fWindValue &= 1;
michael@0:     }
michael@0:     if (fOppXor) {
michael@0:         span->fOppValue &= 1;
michael@0:     }
michael@0:     if (!span->fWindValue && !span->fOppValue) {
michael@0:         span->fDone = true;
michael@0:         ++fDoneSpans;
michael@0:         return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: // look to see if the curve end intersects an intermediary that intersects the other
michael@0: void SkOpSegment::checkEnds() {
michael@0:     debugValidate();
michael@0:     SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
michael@0:     int count = fTs.count();
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         const SkOpSpan& span = fTs[index];
michael@0:         double otherT = span.fOtherT;
michael@0:         if (otherT != 0 && otherT != 1) { // only check ends
michael@0:             continue;
michael@0:         }
michael@0:         const SkOpSegment* other = span.fOther;
michael@0:         // peek start/last describe the range of spans that match the other t of this span
michael@0:         int peekStart = span.fOtherIndex;
michael@0:         while (--peekStart >= 0 && other->fTs[peekStart].fT == otherT)
michael@0:             ;
michael@0:         int otherCount = other->fTs.count();
michael@0:         int peekLast = span.fOtherIndex;
michael@0:         while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT)
michael@0:             ;
michael@0:         if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do
michael@0:             continue;
michael@0:         }
michael@0:         // t start/last describe the range of spans that match the t of this span
michael@0:         double t = span.fT;
michael@0:         double tBottom = -1;
michael@0:         int tStart = -1;
michael@0:         int tLast = count;
michael@0:         bool lastSmall = false;
michael@0:         double afterT = t;
michael@0:         for (int inner = 0; inner < count; ++inner) {
michael@0:             double innerT = fTs[inner].fT;
michael@0:             if (innerT <= t && innerT > tBottom) {
michael@0:                 if (innerT < t || !lastSmall) {
michael@0:                     tStart = inner - 1;
michael@0:                 }
michael@0:                 tBottom = innerT;
michael@0:             }
michael@0:             if (innerT > afterT) {
michael@0:                 if (t == afterT && lastSmall) {
michael@0:                     afterT = innerT;
michael@0:                 } else {
michael@0:                     tLast = inner;
michael@0:                     break;
michael@0:                 }
michael@0:             }
michael@0:             lastSmall = innerT <= t ? fTs[inner].fSmall : false;
michael@0:         }
michael@0:         for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
michael@0:             if (peekIndex == span.fOtherIndex) {  // skip the other span pointed to by this span
michael@0:                 continue;
michael@0:             }
michael@0:             const SkOpSpan& peekSpan = other->fTs[peekIndex];
michael@0:             SkOpSegment* match = peekSpan.fOther;
michael@0:             if (match->done()) {
michael@0:                 continue;  // if the edge has already been eaten (likely coincidence), ignore it
michael@0:             }
michael@0:             const double matchT = peekSpan.fOtherT;
michael@0:             // see if any of the spans match the other spans
michael@0:             for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) {
michael@0:                 const SkOpSpan& tSpan = fTs[tIndex];
michael@0:                 if (tSpan.fOther == match) {
michael@0:                     if (tSpan.fOtherT == matchT) {
michael@0:                         goto nextPeekIndex;
michael@0:                     }
michael@0:                     double midT = (tSpan.fOtherT + matchT) / 2;
michael@0:                     if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
michael@0:                         goto nextPeekIndex;
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0:             if (missingSpans.count() > 0) {
michael@0:                 const MissingSpan& lastMissing = missingSpans.back();
michael@0:                 if (lastMissing.fT == t
michael@0:                         && lastMissing.fOther == match
michael@0:                         && lastMissing.fOtherT == matchT) {
michael@0:                     SkASSERT(lastMissing.fPt == peekSpan.fPt);
michael@0:                     continue;
michael@0:                 }
michael@0:             }
michael@0: #if DEBUG_CHECK_ENDS
michael@0:             SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n",
michael@0:                     __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY);
michael@0: #endif
michael@0:             // this segment is missing a entry that the other contains
michael@0:             // remember so we can add the missing one and recompute the indices
michael@0:             {
michael@0:                 MissingSpan& missing = missingSpans.push_back();
michael@0:                 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
michael@0:                 missing.fT = t;
michael@0:                 missing.fOther = match;
michael@0:                 missing.fOtherT = matchT;
michael@0:                 missing.fPt = peekSpan.fPt;
michael@0:             }
michael@0:             break;
michael@0: nextPeekIndex:
michael@0:             ;
michael@0:         }
michael@0:     }
michael@0:     if (missingSpans.count() == 0) {
michael@0:         debugValidate();
michael@0:         return;
michael@0:     }
michael@0:     debugValidate();
michael@0:     int missingCount = missingSpans.count();
michael@0:     for (int index = 0; index < missingCount; ++index)  {
michael@0:         MissingSpan& missing = missingSpans[index];
michael@0:         addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
michael@0:     }
michael@0:     fixOtherTIndex();
michael@0:     // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
michael@0:     // avoid this
michael@0:     for (int index = 0; index < missingCount; ++index)  {
michael@0:         missingSpans[index].fOther->fixOtherTIndex();
michael@0:     }
michael@0:     debugValidate();
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::checkSmall(int index) const {
michael@0:     if (fTs[index].fSmall) {
michael@0:         return true;
michael@0:     }
michael@0:     double tBase = fTs[index].fT;
michael@0:     while (index > 0 && precisely_negative(tBase - fTs[--index].fT))
michael@0:         ;
michael@0:     return fTs[index].fSmall;
michael@0: }
michael@0: 
michael@0: // if pair of spans on either side of tiny have the same end point and mid point, mark
michael@0: // them as parallel
michael@0: // OPTIMIZATION : mark the segment to note that some span is tiny
michael@0: void SkOpSegment::checkTiny() {
michael@0:     SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
michael@0:     SkOpSpan* thisSpan = fTs.begin() - 1;
michael@0:     const SkOpSpan* endSpan = fTs.end() - 1;  // last can't be tiny
michael@0:     while (++thisSpan < endSpan) {
michael@0:         if (!thisSpan->fTiny) {
michael@0:             continue;
michael@0:         }
michael@0:         SkOpSpan* nextSpan = thisSpan + 1;
michael@0:         double thisT = thisSpan->fT;
michael@0:         double nextT = nextSpan->fT;
michael@0:         if (thisT == nextT) {
michael@0:             continue;
michael@0:         }
michael@0:         SkASSERT(thisT < nextT);
michael@0:         SkASSERT(thisSpan->fPt == nextSpan->fPt);
michael@0:         SkOpSegment* thisOther = thisSpan->fOther;
michael@0:         SkOpSegment* nextOther = nextSpan->fOther;
michael@0:         int oIndex = thisSpan->fOtherIndex;
michael@0:         for (int oStep = -1; oStep <= 1; oStep += 2) {
michael@0:             int oEnd = thisOther->nextExactSpan(oIndex, oStep);
michael@0:             if (oEnd < 0) {
michael@0:                 continue;
michael@0:             }
michael@0:             const SkOpSpan& oSpan = thisOther->span(oEnd);
michael@0:             int nIndex = nextSpan->fOtherIndex;
michael@0:             for (int nStep = -1; nStep <= 1; nStep += 2) {
michael@0:                 int nEnd = nextOther->nextExactSpan(nIndex, nStep);
michael@0:                 if (nEnd < 0) {
michael@0:                     continue;
michael@0:                 }
michael@0:                 const SkOpSpan& nSpan = nextOther->span(nEnd);
michael@0:                 if (oSpan.fPt != nSpan.fPt) {
michael@0:                     continue;
michael@0:                 }
michael@0:                 double oMidT = (thisSpan->fOtherT + oSpan.fT) / 2;
michael@0:                 const SkPoint& oPt = thisOther->ptAtT(oMidT);
michael@0:                 double nMidT = (nextSpan->fOtherT + nSpan.fT) / 2;
michael@0:                 const SkPoint& nPt = nextOther->ptAtT(nMidT);
michael@0:                 if (!AlmostEqualUlps(oPt, nPt)) {
michael@0:                     continue;
michael@0:                 }
michael@0: #if DEBUG_CHECK_TINY
michael@0:                 SkDebugf("%s [%d] add coincidence [%d] [%d]\n", __FUNCTION__, fID,
michael@0:                     thisOther->fID, nextOther->fID);
michael@0: #endif
michael@0:                 // this segment is missing a entry that the other contains
michael@0:                 // remember so we can add the missing one and recompute the indices
michael@0:                 MissingSpan& missing = missingSpans.push_back();
michael@0:                 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
michael@0:                 missing.fSegment = thisOther;
michael@0:                 missing.fT = thisSpan->fOtherT;
michael@0:                 missing.fOther = nextOther;
michael@0:                 missing.fOtherT = nextSpan->fOtherT;
michael@0:                 missing.fPt = thisSpan->fPt;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     int missingCount = missingSpans.count();
michael@0:     if (!missingCount) {
michael@0:         return;
michael@0:     }
michael@0:     for (int index = 0; index < missingCount; ++index)  {
michael@0:         MissingSpan& missing = missingSpans[index];
michael@0:         missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
michael@0:     }
michael@0:     for (int index = 0; index < missingCount; ++index)  {
michael@0:         MissingSpan& missing = missingSpans[index];
michael@0:         missing.fSegment->fixOtherTIndex();
michael@0:         missing.fOther->fixOtherTIndex();
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart,
michael@0:         int oEnd, int step, SkPoint* startPt, SkPoint* endPt, double* endT) const {
michael@0:     SkASSERT(span->fT == 0 || span->fT == 1);
michael@0:     SkASSERT(span->fOtherT == 0 || span->fOtherT == 1);
michael@0:     const SkOpSpan* otherSpan = &other->span(oEnd);
michael@0:     double refT = otherSpan->fT;
michael@0:     const SkPoint& refPt = otherSpan->fPt;
michael@0:     const SkOpSpan* lastSpan = &other->span(step > 0 ? other->count() - 1 : 0);
michael@0:     do {
michael@0:         const SkOpSegment* match = span->fOther;
michael@0:         if (match == otherSpan->fOther) {
michael@0:             // find start of respective spans and see if both have winding
michael@0:             int startIndex, endIndex;
michael@0:             if (span->fOtherT == 1) {
michael@0:                 endIndex = span->fOtherIndex;
michael@0:                 startIndex = match->nextExactSpan(endIndex, -1);
michael@0:             } else {
michael@0:                 startIndex = span->fOtherIndex;
michael@0:                 endIndex = match->nextExactSpan(startIndex, 1);
michael@0:             }
michael@0:             const SkOpSpan& startSpan = match->span(startIndex);
michael@0:             if (startSpan.fWindValue != 0) {
michael@0:                 // draw ray from endSpan.fPt perpendicular to end tangent and measure distance
michael@0:                 // to other segment.
michael@0:                 const SkOpSpan& endSpan = match->span(endIndex);
michael@0:                 SkDLine ray;
michael@0:                 SkVector dxdy;
michael@0:                 if (span->fOtherT == 1) {
michael@0:                     ray.fPts[0].set(startSpan.fPt);
michael@0:                     dxdy = match->dxdy(startIndex);
michael@0:                 } else {
michael@0:                     ray.fPts[0].set(endSpan.fPt);
michael@0:                     dxdy = match->dxdy(endIndex);
michael@0:                 }
michael@0:                 ray.fPts[1].fX = ray.fPts[0].fX + dxdy.fY;
michael@0:                 ray.fPts[1].fY = ray.fPts[0].fY - dxdy.fX;
michael@0:                 SkIntersections i;
michael@0:                 int roots = (i.*CurveRay[SkPathOpsVerbToPoints(other->verb())])(other->pts(), ray);
michael@0:                 for (int index = 0; index < roots; ++index) {
michael@0:                     if (ray.fPts[0].approximatelyEqual(i.pt(index))) {
michael@0:                         double matchMidT = (match->span(startIndex).fT
michael@0:                                 + match->span(endIndex).fT) / 2;
michael@0:                         SkPoint matchMidPt = match->ptAtT(matchMidT);
michael@0:                         double otherMidT = (i[0][index] + other->span(oStart).fT) / 2;
michael@0:                         SkPoint otherMidPt = other->ptAtT(otherMidT);
michael@0:                         if (SkDPoint::ApproximatelyEqual(matchMidPt, otherMidPt)) {
michael@0:                             *startPt = startSpan.fPt;
michael@0:                             *endPt = endSpan.fPt;
michael@0:                             *endT = endSpan.fT;
michael@0:                             return true;
michael@0:                         }
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0:             return false;
michael@0:         }
michael@0:         if (otherSpan == lastSpan) {
michael@0:             break;
michael@0:         }
michael@0:         otherSpan += step;
michael@0:     } while (otherSpan->fT == refT || otherSpan->fPt == refPt);
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  The M and S variable name parts stand for the operators.
michael@0:    Mi stands for Minuend (see wiki subtraction, analogous to difference)
michael@0:    Su stands for Subtrahend
michael@0:  The Opp variable name part designates that the value is for the Opposite operator.
michael@0:  Opposite values result from combining coincident spans.
michael@0:  */
michael@0: SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
michael@0:                                      bool* unsortable, SkPathOp op, const int xorMiMask,
michael@0:                                      const int xorSuMask) {
michael@0:     const int startIndex = *nextStart;
michael@0:     const int endIndex = *nextEnd;
michael@0:     SkASSERT(startIndex != endIndex);
michael@0:     SkDEBUGCODE(const int count = fTs.count());
michael@0:     SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
michael@0:     const int step = SkSign32(endIndex - startIndex);
michael@0:     const int end = nextExactSpan(startIndex, step);
michael@0:     SkASSERT(end >= 0);
michael@0:     SkOpSpan* endSpan = &fTs[end];
michael@0:     SkOpSegment* other;
michael@0:     if (isSimple(end)) {
michael@0:     // mark the smaller of startIndex, endIndex done, and all adjacent
michael@0:     // spans with the same T value (but not 'other' spans)
michael@0: #if DEBUG_WINDING
michael@0:         SkDebugf("%s simple\n", __FUNCTION__);
michael@0: #endif
michael@0:         int min = SkMin32(startIndex, endIndex);
michael@0:         if (fTs[min].fDone) {
michael@0:             return NULL;
michael@0:         }
michael@0:         markDoneBinary(min);
michael@0:         other = endSpan->fOther;
michael@0:         *nextStart = endSpan->fOtherIndex;
michael@0:         double startT = other->fTs[*nextStart].fT;
michael@0:         *nextEnd = *nextStart;
michael@0:         do {
michael@0:             *nextEnd += step;
michael@0:         } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
michael@0:         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
michael@0:         if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
michael@0:             *unsortable = true;
michael@0:             return NULL;
michael@0:         }
michael@0:         return other;
michael@0:     }
michael@0:     // more than one viable candidate -- measure angles to find best
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
michael@0:     SkASSERT(startIndex - endIndex != 0);
michael@0:     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
michael@0:     int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp, &angles, &sorted);
michael@0:     bool sortable = calcWinding != SK_NaN32;
michael@0:     if (sortable && sorted.count() == 0) {
michael@0:         // if no edge has a computed winding sum, we can go no further
michael@0:         *unsortable = true;
michael@0:         return NULL;
michael@0:     }
michael@0:     int angleCount = angles.count();
michael@0:     int firstIndex = findStartingEdge(sorted, startIndex, end);
michael@0:     SkASSERT(!sortable || firstIndex >= 0);
michael@0: #if DEBUG_SORT
michael@0:     debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
michael@0: #endif
michael@0:     if (!sortable) {
michael@0:         *unsortable = true;
michael@0:         return NULL;
michael@0:     }
michael@0:     SkASSERT(sorted[firstIndex]->segment() == this);
michael@0: #if DEBUG_WINDING
michael@0:     SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
michael@0:             sorted[firstIndex]->sign());
michael@0: #endif
michael@0:     int sumMiWinding = updateWinding(endIndex, startIndex);
michael@0:     int sumSuWinding = updateOppWinding(endIndex, startIndex);
michael@0:     if (operand()) {
michael@0:         SkTSwap<int>(sumMiWinding, sumSuWinding);
michael@0:     }
michael@0:     int nextIndex = firstIndex + 1;
michael@0:     int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
michael@0:     const SkOpAngle* foundAngle = NULL;
michael@0:     bool foundDone = false;
michael@0:     // iterate through the angle, and compute everyone's winding
michael@0:     SkOpSegment* nextSegment;
michael@0:     int activeCount = 0;
michael@0:     do {
michael@0:         SkASSERT(nextIndex != firstIndex);
michael@0:         if (nextIndex == angleCount) {
michael@0:             nextIndex = 0;
michael@0:         }
michael@0:         const SkOpAngle* nextAngle = sorted[nextIndex];
michael@0:         nextSegment = nextAngle->segment();
michael@0:         int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
michael@0:         bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
michael@0:                 nextAngle->end(), op, &sumMiWinding, &sumSuWinding,
michael@0:                 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
michael@0:         if (activeAngle) {
michael@0:             ++activeCount;
michael@0:             if (!foundAngle || (foundDone && activeCount & 1)) {
michael@0:                 if (nextSegment->isTiny(nextAngle)) {
michael@0:                     *unsortable = true;
michael@0:                     return NULL;
michael@0:                 }
michael@0:                 foundAngle = nextAngle;
michael@0:                 foundDone = nextSegment->done(nextAngle);
michael@0:             }
michael@0:         }
michael@0:         if (nextSegment->done()) {
michael@0:             continue;
michael@0:         }
michael@0:         if (nextSegment->isTiny(nextAngle)) {
michael@0:             continue;
michael@0:         }
michael@0:         if (!activeAngle) {
michael@0:             nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
michael@0:         }
michael@0:         SkOpSpan* last = nextAngle->lastMarked();
michael@0:         if (last) {
michael@0:             *chase->append() = last;
michael@0: #if DEBUG_WINDING
michael@0:             SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
michael@0:                     last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
michael@0:                     last->fSmall);
michael@0: #endif
michael@0:         }
michael@0:     } while (++nextIndex != lastIndex);
michael@0:     markDoneBinary(SkMin32(startIndex, endIndex));
michael@0:     if (!foundAngle) {
michael@0:         return NULL;
michael@0:     }
michael@0:     *nextStart = foundAngle->start();
michael@0:     *nextEnd = foundAngle->end();
michael@0:     nextSegment = foundAngle->segment();
michael@0: #if DEBUG_WINDING
michael@0:     SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
michael@0:             __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
michael@0:  #endif
michael@0:     return nextSegment;
michael@0: }
michael@0: 
michael@0: SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart,
michael@0:                                           int* nextEnd, bool* unsortable) {
michael@0:     const int startIndex = *nextStart;
michael@0:     const int endIndex = *nextEnd;
michael@0:     SkASSERT(startIndex != endIndex);
michael@0:     SkDEBUGCODE(const int count = fTs.count());
michael@0:     SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
michael@0:     const int step = SkSign32(endIndex - startIndex);
michael@0:     const int end = nextExactSpan(startIndex, step);
michael@0:     SkASSERT(end >= 0);
michael@0:     SkOpSpan* endSpan = &fTs[end];
michael@0:     SkOpSegment* other;
michael@0:     if (isSimple(end)) {
michael@0:     // mark the smaller of startIndex, endIndex done, and all adjacent
michael@0:     // spans with the same T value (but not 'other' spans)
michael@0: #if DEBUG_WINDING
michael@0:         SkDebugf("%s simple\n", __FUNCTION__);
michael@0: #endif
michael@0:         int min = SkMin32(startIndex, endIndex);
michael@0:         if (fTs[min].fDone) {
michael@0:             return NULL;
michael@0:         }
michael@0:         markDoneUnary(min);
michael@0:         other = endSpan->fOther;
michael@0:         *nextStart = endSpan->fOtherIndex;
michael@0:         double startT = other->fTs[*nextStart].fT;
michael@0:         *nextEnd = *nextStart;
michael@0:         do {
michael@0:             *nextEnd += step;
michael@0:         } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
michael@0:         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
michael@0:         if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
michael@0:             *unsortable = true;
michael@0:             return NULL;
michael@0:         }
michael@0:         return other;
michael@0:     }
michael@0:     // more than one viable candidate -- measure angles to find best
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
michael@0:     SkASSERT(startIndex - endIndex != 0);
michael@0:     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
michael@0:     int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding, &angles, &sorted);
michael@0:     bool sortable = calcWinding != SK_NaN32;
michael@0:     int angleCount = angles.count();
michael@0:     int firstIndex = findStartingEdge(sorted, startIndex, end);
michael@0:     SkASSERT(!sortable || firstIndex >= 0);
michael@0: #if DEBUG_SORT
michael@0:     debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
michael@0: #endif
michael@0:     if (!sortable) {
michael@0:         *unsortable = true;
michael@0:         return NULL;
michael@0:     }
michael@0:     SkASSERT(sorted[firstIndex]->segment() == this);
michael@0: #if DEBUG_WINDING
michael@0:     SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
michael@0:             sorted[firstIndex]->sign());
michael@0: #endif
michael@0:     int sumWinding = updateWinding(endIndex, startIndex);
michael@0:     int nextIndex = firstIndex + 1;
michael@0:     int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
michael@0:     const SkOpAngle* foundAngle = NULL;
michael@0:     bool foundDone = false;
michael@0:     // iterate through the angle, and compute everyone's winding
michael@0:     SkOpSegment* nextSegment;
michael@0:     int activeCount = 0;
michael@0:     do {
michael@0:         SkASSERT(nextIndex != firstIndex);
michael@0:         if (nextIndex == angleCount) {
michael@0:             nextIndex = 0;
michael@0:         }
michael@0:         const SkOpAngle* nextAngle = sorted[nextIndex];
michael@0:         nextSegment = nextAngle->segment();
michael@0:         int maxWinding;
michael@0:         bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
michael@0:                 &maxWinding, &sumWinding);
michael@0:         if (activeAngle) {
michael@0:             ++activeCount;
michael@0:             if (!foundAngle || (foundDone && activeCount & 1)) {
michael@0:                 if (nextSegment->isTiny(nextAngle)) {
michael@0:                     *unsortable = true;
michael@0:                     return NULL;
michael@0:                 }
michael@0:                 foundAngle = nextAngle;
michael@0:                 foundDone = nextSegment->done(nextAngle);
michael@0:             }
michael@0:         }
michael@0:         if (nextSegment->done()) {
michael@0:             continue;
michael@0:         }
michael@0:         if (nextSegment->isTiny(nextAngle)) {
michael@0:             continue;
michael@0:         }
michael@0:         if (!activeAngle) {
michael@0:             nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end());
michael@0:         }
michael@0:         SkOpSpan* last = nextAngle->lastMarked();
michael@0:         if (last) {
michael@0:             *chase->append() = last;
michael@0: #if DEBUG_WINDING
michael@0:             SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
michael@0:                     last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
michael@0:                     last->fSmall);
michael@0: #endif
michael@0:         }
michael@0:     } while (++nextIndex != lastIndex);
michael@0:     markDoneUnary(SkMin32(startIndex, endIndex));
michael@0:     if (!foundAngle) {
michael@0:         return NULL;
michael@0:     }
michael@0:     *nextStart = foundAngle->start();
michael@0:     *nextEnd = foundAngle->end();
michael@0:     nextSegment = foundAngle->segment();
michael@0: #if DEBUG_WINDING
michael@0:     SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
michael@0:             __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
michael@0:  #endif
michael@0:     return nextSegment;
michael@0: }
michael@0: 
michael@0: SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsortable) {
michael@0:     const int startIndex = *nextStart;
michael@0:     const int endIndex = *nextEnd;
michael@0:     SkASSERT(startIndex != endIndex);
michael@0:     SkDEBUGCODE(int count = fTs.count());
michael@0:     SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
michael@0:     int step = SkSign32(endIndex - startIndex);
michael@0:     int end = nextExactSpan(startIndex, step);
michael@0:     SkASSERT(end >= 0);
michael@0:     SkOpSpan* endSpan = &fTs[end];
michael@0:     SkOpSegment* other;
michael@0:     if (isSimple(end)) {
michael@0: #if DEBUG_WINDING
michael@0:         SkDebugf("%s simple\n", __FUNCTION__);
michael@0: #endif
michael@0:         int min = SkMin32(startIndex, endIndex);
michael@0:         if (fTs[min].fDone) {
michael@0:             return NULL;
michael@0:         }
michael@0:         markDone(min, 1);
michael@0:         other = endSpan->fOther;
michael@0:         *nextStart = endSpan->fOtherIndex;
michael@0:         double startT = other->fTs[*nextStart].fT;
michael@0:         // FIXME: I don't know why the logic here is difference from the winding case
michael@0:         SkDEBUGCODE(bool firstLoop = true;)
michael@0:         if ((approximately_less_than_zero(startT) && step < 0)
michael@0:                 || (approximately_greater_than_one(startT) && step > 0)) {
michael@0:             step = -step;
michael@0:             SkDEBUGCODE(firstLoop = false;)
michael@0:         }
michael@0:         do {
michael@0:             *nextEnd = *nextStart;
michael@0:             do {
michael@0:                 *nextEnd += step;
michael@0:             } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
michael@0:             if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) {
michael@0:                 break;
michael@0:             }
michael@0:             SkASSERT(firstLoop);
michael@0:             SkDEBUGCODE(firstLoop = false;)
michael@0:             step = -step;
michael@0:         } while (true);
michael@0:         SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
michael@0:         return other;
michael@0:     }
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
michael@0:     SkASSERT(startIndex - endIndex != 0);
michael@0:     SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
michael@0:     int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryXor, &angles, &sorted);
michael@0:     bool sortable = calcWinding != SK_NaN32;
michael@0:     int angleCount = angles.count();
michael@0:     int firstIndex = findStartingEdge(sorted, startIndex, end);
michael@0:     SkASSERT(!sortable || firstIndex >= 0);
michael@0: #if DEBUG_SORT
michael@0:     debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable);
michael@0: #endif
michael@0:     if (!sortable) {
michael@0:         *unsortable = true;
michael@0:         return NULL;
michael@0:     }
michael@0:     SkASSERT(sorted[firstIndex]->segment() == this);
michael@0: #if DEBUG_WINDING
michael@0:     SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
michael@0:             sorted[firstIndex]->sign());
michael@0: #endif
michael@0:     int nextIndex = firstIndex + 1;
michael@0:     int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
michael@0:     const SkOpAngle* foundAngle = NULL;
michael@0:     bool foundDone = false;
michael@0:     SkOpSegment* nextSegment;
michael@0:     int activeCount = 0;
michael@0:     do {
michael@0:         SkASSERT(nextIndex != firstIndex);
michael@0:         if (nextIndex == angleCount) {
michael@0:             nextIndex = 0;
michael@0:         }
michael@0:         const SkOpAngle* nextAngle = sorted[nextIndex];
michael@0:         nextSegment = nextAngle->segment();
michael@0:         ++activeCount;
michael@0:         if (!foundAngle || (foundDone && activeCount & 1)) {
michael@0:             if (nextSegment->isTiny(nextAngle)) {
michael@0:                 *unsortable = true;
michael@0:                 return NULL;
michael@0:             }
michael@0:             foundAngle = nextAngle;
michael@0:             foundDone = nextSegment->done(nextAngle);
michael@0:         }
michael@0:         if (nextSegment->done()) {
michael@0:             continue;
michael@0:         }
michael@0:     } while (++nextIndex != lastIndex);
michael@0:     markDone(SkMin32(startIndex, endIndex), 1);
michael@0:     if (!foundAngle) {
michael@0:         return NULL;
michael@0:     }
michael@0:     *nextStart = foundAngle->start();
michael@0:     *nextEnd = foundAngle->end();
michael@0:     nextSegment = foundAngle->segment();
michael@0: #if DEBUG_WINDING
michael@0:     SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
michael@0:             __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
michael@0:  #endif
michael@0:     return nextSegment;
michael@0: }
michael@0: 
michael@0: int SkOpSegment::findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end) {
michael@0:     int angleCount = sorted.count();
michael@0:     int firstIndex = -1;
michael@0:     for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
michael@0:         const SkOpAngle* angle = sorted[angleIndex];
michael@0:         if (angle->segment() == this && angle->start() == end &&
michael@0:                 angle->end() == start) {
michael@0:             firstIndex = angleIndex;
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0:     return firstIndex;
michael@0: }
michael@0: 
michael@0: int SkOpSegment::findT(double t, const SkOpSegment* match) const {
michael@0:     int count = this->count();
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         const SkOpSpan& span = fTs[index];
michael@0:         if (span.fT == t && span.fOther == match) {
michael@0:             return index;
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(0);
michael@0:     return -1;
michael@0: }
michael@0: 
michael@0: // FIXME: either:
michael@0: // a) mark spans with either end unsortable as done, or
michael@0: // b) rewrite findTop / findTopSegment / findTopContour to iterate further
michael@0: //    when encountering an unsortable span
michael@0: 
michael@0: // OPTIMIZATION : for a pair of lines, can we compute points at T (cached)
michael@0: // and use more concise logic like the old edge walker code?
michael@0: // FIXME: this needs to deal with coincident edges
michael@0: SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable,
michael@0:                                   bool onlySortable) {
michael@0:     // iterate through T intersections and return topmost
michael@0:     // topmost tangent from y-min to first pt is closer to horizontal
michael@0:     SkASSERT(!done());
michael@0:     int firstT = -1;
michael@0:     /* SkPoint topPt = */ activeLeftTop(onlySortable, &firstT);
michael@0:     if (firstT < 0) {
michael@0:         *unsortable = true;
michael@0:         firstT = 0;
michael@0:         while (fTs[firstT].fDone) {
michael@0:             SkASSERT(firstT < fTs.count());
michael@0:             ++firstT;
michael@0:         }
michael@0:         *tIndexPtr = firstT;
michael@0:         *endIndexPtr = nextExactSpan(firstT, 1);
michael@0:         return this;
michael@0:     }
michael@0:     // sort the edges to find the leftmost
michael@0:     int step = 1;
michael@0:     int end = nextSpan(firstT, step);
michael@0:     if (end == -1) {
michael@0:         step = -1;
michael@0:         end = nextSpan(firstT, step);
michael@0:         SkASSERT(end != -1);
michael@0:     }
michael@0:     // if the topmost T is not on end, or is three-way or more, find left
michael@0:     // look for left-ness from tLeft to firstT (matching y of other)
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
michael@0:     SkASSERT(firstT - end != 0);
michael@0:     addTwoAngles(end, firstT, &angles);
michael@0:     if (!buildAngles(firstT, &angles, true) && onlySortable) {
michael@0: //        *unsortable = true;
michael@0: //        return NULL;
michael@0:     }
michael@0:     SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
michael@0:     bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind);
michael@0:     if (onlySortable && !sortable) {
michael@0:         *unsortable = true;
michael@0:         return NULL;
michael@0:     }
michael@0:     int first = SK_MaxS32;
michael@0:     SkScalar top = SK_ScalarMax;
michael@0:     int count = sorted.count();
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         const SkOpAngle* angle = sorted[index];
michael@0:         if (onlySortable && angle->unorderable()) {
michael@0:             continue;
michael@0:         }
michael@0:         SkOpSegment* next = angle->segment();
michael@0:         SkPathOpsBounds bounds;
michael@0:         next->subDivideBounds(angle->end(), angle->start(), &bounds);
michael@0:         if (approximately_greater(top, bounds.fTop)) {
michael@0:             top = bounds.fTop;
michael@0:             first = index;
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(first < SK_MaxS32);
michael@0: #if DEBUG_SORT  // || DEBUG_SWAP_TOP
michael@0:     sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable);
michael@0: #endif
michael@0:     // skip edges that have already been processed
michael@0:     firstT = first - 1;
michael@0:     SkOpSegment* leftSegment;
michael@0:     do {
michael@0:         if (++firstT == count) {
michael@0:             firstT = 0;
michael@0:         }
michael@0:         const SkOpAngle* angle = sorted[firstT];
michael@0:         SkASSERT(!onlySortable || !angle->unsortable());
michael@0:         leftSegment = angle->segment();
michael@0:         *tIndexPtr = angle->end();
michael@0:         *endIndexPtr = angle->start();
michael@0:     } while (leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone);
michael@0:     if (leftSegment->verb() >= SkPath::kQuad_Verb) {
michael@0:         const int tIndex = *tIndexPtr;
michael@0:         const int endIndex = *endIndexPtr;
michael@0:         if (!leftSegment->clockwise(tIndex, endIndex)) {
michael@0:             bool swap = !leftSegment->monotonicInY(tIndex, endIndex)
michael@0:                     && !leftSegment->serpentine(tIndex, endIndex);
michael@0:     #if DEBUG_SWAP_TOP
michael@0:             SkDebugf("%s swap=%d serpentine=%d containedByEnds=%d monotonic=%d\n", __FUNCTION__,
michael@0:                     swap,
michael@0:                     leftSegment->serpentine(tIndex, endIndex),
michael@0:                     leftSegment->controlsContainedByEnds(tIndex, endIndex),
michael@0:                     leftSegment->monotonicInY(tIndex, endIndex));
michael@0:     #endif
michael@0:             if (swap) {
michael@0:     // FIXME: I doubt it makes sense to (necessarily) swap if the edge was not the first
michael@0:     // sorted but merely the first not already processed (i.e., not done)
michael@0:                 SkTSwap(*tIndexPtr, *endIndexPtr);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fTiny);
michael@0:     return leftSegment;
michael@0: }
michael@0: 
michael@0: // FIXME: not crazy about this
michael@0: // when the intersections are performed, the other index is into an
michael@0: // incomplete array. As the array grows, the indices become incorrect
michael@0: // while the following fixes the indices up again, it isn't smart about
michael@0: // skipping segments whose indices are already correct
michael@0: // assuming we leave the code that wrote the index in the first place
michael@0: // FIXME: if called after remove, this needs to correct tiny
michael@0: void SkOpSegment::fixOtherTIndex() {
michael@0:     int iCount = fTs.count();
michael@0:     for (int i = 0; i < iCount; ++i) {
michael@0:         SkOpSpan& iSpan = fTs[i];
michael@0:         double oT = iSpan.fOtherT;
michael@0:         SkOpSegment* other = iSpan.fOther;
michael@0:         int oCount = other->fTs.count();
michael@0:         SkDEBUGCODE(iSpan.fOtherIndex = -1);
michael@0:         for (int o = 0; o < oCount; ++o) {
michael@0:             SkOpSpan& oSpan = other->fTs[o];
michael@0:             if (oT == oSpan.fT && this == oSpan.fOther && oSpan.fOtherT == iSpan.fT) {
michael@0:                 iSpan.fOtherIndex = o;
michael@0:                 oSpan.fOtherIndex = i;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:         SkASSERT(iSpan.fOtherIndex >= 0);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
michael@0:     fDoneSpans = 0;
michael@0:     fOperand = operand;
michael@0:     fXor = evenOdd;
michael@0:     fPts = pts;
michael@0:     fVerb = verb;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::initWinding(int start, int end) {
michael@0:     int local = spanSign(start, end);
michael@0:     int oppLocal = oppSign(start, end);
michael@0:     (void) markAndChaseWinding(start, end, local, oppLocal);
michael@0:     // OPTIMIZATION: the reverse mark and chase could skip the first marking
michael@0:     (void) markAndChaseWinding(end, start, local, oppLocal);
michael@0: }
michael@0: 
michael@0: /*
michael@0: when we start with a vertical intersect, we try to use the dx to determine if the edge is to
michael@0: the left or the right of vertical. This determines if we need to add the span's
michael@0: sign or not. However, this isn't enough.
michael@0: If the supplied sign (winding) is zero, then we didn't hit another vertical span, so dx is needed.
michael@0: If there was a winding, then it may or may not need adjusting. If the span the winding was borrowed
michael@0: from has the same x direction as this span, the winding should change. If the dx is opposite, then
michael@0: the same winding is shared by both.
michael@0: */
michael@0: void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkScalar hitDx,
michael@0:                               int oppWind, SkScalar hitOppDx) {
michael@0:     SkASSERT(hitDx || !winding);
michael@0:     SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
michael@0:     SkASSERT(dx);
michael@0:     int windVal = windValue(SkMin32(start, end));
michael@0: #if DEBUG_WINDING_AT_T
michael@0:     SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding,
michael@0:             hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
michael@0: #endif
michael@0:     if (!winding) {
michael@0:         winding = dx < 0 ? windVal : -windVal;
michael@0:     } else if (winding * dx < 0) {
michael@0:         int sideWind = winding + (dx < 0 ? windVal : -windVal);
michael@0:         if (abs(winding) < abs(sideWind)) {
michael@0:             winding = sideWind;
michael@0:         }
michael@0:     }
michael@0: #if DEBUG_WINDING_AT_T
michael@0:     SkDebugf(" winding=%d\n", winding);
michael@0: #endif
michael@0:     SkDEBUGCODE(int oppLocal = oppSign(start, end));
michael@0:     SkASSERT(hitOppDx || !oppWind || !oppLocal);
michael@0:     int oppWindVal = oppValue(SkMin32(start, end));
michael@0:     if (!oppWind) {
michael@0:         oppWind = dx < 0 ? oppWindVal : -oppWindVal;
michael@0:     } else if (hitOppDx * dx >= 0) {
michael@0:         int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
michael@0:         if (abs(oppWind) < abs(oppSideWind)) {
michael@0:             oppWind = oppSideWind;
michael@0:         }
michael@0:     }
michael@0:     (void) markAndChaseWinding(start, end, winding, oppWind);
michael@0:     // OPTIMIZATION: the reverse mark and chase could skip the first marking
michael@0:     (void) markAndChaseWinding(end, start, winding, oppWind);
michael@0: }
michael@0: 
michael@0: // OPTIMIZE: successive calls could start were the last leaves off
michael@0: // or calls could specialize to walk forwards or backwards
michael@0: bool SkOpSegment::isMissing(double startT, const SkPoint& pt) const {
michael@0:     size_t tCount = fTs.count();
michael@0:     for (size_t index = 0; index < tCount; ++index) {
michael@0:         const SkOpSpan& span = fTs[index];
michael@0:         if (approximately_zero(startT - span.fT) && pt == span.fPt) {
michael@0:             return false;
michael@0:         }
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::isSimple(int end) const {
michael@0:     int count = fTs.count();
michael@0:     if (count == 2) {
michael@0:         return true;
michael@0:     }
michael@0:     double t = fTs[end].fT;
michael@0:     if (approximately_less_than_zero(t)) {
michael@0:         return !approximately_less_than_zero(fTs[1].fT);
michael@0:     }
michael@0:     if (approximately_greater_than_one(t)) {
michael@0:         return !approximately_greater_than_one(fTs[count - 2].fT);
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
michael@0:     int start = angle->start();
michael@0:     int end = angle->end();
michael@0:     const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
michael@0:     return mSpan.fTiny;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::isTiny(int index) const {
michael@0:     return fTs[index].fTiny;
michael@0: }
michael@0: 
michael@0: // look pair of active edges going away from coincident edge
michael@0: // one of them should be the continuation of other
michael@0: // if both are active, look to see if they both the connect to another coincident pair
michael@0: // if one at least one is a line, then make the pair coincident
michael@0: // if neither is a line, test for coincidence
michael@0: bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, int step,
michael@0:         bool cancel) {
michael@0:     int otherTIndex = other->findT(otherT, this);
michael@0:     int next = other->nextExactSpan(otherTIndex, step);
michael@0:     int otherMin = SkTMin(otherTIndex, next);
michael@0:     int otherWind = other->span(otherMin).fWindValue;
michael@0:     if (otherWind == 0) {
michael@0:         return false;
michael@0:     }
michael@0:     SkASSERT(next >= 0);
michael@0:     int tIndex = 0;
michael@0:     do {
michael@0:         SkOpSpan* test = &fTs[tIndex];
michael@0:         SkASSERT(test->fT == 0);
michael@0:         if (test->fOther == other || test->fOtherT != 1) {
michael@0:             continue;
michael@0:         }
michael@0:         SkPoint startPt, endPt;
michael@0:         double endT;
michael@0:         if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
michael@0:             SkOpSegment* match = test->fOther;
michael@0:             if (cancel) {
michael@0:                 match->addTCancel(startPt, endPt, other);
michael@0:             } else {
michael@0:                 match->addTCoincident(startPt, endPt, endT, other);
michael@0:             }
michael@0:             return true;
michael@0:         }
michael@0:     } while (fTs[++tIndex].fT == 0);
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: // this span is excluded by the winding rule -- chase the ends
michael@0: // as long as they are unambiguous to mark connections as done
michael@0: // and give them the same winding value
michael@0: 
michael@0: SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) {
michael@0:     int step = SkSign32(endIndex - index);
michael@0:     int min = SkMin32(index, endIndex);
michael@0:     markDoneBinary(min);
michael@0:     SkOpSpan* last;
michael@0:     SkOpSegment* other = this;
michael@0:     while ((other = other->nextChase(&index, step, &min, &last))) {
michael@0:         if (other->done()) {
michael@0:             return NULL;
michael@0:         }
michael@0:         other->markDoneBinary(min);
michael@0:     }
michael@0:     return last;
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) {
michael@0:     int step = SkSign32(endIndex - index);
michael@0:     int min = SkMin32(index, endIndex);
michael@0:     markDoneUnary(min);
michael@0:     SkOpSpan* last;
michael@0:     SkOpSegment* other = this;
michael@0:     while ((other = other->nextChase(&index, step, &min, &last))) {
michael@0:         if (other->done()) {
michael@0:             return NULL;
michael@0:         }
michael@0:         other->markDoneUnary(min);
michael@0:     }
michael@0:     return last;
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, const int winding) {
michael@0:     int index = angle->start();
michael@0:     int endIndex = angle->end();
michael@0:     int step = SkSign32(endIndex - index);
michael@0:     int min = SkMin32(index, endIndex);
michael@0:     markWinding(min, winding);
michael@0:     SkOpSpan* last;
michael@0:     SkOpSegment* other = this;
michael@0:     while ((other = other->nextChase(&index, step, &min, &last))) {
michael@0:         if (other->fTs[min].fWindSum != SK_MinS32) {
michael@0:             SkASSERT(other->fTs[min].fWindSum == winding);
michael@0:             return NULL;
michael@0:         }
michael@0:         other->markWinding(min, winding);
michael@0:     }
michael@0:     return last;
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
michael@0:     int min = SkMin32(index, endIndex);
michael@0:     int step = SkSign32(endIndex - index);
michael@0:     markWinding(min, winding, oppWinding);
michael@0:     SkOpSpan* last;
michael@0:     SkOpSegment* other = this;
michael@0:     while ((other = other->nextChase(&index, step, &min, &last))) {
michael@0:         if (other->fTs[min].fWindSum != SK_MinS32) {
michael@0:             SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
michael@0:             return NULL;
michael@0:         }
michael@0:         other->markWinding(min, winding, oppWinding);
michael@0:     }
michael@0:     return last;
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding) {
michael@0:     int start = angle->start();
michael@0:     int end = angle->end();
michael@0:     return markAndChaseWinding(start, end, winding, oppWinding);
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
michael@0:     SkASSERT(angle->segment() == this);
michael@0:     if (UseInnerWinding(maxWinding, sumWinding)) {
michael@0:         maxWinding = sumWinding;
michael@0:     }
michael@0:     SkOpSpan* last = markAndChaseWinding(angle, maxWinding);
michael@0: #if DEBUG_WINDING
michael@0:     if (last) {
michael@0:         SkDebugf("%s last id=%d windSum=", __FUNCTION__,
michael@0:                 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
michael@0:         SkPathOpsDebug::WindingPrintf(last->fWindSum);
michael@0:         SkDebugf(" small=%d\n", last->fSmall);
michael@0:     }
michael@0: #endif
michael@0:     return last;
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
michael@0:                                  int oppSumWinding, const SkOpAngle* angle) {
michael@0:     SkASSERT(angle->segment() == this);
michael@0:     if (UseInnerWinding(maxWinding, sumWinding)) {
michael@0:         maxWinding = sumWinding;
michael@0:     }
michael@0:     if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
michael@0:         oppMaxWinding = oppSumWinding;
michael@0:     }
michael@0:     SkOpSpan* last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
michael@0: #if DEBUG_WINDING
michael@0:     if (last) {
michael@0:         SkDebugf("%s last id=%d windSum=", __FUNCTION__,
michael@0:                 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
michael@0:         SkPathOpsDebug::WindingPrintf(last->fWindSum);
michael@0:         SkDebugf(" small=%d\n", last->fSmall);
michael@0:     }
michael@0: #endif
michael@0:     return last;
michael@0: }
michael@0: 
michael@0: // FIXME: this should also mark spans with equal (x,y)
michael@0: // This may be called when the segment is already marked done. While this
michael@0: // wastes time, it shouldn't do any more than spin through the T spans.
michael@0: // OPTIMIZATION: abort on first done found (assuming that this code is
michael@0: // always called to mark segments done).
michael@0: void SkOpSegment::markDone(int index, int winding) {
michael@0:   //  SkASSERT(!done());
michael@0:     SkASSERT(winding);
michael@0:     double referenceT = fTs[index].fT;
michael@0:     int lesser = index;
michael@0:     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
michael@0:         markOneDone(__FUNCTION__, lesser, winding);
michael@0:     }
michael@0:     do {
michael@0:         markOneDone(__FUNCTION__, index, winding);
michael@0:     } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
michael@0: }
michael@0: 
michael@0: void SkOpSegment::markDoneBinary(int index) {
michael@0:     double referenceT = fTs[index].fT;
michael@0:     int lesser = index;
michael@0:     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
michael@0:         markOneDoneBinary(__FUNCTION__, lesser);
michael@0:     }
michael@0:     do {
michael@0:         markOneDoneBinary(__FUNCTION__, index);
michael@0:     } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
michael@0: }
michael@0: 
michael@0: void SkOpSegment::markDoneUnary(int index) {
michael@0:     double referenceT = fTs[index].fT;
michael@0:     int lesser = index;
michael@0:     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
michael@0:         markOneDoneUnary(__FUNCTION__, lesser);
michael@0:     }
michael@0:     do {
michael@0:         markOneDoneUnary(__FUNCTION__, index);
michael@0:     } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
michael@0: }
michael@0: 
michael@0: void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) {
michael@0:     SkOpSpan* span = markOneWinding(funName, tIndex, winding);
michael@0:     if (!span) {
michael@0:         return;
michael@0:     }
michael@0:     span->fDone = true;
michael@0:     fDoneSpans++;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) {
michael@0:     SkOpSpan* span = verifyOneWinding(funName, tIndex);
michael@0:     if (!span) {
michael@0:         return;
michael@0:     }
michael@0:     span->fDone = true;
michael@0:     fDoneSpans++;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) {
michael@0:     SkOpSpan* span = verifyOneWindingU(funName, tIndex);
michael@0:     if (!span) {
michael@0:         return;
michael@0:     }
michael@0:     span->fDone = true;
michael@0:     fDoneSpans++;
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding) {
michael@0:     SkOpSpan& span = fTs[tIndex];
michael@0:     if (span.fDone) {
michael@0:         return NULL;
michael@0:     }
michael@0: #if DEBUG_MARK_DONE
michael@0:     debugShowNewWinding(funName, span, winding);
michael@0: #endif
michael@0:     SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
michael@0:     SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
michael@0:     span.fWindSum = winding;
michael@0:     return &span;
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding,
michael@0:                                       int oppWinding) {
michael@0:     SkOpSpan& span = fTs[tIndex];
michael@0:     if (span.fDone && !span.fSmall) {
michael@0:         return NULL;
michael@0:     }
michael@0: #if DEBUG_MARK_DONE
michael@0:     debugShowNewWinding(funName, span, winding, oppWinding);
michael@0: #endif
michael@0:     SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
michael@0:     SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
michael@0:     span.fWindSum = winding;
michael@0:     SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
michael@0:     SkASSERT(abs(oppWinding) <= SkPathOpsDebug::gMaxWindSum);
michael@0:     span.fOppSum = oppWinding;
michael@0:     return &span;
michael@0: }
michael@0: 
michael@0: // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
michael@0: bool SkOpSegment::clockwise(int tStart, int tEnd) const {
michael@0:     SkASSERT(fVerb != SkPath::kLine_Verb);
michael@0:     SkPoint edge[4];
michael@0:     subDivide(tStart, tEnd, edge);
michael@0:     int points = SkPathOpsVerbToPoints(fVerb);
michael@0:     double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
michael@0:     if (fVerb == SkPath::kCubic_Verb) {
michael@0:         SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY);
michael@0:         if (edge[1].fY < lesser && edge[2].fY < lesser) {
michael@0:             SkDLine tangent1 = {{ {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1].fY} }};
michael@0:             SkDLine tangent2 = {{ {edge[2].fX, edge[2].fY}, {edge[3].fX, edge[3].fY} }};
michael@0:             if (SkIntersections::Test(tangent1, tangent2)) {
michael@0:                 SkPoint topPt = cubic_top(fPts, fTs[tStart].fT, fTs[tEnd].fT);
michael@0:                 sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY);
michael@0:                 sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY);
michael@0:                 return sum <= 0;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     for (int idx = 0; idx < points; ++idx){
michael@0:         sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
michael@0:     }
michael@0:     return sum <= 0;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::monotonicInY(int tStart, int tEnd) const {
michael@0:     if (fVerb == SkPath::kLine_Verb) {
michael@0:         return false;
michael@0:     }
michael@0:     if (fVerb == SkPath::kQuad_Verb) {
michael@0:         SkDQuad dst = SkDQuad::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
michael@0:         return dst.monotonicInY();
michael@0:     }
michael@0:     SkASSERT(fVerb == SkPath::kCubic_Verb);
michael@0:     SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
michael@0:     return dst.monotonicInY();
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::serpentine(int tStart, int tEnd) const {
michael@0:     if (fVerb != SkPath::kCubic_Verb) {
michael@0:         return false;
michael@0:     }
michael@0:     SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
michael@0:     return dst.serpentine();
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::verifyOneWinding(const char* funName, int tIndex) {
michael@0:     SkOpSpan& span = fTs[tIndex];
michael@0:     if (span.fDone) {
michael@0:         return NULL;
michael@0:     }
michael@0: #if DEBUG_MARK_DONE
michael@0:     debugShowNewWinding(funName, span, span.fWindSum, span.fOppSum);
michael@0: #endif
michael@0: // If the prior angle in the sort is unorderable, the winding sum may not be computable.
michael@0: // To enable the assert, the 'prior is unorderable' state could be
michael@0: // piped down to this test, but not sure it's worth it.
michael@0: // (Once the sort order is stored in the span, this test may be feasible.)
michael@0: //    SkASSERT(span.fWindSum != SK_MinS32);
michael@0: //    SkASSERT(span.fOppSum != SK_MinS32);
michael@0:     return &span;
michael@0: }
michael@0: 
michael@0: SkOpSpan* SkOpSegment::verifyOneWindingU(const char* funName, int tIndex) {
michael@0:     SkOpSpan& span = fTs[tIndex];
michael@0:     if (span.fDone) {
michael@0:         return NULL;
michael@0:     }
michael@0: #if DEBUG_MARK_DONE
michael@0:     debugShowNewWinding(funName, span, span.fWindSum);
michael@0: #endif
michael@0: // If the prior angle in the sort is unorderable, the winding sum may not be computable.
michael@0: // To enable the assert, the 'prior is unorderable' state could be
michael@0: // piped down to this test, but not sure it's worth it.
michael@0: // (Once the sort order is stored in the span, this test may be feasible.)
michael@0: //    SkASSERT(span.fWindSum != SK_MinS32);
michael@0:     return &span;
michael@0: }
michael@0: 
michael@0: // note that just because a span has one end that is unsortable, that's
michael@0: // not enough to mark it done. The other end may be sortable, allowing the
michael@0: // span to be added.
michael@0: // FIXME: if abs(start - end) > 1, mark intermediates as unsortable on both ends
michael@0: void SkOpSegment::markUnsortable(int start, int end) {
michael@0:     SkOpSpan* span = &fTs[start];
michael@0:     if (start < end) {
michael@0: #if DEBUG_UNSORTABLE
michael@0:         debugShowNewWinding(__FUNCTION__, *span, 0);
michael@0: #endif
michael@0:         span->fUnsortableStart = true;
michael@0:     } else {
michael@0:         --span;
michael@0: #if DEBUG_UNSORTABLE
michael@0:         debugShowNewWinding(__FUNCTION__, *span, 0);
michael@0: #endif
michael@0:         span->fUnsortableEnd = true;
michael@0:     }
michael@0:     if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) {
michael@0:         return;
michael@0:     }
michael@0:     span->fDone = true;
michael@0:     fDoneSpans++;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::markWinding(int index, int winding) {
michael@0: //    SkASSERT(!done());
michael@0:     SkASSERT(winding);
michael@0:     double referenceT = fTs[index].fT;
michael@0:     int lesser = index;
michael@0:     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
michael@0:         markOneWinding(__FUNCTION__, lesser, winding);
michael@0:     }
michael@0:     do {
michael@0:         markOneWinding(__FUNCTION__, index, winding);
michael@0:    } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
michael@0: }
michael@0: 
michael@0: void SkOpSegment::markWinding(int index, int winding, int oppWinding) {
michael@0: //    SkASSERT(!done());
michael@0:     SkASSERT(winding || oppWinding);
michael@0:     double referenceT = fTs[index].fT;
michael@0:     int lesser = index;
michael@0:     while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
michael@0:         markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
michael@0:     }
michael@0:     do {
michael@0:         markOneWinding(__FUNCTION__, index, winding, oppWinding);
michael@0:    } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
michael@0: }
michael@0: 
michael@0: void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) {
michael@0:     int nextDoorWind = SK_MaxS32;
michael@0:     int nextOppWind = SK_MaxS32;
michael@0:     if (tIndex > 0) {
michael@0:         const SkOpSpan& below = fTs[tIndex - 1];
michael@0:         if (approximately_negative(t - below.fT)) {
michael@0:             nextDoorWind = below.fWindValue;
michael@0:             nextOppWind = below.fOppValue;
michael@0:         }
michael@0:     }
michael@0:     if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
michael@0:         const SkOpSpan& above = fTs[tIndex + 1];
michael@0:         if (approximately_negative(above.fT - t)) {
michael@0:             nextDoorWind = above.fWindValue;
michael@0:             nextOppWind = above.fOppValue;
michael@0:         }
michael@0:     }
michael@0:     if (nextDoorWind == SK_MaxS32 && borrowWind && tIndex > 0 && t < 1) {
michael@0:         const SkOpSpan& below = fTs[tIndex - 1];
michael@0:         nextDoorWind = below.fWindValue;
michael@0:         nextOppWind = below.fOppValue;
michael@0:     }
michael@0:     if (nextDoorWind != SK_MaxS32) {
michael@0:         SkOpSpan& newSpan = fTs[tIndex];
michael@0:         newSpan.fWindValue = nextDoorWind;
michael@0:         newSpan.fOppValue = nextOppWind;
michael@0:         if (!nextDoorWind && !nextOppWind && !newSpan.fDone) {
michael@0:             newSpan.fDone = true;
michael@0:             ++fDoneSpans;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: // return span if when chasing, two or more radiating spans are not done
michael@0: // OPTIMIZATION: ? multiple spans is detected when there is only one valid
michael@0: // candidate and the remaining spans have windValue == 0 (canceled by
michael@0: // coincidence). The coincident edges could either be removed altogether,
michael@0: // or this code could be more complicated in detecting this case. Worth it?
michael@0: bool SkOpSegment::multipleSpans(int end) const {
michael@0:     return end > 0 && end < fTs.count() - 1;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::nextCandidate(int* start, int* end) const {
michael@0:     while (fTs[*end].fDone) {
michael@0:         if (fTs[*end].fT == 1) {
michael@0:             return false;
michael@0:         }
michael@0:         ++(*end);
michael@0:     }
michael@0:     *start = *end;
michael@0:     *end = nextExactSpan(*start, 1);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSpan** last) {
michael@0:     int end = nextExactSpan(*index, step);
michael@0:     SkASSERT(end >= 0);
michael@0:     if (fTs[end].fSmall) {
michael@0:         *last = NULL;
michael@0:         return NULL;
michael@0:     }
michael@0:     if (multipleSpans(end)) {
michael@0:         *last = &fTs[end];
michael@0:         return NULL;
michael@0:     }
michael@0:     const SkOpSpan& endSpan = fTs[end];
michael@0:     SkOpSegment* other = endSpan.fOther;
michael@0:     *index = endSpan.fOtherIndex;
michael@0:     SkASSERT(*index >= 0);
michael@0:     int otherEnd = other->nextExactSpan(*index, step);
michael@0:     SkASSERT(otherEnd >= 0);
michael@0:     *min = SkMin32(*index, otherEnd);
michael@0:     if (other->fTs[*min].fSmall) {
michael@0:         *last = NULL;
michael@0:         return NULL;
michael@0:     }
michael@0:     return other;
michael@0: }
michael@0: 
michael@0: // This has callers for two different situations: one establishes the end
michael@0: // of the current span, and one establishes the beginning of the next span
michael@0: // (thus the name). When this is looking for the end of the current span,
michael@0: // coincidence is found when the beginning Ts contain -step and the end
michael@0: // contains step. When it is looking for the beginning of the next, the
michael@0: // first Ts found can be ignored and the last Ts should contain -step.
michael@0: // OPTIMIZATION: probably should split into two functions
michael@0: int SkOpSegment::nextSpan(int from, int step) const {
michael@0:     const SkOpSpan& fromSpan = fTs[from];
michael@0:     int count = fTs.count();
michael@0:     int to = from;
michael@0:     while (step > 0 ? ++to < count : --to >= 0) {
michael@0:         const SkOpSpan& span = fTs[to];
michael@0:         if (approximately_zero(span.fT - fromSpan.fT)) {
michael@0:             continue;
michael@0:         }
michael@0:         return to;
michael@0:     }
michael@0:     return -1;
michael@0: }
michael@0: 
michael@0: // FIXME
michael@0: // this returns at any difference in T, vs. a preset minimum. It may be
michael@0: // that all callers to nextSpan should use this instead.
michael@0: int SkOpSegment::nextExactSpan(int from, int step) const {
michael@0:     int to = from;
michael@0:     if (step < 0) {
michael@0:         const SkOpSpan& fromSpan = fTs[from];
michael@0:         while (--to >= 0) {
michael@0:             const SkOpSpan& span = fTs[to];
michael@0:             if (precisely_negative(fromSpan.fT - span.fT) || span.fTiny) {
michael@0:                 continue;
michael@0:             }
michael@0:             return to;
michael@0:         }
michael@0:     } else {
michael@0:         while (fTs[from].fTiny) {
michael@0:             from++;
michael@0:         }
michael@0:         const SkOpSpan& fromSpan = fTs[from];
michael@0:         int count = fTs.count();
michael@0:         while (++to < count) {
michael@0:             const SkOpSpan& span = fTs[to];
michael@0:             if (precisely_negative(span.fT - fromSpan.fT)) {
michael@0:                 continue;
michael@0:             }
michael@0:             return to;
michael@0:         }
michael@0:     }
michael@0:     return -1;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
michael@0:         int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
michael@0:     int deltaSum = spanSign(index, endIndex);
michael@0:     int oppDeltaSum = oppSign(index, endIndex);
michael@0:     if (operand()) {
michael@0:         *maxWinding = *sumSuWinding;
michael@0:         *sumWinding = *sumSuWinding -= deltaSum;
michael@0:         *oppMaxWinding = *sumMiWinding;
michael@0:         *oppSumWinding = *sumMiWinding -= oppDeltaSum;
michael@0:     } else {
michael@0:         *maxWinding = *sumMiWinding;
michael@0:         *sumWinding = *sumMiWinding -= deltaSum;
michael@0:         *oppMaxWinding = *sumSuWinding;
michael@0:         *oppSumWinding = *sumSuWinding -= oppDeltaSum;
michael@0:     }
michael@0:     SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
michael@0:     SkASSERT(abs(*oppSumWinding) <= SkPathOpsDebug::gMaxWindSum);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding,
michael@0:         int* maxWinding, int* sumWinding) {
michael@0:     int deltaSum = spanSign(index, endIndex);
michael@0:     *maxWinding = *sumMiWinding;
michael@0:     *sumWinding = *sumMiWinding -= deltaSum;
michael@0:     SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
michael@0: }
michael@0: 
michael@0: // This marks all spans unsortable so that this info is available for early
michael@0: // exclusion in find top and others. This could be optimized to only mark
michael@0: // adjacent spans that unsortable. However, this makes it difficult to later
michael@0: // determine starting points for edge detection in find top and the like.
michael@0: bool SkOpSegment::SortAngles(const SkTArray<SkOpAngle, true>& angles,
michael@0:                              SkTArray<SkOpAngle*, true>* angleList,
michael@0:                              SortAngleKind orderKind) {
michael@0:     bool sortable = true;
michael@0:     int angleCount = angles.count();
michael@0:     int angleIndex;
michael@0:     for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
michael@0:         const SkOpAngle& angle = angles[angleIndex];
michael@0:         angleList->push_back(const_cast<SkOpAngle*>(&angle));
michael@0: #if DEBUG_ANGLE
michael@0:         (*(angleList->end() - 1))->setID(angleIndex);
michael@0: #endif
michael@0:         sortable &= !(angle.unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
michael@0:                     && angle.unorderable()));
michael@0:     }
michael@0:     if (sortable) {
michael@0:         SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
michael@0:         for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
michael@0:             if (angles[angleIndex].unsortable() || (orderKind == kMustBeOrdered_SortAngleKind
michael@0:                         && angles[angleIndex].unorderable())) {
michael@0:                 sortable = false;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     if (!sortable) {
michael@0:         for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
michael@0:             const SkOpAngle& angle = angles[angleIndex];
michael@0:             angle.segment()->markUnsortable(angle.start(), angle.end());
michael@0:         }
michael@0:     }
michael@0:     return sortable;
michael@0: }
michael@0: 
michael@0: // set segments to unsortable if angle is unsortable, but do not set all angles
michael@0: // note that for a simple 4 way crossing, two of the edges may be orderable even though
michael@0: // two edges are too short to be orderable.
michael@0: // perhaps some classes of unsortable angles should make all shared angles unsortable, but
michael@0: // simple lines that have tiny crossings are always sortable on the large ends
michael@0: // OPTIMIZATION: check earlier when angles are added to input if any are unsortable
michael@0: // may make sense then to mark all segments in angle sweep as unsortableStart/unsortableEnd
michael@0: // solely for the purpose of short-circuiting future angle building around this center
michael@0: bool SkOpSegment::SortAngles2(const SkTArray<SkOpAngle, true>& angles,
michael@0:                               SkTArray<SkOpAngle*, true>* angleList) {
michael@0:     int angleCount = angles.count();
michael@0:     int angleIndex;
michael@0:     for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
michael@0:         const SkOpAngle& angle = angles[angleIndex];
michael@0:         if (angle.unsortable()) {
michael@0:             return false;
michael@0:         }
michael@0:         angleList->push_back(const_cast<SkOpAngle*>(&angle));
michael@0: #if DEBUG_ANGLE
michael@0:         (*(angleList->end() - 1))->setID(angleIndex);
michael@0: #endif
michael@0:     }
michael@0:     SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
michael@0:     // at this point angles are sorted but individually may not be orderable
michael@0:     // this means that only adjcent orderable segments may transfer winding
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: // return true if midpoints were computed
michael@0: bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
michael@0:     SkASSERT(start != end);
michael@0:     edge[0] = fTs[start].fPt;
michael@0:     int points = SkPathOpsVerbToPoints(fVerb);
michael@0:     edge[points] = fTs[end].fPt;
michael@0:     if (fVerb == SkPath::kLine_Verb) {
michael@0:         return false;
michael@0:     }
michael@0:     double startT = fTs[start].fT;
michael@0:     double endT = fTs[end].fT;
michael@0:     if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
michael@0:         // don't compute midpoints if we already have them
michael@0:         if (fVerb == SkPath::kQuad_Verb) {
michael@0:             edge[1] = fPts[1];
michael@0:             return false;
michael@0:         }
michael@0:         SkASSERT(fVerb == SkPath::kCubic_Verb);
michael@0:         if (start < end) {
michael@0:             edge[1] = fPts[1];
michael@0:             edge[2] = fPts[2];
michael@0:             return false;
michael@0:         }
michael@0:         edge[1] = fPts[2];
michael@0:         edge[2] = fPts[1];
michael@0:         return false;
michael@0:     }
michael@0:     const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }};
michael@0:     if (fVerb == SkPath::kQuad_Verb) {
michael@0:         edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint();
michael@0:     } else {
michael@0:         SkASSERT(fVerb == SkPath::kCubic_Verb);
michael@0:         SkDPoint ctrl[2];
michael@0:         SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl);
michael@0:         edge[1] = ctrl[0].asSkPoint();
michael@0:         edge[2] = ctrl[1].asSkPoint();
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: // return true if midpoints were computed
michael@0: bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
michael@0:     SkASSERT(start != end);
michael@0:     (*result)[0].set(fTs[start].fPt);
michael@0:     int points = SkPathOpsVerbToPoints(fVerb);
michael@0:     (*result)[points].set(fTs[end].fPt);
michael@0:     if (fVerb == SkPath::kLine_Verb) {
michael@0:         return false;
michael@0:     }
michael@0:     double startT = fTs[start].fT;
michael@0:     double endT = fTs[end].fT;
michael@0:     if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
michael@0:         // don't compute midpoints if we already have them
michael@0:         if (fVerb == SkPath::kQuad_Verb) {
michael@0:             (*result)[1].set(fPts[1]);
michael@0:             return false;
michael@0:         }
michael@0:         SkASSERT(fVerb == SkPath::kCubic_Verb);
michael@0:         if (start < end) {
michael@0:             (*result)[1].set(fPts[1]);
michael@0:             (*result)[2].set(fPts[2]);
michael@0:             return false;
michael@0:         }
michael@0:         (*result)[1].set(fPts[2]);
michael@0:         (*result)[2].set(fPts[1]);
michael@0:         return false;
michael@0:     }
michael@0:     if (fVerb == SkPath::kQuad_Verb) {
michael@0:         (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT);
michael@0:     } else {
michael@0:         SkASSERT(fVerb == SkPath::kCubic_Verb);
michael@0:         SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]);
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
michael@0:     SkPoint edge[4];
michael@0:     subDivide(start, end, edge);
michael@0:     (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt,
michael@0:         const SkPoint& startPt) {
michael@0:     int outCount = outsidePts->count();
michael@0:     if (outCount == 0 || endPt != (*outsidePts)[outCount - 2]) {
michael@0:         outsidePts->push_back(endPt);
michael@0:         outsidePts->push_back(startPt);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoint& startPt) {
michael@0:     int outCount = outsidePts->count();
michael@0:     if (outCount == 0 || startPt != (*outsidePts)[outCount - 1]) {
michael@0:         outsidePts->push_back(startPt);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkOpSegment::undoneSpan(int* start, int* end) {
michael@0:     size_t tCount = fTs.count();
michael@0:     size_t index;
michael@0:     for (index = 0; index < tCount; ++index) {
michael@0:         if (!fTs[index].fDone) {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(index < tCount - 1);
michael@0:     *start = index;
michael@0:     double startT = fTs[index].fT;
michael@0:     while (approximately_negative(fTs[++index].fT - startT))
michael@0:         SkASSERT(index < tCount);
michael@0:     SkASSERT(index < tCount);
michael@0:     *end = index;
michael@0: }
michael@0: 
michael@0: int SkOpSegment::updateOppWinding(int index, int endIndex) const {
michael@0:     int lesser = SkMin32(index, endIndex);
michael@0:     int oppWinding = oppSum(lesser);
michael@0:     int oppSpanWinding = oppSign(index, endIndex);
michael@0:     if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
michael@0:             && oppWinding != SK_MaxS32) {
michael@0:         oppWinding -= oppSpanWinding;
michael@0:     }
michael@0:     return oppWinding;
michael@0: }
michael@0: 
michael@0: int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
michael@0:     int startIndex = angle->start();
michael@0:     int endIndex = angle->end();
michael@0:     return updateOppWinding(endIndex, startIndex);
michael@0: }
michael@0: 
michael@0: int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
michael@0:     int startIndex = angle->start();
michael@0:     int endIndex = angle->end();
michael@0:     return updateOppWinding(startIndex, endIndex);
michael@0: }
michael@0: 
michael@0: int SkOpSegment::updateWinding(int index, int endIndex) const {
michael@0:     int lesser = SkMin32(index, endIndex);
michael@0:     int winding = windSum(lesser);
michael@0:     int spanWinding = spanSign(index, endIndex);
michael@0:     if (winding && UseInnerWinding(winding - spanWinding, winding)
michael@0:             && winding != SK_MaxS32) {
michael@0:         winding -= spanWinding;
michael@0:     }
michael@0:     return winding;
michael@0: }
michael@0: 
michael@0: int SkOpSegment::updateWinding(const SkOpAngle* angle) const {
michael@0:     int startIndex = angle->start();
michael@0:     int endIndex = angle->end();
michael@0:     return updateWinding(endIndex, startIndex);
michael@0: }
michael@0: 
michael@0: int SkOpSegment::updateWindingReverse(int index, int endIndex) const {
michael@0:     int lesser = SkMin32(index, endIndex);
michael@0:     int winding = windSum(lesser);
michael@0:     int spanWinding = spanSign(endIndex, index);
michael@0:     if (winding && UseInnerWindingReverse(winding - spanWinding, winding)
michael@0:             && winding != SK_MaxS32) {
michael@0:         winding -= spanWinding;
michael@0:     }
michael@0:     return winding;
michael@0: }
michael@0: 
michael@0: int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const {
michael@0:     int startIndex = angle->start();
michael@0:     int endIndex = angle->end();
michael@0:     return updateWindingReverse(endIndex, startIndex);
michael@0: }
michael@0: 
michael@0: // OPTIMIZATION: does the following also work, and is it any faster?
michael@0: // return outerWinding * innerWinding > 0
michael@0: //      || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
michael@0: bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
michael@0:     SkASSERT(outerWinding != SK_MaxS32);
michael@0:     SkASSERT(innerWinding != SK_MaxS32);
michael@0:     int absOut = abs(outerWinding);
michael@0:     int absIn = abs(innerWinding);
michael@0:     bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: bool SkOpSegment::UseInnerWindingReverse(int outerWinding, int innerWinding) {
michael@0:     SkASSERT(outerWinding != SK_MaxS32);
michael@0:     SkASSERT(innerWinding != SK_MaxS32);
michael@0:     int absOut = abs(outerWinding);
michael@0:     int absIn = abs(innerWinding);
michael@0:     bool result = absOut == absIn ? true : absOut < absIn;
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const {
michael@0:     if (approximately_zero(tHit - t(tIndex))) {  // if we hit the end of a span, disregard
michael@0:         return SK_MinS32;
michael@0:     }
michael@0:     int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);
michael@0:     SkASSERT(winding != SK_MinS32);
michael@0:     int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
michael@0: #if DEBUG_WINDING_AT_T
michael@0:     SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal);
michael@0: #endif
michael@0:     // see if a + change in T results in a +/- change in X (compute x'(T))
michael@0:     *dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
michael@0:     if (fVerb > SkPath::kLine_Verb && approximately_zero(*dx)) {
michael@0:         *dx = fPts[2].fX - fPts[1].fX - *dx;
michael@0:     }
michael@0:     if (*dx == 0) {
michael@0: #if DEBUG_WINDING_AT_T
michael@0:         SkDebugf(" dx=0 winding=SK_MinS32\n");
michael@0: #endif
michael@0:         return SK_MinS32;
michael@0:     }
michael@0:     if (windVal < 0) {  // reverse sign if opp contour traveled in reverse
michael@0:             *dx = -*dx;
michael@0:     }
michael@0:     if (winding * *dx > 0) {  // if same signs, result is negative
michael@0:         winding += *dx > 0 ? -windVal : windVal;
michael@0:     }
michael@0: #if DEBUG_WINDING_AT_T
michael@0:     SkDebugf(" dx=%c winding=%d\n", *dx > 0 ? '+' : '-', winding);
michael@0: #endif
michael@0:     return winding;
michael@0: }
michael@0: 
michael@0: int SkOpSegment::windSum(const SkOpAngle* angle) const {
michael@0:     int start = angle->start();
michael@0:     int end = angle->end();
michael@0:     int index = SkMin32(start, end);
michael@0:     return windSum(index);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::zeroSpan(SkOpSpan* span) {
michael@0:     SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
michael@0:     span->fWindValue = 0;
michael@0:     span->fOppValue = 0;
michael@0:     if (span->fTiny || span->fSmall) {
michael@0:         return;
michael@0:     }
michael@0:     SkASSERT(!span->fDone);
michael@0:     span->fDone = true;
michael@0:     ++fDoneSpans;
michael@0: }
michael@0: 
michael@0: #if DEBUG_SWAP_TOP
michael@0: bool SkOpSegment::controlsContainedByEnds(int tStart, int tEnd) const {
michael@0:     if (fVerb != SkPath::kCubic_Verb) {
michael@0:         return false;
michael@0:     }
michael@0:     SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
michael@0:     return dst.controlsContainedByEnds();
michael@0: }
michael@0: #endif
michael@0: 
michael@0: #if DEBUG_CONCIDENT
michael@0: // SkASSERT if pair has not already been added
michael@0: void SkOpSegment::debugAddTPair(double t, const SkOpSegment& other, double otherT) const {
michael@0:     for (int i = 0; i < fTs.count(); ++i) {
michael@0:         if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) {
michael@0:             return;
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(0);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: #if DEBUG_CONCIDENT
michael@0: void SkOpSegment::debugShowTs(const char* prefix) const {
michael@0:     SkDebugf("%s %s id=%d", __FUNCTION__, prefix, fID);
michael@0:     int lastWind = -1;
michael@0:     int lastOpp = -1;
michael@0:     double lastT = -1;
michael@0:     int i;
michael@0:     for (i = 0; i < fTs.count(); ++i) {
michael@0:         bool change = lastT != fTs[i].fT || lastWind != fTs[i].fWindValue
michael@0:                 || lastOpp != fTs[i].fOppValue;
michael@0:         if (change && lastWind >= 0) {
michael@0:             SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
michael@0:                     lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
michael@0:         }
michael@0:         if (change) {
michael@0:             SkDebugf(" [o=%d", fTs[i].fOther->fID);
michael@0:             lastWind = fTs[i].fWindValue;
michael@0:             lastOpp = fTs[i].fOppValue;
michael@0:             lastT = fTs[i].fT;
michael@0:         } else {
michael@0:             SkDebugf(",%d", fTs[i].fOther->fID);
michael@0:         }
michael@0:     }
michael@0:     if (i <= 0) {
michael@0:         return;
michael@0:     }
michael@0:     SkDebugf(" t=%1.3g %1.9g,%1.9g w=%d o=%d]",
michael@0:             lastT, xyAtT(i - 1).fX, xyAtT(i - 1).fY, lastWind, lastOpp);
michael@0:     if (fOperand) {
michael@0:         SkDebugf(" operand");
michael@0:     }
michael@0:     if (done()) {
michael@0:         SkDebugf(" done");
michael@0:     }
michael@0:     SkDebugf("\n");
michael@0: }
michael@0: #endif
michael@0: 
michael@0: #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
michael@0: void SkOpSegment::debugShowActiveSpans() const {
michael@0:     debugValidate();
michael@0:     if (done()) {
michael@0:         return;
michael@0:     }
michael@0: #if DEBUG_ACTIVE_SPANS_SHORT_FORM
michael@0:     int lastId = -1;
michael@0:     double lastT = -1;
michael@0: #endif
michael@0:     for (int i = 0; i < fTs.count(); ++i) {
michael@0:         if (fTs[i].fDone) {
michael@0:             continue;
michael@0:         }
michael@0:         SkASSERT(i < fTs.count() - 1);
michael@0: #if DEBUG_ACTIVE_SPANS_SHORT_FORM
michael@0:         if (lastId == fID && lastT == fTs[i].fT) {
michael@0:             continue;
michael@0:         }
michael@0:         lastId = fID;
michael@0:         lastT = fTs[i].fT;
michael@0: #endif
michael@0:         SkDebugf("%s id=%d", __FUNCTION__, fID);
michael@0:         SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
michael@0:         for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
michael@0:             SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
michael@0:         }
michael@0:         const SkOpSpan* span = &fTs[i];
michael@0:         SkDebugf(") t=%1.9g (%1.9g,%1.9g)", span->fT, xAtT(span), yAtT(span));
michael@0:         int iEnd = i + 1;
michael@0:         while (fTs[iEnd].fT < 1 && approximately_equal(fTs[i].fT, fTs[iEnd].fT)) {
michael@0:             ++iEnd;
michael@0:         }
michael@0:         SkDebugf(" tEnd=%1.9g", fTs[iEnd].fT);
michael@0:         const SkOpSegment* other = fTs[i].fOther;
michael@0:         SkDebugf(" other=%d otherT=%1.9g otherIndex=%d windSum=",
michael@0:                 other->fID, fTs[i].fOtherT, fTs[i].fOtherIndex);
michael@0:         if (fTs[i].fWindSum == SK_MinS32) {
michael@0:             SkDebugf("?");
michael@0:         } else {
michael@0:             SkDebugf("%d", fTs[i].fWindSum);
michael@0:         }
michael@0:         SkDebugf(" windValue=%d oppValue=%d\n", fTs[i].fWindValue, fTs[i].fOppValue);
michael@0:     }
michael@0: }
michael@0: #endif
michael@0: 
michael@0: 
michael@0: #if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
michael@0: void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding) {
michael@0:     const SkPoint& pt = xyAtT(&span);
michael@0:     SkDebugf("%s id=%d", fun, fID);
michael@0:     SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
michael@0:     for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
michael@0:         SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
michael@0:     }
michael@0:     SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
michael@0:             fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
michael@0:     SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d windSum=",
michael@0:             span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
michael@0:             (&span)[1].fT, winding);
michael@0:     if (span.fWindSum == SK_MinS32) {
michael@0:         SkDebugf("?");
michael@0:     } else {
michael@0:         SkDebugf("%d", span.fWindSum);
michael@0:     }
michael@0:     SkDebugf(" windValue=%d\n", span.fWindValue);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding,
michael@0:                                       int oppWinding) {
michael@0:     const SkPoint& pt = xyAtT(&span);
michael@0:     SkDebugf("%s id=%d", fun, fID);
michael@0:     SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY);
michael@0:     for (int vIndex = 1; vIndex <= SkPathOpsVerbToPoints(fVerb); ++vIndex) {
michael@0:         SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY);
michael@0:     }
michael@0:     SkASSERT(&span == &span.fOther->fTs[span.fOtherIndex].fOther->
michael@0:             fTs[span.fOther->fTs[span.fOtherIndex].fOtherIndex]);
michael@0:     SkDebugf(") t=%1.9g [%d] (%1.9g,%1.9g) tEnd=%1.9g newWindSum=%d newOppSum=%d oppSum=",
michael@0:             span.fT, span.fOther->fTs[span.fOtherIndex].fOtherIndex, pt.fX, pt.fY,
michael@0:             (&span)[1].fT, winding, oppWinding);
michael@0:     if (span.fOppSum == SK_MinS32) {
michael@0:         SkDebugf("?");
michael@0:     } else {
michael@0:         SkDebugf("%d", span.fOppSum);
michael@0:     }
michael@0:     SkDebugf(" windSum=");
michael@0:     if (span.fWindSum == SK_MinS32) {
michael@0:         SkDebugf("?");
michael@0:     } else {
michael@0:         SkDebugf("%d", span.fWindSum);
michael@0:     }
michael@0:     SkDebugf(" windValue=%d\n", span.fWindValue);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: #if DEBUG_SORT || DEBUG_SWAP_TOP
michael@0: void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
michael@0:                                 int first, const int contourWinding,
michael@0:                                 const int oppContourWinding, bool sortable) const {
michael@0:     if (--SkPathOpsDebug::gSortCount < 0) {
michael@0:         return;
michael@0:     }
michael@0:     if (!sortable) {
michael@0:         if (angles.count() == 0) {
michael@0:             return;
michael@0:         }
michael@0:         if (first < 0) {
michael@0:             first = 0;
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(angles[first]->segment() == this);
michael@0:     SkASSERT(!sortable || angles.count() > 1);
michael@0:     int lastSum = contourWinding;
michael@0:     int oppLastSum = oppContourWinding;
michael@0:     const SkOpAngle* firstAngle = angles[first];
michael@0:     int windSum = lastSum - spanSign(firstAngle);
michael@0:     int oppoSign = oppSign(firstAngle);
michael@0:     int oppWindSum = oppLastSum - oppoSign;
michael@0:     #define WIND_AS_STRING(x) char x##Str[12]; \
michael@0:             if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \
michael@0:             else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
michael@0:     WIND_AS_STRING(contourWinding);
michael@0:     WIND_AS_STRING(oppContourWinding);
michael@0:     SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__,
michael@0:             contourWindingStr, oppContourWindingStr, spanSign(angles[first]));
michael@0:     int index = first;
michael@0:     bool firstTime = true;
michael@0:     do {
michael@0:         const SkOpAngle& angle = *angles[index];
michael@0:         const SkOpSegment& segment = *angle.segment();
michael@0:         int start = angle.start();
michael@0:         int end = angle.end();
michael@0:         const SkOpSpan& sSpan = segment.fTs[start];
michael@0:         const SkOpSpan& eSpan = segment.fTs[end];
michael@0:         const SkOpSpan& mSpan = segment.fTs[SkMin32(start, end)];
michael@0:         bool opp = segment.fOperand ^ fOperand;
michael@0:         if (!firstTime) {
michael@0:             oppoSign = segment.oppSign(&angle);
michael@0:             if (opp) {
michael@0:                 oppLastSum = oppWindSum;
michael@0:                 oppWindSum -= segment.spanSign(&angle);
michael@0:                 if (oppoSign) {
michael@0:                     lastSum = windSum;
michael@0:                     windSum -= oppoSign;
michael@0:                 }
michael@0:             } else {
michael@0:                 lastSum = windSum;
michael@0:                 windSum -= segment.spanSign(&angle);
michael@0:                 if (oppoSign) {
michael@0:                     oppLastSum = oppWindSum;
michael@0:                     oppWindSum -= oppoSign;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:         SkDebugf("%s [%d] %s", __FUNCTION__, index,
michael@0:                 angle.unsortable() ? "*** UNSORTABLE *** " : "");
michael@0:     #if DEBUG_SORT_COMPACT
michael@0:         SkDebugf("id=%d %s start=%d (%1.9g,%1.9g) end=%d (%1.9g,%1.9g)",
michael@0:                 segment.fID, kLVerbStr[SkPathOpsVerbToPoints(segment.fVerb)],
michael@0:                 start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end,
michael@0:                 segment.xAtT(&eSpan), segment.yAtT(&eSpan));
michael@0:     #else
michael@0:         switch (segment.fVerb) {
michael@0:             case SkPath::kLine_Verb:
michael@0:                 SkDebugf(LINE_DEBUG_STR, LINE_DEBUG_DATA(segment.fPts));
michael@0:                 break;
michael@0:             case SkPath::kQuad_Verb:
michael@0:                 SkDebugf(QUAD_DEBUG_STR, QUAD_DEBUG_DATA(segment.fPts));
michael@0:                 break;
michael@0:             case SkPath::kCubic_Verb:
michael@0:                 SkDebugf(CUBIC_DEBUG_STR, CUBIC_DEBUG_DATA(segment.fPts));
michael@0:                 break;
michael@0:             default:
michael@0:                 SkASSERT(0);
michael@0:         }
michael@0:         SkDebugf(" tStart=%1.9g tEnd=%1.9g", sSpan.fT, eSpan.fT);
michael@0:     #endif
michael@0:         SkDebugf(" sign=%d windValue=%d windSum=", angle.sign(), mSpan.fWindValue);
michael@0:         SkPathOpsDebug::WindingPrintf(mSpan.fWindSum);
michael@0:         int last, wind;
michael@0:         if (opp) {
michael@0:             last = oppLastSum;
michael@0:             wind = oppWindSum;
michael@0:         } else {
michael@0:             last = lastSum;
michael@0:             wind = windSum;
michael@0:         }
michael@0:         bool useInner = SkPathOpsDebug::ValidWind(last) && SkPathOpsDebug::ValidWind(wind)
michael@0:                 && UseInnerWinding(last, wind);
michael@0:         WIND_AS_STRING(last);
michael@0:         WIND_AS_STRING(wind);
michael@0:         WIND_AS_STRING(lastSum);
michael@0:         WIND_AS_STRING(oppLastSum);
michael@0:         WIND_AS_STRING(windSum);
michael@0:         WIND_AS_STRING(oppWindSum);
michael@0:         #undef WIND_AS_STRING
michael@0:         if (!oppoSign) {
michael@0:             SkDebugf(" %s->%s (max=%s)", lastStr, windStr, useInner ? windStr : lastStr);
michael@0:         } else {
michael@0:             SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr,
michael@0:                     opp ? windSumStr : oppWindSumStr);
michael@0:         }
michael@0:         SkDebugf(" done=%d unord=%d small=%d tiny=%d opp=%d\n",
michael@0:                 mSpan.fDone, angle.unorderable(), mSpan.fSmall, mSpan.fTiny, opp);
michael@0:         ++index;
michael@0:         if (index == angles.count()) {
michael@0:             index = 0;
michael@0:         }
michael@0:         if (firstTime) {
michael@0:             firstTime = false;
michael@0:         }
michael@0:     } while (index != first);
michael@0: }
michael@0: 
michael@0: void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
michael@0:                                 int first, bool sortable) {
michael@0:     if (!sortable) {
michael@0:         if (angles.count() == 0) {
michael@0:             return;
michael@0:         }
michael@0:         if (first < 0) {
michael@0:             first = 0;
michael@0:         }
michael@0:     }
michael@0:     const SkOpAngle* firstAngle = angles[first];
michael@0:     const SkOpSegment* segment = firstAngle->segment();
michael@0:     int winding = segment->updateWinding(firstAngle);
michael@0:     int oppWinding = segment->updateOppWinding(firstAngle);
michael@0:     debugShowSort(fun, angles, first, winding, oppWinding, sortable);
michael@0: }
michael@0: 
michael@0: #endif
michael@0: 
michael@0: #if DEBUG_SHOW_WINDING
michael@0: int SkOpSegment::debugShowWindingValues(int slotCount, int ofInterest) const {
michael@0:     if (!(1 << fID & ofInterest)) {
michael@0:         return 0;
michael@0:     }
michael@0:     int sum = 0;
michael@0:     SkTArray<char, true> slots(slotCount * 2);
michael@0:     memset(slots.begin(), ' ', slotCount * 2);
michael@0:     for (int i = 0; i < fTs.count(); ++i) {
michael@0:    //     if (!(1 << fTs[i].fOther->fID & ofInterest)) {
michael@0:    //         continue;
michael@0:    //     }
michael@0:         sum += fTs[i].fWindValue;
michael@0:         slots[fTs[i].fOther->fID - 1] = as_digit(fTs[i].fWindValue);
michael@0:         sum += fTs[i].fOppValue;
michael@0:         slots[slotCount + fTs[i].fOther->fID - 1] = as_digit(fTs[i].fOppValue);
michael@0:     }
michael@0:     SkDebugf("%s id=%2d %.*s | %.*s\n", __FUNCTION__, fID, slotCount, slots.begin(), slotCount,
michael@0:             slots.begin() + slotCount);
michael@0:     return sum;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: void SkOpSegment::debugValidate() const {
michael@0: #if DEBUG_VALIDATE
michael@0:     int count = fTs.count();
michael@0:     SkASSERT(count >= 2);
michael@0:     SkASSERT(fTs[0].fT == 0);
michael@0:     SkASSERT(fTs[count - 1].fT == 1);
michael@0:     int done = 0;
michael@0:     double t = -1;
michael@0:     for (int i = 0; i < count; ++i) {
michael@0:         const SkOpSpan& span = fTs[i];
michael@0:         SkASSERT(t <= span.fT);
michael@0:         t = span.fT;
michael@0:         int otherIndex = span.fOtherIndex;
michael@0:         const SkOpSegment* other = span.fOther;
michael@0:         const SkOpSpan& otherSpan = other->fTs[otherIndex];
michael@0:         SkASSERT(otherSpan.fPt == span.fPt);
michael@0:         SkASSERT(otherSpan.fOtherT == t);
michael@0:         SkASSERT(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]);
michael@0:         done += span.fDone;
michael@0:     }
michael@0:     SkASSERT(done == fDoneSpans);
michael@0: #endif
michael@0: }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0: void SkOpSegment::dumpPts() const {
michael@0:     int last = SkPathOpsVerbToPoints(fVerb);
michael@0:     SkDebugf("{{");
michael@0:     int index = 0;
michael@0:     do {
michael@0:         SkDPoint::dump(fPts[index]);
michael@0:         SkDebugf(", ");
michael@0:     } while (++index < last);
michael@0:     SkDPoint::dump(fPts[index]);
michael@0:     SkDebugf("}}\n");
michael@0: }
michael@0: 
michael@0: void SkOpSegment::dumpDPts() const {
michael@0:     int count = SkPathOpsVerbToPoints(fVerb);
michael@0:     SkDebugf("{{");
michael@0:     int index = 0;
michael@0:     do {
michael@0:         SkDPoint dPt = {fPts[index].fX, fPts[index].fY};
michael@0:         dPt.dump();
michael@0:         if (index != count) {
michael@0:             SkDebugf(", ");
michael@0:         }
michael@0:     } while (++index <= count);
michael@0:     SkDebugf("}}\n");
michael@0: }
michael@0: 
michael@0: void SkOpSegment::dumpSpans() const {
michael@0:     int count = this->count();
michael@0:     for (int index = 0; index < count; ++index) {
michael@0:         const SkOpSpan& span = this->span(index);
michael@0:         SkDebugf("[%d] ", index);
michael@0:         span.dump();
michael@0:     }
michael@0: }
michael@0: #endif