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