pathops version two
R=reed@google.com
marked 'no commit' to attempt to get trybots to run
TBR=reed@google.com
Review URL: https://codereview.chromium.org/1002693002
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 1fb5afa..902f273 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -4,11 +4,20 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
-#include "SkIntersections.h"
+#include "SkOpCoincidence.h"
#include "SkOpContour.h"
#include "SkOpSegment.h"
#include "SkPathWriter.h"
-#include "SkTSort.h"
+
+/*
+After computing raw intersections, post process all segments to:
+- find small collections of points that can be collapsed to a single point
+- find missing intersections to resolve differences caused by different algorithms
+
+Consider segments containing tiny or small intervals. Consider coincident segments
+because coincidence finds intersections through distance measurement that non-coincident
+intersection tests cannot.
+ */
#define F (false) // discard the edge
#define T (true) // keep the edge
@@ -33,147 +42,125 @@
#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)) {
+SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr,
+ SkOpSpanBase** endPtr, bool* done, bool* sortable) {
+ if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, 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;
- }
+ if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, 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;
+SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
+ SkOpSpanBase** endPtr, bool* done, bool* sortable) {
+ SkOpSpan* upSpan = start->upCastable();
+ if (upSpan) {
+ if (upSpan->windValue() || upSpan->oppValue()) {
+ SkOpSpanBase* next = upSpan->next();
+ if (!*endPtr) {
+ *startPtr = start;
+ *endPtr = next;
}
- if (!upSpan.fDone) {
- if (upSpan.fWindSum != SK_MinS32) {
- return spanToAngle(index, next);
+ if (!upSpan->done()) {
+ if (upSpan->windSum() != SK_MinS32) {
+ return spanToAngle(start, next);
}
*done = false;
}
} else {
- SkASSERT(upSpan.fDone);
+ SkASSERT(upSpan->done());
}
}
- int prev = nextExactSpan(index, -1);
+ SkOpSpan* downSpan = start->prev();
// 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) {
+ if (downSpan->windValue() || downSpan->oppValue()) {
+ if (!*endPtr) {
+ *startPtr = start;
+ *endPtr = downSpan;
}
- if (!downSpan.fDone) {
- if (downSpan.fWindSum != SK_MinS32) {
- return spanToAngle(index, prev);
+ if (!downSpan->done()) {
+ if (downSpan->windSum() != SK_MinS32) {
+ return spanToAngle(start, downSpan);
}
*done = false;
}
} else {
- SkASSERT(downSpan.fDone);
+ SkASSERT(downSpan->done());
}
}
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);
+SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
+ SkOpSpanBase** endPtr, bool* done, bool* sortable) {
+ SkOpPtT* oPtT = start->ptT()->next();
+ SkOpSegment* other = oPtT->segment();
+ SkOpSpanBase* oSpan = oPtT->span();
+ return other->activeAngleInner(oSpan, startPtr, endPtr, done, sortable);
}
-SkPoint SkOpSegment::activeLeftTop(int* firstT) const {
+SkPoint SkOpSegment::activeLeftTop(SkOpSpanBase** firstSpan) {
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)) {
+ SkOpSpanBase* span = &fHead;
+ do {
+ if (lastDone && (span->final() || span->upCast()->done())) {
goto next;
}
{
- const SkPoint& xy = xyAtT(&span);
+ const SkPoint& xy = span->pt();
if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
topPt = xy;
- if (firstT) {
- *firstT = index;
+ if (firstSpan) {
+ *firstSpan = span;
}
}
if (fVerb != SkPath::kLine_Verb && !lastDone) {
- SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT, span.fT);
+ SkPoint curveTop = (*CurveTop[SkPathOpsVerbToPoints(fVerb)])(fPts, lastT,
+ span->t());
if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
&& topPt.fX > curveTop.fX)) {
topPt = curveTop;
- if (firstT) {
- *firstT = index;
+ if (firstSpan) {
+ *firstSpan = span;
}
}
}
- lastT = span.fT;
+ lastT = span->t();
}
next:
- lastDone = span.fDone;
- }
+ if (span->final()) {
+ break;
+ }
+ lastDone = span->upCast()->done();
+ } while ((span = span->upCast()->next()));
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);
+bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
+ SkPathOp op) {
+ int sumMiWinding = this->updateWinding(end, start);
+ int sumSuWinding = this->updateOppWinding(end, start);
#if DEBUG_LIMIT_WIND_SUM
SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM);
SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM);
#endif
- if (fOperand) {
+ if (this->operand()) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
- return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &sumSuWinding);
+ return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding);
}
-bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
- int* sumMiWinding, int* sumSuWinding) {
+bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end,
+ SkPathOp op, int* sumMiWinding, int* sumSuWinding) {
int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
- setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
+ this->setUpWindings(start, end, sumMiWinding, sumSuWinding,
&maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
bool miFrom;
bool miTo;
@@ -193,178 +180,31 @@
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,
+ __FUNCTION__, debugID(), start->t(), end->t(),
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(SkOpSpanBase* start, SkOpSpanBase* end) {
+ int sumWinding = updateWinding(end, start);
+ return activeWinding(start, end, &sumWinding);
}
-bool SkOpSegment::activeWinding(int index, int endIndex, int* sumWinding) {
+bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) {
int maxWinding;
- setUpWinding(index, endIndex, &maxWinding, sumWinding);
+ setUpWinding(start, end, &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 {
+void SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* 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)) {
+ if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead)) {
ePtr = fPts;
} else {
// OPTIMIZE? if not active, skip remainder and return xyAtT(end)
@@ -372,7 +212,7 @@
ePtr = edge;
}
if (active) {
- bool reverse = ePtr == fPts && start != 0;
+ bool reverse = ePtr == fPts && start != &fHead;
if (reverse) {
path->deferredMoveLine(ePtr[SkPathOpsVerbToPoints(fVerb)]);
switch (fVerb) {
@@ -388,7 +228,6 @@
default:
SkASSERT(0);
}
- // return ePtr[0];
} else {
path->deferredMoveLine(ePtr[0]);
switch (fVerb) {
@@ -406,1538 +245,285 @@
}
}
}
- // 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();
+SkOpPtT* SkOpSegment::addMissing(double t, SkOpSegment* opp, SkChunkAlloc* allocator) {
+ SkOpSpanBase* existing = NULL;
+ SkOpSpanBase* test = &fHead;
+ double testT;
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) {
+ if ((testT = test->ptT()->fT) >= t) {
+ if (testT == t) {
+ existing = test;
+ }
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;
+ } while ((test = test->upCast()->next()));
+ SkOpPtT* result;
+ if (existing && existing->contains(opp)) {
+ result = existing->ptT();
+ } else {
+ result = this->addT(t, SkOpSegment::kNoAlias, allocator);
+ }
+ SkASSERT(result);
+ return result;
}
-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) {
+SkOpAngle* SkOpSegment::addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** anglePtr,
+ SkChunkAlloc* allocator) {
+ SkOpSpan* startSpan = fTail.prev();
+ SkASSERT(startSpan);
+ SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+ *anglePtr = angle;
+ angle->set(&fTail, startSpan);
+ fTail.setFromAngle(angle);
+ SkOpSegment* other = NULL; // these initializations silence a release build warning
+ SkOpSpan* oStartSpan = NULL;
+ SkOpSpanBase* oEndSpan = NULL;
+ SkOpPtT* ptT = fTail.ptT(), * startPtT = ptT;
+ while ((ptT = ptT->next()) != startPtT) {
+ other = ptT->segment();
+ oStartSpan = ptT->span()->upCastable();
+ if (oStartSpan && oStartSpan->windValue()) {
+ oEndSpan = oStartSpan->next();
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);
+ oEndSpan = ptT->span();
+ oStartSpan = oEndSpan->prev();
+ if (oStartSpan && oStartSpan->windValue()) {
+ break;
+ }
+ }
+ SkOpAngle* oAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+ oAngle->set(oStartSpan, oEndSpan);
+ oStartSpan->setToAngle(oAngle);
*otherPtr = other;
- return &oAngle;
+ return oAngle;
}
-SkOpAngle* SkOpSegment::addSingletonAngles(int step) {
+SkOpAngle* SkOpSegment::addSingletonAngles(int step, SkChunkAlloc* allocator) {
SkOpSegment* other;
SkOpAngle* angle, * otherAngle;
if (step > 0) {
- otherAngle = addSingletonAngleUp(&other, &angle);
+ otherAngle = addSingletonAngleUp(&other, &angle, allocator);
} else {
- otherAngle = addSingletonAngleDown(&other, &angle);
+ otherAngle = addSingletonAngleDown(&other, &angle, allocator);
}
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;
+SkOpAngle* SkOpSegment::addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** anglePtr,
+ SkChunkAlloc* allocator) {
+ SkOpSpanBase* endSpan = fHead.next();
+ SkASSERT(endSpan);
+ SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+ *anglePtr = angle;
+ angle->set(&fHead, endSpan);
+ fHead.setToAngle(angle);
+ SkOpSegment* other = NULL; // these initializations silence a release build warning
+ SkOpSpan* oStartSpan = NULL;
+ SkOpSpanBase* oEndSpan = NULL;
+ SkOpPtT* ptT = fHead.ptT(), * startPtT = ptT;
+ while ((ptT = ptT->next()) != startPtT) {
+ other = ptT->segment();
+ oEndSpan = ptT->span();
+ oStartSpan = oEndSpan->prev();
+ if (oStartSpan && oStartSpan->windValue()) {
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) {
+ oStartSpan = oEndSpan->upCastable();
+ if (oStartSpan && oStartSpan->windValue()) {
+ oEndSpan = oStartSpan->next();
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);
+ SkOpAngle* oAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+ oAngle->set(oEndSpan, oStartSpan);
+ oEndSpan->setFromAngle(oAngle);
+ *otherPtr = other;
+ return oAngle;
}
-void SkOpSegment::alignMultiples(SkTDArray<AlignedSpan>* alignedArray) {
+SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* allocator) {
debugValidate();
- int count = this->count();
- for (int index = 0; index < count; ++index) {
- SkOpSpan& span = fTs[index];
- if (!span.fMultiple) {
- continue;
+ SkPoint pt = this->ptAtT(t);
+ SkOpSpanBase* span = &fHead;
+ do {
+ SkOpPtT* result = span->ptT();
+ if (t == result->fT) {
+ return result;
}
- 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;
- }
+ if (this->match(result, this, t, pt)) {
+ // see if any existing alias matches segment, pt, and t
+ SkOpPtT* loop = result->next();
+ bool duplicatePt = false;
+ while (loop != result) {
+ bool ptMatch = loop->fPt == pt;
+ if (loop->segment() == this && loop->fT == t && ptMatch) {
+ return result;
}
- 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:
- ;
+ duplicatePt |= ptMatch;
+ loop = loop->next();
}
- ++index;
+ if (kNoAlias == allowAlias) {
+ return result;
+ }
+ SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator);
+ alias->init(result->span(), t, pt, duplicatePt);
+ result->insert(alias);
+ result->span()->unaligned();
+ this->debugValidate();
+#if DEBUG_ADD_T
+ SkDebugf("%s alias t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
+ alias->segment()->debugID(), alias->span()->debugID());
+#endif
+ return alias;
}
+ if (t < result->fT) {
+ SkOpSpan* prev = result->span()->prev();
+ SkOpSpan* span = insert(prev, allocator);
+ span->init(this, prev, t, pt);
+ this->debugValidate();
+#if DEBUG_ADD_T
+ SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
+ span->segment()->debugID(), span->debugID());
+#endif
+ return span->ptT();
+ }
+ SkASSERT(span != &fTail);
+ } while ((span = span->upCast()->next()));
+ SkASSERT(0);
+ return NULL;
+}
+
+// choose a solitary t and pt value; remove aliases; align the opposite ends
+void SkOpSegment::align() {
+ debugValidate();
+ SkOpSpanBase* span = &fHead;
+ if (!span->aligned()) {
+ span->alignEnd(0, fPts[0]);
+ }
+ while ((span = span->upCast()->next())) {
+ if (span == &fTail) {
+ break;
+ }
+ span->align();
+ }
+ if (!span->aligned()) {
+ span->alignEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]);
}
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: ;
+bool SkOpSegment::BetweenTs(const SkOpSpanBase* lesser, double testT,
+ const SkOpSpanBase* greater) {
+ if (lesser->t() > greater->t()) {
+ SkTSwap<const SkOpSpanBase*>(lesser, greater);
}
+ return approximately_between(lesser->t(), testT, greater->t());
}
-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;
+void SkOpSegment::calcAngles(SkChunkAlloc* allocator) {
+ bool activePrior = !fHead.isCanceled();
+ if (activePrior && !fHead.simple()) {
+ addStartSpan(allocator);
}
- 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;
- }
+ SkOpSpan* prior = &fHead;
+ SkOpSpanBase* spanBase = fHead.next();
+ while (spanBase != &fTail) {
+ if (activePrior) {
+ SkOpAngle* priorAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+ priorAngle->set(spanBase, prior);
+ spanBase->setFromAngle(priorAngle);
}
- 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);
+ SkOpSpan* span = spanBase->upCast();
+ bool active = !span->isCanceled();
+ SkOpSpanBase* next = span->next();
+ if (active) {
+ SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+ angle->set(span, next);
+ span->setToAngle(angle);
}
- }
- 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;
+ prior = span;
+ spanBase = next;
}
- if (addEnd && activePrior >= 0) {
- addEndSpan(endIndex);
+ if (activePrior && !fTail.simple()) {
+ addEndSpan(allocator);
}
- 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;
+void SkOpSegment::checkAngleCoin(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
+ SkOpSpanBase* base = &fHead;
+ SkOpSpan* span;
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;
+ SkOpAngle* angle = base->fromAngle();
+ if (angle && angle->fCheckCoincidence) {
+ angle->checkNearCoincidence();
}
- int testWinding = angle->segment()->windSum(angle);
- if (SK_MinS32 != testWinding) {
- baseAngle = angle;
- tryReverse = true;
- continue;
+ if (base->final()) {
+ break;
}
- if (baseAngle) {
- ComputeOneSum(baseAngle, angle, includeType);
- baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
+ span = base->upCast();
+ angle = span->toAngle();
+ if (angle && angle->fCheckCoincidence) {
+ angle->checkNearCoincidence();
}
- } while (next != firstAngle);
- if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(firstAngle)) {
- firstAngle = baseAngle;
- tryReverse = true;
+ } while ((base = span->next()));
+}
+
+// from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
+bool SkOpSegment::clockwise(const SkOpSpanBase* start, const SkOpSpanBase* end, bool* swap) const {
+ SkASSERT(fVerb != SkPath::kLine_Verb);
+ SkPoint edge[4];
+ if (fVerb == SkPath::kCubic_Verb) {
+ double startT = start->t();
+ double endT = end->t();
+ bool flip = startT > endT;
+ SkDCubic cubic;
+ cubic.set(fPts);
+ double inflectionTs[2];
+ int inflections = cubic.findInflections(inflectionTs);
+ for (int index = 0; index < inflections; ++index) {
+ double inflectionT = inflectionTs[index];
+ if (between(startT, inflectionT, endT)) {
+ if (flip) {
+ if (inflectionT != endT) {
+ startT = inflectionT;
+ }
+ } else {
+ if (inflectionT != startT) {
+ endT = inflectionT;
+ }
+ }
+ }
+ }
+ SkDCubic part = cubic.subDivide(startT, endT);
+ for (int index = 0; index < 4; ++index) {
+ edge[index] = part[index].asSkPoint();
+ }
+ } else {
+ subDivide(start, end, edge);
}
- 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);
+ bool sumSet = false;
+ int points = SkPathOpsVerbToPoints(fVerb);
+ double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY);
+ if (!sumSet) {
+ for (int idx = 0; idx < points; ++idx){
+ sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
+ }
}
- int minIndex = SkMin32(startIndex, endIndex);
- return windSum(minIndex);
+ if (fVerb == SkPath::kCubic_Verb) {
+ SkDCubic cubic;
+ cubic.set(edge);
+ *swap = sum > 0 && !cubic.monotonicInY();
+ } else {
+ SkDQuad quad;
+ quad.set(edge);
+ *swap = sum > 0 && !quad.monotonicInY();
+ }
+ return sum <= 0;
}
void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
@@ -1954,7 +540,7 @@
}
SkOpSegment* nextSegment = nextAngle->segment();
int maxWinding, sumWinding;
- SkOpSpan* last;
+ SkOpSpanBase* last;
if (binary) {
int oppMaxWinding, oppSumWinding;
nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
@@ -1983,7 +569,7 @@
}
SkOpSegment* nextSegment = nextAngle->segment();
int maxWinding, sumWinding;
- SkOpSpan* last;
+ SkOpSpanBase* last;
if (binary) {
int oppMaxWinding, oppSumWinding;
nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
@@ -1998,64 +584,98 @@
nextAngle->setLastMarked(last);
}
-bool SkOpSegment::containsPt(const SkPoint& pt, int index, int endIndex) const {
- int step = index < endIndex ? 1 : -1;
+// at this point, the span is already ordered, or unorderable
+int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end,
+ SkOpAngle::IncludeType includeType) {
+ SkASSERT(includeType != SkOpAngle::kUnaryXor);
+ SkOpAngle* firstAngle = this->spanToAngle(end, start);
+ 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 {
- const SkOpSpan& span = this->span(index);
- if (span.fPt == pt) {
- const SkOpSpan& endSpan = this->span(endIndex);
- return span.fT == endSpan.fT && pt != endSpan.fPt;
+ 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;
}
- 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;
+ int testWinding = angle->starter()->windSum();
+ if (SK_MinS32 != testWinding) {
+ baseAngle = angle;
+ tryReverse = true;
+ continue;
}
- if (t == span.fT) {
- if (other != span.fOther) {
+ if (baseAngle) {
+ ComputeOneSum(baseAngle, angle, includeType);
+ baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : NULL;
+ }
+ } while (next != firstAngle);
+ if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) {
+ 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;
}
- if (other->fVerb != SkPath::kCubic_Verb) {
- return true;
+ int testWinding = angle->starter()->windSum();
+ if (SK_MinS32 != testWinding) {
+ baseAngle = angle;
+ continue;
}
- if (!other->fLoop) {
- return true;
+ if (baseAngle) {
+ ComputeOneSumReverse(baseAngle, angle, includeType);
+ baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : NULL;
}
- double otherMidT = (otherT + span.fOtherT) / 2;
- SkPoint otherPt = other->ptAtT(otherMidT);
- return SkDPoint::ApproximatelyEqual(span.fPt, otherPt);
- }
+ } while (prior != firstAngle);
}
- return false;
+ return start->starter(end)->windSum();
}
-int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
- bool* hitSomething, double mid, bool opp, bool current) const {
+SkOpSpan* SkOpSegment::crossedSpanY(const SkPoint& basePt, double mid, bool opp, bool current,
+ SkScalar* bestY, double* hitT, bool* hitSomething, bool* vertical) {
SkScalar bottom = fBounds.fBottom;
- int bestTIndex = -1;
+ *vertical = false;
if (bottom <= *bestY) {
- return bestTIndex;
+ return NULL;
}
SkScalar top = fBounds.fTop;
if (top >= basePt.fY) {
- return bestTIndex;
+ return NULL;
}
if (fBounds.fLeft > basePt.fX) {
- return bestTIndex;
+ return NULL;
}
if (fBounds.fRight < basePt.fX) {
- return bestTIndex;
+ return NULL;
}
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;
+ *vertical = AlmostEqualUlps(basePt.fX, fBounds.fLeft);
+ return NULL;
}
// intersect ray starting at basePt with edge
SkIntersections intersections;
@@ -2065,7 +685,7 @@
int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])
(fPts, top, bottom, basePt.fX, false);
if (pts == 0 || (current && pts == 1)) {
- return bestTIndex;
+ return NULL;
}
if (current) {
SkASSERT(pts > 1);
@@ -2093,933 +713,73 @@
continue;
}
if (pts > 1 && fVerb == SkPath::kLine_Verb) {
- return SK_MinS32; // if the intersection is edge on, wait for another one
+ *vertical = true;
+ return NULL; // 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
+ *vertical = true;
+ return NULL; // hit vertical, wait for another one
}
}
*bestY = testY;
bestT = foundT;
}
if (bestT < 0) {
- return bestTIndex;
+ return NULL;
}
SkASSERT(bestT >= 0);
- SkASSERT(bestT <= 1);
- int start;
- int end = 0;
+ SkASSERT(bestT < 1);
+ SkOpSpanBase* testTSpanBase = &this->fHead;
+ SkOpSpanBase* nextTSpan;
+ double endT = 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)) {
+ nextTSpan = testTSpanBase->upCast()->next();
+ endT = nextTSpan->t();
+ if (endT >= bestT) {
+ break;
+ }
+ testTSpanBase = nextTSpan;
+ } while (testTSpanBase);
+ SkOpSpan* bestTSpan = NULL;
+ SkOpSpan* testTSpan = testTSpanBase->upCast();
+ if (!testTSpan->isCanceled()) {
*hitT = bestT;
- bestTIndex = start;
+ bestTSpan = testTSpan;
*hitSomething = true;
}
- return bestTIndex;
+ return bestTSpan;
}
-bool SkOpSegment::decrementSpan(SkOpSpan* span) {
- SkASSERT(span->fWindValue > 0);
- if (--(span->fWindValue) == 0) {
- if (!span->fOppValue && !span->fDone) {
- span->fDone = true;
- ++fDoneSpans;
- return true;
- }
+void SkOpSegment::detach(const SkOpSpan* span) {
+ if (span->done()) {
+ --this->fDoneCount;
}
- return false;
+ --this->fCount;
}
-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) {
+double SkOpSegment::distSq(double t, SkOpAngle* oppAngle) {
+ SkDPoint testPt = this->dPtAtT(t);
+ SkDLine testPerp = {{ testPt, testPt }};
+ SkDVector slope = this->dSlopeAtT(t);
+ testPerp[1].fX += slope.fY;
+ testPerp[1].fY -= slope.fX;
+ SkIntersections i;
+ SkOpSegment* oppSegment = oppAngle->segment();
+ int oppPtCount = SkPathOpsVerbToPoints(oppSegment->verb());
+ (*CurveIntersectRay[oppPtCount])(oppSegment->pts(), testPerp, &i);
+ double closestDistSq = SK_ScalarInfinity;
+ for (int index = 0; index < i.used(); ++index) {
+ if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) {
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);
+ double testDistSq = testPt.distanceSquared(i.pt(index));
+ if (closestDistSq > testDistSq) {
+ closestDistSq = testDistSq;
}
}
- 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 SkOpSpan* base,
- SkTArray<MissingSpan, true>* missingSpans) const {
- const SkOpSpan* first = fTs.begin();
- const SkOpSpan* last = fTs.end() - 1;
- SkASSERT(base >= first && last >= base);
- const SkOpSegment* other = base->fOther;
- const SkOpSpan* oFirst = other->fTs.begin();
- const SkOpSpan* oLast = other->fTs.end() - 1;
- const SkOpSpan* oSpan = &other->fTs[base->fOtherIndex];
- const SkOpSpan* test = base;
- const SkOpSpan* missing = NULL;
- while (test > first && (--test)->fPt == base->fPt) {
- if (this == test->fOther) {
- continue;
- }
- CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
- }
- test = base;
- while (test < last && (++test)->fPt == base->fPt) {
- SkASSERT(this != test->fOther || test->fLoop);
- CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
- }
-}
-
-// see if spans with two or more intersections all agree on common t and point values
-void SkOpSegment::checkMultiples() {
- debugValidate();
- int index;
- int end = 0;
- while (fTs[++end].fT == 0)
- ;
- while (fTs[end].fT < 1) {
- int start = index = end;
- end = nextExactSpan(index, 1);
- if (end <= index) {
- return; // buffer overflow example triggers this
- }
- if (index + 1 == end) {
- continue;
- }
- // force the duplicates to agree on t and pt if not on the end
- SkOpSpan& span = fTs[index];
- double thisT = span.fT;
- const SkPoint& thisPt = span.fPt;
- span.fMultiple = true;
- bool aligned = false;
- while (++index < end) {
- aligned |= alignSpan(index, thisT, thisPt);
- }
- if (aligned) {
- alignSpanState(start, end);
- }
- fMultiples = true;
- }
- debugValidate();
-}
-
-void SkOpSegment::CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan,
- const SkOpSpan* oFirst, const SkOpSpan* oLast, const SkOpSpan** missingPtr,
- SkTArray<MissingSpan, true>* missingSpans) {
- SkASSERT(oSpan->fPt == test->fPt);
- const SkOpSpan* oTest = oSpan;
- while (oTest > oFirst && (--oTest)->fPt == test->fPt) {
- if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) {
- return;
- }
- }
- oTest = oSpan;
- while (oTest < oLast && (++oTest)->fPt == test->fPt) {
- if (oTest->fOther == test->fOther && oTest->fOtherT == test->fOtherT) {
- return;
- }
- }
- if (*missingPtr) {
- missingSpans->push_back();
- }
- MissingSpan& lastMissing = missingSpans->back();
- if (*missingPtr) {
- lastMissing = missingSpans->end()[-2];
- }
- *missingPtr = test;
- lastMissing.fOther = test->fOther;
- lastMissing.fOtherT = test->fOtherT;
-}
-
-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;
-}
-
-// a pair of curves may turn into coincident lines -- small may be a hint that that happened
-// if a cubic contains a loop, the counts must be adjusted
-void SkOpSegment::checkSmall() {
- SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
- const SkOpSpan* beginSpan = fTs.begin();
- const SkOpSpan* thisSpan = beginSpan - 1;
- const SkOpSpan* endSpan = fTs.end() - 1; // last can't be small
- while (++thisSpan < endSpan) {
- if (!thisSpan->fSmall) {
- continue;
- }
- if (!thisSpan->fWindValue) {
- continue;
- }
- const SkOpSpan& firstSpan = this->firstSpan(*thisSpan);
- const SkOpSpan& lastSpan = this->lastSpan(*thisSpan);
- const SkOpSpan* nextSpan = &firstSpan + 1;
- ptrdiff_t smallCount = &lastSpan - &firstSpan + 1;
- SkASSERT(1 <= smallCount && smallCount < count());
- if (smallCount <= 1 && !nextSpan->fSmall) {
- SkASSERT(1 == smallCount);
- checkSmallCoincidence(firstSpan, NULL);
- continue;
- }
- // at this point, check for missing computed intersections
- const SkPoint& testPt = firstSpan.fPt;
- thisSpan = &firstSpan - 1;
- SkOpSegment* other = NULL;
- while (++thisSpan <= &lastSpan) {
- other = thisSpan->fOther;
- if (other != this) {
- break;
- }
- }
- SkASSERT(other != this);
- int oIndex = thisSpan->fOtherIndex;
- const SkOpSpan& oSpan = other->span(oIndex);
- const SkOpSpan& oFirstSpan = other->firstSpan(oSpan);
- const SkOpSpan& oLastSpan = other->lastSpan(oSpan);
- ptrdiff_t oCount = &oLastSpan - &oFirstSpan + 1;
- if (fLoop) {
- int smallCounts[2];
- SkASSERT(!other->fLoop); // FIXME: we need more complicated logic for pair of loops
- if (calcLoopSpanCount(*thisSpan, smallCounts)) {
- if (smallCounts[0] && oCount != smallCounts[0]) {
- SkASSERT(0); // FIXME: need a working test case to properly code & debug
- }
- if (smallCounts[1] && oCount != smallCounts[1]) {
- SkASSERT(0); // FIXME: need a working test case to properly code & debug
- }
- goto nextSmallCheck;
- }
- }
- if (other->fLoop) {
- int otherCounts[2];
- if (other->calcLoopSpanCount(other->span(oIndex), otherCounts)) {
- if (otherCounts[0] && otherCounts[0] != smallCount) {
- SkASSERT(0); // FIXME: need a working test case to properly code & debug
- }
- if (otherCounts[1] && otherCounts[1] != smallCount) {
- SkASSERT(0); // FIXME: need a working test case to properly code & debug
- }
- goto nextSmallCheck;
- }
- }
- if (oCount != smallCount) { // check if number of pts in this match other
- MissingSpan& missing = missingSpans.push_back();
- missing.fOther = NULL;
- SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
- missing.fPt = testPt;
- const SkOpSpan& oSpan = other->span(oIndex);
- if (oCount > smallCount) {
- 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 || missing.fSegment->done()) {
- missingSpans.pop_back();
- }
- }
-nextSmallCheck:
- thisSpan = &lastSpan;
- }
- int missingCount = missingSpans.count();
- for (int index = 0; index < missingCount; ++index) {
- MissingSpan& missing = missingSpans[index];
- SkOpSegment* missingOther = missing.fOther;
- // note that add t pair may edit span arrays, so prior pointers to spans are no longer valid
- if (!missing.fSegment->addTPair(missing.fT, missingOther, missing.fOtherT, false,
- missing.fPt)) {
- continue;
- }
- int otherTIndex = missingOther->findT(missing.fOtherT, missing.fPt, missing.fSegment);
- const SkOpSpan& otherSpan = missingOther->span(otherTIndex);
- if (otherSpan.fSmall) {
- const SkOpSpan* nextSpan = &otherSpan;
- if (nextSpan->fPt == missing.fPt) {
- continue;
- }
- do {
- ++nextSpan;
- } while (nextSpan->fSmall);
- if (nextSpan->fT == 1) {
- continue;
- }
- SkAssertResult(missing.fSegment->addTCoincident(missing.fPt, nextSpan->fPt,
- nextSpan->fT, missingOther));
- } else if (otherSpan.fT > 0) {
- const SkOpSpan* priorSpan = &otherSpan;
- do {
- --priorSpan;
- } while (priorSpan->fT == otherSpan.fT);
- if (priorSpan->fSmall) {
- missing.fSegment->addTCancel(missing.fPt, priorSpan->fPt, missingOther);
- }
- }
- }
- // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
- // avoid this
- for (int index = 0; index < missingCount; ++index) {
- MissingSpan& missing = missingSpans[index];
- missing.fSegment->fixOtherTIndex();
- missing.fOther->fixOtherTIndex();
- }
- debugValidate();
-}
-
-void SkOpSegment::checkSmallCoincidence(const SkOpSpan& span,
- SkTArray<MissingSpan, true>* checkMultiple) {
- SkASSERT(span.fSmall);
- if (0 && !span.fWindValue) {
- return;
- }
- SkASSERT(&span < fTs.end() - 1);
- const SkOpSpan* next = &span + 1;
- SkASSERT(!next->fSmall || checkMultiple);
- if (checkMultiple) {
- while (next->fSmall) {
- ++next;
- SkASSERT(next < fTs.end());
- }
- }
- SkOpSegment* other = span.fOther;
- while (other != next->fOther) {
- if (!checkMultiple) {
- return;
- }
- const SkOpSpan* test = next + 1;
- if (test == fTs.end()) {
- return;
- }
- if (test->fPt != next->fPt || !precisely_equal(test->fT, next->fT)) {
- return;
- }
- next = test;
- }
- SkASSERT(span.fT < next->fT);
- int oStartIndex = other->findExactT(span.fOtherT, this);
- int oEndIndex = other->findExactT(next->fOtherT, this);
- // FIXME: be overly conservative by limiting this to the caller that allows multiple smalls
- if (!checkMultiple || fVerb != SkPath::kLine_Verb || other->fVerb != SkPath::kLine_Verb) {
- SkPoint mid = ptAtT((span.fT + next->fT) / 2);
- const SkOpSpan& oSpanStart = other->fTs[oStartIndex];
- const SkOpSpan& oSpanEnd = other->fTs[oEndIndex];
- SkPoint oMid = other->ptAtT((oSpanStart.fT + oSpanEnd.fT) / 2);
- if (!SkDPoint::ApproximatelyEqual(mid, oMid)) {
- return;
- }
- }
- // FIXME: again, be overly conservative to avoid breaking existing tests
- const SkOpSpan& oSpan = oStartIndex < oEndIndex ? other->fTs[oStartIndex]
- : other->fTs[oEndIndex];
- if (checkMultiple && !oSpan.fSmall) {
- return;
- }
-// SkASSERT(oSpan.fSmall);
- if (oStartIndex < oEndIndex) {
- SkAssertResult(addTCoincident(span.fPt, next->fPt, next->fT, other));
- } else {
- addTCancel(span.fPt, next->fPt, other);
- }
- if (!checkMultiple) {
- return;
- }
- // check to see if either segment is coincident with a third segment -- if it is, and if
- // the opposite segment is not already coincident with the third, make it so
- // OPTIMIZE: to make this check easier, add coincident and cancel could set a coincident bit
- if (span.fWindValue != 1 || span.fOppValue != 0) {
-// start here;
- // iterate through the spans, looking for the third coincident case
- // if we find one, we need to return state to the caller so that the indices can be fixed
- // this also suggests that all of this function is fragile since it relies on a valid index
- }
- // probably should make this a common function rather than copy/paste code
- if (oSpan.fWindValue != 1 || oSpan.fOppValue != 0) {
- const SkOpSpan* oTest = &oSpan;
- while (--oTest >= other->fTs.begin()) {
- if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) {
- break;
- }
- SkOpSegment* testOther = oTest->fOther;
- SkASSERT(testOther != this);
- // look in both directions to see if there is a coincident span
- const SkOpSpan* tTest = testOther->fTs.begin();
- for (int testIndex = 0; testIndex < testOther->count(); ++testIndex) {
- if (tTest->fPt != span.fPt) {
- ++tTest;
- continue;
- }
- if (testOther->verb() != SkPath::kLine_Verb
- || other->verb() != SkPath::kLine_Verb) {
- SkPoint mid = ptAtT((span.fT + next->fT) / 2);
- SkPoint oMid = other->ptAtT((oTest->fOtherT + tTest->fT) / 2);
- if (!SkDPoint::ApproximatelyEqual(mid, oMid)) {
- continue;
- }
- }
-#if DEBUG_CONCIDENT
- SkDebugf("%s coincident found=%d %1.9g %1.9g\n", __FUNCTION__, testOther->fID,
- oTest->fOtherT, tTest->fT);
-#endif
- if (tTest->fT < oTest->fOtherT) {
- SkAssertResult(addTCoincident(span.fPt, next->fPt, next->fT, testOther));
- } else {
- addTCancel(span.fPt, next->fPt, testOther);
- }
- MissingSpan missing;
- missing.fSegment = testOther;
- checkMultiple->push_back(missing);
- break;
- }
- }
- oTest = &oSpan;
- while (++oTest < other->fTs.end()) {
- if (oTest->fPt != oSpan.fPt || !precisely_equal(oTest->fT, oSpan.fT)) {
- break;
- }
-
- }
- }
-}
-
-// if pair of spans on either side of tiny have the same end point and mid point, mark
-// them as parallel
-void SkOpSegment::checkTiny() {
- SkSTArray<kMissingSpanCount, MissingSpan, true> 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;
- SkASSERT(this != nextOther);
- 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];
- if (missing.fSegment != missing.fOther) {
- missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false,
- missing.fPt);
- }
- }
- // OPTIMIZE: consolidate to avoid multiple calls to fix index
- for (int index = 0; index < missingCount; ++index) {
- MissingSpan& missing = missingSpans[index];
- missing.fSegment->fixOtherTIndex();
- missing.fOther->fixOtherTIndex();
- }
-}
-
-bool SkOpSegment::coincidentSmall(const SkPoint& pt, double t, const SkOpSegment* other) const {
- int count = this->count();
- for (int index = 0; index < count; ++index) {
- const SkOpSpan& span = this->span(index);
- if (span.fOther != other) {
- continue;
- }
- if (span.fPt == pt) {
- continue;
- }
- if (!AlmostEqualUlps(span.fPt, pt)) {
- continue;
- }
- if (fVerb != SkPath::kCubic_Verb) {
- return true;
- }
- double tInterval = t - span.fT;
- double tMid = t - tInterval / 2;
- SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
- return midPt.approximatelyEqual(xyAtT(t));
- }
- return false;
-}
-
-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;
-}
-
-int SkOpSegment::findEndSpan(int endIndex) const {
- const SkOpSpan* span = &fTs[--endIndex];
- const SkPoint& lastPt = span->fPt;
- double endT = span->fT;
- do {
- span = &fTs[--endIndex];
- } while (SkDPoint::ApproximatelyEqual(span->fPt, lastPt) && (span->fT == endT || span->fTiny));
- return endIndex + 1;
+ return closestDistSq;
}
/*
@@ -3029,71 +789,57 @@
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<SkOpSpan*>* 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);
- int step = SkSign32(endIndex - startIndex);
- *nextStart = startIndex;
- SkOpSegment* other = isSimple(nextStart, &step);
- if (other)
- {
+SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
+ SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) {
+ SkOpSpanBase* start = *nextStart;
+ SkOpSpanBase* end = *nextEnd;
+ SkASSERT(start != end);
+ int step = start->step(end);
+ SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
+ if (other) {
// 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) {
+ SkOpSpan* startSpan = start->starter(end);
+ if (startSpan->done()) {
return NULL;
}
- markDoneBinary(min);
- 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;
- }
+ markDone(startSpan);
+ *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
return other;
}
- const int end = nextExactSpan(startIndex, step);
- SkASSERT(end >= 0);
- SkASSERT(startIndex - endIndex != 0);
- SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
+ SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
+ SkASSERT(endNear == end); // is this ever not end?
+ SkASSERT(endNear);
+ SkASSERT(start != endNear);
+ SkASSERT((start->t() < endNear->t()) ^ (step < 0));
// more than one viable candidate -- measure angles to find best
-
- int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp);
+ int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp);
bool sortable = calcWinding != SK_NaN32;
if (!sortable) {
*unsortable = true;
- markDoneBinary(SkMin32(startIndex, endIndex));
+ markDone(start->starter(end));
return NULL;
}
- SkOpAngle* angle = spanToAngle(end, startIndex);
+ SkOpAngle* angle = this->spanToAngle(end, start);
if (angle->unorderable()) {
*unsortable = true;
- markDoneBinary(SkMin32(startIndex, endIndex));
+ markDone(start->starter(end));
return NULL;
}
#if DEBUG_SORT
SkDebugf("%s\n", __FUNCTION__);
angle->debugLoop();
#endif
- int sumMiWinding = updateWinding(endIndex, startIndex);
+ int sumMiWinding = updateWinding(end, start);
if (sumMiWinding == SK_MinS32) {
*unsortable = true;
- markDoneBinary(SkMin32(startIndex, endIndex));
+ markDone(start->starter(end));
return NULL;
}
- int sumSuWinding = updateOppWinding(endIndex, startIndex);
+ int sumSuWinding = updateOppWinding(end, start);
if (operand()) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
@@ -3110,11 +856,6 @@
if (activeAngle) {
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
- if (nextSegment->isTiny(nextAngle)) {
- *unsortable = true;
- markDoneBinary(SkMin32(startIndex, endIndex));
- return NULL;
- }
foundAngle = nextAngle;
foundDone = nextSegment->done(nextAngle);
}
@@ -3122,30 +863,24 @@
if (nextSegment->done()) {
continue;
}
- if (nextSegment->isTiny(nextAngle)) {
- continue;
- }
if (!activeAngle) {
- (void) nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
+ (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end());
}
- SkOpSpan* last = nextAngle->lastMarked();
+ SkOpSpanBase* last = nextAngle->lastMarked();
if (last) {
SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, 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);
+ SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
+ last->segment()->debugID(), last->debugID());
+ if (!last->final()) {
+ SkDebugf(" windSum=%d", last->upCast()->windSum());
+ }
+ SkDebugf("\n");
#endif
}
} while ((nextAngle = nextAngle->next()) != angle);
-#if DEBUG_ANGLE
- if (foundAngle) {
- foundAngle->debugSameAs(foundAngle);
- }
-#endif
-
- markDoneBinary(SkMin32(startIndex, endIndex));
+ start->segment()->markDone(start->starter(end));
if (!foundAngle) {
return NULL;
}
@@ -3159,62 +894,55 @@
return nextSegment;
}
-SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* 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);
- int step = SkSign32(endIndex - startIndex);
- *nextStart = startIndex;
- SkOpSegment* other = isSimple(nextStart, &step);
- if (other)
- {
+SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase,
+ SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) {
+ SkOpSpanBase* start = *nextStart;
+ SkOpSpanBase* end = *nextEnd;
+ SkASSERT(start != end);
+ int step = start->step(end);
+ SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
+ if (other) {
// 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) {
+ SkOpSpan* startSpan = start->starter(end);
+ if (startSpan->done()) {
return NULL;
}
- markDoneUnary(min);
- 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;
- }
+ markDone(startSpan);
+ *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
return other;
}
- const int end = nextExactSpan(startIndex, step);
- SkASSERT(end >= 0);
- SkASSERT(startIndex - endIndex != 0);
- SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
+ SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
+ SkASSERT(endNear == end); // is this ever not end?
+ SkASSERT(endNear);
+ SkASSERT(start != endNear);
+ SkASSERT((start->t() < endNear->t()) ^ (step < 0));
// more than one viable candidate -- measure angles to find best
-
- int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding);
+ int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding);
bool sortable = calcWinding != SK_NaN32;
if (!sortable) {
*unsortable = true;
- markDoneUnary(SkMin32(startIndex, endIndex));
+ markDone(start->starter(end));
return NULL;
}
- SkOpAngle* angle = spanToAngle(end, startIndex);
+ SkOpAngle* angle = this->spanToAngle(end, start);
+ if (angle->unorderable()) {
+ *unsortable = true;
+ markDone(start->starter(end));
+ return NULL;
+ }
#if DEBUG_SORT
SkDebugf("%s\n", __FUNCTION__);
angle->debugLoop();
#endif
- int sumWinding = updateWinding(endIndex, startIndex);
+ int sumWinding = updateWinding(end, start);
SkOpAngle* nextAngle = angle->next();
const SkOpAngle* foundAngle = NULL;
bool foundDone = false;
+ // iterate through the angle, and compute everyone's winding
SkOpSegment* nextSegment;
int activeCount = 0;
do {
@@ -3224,11 +952,6 @@
if (activeAngle) {
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
- if (nextSegment->isTiny(nextAngle)) {
- *unsortable = true;
- markDoneUnary(SkMin32(startIndex, endIndex));
- return NULL;
- }
foundAngle = nextAngle;
foundDone = nextSegment->done(nextAngle);
}
@@ -3236,24 +959,24 @@
if (nextSegment->done()) {
continue;
}
- if (nextSegment->isTiny(nextAngle)) {
- continue;
- }
if (!activeAngle) {
- nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end());
+ (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end());
}
- SkOpSpan* last = nextAngle->lastMarked();
+ SkOpSpanBase* last = nextAngle->lastMarked();
if (last) {
SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, 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);
+ SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
+ last->segment()->debugID(), last->debugID());
+ if (!last->final()) {
+ SkDebugf(" windSum=%d", last->upCast()->windSum());
+ }
+ SkDebugf("\n");
#endif
}
} while ((nextAngle = nextAngle->next()) != angle);
- markDoneUnary(SkMin32(startIndex, endIndex));
+ start->segment()->markDone(start->starter(end));
if (!foundAngle) {
return NULL;
}
@@ -3267,57 +990,39 @@
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);
-// Detect cases where all the ends canceled out (e.g.,
-// there is no angle) and therefore there's only one valid connection
- *nextStart = startIndex;
- SkOpSegment* other = isSimple(nextStart, &step);
- if (other)
- {
+SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd,
+ bool* unsortable) {
+ SkOpSpanBase* start = *nextStart;
+ SkOpSpanBase* end = *nextEnd;
+ SkASSERT(start != end);
+ int step = start->step(end);
+ SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
+ if (other) {
+ // 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) {
+ SkOpSpan* startSpan = start->starter(end);
+ if (startSpan->done()) {
return NULL;
}
- markDone(min, 1);
- 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());
+ markDone(startSpan);
+ *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
return other;
}
- SkASSERT(startIndex - endIndex != 0);
- SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
- // parallel block above with presorted version
- int end = nextExactSpan(startIndex, step);
- SkASSERT(end >= 0);
- SkOpAngle* angle = spanToAngle(end, startIndex);
- SkASSERT(angle);
+ SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \
+ : (*nextStart)->prev());
+ SkASSERT(endNear == end); // is this ever not end?
+ SkASSERT(endNear);
+ SkASSERT(start != endNear);
+ SkASSERT((start->t() < endNear->t()) ^ (step < 0));
+ SkOpAngle* angle = this->spanToAngle(end, start);
+ if (angle->unorderable()) {
+ *unsortable = true;
+ markDone(start->starter(end));
+ return NULL;
+ }
#if DEBUG_SORT
SkDebugf("%s\n", __FUNCTION__);
angle->debugLoop();
@@ -3325,16 +1030,13 @@
SkOpAngle* nextAngle = angle->next();
const SkOpAngle* foundAngle = NULL;
bool foundDone = false;
+ // iterate through the angle, and compute everyone's winding
SkOpSegment* nextSegment;
int activeCount = 0;
do {
nextSegment = nextAngle->segment();
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
- if (nextSegment->isTiny(nextAngle)) {
- *unsortable = true;
- return NULL;
- }
foundAngle = nextAngle;
if (!(foundDone = nextSegment->done(nextAngle))) {
break;
@@ -3342,7 +1044,7 @@
}
nextAngle = nextAngle->next();
} while (nextAngle != angle);
- markDone(SkMin32(startIndex, endIndex), 1);
+ start->segment()->markDone(start->starter(end));
if (!foundAngle) {
return NULL;
}
@@ -3356,105 +1058,39 @@
return nextSegment;
}
-int SkOpSegment::findStartSpan(int startIndex) const {
- int index = startIndex;
- const SkOpSpan* span = &fTs[index];
- const SkPoint& firstPt = span->fPt;
- double firstT = span->fT;
- const SkOpSpan* prior;
- do {
- prior = span;
- span = &fTs[++index];
- } while (SkDPoint::ApproximatelyEqual(span->fPt, firstPt)
- && (span->fT == firstT || prior->fTiny));
- return index;
-}
-
-int SkOpSegment::findExactT(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;
-}
-
-
-
-int SkOpSegment::findOtherT(double t, const SkOpSegment* match) const {
- int count = this->count();
- for (int index = 0; index < count; ++index) {
- const SkOpSpan& span = fTs[index];
- if (span.fOtherT == t && span.fOther == match) {
- return index;
- }
- }
- return -1;
-}
-
-int SkOpSegment::findT(double t, const SkPoint& pt, const SkOpSegment* match) const {
- int count = this->count();
- // prefer exact matches over approximate matches
- for (int index = 0; index < count; ++index) {
- const SkOpSpan& span = fTs[index];
- if (span.fT == t && span.fOther == match) {
- return index;
- }
- }
- for (int index = 0; index < count; ++index) {
- const SkOpSpan& span = fTs[index];
- if (approximately_equal_orderable(span.fT, t) && span.fOther == match) {
- return index;
- }
- }
- // Usually, the pair of ts are an exact match. It's possible that the t values have
- // been adjusted to make multiple intersections align. In this rare case, look for a
- // matching point / match pair instead.
- for (int index = 0; index < count; ++index) {
- const SkOpSpan& span = fTs[index];
- if (span.fPt == pt && span.fOther == match) {
- return index;
- }
- }
- SkASSERT(0);
- return -1;
-}
-
-SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable,
- bool firstPass) {
+SkOpSegment* SkOpSegment::findTop(bool firstPass, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr,
+ bool* unsortable, SkChunkAlloc* allocator) {
// 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(&firstT);
- if (firstT < 0) {
+ SkOpSpanBase* firstT = NULL;
+ (void) this->activeLeftTop(&firstT);
+ if (!firstT) {
*unsortable = !firstPass;
- firstT = 0;
- while (fTs[firstT].fDone) {
- SkASSERT(firstT < fTs.count());
- ++firstT;
+ firstT = &fHead;
+ while (firstT->upCast()->done()) {
+ firstT = firstT->upCast()->next();
}
- *tIndexPtr = firstT;
- *endIndexPtr = nextExactSpan(firstT, 1);
+ *startPtr = firstT;
+ *endPtr = firstT->upCast()->next();
return this;
}
// sort the edges to find the leftmost
int step = 1;
- int end;
- if (span(firstT).fDone || (end = nextSpan(firstT, step)) == -1) {
+ SkOpSpanBase* end;
+ if (firstT->final() || firstT->upCast()->done()) {
step = -1;
- end = nextSpan(firstT, step);
- SkASSERT(end != -1);
+ end = firstT->prev();
+ SkASSERT(end);
+ } else {
+ end = firstT->upCast()->next();
}
// 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)
- SkASSERT(firstT - end != 0);
+ SkASSERT(firstT != end);
SkOpAngle* markAngle = spanToAngle(firstT, end);
if (!markAngle) {
- markAngle = addSingletonAngles(step);
+ markAngle = addSingletonAngles(step, allocator);
}
markAngle->markStops();
const SkOpAngle* baseAngle = markAngle->next() == markAngle && !isVertical() ? markAngle
@@ -3467,7 +1103,7 @@
const SkOpAngle* angle = baseAngle;
do {
if (!angle->unorderable()) {
- SkOpSegment* next = angle->segment();
+ const SkOpSegment* next = angle->segment();
SkPathOpsBounds bounds;
next->subDivideBounds(angle->end(), angle->start(), &bounds);
bool nearSame = AlmostEqualUlps(top, bounds.top());
@@ -3495,9 +1131,10 @@
*unsortable = angle->unorderable();
if (firstPass || !*unsortable) {
leftSegment = angle->segment();
- *tIndexPtr = angle->end();
- *endIndexPtr = angle->start();
- if (!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone) {
+ *startPtr = angle->end();
+ *endPtr = angle->start();
+ const SkOpSpan* firstSpan = (*startPtr)->starter(*endPtr);
+ if (!firstSpan->done()) {
break;
}
}
@@ -3508,157 +1145,52 @@
return NULL;
}
if (leftSegment->verb() >= SkPath::kQuad_Verb) {
- const int tIndex = *tIndexPtr;
- const int endIndex = *endIndexPtr;
+ SkOpSpanBase* start = *startPtr;
+ SkOpSpanBase* end = *endPtr;
bool swap;
- if (!leftSegment->clockwise(tIndex, endIndex, &swap)) {
+ if (!leftSegment->clockwise(start, end, &swap)) {
#if DEBUG_SWAP_TOP
- SkDebugf("%s swap=%d inflections=%d serpentine=%d controlledbyends=%d monotonic=%d\n",
+ SkDebugf("%s swap=%d inflections=%d monotonic=%d\n",
__FUNCTION__,
- swap, leftSegment->debugInflections(tIndex, endIndex),
- leftSegment->serpentine(tIndex, endIndex),
- leftSegment->controlsContainedByEnds(tIndex, endIndex),
- leftSegment->monotonicInY(tIndex, endIndex));
+ swap, leftSegment->debugInflections(start, end),
+ leftSegment->monotonicInY(start, end));
#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);
+ SkTSwap(*startPtr, *endPtr);
}
}
}
- SkASSERT(!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fTiny);
return leftSegment;
}
-int SkOpSegment::firstActive(int tIndex) const {
- while (fTs[tIndex].fTiny) {
- SkASSERT(!isCanceled(tIndex));
- ++tIndex;
- }
- return tIndex;
+SkOpGlobalState* SkOpSegment::globalState() const {
+ return contour()->globalState();
}
-// 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);
- }
-}
-
-bool SkOpSegment::inCoincidentSpan(double t, const SkOpSegment* other) const {
- int foundEnds = 0;
- int count = this->count();
- for (int index = 0; index < count; ++index) {
- const SkOpSpan& span = this->span(index);
- if (span.fCoincident) {
- foundEnds |= (span.fOther == other) << ((t > span.fT) + (t >= span.fT));
- }
- }
- SkASSERT(foundEnds != 7);
- return foundEnds == 0x3 || foundEnds == 0x5 || foundEnds == 0x6; // two bits set
-}
-
-bool SkOpSegment::inconsistentAngle(int maxWinding, int sumWinding, int oppMaxWinding,
- int oppSumWinding, const SkOpAngle* angle) const {
- SkASSERT(angle->segment() == this);
- if (UseInnerWinding(maxWinding, sumWinding)) {
- maxWinding = sumWinding;
- }
- if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
- oppMaxWinding = oppSumWinding;
- }
- return inconsistentWinding(angle, maxWinding, oppMaxWinding);
-}
-
-bool SkOpSegment::inconsistentWinding(const SkOpAngle* angle, int winding,
- int oppWinding) const {
- int index = angle->start();
- int endIndex = angle->end();
- int min = SkMin32(index, endIndex);
- int step = SkSign32(endIndex - index);
- if (inconsistentWinding(min, winding, oppWinding)) {
- return true;
- }
- const SkOpSegment* other = this;
- while ((other = other->nextChase(&index, &step, &min, NULL))) {
- if (other->fTs[min].fWindSum != SK_MinS32) {
- break;
- }
- if (fOperand == other->fOperand) {
- if (other->inconsistentWinding(min, winding, oppWinding)) {
- return true;
- }
- } else {
- if (other->inconsistentWinding(min, oppWinding, winding)) {
- return true;
- }
- }
- }
- return false;
-}
-
-bool SkOpSegment::inconsistentWinding(int index, int winding, int oppWinding) const {
- SkASSERT(winding || oppWinding);
- double referenceT = this->span(index).fT;
- int lesser = index;
- while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
- if (inconsistentWinding(__FUNCTION__, lesser, winding, oppWinding)) {
- return true;
- }
- }
- do {
- if (inconsistentWinding(__FUNCTION__, index, winding, oppWinding)) {
- return true;
- }
- } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
- return false;
-}
-
-bool SkOpSegment::inconsistentWinding(const char* funName, int tIndex, int winding,
- int oppWinding) const {
- const SkOpSpan& span = this->span(tIndex);
- if (span.fDone && !span.fSmall) {
- return false;
- }
- return (span.fWindSum != SK_MinS32 && span.fWindSum != winding)
- || (span.fOppSum != SK_MinS32 && span.fOppSum != oppWinding);
-}
-
-void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
- fDoneSpans = 0;
- fOperand = operand;
- fXor = evenOdd;
+void SkOpSegment::init(SkPoint pts[], SkOpContour* contour, SkPath::Verb verb) {
+ fContour = contour;
+ fNext = NULL;
fPts = pts;
fVerb = verb;
- fLoop = fMultiples = fSmall = fTiny = false;
+ fCount = 0;
+ fDoneCount = 0;
+ fVisited = false;
+ SkOpSpan* zeroSpan = &fHead;
+ zeroSpan->init(this, NULL, 0, fPts[0]);
+ SkOpSpanBase* oneSpan = &fTail;
+ zeroSpan->setNext(oneSpan);
+ oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]);
+ PATH_OPS_DEBUG_CODE(fID = globalState()->nextSegmentID());
}
-void SkOpSegment::initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType) {
- int local = spanSign(start, end);
+void SkOpSegment::initWinding(SkOpSpanBase* start, SkOpSpanBase* end,
+ SkOpAngle::IncludeType angleIncludeType) {
+ int local = SkOpSegment::SpanSign(start, end);
SkDEBUGCODE(bool success);
if (angleIncludeType == SkOpAngle::kBinarySingle) {
- int oppLocal = oppSign(start, end);
+ int oppLocal = SkOpSegment::OppSign(start, end);
SkDEBUGCODE(success =) markAndChaseWinding(start, end, local, oppLocal, NULL);
// OPTIMIZATION: the reverse mark and chase could skip the first marking
SkDEBUGCODE(success |=) markAndChaseWinding(end, start, local, oppLocal, NULL);
@@ -3679,12 +1211,13 @@
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.
*/
-bool SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkScalar hitDx,
- int oppWind, SkScalar hitOppDx) {
+bool SkOpSegment::initWinding(SkOpSpanBase* start, SkOpSpanBase* end, double tHit,
+ int winding, SkScalar hitDx, int oppWind, SkScalar hitOppDx) {
+ SkASSERT(this == start->segment());
SkASSERT(hitDx || !winding);
SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
- SkASSERT(dx);
- int windVal = windValue(SkMin32(start, end));
+// SkASSERT(dx);
+ int windVal = start->starter(end)->windValue();
#if DEBUG_WINDING_AT_T
SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, debugID(), winding,
hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
@@ -3693,9 +1226,9 @@
if (abs(winding) < abs(sideWind)) {
winding = sideWind;
}
- SkDEBUGCODE(int oppLocal = oppSign(start, end));
+ SkDEBUGCODE(int oppLocal = SkOpSegment::OppSign(start, end));
SkASSERT(hitOppDx || !oppWind || !oppLocal);
- int oppWindVal = oppValue(SkMin32(start, end));
+ int oppWindVal = start->starter(end)->oppValue();
if (!oppWind) {
oppWind = dx < 0 ? oppWindVal : -oppWindVal;
} else if (hitOppDx * dx >= 0) {
@@ -3714,149 +1247,57 @@
return success;
}
-bool SkOpSegment::inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const {
- if (!baseAngle->inLoop()) {
- return false;
- }
- int index = *indexPtr;
- SkOpAngle* from = fTs[index].fFromAngle;
- SkOpAngle* to = fTs[index].fToAngle;
- while (++index < spanCount) {
- SkOpAngle* nextFrom = fTs[index].fFromAngle;
- SkOpAngle* nextTo = fTs[index].fToAngle;
- if (from != nextFrom || to != nextTo) {
- break;
- }
- }
- *indexPtr = index;
- return true;
-}
-
-// 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 {
- int tCount = fTs.count();
- for (int index = 0; index < tCount; ++index) {
- const SkOpSpan& span = fTs[index];
- if (approximately_zero(startT - span.fT) && pt == span.fPt) {
- return false;
- }
- }
- return true;
-}
-
-
-SkOpSegment* SkOpSegment::isSimple(int* end, int* step) {
- return nextChase(end, step, NULL, NULL);
-}
-
-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 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, const SkPoint& otherPt,
- int step, bool cancel) {
- int otherTIndex = other->findT(otherT, otherPt, this);
- int next = other->nextExactSpan(otherTIndex, step);
- int otherMin = SkMin32(otherTIndex, next);
- int otherWind = other->span(otherMin).fWindValue;
- if (otherWind == 0) {
- return false;
- }
- if (next < 0) {
- return false; // can happen if t values were adjusted but coincident ts were not
- }
- 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 {
- if (!match->addTCoincident(startPt, endPt, endT, other)) {
- return false;
- }
- }
+bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const {
+ SkDPoint cPt = this->dPtAtT(t);
+ int pts = SkPathOpsVerbToPoints(this->verb());
+ SkDVector dxdy = (*CurveDSlopeAtT[pts])(this->pts(), t);
+ SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
+ SkIntersections i;
+ int oppPts = SkPathOpsVerbToPoints(opp->verb());
+ (*CurveIntersectRay[oppPts])(opp->pts(), perp, &i);
+ int used = i.used();
+ for (int index = 0; index < used; ++index) {
+ if (cPt.roughlyEqual(i.pt(index))) {
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
+bool SkOpSegment::isXor() const {
+ return fContour->isXor();
+}
-SkOpSpan* SkOpSegment::markAndChaseDoneBinary(int index, int endIndex) {
- int step = SkSign32(endIndex - index);
- int min = SkMin32(index, endIndex);
- markDoneBinary(min);
- SkOpSpan* last = NULL;
+SkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) {
+ int step = start->step(end);
+ SkOpSpan* minSpan = start->starter(end);
+ markDone(minSpan);
+ SkOpSpanBase* last = NULL;
SkOpSegment* other = this;
- while ((other = other->nextChase(&index, &step, &min, &last))) {
+ while ((other = other->nextChase(&start, &step, &minSpan, &last))) {
if (other->done()) {
SkASSERT(!last);
break;
}
- other->markDoneBinary(min);
+ other->markDone(minSpan);
}
return last;
}
-SkOpSpan* SkOpSegment::markAndChaseDoneUnary(int index, int endIndex) {
- int step = SkSign32(endIndex - index);
- int min = SkMin32(index, endIndex);
- markDoneUnary(min);
- SkOpSpan* last = NULL;
+bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
+ SkOpSpanBase** lastPtr) {
+ SkOpSpan* spanStart = start->starter(end);
+ int step = start->step(end);
+ bool success = markWinding(spanStart, winding);
+ SkOpSpanBase* last = NULL;
SkOpSegment* other = this;
- while ((other = other->nextChase(&index, &step, &min, &last))) {
- if (other->done()) {
+ while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
+ if (spanStart->windSum() != SK_MinS32) {
+ SkASSERT(spanStart->windSum() == winding);
SkASSERT(!last);
break;
}
- other->markDoneUnary(min);
- }
- return last;
-}
-
-bool SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, SkOpSpan** lastPtr) {
- int index = angle->start();
- int endIndex = angle->end();
- return markAndChaseWinding(index, endIndex, winding, lastPtr);
-}
-
-bool SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, SkOpSpan** lastPtr) {
- int min = SkMin32(index, endIndex);
- int step = SkSign32(endIndex - index);
- bool success = markWinding(min, winding);
- SkOpSpan* last = NULL;
- 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);
- SkASSERT(!last);
- break;
- }
- (void) other->markWinding(min, winding);
+ (void) other->markWinding(spanStart, winding);
}
if (lastPtr) {
*lastPtr = last;
@@ -3864,37 +1305,32 @@
return success;
}
-bool SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding,
- SkOpSpan** lastPtr) {
- int min = SkMin32(index, endIndex);
- int step = SkSign32(endIndex - index);
- bool success = markWinding(min, winding, oppWinding);
- SkOpSpan* last = NULL;
+bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end,
+ int winding, int oppWinding, SkOpSpanBase** lastPtr) {
+ SkOpSpan* spanStart = start->starter(end);
+ int step = start->step(end);
+ bool success = markWinding(spanStart, winding, oppWinding);
+ SkOpSpanBase* last = NULL;
SkOpSegment* other = this;
- while ((other = other->nextChase(&index, &step, &min, &last))) {
- if (other->fTs[min].fWindSum != SK_MinS32) {
-#ifdef SK_DEBUG
- if (!other->fTs[min].fLoop) {
- if (fOperand == other->fOperand) {
-// FIXME: this is probably a bug -- rects4 asserts here
-// SkASSERT(other->fTs[min].fWindSum == winding);
-// FIXME: this is probably a bug -- rects3 asserts here
-// SkASSERT(other->fTs[min].fOppSum == oppWinding);
- } else {
-// FIXME: this is probably a bug -- issue414409b asserts here
-// SkASSERT(other->fTs[min].fWindSum == oppWinding);
-// FIXME: this is probably a bug -- skpwww_joomla_org_23 asserts here
-// SkASSERT(other->fTs[min].fOppSum == winding);
+ while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
+ if (spanStart->windSum() != SK_MinS32) {
+ if (this->operand() == other->operand()) {
+ SkASSERT(spanStart->windSum() == winding);
+ if (spanStart->oppSum() != oppWinding) {
+ this->globalState()->setWindingFailed();
+ return false;
}
+ } else {
+ SkASSERT(spanStart->windSum() == oppWinding);
+ SkASSERT(spanStart->oppSum() == winding);
}
SkASSERT(!last);
-#endif
break;
}
- if (fOperand == other->fOperand) {
- (void) other->markWinding(min, winding, oppWinding);
+ if (this->operand() == other->operand()) {
+ (void) other->markWinding(spanStart, winding, oppWinding);
} else {
- (void) other->markWinding(min, oppWinding, winding);
+ (void) other->markWinding(spanStart, oppWinding, winding);
}
}
if (lastPtr) {
@@ -3903,33 +1339,29 @@
return success;
}
-bool SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding,
- SkOpSpan** lastPtr) {
- int start = angle->start();
- int end = angle->end();
- return markAndChaseWinding(start, end, winding, oppWinding, lastPtr);
-}
-
-SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
+SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) {
SkASSERT(angle->segment() == this);
if (UseInnerWinding(maxWinding, sumWinding)) {
maxWinding = sumWinding;
}
- SkOpSpan* last;
- SkAssertResult(markAndChaseWinding(angle, maxWinding, &last));
+ SkOpSpanBase* last;
+ (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last);
#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);
+ SkDebugf("%s last seg=%d span=%d", __FUNCTION__,
+ last->segment()->debugID(), last->debugID());
+ if (!last->final()) {
+ SkDebugf(" windSum=");
+ SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
+ }
+ SkDebugf("\n");
}
#endif
return last;
}
-SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
- int oppSumWinding, const SkOpAngle* angle) {
+SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
+ int oppSumWinding, const SkOpAngle* angle) {
SkASSERT(angle->segment() == this);
if (UseInnerWinding(maxWinding, sumWinding)) {
maxWinding = sumWinding;
@@ -3937,440 +1369,161 @@
if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
oppMaxWinding = oppSumWinding;
}
- SkOpSpan* last;
+ SkOpSpanBase* last = NULL;
// caller doesn't require that this marks anything
- (void) markAndChaseWinding(angle, maxWinding, oppMaxWinding, &last);
+ (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last);
#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);
+ SkDebugf("%s last segment=%d span=%d", __FUNCTION__,
+ last->segment()->debugID(), last->debugID());
+ if (!last->final()) {
+ SkDebugf(" windSum=");
+ SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
+ }
+ SkDebugf(" \n");
}
#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());
+void SkOpSegment::markDone(SkOpSpan* span) {
+ SkASSERT(this == span->segment());
+ if (span->done()) {
+ return;
+ }
+#if DEBUG_MARK_DONE
+ debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum());
+#endif
+ span->setDone(true);
+ ++fDoneCount;
+ debugValidate();
+}
+
+bool SkOpSegment::markWinding(SkOpSpan* span, int winding) {
+ SkASSERT(this == span->segment());
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));
- debugValidate();
-}
-
-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));
- debugValidate();
-}
-
-void SkOpSegment::markDoneFinal(int index) {
- double referenceT = fTs[index].fT;
- int lesser = index;
- while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
- markOneDoneFinal(__FUNCTION__, lesser);
- }
- do {
- markOneDoneFinal(__FUNCTION__, index);
- } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
- debugValidate();
-}
-
-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));
- debugValidate();
-}
-
-void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) {
- SkOpSpan* span;
- (void) markOneWinding(funName, tIndex, winding, &span); // allowed to do nothing
- if (span->fDone) {
- return;
- }
- span->fDone = true;
- ++fDoneSpans;
-}
-
-void SkOpSegment::markOneDoneFinal(const char* funName, int tIndex) {
- SkOpSpan* span = &fTs[tIndex];
- if (span->fDone) {
- return;
- }
- span->fDone = true;
- ++fDoneSpans;
-}
-
-void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) {
- SkOpSpan* span = verifyOneWinding(funName, tIndex);
- if (!span) {
- return;
- }
- SkASSERT(!span->fDone);
- span->fDone = true;
- ++fDoneSpans;
-}
-
-void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) {
- SkOpSpan* span = verifyOneWindingU(funName, tIndex);
- if (!span) {
- return;
- }
- if (span->fWindSum == SK_MinS32) {
- SkDebugf("%s uncomputed\n", __FUNCTION__);
- }
- SkASSERT(!span->fDone);
- span->fDone = true;
- ++fDoneSpans;
-}
-
-bool SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding, SkOpSpan** lastPtr) {
- SkOpSpan* span = &fTs[tIndex];
- if (lastPtr) {
- *lastPtr = span;
- }
- if (span->fDone && !span->fSmall) {
+ if (span->done()) {
return false;
}
#if DEBUG_MARK_DONE
- debugShowNewWinding(funName, *span, winding);
+ debugShowNewWinding(__FUNCTION__, span, winding);
#endif
- SkASSERT(span->fWindSum == SK_MinS32 || span->fWindSum == winding);
-#if DEBUG_LIMIT_WIND_SUM
- SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
-#endif
- span->fWindSum = winding;
+ span->setWindSum(winding);
+ debugValidate();
return true;
}
-bool SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding,
- int oppWinding, SkOpSpan** lastPtr) {
- SkOpSpan* span = &fTs[tIndex];
- if (span->fDone && !span->fSmall) {
- return false;
- }
-#if DEBUG_MARK_DONE
- debugShowNewWinding(funName, *span, winding, oppWinding);
-#endif
- SkASSERT(span->fWindSum == SK_MinS32 || span->fWindSum == winding);
-#if DEBUG_LIMIT_WIND_SUM
- SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
-#endif
- span->fWindSum = winding;
- SkASSERT(span->fOppSum == SK_MinS32 || span->fOppSum == oppWinding);
-#if DEBUG_LIMIT_WIND_SUM
- SkASSERT(abs(oppWinding) <= DEBUG_LIMIT_WIND_SUM);
-#endif
- span->fOppSum = oppWinding;
- debugValidate();
- if (lastPtr) {
- *lastPtr = span;
- }
- return true;
-}
-
-// 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, bool* swap) 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);
- bool sumSet = false;
- if (fVerb == SkPath::kCubic_Verb) {
- SkDCubic cubic;
- cubic.set(edge);
- double inflectionTs[2];
- int inflections = cubic.findInflections(inflectionTs);
- // FIXME: this fixes cubicOp114 and breaks cubicOp58d
- // the trouble is that cubics with inflections confuse whether the curve breaks towards
- // or away, which in turn is used to determine if it is on the far right or left.
- // Probably a totally different approach is in order. At one time I tried to project a
- // horizontal ray to determine winding, but was confused by how to map the vertically
- // oriented winding computation over.
- if (0 && inflections) {
- double tLo = this->span(tStart).fT;
- double tHi = this->span(tEnd).fT;
- double tLoStart = tLo;
- for (int index = 0; index < inflections; ++index) {
- if (between(tLo, inflectionTs[index], tHi)) {
- tLo = inflectionTs[index];
- }
- }
- if (tLo != tLoStart && tLo != tHi) {
- SkDPoint sub[2];
- sub[0] = cubic.ptAtT(tLo);
- sub[1].set(edge[3]);
- SkDPoint ctrl[2];
- SkDCubic::SubDivide(fPts, sub[0], sub[1], tLo, tHi, ctrl);
- edge[0] = sub[0].asSkPoint();
- edge[1] = ctrl[0].asSkPoint();
- edge[2] = ctrl[1].asSkPoint();
- sum = (edge[0].fX - edge[3].fX) * (edge[0].fY + edge[3].fY);
- }
- }
- SkScalar lesser = SkTMin<SkScalar>(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);
- sumSet = true;
- }
- }
- }
- if (!sumSet) {
- for (int idx = 0; idx < points; ++idx){
- sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY);
- }
- }
- if (fVerb == SkPath::kCubic_Verb) {
- SkDCubic cubic;
- cubic.set(edge);
- *swap = sum > 0 && !cubic.monotonicInY() && !cubic.serpentine();
- } else {
- SkDQuad quad;
- quad.set(edge);
- *swap = sum > 0 && !quad.monotonicInY();
- }
- return sum <= 0;
-}
-
-bool SkOpSegment::monotonicInY(int tStart, int tEnd) const {
- SkASSERT(fVerb != SkPath::kLine_Verb);
- 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;
-}
-
-bool SkOpSegment::markWinding(int index, int winding) {
-// SkASSERT(!done());
- SkASSERT(winding);
- double referenceT = fTs[index].fT;
- int lesser = index;
- bool success = false;
- while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
- success |= markOneWinding(__FUNCTION__, lesser, winding, NULL);
- }
- do {
- success |= markOneWinding(__FUNCTION__, index, winding, NULL);
- } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
- debugValidate();
- return success;
-}
-
-bool SkOpSegment::markWinding(int index, int winding, int oppWinding) {
-// SkASSERT(!done());
+bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) {
+ SkASSERT(this == span->segment());
SkASSERT(winding || oppWinding);
- double referenceT = fTs[index].fT;
- int lesser = index;
- bool success = false;
- while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
- success |= markOneWinding(__FUNCTION__, lesser, winding, oppWinding, NULL);
+ if (span->done()) {
+ return false;
}
- do {
- success |= markOneWinding(__FUNCTION__, index, winding, oppWinding, NULL);
- } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenceT));
+#if DEBUG_MARK_DONE
+ debugShowNewWinding(__FUNCTION__, span, winding, oppWinding);
+#endif
+ span->setWindSum(winding);
+ span->setOppSum(oppWinding);
debugValidate();
- return success;
-}
-
-void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) {
- int nextDoorWind = SK_MaxS32;
- int nextOppWind = SK_MaxS32;
- // prefer exact matches
- if (tIndex > 0) {
- const SkOpSpan& below = fTs[tIndex - 1];
- if (below.fT == t) {
- nextDoorWind = below.fWindValue;
- nextOppWind = below.fOppValue;
- }
- }
- if (nextDoorWind == SK_MaxS32 && tIndex + 1 < fTs.count()) {
- const SkOpSpan& above = fTs[tIndex + 1];
- if (above.fT == t) {
- nextDoorWind = above.fWindValue;
- nextOppWind = above.fOppValue;
- }
- }
- if (nextDoorWind == SK_MaxS32 && 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;
- }
- }
-}
-
-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;
}
-static SkOpSegment* set_last(SkOpSpan** last, const SkOpSpan* endSpan) {
- if (last && !endSpan->fSmall) {
- *last = const_cast<SkOpSpan*>(endSpan); // FIXME: get rid of cast
+bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT,
+ const SkPoint& testPt) const {
+ const SkOpSegment* baseParent = base->segment();
+ if (this == baseParent && this == testParent && precisely_equal(base->fT, testT)) {
+ return true;
+ }
+ if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) {
+ return false;
+ }
+ return !ptsDisjoint(base->fT, base->fPt, testT, testPt);
+}
+
+static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) {
+ if (last) {
+ *last = endSpan;
}
return NULL;
}
-SkOpSegment* SkOpSegment::nextChase(int* indexPtr, int* stepPtr, int* minPtr,
- SkOpSpan** last) const {
- int origIndex = *indexPtr;
+bool SkOpSegment::monotonicInY(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
+ SkASSERT(fVerb != SkPath::kLine_Verb);
+ if (fVerb == SkPath::kQuad_Verb) {
+ SkDQuad dst = SkDQuad::SubDivide(fPts, start->t(), end->t());
+ return dst.monotonicInY();
+ }
+ SkASSERT(fVerb == SkPath::kCubic_Verb);
+ SkDCubic dst = SkDCubic::SubDivide(fPts, start->t(), end->t());
+ return dst.monotonicInY();
+}
+
+bool SkOpSegment::NextCandidate(SkOpSpanBase* span, SkOpSpanBase** start,
+ SkOpSpanBase** end) {
+ while (span->final() || span->upCast()->done()) {
+ if (span->final()) {
+ return false;
+ }
+ span = span->upCast()->next();
+ }
+ *start = span;
+ *end = span->upCast()->next();
+ return true;
+}
+
+SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr,
+ SkOpSpanBase** last) const {
+ SkOpSpanBase* origStart = *startPtr;
int step = *stepPtr;
- int end = nextExactSpan(origIndex, step);
- SkASSERT(end >= 0);
- const SkOpSpan& endSpan = this->span(end);
- SkOpAngle* angle = step > 0 ? endSpan.fFromAngle : endSpan.fToAngle;
- int foundIndex;
- int otherEnd;
+ SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev();
+ SkASSERT(endSpan);
+ SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle();
+ SkOpSpanBase* foundSpan;
+ SkOpSpanBase* otherEnd;
SkOpSegment* other;
if (angle == NULL) {
- if (endSpan.fT != 0 && endSpan.fT != 1) {
+ if (endSpan->t() != 0 && endSpan->t() != 1) {
return NULL;
}
- other = endSpan.fOther;
- foundIndex = endSpan.fOtherIndex;
- otherEnd = other->nextExactSpan(foundIndex, step);
+ SkOpPtT* otherPtT = endSpan->ptT()->next();
+ other = otherPtT->segment();
+ foundSpan = otherPtT->span();
+ otherEnd = step > 0 ? foundSpan->upCast()->next() : foundSpan->prev();
} else {
int loopCount = angle->loopCount();
if (loopCount > 2) {
- return set_last(last, &endSpan);
+ return set_last(last, endSpan);
}
const SkOpAngle* next = angle->next();
if (NULL == next) {
return NULL;
}
- if (angle->sign() != next->sign()) {
#if DEBUG_WINDING
+ if (angle->sign() != next->sign() && !angle->segment()->contour()->isXor()
+ && !next->segment()->contour()->isXor()) {
SkDebugf("%s mismatched signs\n", __FUNCTION__);
-#endif
- // return set_last(last, &endSpan);
}
+#endif
other = next->segment();
- foundIndex = end = next->start();
+ foundSpan = endSpan = next->start();
otherEnd = next->end();
}
- int foundStep = foundIndex < otherEnd ? 1 : -1;
+ int foundStep = foundSpan->step(otherEnd);
if (*stepPtr != foundStep) {
- return set_last(last, &endSpan);
+ return set_last(last, endSpan);
}
- SkASSERT(*indexPtr >= 0);
- if (otherEnd < 0) {
+ SkASSERT(*startPtr);
+ if (!otherEnd) {
return NULL;
}
// SkASSERT(otherEnd >= 0);
-#if 1
- int origMin = origIndex + (step < 0 ? step : 0);
- const SkOpSpan& orig = this->span(origMin);
-#endif
- int foundMin = SkMin32(foundIndex, otherEnd);
-#if 1
- const SkOpSpan& found = other->span(foundMin);
- if (found.fWindValue != orig.fWindValue || found.fOppValue != orig.fOppValue) {
- return set_last(last, &endSpan);
+ SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast();
+ SkOpSpan* foundMin = foundSpan->starter(otherEnd);
+ if (foundMin->windValue() != origMin->windValue()
+ || foundMin->oppValue() != origMin->oppValue()) {
+ return set_last(last, endSpan);
}
-#endif
- *indexPtr = foundIndex;
+ *startPtr = foundSpan;
*stepPtr = foundStep;
if (minPtr) {
*minPtr = foundMin;
@@ -4378,101 +1531,217 @@
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;
+static void clear_visited(SkOpSpan* span) {
+ // reset visited flag back to false
+ do {
+ SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
+ while ((ptT = ptT->next()) != stopPtT) {
+ SkOpSegment* opp = ptT->segment();
+ opp->resetVisited();
}
- return to;
- }
- return -1;
+ } while ((span = span->next()->upCastable()));
}
-// 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) {
+// look for pairs of undetected coincident curves
+// assumes that segments going in have visited flag clear
+// curve/curve intersection should now do a pretty good job of finding coincident runs so
+// this may be only be necessary for line/curve pairs -- so skip unless this is a line and the
+// the opp is not a line
+void SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
+ if (this->verb() != SkPath::kLine_Verb) {
+ return;
+ }
+ SkOpSpan* prior = NULL;
+ SkOpSpan* span = &fHead;
+ do {
+ SkOpPtT* ptT = span->ptT(), * spanStopPtT = ptT;
+ SkASSERT(ptT->span() == span);
+ while ((ptT = ptT->next()) != spanStopPtT) {
+ SkOpSegment* opp = ptT->span()->segment();
+ if (opp->setVisited()) {
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)) {
+ if (opp->verb() == SkPath::kLine_Verb) {
continue;
}
- return to;
- }
- }
- return -1;
-}
-
-void SkOpSegment::pinT(const SkPoint& pt, double* t) {
- if (pt == fPts[0]) {
- *t = 0;
- }
- int count = SkPathOpsVerbToPoints(fVerb);
- if (pt == fPts[count]) {
- *t = 1;
- }
-}
-
-bool SkOpSegment::reversePoints(const SkPoint& p1, const SkPoint& p2) const {
- SkASSERT(p1 != p2);
- int spanCount = count();
- int p1IndexMin = -1;
- int p2IndexMax = spanCount;
- for (int index = 0; index < spanCount; ++index) {
- const SkOpSpan& span = fTs[index];
- if (span.fPt == p1) {
- if (p1IndexMin < 0) {
- p1IndexMin = index;
+ if (span->containsCoincidence(opp)) { // FIXME: this assumes that if the opposite
+ // segment is coincident then no more coincidence
+ // needs to be detected. This may not be true.
+ continue;
}
- } else if (span.fPt == p2) {
- p2IndexMax = index;
+ if (span->containsCoinEnd(opp)) {
+ continue;
+ }
+ // if already visited and visited again, check for coin
+ if (span == &fHead) {
+ continue;
+ }
+ SkOpPtT* priorPtT = NULL, * priorStopPtT;
+ // find prior span containing opp segment
+ SkOpSegment* priorOpp = NULL;
+ prior = span;
+ while (!priorOpp && (prior = prior->prev())) {
+ priorStopPtT = priorPtT = prior->ptT();
+ while ((priorPtT = priorPtT->next()) != priorStopPtT) {
+ SkOpSegment* segment = priorPtT->span()->segment();
+ if (segment == opp) {
+ priorOpp = opp;
+ break;
+ }
+ }
+ }
+ if (!priorOpp) {
+ continue;
+ }
+ SkOpPtT* oppStart = prior->ptT();
+ SkOpPtT* oppEnd = span->ptT();
+ bool swapped = priorPtT->fT > ptT->fT;
+ if (swapped) {
+ SkTSwap(priorPtT, ptT);
+ SkTSwap(oppStart, oppEnd);
+ }
+ bool flipped = oppStart->fT > oppEnd->fT;
+ bool coincident;
+ if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
+ goto swapBack;
+ }
+ {
+ // average t, find mid pt
+ double midT = (prior->t() + span->t()) / 2;
+ SkPoint midPt = this->ptAtT(midT);
+ coincident = true;
+ // if the mid pt is not near either end pt, project perpendicular through opp seg
+ if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
+ && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
+ coincident = false;
+ SkIntersections i;
+ int ptCount = SkPathOpsVerbToPoints(this->verb());
+ SkVector dxdy = (*CurveSlopeAtT[ptCount])(pts(), midT);
+ SkDLine ray = {{{midPt.fX, midPt.fY},
+ {midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}};
+ int oppPtCount = SkPathOpsVerbToPoints(opp->verb());
+ (*CurveIntersectRay[oppPtCount])(opp->pts(), ray, &i);
+ // measure distance and see if it's small enough to denote coincidence
+ for (int index = 0; index < i.used(); ++index) {
+ SkDPoint oppPt = i.pt(index);
+ if (oppPt.approximatelyEqual(midPt)) {
+ SkVector oppDxdy = (*CurveSlopeAtT[oppPtCount])(opp->pts(),
+ i[index][0]);
+ oppDxdy.normalize();
+ dxdy.normalize();
+ SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON);
+ coincident |= flatness < 5000; // FIXME: replace with tuned value
+ }
+ }
+ }
+ }
+ if (coincident) {
+ // mark coincidence
+ coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator);
+ clear_visited(&fHead);
+ missingCoincidence(coincidences, allocator);
+ return;
+ }
+ swapBack:
+ if (swapped) {
+ SkTSwap(priorPtT, ptT);
+ }
}
- }
- return p1IndexMin > p2IndexMax;
+ } while ((span = span->next()->upCastable()));
+ clear_visited(&fHead);
}
-void SkOpSegment::setCoincidentRange(const SkPoint& startPt, const SkPoint& endPt,
- SkOpSegment* other) {
- int count = this->count();
- for (int index = 0; index < count; ++index) {
- SkOpSpan &span = fTs[index];
- if ((startPt == span.fPt || endPt == span.fPt) && other == span.fOther) {
- span.fCoincident = true;
+// Move nearby t values and pts so they all hang off the same span. Alignment happens later.
+bool SkOpSegment::moveNearby() {
+ debugValidate();
+ SkOpSpanBase* spanS = &fHead;
+ do {
+ SkOpSpanBase* test = spanS->upCast()->next();
+ SkOpSpanBase* next;
+ if (spanS->contains(test)) {
+ if (!test->final()) {
+ test->upCast()->detach(spanS->ptT());
+ continue;
+ } else if (spanS != &fHead) {
+ spanS->upCast()->detach(test->ptT());
+ spanS = test;
+ continue;
+ }
}
- }
+ do { // iterate through all spans associated with start
+ SkOpPtT* startBase = spanS->ptT();
+ next = test->final() ? NULL : test->upCast()->next();
+ do {
+ SkOpPtT* testBase = test->ptT();
+ do {
+ if (startBase == testBase) {
+ goto checkNextSpan;
+ }
+ if (testBase->duplicate()) {
+ continue;
+ }
+ if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) {
+ if (test == &this->fTail) {
+ if (spanS == &fHead) {
+ debugValidate();
+ return true; // if this span has collapsed, remove it from parent
+ }
+ this->fTail.merge(spanS->upCast());
+ debugValidate();
+ return true;
+ }
+ spanS->merge(test->upCast());
+ spanS->upCast()->setNext(next);
+ goto checkNextSpan;
+ }
+ } while ((testBase = testBase->next()) != test->ptT());
+ } while ((startBase = startBase->next()) != spanS->ptT());
+ checkNextSpan:
+ ;
+ } while ((test = next));
+ spanS = spanS->upCast()->next();
+ } while (!spanS->final());
+ debugValidate();
+ return true;
}
-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);
+bool SkOpSegment::operand() const {
+ return fContour->operand();
+}
+
+bool SkOpSegment::oppXor() const {
+ return fContour->oppXor();
+}
+
+bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const {
+ if (fVerb == SkPath::kLine_Verb) {
+ return false;
+ }
+ // quads (and cubics) can loop back to nearly a line so that an opposite curve
+ // hits in two places with very different t values.
+ // OPTIMIZATION: curves could be preflighted so that, for example, something like
+ // 'controls contained by ends' could avoid this check for common curves
+ // 'ends are extremes in x or y' is cheaper to compute and real-world common
+ // on the other hand, the below check is relatively inexpensive
+ double midT = (t1 + t2) / 2;
+ SkPoint midPt = this->ptAtT(midT);
+ double seDistSq = SkTMax(pt1.distanceToSqd(pt2) * 2, FLT_EPSILON * 2);
+ return midPt.distanceToSqd(pt1) > seDistSq || midPt.distanceToSqd(pt2) > seDistSq;
+}
+
+void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
+ int* maxWinding, int* sumWinding) {
+ int deltaSum = SpanSign(start, end);
+ *maxWinding = *sumMiWinding;
+ *sumWinding = *sumMiWinding -= deltaSum;
+ SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
+}
+
+void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
+ int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding,
+ int* oppSumWinding) {
+ int deltaSum = SpanSign(start, end);
+ int oppDeltaSum = OppSign(start, end);
if (operand()) {
*maxWinding = *sumSuWinding;
*sumWinding = *sumSuWinding -= deltaSum;
@@ -4484,130 +1753,94 @@
*oppMaxWinding = *sumSuWinding;
*oppSumWinding = *sumSuWinding -= oppDeltaSum;
}
-#if DEBUG_LIMIT_WIND_SUM
- SkASSERT(abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
- SkASSERT(abs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
-#endif
-}
-
-void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding,
- int* maxWinding, int* sumWinding) {
- int deltaSum = spanSign(index, endIndex);
- *maxWinding = *sumMiWinding;
- *sumWinding = *sumMiWinding -= deltaSum;
-#if DEBUG_LIMIT_WIND_SUM
- SkASSERT(abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
-#endif
+ SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
+ SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
}
void SkOpSegment::sortAngles() {
- int spanCount = fTs.count();
- if (spanCount <= 2) {
- return;
- }
- int index = 0;
+ SkOpSpanBase* span = &this->fHead;
do {
- SkOpAngle* fromAngle = fTs[index].fFromAngle;
- SkOpAngle* toAngle = fTs[index].fToAngle;
+ SkOpAngle* fromAngle = span->fromAngle();
+ SkOpAngle* toAngle = span->final() ? NULL : span->upCast()->toAngle();
if (!fromAngle && !toAngle) {
- index += 1;
continue;
}
- SkOpAngle* baseAngle = NULL;
- if (fromAngle) {
- baseAngle = fromAngle;
- if (inLoop(baseAngle, spanCount, &index)) {
- continue;
- }
- }
#if DEBUG_ANGLE
bool wroteAfterHeader = false;
#endif
- if (toAngle) {
- if (!baseAngle) {
- baseAngle = toAngle;
- if (inLoop(baseAngle, spanCount, &index)) {
- continue;
- }
- } else {
- SkDEBUGCODE(int newIndex = index);
- SkASSERT(!inLoop(baseAngle, spanCount, &newIndex) && newIndex == index);
+ SkOpAngle* baseAngle = fromAngle;
+ if (fromAngle && toAngle) {
#if DEBUG_ANGLE
- SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
- index);
- wroteAfterHeader = true;
+ SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(),
+ span->debugID());
+ wroteAfterHeader = true;
#endif
- baseAngle->insert(toAngle);
- }
+ fromAngle->insert(toAngle);
+ } else if (!fromAngle) {
+ baseAngle = toAngle;
}
- SkOpAngle* nextFrom, * nextTo;
- int firstIndex = index;
+ SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
do {
- SkOpSpan& span = fTs[index];
- SkOpSegment* other = span.fOther;
- SkOpSpan& oSpan = other->fTs[span.fOtherIndex];
- SkOpAngle* oAngle = oSpan.fFromAngle;
+ SkOpSpanBase* oSpan = ptT->span();
+ if (oSpan == span) {
+ continue;
+ }
+ SkOpAngle* oAngle = oSpan->fromAngle();
if (oAngle) {
#if DEBUG_ANGLE
if (!wroteAfterHeader) {
- SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
- index);
+ SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
+ span->t(), span->debugID());
wroteAfterHeader = true;
}
#endif
- if (!oAngle->loopContains(*baseAngle)) {
+ if (!oAngle->loopContains(baseAngle)) {
baseAngle->insert(oAngle);
}
}
- oAngle = oSpan.fToAngle;
- if (oAngle) {
+ if (!oSpan->final()) {
+ oAngle = oSpan->upCast()->toAngle();
+ if (oAngle) {
#if DEBUG_ANGLE
- if (!wroteAfterHeader) {
- SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
- index);
- wroteAfterHeader = true;
- }
+ if (!wroteAfterHeader) {
+ SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
+ span->t(), span->debugID());
+ wroteAfterHeader = true;
+ }
#endif
- if (!oAngle->loopContains(*baseAngle)) {
- baseAngle->insert(oAngle);
+ if (!oAngle->loopContains(baseAngle)) {
+ baseAngle->insert(oAngle);
+ }
}
}
- if (++index == spanCount) {
- break;
+ } while ((ptT = ptT->next()) != stopPtT);
+ if (baseAngle->loopCount() == 1) {
+ span->setFromAngle(NULL);
+ if (toAngle) {
+ span->upCast()->setToAngle(NULL);
}
- nextFrom = fTs[index].fFromAngle;
- nextTo = fTs[index].fToAngle;
- } while (fromAngle == nextFrom && toAngle == nextTo);
- if (baseAngle && baseAngle->loopCount() == 1) {
- index = firstIndex;
- do {
- SkOpSpan& span = fTs[index];
- span.fFromAngle = span.fToAngle = NULL;
- if (++index == spanCount) {
- break;
- }
- nextFrom = fTs[index].fFromAngle;
- nextTo = fTs[index].fToAngle;
- } while (fromAngle == nextFrom && toAngle == nextTo);
baseAngle = NULL;
}
#if DEBUG_SORT
SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
#endif
- } while (index < spanCount);
+ } while (!span->final() && (span = span->upCast()->next()));
}
// return true if midpoints were computed
-bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
+bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
+ SkPoint edge[4]) const {
SkASSERT(start != end);
- edge[0] = fTs[start].fPt;
+ const SkOpPtT& startPtT = *start->ptT();
+ const SkOpPtT& endPtT = *end->ptT();
+ edge[0] = startPtT.fPt;
int points = SkPathOpsVerbToPoints(fVerb);
- edge[points] = fTs[end].fPt;
+ edge[points] = endPtT.fPt;
if (fVerb == SkPath::kLine_Verb) {
return false;
}
- double startT = fTs[start].fT;
- double endT = fTs[end].fT;
+ double startT = startPtT.fT;
+ double endT = endPtT.fT;
if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
// don't compute midpoints if we already have them
if (fVerb == SkPath::kQuad_Verb) {
@@ -4637,17 +1870,19 @@
return true;
}
-// return true if midpoints were computed
-bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const {
+bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
+ SkDCubic* result) const {
SkASSERT(start != end);
- (*result)[0].set(fTs[start].fPt);
+ const SkOpPtT& startPtT = *start->ptT();
+ const SkOpPtT& endPtT = *end->ptT();
+ (*result)[0].set(startPtT.fPt);
int points = SkPathOpsVerbToPoints(fVerb);
- (*result)[points].set(fTs[end].fPt);
+ (*result)[points].set(endPtT.fPt);
if (fVerb == SkPath::kLine_Verb) {
return false;
}
- double startT = fTs[start].fT;
- double endT = fTs[end].fT;
+ double startT = startPtT.fT;
+ double endT = endPtT.fT;
if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
// don't compute midpoints if we already have them
if (fVerb == SkPath::kQuad_Verb) {
@@ -4655,7 +1890,7 @@
return false;
}
SkASSERT(fVerb == SkPath::kCubic_Verb);
- if (start < end) {
+ if (startT == 0) {
(*result)[1].set(fPts[1]);
(*result)[2].set(fPts[2]);
return false;
@@ -4673,49 +1908,29 @@
return true;
}
-void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const {
+void SkOpSegment::subDivideBounds(const SkOpSpanBase* start, const SkOpSpanBase* end,
+ SkPathOpsBounds* bounds) const {
SkPoint edge[4];
subDivide(start, end, edge);
(bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge);
}
-void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* 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<SkPoint, true>* 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) {
- int tCount = fTs.count();
- int index;
- for (index = 0; index < tCount; ++index) {
- if (!fTs[index].fDone) {
+void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) {
+ SkOpSpan* span = this->head();
+ do {
+ if (!span->done()) {
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;
+ } while ((span = span->next()->upCastable()));
+ SkASSERT(span);
+ *start = span;
+ *end = span->next();
}
-int SkOpSegment::updateOppWinding(int index, int endIndex) const {
- int lesser = SkMin32(index, endIndex);
- int oppWinding = oppSum(lesser);
- int oppSpanWinding = oppSign(index, endIndex);
+int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
+ const SkOpSpan* lesser = start->starter(end);
+ int oppWinding = lesser->oppSum();
+ int oppSpanWinding = SkOpSegment::OppSign(start, end);
if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
&& oppWinding != SK_MaxS32) {
oppWinding -= oppSpanWinding;
@@ -4724,24 +1939,24 @@
}
int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
- int startIndex = angle->start();
- int endIndex = angle->end();
- return updateOppWinding(endIndex, startIndex);
+ const SkOpSpanBase* startSpan = angle->start();
+ const SkOpSpanBase* endSpan = angle->end();
+ return updateOppWinding(endSpan, startSpan);
}
int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
- int startIndex = angle->start();
- int endIndex = angle->end();
- return updateOppWinding(startIndex, endIndex);
+ const SkOpSpanBase* startSpan = angle->start();
+ const SkOpSpanBase* endSpan = angle->end();
+ return updateOppWinding(startSpan, endSpan);
}
-int SkOpSegment::updateWinding(int index, int endIndex) const {
- int lesser = SkMin32(index, endIndex);
- int winding = windSum(lesser);
+int SkOpSegment::updateWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
+ const SkOpSpan* lesser = start->starter(end);
+ int winding = lesser->windSum();
if (winding == SK_MinS32) {
return winding;
}
- int spanWinding = spanSign(index, endIndex);
+ int spanWinding = SkOpSegment::SpanSign(start, end);
if (winding && UseInnerWinding(winding - spanWinding, winding)
&& winding != SK_MaxS32) {
winding -= spanWinding;
@@ -4750,26 +1965,15 @@
}
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;
+ const SkOpSpanBase* startSpan = angle->start();
+ const SkOpSpanBase* endSpan = angle->end();
+ return updateWinding(endSpan, startSpan);
}
int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const {
- int startIndex = angle->start();
- int endIndex = angle->end();
- return updateWindingReverse(endIndex, startIndex);
+ const SkOpSpanBase* startSpan = angle->start();
+ const SkOpSpanBase* endSpan = angle->end();
+ return updateWinding(startSpan, endSpan);
}
// OPTIMIZATION: does the following also work, and is it any faster?
@@ -4784,25 +1988,17 @@
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
+int SkOpSegment::windingAtT(double tHit, const SkOpSpan* span, bool crossOpp,
+ SkScalar* dx) const {
+ if (approximately_zero(tHit - span->t())) { // if we hit the end of a span, disregard
return SK_MinS32;
}
- int winding = crossOpp ? oppSum(tIndex) : windSum(tIndex);
+ int winding = crossOpp ? span->oppSum() : span->windSum();
SkASSERT(winding != SK_MinS32);
- int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
+ int windVal = crossOpp ? span->oppValue() : span->windValue();
#if DEBUG_WINDING_AT_T
SkDebugf("%s id=%d opp=%d tHit=%1.9g t=%1.9g oldWinding=%d windValue=%d", __FUNCTION__,
- debugID(), crossOpp, tHit, t(tIndex), winding, windVal);
+ debugID(), crossOpp, tHit, span->t(), 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;
@@ -4828,20 +2024,6 @@
}
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;
+ const SkOpSpan* minSpan = angle->start()->starter(angle->end());
+ return minSpan->windSum();
}