| /* |
| * 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 "SkOpContour.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 |
| }; |
| |
| const SkOpAngle* SkOpSegment::activeAngle(int index, int* start, int* end, bool* done, |
| bool* sortable) const { |
| if (const SkOpAngle* result = activeAngleInner(index, start, end, done, sortable)) { |
| return result; |
| } |
| double referenceT = fTs[index].fT; |
| int lesser = index; |
| while (--lesser >= 0 |
| && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) { |
| if (const SkOpAngle* result = activeAngleOther(lesser, start, end, done, sortable)) { |
| return result; |
| } |
| } |
| do { |
| if (const SkOpAngle* result = activeAngleOther(index, start, end, done, sortable)) { |
| return result; |
| } |
| if (++index == fTs.count()) { |
| break; |
| } |
| if (fTs[index - 1].fTiny) { |
| referenceT = fTs[index].fT; |
| continue; |
| } |
| } while (precisely_negative(fTs[index].fT - referenceT)); |
| return NULL; |
| } |
| |
| const SkOpAngle* SkOpSegment::activeAngleInner(int index, int* start, int* end, bool* done, |
| bool* sortable) const { |
| int next = nextExactSpan(index, 1); |
| if (next > 0) { |
| const SkOpSpan& upSpan = fTs[index]; |
| if (upSpan.fWindValue || upSpan.fOppValue) { |
| if (*end < 0) { |
| *start = index; |
| *end = next; |
| } |
| if (!upSpan.fDone) { |
| if (upSpan.fWindSum != SK_MinS32) { |
| return spanToAngle(index, next); |
| } |
| *done = false; |
| } |
| } else { |
| SkASSERT(upSpan.fDone); |
| } |
| } |
| int prev = nextExactSpan(index, -1); |
| // edge leading into junction |
| if (prev >= 0) { |
| const SkOpSpan& downSpan = fTs[prev]; |
| if (downSpan.fWindValue || downSpan.fOppValue) { |
| if (*end < 0) { |
| *start = index; |
| *end = prev; |
| } |
| if (!downSpan.fDone) { |
| if (downSpan.fWindSum != SK_MinS32) { |
| return spanToAngle(index, prev); |
| } |
| *done = false; |
| } |
| } else { |
| SkASSERT(downSpan.fDone); |
| } |
| } |
| return NULL; |
| } |
| |
| const SkOpAngle* SkOpSegment::activeAngleOther(int index, int* start, int* end, bool* done, |
| bool* sortable) const { |
| const SkOpSpan* span = &fTs[index]; |
| SkOpSegment* other = span->fOther; |
| int oIndex = span->fOtherIndex; |
| return other->activeAngleInner(oIndex, start, end, done, sortable); |
| } |
| |
| SkPoint SkOpSegment::activeLeftTop(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; |
| double lastT = -1; |
| for (int index = 0; index < count; ++index) { |
| const SkOpSpan& span = fTs[index]; |
| 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; |
| } |
| 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 DEBUG_LIMIT_WIND_SUM |
| SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM); |
| SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM); |
| #endif |
| if (fOperand) { |
| SkTSwap<int>(sumMiWinding, sumSuWinding); |
| } |
| return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding); |
| } |
| |
| bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op, |
| int* sumMiWinding, int* sumSuWinding) { |
| int maxWinding, sumWinding, oppMaxWinding, 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 id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", |
| __FUNCTION__, debugID(), span(index).fT, span(endIndex).fT, |
| SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); |
| #endif |
| return result; |
| } |
| |
| bool SkOpSegment::activeWinding(int index, int endIndex) { |
| int sumWinding = updateWinding(endIndex, index); |
| return activeWinding(index, endIndex, &sumWinding); |
| } |
| |
| bool SkOpSegment::activeWinding(int index, int endIndex, int* sumWinding) { |
| int maxWinding; |
| setUpWinding(index, endIndex, &maxWinding, sumWinding); |
| bool from = maxWinding != 0; |
| bool to = *sumWinding != 0; |
| bool result = gUnaryActiveEdge[from][to]; |
| return result; |
| } |
| |
| 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 |
| SkPoint copy = fTs[tIndexStart].fPt; // add t pair may move the point array |
| addTPair(fTs[tIndexStart].fT, other, other->fTs[oIndex].fT, false, copy); |
| } |
| 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 |
| SkPoint copy = fTs[tIndex].fPt; // add t pair may move the point array |
| addTPair(fTs[tIndex].fT, other, other->fTs[oIndexStart].fT, false, copy); |
| } |
| } 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); |
| int ttIndex = tIndex; |
| bool checkOtherTMatch = false; |
| do { |
| const SkOpSpan& span = fTs[ttIndex]; |
| if (startPt != span.fPt) { |
| break; |
| } |
| if (span.fOther == other && span.fPt == startPt) { |
| checkOtherTMatch = true; |
| break; |
| } |
| } while (++ttIndex < count()); |
| do { |
| ++oIndex; |
| } while (startPt != other->fTs[oIndex].fPt); |
| bool skipAdd = false; |
| if (checkOtherTMatch) { |
| int ooIndex = oIndex; |
| do { |
| const SkOpSpan& oSpan = other->fTs[ooIndex]; |
| if (startPt != oSpan.fPt) { |
| break; |
| } |
| if (oSpan.fT == fTs[ttIndex].fOtherT) { |
| skipAdd = true; |
| break; |
| } |
| } while (++ooIndex < other->count()); |
| } |
| if ((tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) && !skipAdd) { |
| 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); |
| const SkPoint* oWorkPt; |
| do { |
| oWorkPt = &other->fTs[++oIndex].fPt; |
| } while (nextPt == *oWorkPt); |
| nextPt = *workPt; |
| double tStart = fTs[tIndex].fT; |
| double oStart = other->fTs[oIndex].fT; |
| if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) { |
| break; |
| } |
| if (*workPt == *oWorkPt) { |
| 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::addEndSpan(int endIndex) { |
| SkASSERT(span(endIndex).fT == 1 || (span(endIndex).fTiny |
| // && approximately_greater_than_one(span(endIndex).fT) |
| )); |
| int spanCount = fTs.count(); |
| int startIndex = endIndex - 1; |
| while (fTs[startIndex].fT == 1 || fTs[startIndex].fTiny) { |
| --startIndex; |
| SkASSERT(startIndex > 0); |
| --endIndex; |
| } |
| SkOpAngle& angle = fAngles.push_back(); |
| angle.set(this, spanCount - 1, startIndex); |
| #if DEBUG_ANGLE |
| debugCheckPointsEqualish(endIndex, spanCount); |
| #endif |
| setFromAngle(endIndex, &angle); |
| } |
| |
| void SkOpSegment::setFromAngle(int endIndex, SkOpAngle* angle) { |
| int spanCount = fTs.count(); |
| do { |
| fTs[endIndex].fFromAngle = angle; |
| } while (++endIndex < spanCount); |
| } |
| |
| 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); |
| } |
| |
| SkOpAngle* SkOpSegment::addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** anglePtr) { |
| int spanIndex = count() - 1; |
| int startIndex = nextExactSpan(spanIndex, -1); |
| SkASSERT(startIndex >= 0); |
| SkOpAngle& angle = fAngles.push_back(); |
| *anglePtr = ∠ |
| angle.set(this, spanIndex, startIndex); |
| setFromAngle(spanIndex, &angle); |
| SkOpSegment* other; |
| int oStartIndex, oEndIndex; |
| do { |
| const SkOpSpan& span = fTs[spanIndex]; |
| SkASSERT(span.fT > 0); |
| other = span.fOther; |
| oStartIndex = span.fOtherIndex; |
| oEndIndex = other->nextExactSpan(oStartIndex, 1); |
| if (oEndIndex > 0 && other->span(oStartIndex).fWindValue) { |
| break; |
| } |
| oEndIndex = oStartIndex; |
| oStartIndex = other->nextExactSpan(oEndIndex, -1); |
| --spanIndex; |
| } while (oStartIndex < 0 || !other->span(oStartIndex).fWindSum); |
| SkOpAngle& oAngle = other->fAngles.push_back(); |
| oAngle.set(other, oStartIndex, oEndIndex); |
| other->setToAngle(oEndIndex, &oAngle); |
| *otherPtr = other; |
| return &oAngle; |
| } |
| |
| SkOpAngle* SkOpSegment::addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** anglePtr) { |
| int endIndex = nextExactSpan(0, 1); |
| SkASSERT(endIndex > 0); |
| SkOpAngle& angle = fAngles.push_back(); |
| *anglePtr = ∠ |
| angle.set(this, 0, endIndex); |
| setToAngle(endIndex, &angle); |
| int spanIndex = 0; |
| SkOpSegment* other; |
| int oStartIndex, oEndIndex; |
| do { |
| const SkOpSpan& span = fTs[spanIndex]; |
| SkASSERT(span.fT < 1); |
| other = span.fOther; |
| oEndIndex = span.fOtherIndex; |
| oStartIndex = other->nextExactSpan(oEndIndex, -1); |
| if (oStartIndex >= 0 && other->span(oStartIndex).fWindValue) { |
| break; |
| } |
| oStartIndex = oEndIndex; |
| oEndIndex = other->nextExactSpan(oStartIndex, 1); |
| ++spanIndex; |
| } while (oEndIndex < 0 || !other->span(oStartIndex).fWindValue); |
| SkOpAngle& oAngle = other->fAngles.push_back(); |
| oAngle.set(other, oEndIndex, oStartIndex); |
| other->setFromAngle(oEndIndex, &oAngle); |
| *otherPtr = other; |
| return &oAngle; |
| } |
| |
| SkOpAngle* SkOpSegment::addSingletonAngles(int step) { |
| SkOpSegment* other; |
| SkOpAngle* angle, * otherAngle; |
| if (step > 0) { |
| otherAngle = addSingletonAngleUp(&other, &angle); |
| } else { |
| otherAngle = addSingletonAngleDown(&other, &angle); |
| } |
| angle->insert(otherAngle); |
| return angle; |
| } |
| |
| void SkOpSegment::addStartSpan(int endIndex) { |
| int index = 0; |
| SkOpAngle& angle = fAngles.push_back(); |
| angle.set(this, index, endIndex); |
| #if DEBUG_ANGLE |
| debugCheckPointsEqualish(index, endIndex); |
| #endif |
| setToAngle(endIndex, &angle); |
| } |
| |
| void SkOpSegment::setToAngle(int endIndex, SkOpAngle* angle) { |
| int index = 0; |
| do { |
| fTs[index].fToAngle = angle; |
| } while (++index < endIndex); |
| } |
| |
| // 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) { |
| SkASSERT(this != other || fVerb == SkPath::kCubic_Verb); |
| #if 0 // this needs an even rougher association to be useful |
| SkASSERT(SkDPoint::RoughlyEqual(ptAtT(newT), pt)); |
| #endif |
| const SkPoint& firstPt = fPts[0]; |
| const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)]; |
| SkASSERT(newT == 0 || !precisely_zero(newT)); |
| SkASSERT(newT == 1 || !precisely_equal(newT, 1)); |
| // FIXME: in the pathological case where there is a ton of intercepts, |
| // binary search? |
| int insertedAt = -1; |
| int tCount = fTs.count(); |
| for (int 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->fOtherT = -1; |
| 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->fFromAngle = NULL; |
| span->fToAngle = NULL; |
| span->fWindSum = SK_MinS32; |
| span->fOppSum = SK_MinS32; |
| span->fWindValue = 1; |
| span->fOppValue = 0; |
| span->fChased = false; |
| span->fCoincident = false; |
| span->fLoop = false; |
| span->fNear = false; |
| span->fMultiple = false; |
| span->fSmall = false; |
| span->fTiny = false; |
| if ((span->fDone = newT == 1)) { |
| ++fDoneSpans; |
| } |
| setSpanFlags(pt, newT, span); |
| return insertedAt; |
| } |
| |
| void SkOpSegment::setSpanFlags(const SkPoint& pt, double newT, SkOpSpan* span) { |
| int less = -1; |
| // FIXME: note that this relies on spans being a continguous array |
| // find range of spans with nearly the same point as this one |
| // FIXME: SkDPoint::ApproximatelyEqual is better but breaks tests at the moment |
| while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) { |
| if (fVerb == SkPath::kCubic_Verb) { |
| double tInterval = newT - span[less].fT; |
| double tMid = newT - tInterval / 2; |
| SkDPoint midPt = dcubic_xy_at_t(fPts, tMid); |
| if (!midPt.approximatelyEqual(xyAtT(span))) { |
| break; |
| } |
| } |
| --less; |
| } |
| int more = 1; |
| // FIXME: SkDPoint::ApproximatelyEqual is better but breaks tests at the moment |
| while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, pt)) { |
| if (fVerb == SkPath::kCubic_Verb) { |
| double tEndInterval = span[more].fT - newT; |
| double tMid = newT - tEndInterval / 2; |
| SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid); |
| if (!midEndPt.approximatelyEqual(xyAtT(span))) { |
| break; |
| } |
| } |
| ++more; |
| } |
| ++less; |
| --more; |
| while (more - 1 > less && span[more].fPt == span[more - 1].fPt |
| && span[more].fT == span[more - 1].fT) { |
| --more; |
| } |
| if (less == more) { |
| return; |
| } |
| if (precisely_negative(span[more].fT - span[less].fT)) { |
| return; |
| } |
| // if the total range of t values is big enough, mark all tiny |
| bool tiny = span[less].fPt == span[more].fPt; |
| int index = less; |
| do { |
| fSmall = span[index].fSmall = true; |
| fTiny |= span[index].fTiny = tiny; |
| if (!span[index].fDone) { |
| span[index].fDone = true; |
| ++fDoneSpans; |
| } |
| } while (++index < more); |
| return; |
| } |
| |
| void SkOpSegment::resetSpanFlags() { |
| fSmall = fTiny = false; |
| fDoneSpans = 0; |
| int start = 0; |
| int last = this->count() - 1; |
| do { |
| SkOpSpan* startSpan = &this->fTs[start]; |
| double startT = startSpan->fT; |
| startSpan->fSmall = startSpan->fTiny = false; // sets range initial |
| bool terminus = startT == 1; |
| if ((startSpan->fDone = !startSpan->fWindValue | terminus)) { |
| ++fDoneSpans; |
| } |
| ++start; // range initial + 1 |
| if (terminus) { |
| continue; |
| } |
| const SkPoint& pt = startSpan->fPt; |
| int end = start; // range initial + 1 |
| while (end <= last) { |
| const SkOpSpan& endSpan = this->span(end); |
| if (!AlmostEqualUlps(endSpan.fPt, pt)) { |
| break; |
| } |
| if (fVerb == SkPath::kCubic_Verb) { |
| double tMid = (startSpan->fT + endSpan.fT) / 2; |
| SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid); |
| if (!midEndPt.approximatelyEqual(xyAtT(startSpan))) { |
| break; |
| } |
| } |
| ++end; |
| } |
| if (start == end) { // end == range final + 1 |
| continue; |
| } |
| while (--end >= start) { // end == range final |
| const SkOpSpan& endSpan = this->span(end); |
| const SkOpSpan& priorSpan = this->span(end - 1); |
| if (endSpan.fPt != priorSpan.fPt || endSpan.fT != priorSpan.fT) { |
| break; // end == range final + 1 |
| } |
| } |
| if (end < start) { // end == range final + 1 |
| continue; |
| } |
| int index = start - 1; // index == range initial |
| start = end; // start = range final + 1 |
| const SkOpSpan& nextSpan = this->span(end); |
| if (precisely_negative(nextSpan.fT - startSpan->fT)) { |
| while (++index < end) { |
| startSpan = &this->fTs[index]; |
| startSpan->fSmall = startSpan->fTiny = false; // sets range initial + 1 |
| if ((startSpan->fDone = !startSpan->fWindValue)) { |
| ++fDoneSpans; |
| } |
| } |
| continue; |
| } |
| if (!startSpan->fWindValue) { |
| --fDoneSpans; // added back below |
| } |
| bool tiny = nextSpan.fPt == startSpan->fPt; |
| do { |
| fSmall = startSpan->fSmall = true; // sets range initial |
| fTiny |= startSpan->fTiny = tiny; |
| startSpan->fDone = true; |
| ++fDoneSpans; |
| startSpan = &this->fTs[++index]; |
| } while (index < end); // loop through tiny small range end (last) |
| } while (start <= last); |
| } |
| |
| // 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 && precisely_equal(fTs[index].fT, fTs[index - 1].fT)) { |
| --index; |
| } |
| bool oFoundEnd = false; |
| 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 || precisely_equal(oStartT, other->fTs[oIndex].fT)) { |
| if (!oIndex) { |
| return; // tiny spans may move in the wrong direction |
| } |
| } |
| SkOpSpan* test = &fTs[index]; |
| SkOpSpan* oTest = &other->fTs[oIndex]; |
| SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts; |
| SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts; |
| bool decrement, track, bigger; |
| int originalWindValue; |
| const SkPoint* testPt; |
| const SkPoint* oTestPt; |
| do { |
| SkASSERT(test->fT < 1); |
| SkASSERT(oTest->fT < 1); |
| decrement = test->fWindValue && oTest->fWindValue; |
| track = test->fWindValue || oTest->fWindValue; |
| bigger = test->fWindValue >= oTest->fWindValue; |
| testPt = &test->fPt; |
| double testT = test->fT; |
| 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 || precisely_equal(testT, test->fT)); |
| 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; |
| } |
| oFoundEnd |= endPt == oTest->fPt; |
| oTest = &other->fTs[--oIndex]; |
| } while (*oTestPt == oTest->fPt || precisely_equal(oTestT, oTest->fT)); |
| } while (endPt != test->fPt && test->fT < 1); |
| // FIXME: determine if canceled edges need outside ts added |
| if (!oFoundEnd) { |
| for (int oIdx2 = oIndex; oIdx2 >= 0; --oIdx2) { |
| SkOpSpan* oTst2 = &other->fTs[oIdx2]; |
| if (originalWindValue != oTst2->fWindValue) { |
| goto skipAdvanceOtherCancel; |
| } |
| if (!oTst2->fWindValue) { |
| goto skipAdvanceOtherCancel; |
| } |
| if (endPt == other->fTs[oIdx2].fPt) { |
| break; |
| } |
| } |
| oFoundEnd = endPt == oTest->fPt; |
| do { |
| 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]; |
| oFoundEnd |= endPt == oTest->fPt; |
| } while (!oFoundEnd || endPt == oTest->fPt); |
| } |
| skipAdvanceOtherCancel: |
| 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); |
| } |
| setCoincidentRange(startPt, endPt, other); |
| other->setCoincidentRange(startPt, endPt, this); |
| } |
| |
| int SkOpSegment::addSelfT(const SkPoint& pt, double newT) { |
| // if the tail nearly intersects itself but not quite, the caller records this separately |
| int result = addT(this, pt, newT); |
| SkOpSpan* span = &fTs[result]; |
| fLoop = span->fLoop = true; |
| return result; |
| } |
| |
| // find the starting or ending span with an existing loop of angles |
| // FIXME? replicate for all identical starting/ending spans? |
| // OPTIMIZE? remove the spans pointing to windValue==0 here or earlier? |
| // FIXME? assert that only one other span has a valid windValue or oppValue |
| void SkOpSegment::addSimpleAngle(int index) { |
| SkOpSpan* span = &fTs[index]; |
| int idx; |
| int start, end; |
| if (span->fT == 0) { |
| idx = 0; |
| span = &fTs[0]; |
| do { |
| if (span->fToAngle) { |
| SkASSERT(span->fToAngle->loopCount() == 2); |
| SkASSERT(!span->fFromAngle); |
| span->fFromAngle = span->fToAngle->next(); |
| return; |
| } |
| span = &fTs[++idx]; |
| } while (span->fT == 0); |
| SkASSERT(!fTs[0].fTiny && fTs[idx].fT > 0); |
| addStartSpan(idx); |
| start = 0; |
| end = idx; |
| } else { |
| idx = count() - 1; |
| span = &fTs[idx]; |
| do { |
| if (span->fFromAngle) { |
| SkASSERT(span->fFromAngle->loopCount() == 2); |
| SkASSERT(!span->fToAngle); |
| span->fToAngle = span->fFromAngle->next(); |
| return; |
| } |
| span = &fTs[--idx]; |
| } while (span->fT == 1); |
| SkASSERT(!fTs[idx].fTiny && fTs[idx].fT < 1); |
| addEndSpan(++idx); |
| start = idx; |
| end = count(); |
| } |
| SkOpSegment* other; |
| SkOpSpan* oSpan; |
| index = start; |
| do { |
| span = &fTs[index]; |
| other = span->fOther; |
| int oFrom = span->fOtherIndex; |
| oSpan = &other->fTs[oFrom]; |
| if (oSpan->fT < 1 && oSpan->fWindValue) { |
| break; |
| } |
| if (oSpan->fT == 0) { |
| continue; |
| } |
| oFrom = other->nextExactSpan(oFrom, -1); |
| SkOpSpan* oFromSpan = &other->fTs[oFrom]; |
| SkASSERT(oFromSpan->fT < 1); |
| if (oFromSpan->fWindValue) { |
| break; |
| } |
| } while (++index < end); |
| SkOpAngle* angle, * oAngle; |
| if (span->fT == 0) { |
| SkASSERT(span->fOtherIndex - 1 >= 0); |
| SkASSERT(span->fOtherT == 1); |
| SkDEBUGCODE(int oPriorIndex = other->nextExactSpan(span->fOtherIndex, -1)); |
| SkDEBUGCODE(const SkOpSpan& oPrior = other->span(oPriorIndex)); |
| SkASSERT(!oPrior.fTiny && oPrior.fT < 1); |
| other->addEndSpan(span->fOtherIndex); |
| angle = span->fToAngle; |
| oAngle = oSpan->fFromAngle; |
| } else { |
| SkASSERT(span->fOtherIndex + 1 < other->count()); |
| SkASSERT(span->fOtherT == 0); |
| SkASSERT(!oSpan->fTiny && (other->fTs[span->fOtherIndex + 1].fT > 0 |
| || (other->fTs[span->fOtherIndex + 1].fFromAngle == NULL |
| && other->fTs[span->fOtherIndex + 1].fToAngle == NULL))); |
| int oIndex = 1; |
| do { |
| const SkOpSpan& osSpan = other->span(oIndex); |
| if (osSpan.fFromAngle || osSpan.fT > 0) { |
| break; |
| } |
| ++oIndex; |
| SkASSERT(oIndex < other->count()); |
| } while (true); |
| other->addStartSpan(oIndex); |
| angle = span->fFromAngle; |
| oAngle = oSpan->fToAngle; |
| } |
| angle->insert(oAngle); |
| } |
| |
| void SkOpSegment::alignMultiples(SkTDArray<AlignedSpan>* alignedArray) { |
| debugValidate(); |
| int count = this->count(); |
| for (int index = 0; index < count; ++index) { |
| SkOpSpan& span = fTs[index]; |
| if (!span.fMultiple) { |
| continue; |
| } |
| int end = nextExactSpan(index, 1); |
| SkASSERT(end > index + 1); |
| const SkPoint& thisPt = span.fPt; |
| while (index < end - 1) { |
| SkOpSegment* other1 = span.fOther; |
| int oCnt = other1->count(); |
| for (int idx2 = index + 1; idx2 < end; ++idx2) { |
| SkOpSpan& span2 = fTs[idx2]; |
| SkOpSegment* other2 = span2.fOther; |
| for (int oIdx = 0; oIdx < oCnt; ++oIdx) { |
| SkOpSpan& oSpan = other1->fTs[oIdx]; |
| if (oSpan.fOther != other2) { |
| continue; |
| } |
| if (oSpan.fPt == thisPt) { |
| goto skipExactMatches; |
| } |
| } |
| for (int oIdx = 0; oIdx < oCnt; ++oIdx) { |
| SkOpSpan& oSpan = other1->fTs[oIdx]; |
| if (oSpan.fOther != other2) { |
| continue; |
| } |
| if (SkDPoint::RoughlyEqual(oSpan.fPt, thisPt)) { |
| SkOpSpan& oSpan2 = other2->fTs[oSpan.fOtherIndex]; |
| if (zero_or_one(span.fOtherT) || zero_or_one(oSpan.fT) |
| || zero_or_one(span2.fOtherT) || zero_or_one(oSpan2.fT)) { |
| return; |
| } |
| if (!way_roughly_equal(span.fOtherT, oSpan.fT) |
| || !way_roughly_equal(span2.fOtherT, oSpan2.fT) |
| || !way_roughly_equal(span2.fOtherT, oSpan.fOtherT) |
| || !way_roughly_equal(span.fOtherT, oSpan2.fOtherT)) { |
| return; |
| } |
| alignSpan(thisPt, span.fOtherT, other1, span2.fOtherT, |
| other2, &oSpan, alignedArray); |
| alignSpan(thisPt, span2.fOtherT, other2, span.fOtherT, |
| other1, &oSpan2, alignedArray); |
| break; |
| } |
| } |
| skipExactMatches: |
| ; |
| } |
| ++index; |
| } |
| } |
| debugValidate(); |
| } |
| |
| void SkOpSegment::alignRange(int lower, int upper, |
| const SkOpSegment* other, int oLower, int oUpper) { |
| for (int oIndex = oLower; oIndex <= oUpper; ++oIndex) { |
| const SkOpSpan& oSpan = other->span(oIndex); |
| const SkOpSegment* oOther = oSpan.fOther; |
| if (oOther == this) { |
| continue; |
| } |
| SkOpSpan* matchSpan; |
| int matchIndex; |
| const SkOpSpan* refSpan; |
| for (int iIndex = lower; iIndex <= upper; ++iIndex) { |
| const SkOpSpan& iSpan = this->span(iIndex); |
| const SkOpSegment* iOther = iSpan.fOther; |
| if (iOther == other) { |
| continue; |
| } |
| if (iOther == oOther) { |
| goto nextI; |
| } |
| } |
| { |
| // oSpan does not have a match in this |
| int iCount = this->count(); |
| const SkOpSpan* iMatch = NULL; |
| double iMatchTDiff; |
| matchIndex = -1; |
| for (int iIndex = 0; iIndex < iCount; ++iIndex) { |
| const SkOpSpan& iSpan = this->span(iIndex); |
| const SkOpSegment* iOther = iSpan.fOther; |
| if (iOther != oOther) { |
| continue; |
| } |
| double testTDiff = fabs(iSpan.fOtherT - oSpan.fOtherT); |
| if (!iMatch || testTDiff < iMatchTDiff) { |
| matchIndex = iIndex; |
| iMatch = &iSpan; |
| iMatchTDiff = testTDiff; |
| } |
| } |
| if (matchIndex < 0) { |
| continue; // the entry is missing, & will be picked up later (FIXME: fix it here?) |
| } |
| matchSpan = &this->fTs[matchIndex]; |
| refSpan = &this->span(lower); |
| if (!SkDPoint::ApproximatelyEqual(matchSpan->fPt, refSpan->fPt)) { |
| goto nextI; |
| } |
| if (matchIndex != lower - 1 && matchIndex != upper + 1) { |
| // the consecutive spans need to be rearranged to get the missing one close |
| continue; // FIXME: more work to do |
| } |
| } |
| { |
| this->fixOtherTIndex(); |
| SkScalar newT; |
| if (matchSpan->fT != 0 && matchSpan->fT != 1) { |
| newT = matchSpan->fT = refSpan->fT; |
| matchSpan->fOther->fTs[matchSpan->fOtherIndex].fOtherT = refSpan->fT; |
| } else { // leave span at the start or end there and adjust the neighbors |
| newT = matchSpan->fT; |
| for (int iIndex = lower; iIndex <= upper; ++iIndex) { |
| matchSpan = &this->fTs[iIndex]; |
| matchSpan->fT = newT; |
| matchSpan->fOther->fTs[matchSpan->fOtherIndex].fOtherT = newT; |
| } |
| } |
| this->resetSpanFlags(); // fix up small / tiny / done |
| // align ts of other ranges with adjacent spans that match the aligned points |
| lower = SkTMin(lower, matchIndex); |
| while (lower > 0) { |
| const SkOpSpan& span = this->span(lower - 1); |
| if (span.fT != newT) { |
| break; |
| } |
| --lower; |
| } |
| upper = SkTMax(upper, matchIndex); |
| int last = this->count() - 1; |
| while (upper < last) { |
| const SkOpSpan& span = this->span(upper + 1); |
| if (span.fT != newT) { |
| break; |
| } |
| ++upper; |
| } |
| for (int iIndex = lower; iIndex <= upper; ++iIndex) { |
| const SkOpSpan& span = this->span(iIndex); |
| SkOpSegment* aOther = span.fOther; |
| int aLower = span.fOtherIndex; |
| SkScalar aT = span.fOtherT; |
| bool aResetFlags = false; |
| while (aLower > 0) { |
| SkOpSpan* aSpan = &aOther->fTs[aLower - 1]; |
| for (int iIndex = lower; iIndex <= upper; ++iIndex) { |
| if (aSpan->fPt == this->fTs[iIndex].fPt) { |
| goto matchFound; |
| } |
| } |
| break; |
| matchFound: |
| --aLower; |
| } |
| int aUpper = span.fOtherIndex; |
| int aLast = aOther->count() - 1; |
| while (aUpper < aLast) { |
| SkOpSpan* aSpan = &aOther->fTs[aUpper + 1]; |
| for (int iIndex = lower; iIndex <= upper; ++iIndex) { |
| if (aSpan->fPt == this->fTs[iIndex].fPt) { |
| goto matchFound2; |
| } |
| } |
| break; |
| matchFound2: |
| ++aUpper; |
| } |
| if (aOther->fTs[aLower].fT == 0) { |
| aT = 0; |
| } else if (aOther->fTs[aUpper].fT == 1) { |
| aT = 1; |
| } |
| bool aFixed = false; |
| for (int aIndex = aLower; aIndex <= aUpper; ++aIndex) { |
| SkOpSpan* aSpan = &aOther->fTs[aIndex]; |
| if (aSpan->fT == aT) { |
| continue; |
| } |
| SkASSERT(way_roughly_equal(aSpan->fT, aT)); |
| if (!aFixed) { |
| aOther->fixOtherTIndex(); |
| aFixed = true; |
| } |
| aSpan->fT = aT; |
| aSpan->fOther->fTs[aSpan->fOtherIndex].fOtherT = aT; |
| aResetFlags = true; |
| } |
| if (aResetFlags) { |
| aOther->resetSpanFlags(); |
| } |
| } |
| } |
| nextI: ; |
| } |
| } |
| |
| void SkOpSegment::alignSpan(const SkPoint& newPt, double newT, const SkOpSegment* other, |
| double otherT, const SkOpSegment* other2, SkOpSpan* oSpan, |
| SkTDArray<AlignedSpan>* alignedArray) { |
| AlignedSpan* aligned = alignedArray->append(); |
| aligned->fOldPt = oSpan->fPt; |
| aligned->fPt = newPt; |
| aligned->fOldT = oSpan->fT; |
| aligned->fT = newT; |
| aligned->fSegment = this; // OPTIMIZE: may be unused, can remove |
| aligned->fOther1 = other; |
| aligned->fOther2 = other2; |
| SkASSERT(SkDPoint::RoughlyEqual(oSpan->fPt, newPt)); |
| oSpan->fPt = newPt; |
| // SkASSERT(way_roughly_equal(oSpan->fT, newT)); |
| oSpan->fT = newT; |
| // SkASSERT(way_roughly_equal(oSpan->fOtherT, otherT)); |
| oSpan->fOtherT = otherT; |
| } |
| |
| bool SkOpSegment::alignSpan(int index, double thisT, const SkPoint& thisPt) { |
| bool aligned = false; |
| SkOpSpan* span = &fTs[index]; |
| SkOpSegment* other = span->fOther; |
| int oIndex = span->fOtherIndex; |
| SkOpSpan* oSpan = &other->fTs[oIndex]; |
| if (span->fT != thisT) { |
| span->fT = thisT; |
| oSpan->fOtherT = thisT; |
| aligned = true; |
| } |
| if (span->fPt != thisPt) { |
| span->fPt = thisPt; |
| oSpan->fPt = thisPt; |
| aligned = true; |
| } |
| double oT = oSpan->fT; |
| if (oT == 0) { |
| return aligned; |
| } |
| int oStart = other->nextSpan(oIndex, -1) + 1; |
| oSpan = &other->fTs[oStart]; |
| int otherIndex = oStart; |
| if (oT == 1) { |
| if (aligned) { |
| while (oSpan->fPt == thisPt && oSpan->fT != 1) { |
| oSpan->fTiny = true; |
| ++oSpan; |
| } |
| } |
| return aligned; |
| } |
| oT = oSpan->fT; |
| int oEnd = other->nextSpan(oIndex, 1); |
| bool oAligned = false; |
| if (oSpan->fPt != thisPt) { |
| oAligned |= other->alignSpan(oStart, oT, thisPt); |
| } |
| while (++otherIndex < oEnd) { |
| SkOpSpan* oNextSpan = &other->fTs[otherIndex]; |
| if (oNextSpan->fT != oT || oNextSpan->fPt != thisPt) { |
| oAligned |= other->alignSpan(otherIndex, oT, thisPt); |
| } |
| } |
| if (oAligned) { |
| other->alignSpanState(oStart, oEnd); |
| } |
| return aligned; |
| } |
| |
| void SkOpSegment::alignSpanState(int start, int end) { |
| SkOpSpan* lastSpan = &fTs[--end]; |
| bool allSmall = lastSpan->fSmall; |
| bool allTiny = lastSpan->fTiny; |
| bool allDone = lastSpan->fDone; |
| SkDEBUGCODE(int winding = lastSpan->fWindValue); |
| SkDEBUGCODE(int oppWinding = lastSpan->fOppValue); |
| int index = start; |
| while (index < end) { |
| SkOpSpan* span = &fTs[index]; |
| span->fSmall = allSmall; |
| span->fTiny = allTiny; |
| if (span->fDone != allDone) { |
| span->fDone = allDone; |
| fDoneSpans += allDone ? 1 : -1; |
| } |
| SkASSERT(span->fWindValue == winding); |
| SkASSERT(span->fOppValue == oppWinding); |
| ++index; |
| } |
| } |
| |
| void SkOpSegment::blindCancel(const SkCoincidence& coincidence, SkOpSegment* other) { |
| bool binary = fOperand != other->fOperand; |
| int index = 0; |
| int last = this->count(); |
| do { |
| SkOpSpan& span = this->fTs[--last]; |
| if (span.fT != 1 && !span.fSmall) { |
| break; |
| } |
| span.fCoincident = true; |
| } while (true); |
| int oIndex = other->count(); |
| do { |
| SkOpSpan& oSpan = other->fTs[--oIndex]; |
| if (oSpan.fT != 1 && !oSpan.fSmall) { |
| break; |
| } |
| oSpan.fCoincident = true; |
| } while (true); |
| do { |
| SkOpSpan* test = &this->fTs[index]; |
| int baseWind = test->fWindValue; |
| int baseOpp = test->fOppValue; |
| int endIndex = index; |
| while (++endIndex <= last) { |
| SkOpSpan* endSpan = &this->fTs[endIndex]; |
| SkASSERT(endSpan->fT < 1); |
| if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) { |
| break; |
| } |
| endSpan->fCoincident = true; |
| } |
| SkOpSpan* oTest = &other->fTs[oIndex]; |
| int oBaseWind = oTest->fWindValue; |
| int oBaseOpp = oTest->fOppValue; |
| int oStartIndex = oIndex; |
| while (--oStartIndex >= 0) { |
| SkOpSpan* oStartSpan = &other->fTs[oStartIndex]; |
| if (oStartSpan->fWindValue != oBaseWind || oStartSpan->fOppValue != oBaseOpp) { |
| break; |
| } |
| oStartSpan->fCoincident = true; |
| } |
| bool decrement = baseWind && oBaseWind; |
| bool bigger = baseWind >= oBaseWind; |
| do { |
| SkASSERT(test->fT < 1); |
| if (decrement) { |
| if (binary && bigger) { |
| test->fOppValue--; |
| } else { |
| decrementSpan(test); |
| } |
| } |
| test->fCoincident = true; |
| test = &fTs[++index]; |
| } while (index < endIndex); |
| do { |
| SkASSERT(oTest->fT < 1); |
| if (decrement) { |
| if (binary && !bigger) { |
| oTest->fOppValue--; |
| } else { |
| other->decrementSpan(oTest); |
| } |
| } |
| oTest->fCoincident = true; |
| oTest = &other->fTs[--oIndex]; |
| } while (oIndex > oStartIndex); |
| } while (index <= last && oIndex >= 0); |
| SkASSERT(index > last); |
| SkASSERT(oIndex < 0); |
| } |
| |
| void SkOpSegment::blindCoincident(const SkCoincidence& coincidence, SkOpSegment* other) { |
| bool binary = fOperand != other->fOperand; |
| int index = 0; |
| int last = this->count(); |
| do { |
| SkOpSpan& span = this->fTs[--last]; |
| if (span.fT != 1 && !span.fSmall) { |
| break; |
| } |
| span.fCoincident = true; |
| } while (true); |
| int oIndex = 0; |
| int oLast = other->count(); |
| do { |
| SkOpSpan& oSpan = other->fTs[--oLast]; |
| if (oSpan.fT != 1 && !oSpan.fSmall) { |
| break; |
| } |
| oSpan.fCoincident = true; |
| } while (true); |
| do { |
| SkOpSpan* test = &this->fTs[index]; |
| int baseWind = test->fWindValue; |
| int baseOpp = test->fOppValue; |
| int endIndex = index; |
| SkOpSpan* endSpan; |
| while (++endIndex <= last) { |
| endSpan = &this->fTs[endIndex]; |
| SkASSERT(endSpan->fT < 1); |
| if (endSpan->fWindValue != baseWind || endSpan->fOppValue != baseOpp) { |
| break; |
| } |
| endSpan->fCoincident = true; |
| } |
| SkOpSpan* oTest = &other->fTs[oIndex]; |
| int oBaseWind = oTest->fWindValue; |
| int oBaseOpp = oTest->fOppValue; |
| int oEndIndex = oIndex; |
| SkOpSpan* oEndSpan; |
| while (++oEndIndex <= oLast) { |
| oEndSpan = &this->fTs[oEndIndex]; |
| SkASSERT(oEndSpan->fT < 1); |
| if (oEndSpan->fWindValue != oBaseWind || oEndSpan->fOppValue != oBaseOpp) { |
| break; |
| } |
| oEndSpan->fCoincident = true; |
| } |
| // consolidate the winding count even if done |
| if ((test->fWindValue || test->fOppValue) && (oTest->fWindValue || oTest->fOppValue)) { |
| if (!binary || test->fWindValue + oTest->fOppValue >= 0) { |
| bumpCoincidentBlind(binary, index, endIndex); |
| other->bumpCoincidentOBlind(oIndex, oEndIndex); |
| } else { |
| other->bumpCoincidentBlind(binary, oIndex, oEndIndex); |
| bumpCoincidentOBlind(index, endIndex); |
| } |
| } |
| index = endIndex; |
| oIndex = oEndIndex; |
| } while (index <= last && oIndex <= oLast); |
| SkASSERT(index > last); |
| SkASSERT(oIndex > oLast); |
| } |
| |
| void SkOpSegment::bumpCoincidentBlind(bool binary, int index, int endIndex) { |
| const SkOpSpan& oTest = fTs[index]; |
| int oWindValue = oTest.fWindValue; |
| int oOppValue = oTest.fOppValue; |
| if (binary) { |
| SkTSwap<int>(oWindValue, oOppValue); |
| } |
| do { |
| (void) bumpSpan(&fTs[index], oWindValue, oOppValue); |
| } while (++index < endIndex); |
| } |
| |
| bool SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr, |
| SkTArray<SkPoint, true>* outsideTs) { |
| int index = *indexPtr; |
| int oWindValue = oTest.fWindValue; |
| int oOppValue = oTest.fOppValue; |
| if (binary) { |
| SkTSwap<int>(oWindValue, oOppValue); |
| } |
| SkOpSpan* const test = &fTs[index]; |
| SkOpSpan* end = test; |
| const SkPoint& oStartPt = oTest.fPt; |
| do { |
| if (end->fDone && !end->fTiny && !end->fSmall) { // extremely large paths trigger this |
| return false; |
| } |
| if (bumpSpan(end, oWindValue, oOppValue)) { |
| TrackOutside(outsideTs, oStartPt); |
| } |
| end = &fTs[++index]; |
| } while ((end->fPt == test->fPt || precisely_equal(end->fT, test->fT)) && end->fT < 1); |
| *indexPtr = index; |
| return true; |
| } |
| |
| void SkOpSegment::bumpCoincidentOBlind(int index, int endIndex) { |
| do { |
| zeroSpan(&fTs[index]); |
| } while (++index < endIndex); |
| } |
| |
| // 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 |
| bool SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr, |
| SkTArray<SkPoint, true>* oOutsidePts, const SkPoint& oEndPt) { |
| int oIndex = *oIndexPtr; |
| SkOpSpan* const oTest = &fTs[oIndex]; |
| SkOpSpan* oEnd = oTest; |
| const SkPoint& oStartPt = oTest->fPt; |
| double oStartT = oTest->fT; |
| #if 0 // FIXME : figure out what disabling this breaks |
| const SkPoint& startPt = test.fPt; |
| // this is always true since oEnd == oTest && oStartPt == oTest->fPt -- find proper condition |
| if (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) { |
| TrackOutside(oOutsidePts, startPt); |
| } |
| #endif |
| bool foundEnd = false; |
| while (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) { |
| foundEnd |= oEndPt == oEnd->fPt; |
| zeroSpan(oEnd); |
| oEnd = &fTs[++oIndex]; |
| } |
| *oIndexPtr = oIndex; |
| return foundEnd; |
| } |
| |
| // 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 |
| bool 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 && precisely_equal(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 && precisely_equal(other->fTs[oIndex - 1].fT, oStartT)) { |
| --oIndex; |
| } |
| SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts; |
| SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts; |
| SkOpSpan* test = &fTs[index]; |
| const SkPoint* testPt = &test->fPt; |
| double testT = test->fT; |
| SkOpSpan* oTest = &other->fTs[oIndex]; |
| const SkPoint* oTestPt = &oTest->fPt; |
| // paths with extreme data will fail this test and eject out of pathops altogether later on |
| // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); |
| do { |
| SkASSERT(test->fT < 1); |
| if (oTest->fT == 1) { |
| // paths with extreme data may be so mismatched that we fail here |
| return false; |
| } |
| |
| // consolidate the winding count even if done |
| bool foundEnd = false; |
| if ((test->fWindValue == 0 && test->fOppValue == 0) |
| || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) { |
| 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) { |
| if (!bumpCoincidentThis(*oTest, binary, &index, &outsidePts)) { |
| return false; |
| } |
| foundEnd = other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts, endPt); |
| } else { |
| if (!other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts)) { |
| return false; |
| } |
| foundEnd = bumpCoincidentOther(*oTest, &index, &outsidePts, endPt); |
| } |
| } |
| test = &fTs[index]; |
| testPt = &test->fPt; |
| testT = test->fT; |
| oTest = &other->fTs[oIndex]; |
| oTestPt = &oTest->fPt; |
| if (endPt == *testPt || precisely_equal(endT, testT)) { |
| break; |
| } |
| if (0 && foundEnd) { // FIXME: this is likely needed but wait until a test case triggers it |
| break; |
| } |
| // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); |
| } while (endPt != *oTestPt); |
| // in rare cases, one may have ended before the other |
| if (endPt != *testPt && !precisely_equal(endT, testT)) { |
| 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) { |
| SkASSERT(!test->fDone); |
| test->fDone = true; |
| ++fDoneSpans; |
| } |
| } |
| test = &fTs[++index]; |
| testPt = &test->fPt; |
| } while (endPt != *testPt); |
| } |
| if (endPt != *oTestPt) { |
| // look ahead to see if zeroing more spans will allows us to catch up |
| int oPeekIndex = oIndex; |
| bool success = true; |
| SkOpSpan* oPeek; |
| int oCount = other->count(); |
| do { |
| oPeek = &other->fTs[oPeekIndex]; |
| if (++oPeekIndex == oCount) { |
| success = false; |
| break; |
| } |
| } while (endPt != oPeek->fPt); |
| if (success) { |
| // make sure the matching point completes the coincidence span |
| success = false; |
| do { |
| if (oPeek->fOther == this) { |
| success = true; |
| break; |
| } |
| if (++oPeekIndex == oCount) { |
| break; |
| } |
| oPeek = &other->fTs[oPeekIndex]; |
| } while (endPt == oPeek->fPt); |
| } |
| if (success) { |
| do { |
| if (!binary || test->fWindValue + oTest->fOppValue >= 0) { |
| if (other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts, endPt)) { |
| break; |
| } |
| } else { |
| if (!other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts)) { |
| return false; |
| } |
| } |
| oTest = &other->fTs[oIndex]; |
| oTestPt = &oTest->fPt; |
| } while (endPt != *oTestPt); |
| } |
| } |
| int outCount = outsidePts.count(); |
| if (!done() && outCount) { |
| addCoinOutsides(outsidePts[0], endPt, other); |
| } |
| if (!other->done() && oOutsidePts.count()) { |
| other->addCoinOutsides(oOutsidePts[0], endPt, this); |
| } |
| setCoincidentRange(startPt, endPt, other); |
| other->setCoincidentRange(startPt, endPt, this); |
| return true; |
| } |
| |
| // FIXME: this doesn't prevent the same span from being added twice |
| // fix in caller, SkASSERT here? |
| // FIXME: this may erroneously reject adds for cubic loops |
| const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, |
| const SkPoint& pt, const SkPoint& pt2) { |
| int tCount = fTs.count(); |
| for (int tIndex = 0; tIndex < tCount; ++tIndex) { |
| const SkOpSpan& span = fTs[tIndex]; |
| if (!approximately_negative(span.fT - t)) { |
| break; |
| } |
| if (span.fOther == other) { |
| bool tsMatch = approximately_equal(span.fT, t); |
| bool otherTsMatch = approximately_equal(span.fOtherT, otherT); |
| // FIXME: add cubic loop detecting logic here |
| // if fLoop bit is set on span, that could be enough if addOtherT copies the bit |
| // or if a new bit is added ala fOtherLoop |
| if (tsMatch || otherTsMatch) { |
| #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 NULL; |
| } |
| } |
| } |
| int oCount = other->count(); |
| for (int oIndex = 0; oIndex < oCount; ++oIndex) { |
| const SkOpSpan& oSpan = other->span(oIndex); |
| if (!approximately_negative(oSpan.fT - otherT)) { |
| break; |
| } |
| if (oSpan.fOther == this) { |
| bool otherTsMatch = approximately_equal(oSpan.fT, otherT); |
| bool tsMatch = approximately_equal(oSpan.fOtherT, t); |
| if (otherTsMatch || tsMatch) { |
| #if DEBUG_ADD_T_PAIR |
| SkDebugf("%s addTPair other duplicate this=%d %1.9g other=%d %1.9g\n", |
| __FUNCTION__, fID, t, other->fID, otherT); |
| #endif |
| return NULL; |
| } |
| } |
| } |
| #if DEBUG_ADD_T_PAIR |
| SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", |
| __FUNCTION__, fID, t, other->fID, otherT); |
| #endif |
| SkASSERT(other != this); |
| int insertedAt = addT(other, pt, t); |
| int otherInsertedAt = other->addT(this, pt2, otherT); |
| this->addOtherT(insertedAt, otherT, otherInsertedAt); |
| other->addOtherT(otherInsertedAt, t, insertedAt); |
| this->matchWindingValue(insertedAt, t, borrowWind); |
| other->matchWindingValue(otherInsertedAt, otherT, borrowWind); |
| SkOpSpan& span = this->fTs[insertedAt]; |
| if (pt != pt2) { |
| span.fNear = true; |
| SkOpSpan& oSpan = other->fTs[otherInsertedAt]; |
| oSpan.fNear = true; |
| } |
| // if the newly inserted spans match a neighbor on one but not the other, make them agree |
| int lower = this->nextExactSpan(insertedAt, -1) + 1; |
| int upper = this->nextExactSpan(insertedAt, 1) - 1; |
| if (upper < 0) { |
| upper = this->count() - 1; |
| } |
| int oLower = other->nextExactSpan(otherInsertedAt, -1) + 1; |
| int oUpper = other->nextExactSpan(otherInsertedAt, 1) - 1; |
| if (oUpper < 0) { |
| oUpper = other->count() - 1; |
| } |
| if (lower == upper && oLower == oUpper) { |
| return &span; |
| } |
| #if DEBUG_CONCIDENT |
| SkDebugf("%s id=%d lower=%d upper=%d other=%d oLower=%d oUpper=%d\n", __FUNCTION__, |
| debugID(), lower, upper, other->debugID(), oLower, oUpper); |
| #endif |
| // find the nearby spans in one range missing in the other |
| this->alignRange(lower, upper, other, oLower, oUpper); |
| other->alignRange(oLower, oUpper, this, lower, upper); |
| return &span; |
| } |
| |
| const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, |
| const SkPoint& pt) { |
| return addTPair(t, other, otherT, borrowWind, pt, pt); |
| } |
| |
| 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<int>(lesser, greater); |
| } |
| return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT); |
| } |
| |
| // in extreme cases (like the buffer overflow test) return false to abort |
| // for now, if one t value represents two different points, then the values are too extreme |
| // to generate meaningful results |
| bool SkOpSegment::calcAngles() { |
| int spanCount = fTs.count(); |
| if (spanCount <= 2) { |
| return spanCount == 2; |
| } |
| int index = 1; |
| const SkOpSpan* firstSpan = &fTs[index]; |
| int activePrior = checkSetAngle(0); |
| const SkOpSpan* span = &fTs[0]; |
| if (firstSpan->fT == 0 || span->fTiny || span->fOtherT != 1 || span->fOther->multipleEnds()) { |
| index = findStartSpan(0); // curve start intersects |
| if (fTs[index].fT == 0) { |
| return false; |
| } |
| SkASSERT(index > 0); |
| if (activePrior >= 0) { |
| addStartSpan(index); |
| } |
| } |
| bool addEnd; |
| int endIndex = spanCount - 1; |
| span = &fTs[endIndex - 1]; |
| if ((addEnd = span->fT == 1 || span->fTiny)) { // if curve end intersects |
| endIndex = findEndSpan(endIndex); |
| SkASSERT(endIndex > 0); |
| } else { |
| addEnd = fTs[endIndex].fOtherT != 0 || fTs[endIndex].fOther->multipleStarts(); |
| } |
| SkASSERT(endIndex >= index); |
| int prior = 0; |
| while (index < endIndex) { |
| const SkOpSpan& fromSpan = fTs[index]; // for each intermediate intersection |
| const SkOpSpan* lastSpan; |
| span = &fromSpan; |
| int start = index; |
| do { |
| lastSpan = span; |
| span = &fTs[++index]; |
| SkASSERT(index < spanCount); |
| if (!precisely_negative(span->fT - lastSpan->fT) && !lastSpan->fTiny) { |
| break; |
| } |
| if (!SkDPoint::ApproximatelyEqual(lastSpan->fPt, span->fPt)) { |
| return false; |
| } |
| } while (true); |
| SkOpAngle* angle = NULL; |
| SkOpAngle* priorAngle; |
| if (activePrior >= 0) { |
| int pActive = firstActive(prior); |
| SkASSERT(pActive < start); |
| priorAngle = &fAngles.push_back(); |
| priorAngle->set(this, start, pActive); |
| } |
| int active = checkSetAngle(start); |
| if (active >= 0) { |
| SkASSERT(active < index); |
| angle = &fAngles.push_back(); |
| angle->set(this, active, index); |
| } |
| #if DEBUG_ANGLE |
| debugCheckPointsEqualish(start, index); |
| #endif |
| prior = start; |
| do { |
| const SkOpSpan* startSpan = &fTs[start - 1]; |
| if (!startSpan->fSmall || isCanceled(start - 1) || startSpan->fFromAngle |
| || startSpan->fToAngle) { |
| break; |
| } |
| --start; |
| } while (start > 0); |
| do { |
| if (activePrior >= 0) { |
| SkASSERT(fTs[start].fFromAngle == NULL); |
| fTs[start].fFromAngle = priorAngle; |
| } |
| if (active >= 0) { |
| SkASSERT(fTs[start].fToAngle == NULL); |
| fTs[start].fToAngle = angle; |
| } |
| } while (++start < index); |
| activePrior = active; |
| } |
| if (addEnd && activePrior >= 0) { |
| addEndSpan(endIndex); |
| } |
| return true; |
| } |
| |
| int SkOpSegment::checkSetAngle(int tIndex) const { |
| const SkOpSpan* span = &fTs[tIndex]; |
| while (span->fTiny /* || span->fSmall */) { |
| span = &fTs[++tIndex]; |
| } |
| return isCanceled(tIndex) ? -1 : tIndex; |
| } |
| |
| // at this point, the span is already ordered, or unorderable |
| int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType) { |
| SkASSERT(includeType != SkOpAngle::kUnaryXor); |
| SkOpAngle* firstAngle = spanToAngle(endIndex, startIndex); |
| if (NULL == firstAngle || NULL == firstAngle->next()) { |
| return SK_NaN32; |
| } |
| // 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 both are next to orderable angles, |
| // and one has winding computed, transfer to the other |
| SkOpAngle* baseAngle = NULL; |
| bool tryReverse = false; |
| // look for counterclockwise transfers |
| SkOpAngle* angle = firstAngle->previous(); |
| SkOpAngle* next = angle->next(); |
| firstAngle = next; |
| do { |
| SkOpAngle* prior = angle; |
| angle = next; |
| next = angle->next(); |
| SkASSERT(prior->next() == angle); |
| SkASSERT(angle->next() == next); |
| if (prior->unorderable() || angle->unorderable() || next->unorderable()) { |
| baseAngle = NULL; |
| continue; |
| } |
| int testWinding = angle->segment()->windSum(angle); |
| if (SK_MinS32 != testWinding) { |
| baseAngle = angle; |
| tryReverse = true; |
| continue; |
| } |
| if (baseAngle) { |
| ComputeOneSum(baseAngle, angle, includeType); |
| baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL; |
| } |
| } while (next != firstAngle); |
| if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(firstAngle)) { |
| firstAngle = baseAngle; |
| tryReverse = true; |
| } |
| if (tryReverse) { |
| baseAngle = NULL; |
| SkOpAngle* prior = firstAngle; |
| do { |
| angle = prior; |
| prior = angle->previous(); |
| SkASSERT(prior->next() == angle); |
| next = angle->next(); |
| if (prior->unorderable() || angle->unorderable() || next->unorderable()) { |
| baseAngle = NULL; |
| continue; |
| } |
| int testWinding = angle->segment()->windSum(angle); |
| if (SK_MinS32 != testWinding) { |
| baseAngle = angle; |
| continue; |
| } |
| if (baseAngle) { |
| ComputeOneSumReverse(baseAngle, angle, includeType); |
| baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL; |
| } |
| } while (prior != firstAngle); |
| } |
| 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<int>(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<int>(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); |
| } |
| |
| bool SkOpSegment::containsPt(const SkPoint& pt, int index, int endIndex) const { |
| int step = index < endIndex ? 1 : -1; |
| do { |
| const SkOpSpan& span = this->span(index); |
| if (span.fPt == pt) { |
| const SkOpSpan& endSpan = this->span(endIndex); |
| return span.fT == endSpan.fT && pt != endSpan.fPt; |
| } |
| index += step; |
| } while (index != endIndex); |
| return false; |
| } |
| |
| bool SkOpSegment::containsT(double t, const SkOpSegment* other, double otherT) const { |
| int count = this->count(); |
| for (int index = 0; index < count; ++index) { |
| const SkOpSpan& span = fTs[index]; |
| if (t < span.fT) { |
| return false; |
| } |
| if (t == span.fT) { |
| if (other != span.fOther) { |
| continue; |
| } |
| if (other->fVerb != SkPath::kCubic_Verb) { |
| return true; |
| } |
| if (!other->fLoop) { |
| return true; |
| } |
| double otherMidT = (otherT + span.fOtherT) / 2; |
| SkPoint otherPt = other->ptAtT(otherMidT); |
| return SkDPoint::ApproximatelyEqual(span.fPt, otherPt); |
| } |
| } |
| return false; |
| } |
| |
| 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) { |
| if (!span->fDone) { |
| span->fDone = true; |
| ++fDoneSpans; |
| } |
| return true; |
| } |
| return false; |
| } |
| |
| const SkOpSpan& SkOpSegment::firstSpan(const SkOpSpan& thisSpan) const { |
| const SkOpSpan* firstSpan = &thisSpan; // rewind to the start |
| const SkOpSpan* beginSpan = fTs.begin(); |
| const SkPoint& testPt = thisSpan.fPt; |
| while (firstSpan > beginSpan && firstSpan[-1].fPt == testPt) { |
| --firstSpan; |
| } |
| return *firstSpan; |
| } |
| |
| const SkOpSpan& SkOpSegment::lastSpan(const SkOpSpan& thisSpan) const { |
| const SkOpSpan* endSpan = fTs.end() - 1; // last can't be small |
| const SkOpSpan* lastSpan = &thisSpan; // find the end |
| const SkPoint& testPt = thisSpan.fPt; |
| while (lastSpan < endSpan && lastSpan[1].fPt == testPt) { |
| ++lastSpan; |
| } |
| return *lastSpan; |
| } |
| |
| // with a loop, the comparison is move involved |
| // scan backwards and forwards to count all matching points |
| // (verify that there are twp scans marked as loops) |
| // compare that against 2 matching scans for loop plus other results |
| bool SkOpSegment::calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts) { |
| const SkOpSpan& firstSpan = this->firstSpan(thisSpan); // rewind to the start |
| const SkOpSpan& lastSpan = this->lastSpan(thisSpan); // find the end |
| double firstLoopT = -1, lastLoopT = -1; |
| const SkOpSpan* testSpan = &firstSpan - 1; |
| while (++testSpan <= &lastSpan) { |
| if (testSpan->fLoop) { |
| firstLoopT = testSpan->fT; |
| break; |
| } |
| } |
| testSpan = &lastSpan + 1; |
| while (--testSpan >= &firstSpan) { |
| if (testSpan->fLoop) { |
| lastLoopT = testSpan->fT; |
| break; |
| } |
| } |
| SkASSERT((firstLoopT == -1) == (lastLoopT == -1)); |
| if (firstLoopT == -1) { |
| return false; |
| } |
| SkASSERT(firstLoopT < lastLoopT); |
| testSpan = &firstSpan - 1; |
| smallCounts[0] = smallCounts[1] = 0; |
| while (++testSpan <= &lastSpan) { |
| SkASSERT(approximately_equal(testSpan->fT, firstLoopT) + |
| approximately_equal(testSpan->fT, lastLoopT) == 1); |
| smallCounts[approximately_equal(testSpan->fT, lastLoopT)]++; |
| } |
| return true; |
| } |
| |
| double SkOpSegment::calcMissingTEnd(const SkOpSegment* ref, double loEnd, double min, double max, |
| double hiEnd, const SkOpSegment* other, int thisStart) { |
| if (max >= hiEnd) { |
| return -1; |
| } |
| int end = findOtherT(hiEnd, ref); |
| if (end < 0) { |
| return -1; |
| } |
| double tHi = span(end).fT; |
| double tLo, refLo; |
| if (thisStart >= 0) { |
| tLo = span(thisStart).fT; |
| refLo = min; |
| } else { |
| int start1 = findOtherT(loEnd, ref); |
| SkASSERT(start1 >= 0); |
| tLo = span(start1).fT; |
| refLo = loEnd; |
| } |
| double missingT = (max - refLo) / (hiEnd - refLo); |
| missingT = tLo + missingT * (tHi - tLo); |
| return missingT; |
| } |
| |
| double SkOpSegment::calcMissingTStart(const SkOpSegment* ref, double loEnd, double min, double max, |
| double hiEnd, const SkOpSegment* other, int thisEnd) { |
| if (min <= loEnd) { |
| return -1; |
| } |
| int start = findOtherT(loEnd, ref); |
| if (start < 0) { |
| return -1; |
| } |
| double tLo = span(start).fT; |
| double tHi, refHi; |
| if (thisEnd >= 0) { |
| tHi = span(thisEnd).fT; |
| refHi = max; |
| } else { |
| int end1 = findOtherT(hiEnd, ref); |
| if (end1 < 0) { |
| return -1; |
| } |
| tHi = span(end1).fT; |
| refHi = hiEnd; |
| } |
| double missingT = (min - loEnd) / (refHi - loEnd); |
| missingT = tLo + missingT * (tHi - tLo); |
| return missingT; |
| } |
| |
| // see if spans with two or more intersections have the same number on the other end |
| void SkOpSegment::checkDuplicates() { |
| debugValidate(); |
| SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans; |
| int index; |
| int endIndex = 0; |
| bool endFound; |
| do { |
| index = endIndex; |
| endIndex = nextExactSpan(index, 1); |
| if ((endFound = endIndex < 0)) { |
| endIndex = count(); |
| } |
| int dupCount = endIndex - index; |
| if (dupCount < 2) { |
| continue; |
| } |
| do { |
| const SkOpSpan* thisSpan = &fTs[index]; |
| if (thisSpan->fNear) { |
| continue; |
| } |
| SkOpSegment* other = thisSpan->fOther; |
| int oIndex = thisSpan->fOtherIndex; |
| int oStart = other->nextExactSpan(oIndex, -1) + 1; |
| int oEnd = other->nextExactSpan(oIndex, 1); |
| if (oEnd < 0) { |
| oEnd = other->count(); |
| } |
| int oCount = oEnd - oStart; |
| // force the other to match its t and this pt if not on an end point |
| if (oCount != dupCount) { |
| MissingSpan& missing = missingSpans.push_back(); |
| missing.fOther = NULL; |
| SkDEBUGCODE(sk_bzero(&missing, sizeof(missing))); |
| missing.fPt = thisSpan->fPt; |
| const SkOpSpan& oSpan = other->span(oIndex); |
| if (oCount > dupCount) { |
| missing.fSegment = this; |
| missing.fT = thisSpan->fT; |
| other->checkLinks(&oSpan, &missingSpans); |
| } else { |
| missing.fSegment = other; |
| missing.fT = oSpan.fT; |
| checkLinks(thisSpan, &missingSpans); |
| } |
| if (!missingSpans.back().fOther) { |
| missingSpans.pop_back(); |
| } |
| } |
| } while (++index < endIndex); |
| } while (!endFound); |
| int missingCount = missingSpans.count(); |
| if (missingCount == 0) { |
| return; |
| } |
| SkSTArray<kMissingSpanCount, MissingSpan, true> missingCoincidence; |
| for (index = 0; index < missingCount; ++index) { |
| MissingSpan& missing = missingSpans[index]; |
| SkOpSegment* missingOther = missing.fOther; |
| if (missing.fSegment == missing.fOther) { |
| continue; |
| } |
| #if 0 // FIXME: this eliminates spurious data from skpwww_argus_presse_fr_41 but breaks |
| // skpwww_fashionscandal_com_94 -- calcAngles complains, but I don't understand why |
| if (missing.fSegment->containsT(missing.fT, missing.fOther, missing.fOtherT)) { |
| #if DEBUG_DUPLICATES |
| SkDebugf("skip 1 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fSegment->fID, |
| missing.fT, missing.fOther->fID, missing.fOtherT); |
| #endif |
| continue; |
| } |
| if (missing.fOther->containsT(missing.fOtherT, missing.fSegment, missing.fT)) { |
| #if DEBUG_DUPLICATES |
| SkDebugf("skip 2 id=%d t=%1.9g other=%d otherT=%1.9g\n", missing.fOther->fID, |
| missing.fOtherT, missing.fSegment->fID, missing.fT); |
| #endif |
| continue; |
| } |
| #endif |
| // skip if adding would insert point into an existing coincindent span |
| if (missing.fSegment->inCoincidentSpan(missing.fT, missingOther) |
| && missingOther->inCoincidentSpan(missing.fOtherT, this)) { |
| continue; |
| } |
| // skip if the created coincident spans are small |
| if (missing.fSegment->coincidentSmall(missing.fPt, missing.fT, missingOther) |
| && missingOther->coincidentSmall(missing.fPt, missing.fOtherT, missing.fSegment)) { |
| continue; |
| } |
| const SkOpSpan* added = missing.fSegment->addTPair(missing.fT, missingOther, |
| missing.fOtherT, false, missing.fPt); |
| if (added && added->fSmall) { |
| missing.fSegment->checkSmallCoincidence(*added, &missingCoincidence); |
| } |
| } |
| for (index = 0; index < missingCount; ++index) { |
| MissingSpan& missing = missingSpans[index]; |
| missing.fSegment->fixOtherTIndex(); |
| missing.fOther->fixOtherTIndex(); |
| } |
| for (index = 0; index < missingCoincidence.count(); ++index) { |
| MissingSpan& missing = missingCoincidence[index]; |
| missing.fSegment->fixOtherTIndex(); |
| } |
| debugValidate(); |
| } |
| |
| // look to see if the curve end intersects an intermediary that intersects the other |
| bool SkOpSegment::checkEnds() { |
| debugValidate(); |
| SkSTArray<kMissingSpanCount, MissingSpan, true> 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(SkDPoint::ApproximatelyEqual(lastMissing.fPt, peekSpan.fPt)); |
| continue; |
| } |
| } |
| if (this == match) { |
| return false; // extremely large paths can trigger this |
| } |
| #if DEBUG_CHECK_ALIGN |
| 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; |
| SkASSERT(this != match); |
| missing.fOther = match; |
| missing.fOtherT = matchT; |
| missing.fPt = peekSpan.fPt; |
| } |
| break; |
| nextPeekIndex: |
| ; |
| } |
| } |
| if (missingSpans.count() == 0) { |
| debugValidate(); |
| return true; |
| } |
| debugValidate(); |
| int missingCount = missingSpans.count(); |
| for (int index = 0; index < missingCount; ++index) { |
| MissingSpan& missing = missingSpans[index]; |
| if (this != missing.fOther) { |
| 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(); |
| return true; |
| } |
| |
| void SkOpSegment::checkLinks(const |