fix minor skp-found bugs
remove globals from pathops_unittest
BUG=skia:2460
TBR=mtklein
Author: caryclark@google.com
Review URL: https://codereview.chromium.org/239563004
git-svn-id: http://skia.googlecode.com/svn/trunk@14378 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index dc1063c..dd51195 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -494,7 +494,18 @@
cubicNearEnd(c1, false, c2, c2Bounds);
}
if (!(exactEndBits & 8)) {
+ if (selfIntersect && fUsed) {
+ return fUsed;
+ }
cubicNearEnd(c1, true, c2, c2Bounds);
+ if (selfIntersect && fUsed && ((approximately_less_than_zero(fT[0][0])
+ && approximately_less_than_zero(fT[1][0]))
+ || (approximately_greater_than_one(fT[0][0])
+ && approximately_greater_than_one(fT[1][0])))) {
+ SkASSERT(fUsed == 1);
+ fUsed = 0;
+ return fUsed;
+ }
}
if (!selfIntersect) {
SkDRect c1Bounds;
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index f1adce2..8969539 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -292,7 +292,7 @@
int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
double x, bool flipped) {
- fMax = 2;
+ fMax = 3; // cleanup parallel lines will bring this back line
// see if end points intersect the opposite line
double t;
SkDPoint topPt = { x, top };
@@ -344,6 +344,7 @@
}
}
cleanUpParallelLines(result == 2);
+ SkASSERT(fUsed <= 2);
return fUsed;
}
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index 45daa10..1b9d8cc 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -98,7 +98,7 @@
, fLine(l)
, fIntersections(i)
, fAllowNear(true) {
- i->setMax(2);
+ i->setMax(3); // allow short partial coincidence plus discrete intersection
}
void allowNear(bool allow) {
@@ -331,6 +331,9 @@
*pt = fLine[1];
*lineT = 1;
}
+ if (fIntersections->used() > 0 && approximately_equal((*fIntersections)[1][0], *lineT)) {
+ return false;
+ }
if (gridPt == fQuad[0].asSkPoint()) {
*pt = fQuad[0];
*quadT = 0;
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index 119ca78..eced4dd 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -164,7 +164,7 @@
quad.set(a);
SkDLine line;
line.set(b);
- fMax = 2;
+ fMax = 3; // 2; permit small coincident segment + non-coincident intersection
return intersect(quad, line);
}
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index 62cf4b0..094b22c 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -321,9 +321,11 @@
fUnorderable = true;
return false;
}
+ int saveEnd = fEnd;
fEnd = checkEnd - step;
setSpans();
setSector();
+ fEnd = saveEnd;
return !fUnorderable;
}
@@ -658,6 +660,9 @@
}
SkOpAngle* next = fNext;
if (next->fNext == this) {
+ if (angle->overlap(*this)) {
+ return;
+ }
if (singleton || angle->after(this)) {
this->fNext = angle;
angle->fNext = next;
@@ -671,6 +676,9 @@
SkOpAngle* last = this;
do {
SkASSERT(last->fNext == next);
+ if (angle->overlap(*last) || angle->overlap(*next)) {
+ return;
+ }
if (angle->after(last)) {
last->fNext = angle;
angle->fNext = next;
@@ -701,6 +709,33 @@
return fLastMarked;
}
+bool SkOpAngle::loopContains(const SkOpAngle& test) const {
+ if (!fNext) {
+ return false;
+ }
+ const SkOpAngle* first = this;
+ const SkOpAngle* loop = this;
+ const SkOpSegment* tSegment = test.fSegment;
+ double tStart = tSegment->span(test.fStart).fT;
+ double tEnd = tSegment->span(test.fEnd).fT;
+ do {
+ const SkOpSegment* lSegment = loop->fSegment;
+ // FIXME : use precisely_equal ? or compare points exactly ?
+ if (lSegment != tSegment) {
+ continue;
+ }
+ double lStart = lSegment->span(loop->fStart).fT;
+ if (lStart != tEnd) {
+ continue;
+ }
+ double lEnd = lSegment->span(loop->fEnd).fT;
+ if (lEnd == tStart) {
+ return true;
+ }
+ } while ((loop = loop->fNext) != first);
+ return false;
+}
+
int SkOpAngle::loopCount() const {
int count = 0;
const SkOpAngle* first = this;
@@ -813,6 +848,23 @@
return true;
}
+bool SkOpAngle::overlap(const SkOpAngle& other) const {
+ int min = SkTMin(fStart, fEnd);
+ const SkOpSpan& span = fSegment->span(min);
+ const SkOpSegment* oSeg = other.fSegment;
+ int oMin = SkTMin(other.fStart, other.fEnd);
+ const SkOpSpan& oSpan = oSeg->span(oMin);
+ if (!span.fSmall && !oSpan.fSmall) {
+ return false;
+ }
+ if (fSegment->span(fStart).fPt != oSeg->span(other.fStart).fPt) {
+ return false;
+ }
+ // see if small span is contained by opposite span
+ return span.fSmall ? oSeg->containsPt(fSegment->span(fEnd).fPt, other.fEnd, other.fStart)
+ : fSegment->containsPt(oSeg->span(other.fEnd).fPt, fEnd, fStart);
+}
+
// OPTIMIZE: if this shows up in a profile, add a previous pointer
// as is, this should be rarely called
SkOpAngle* SkOpAngle::previous() const {
diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h
index 01150e6..e566913 100644
--- a/src/pathops/SkOpAngle.h
+++ b/src/pathops/SkOpAngle.h
@@ -24,6 +24,7 @@
kBinaryOpp,
};
+
int end() const {
return fEnd;
}
@@ -37,6 +38,7 @@
void insert(SkOpAngle* );
bool isHorizontal() const;
SkOpSpan* lastMarked() const;
+ bool loopContains(const SkOpAngle& ) const;
int loopCount() const;
void markStops();
bool merge(SkOpAngle* );
@@ -104,6 +106,7 @@
double midT() const;
bool oppositePlanes(const SkOpAngle& rh) const;
bool orderable(const SkOpAngle& rh) const; // false == this < rh ; true == this > rh
+ bool overlap(const SkOpAngle& test) const;
void setCurveHullSweep();
void setSector();
void setSpans();
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index db805a2..e3137b7 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -211,9 +211,12 @@
}
bool swapStart = startT > endT;
bool swapOther = oStartT > oEndT;
+ const SkPoint* startPt = &coincidence.fPts[0];
+ const SkPoint* endPt = &coincidence.fPts[1];
if (swapStart) {
- SkTSwap<double>(startT, endT);
- SkTSwap<double>(oStartT, oEndT);
+ SkTSwap(startT, endT);
+ SkTSwap(oStartT, oEndT);
+ SkTSwap(startPt, endPt);
}
bool cancel = swapOther != swapStart;
int step = swapStart ? -1 : 1;
@@ -222,17 +225,18 @@
if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
bool added = false;
if (oMatchStart != 0) {
- added = thisOne.joinCoincidence(&other, oMatchStart, oStep, cancel);
+ const SkPoint& oMatchStartPt = cancel ? *endPt : *startPt;
+ added = thisOne.joinCoincidence(&other, oMatchStart, oMatchStartPt, oStep, cancel);
}
if (!cancel && startT != 0 && !added) {
- (void) other.joinCoincidence(&thisOne, startT, step, cancel);
+ (void) other.joinCoincidence(&thisOne, startT, *startPt, step, cancel);
}
}
double oMatchEnd = cancel ? oStartT : oEndT;
if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
bool added = false;
if (cancel && endT != 1 && !added) {
- (void) other.joinCoincidence(&thisOne, endT, -step, cancel);
+ (void) other.joinCoincidence(&thisOne, endT, *endPt, -step, cancel);
}
}
}
@@ -329,7 +333,7 @@
continue;
}
fDone = false;
- SkPoint testXY = testSegment->activeLeftTop(true, NULL);
+ SkPoint testXY = testSegment->activeLeftTop(NULL);
if (*topStart) {
if (testXY.fY < topLeft.fY) {
continue;
diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp
index ae72e29..c14af9a 100644
--- a/src/pathops/SkOpEdgeBuilder.cpp
+++ b/src/pathops/SkOpEdgeBuilder.cpp
@@ -13,7 +13,7 @@
fOperand = false;
fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
: kWinding_PathOpsMask;
-#ifdef SK_DEBUG
+#if defined(SK_DEBUG) || !FORCE_RELEASE
SkPathOpsDebug::gContourID = 0;
SkPathOpsDebug::gSegmentID = 0;
#endif
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 67f9fb2..0e48b3f 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -70,16 +70,12 @@
int next = nextExactSpan(index, 1);
if (next > 0) {
const SkOpSpan& upSpan = fTs[index];
- if (upSpan.fUnsortableStart) {
- *sortable = false;
- return NULL;
- }
if (upSpan.fWindValue || upSpan.fOppValue) {
if (*end < 0) {
*start = index;
*end = next;
}
- if (!upSpan.fDone && !upSpan.fUnsortableEnd) {
+ if (!upSpan.fDone) {
if (upSpan.fWindSum != SK_MinS32) {
return spanToAngle(index, next);
}
@@ -93,10 +89,6 @@
// edge leading into junction
if (prev >= 0) {
const SkOpSpan& downSpan = fTs[prev];
- if (downSpan.fUnsortableEnd) {
- *sortable = false;
- return NULL;
- }
if (downSpan.fWindValue || downSpan.fOppValue) {
if (*end < 0) {
*start = index;
@@ -123,19 +115,15 @@
return other->activeAngleInner(oIndex, start, end, done, sortable);
}
-SkPoint SkOpSegment::activeLeftTop(bool onlySortable, int* firstT) const {
+SkPoint SkOpSegment::activeLeftTop(int* firstT) const {
SkASSERT(!done());
SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
int count = fTs.count();
// see if either end is not done since we want smaller Y of the pair
bool lastDone = true;
- bool lastUnsortable = false;
double lastT = -1;
for (int index = 0; index < count; ++index) {
const SkOpSpan& span = fTs[index];
- if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
- goto next;
- }
if (span.fDone && lastDone) {
goto next;
}
@@ -164,7 +152,6 @@
}
next:
lastDone = span.fDone;
- lastUnsortable = span.fUnsortableEnd;
}
return topPt;
}
@@ -345,16 +332,19 @@
do {
workPt = &fTs[++tIndex].fPt;
} while (nextPt == *workPt);
+ const SkPoint* oWorkPt;
do {
- workPt = &other->fTs[++oIndex].fPt;
- } while (nextPt == *workPt);
+ 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;
}
- addTPair(tStart, other, oStart, false, nextPt);
+ if (*workPt == *oWorkPt) {
+ addTPair(tStart, other, oStart, false, nextPt);
+ }
} while (endPt != nextPt);
}
@@ -618,8 +608,6 @@
span->fLoop = false;
span->fSmall = false;
span->fTiny = false;
- span->fUnsortableStart = false;
- span->fUnsortableEnd = false;
int less = -1;
// find range of spans with nearly the same point as this one
while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) {
@@ -834,18 +822,27 @@
aligned = true;
}
double oT = oSpan->fT;
- if (oT == 0 || oT == 1) {
+ if (oT == 0) {
return aligned;
}
int oStart = other->nextSpan(oIndex, -1) + 1;
- int oEnd = other->nextSpan(oIndex, 1);
oSpan = &other->fTs[oStart];
+ int otherIndex = oStart;
+ if (oT == 1) {
+ if (aligned) {
+ while (oSpan->fPt == thisPt && oSpan->fT != 1) {
+ oSpan->fTiny = true;
+ ++oSpan;
+ }
+ }
+ return aligned;
+ }
oT = oSpan->fT;
+ int oEnd = other->nextSpan(oIndex, 1);
bool oAligned = false;
if (oSpan->fPt != thisPt) {
oAligned |= other->alignSpan(oStart, oT, thisPt);
}
- int otherIndex = oStart;
while (++otherIndex < oEnd) {
SkOpSpan* oNextSpan = &other->fTs[otherIndex];
if (oNextSpan->fT != oT || oNextSpan->fPt != thisPt) {
@@ -1352,14 +1349,17 @@
nextAngle->setLastMarked(last);
}
-void SkOpSegment::constructLine(SkPoint shortLine[2]) {
- addLine(shortLine, false, false);
- addT(NULL, shortLine[0], 0);
- addT(NULL, shortLine[1], 1);
- addStartSpan(1);
- addEndSpan(1);
- SkOpAngle& angle = fAngles.push_back();
- angle.set(this, 0, 1);
+bool SkOpSegment::containsPt(const SkPoint& pt, int index, int endIndex) const {
+ int step = index < endIndex ? 1 : -1;
+ do {
+ const SkOpSpan& span = this->span(index);
+ if (span.fPt == pt) {
+ const SkOpSpan& endSpan = this->span(endIndex);
+ return span.fT == endSpan.fT && pt != endSpan.fPt;
+ }
+ index += step;
+ } while (index != endIndex);
+ return false;
}
int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
@@ -1923,7 +1923,7 @@
missing.fPt)) {
continue;
}
- int otherTIndex = missingOther->findT(missing.fOtherT, missing.fSegment);
+ int otherTIndex = missingOther->findT(missing.fOtherT, missing.fPt, missing.fSegment);
const SkOpSpan& otherSpan = missingOther->span(otherTIndex);
if (otherSpan.fSmall) {
const SkOpSpan* nextSpan = &otherSpan;
@@ -1955,7 +1955,9 @@
void SkOpSegment::checkSmallCoincidence(const SkOpSpan& span,
SkTArray<MissingSpan, true>* checkMultiple) {
SkASSERT(span.fSmall);
- SkASSERT(span.fWindValue);
+ if (0 && !span.fWindValue) {
+ return;
+ }
SkASSERT(&span < fTs.end() - 1);
const SkOpSpan* next = &span + 1;
SkASSERT(!next->fSmall || checkMultiple);
@@ -2271,11 +2273,13 @@
bool sortable = calcWinding != SK_NaN32;
if (!sortable) {
*unsortable = true;
+ markDoneBinary(SkMin32(startIndex, endIndex));
return NULL;
}
SkOpAngle* angle = spanToAngle(end, startIndex);
if (angle->unorderable()) {
*unsortable = true;
+ markDoneBinary(SkMin32(startIndex, endIndex));
return NULL;
}
#if DEBUG_SORT
@@ -2283,6 +2287,11 @@
angle->debugLoop();
#endif
int sumMiWinding = updateWinding(endIndex, startIndex);
+ if (sumMiWinding == SK_MinS32) {
+ *unsortable = true;
+ markDoneBinary(SkMin32(startIndex, endIndex));
+ return NULL;
+ }
int sumSuWinding = updateOppWinding(endIndex, startIndex);
if (operand()) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
@@ -2302,6 +2311,7 @@
if (!foundAngle || (foundDone && activeCount & 1)) {
if (nextSegment->isTiny(nextAngle)) {
*unsortable = true;
+ markDoneBinary(SkMin32(startIndex, endIndex));
return NULL;
}
foundAngle = nextAngle;
@@ -2393,6 +2403,7 @@
bool sortable = calcWinding != SK_NaN32;
if (!sortable) {
*unsortable = true;
+ markDoneUnary(SkMin32(startIndex, endIndex));
return NULL;
}
SkOpAngle* angle = spanToAngle(end, startIndex);
@@ -2415,6 +2426,7 @@
if (!foundAngle || (foundDone && activeCount & 1)) {
if (nextSegment->isTiny(nextAngle)) {
*unsortable = true;
+ markDoneUnary(SkMin32(startIndex, endIndex));
return NULL;
}
foundAngle = nextAngle;
@@ -2433,7 +2445,6 @@
SkOpSpan* last = nextAngle->lastMarked();
if (last) {
SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
- // assert here that span isn't already in array
*chase->append() = last;
#if DEBUG_WINDING
SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
@@ -2584,7 +2595,7 @@
return -1;
}
-int SkOpSegment::findT(double t, const SkOpSegment* match) const {
+int SkOpSegment::findT(double t, const SkPoint& pt, const SkOpSegment* match) const {
int count = this->count();
for (int index = 0; index < count; ++index) {
const SkOpSpan& span = fTs[index];
@@ -2592,18 +2603,28 @@
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) {
+SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsortable,
+ bool firstPass) {
// 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(true, &firstT);
+ /* SkPoint topPt = */ activeLeftTop(&firstT);
if (firstT < 0) {
- *unsortable = true;
+ *unsortable = !firstPass;
firstT = 0;
while (fTs[firstT].fDone) {
SkASSERT(firstT < fTs.count());
@@ -2655,14 +2676,24 @@
#endif
// skip edges that have already been processed
angle = firstAngle;
- SkOpSegment* leftSegment;
+ SkOpSegment* leftSegment = NULL;
+ bool looped = false;
do {
-// SkASSERT(!angle->unsortable());
- leftSegment = angle->segment();
- *tIndexPtr = angle->end();
- *endIndexPtr = angle->start();
+ *unsortable = angle->unorderable();
+ if (firstPass || !*unsortable) {
+ leftSegment = angle->segment();
+ *tIndexPtr = angle->end();
+ *endIndexPtr = angle->start();
+ if (!leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone) {
+ break;
+ }
+ }
angle = angle->next();
- } while (leftSegment->fTs[SkMin32(*tIndexPtr, *endIndexPtr)].fDone);
+ looped = true;
+ } while (angle != firstAngle);
+ if (angle == firstAngle && looped) {
+ return NULL;
+ }
if (leftSegment->verb() >= SkPath::kQuad_Verb) {
const int tIndex = *tIndexPtr;
const int endIndex = *endIndexPtr;
@@ -2670,8 +2701,9 @@
bool swap = !leftSegment->monotonicInY(tIndex, endIndex)
&& !leftSegment->serpentine(tIndex, endIndex);
#if DEBUG_SWAP_TOP
- SkDebugf("%s swap=%d serpentine=%d containedByEnds=%d monotonic=%d\n", __FUNCTION__,
- swap,
+ SkDebugf("%s swap=%d inflections=%d serpentine=%d controlledbyends=%d monotonic=%d\n",
+ __FUNCTION__,
+ swap, leftSegment->debugInflections(tIndex, endIndex),
leftSegment->serpentine(tIndex, endIndex),
leftSegment->controlsContainedByEnds(tIndex, endIndex),
leftSegment->monotonicInY(tIndex, endIndex));
@@ -2840,13 +2872,6 @@
#endif
}
-bool SkOpSegment::isSmall(const SkOpAngle* angle) const {
- int start = angle->start();
- int end = angle->end();
- const SkOpSpan& mSpan = fTs[SkMin32(start, end)];
- return mSpan.fSmall;
-}
-
bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
int start = angle->start();
int end = angle->end();
@@ -2863,8 +2888,9 @@
// 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, int step, bool cancel) {
- int otherTIndex = other->findT(otherT, this);
+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;
@@ -3106,7 +3132,9 @@
debugShowNewWinding(funName, span, winding);
#endif
SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
- SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
+#if DEBUG_LIMIT_WIND_SUM
+ SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
+#endif
span.fWindSum = winding;
return &span;
}
@@ -3121,10 +3149,14 @@
debugShowNewWinding(funName, span, winding, oppWinding);
#endif
SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
- SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
+#if DEBUG_LIMIT_WIND_SUM
+ SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
+#endif
span.fWindSum = winding;
SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
- SkASSERT(abs(oppWinding) <= SkPathOpsDebug::gMaxWindSum);
+#if DEBUG_LIMIT_WIND_SUM
+ SkASSERT(abs(oppWinding) <= DEBUG_LIMIT_WIND_SUM);
+#endif
span.fOppSum = oppWinding;
debugValidate();
return &span;
@@ -3157,9 +3189,7 @@
}
bool SkOpSegment::monotonicInY(int tStart, int tEnd) const {
- if (fVerb == SkPath::kLine_Verb) {
- return false;
- }
+ SkASSERT(fVerb != SkPath::kLine_Verb);
if (fVerb == SkPath::kQuad_Verb) {
SkDQuad dst = SkDQuad::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
return dst.monotonicInY();
@@ -3210,33 +3240,6 @@
return &span;
}
-// note that just because a span has one end that is unsortable, that's
-// not enough to mark it done. The other end may be sortable, allowing the
-// span to be added.
-// FIXME: if abs(start - end) > 1, mark intermediates as unsortable on both ends
-void SkOpSegment::markUnsortable(int start, int end) {
- SkOpSpan* span = &fTs[start];
- if (start < end) {
-#if DEBUG_UNSORTABLE
- debugShowNewWinding(__FUNCTION__, *span, 0);
-#endif
- span->fUnsortableStart = true;
- } else {
- --span;
-#if DEBUG_UNSORTABLE
- debugShowNewWinding(__FUNCTION__, *span, 0);
-#endif
- span->fUnsortableEnd = true;
- }
- if (!span->fUnsortableStart || !span->fUnsortableEnd || span->fDone) {
- debugValidate();
- return;
- }
- span->fDone = true;
- fDoneSpans++;
- debugValidate();
-}
-
void SkOpSegment::markWinding(int index, int winding) {
// SkASSERT(!done());
SkASSERT(winding);
@@ -3426,8 +3429,10 @@
*oppMaxWinding = *sumSuWinding;
*oppSumWinding = *sumSuWinding -= oppDeltaSum;
}
- SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
- SkASSERT(abs(*oppSumWinding) <= SkPathOpsDebug::gMaxWindSum);
+#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,
@@ -3435,7 +3440,9 @@
int deltaSum = spanSign(index, endIndex);
*maxWinding = *sumMiWinding;
*sumWinding = *sumMiWinding -= deltaSum;
- SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
+#if DEBUG_LIMIT_WIND_SUM
+ SkASSERT(abs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
+#endif
}
void SkOpSegment::sortAngles() {
@@ -3494,7 +3501,10 @@
wroteAfterHeader = true;
}
#endif
- baseAngle->insert(&other->angle(otherAngleIndex));
+ SkOpAngle* oAngle = &other->angle(otherAngleIndex);
+ if (!oAngle->loopContains(*baseAngle)) {
+ baseAngle->insert(oAngle);
+ }
}
otherAngleIndex = oSpan.fToAngleIndex;
if (otherAngleIndex >= 0) {
@@ -3505,7 +3515,10 @@
wroteAfterHeader = true;
}
#endif
- baseAngle->insert(&other->angle(otherAngleIndex));
+ SkOpAngle* oAngle = &other->angle(otherAngleIndex);
+ if (!oAngle->loopContains(*baseAngle)) {
+ baseAngle->insert(oAngle);
+ }
}
if (++index == spanCount) {
break;
@@ -3673,6 +3686,9 @@
int SkOpSegment::updateWinding(int index, int endIndex) const {
int lesser = SkMin32(index, endIndex);
int winding = windSum(lesser);
+ if (winding == SK_MinS32) {
+ return winding;
+ }
int spanWinding = spanSign(index, endIndex);
if (winding && UseInnerWinding(winding - spanWinding, winding)
&& winding != SK_MaxS32) {
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 54c1892..b6eab86 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -48,8 +48,6 @@
return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
}
- void constructLine(SkPoint shortLine[2]);
-
int count() const {
return fTs.count();
}
@@ -193,11 +191,6 @@
return const_cast<SkOpAngle*>(cAngle);
}
- // OPTIMIZATION: mark as debugging only if used solely by tests
- const SkTDArray<SkOpSpan>& spans() const {
- return fTs;
- }
-
int spanSign(const SkOpAngle* angle) const {
SkASSERT(angle->segment() == this);
return spanSign(angle->start(), angle->end());
@@ -219,10 +212,6 @@
return fTs[start].fT * (1 - mid) + fTs[end].fT * mid;
}
- bool unsortable(int index) const {
- return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd;
- }
-
void updatePts(const SkPoint pts[]) {
fPts = pts;
}
@@ -267,7 +256,7 @@
const SkOpAngle* activeAngle(int index, int* start, int* end, bool* done,
bool* sortable) const;
- SkPoint activeLeftTop(bool onlySortable, int* firstT) const;
+ SkPoint activeLeftTop(int* firstT) const;
bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op);
bool activeWinding(int index, int endIndex);
void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);
@@ -297,6 +286,7 @@
bool checkSmall(int index) const;
void checkTiny();
int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType);
+ bool containsPt(const SkPoint& , int index, int endIndex) const;
int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
double mid, bool opp, bool current) const;
bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd,
@@ -307,16 +297,16 @@
bool* unsortable);
SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
int findExactT(double t, const SkOpSegment* ) const;
- int findT(double t, const SkOpSegment* ) const;
- SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable);
+ int findT(double t, const SkPoint& , const SkOpSegment* ) const;
+ SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool firstPass);
void fixOtherTIndex();
void initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType);
void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
SkScalar hitOppDx);
bool isMissing(double startT, const SkPoint& pt) const;
- bool isSmall(const SkOpAngle* angle) const;
bool isTiny(const SkOpAngle* angle) const;
- bool joinCoincidence(SkOpSegment* other, double otherT, int step, bool cancel);
+ bool joinCoincidence(SkOpSegment* other, double otherT, const SkPoint& otherPt, int step,
+ bool cancel);
SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
@@ -361,6 +351,7 @@
#if DEBUG_SHOW_WINDING
int debugShowWindingValues(int slotCount, int ofInterest) const;
#endif
+ const SkTDArray<SkOpSpan>& debugSpans() const;
void debugValidate() const;
// available to testing only
void dumpAngles() const;
@@ -439,7 +430,6 @@
SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);
void markWinding(int index, int winding);
void markWinding(int index, int winding, int oppWinding);
- void markUnsortable(int start, int end);
bool monotonicInY(int tStart, int tEnd) const;
bool multipleEnds() const {
@@ -490,6 +480,9 @@
#if DEBUG_ANGLE
void debugCheckPointsEqualish(int tStart, int tEnd) const;
#endif
+#if DEBUG_SWAP_TOP
+ int debugInflections(int index, int endIndex) const;
+#endif
#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE
void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding);
void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding);
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index 2fe0b61..1ffdc0e 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -28,8 +28,6 @@
bool fLoop; // set when a cubic loops back to this point
bool fSmall; // if set, consecutive points are almost equal
bool fTiny; // if set, consecutive points are equal but consecutive ts are not precisely equal
- bool fUnsortableStart; // set when start is part of an unsortable pair
- bool fUnsortableEnd; // set when end is part of an unsortable pair
// available to testing only
const SkOpSegment* debugToSegment(ptrdiff_t* ) const;
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index f341483..0e9e1be 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -206,7 +206,7 @@
static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourList,
int* index, int* endIndex, SkPoint* topLeft, bool* unsortable,
- bool* done, bool onlySortable) {
+ bool* done, bool firstPass) {
SkOpSegment* result;
const SkOpSegment* lastTopStart = NULL;
int lastIndex = -1, lastEndIndex = -1;
@@ -238,7 +238,7 @@
return NULL;
}
*topLeft = bestXY;
- result = topStart->findTop(index, endIndex, unsortable);
+ result = topStart->findTop(index, endIndex, unsortable, firstPass);
if (!result) {
if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) {
*done = true;
@@ -249,9 +249,11 @@
lastEndIndex = *endIndex;
}
} while (!result);
+#if 0
if (result) {
*unsortable = false;
}
+#endif
return result;
}
@@ -283,18 +285,20 @@
if (contour->done()) {
continue;
}
- *current = contour->nonVerticalSegment(index, endIndex);
- if (*current) {
+ SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex);
+ if (nonVertical) {
+ *current = nonVertical;
return;
}
}
+ return;
}
SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
- int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done) {
+ int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) {
SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
- done, true);
+ done, firstPass);
if (!current) {
return NULL;
}
@@ -332,7 +336,7 @@
// if only remaining candidates are vertical, then they can be marked done
SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
skipVertical(contourList, ¤t, indexPtr, endIndexPtr);
-
+ SkASSERT(current); // FIXME: if null, all remaining are vertical
SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
tryAgain = false;
contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit,
@@ -348,6 +352,9 @@
} while (tryAgain);
current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding,
hitOppDx);
+ if (current->done()) {
+ return NULL;
+ }
return current;
}
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index 9a558cf..6a7bb72 100644
--- a/src/pathops/SkPathOpsCommon.h
+++ b/src/pathops/SkPathOpsCommon.h
@@ -18,7 +18,7 @@
SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex);
SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& , SkOpAngle::IncludeType ,
bool* firstContour, int* index, int* endIndex, SkPoint* topLeft,
- bool* unsortable, bool* done);
+ bool* unsortable, bool* done, bool firstPass);
SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end);
void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list,
bool evenOdd, bool oppEvenOdd);
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index fda42a3..a89604f 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -94,6 +94,11 @@
}
bool SkDCubic::serpentine() const {
+#if 0 // FIXME: enabling this fixes cubicOp114 but breaks cubicOp58d and cubicOp53d
+ double tValues[2];
+ // OPTIMIZATION : another case where caching the present of cubic inflections would be useful
+ return findInflections(tValues) > 1;
+#endif
if (!controlsContainedByEnds()) {
return false;
}
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 4e42163..3a5153a 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -10,12 +10,12 @@
#if defined SK_DEBUG || !FORCE_RELEASE
-int SkPathOpsDebug::gMaxWindSum = SK_MaxS32;
-int SkPathOpsDebug::gMaxWindValue = SK_MaxS32;
-
const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"};
+
+#if defined(SK_DEBUG) || !FORCE_RELEASE
int SkPathOpsDebug::gContourID;
int SkPathOpsDebug::gSegmentID;
+#endif
#if DEBUG_SORT || DEBUG_SWAP_TOP
int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
@@ -393,6 +393,17 @@
}
#endif
+#if DEBUG_SWAP_TOP
+int SkOpSegment::debugInflections(int tStart, int tEnd) const {
+ if (fVerb != SkPath::kCubic_Verb) {
+ return false;
+ }
+ SkDCubic dst = SkDCubic::SubDivide(fPts, fTs[tStart].fT, fTs[tEnd].fT);
+ double inflections[2];
+ return dst.findInflections(inflections);
+}
+#endif
+
void SkOpSegment::debugReset() {
fTs.reset();
fAngles.reset();
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index 5cacee5..39d5a6d 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -52,6 +52,7 @@
#define DEBUG_CROSS 0
#define DEBUG_FLAT_QUADS 0
#define DEBUG_FLOW 0
+#define DEBUG_LIMIT_WIND_SUM 0
#define DEBUG_MARK_DONE 0
#define DEBUG_PATH_CONSTRUCTION 0
#define DEBUG_SHOW_TEST_NAME 0
@@ -85,6 +86,7 @@
#define DEBUG_CROSS 01
#define DEBUG_FLAT_QUADS 0
#define DEBUG_FLOW 1
+#define DEBUG_LIMIT_WIND_SUM 4
#define DEBUG_MARK_DONE 1
#define DEBUG_PATH_CONSTRUCTION 1
#define DEBUG_SHOW_TEST_NAME 1
@@ -96,7 +98,7 @@
#define DEBUG_SORT_SINGLE 0
#define DEBUG_SWAP_TOP 1
#define DEBUG_UNSORTABLE 1
-#define DEBUG_VALIDATE 1
+#define DEBUG_VALIDATE 0
#define DEBUG_WIND_BUMP 0
#define DEBUG_WINDING 1
#define DEBUG_WINDING_AT_T 1
@@ -134,12 +136,12 @@
class SkPathOpsDebug {
public:
- static int gMaxWindSum;
- static int gMaxWindValue;
-
static const char* kLVerbStr[];
+
+#if defined(SK_DEBUG) || !FORCE_RELEASE
static int gContourID;
static int gSegmentID;
+#endif
#if DEBUG_SORT || DEBUG_SWAP_TOP
static int gSortCountDefault;
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 130d498..5af4753 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -21,6 +21,9 @@
*endIndex = -1;
if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
&sortable)) {
+ if (last->unorderable()) {
+ continue;
+ }
*tIndex = last->start();
*endIndex = last->end();
#if TRY_ROTATE
@@ -116,21 +119,31 @@
bool firstContour = true;
bool unsortable = false;
bool topUnsortable = false;
+ bool firstPass = true;
+ SkPoint lastTopLeft;
SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
do {
int index, endIndex;
- bool done;
+ bool topDone;
+ lastTopLeft = topLeft;
SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
- &index, &endIndex, &topLeft, &topUnsortable, &done);
+ &index, &endIndex, &topLeft, &topUnsortable, &topDone, firstPass);
if (!current) {
- if (topUnsortable || !done) {
- topUnsortable = false;
+ if ((!topUnsortable || firstPass) && !topDone) {
SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
+ if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) {
+ if (firstPass) {
+ firstPass = false;
+ } else {
+ break;
+ }
+ }
topLeft.fX = topLeft.fY = SK_ScalarMin;
continue;
}
break;
}
+ firstPass = !topUnsortable || lastTopLeft != topLeft;
SkTDArray<SkOpSpan*> chaseArray;
do {
if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 66a6c40..0917b69 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -13,21 +13,24 @@
bool firstContour = true;
bool unsortable = false;
bool topUnsortable = false;
+ bool firstPass = true;
+ SkPoint lastTopLeft;
SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
do {
int index, endIndex;
bool topDone;
+ lastTopLeft = topLeft;
SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
- &index, &endIndex, &topLeft, &topUnsortable, &topDone);
+ &index, &endIndex, &topLeft, &topUnsortable, &topDone, firstPass);
if (!current) {
- if (topUnsortable || !topDone) {
- topUnsortable = false;
+ if ((!topUnsortable || firstPass) && !topDone) {
SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
topLeft.fX = topLeft.fY = SK_ScalarMin;
continue;
}
break;
}
+ firstPass = !topUnsortable || lastTopLeft != topLeft;
SkTDArray<SkOpSpan*> chaseArray;
do {
if (current->activeWinding(index, endIndex)) {
diff --git a/src/pathops/SkReduceOrder.cpp b/src/pathops/SkReduceOrder.cpp
index ada5276..bb2038b 100644
--- a/src/pathops/SkReduceOrder.cpp
+++ b/src/pathops/SkReduceOrder.cpp
@@ -161,8 +161,8 @@
while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) {
--endIndex;
if (endIndex == 0) {
- SkDebugf("%s shouldn't get here if all four points are about equal\n", __FUNCTION__);
- SkASSERT(0);
+ endIndex = 3;
+ break;
}
}
if (!cubic.isLinear(startIndex, endIndex)) {