Enabling the canvas bit to turn the clip stack into a flat replace exposed around 100 failures when testing the 800K skp set generated from the top 1M web sites.
This fixes all but one of those failures.
Major changes include:
- Replace angle indices with angle pointers. This was motivated by the need to add angles later but not renumber existing angles.
- Aggressive segment chase. When the winding is known on a segment, more aggressively passing that winding to adjacent segments allows fragmented data sets to succeed.
- Line segments with ends nearly the same are treated as coincident first.
- Transfer partial coincidence by observing that if segment A is partially coincident to B and C then B and C may be partially coincident.
TBR=reed
Author: caryclark@google.com
Review URL: https://codereview.chromium.org/272153002
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp
index 620842b..52e751b 100644
--- a/src/pathops/SkAddIntersections.cpp
+++ b/src/pathops/SkAddIntersections.cpp
@@ -397,6 +397,7 @@
SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
SkPoint point = ts.pt(pt).asSkPoint();
+ wt.alignTPt(wn, swap, pt, &ts, &point);
int testTAt = wt.addT(wn, point, ts[swap][pt]);
int nextTAt = wn.addT(wt, point, ts[!swap][pt]);
wt.addOtherT(testTAt, ts[!swap][pt], nextTAt);
@@ -437,6 +438,10 @@
int contourCount = (*contourList).count();
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
SkOpContour* contour = (*contourList)[cIndex];
+ contour->resolveNearCoincidence();
+ }
+ for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
+ SkOpContour* contour = (*contourList)[cIndex];
contour->addCoincidentPoints();
}
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index dd51195..1c237d9 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -303,15 +303,39 @@
continue;
}
if (swap) {
- insert(testT, impTs[0][index], tmpLine[0]);
+ cubicInsert(testT, impTs[0][index], tmpLine[0], cubic2, cubic1);
} else {
- insert(impTs[0][index], testT, tmpLine[0]);
+ cubicInsert(impTs[0][index], testT, tmpLine[0], cubic1, cubic2);
}
return true;
}
return false;
}
+
+void SkIntersections::cubicInsert(double one, double two, const SkDPoint& pt,
+ const SkDCubic& cubic1, const SkDCubic& cubic2) {
+ for (int index = 0; index < fUsed; ++index) {
+ if (fT[0][index] == one) {
+ double oldTwo = fT[1][index];
+ if (oldTwo == two) {
+ return;
+ }
+ SkDPoint mid = cubic2.ptAtT((oldTwo + two) / 2);
+ if (mid.approximatelyEqual(fPt[index])) {
+ return;
+ }
+ }
+ if (fT[1][index] == two) {
+ SkDPoint mid = cubic1.ptAtT((fT[0][index] + two) / 2);
+ if (mid.approximatelyEqual(fPt[index])) {
+ return;
+ }
+ }
+ }
+ insert(one, two, pt);
+}
+
void SkIntersections::cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2,
const SkDRect& bounds2) {
SkDLine line;
@@ -371,11 +395,15 @@
double tMin2 = SkTMax(tVals[tIdx] - LINE_FRACTION, 0.0);
double tMax2 = SkTMin(tVals[tLast] + LINE_FRACTION, 1.0);
int lastUsed = used();
- ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this);
+ if (start ? tMax1 < tMin2 : tMax2 < tMin1) {
+ ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this);
+ }
if (lastUsed == used()) {
tMin2 = SkTMax(tVals[tIdx] - (1.0 / SkDCubic::gPrecisionUnit), 0.0);
tMax2 = SkTMin(tVals[tLast] + (1.0 / SkDCubic::gPrecisionUnit), 1.0);
- ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this);
+ if (start ? tMax1 < tMin2 : tMax2 < tMin1) {
+ ::intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, *this);
+ }
}
tIdx = tLast + 1;
} while (tIdx < tVals.count());
@@ -421,6 +449,9 @@
}
double adj = endPt[oppTest]->fX - origX;
double opp = endPt[oppTest]->fY - origY;
+ if (adj == 0 && opp == 0) { // if the other point equals the test point, ignore it
+ continue;
+ }
double sign = (c1[oddMan].fY - origY) * adj - (c1[oddMan].fX - origX) * opp;
if (approximately_zero(sign)) {
goto tryNextHalfPlane;
@@ -531,7 +562,7 @@
if (compCount) {
int exactCount = used();
if (exactCount == 0) {
- set(i);
+ *this = i;
} else {
// at least one is exact or near, and at least one was computed. Eliminate duplicates
for (int exIdx = 0; exIdx < exactCount; ++exIdx) {
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index 41828bb..696c42e 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -261,7 +261,7 @@
if (fIntersections->hasT(cubicT)) {
continue;
}
- double lineT = fLine.nearPoint(fCubic[cIndex]);
+ double lineT = fLine.nearPoint(fCubic[cIndex], NULL);
if (lineT < 0) {
continue;
}
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index 8969539..9ae0107 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -154,15 +154,52 @@
computePoints(a, 1);
}
}
+/* Allow tracking that both sets of end points are near each other -- the lines are entirely
+ coincident -- even when the end points are not exactly the same.
+ Mark this as a 'wild card' for the end points, so that either point is considered totally
+ coincident. Then, avoid folding the lines over each other, but allow either end to mate
+ to the next set of lines.
+ */
if (fAllowNear || !unparallel) {
- for (int iA = 0; iA < 2; ++iA) {
- if ((t = b.nearPoint(a[iA])) >= 0) {
- insert(iA, t, a[iA]);
- }
+ double aNearB[2];
+ double bNearA[2];
+ bool aNotB[2] = {false, false};
+ bool bNotA[2] = {false, false};
+ int nearCount = 0;
+ for (int index = 0; index < 2; ++index) {
+ aNearB[index] = t = b.nearPoint(a[index], &aNotB[index]);
+ nearCount += t >= 0;
+ bNearA[index] = t = a.nearPoint(b[index], &bNotA[index]);
+ nearCount += t >= 0;
}
- for (int iB = 0; iB < 2; ++iB) {
- if ((t = a.nearPoint(b[iB])) >= 0) {
- insert(t, iB, b[iB]);
+ if (nearCount > 0) {
+ for (int iA = 0; iA < 2; ++iA) {
+ if (!aNotB[iA]) {
+ continue;
+ }
+ int nearer = aNearB[iA] > 0.5;
+ if (!bNotA[nearer]) {
+ continue;
+ }
+ SkASSERT(a[iA] != b[nearer]);
+ SkASSERT(iA == (bNearA[nearer] > 0.5));
+ fNearlySame[iA] = true;
+ insertNear(iA, nearer, a[iA], b[nearer]);
+ aNearB[iA] = -1;
+ bNearA[nearer] = -1;
+ nearCount -= 2;
+ }
+ if (nearCount > 0) {
+ for (int iA = 0; iA < 2; ++iA) {
+ if (aNearB[iA] >= 0) {
+ insert(iA, aNearB[iA], a[iA]);
+ }
+ }
+ for (int iB = 0; iB < 2; ++iB) {
+ if (bNearA[iB] >= 0) {
+ insert(bNearA[iB], iB, b[iB]);
+ }
+ }
}
}
}
@@ -240,12 +277,12 @@
}
}
if (fAllowNear || result == 2) {
- if ((t = line.nearPoint(leftPt)) >= 0) {
+ if ((t = line.nearPoint(leftPt, NULL)) >= 0) {
insert(t, (double) flipped, leftPt);
}
if (left != right) {
const SkDPoint rightPt = { right, y };
- if ((t = line.nearPoint(rightPt)) >= 0) {
+ if ((t = line.nearPoint(rightPt, NULL)) >= 0) {
insert(t, (double) !flipped, rightPt);
}
for (int index = 0; index < 2; ++index) {
@@ -328,12 +365,12 @@
}
}
if (fAllowNear || result == 2) {
- if ((t = line.nearPoint(topPt)) >= 0) {
+ if ((t = line.nearPoint(topPt, NULL)) >= 0) {
insert(t, (double) flipped, topPt);
}
if (top != bottom) {
SkDPoint bottomPt = { x, bottom };
- if ((t = line.nearPoint(bottomPt)) >= 0) {
+ if ((t = line.nearPoint(bottomPt, NULL)) >= 0) {
insert(t, (double) !flipped, bottomPt);
}
for (int index = 0; index < 2; ++index) {
diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp
index 14ccac6..5a8bafc 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -422,7 +422,7 @@
swapped.setMax(fMax);
if (is_linear(q2, q1, &swapped)) {
swapped.swapPts();
- set(swapped);
+ *this = swapped;
return fUsed;
}
SkIntersections copyI(*this);
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index 1b9d8cc..ef8edb0 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -238,7 +238,7 @@
if (fIntersections->hasT(quadT)) {
continue;
}
- double lineT = fLine.nearPoint(fQuad[qIndex]);
+ double lineT = fLine.nearPoint(fQuad[qIndex], NULL);
if (lineT < 0) {
continue;
}
@@ -324,10 +324,10 @@
*pt = fQuad.ptAtT(qT);
}
SkPoint gridPt = pt->asSkPoint();
- if (gridPt == fLine[0].asSkPoint()) {
+ if (SkDPoint::ApproximatelyEqual(gridPt, fLine[0].asSkPoint())) {
*pt = fLine[0];
*lineT = 0;
- } else if (gridPt == fLine[1].asSkPoint()) {
+ } else if (SkDPoint::ApproximatelyEqual(gridPt, fLine[1].asSkPoint())) {
*pt = fLine[1];
*lineT = 1;
}
diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h
index 4e8c658..3569c93 100644
--- a/src/pathops/SkIntersectionHelper.h
+++ b/src/pathops/SkIntersectionHelper.h
@@ -54,6 +54,11 @@
return ++fIndex < fLast;
}
+ void alignTPt(SkIntersectionHelper& other, bool swap, int index,
+ SkIntersections* ts, SkPoint* point) {
+ fContour->alignTPt(fIndex, other.fContour, other.fIndex, swap, index, ts, point);
+ }
+
SkScalar bottom() const {
return bounds().fBottom;
}
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index c8b4b83..56eba27 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -103,6 +103,7 @@
int remaining = fUsed - index;
if (remaining > 0) {
memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[0]) * remaining);
+ memmove(&fPt2[index + 1], &fPt2[index], sizeof(fPt2[0]) * remaining);
memmove(&fT[0][index + 1], &fT[0][index], sizeof(fT[0][0]) * remaining);
memmove(&fT[1][index + 1], &fT[1][index], sizeof(fT[1][0]) * remaining);
int clearMask = ~((1 << index) - 1);
@@ -116,6 +117,15 @@
return index;
}
+void SkIntersections::insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2) {
+ SkASSERT(one == 0 || one == 1);
+ SkASSERT(two == 0 || two == 1);
+ SkASSERT(pt1 != pt2);
+ SkASSERT(fNearlySame[(int) one]);
+ (void) insert(one, two, pt1);
+ fPt2[one ? fUsed - 1 : 0] = pt2;
+}
+
void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
int index = insertSwap(one, two, pt);
int bit = 1 << index;
@@ -158,6 +168,7 @@
return;
}
memmove(&fPt[index], &fPt[index + 1], sizeof(fPt[0]) * remaining);
+ memmove(&fPt2[index], &fPt2[index + 1], sizeof(fPt2[0]) * remaining);
memmove(&fT[0][index], &fT[0][index + 1], sizeof(fT[0][0]) * remaining);
memmove(&fT[1][index], &fT[1][index + 1], sizeof(fT[1][0]) * remaining);
SkASSERT(fIsCoincident[0] == 0);
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index eced4dd..0186b37 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -21,8 +21,10 @@
#endif
{
sk_bzero(fPt, sizeof(fPt));
+ sk_bzero(fPt2, sizeof(fPt2));
sk_bzero(fT, sizeof(fT));
sk_bzero(fIsCoincident, sizeof(fIsCoincident));
+ sk_bzero(fNearlySame, sizeof(fNearlySame));
reset();
fMax = 0; // require that the caller set the max
}
@@ -37,16 +39,6 @@
};
TArray operator[](int n) const { return TArray(fT[n]); }
- void set(const SkIntersections& i) {
- memcpy(fPt, i.fPt, sizeof(fPt));
- memcpy(fT, i.fT, sizeof(fT));
- memcpy(fIsCoincident, i.fIsCoincident, sizeof(fIsCoincident));
- fUsed = i.fUsed;
- fMax = i.fMax;
- fSwap = i.fSwap;
- SkDEBUGCODE(fDepth = i.fDepth);
- }
-
void allowNear(bool nearAllowed) {
fAllowNear = nearAllowed;
}
@@ -140,10 +132,19 @@
return intersect(aLine, bLine);
}
+ bool nearlySame(int index) const {
+ SkASSERT(index == 0 || index == 1);
+ return fNearlySame[index];
+ }
+
const SkDPoint& pt(int index) const {
return fPt[index];
}
+ const SkDPoint& pt2(int index) const {
+ return fPt2[index];
+ }
+
int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y,
bool flipped) {
SkDQuad quad;
@@ -177,12 +178,16 @@
return intersect(aQuad, bQuad);
}
- // leaves flip, swap, max alone
+ // leaves swap, max alone
void reset() {
fAllowNear = true;
fUsed = 0;
}
+ void set(bool swap, int tIndex, double t) {
+ fT[(int) swap][tIndex] = t;
+ }
+
void setMax(int max) {
fMax = max;
}
@@ -212,6 +217,8 @@
void append(const SkIntersections& );
void cleanUpCoincidence();
int coincidentUsed() const;
+ void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1,
+ const SkDCubic& c2);
int cubicRay(const SkPoint pts[4], const SkDLine& line);
void flip();
int horizontal(const SkDLine&, double y);
@@ -223,7 +230,7 @@
int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
// FIXME : does not respect swap
int insert(double one, double two, const SkDPoint& pt);
- void insertNear(double one, double two, const SkDPoint& pt);
+ void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2);
// start if index == 0 : end if index == 1
void insertCoincident(double one, double two, const SkDPoint& pt);
int intersect(const SkDLine&, const SkDLine&);
@@ -267,8 +274,10 @@
void computePoints(const SkDLine& line, int used);
SkDPoint fPt[9]; // FIXME: since scans store points as SkPoint, this should also
+ SkDPoint fPt2[9]; // used by nearly same to store alternate intersection point
double fT[2][9];
uint16_t fIsCoincident[2]; // bit set for each curve's coincident T
+ bool fNearlySame[2]; // true if end points nearly match
unsigned char fUsed;
unsigned char fMax;
bool fAllowNear;
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index 094b22c..894758c 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -289,7 +289,7 @@
// FIXME: logically, this should return !fUnorderable, but doing so breaks testQuadratic51
// -- but in general, this code may not work so this may be the least of problems
// adding the bang fixes testQuads46x in release, however
- return fUnorderable;
+ return !fUnorderable;
}
SkASSERT(fSegment->verb() != SkPath::kLine_Verb && small());
fComputedSector = true;
@@ -322,7 +322,7 @@
return false;
}
int saveEnd = fEnd;
- fEnd = checkEnd - step;
+ fComputedEnd = fEnd = checkEnd - step;
setSpans();
setSector();
fEnd = saveEnd;
@@ -414,12 +414,12 @@
SkIntersections i;
(*CurveIntersectRay[index ? rPts : lPts])(segment.pts(), rays[index], &i);
// SkASSERT(i.used() >= 1);
- if (i.used() <= 1) {
- continue;
- }
+// if (i.used() <= 1) {
+// continue;
+// }
double tStart = segment.t(index ? rh.fStart : fStart);
- double tEnd = segment.t(index ? rh.fEnd : fEnd);
- bool testAscends = index ? rh.fStart < rh.fEnd : fStart < fEnd;
+ double tEnd = segment.t(index ? rh.fComputedEnd : fComputedEnd);
+ bool testAscends = index ? rh.fStart < rh.fComputedEnd : fStart < fComputedEnd;
double t = testAscends ? 0 : 1;
for (int idx2 = 0; idx2 < i.used(); ++idx2) {
double testT = i[0][idx2];
@@ -879,12 +879,9 @@
}
void SkOpAngle::set(const SkOpSegment* segment, int start, int end) {
-#if DEBUG_ANGLE
- fID = 0;
-#endif
fSegment = segment;
fStart = start;
- fEnd = end;
+ fComputedEnd = fEnd = end;
fNext = NULL;
fComputeSector = fComputedSector = false;
fStop = false;
@@ -1097,3 +1094,33 @@
double mFactor = fabs(useS ? distEndRatio(sDist) : rh.distEndRatio(tDist));
return mFactor < 5000; // empirically found limit
}
+
+SkOpAngleSet::SkOpAngleSet()
+ : fAngles(NULL)
+#if DEBUG_ANGLE
+ , fCount(0)
+#endif
+{
+}
+
+SkOpAngleSet::~SkOpAngleSet() {
+ SkDELETE(fAngles);
+}
+
+SkOpAngle& SkOpAngleSet::push_back() {
+ if (!fAngles) {
+ fAngles = SkNEW_ARGS(SkChunkAlloc, (2));
+ }
+ void* ptr = fAngles->allocThrow(sizeof(SkOpAngle));
+ SkOpAngle* angle = (SkOpAngle*) ptr;
+#if DEBUG_ANGLE
+ angle->setID(++fCount);
+#endif
+ return *angle;
+}
+
+void SkOpAngleSet::reset() {
+ if (fAngles) {
+ fAngles->reset();
+ }
+}
diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h
index e566913..63d378d 100644
--- a/src/pathops/SkOpAngle.h
+++ b/src/pathops/SkOpAngle.h
@@ -7,6 +7,7 @@
#ifndef SkOpAngle_DEFINED
#define SkOpAngle_DEFINED
+#include "SkChunkAlloc.h"
#include "SkLineParameters.h"
class SkOpSegment;
@@ -81,13 +82,19 @@
void debugSameAs(const SkOpAngle* compare) const;
#endif
void dump() const;
- void dumpFromTo(const SkOpSegment* fromSeg, int from, int to) const;
+ void dumpLoop() const;
+ void dumpTo(const SkOpSegment* fromSeg, const SkOpAngle* ) const;
#if DEBUG_ANGLE
+ int debugID() const { return fID; }
+
void setID(int id) {
fID = id;
}
+#else
+ int debugID() const { return 0; }
#endif
+
#if DEBUG_VALIDATE
void debugValidateLoop() const;
#endif
@@ -121,6 +128,7 @@
SkDVector fSweep[2];
int fStart;
int fEnd;
+ int fComputedEnd;
int fSectorMask;
int8_t fSectorStart; // in 32nds of a circle
int8_t fSectorEnd;
@@ -131,11 +139,7 @@
bool fComputeSector;
bool fComputedSector;
-#if DEBUG_SORT
- void debugOne(bool showFunc) const; // available to testing only
-#endif
#if DEBUG_ANGLE
- int debugID() const { return fID; }
int fID;
#endif
#if DEBUG_VALIDATE
@@ -143,9 +147,23 @@
#else
void debugValidateNext() const {}
#endif
- void dumpLoop() const; // utility to be called by user from debugger
+ void dumpOne(bool showFunc) const; // available to testing only
void dumpPartials() const; // utility to be called by user from debugger
friend class PathOpsAngleTester;
};
+class SkOpAngleSet {
+public:
+ SkOpAngleSet();
+ ~SkOpAngleSet();
+ SkOpAngle& push_back();
+ void reset();
+private:
+ void dump() const; // utility to be called by user from debugger
+#if DEBUG_ANGLE
+ int fCount;
+#endif
+ SkChunkAlloc* fAngles;
+};
+
#endif
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index e3137b7..5ef702d 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -28,8 +28,14 @@
coincidence.fTs[swap][1] = ts[0][1];
coincidence.fTs[!swap][0] = ts[1][0];
coincidence.fTs[!swap][1] = ts[1][1];
- coincidence.fPts[0] = pt0;
- coincidence.fPts[1] = pt1;
+ coincidence.fPts[swap][0] = pt0;
+ coincidence.fPts[swap][1] = pt1;
+ bool nearStart = ts.nearlySame(0);
+ bool nearEnd = ts.nearlySame(1);
+ coincidence.fPts[!swap][0] = nearStart ? ts.pt2(0).asSkPoint() : pt0;
+ coincidence.fPts[!swap][1] = nearEnd ? ts.pt2(1).asSkPoint() : pt1;
+ coincidence.fNearly[0] = nearStart;
+ coincidence.fNearly[1] = nearEnd;
return true;
}
@@ -93,28 +99,31 @@
cancelers ^= true;
}
SkASSERT(!approximately_negative(oEndT - oStartT));
+ const SkPoint& startPt = coincidence.fPts[0][startSwapped];
if (cancelers) {
// make sure startT and endT have t entries
- const SkPoint& startPt = coincidence.fPts[startSwapped];
if (startT > 0 || oEndT < 1
|| thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
- thisOne.addTPair(startT, &other, oEndT, true, startPt);
+ thisOne.addTPair(startT, &other, oEndT, true, startPt,
+ coincidence.fPts[1][startSwapped]);
}
- const SkPoint& oStartPt = coincidence.fPts[oStartSwapped];
+ const SkPoint& oStartPt = coincidence.fPts[1][oStartSwapped];
if (oStartT > 0 || endT < 1
|| thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
- other.addTPair(oStartT, &thisOne, endT, true, oStartPt);
+ other.addTPair(oStartT, &thisOne, endT, true, oStartPt,
+ coincidence.fPts[0][oStartSwapped]);
}
} else {
- const SkPoint& startPt = coincidence.fPts[startSwapped];
if (startT > 0 || oStartT > 0
|| thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
- thisOne.addTPair(startT, &other, oStartT, true, startPt);
+ thisOne.addTPair(startT, &other, oStartT, true, startPt,
+ coincidence.fPts[1][startSwapped]);
}
- const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped];
+ const SkPoint& oEndPt = coincidence.fPts[1][!oStartSwapped];
if (endT < 1 || oEndT < 1
|| thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
- other.addTPair(oEndT, &thisOne, endT, true, oEndPt);
+ other.addTPair(oEndT, &thisOne, endT, true, oEndPt,
+ coincidence.fPts[0][!oStartSwapped]);
}
}
#if DEBUG_CONCIDENT
@@ -122,6 +131,32 @@
other.debugShowTs("o");
#endif
}
+ // if there are multiple pairs of coincidence that share an edge, see if the opposite
+ // are also coincident
+ for (int index = 0; index < count - 1; ++index) {
+ const SkCoincidence& coincidence = fCoincidences[index];
+ int thisIndex = coincidence.fSegments[0];
+ SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ for (int idx2 = 1; idx2 < count; ++idx2) {
+ const SkCoincidence& innerCoin = fCoincidences[idx2];
+ int innerThisIndex = innerCoin.fSegments[0];
+ if (thisIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 1, innerCoin, 1, false);
+ }
+ if (this == otherContour && otherIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 0, innerCoin, 1, false);
+ }
+ SkOpContour* innerOtherContour = innerCoin.fOther;
+ innerThisIndex = innerCoin.fSegments[1];
+ if (this == innerOtherContour && thisIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 1, innerCoin, 0, false);
+ }
+ if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 0, innerCoin, 0, false);
+ }
+ }
+ }
}
bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
@@ -143,11 +178,77 @@
coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
coincidence.fTs[!swap][0] = ts[1][ptIndex];
coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
- coincidence.fPts[0] = pt0;
- coincidence.fPts[1] = pt1;
+ coincidence.fPts[0][0] = coincidence.fPts[1][0] = pt0;
+ coincidence.fPts[0][1] = coincidence.fPts[1][1] = pt1;
+ coincidence.fNearly[0] = 0;
+ coincidence.fNearly[1] = 0;
return true;
}
+void SkOpContour::align(const SkOpSegment::AlignedSpan& aligned, bool swap,
+ SkCoincidence* coincidence) {
+ for (int idx2 = 0; idx2 < 2; ++idx2) {
+ if (coincidence->fPts[0][idx2] == aligned.fOldPt
+ && coincidence->fTs[swap][idx2] == aligned.fOldT) {
+ SkASSERT(SkDPoint::RoughlyEqual(coincidence->fPts[0][idx2], aligned.fPt));
+ coincidence->fPts[0][idx2] = aligned.fPt;
+ SkASSERT(way_roughly_equal(coincidence->fTs[swap][idx2], aligned.fT));
+ coincidence->fTs[swap][idx2] = aligned.fT;
+ }
+ }
+}
+
+void SkOpContour::alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
+ SkTArray<SkCoincidence, true>* coincidences) {
+ int count = coincidences->count();
+ for (int index = 0; index < count; ++index) {
+ SkCoincidence& coincidence = (*coincidences)[index];
+ int thisIndex = coincidence.fSegments[0];
+ const SkOpSegment* thisOne = &fSegments[thisIndex];
+ const SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ const SkOpSegment* other = &otherContour->fSegments[otherIndex];
+ if (thisOne == aligned.fOther1 && other == aligned.fOther2) {
+ align(aligned, false, &coincidence);
+ } else if (thisOne == aligned.fOther2 && other == aligned.fOther1) {
+ align(aligned, true, &coincidence);
+ }
+ }
+}
+
+void SkOpContour::alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex,
+ bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const {
+ int zeroPt;
+ if ((zeroPt = alignT(swap, tIndex, ts)) >= 0) {
+ alignPt(segmentIndex, point, zeroPt);
+ }
+ if ((zeroPt = other->alignT(!swap, tIndex, ts)) >= 0) {
+ other->alignPt(otherIndex, point, zeroPt);
+ }
+}
+
+void SkOpContour::alignPt(int index, SkPoint* point, int zeroPt) const {
+ const SkOpSegment& segment = fSegments[index];
+ if (0 == zeroPt) {
+ *point = segment.pts()[0];
+ } else {
+ *point = segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
+ }
+}
+
+int SkOpContour::alignT(bool swap, int tIndex, SkIntersections* ts) const {
+ double tVal = (*ts)[swap][tIndex];
+ if (tVal != 0 && precisely_zero(tVal)) {
+ ts->set(swap, tIndex, 0);
+ return 0;
+ }
+ if (tVal != 1 && precisely_equal(tVal, 1)) {
+ ts->set(swap, tIndex, 1);
+ return 1;
+ }
+ return -1;
+}
+
bool SkOpContour::calcAngles() {
int segmentCount = fSegments.count();
for (int test = 0; test < segmentCount; ++test) {
@@ -180,7 +281,187 @@
#endif
for (int index = 0; index < count; ++index) {
SkCoincidence& coincidence = fPartialCoincidences[index];
- calcCommonCoincidentWinding(coincidence);
+ calcCommonCoincidentWinding(coincidence);
+ }
+ // if there are multiple pairs of partial coincidence that share an edge, see if the opposite
+ // are also coincident
+ for (int index = 0; index < count - 1; ++index) {
+ const SkCoincidence& coincidence = fPartialCoincidences[index];
+ int thisIndex = coincidence.fSegments[0];
+ SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ for (int idx2 = 1; idx2 < count; ++idx2) {
+ const SkCoincidence& innerCoin = fPartialCoincidences[idx2];
+ int innerThisIndex = innerCoin.fSegments[0];
+ if (thisIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 1, innerCoin, 1, true);
+ }
+ if (this == otherContour && otherIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 0, innerCoin, 1, true);
+ }
+ SkOpContour* innerOtherContour = innerCoin.fOther;
+ innerThisIndex = innerCoin.fSegments[1];
+ if (this == innerOtherContour && thisIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 1, innerCoin, 0, true);
+ }
+ if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
+ checkCoincidentPair(coincidence, 0, innerCoin, 0, true);
+ }
+ }
+ }
+}
+
+void SkOpContour::checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
+ const SkCoincidence& twoCoin, int twoIdx, bool partial) {
+ SkASSERT((oneIdx ? this : oneCoin.fOther) == (twoIdx ? this : twoCoin.fOther));
+ SkASSERT(oneCoin.fSegments[!oneIdx] == twoCoin.fSegments[!twoIdx]);
+ // look for common overlap
+ double min = SK_ScalarMax;
+ double max = SK_ScalarMin;
+ double min1 = oneCoin.fTs[!oneIdx][0];
+ double max1 = oneCoin.fTs[!oneIdx][1];
+ double min2 = twoCoin.fTs[!twoIdx][0];
+ double max2 = twoCoin.fTs[!twoIdx][1];
+ bool cancelers = (min1 < max1) != (min2 < max2);
+ if (min1 > max1) {
+ SkTSwap(min1, max1);
+ }
+ if (min2 > max2) {
+ SkTSwap(min2, max2);
+ }
+ if (between(min1, min2, max1)) {
+ min = min2;
+ }
+ if (between(min1, max2, max1)) {
+ max = max2;
+ }
+ if (between(min2, min1, max2)) {
+ min = SkTMin(min, min1);
+ }
+ if (between(min2, max1, max2)) {
+ max = SkTMax(max, max1);
+ }
+ if (min >= max) {
+ return; // no overlap
+ }
+ // look to see if opposite are different segments
+ int seg1Index = oneCoin.fSegments[oneIdx];
+ int seg2Index = twoCoin.fSegments[twoIdx];
+ if (seg1Index == seg2Index) {
+ return;
+ }
+ SkOpContour* contour1 = oneIdx ? oneCoin.fOther : this;
+ SkOpContour* contour2 = twoIdx ? twoCoin.fOther : this;
+ SkOpSegment* segment1 = &contour1->fSegments[seg1Index];
+ SkOpSegment* segment2 = &contour2->fSegments[seg2Index];
+ // find opposite t value ranges corresponding to reference min/max range
+ const SkOpContour* refContour = oneIdx ? this : oneCoin.fOther;
+ const int refSegIndex = oneCoin.fSegments[!oneIdx];
+ const SkOpSegment* refSegment = &refContour->fSegments[refSegIndex];
+ int seg1Start = segment1->findOtherT(min, refSegment);
+ int seg1End = segment1->findOtherT(max, refSegment);
+ int seg2Start = segment2->findOtherT(min, refSegment);
+ int seg2End = segment2->findOtherT(max, refSegment);
+ // if the opposite pairs already contain min/max, we're done
+ if (seg1Start >= 0 && seg1End >= 0 && seg2Start >= 0 && seg2End >= 0) {
+ return;
+ }
+ double loEnd = SkTMin(min1, min2);
+ double hiEnd = SkTMax(max1, max2);
+ // insert the missing coincident point(s)
+ double missingT1 = -1;
+ double otherT1 = -1;
+ if (seg1Start < 0) {
+ if (seg2Start < 0) {
+ return;
+ }
+ missingT1 = segment1->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
+ segment2, seg1End);
+ if (missingT1 < 0) {
+ return;
+ }
+ const SkOpSpan* missingSpan = &segment2->span(seg2Start);
+ otherT1 = missingSpan->fT;
+ } else if (seg2Start < 0) {
+ SkASSERT(seg1Start >= 0);
+ missingT1 = segment2->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
+ segment1, seg2End);
+ if (missingT1 < 0) {
+ return;
+ }
+ const SkOpSpan* missingSpan = &segment1->span(seg1Start);
+ otherT1 = missingSpan->fT;
+ }
+ SkPoint missingPt1;
+ SkOpSegment* addTo1 = NULL;
+ SkOpSegment* addOther1 = seg1Start < 0 ? segment2 : segment1;
+ int minTIndex = refSegment->findExactT(min, addOther1);
+ SkASSERT(minTIndex >= 0);
+ if (missingT1 >= 0) {
+ missingPt1 = refSegment->span(minTIndex).fPt;
+ addTo1 = seg1Start < 0 ? segment1 : segment2;
+ }
+ double missingT2 = -1;
+ double otherT2 = -1;
+ if (seg1End < 0) {
+ if (seg2End < 0) {
+ return;
+ }
+ missingT2 = segment1->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
+ segment2, seg1Start);
+ if (missingT2 < 0) {
+ return;
+ }
+ const SkOpSpan* missingSpan = &segment2->span(seg2End);
+ otherT2 = missingSpan->fT;
+ } else if (seg2End < 0) {
+ SkASSERT(seg1End >= 0);
+ missingT2 = segment2->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
+ segment1, seg2Start);
+ if (missingT2 < 0) {
+ return;
+ }
+ const SkOpSpan* missingSpan = &segment1->span(seg1End);
+ otherT2 = missingSpan->fT;
+ }
+ SkPoint missingPt2;
+ SkOpSegment* addTo2 = NULL;
+ SkOpSegment* addOther2 = seg1End < 0 ? segment2 : segment1;
+ int maxTIndex = refSegment->findExactT(max, addOther2);
+ SkASSERT(maxTIndex >= 0);
+ if (missingT2 >= 0) {
+ missingPt2 = refSegment->span(maxTIndex).fPt;
+ addTo2 = seg1End < 0 ? segment1 : segment2;
+ }
+ if (missingT1 >= 0) {
+ addTo1->pinT(missingPt1, &missingT1);
+ addTo1->addTPair(missingT1, addOther1, otherT1, false, missingPt1);
+ } else {
+ SkASSERT(minTIndex >= 0);
+ missingPt1 = refSegment->span(minTIndex).fPt;
+ }
+ if (missingT2 >= 0) {
+ addTo2->pinT(missingPt2, &missingT2);
+ addTo2->addTPair(missingT2, addOther2, otherT2, false, missingPt2);
+ } else {
+ SkASSERT(minTIndex >= 0);
+ missingPt2 = refSegment->span(maxTIndex).fPt;
+ }
+ if (!partial) {
+ return;
+ }
+ if (cancelers) {
+ if (missingT1 >= 0) {
+ addTo1->addTCancel(missingPt1, missingPt2, addOther1);
+ } else {
+ addTo2->addTCancel(missingPt1, missingPt2, addOther2);
+ }
+ } else if (missingT1 >= 0) {
+ addTo1->addTCoincident(missingPt1, missingPt2, addTo1 == addTo2 ? missingT2 : otherT2,
+ addOther1);
+ } else {
+ addTo2->addTCoincident(missingPt2, missingPt1, addTo2 == addTo1 ? missingT1 : otherT1,
+ addOther2);
}
}
@@ -196,9 +477,15 @@
const SkCoincidence& coincidence = coincidences[index];
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
+ if (thisOne.done()) {
+ continue;
+ }
SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
SkOpSegment& other = otherContour->fSegments[otherIndex];
+ if (other.done()) {
+ continue;
+ }
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
if (startT == endT) { // this can happen in very large compares
@@ -211,8 +498,8 @@
}
bool swapStart = startT > endT;
bool swapOther = oStartT > oEndT;
- const SkPoint* startPt = &coincidence.fPts[0];
- const SkPoint* endPt = &coincidence.fPts[1];
+ const SkPoint* startPt = &coincidence.fPts[0][0];
+ const SkPoint* endPt = &coincidence.fPts[0][1];
if (swapStart) {
SkTSwap(startT, endT);
SkTSwap(oStartT, oEndT);
@@ -243,6 +530,9 @@
}
void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
+ if (coincidence.fNearly[0] && coincidence.fNearly[1]) {
+ return;
+ }
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
if (thisOne.done()) {
@@ -256,8 +546,8 @@
}
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
- const SkPoint* startPt = &coincidence.fPts[0];
- const SkPoint* endPt = &coincidence.fPts[1];
+ const SkPoint* startPt = &coincidence.fPts[0][0];
+ const SkPoint* endPt = &coincidence.fPts[0][1];
bool cancelers;
if ((cancelers = startT > endT)) {
SkTSwap<double>(startT, endT);
@@ -291,6 +581,57 @@
#endif
}
+void SkOpContour::resolveNearCoincidence() {
+ int count = fCoincidences.count();
+ for (int index = 0; index < count; ++index) {
+ SkCoincidence& coincidence = fCoincidences[index];
+ if (!coincidence.fNearly[0] || !coincidence.fNearly[1]) {
+ continue;
+ }
+ int thisIndex = coincidence.fSegments[0];
+ SkOpSegment& thisOne = fSegments[thisIndex];
+ SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ SkOpSegment& other = otherContour->fSegments[otherIndex];
+ if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
+ // OPTIMIZATION: remove from coincidence array
+ continue;
+ }
+ #if DEBUG_CONCIDENT
+ thisOne.debugShowTs("-");
+ other.debugShowTs("o");
+ #endif
+ double startT = coincidence.fTs[0][0];
+ double endT = coincidence.fTs[0][1];
+ bool cancelers;
+ if ((cancelers = startT > endT)) {
+ SkTSwap<double>(startT, endT);
+ }
+ if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
+ if (endT <= 1 - FLT_EPSILON) {
+ endT += FLT_EPSILON;
+ SkASSERT(endT <= 1);
+ } else {
+ startT -= FLT_EPSILON;
+ SkASSERT(startT >= 0);
+ }
+ }
+ SkASSERT(!approximately_negative(endT - startT));
+ double oStartT = coincidence.fTs[1][0];
+ double oEndT = coincidence.fTs[1][1];
+ if (oStartT > oEndT) {
+ SkTSwap<double>(oStartT, oEndT);
+ cancelers ^= true;
+ }
+ SkASSERT(!approximately_negative(oEndT - oStartT));
+ if (cancelers) {
+ thisOne.blindCancel(coincidence, &other);
+ } else {
+ thisOne.blindCoincident(coincidence, &other);
+ }
+ }
+}
+
void SkOpContour::sortAngles() {
int segmentCount = fSegments.count();
for (int test = 0; test < segmentCount; ++test) {
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index 7fad7a4..d1b3cd0 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -22,7 +22,8 @@
SkOpContour* fOther;
int fSegments[2];
double fTs[2][2];
- SkPoint fPts[2];
+ SkPoint fPts[2][2];
+ int fNearly[2];
};
class SkOpContour {
@@ -86,6 +87,28 @@
return fSegments[segIndex].addSelfT(pt, newT);
}
+ void align(const SkOpSegment::AlignedSpan& aligned, bool swap, SkCoincidence* coincidence);
+ void alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
+ SkTArray<SkCoincidence, true>* coincidences);
+
+ void alignCoincidence(const SkOpSegment::AlignedSpan& aligned) {
+ alignCoincidence(aligned, &fCoincidences);
+ alignCoincidence(aligned, &fPartialCoincidences);
+ }
+
+ void alignMultiples(SkTDArray<SkOpSegment::AlignedSpan>* aligned) {
+ int segmentCount = fSegments.count();
+ for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
+ SkOpSegment& segment = fSegments[sIndex];
+ if (segment.hasMultiples()) {
+ segment.alignMultiples(aligned);
+ }
+ }
+ }
+
+ void alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex,
+ bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const;
+
const SkPathOpsBounds& bounds() const {
return fBounds;
}
@@ -127,6 +150,7 @@
SkOpSegment& segment = fSegments[sIndex];
if (segment.count() > 2) {
segment.checkMultiples();
+ fMultiples |= segment.hasMultiples();
}
}
}
@@ -135,6 +159,7 @@
int segmentCount = fSegments.count();
for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
SkOpSegment& segment = fSegments[sIndex];
+ // OPTIMIZATION : skip segments that are done?
if (segment.hasSmall()) {
segment.checkSmall();
}
@@ -189,6 +214,10 @@
}
}
+ bool hasMultiples() const {
+ return fMultiples;
+ }
+
void joinCoincidence() {
joinCoincidence(fCoincidences, false);
joinCoincidence(fPartialCoincidences, true);
@@ -203,9 +232,11 @@
void reset() {
fSegments.reset();
fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
- fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = false;
+ fContainsCurves = fContainsCubics = fContainsIntercepts = fDone = fMultiples = false;
}
+ void resolveNearCoincidence();
+
SkTArray<SkOpSegment>& segments() {
return fSegments;
}
@@ -284,11 +315,19 @@
// available to test routines only
void dump() const;
void dumpAngles() const;
+ void dumpCoincidence(const SkCoincidence& ) const;
+ void dumpCoincidences() const;
+ void dumpPt(int ) const;
void dumpPts() const;
+ void dumpSpan(int ) const;
void dumpSpans() const;
private:
+ void alignPt(int index, SkPoint* point, int zeroPt) const;
+ int alignT(bool swap, int tIndex, SkIntersections* ts) const;
void calcCommonCoincidentWinding(const SkCoincidence& );
+ void checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
+ const SkCoincidence& twoCoin, int twoIdx, bool partial);
void joinCoincidence(const SkTArray<SkCoincidence, true>& , bool partial);
void setBounds();
@@ -303,6 +342,7 @@
bool fContainsCubics;
bool fContainsCurves;
bool fDone;
+ bool fMultiples; // set if some segment has multiple identical intersections with other curves
bool fOperand; // true for the second argument to a binary operator
bool fXor;
bool fOppXor;
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 0e48b3f..59e6d34 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -5,6 +5,7 @@
* found in the LICENSE file.
*/
#include "SkIntersections.h"
+#include "SkOpContour.h"
#include "SkOpSegment.h"
#include "SkPathWriter.h"
#include "SkTSort.h"
@@ -187,7 +188,8 @@
}
bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
#if DEBUG_ACTIVE_OP
- SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__,
+ SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n",
+ __FUNCTION__, debugID(), span(index).fT, span(endIndex).fT,
SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
#endif
return result;
@@ -404,25 +406,24 @@
void SkOpSegment::addEndSpan(int endIndex) {
int spanCount = fTs.count();
- int angleIndex = fAngles.count();
int startIndex = endIndex - 1;
while (fTs[startIndex].fT == 1 || fTs[startIndex].fTiny) {
++startIndex;
SkASSERT(startIndex < spanCount - 1);
++endIndex;
}
- fAngles.push_back().set(this, spanCount - 1, startIndex);
+ SkOpAngle& angle = fAngles.push_back();
+ angle.set(this, spanCount - 1, startIndex);
#if DEBUG_ANGLE
- fAngles.back().setID(angleIndex);
debugCheckPointsEqualish(endIndex, spanCount);
#endif
- setFromAngleIndex(endIndex, angleIndex);
+ setFromAngle(endIndex, &angle);
}
-void SkOpSegment::setFromAngleIndex(int endIndex, int angleIndex) {
+void SkOpSegment::setFromAngle(int endIndex, SkOpAngle* angle) {
int spanCount = fTs.count();
do {
- fTs[endIndex].fFromAngleIndex = angleIndex;
+ fTs[endIndex].fFromAngle = angle;
} while (++endIndex < spanCount);
}
@@ -448,89 +449,92 @@
fBounds.setQuadBounds(pts);
}
-int SkOpSegment::addSingletonAngleDown(int endIndex, SkOpSegment** otherPtr) {
- int startIndex = findEndSpan(endIndex);
- SkASSERT(startIndex > 0);
- int spanIndex = endIndex - 1;
- fSingletonAngles.push_back().set(this, spanIndex, startIndex - 1);
- setFromAngleIndex(startIndex, fAngles.count() + fSingletonAngles.count() - 1);
+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 {
- other = fTs[spanIndex].fOther;
- if (other->fTs[0].fWindValue) {
+ const SkOpSpan& span = fTs[spanIndex];
+ SkASSERT(span.fT > 0);
+ other = span.fOther;
+ oStartIndex = span.fOtherIndex;
+ oEndIndex = other->nextExactSpan(oStartIndex, 1);
+ if (oEndIndex > 0 && other->span(oStartIndex).fWindValue) {
break;
}
+ oEndIndex = oStartIndex;
+ oStartIndex = other->nextExactSpan(oEndIndex, -1);
--spanIndex;
- SkASSERT(fTs[spanIndex].fT == 1);
- } while (true);
- int oEndIndex = other->findStartSpan(0);
- SkASSERT(oEndIndex > 0);
- int otherIndex = other->fSingletonAngles.count();
- other->fSingletonAngles.push_back().set(other, 0, oEndIndex);
- other->setToAngleIndex(oEndIndex, other->fAngles.count() + otherIndex);
+ } 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 otherIndex;
+ return &oAngle;
}
-int SkOpSegment::addSingletonAngleUp(int start, SkOpSegment** otherPtr) {
- int endIndex = findStartSpan(start);
+SkOpAngle* SkOpSegment::addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** anglePtr) {
+ int endIndex = nextExactSpan(0, 1);
SkASSERT(endIndex > 0);
- int thisIndex = fSingletonAngles.count();
- fSingletonAngles.push_back().set(this, start, endIndex);
- setToAngleIndex(endIndex, fAngles.count() + thisIndex);
- int spanIndex = start;
+ SkOpAngle& angle = fAngles.push_back();
+ *anglePtr = ∠
+ angle.set(this, 0, endIndex);
+ setToAngle(endIndex, &angle);
+ int spanIndex = 0;
SkOpSegment* other;
- int oCount, oStartIndex;
+ int oStartIndex, oEndIndex;
do {
- other = fTs[spanIndex].fOther;
- oCount = other->count();
- oStartIndex = other->findEndSpan(oCount);
- SkASSERT(oStartIndex > 0);
- if (other->fTs[oStartIndex - 1].fWindValue) {
+ const SkOpSpan& span = fTs[spanIndex];
+ SkASSERT(span.fT < 1);
+ other = span.fOther;
+ oEndIndex = span.fOtherIndex;
+ oStartIndex = other->nextExactSpan(oEndIndex, -1);
+ if (oStartIndex >= 0 && other->span(oStartIndex).fWindValue) {
break;
}
+ oStartIndex = oEndIndex;
+ oEndIndex = other->nextExactSpan(oStartIndex, 1);
++spanIndex;
- SkASSERT(fTs[spanIndex].fT == 0);
- } while (true);
- int otherIndex = other->fSingletonAngles.count();
- other->fSingletonAngles.push_back().set(other, oCount - 1, oStartIndex - 1);
- other->setFromAngleIndex(oStartIndex, other->fAngles.count() + otherIndex);
+ } while (oEndIndex < 0 || !other->span(oStartIndex).fWindValue);
+ SkOpAngle& oAngle = other->fAngles.push_back();
+ oAngle.set(other, oEndIndex, oStartIndex);
+ other->setFromAngle(oEndIndex, &oAngle);
*otherPtr = other;
- return otherIndex;
+ return &oAngle;
}
-SkOpAngle* SkOpSegment::addSingletonAngles(int start, int step) {
- int thisIndex = fSingletonAngles.count();
+SkOpAngle* SkOpSegment::addSingletonAngles(int step) {
SkOpSegment* other;
- int otherIndex;
+ SkOpAngle* angle, * otherAngle;
if (step > 0) {
- otherIndex = addSingletonAngleUp(start, &other);
+ otherAngle = addSingletonAngleUp(&other, &angle);
} else {
- otherIndex = addSingletonAngleDown(start + 1, &other);
+ otherAngle = addSingletonAngleDown(&other, &angle);
}
- fSingletonAngles[thisIndex].insert(&other->fSingletonAngles[otherIndex]);
-#if DEBUG_ANGLE
- fSingletonAngles[thisIndex].setID(fAngles.count() + thisIndex);
- other->fSingletonAngles[otherIndex].setID(other->fAngles.count() + otherIndex);
-#endif
- return &fSingletonAngles[thisIndex];
+ angle->insert(otherAngle);
+ return angle;
}
void SkOpSegment::addStartSpan(int endIndex) {
- int angleIndex = fAngles.count();
int index = 0;
- fAngles.push_back().set(this, index, endIndex);
+ SkOpAngle& angle = fAngles.push_back();
+ angle.set(this, index, endIndex);
#if DEBUG_ANGLE
- fAngles.back().setID(angleIndex);
debugCheckPointsEqualish(index, endIndex);
#endif
- setToAngleIndex(endIndex, angleIndex);
+ setToAngle(endIndex, &angle);
}
-void SkOpSegment::setToAngleIndex(int endIndex, int angleIndex) {
+void SkOpSegment::setToAngle(int endIndex, SkOpAngle* angle) {
int index = 0;
do {
- fTs[index].fToAngleIndex = angleIndex;
+ fTs[index].fToAngle = angle;
} while (++index < endIndex);
}
@@ -546,17 +550,14 @@
#if 0 // this needs an even rougher association to be useful
SkASSERT(SkDPoint::RoughlyEqual(ptAtT(newT), pt));
#endif
- if (precisely_zero(newT)) {
- newT = 0;
- } else if (precisely_equal(newT, 1)) {
- newT = 1;
- }
+ 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();
- const SkPoint& firstPt = fPts[0];
- const SkPoint& lastPt = fPts[SkPathOpsVerbToPoints(fVerb)];
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
@@ -588,6 +589,9 @@
span = fTs.append();
}
span->fT = newT;
+#if SK_DEBUG
+ span->fOtherT = -1;
+#endif
span->fOther = other;
span->fPt = pt;
#if 0
@@ -595,20 +599,24 @@
SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
&& approximately_equal(xyAtT(newT).fY, pt.fY));
#endif
- span->fFromAngleIndex = -1;
- span->fToAngleIndex = -1;
+ 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;
}
- span->fLoop = false;
- span->fSmall = false;
- span->fTiny = false;
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
while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) {
if (fVerb == SkPath::kCubic_Verb) {
@@ -687,6 +695,7 @@
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);
@@ -700,15 +709,19 @@
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);
- bool decrement = test->fWindValue && oTest->fWindValue;
- bool track = test->fWindValue || oTest->fWindValue;
- bool bigger = test->fWindValue >= oTest->fWindValue;
- const SkPoint& testPt = test->fPt;
+ decrement = test->fWindValue && oTest->fWindValue;
+ track = test->fWindValue || oTest->fWindValue;
+ bigger = test->fWindValue >= oTest->fWindValue;
+ testPt = &test->fPt;
double testT = test->fT;
- const SkPoint& oTestPt = oTest->fPt;
+ oTestPt = &oTest->fPt;
double oTestT = oTest->fT;
do {
if (decrement) {
@@ -718,12 +731,12 @@
decrementSpan(test);
}
} else if (track) {
- TrackOutsidePair(&outsidePts, testPt, oTestPt);
+ TrackOutsidePair(&outsidePts, *testPt, *oTestPt);
}
SkASSERT(index < fTs.count() - 1);
test = &fTs[++index];
- } while (testPt == test->fPt || precisely_equal(testT, test->fT));
- SkDEBUGCODE(int originalWindValue = oTest->fWindValue);
+ } while (*testPt == test->fPt || precisely_equal(testT, test->fT));
+ originalWindValue = oTest->fWindValue;
do {
SkASSERT(oTest->fT < 1);
SkASSERT(originalWindValue == oTest->fWindValue);
@@ -734,15 +747,48 @@
other->decrementSpan(oTest);
}
} else if (track) {
- TrackOutsidePair(&oOutsidePts, oTestPt, testPt);
+ 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;
+ }
+ }
+ 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];
- } 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
+ oFoundEnd |= endPt == oTest->fPt;
+ } while (!oFoundEnd || endPt == oTest->fPt);
+ }
+skipAdvanceOtherCancel:
int outCount = outsidePts.count();
if (!done() && outCount) {
addCancelOutsides(outsidePts[0], outsidePts[1], other);
@@ -753,6 +799,8 @@
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) {
@@ -763,48 +811,153 @@
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];
if (index == 0) {
- SkASSERT(!fTs[index].fTiny && fTs[index + 1].fT > 0);
+ do {
+ if (span->fToAngle) {
+ SkASSERT(span->fToAngle->loopCount() == 2);
+ SkASSERT(!span->fFromAngle);
+ span->fFromAngle = span->fToAngle->next();
+ return;
+ }
+ span = &fTs[++index];
+ } while (span->fT == 0);
+ SkASSERT(index == 1);
+ index = 0;
+ SkASSERT(!fTs[0].fTiny && fTs[1].fT > 0);
addStartSpan(1);
} else {
+ do {
+ if (span->fFromAngle) {
+ SkASSERT(span->fFromAngle->loopCount() == 2);
+ SkASSERT(!span->fToAngle);
+ span->fToAngle = span->fFromAngle->next();
+ return;
+ }
+ span = &fTs[--index];
+ } while (span->fT == 1);
+ SkASSERT(index == count() - 2);
+ index = count() - 1;
SkASSERT(!fTs[index - 1].fTiny && fTs[index - 1].fT < 1);
addEndSpan(index);
}
- SkOpSpan& span = fTs[index];
- SkOpSegment* other = span.fOther;
- SkOpSpan& oSpan = other->fTs[span.fOtherIndex];
+ span = &fTs[index];
+ SkOpSegment* other = span->fOther;
+ SkOpSpan& oSpan = other->fTs[span->fOtherIndex];
SkOpAngle* angle, * oAngle;
if (index == 0) {
- SkASSERT(span.fOtherIndex - 1 >= 0);
- SkASSERT(span.fOtherT == 1);
- SkDEBUGCODE(SkOpSpan& oPrior = other->fTs[span.fOtherIndex - 1]);
+ SkASSERT(span->fOtherIndex - 1 >= 0);
+ SkASSERT(span->fOtherT == 1);
+ SkDEBUGCODE(SkOpSpan& oPrior = other->fTs[span->fOtherIndex - 1]);
SkASSERT(!oPrior.fTiny && oPrior.fT < 1);
- other->addEndSpan(span.fOtherIndex);
- angle = &this->angle(span.fToAngleIndex);
- oAngle = &other->angle(oSpan.fFromAngleIndex);
+ 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].fFromAngleIndex < 0
- && other->fTs[span.fOtherIndex + 1].fToAngleIndex < 0)));
+ 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.fFromAngleIndex >= 0 || osSpan.fT > 0) {
+ if (osSpan.fFromAngle || osSpan.fT > 0) {
break;
}
++oIndex;
SkASSERT(oIndex < other->count());
} while (true);
other->addStartSpan(oIndex);
- angle = &this->angle(span.fFromAngleIndex);
- oAngle = &other->angle(oSpan.fToAngleIndex);
+ angle = span->fFromAngle;
+ oAngle = oSpan.fToAngle;
}
angle->insert(oAngle);
}
+void SkOpSegment::alignMultiples(SkTDArray<AlignedSpan>* alignedArray) {
+ debugValidate();
+ int count = this->count();
+ for (int index = 0; index < count; ++index) {
+ SkOpSpan& span = fTs[index];
+ if (!span.fMultiple) {
+ continue;
+ }
+ int end = nextExactSpan(index, 1);
+ SkASSERT(end > index + 1);
+ const SkPoint& thisPt = span.fPt;
+ while (index < end - 1) {
+ SkOpSegment* other1 = span.fOther;
+ int oCnt = other1->count();
+ for (int idx2 = index + 1; idx2 < end; ++idx2) {
+ SkOpSpan& span2 = fTs[idx2];
+ SkOpSegment* other2 = span2.fOther;
+ for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
+ SkOpSpan& oSpan = other1->fTs[oIdx];
+ if (oSpan.fOther != other2) {
+ continue;
+ }
+ if (oSpan.fPt == thisPt) {
+ goto skipExactMatches;
+ }
+ }
+ for (int oIdx = 0; oIdx < oCnt; ++oIdx) {
+ SkOpSpan& oSpan = other1->fTs[oIdx];
+ if (oSpan.fOther != other2) {
+ continue;
+ }
+ if (SkDPoint::RoughlyEqual(oSpan.fPt, thisPt)) {
+ SkOpSpan& oSpan2 = other2->fTs[oSpan.fOtherIndex];
+ if (zero_or_one(span.fOtherT) || zero_or_one(oSpan.fT)
+ || zero_or_one(span2.fOtherT) || zero_or_one(oSpan2.fT)) {
+ return;
+ }
+ if (!way_roughly_equal(span.fOtherT, oSpan.fT)
+ || !way_roughly_equal(span2.fOtherT, oSpan2.fT)
+ || !way_roughly_equal(span2.fOtherT, oSpan.fOtherT)
+ || !way_roughly_equal(span.fOtherT, oSpan2.fOtherT)) {
+ return;
+ }
+ alignSpan(thisPt, span.fOtherT, other1, span2.fOtherT,
+ other2, &oSpan, alignedArray);
+ alignSpan(thisPt, span2.fOtherT, other2, span.fOtherT,
+ other1, &oSpan2, alignedArray);
+ break;
+ }
+ }
+ skipExactMatches:
+ ;
+ }
+ ++index;
+ }
+ }
+ debugValidate();
+}
+
+void SkOpSegment::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];
@@ -877,6 +1030,156 @@
}
}
+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);
+}
+
void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr,
SkTArray<SkPoint, true>* outsideTs) {
int index = *indexPtr;
@@ -897,6 +1200,12 @@
*indexPtr = index;
}
+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)
@@ -1025,13 +1334,13 @@
int oPeekIndex = oIndex;
bool success = true;
SkOpSpan* oPeek;
+ int oCount = other->count();
do {
oPeek = &other->fTs[oPeekIndex];
- if (oPeek->fT == 1) {
+ if (++oPeekIndex == oCount) {
success = false;
break;
}
- ++oPeekIndex;
} while (endPt != oPeek->fPt);
if (success) {
// make sure the matching point completes the coincidence span
@@ -1063,12 +1372,14 @@
if (!other->done() && oOutsidePts.count()) {
other->addCoinOutsides(oOutsidePts[0], endPt, this);
}
+ setCoincidentRange(startPt, endPt, other);
+ other->setCoincidentRange(startPt, endPt, this);
}
// FIXME: this doesn't prevent the same span from being added twice
// fix in caller, SkASSERT here?
const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
- const SkPoint& pt) {
+ const SkPoint& pt, const SkPoint& pt2) {
int tCount = fTs.count();
for (int tIndex = 0; tIndex < tCount; ++tIndex) {
const SkOpSpan& span = fTs[tIndex];
@@ -1089,24 +1400,23 @@
__FUNCTION__, fID, t, other->fID, otherT);
#endif
int insertedAt = addT(other, pt, t);
- int otherInsertedAt = other->addT(this, pt, otherT);
+ int otherInsertedAt = other->addT(this, pt2, otherT);
addOtherT(insertedAt, otherT, otherInsertedAt);
other->addOtherT(otherInsertedAt, t, insertedAt);
matchWindingValue(insertedAt, t, borrowWind);
other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
- return &span(insertedAt);
+ SkOpSpan& span = this->fTs[insertedAt];
+ if (pt != pt2) {
+ span.fNear = true;
+ SkOpSpan& oSpan = other->fTs[otherInsertedAt];
+ oSpan.fNear = true;
+ }
+ return &span;
}
-const SkOpAngle& SkOpSegment::angle(int index) const {
- SkASSERT(index >= 0);
- int count = fAngles.count();
- if (index < count) {
- return fAngles[index];
- }
- index -= count;
- count = fSingletonAngles.count();
- SkASSERT(index < count);
- return fSingletonAngles[index];
+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 {
@@ -1138,9 +1448,7 @@
const SkOpSpan* span = &fTs[0];
if (firstSpan->fT == 0 || span->fTiny || span->fOtherT != 1 || span->fOther->multipleEnds()) {
index = findStartSpan(0); // curve start intersects
- if (index < 0) {
- return false;
- }
+ SkASSERT(index > 0);
if (activePrior >= 0) {
addStartSpan(index);
}
@@ -1150,9 +1458,7 @@
span = &fTs[endIndex - 1];
if ((addEnd = span->fT == 1 || span->fTiny)) { // if curve end intersects
endIndex = findEndSpan(endIndex);
- if (endIndex < 0) {
- return false;
- }
+ SkASSERT(endIndex > 0);
} else {
addEnd = fTs[endIndex].fOtherT != 0 || fTs[endIndex].fOther->multipleStarts();
}
@@ -1174,24 +1480,19 @@
return false;
}
} while (true);
- int angleIndex = fAngles.count();
- int priorAngleIndex;
+ SkOpAngle* angle = NULL;
+ SkOpAngle* priorAngle;
if (activePrior >= 0) {
int pActive = firstActive(prior);
SkASSERT(pActive < start);
- fAngles.push_back().set(this, start, pActive);
- priorAngleIndex = angleIndex++;
- #if DEBUG_ANGLE
- fAngles.back().setID(priorAngleIndex);
- #endif
+ priorAngle = &fAngles.push_back();
+ priorAngle->set(this, start, pActive);
}
int active = checkSetAngle(start);
if (active >= 0) {
SkASSERT(active < index);
- fAngles.push_back().set(this, active, index);
- #if DEBUG_ANGLE
- fAngles.back().setID(angleIndex);
- #endif
+ angle = &fAngles.push_back();
+ angle->set(this, active, index);
}
#if DEBUG_ANGLE
debugCheckPointsEqualish(start, index);
@@ -1199,20 +1500,20 @@
prior = start;
do {
const SkOpSpan* startSpan = &fTs[start - 1];
- if (!startSpan->fSmall || startSpan->fFromAngleIndex >= 0
- || startSpan->fToAngleIndex >= 0) {
+ if (!startSpan->fSmall || isCanceled(start - 1) || startSpan->fFromAngle
+ || startSpan->fToAngle) {
break;
}
--start;
} while (start > 0);
do {
if (activePrior >= 0) {
- SkASSERT(fTs[start].fFromAngleIndex == -1);
- fTs[start].fFromAngleIndex = priorAngleIndex;
+ SkASSERT(fTs[start].fFromAngle == NULL);
+ fTs[start].fFromAngle = priorAngle;
}
if (active >= 0) {
- SkASSERT(fTs[start].fToAngleIndex == -1);
- fTs[start].fToAngleIndex = angleIndex;
+ SkASSERT(fTs[start].fToAngle == NULL);
+ fTs[start].fToAngle = angle;
}
} while (++start < index);
activePrior = active;
@@ -1231,7 +1532,7 @@
return isCanceled(tIndex) ? -1 : tIndex;
}
-// at this point, the span is already ordered, or unorderable, or unsortable
+// 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);
@@ -1242,50 +1543,61 @@
// or if no adjacent angles are orderable,
// or if adjacent orderable angles have no computed winding,
// there's nothing to do
- // if two orderable angles are adjacent, and one has winding computed, transfer to the other
+ // 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;
+ SkOpAngle* angle = firstAngle->previous();
+ SkOpAngle* next = angle->next();
+ firstAngle = next;
do {
- int testWinding = angle->segment()->windSum(angle);
- if (SK_MinS32 != testWinding && !angle->unorderable()) {
- baseAngle = angle;
+ 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;
}
- if (angle->unorderable()) {
- baseAngle = NULL;
+ int testWinding = angle->segment()->windSum(angle);
+ if (SK_MinS32 != testWinding) {
+ baseAngle = angle;
tryReverse = true;
continue;
}
if (baseAngle) {
ComputeOneSum(baseAngle, angle, includeType);
baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
- tryReverse |= !baseAngle;
}
- } while ((angle = angle->next()) != firstAngle);
- if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(angle)) {
+ } while (next != firstAngle);
+ if (baseAngle && SK_MinS32 == firstAngle->segment()->windSum(firstAngle)) {
firstAngle = baseAngle;
tryReverse = true;
}
if (tryReverse) {
baseAngle = NULL;
- angle = firstAngle;
+ 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 (angle->unorderable()) {
- baseAngle = NULL;
- continue;
- }
if (baseAngle) {
ComputeOneSumReverse(baseAngle, angle, includeType);
baseAngle = SK_MinS32 != angle->segment()->windSum(angle) ? angle : NULL;
}
- } while ((angle = angle->previous()) != firstAngle);
+ } while (prior != firstAngle);
}
int minIndex = SkMin32(startIndex, endIndex);
return windSum(minIndex);
@@ -1362,6 +1674,31 @@
return false;
}
+bool SkOpSegment::containsT(double t, const SkOpSegment* other, double otherT) const {
+ int count = this->count();
+ for (int index = 0; index < count; ++index) {
+ const SkOpSpan& span = fTs[index];
+ if (t < span.fT) {
+ return false;
+ }
+ if (t == span.fT) {
+ if (other != span.fOther) {
+ continue;
+ }
+ if (other->fVerb != SkPath::kCubic_Verb) {
+ return true;
+ }
+ if (!other->fLoop) {
+ return true;
+ }
+ double otherMidT = (otherT + span.fOtherT) / 2;
+ SkPoint otherPt = other->ptAtT(otherMidT);
+ return SkDPoint::ApproximatelyEqual(span.fPt, otherPt);
+ }
+ }
+ return false;
+}
+
int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
bool* hitSomething, double mid, bool opp, bool current) const {
SkScalar bottom = fBounds.fBottom;
@@ -1542,6 +1879,58 @@
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();
@@ -1561,6 +1950,9 @@
}
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;
@@ -1602,6 +1994,33 @@
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) {
@@ -1777,8 +2196,10 @@
continue;
}
// force the duplicates to agree on t and pt if not on the end
- double thisT = fTs[index].fT;
- const SkPoint& thisPt = fTs[index].fPt;
+ 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);
@@ -1786,6 +2207,7 @@
if (aligned) {
alignSpanState(start, end);
}
+ fMultiples = true;
}
debugValidate();
}
@@ -2146,6 +2568,30 @@
}
}
+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);
@@ -2235,12 +2681,11 @@
SkASSERT(startIndex != endIndex);
SkDEBUGCODE(const int count = fTs.count());
SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
- const int step = SkSign32(endIndex - startIndex);
- const int end = nextExactSpan(startIndex, step);
- SkASSERT(end >= 0);
- SkOpSpan* endSpan = &fTs[end];
- SkOpSegment* other;
- if (isSimple(end)) {
+ int step = SkSign32(endIndex - startIndex);
+ *nextStart = startIndex;
+ SkOpSegment* other = isSimple(nextStart, &step);
+ 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
@@ -2251,8 +2696,6 @@
return NULL;
}
markDoneBinary(min);
- other = endSpan->fOther;
- *nextStart = endSpan->fOtherIndex;
double startT = other->fTs[*nextStart].fT;
*nextEnd = *nextStart;
do {
@@ -2265,6 +2708,8 @@
}
return other;
}
+ const int end = nextExactSpan(startIndex, step);
+ SkASSERT(end >= 0);
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
// more than one viable candidate -- measure angles to find best
@@ -2325,7 +2770,7 @@
continue;
}
if (!activeAngle) {
- nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
+ (void) nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
}
SkOpSpan* last = nextAngle->lastMarked();
if (last) {
@@ -2365,12 +2810,11 @@
SkASSERT(startIndex != endIndex);
SkDEBUGCODE(const int count = fTs.count());
SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
- const int step = SkSign32(endIndex - startIndex);
- const int end = nextExactSpan(startIndex, step);
- SkASSERT(end >= 0);
- SkOpSpan* endSpan = &fTs[end];
- SkOpSegment* other;
- if (isSimple(end)) {
+ int step = SkSign32(endIndex - startIndex);
+ *nextStart = startIndex;
+ SkOpSegment* other = isSimple(nextStart, &step);
+ 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
@@ -2381,8 +2825,6 @@
return NULL;
}
markDoneUnary(min);
- other = endSpan->fOther;
- *nextStart = endSpan->fOtherIndex;
double startT = other->fTs[*nextStart].fT;
*nextEnd = *nextStart;
do {
@@ -2395,6 +2837,8 @@
}
return other;
}
+ const int end = nextExactSpan(startIndex, step);
+ SkASSERT(end >= 0);
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
// more than one viable candidate -- measure angles to find best
@@ -2474,13 +2918,12 @@
SkDEBUGCODE(int count = fTs.count());
SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
int step = SkSign32(endIndex - startIndex);
- int end = nextExactSpan(startIndex, step);
- SkASSERT(end >= 0);
- SkOpSpan* endSpan = &fTs[end];
- SkOpSegment* other;
// Detect cases where all the ends canceled out (e.g.,
-// there is no angle) and therefore there's only one valid connection
- if (isSimple(end) || !spanToAngle(end, startIndex)) {
+// there is no angle) and therefore there's only one valid connection
+ *nextStart = startIndex;
+ SkOpSegment* other = isSimple(nextStart, &step);
+ if (other)
+ {
#if DEBUG_WINDING
SkDebugf("%s simple\n", __FUNCTION__);
#endif
@@ -2489,8 +2932,6 @@
return NULL;
}
markDone(min, 1);
- other = endSpan->fOther;
- *nextStart = endSpan->fOtherIndex;
double startT = other->fTs[*nextStart].fT;
// FIXME: I don't know why the logic here is difference from the winding case
SkDEBUGCODE(bool firstLoop = true;)
@@ -2517,6 +2958,8 @@
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);
#if DEBUG_SORT
@@ -2562,24 +3005,12 @@
const SkOpSpan* span = &fTs[index];
const SkPoint& firstPt = span->fPt;
double firstT = span->fT;
+ const SkOpSpan* prior;
do {
- if (index > 0) {
- if (span->fT != firstT) {
- break;
- }
- if (!SkDPoint::ApproximatelyEqual(firstPt, fTs[index].fPt)) {
- return -1;
- }
- }
- ++index;
- if (span->fTiny) {
- if (!SkDPoint::ApproximatelyEqual(firstPt, fTs[index].fPt)) {
- return -1;
- }
- firstT = fTs[index++].fT;
- }
- span = &fTs[index];
- } while (true);
+ prior = span;
+ span = &fTs[++index];
+ } while (SkDPoint::ApproximatelyEqual(span->fPt, firstPt)
+ && (span->fT == firstT || prior->fTiny));
return index;
}
@@ -2595,6 +3026,17 @@
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();
for (int index = 0; index < count; ++index) {
@@ -2647,7 +3089,7 @@
SkASSERT(firstT - end != 0);
SkOpAngle* markAngle = spanToAngle(firstT, end);
if (!markAngle) {
- markAngle = addSingletonAngles(firstT, step);
+ markAngle = addSingletonAngles(step);
}
markAngle->markStops();
const SkOpAngle* baseAngle = markAngle->findFirst();
@@ -2754,13 +3196,26 @@
}
}
+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
+}
+
void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd) {
fDoneSpans = 0;
fOperand = operand;
fXor = evenOdd;
fPts = pts;
fVerb = verb;
- fLoop = fSmall = fTiny = false;
+ fLoop = fMultiples = fSmall = fTiny = false;
}
void SkOpSegment::initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType) {
@@ -2793,16 +3248,13 @@
SkASSERT(dx);
int windVal = windValue(SkMin32(start, end));
#if DEBUG_WINDING_AT_T
- SkDebugf("%s oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, winding,
+ SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, debugID(), winding,
hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
#endif
int sideWind = winding + (dx < 0 ? windVal : -windVal);
if (abs(winding) < abs(sideWind)) {
winding = sideWind;
}
-#if DEBUG_WINDING_AT_T
- SkDebugf(" winding=%d\n", winding);
-#endif
SkDEBUGCODE(int oppLocal = oppSign(start, end));
SkASSERT(hitOppDx || !oppWind || !oppLocal);
int oppWindVal = oppValue(SkMin32(start, end));
@@ -2814,6 +3266,9 @@
oppWind = oppSideWind;
}
}
+#if DEBUG_WINDING_AT_T
+ SkDebugf(" winding=%d oppWind=%d\n", winding, oppWind);
+#endif
(void) markAndChaseWinding(start, end, winding, oppWind);
// OPTIMIZATION: the reverse mark and chase could skip the first marking
(void) markAndChaseWinding(end, start, winding, oppWind);
@@ -2824,12 +3279,12 @@
return false;
}
int index = *indexPtr;
- int froIndex = fTs[index].fFromAngleIndex;
- int toIndex = fTs[index].fToAngleIndex;
+ SkOpAngle* from = fTs[index].fFromAngle;
+ SkOpAngle* to = fTs[index].fToAngle;
while (++index < spanCount) {
- int nextFro = fTs[index].fFromAngleIndex;
- int nextTo = fTs[index].fToAngleIndex;
- if (froIndex != nextFro || toIndex != nextTo) {
+ SkOpAngle* nextFrom = fTs[index].fFromAngle;
+ SkOpAngle* nextTo = fTs[index].fToAngle;
+ if (from != nextFrom || to != nextTo) {
break;
}
}
@@ -2850,26 +3305,9 @@
return true;
}
-bool SkOpSegment::isSimple(int end) const {
-#if 1
- int count = fTs.count();
- if (count == 2) {
- return true;
- }
- double t = fTs[end].fT;
- if (approximately_less_than_zero(t)) {
- return !approximately_less_than_zero(fTs[1].fT);
- }
- if (approximately_greater_than_one(t)) {
- return !approximately_greater_than_one(fTs[count - 2].fT);
- }
- return false;
-#else
- // OPTIMIZE: code could be rejiggered to use this simpler test. To make this work, a little
- // more logic is required to ignore the dangling canceled out spans
- const SkOpSpan& span = fTs[end];
- return span.fFromAngleIndex < 0 && span.fToAngleIndex < 0;
-#endif
+
+SkOpSegment* SkOpSegment::isSimple(int* end, int* step) {
+ return nextChase(end, step, NULL, NULL);
}
bool SkOpSegment::isTiny(const SkOpAngle* angle) const {
@@ -2928,11 +3366,12 @@
int step = SkSign32(endIndex - index);
int min = SkMin32(index, endIndex);
markDoneBinary(min);
- SkOpSpan* last;
+ SkOpSpan* last = NULL;
SkOpSegment* other = this;
- while ((other = other->nextChase(&index, step, &min, &last))) {
+ while ((other = other->nextChase(&index, &step, &min, &last))) {
if (other->done()) {
- return NULL;
+ SkASSERT(!last);
+ break;
}
other->markDoneBinary(min);
}
@@ -2943,11 +3382,12 @@
int step = SkSign32(endIndex - index);
int min = SkMin32(index, endIndex);
markDoneUnary(min);
- SkOpSpan* last;
+ SkOpSpan* last = NULL;
SkOpSegment* other = this;
- while ((other = other->nextChase(&index, step, &min, &last))) {
+ while ((other = other->nextChase(&index, &step, &min, &last))) {
if (other->done()) {
- return NULL;
+ SkASSERT(!last);
+ break;
}
other->markDoneUnary(min);
}
@@ -2960,12 +3400,13 @@
int step = SkSign32(endIndex - index);
int min = SkMin32(index, endIndex);
markWinding(min, winding);
- SkOpSpan* last;
+ SkOpSpan* last = NULL;
SkOpSegment* other = this;
- while ((other = other->nextChase(&index, step, &min, &last))) {
+ while ((other = other->nextChase(&index, &step, &min, &last))) {
if (other->fTs[min].fWindSum != SK_MinS32) {
SkASSERT(other->fTs[min].fWindSum == winding);
- return NULL;
+ SkASSERT(!last);
+ break;
}
other->markWinding(min, winding);
}
@@ -2976,12 +3417,13 @@
int min = SkMin32(index, endIndex);
int step = SkSign32(endIndex - index);
markWinding(min, winding);
- SkOpSpan* last;
+ SkOpSpan* last = NULL;
SkOpSegment* other = this;
- while ((other = other->nextChase(&index, step, &min, &last))) {
+ while ((other = other->nextChase(&index, &step, &min, &last))) {
if (other->fTs[min].fWindSum != SK_MinS32) {
SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
- return NULL;
+ SkASSERT(!last);
+ break;
}
other->markWinding(min, winding);
}
@@ -2992,14 +3434,32 @@
int min = SkMin32(index, endIndex);
int step = SkSign32(endIndex - index);
markWinding(min, winding, oppWinding);
- SkOpSpan* last;
+ SkOpSpan* last = NULL;
SkOpSegment* other = this;
- while ((other = other->nextChase(&index, step, &min, &last))) {
+ while ((other = other->nextChase(&index, &step, &min, &last))) {
if (other->fTs[min].fWindSum != SK_MinS32) {
- SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoop);
- return NULL;
+#if 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 {
+ SkASSERT(other->fTs[min].fWindSum == oppWinding);
+// FIXME: this is probably a bug -- skpwww_joomla_org_23 asserts here
+// SkASSERT(other->fTs[min].fOppSum == winding);
+ }
+ }
+ SkASSERT(!last);
+#endif
+ break;
}
- other->markWinding(min, winding, oppWinding);
+ if (fOperand == other->fOperand) {
+ other->markWinding(min, winding, oppWinding);
+ } else {
+ other->markWinding(min, oppWinding, winding);
+ }
}
return last;
}
@@ -3316,15 +3776,6 @@
}
}
-// return span if when chasing, two or more radiating spans are not done
-// OPTIMIZATION: ? multiple spans is detected when there is only one valid
-// candidate and the remaining spans have windValue == 0 (canceled by
-// coincidence). The coincident edges could either be removed altogether,
-// or this code could be more complicated in detecting this case. Worth it?
-bool SkOpSegment::multipleSpans(int end) const {
- return end > 0 && end < fTs.count() - 1;
-}
-
bool SkOpSegment::nextCandidate(int* start, int* end) const {
while (fTs[*end].fDone) {
if (fTs[*end].fT == 1) {
@@ -3337,27 +3788,67 @@
return true;
}
-SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSpan** last) {
- int end = nextExactSpan(*index, step);
+static SkOpSegment* set_last(SkOpSpan** last, SkOpSpan* endSpan) {
+ if (last && !endSpan->fSmall) {
+ *last = endSpan;
+ }
+ return NULL;
+}
+
+SkOpSegment* SkOpSegment::nextChase(int* indexPtr, int* stepPtr, int* minPtr, SkOpSpan** last) {
+ int origIndex = *indexPtr;
+ int step = *stepPtr;
+ int end = nextExactSpan(origIndex, step);
SkASSERT(end >= 0);
- if (fTs[end].fSmall) {
- *last = NULL;
- return NULL;
+ SkOpSpan& endSpan = fTs[end];
+ SkOpAngle* angle = step > 0 ? endSpan.fFromAngle : endSpan.fToAngle;
+ int foundIndex;
+ int otherEnd;
+ SkOpSegment* other;
+ if (angle == NULL) {
+ if (endSpan.fT != 0 && endSpan.fT != 1) {
+ return NULL;
+ }
+ other = endSpan.fOther;
+ foundIndex = endSpan.fOtherIndex;
+ otherEnd = other->nextExactSpan(foundIndex, step);
+ } else {
+ int loopCount = angle->loopCount();
+ if (loopCount > 2) {
+ return set_last(last, &endSpan);
+ }
+ const SkOpAngle* next = angle->next();
+ if (angle->sign() != next->sign()) {
+#if DEBUG_WINDING
+ SkDebugf("%s mismatched signs\n", __FUNCTION__);
+#endif
+ // return set_last(last, &endSpan);
+ }
+ other = next->segment();
+ foundIndex = end = next->start();
+ otherEnd = next->end();
}
- if (multipleSpans(end)) {
- *last = &fTs[end];
- return NULL;
+ int foundStep = foundIndex < otherEnd ? 1 : -1;
+ if (*stepPtr != foundStep) {
+ return set_last(last, &endSpan);
}
- const SkOpSpan& endSpan = fTs[end];
- SkOpSegment* other = endSpan.fOther;
- *index = endSpan.fOtherIndex;
- SkASSERT(*index >= 0);
- int otherEnd = other->nextExactSpan(*index, step);
+ SkASSERT(*indexPtr >= 0);
SkASSERT(otherEnd >= 0);
- *min = SkMin32(*index, otherEnd);
- if (other->fTs[*min].fSmall) {
- *last = NULL;
- return NULL;
+#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);
+ }
+#endif
+ *indexPtr = foundIndex;
+ *stepPtr = foundStep;
+ if (minPtr) {
+ *minPtr = foundMin;
}
return other;
}
@@ -3414,6 +3905,27 @@
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;
+ }
+}
+
+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;
+ }
+ }
+}
+
void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding) {
int deltaSum = spanSign(index, endIndex);
@@ -3452,15 +3964,15 @@
}
int index = 0;
do {
- int fromIndex = fTs[index].fFromAngleIndex;
- int toIndex = fTs[index].fToAngleIndex;
- if (fromIndex < 0 && toIndex < 0) {
+ SkOpAngle* fromAngle = fTs[index].fFromAngle;
+ SkOpAngle* toAngle = fTs[index].fToAngle;
+ if (!fromAngle && !toAngle) {
index += 1;
continue;
}
SkOpAngle* baseAngle = NULL;
- if (fromIndex >= 0) {
- baseAngle = &this->angle(fromIndex);
+ if (fromAngle) {
+ baseAngle = fromAngle;
if (inLoop(baseAngle, spanCount, &index)) {
continue;
}
@@ -3468,8 +3980,7 @@
#if DEBUG_ANGLE
bool wroteAfterHeader = false;
#endif
- if (toIndex >= 0) {
- SkOpAngle* toAngle = &this->angle(toIndex);
+ if (toAngle) {
if (!baseAngle) {
baseAngle = toAngle;
if (inLoop(baseAngle, spanCount, &index)) {
@@ -3486,14 +3997,14 @@
baseAngle->insert(toAngle);
}
}
- int nextFrom, nextTo;
+ SkOpAngle* nextFrom, * nextTo;
int firstIndex = index;
do {
SkOpSpan& span = fTs[index];
SkOpSegment* other = span.fOther;
SkOpSpan& oSpan = other->fTs[span.fOtherIndex];
- int otherAngleIndex = oSpan.fFromAngleIndex;
- if (otherAngleIndex >= 0) {
+ SkOpAngle* oAngle = oSpan.fFromAngle;
+ if (oAngle) {
#if DEBUG_ANGLE
if (!wroteAfterHeader) {
SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
@@ -3501,13 +4012,12 @@
wroteAfterHeader = true;
}
#endif
- SkOpAngle* oAngle = &other->angle(otherAngleIndex);
if (!oAngle->loopContains(*baseAngle)) {
baseAngle->insert(oAngle);
}
}
- otherAngleIndex = oSpan.fToAngleIndex;
- if (otherAngleIndex >= 0) {
+ oAngle = oSpan.fToAngle;
+ if (oAngle) {
#if DEBUG_ANGLE
if (!wroteAfterHeader) {
SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), fTs[index].fT,
@@ -3515,7 +4025,6 @@
wroteAfterHeader = true;
}
#endif
- SkOpAngle* oAngle = &other->angle(otherAngleIndex);
if (!oAngle->loopContains(*baseAngle)) {
baseAngle->insert(oAngle);
}
@@ -3523,20 +4032,20 @@
if (++index == spanCount) {
break;
}
- nextFrom = fTs[index].fFromAngleIndex;
- nextTo = fTs[index].fToAngleIndex;
- } while (fromIndex == nextFrom && toIndex == nextTo);
+ 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.fFromAngleIndex = span.fToAngleIndex = -1;
+ span.fFromAngle = span.fToAngle = NULL;
if (++index == spanCount) {
break;
}
- nextFrom = fTs[index].fFromAngleIndex;
- nextTo = fTs[index].fToAngleIndex;
- } while (fromIndex == nextFrom && toIndex == nextTo);
+ nextFrom = fTs[index].fFromAngle;
+ nextTo = fTs[index].fToAngle;
+ } while (fromAngle == nextFrom && toAngle == nextTo);
baseAngle = NULL;
}
#if DEBUG_SORT
@@ -3749,7 +4258,8 @@
SkASSERT(winding != SK_MinS32);
int windVal = crossOpp ? oppValue(tIndex) : windValue(tIndex);
#if DEBUG_WINDING_AT_T
- SkDebugf("%s oldWinding=%d windValue=%d", __FUNCTION__, winding, windVal);
+ SkDebugf("%s id=%d opp=%d tHit=%1.9g t=%1.9g oldWinding=%d windValue=%d", __FUNCTION__,
+ debugID(), crossOpp, tHit, t(tIndex), 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;
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 1eaef69..90ed553 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -18,6 +18,7 @@
#include "SkThread.h"
#endif
+struct SkCoincidence;
class SkPathWriter;
class SkOpSegment {
@@ -32,11 +33,15 @@
return fBounds.fTop < rh.fBounds.fTop;
}
- // FIXME: add some template or macro to avoid casting
- SkOpAngle& angle(int index) {
- const SkOpAngle& cAngle = (const_cast<const SkOpSegment*>(this))->angle(index);
- return const_cast<SkOpAngle&>(cAngle);
- }
+ struct AlignedSpan {
+ double fOldT;
+ double fT;
+ SkPoint fOldPt;
+ SkPoint fPt;
+ const SkOpSegment* fSegment;
+ const SkOpSegment* fOther1;
+ const SkOpSegment* fOther2;
+ };
const SkPathOpsBounds& bounds() const {
return fBounds;
@@ -81,6 +86,10 @@
return dxdy(index).fY;
}
+ bool hasMultiples() const {
+ return fMultiples;
+ }
+
bool hasSmall() const {
return fSmall;
}
@@ -185,8 +194,7 @@
const SkOpAngle* spanToAngle(int tStart, int tEnd) const {
SkASSERT(tStart != tEnd);
const SkOpSpan& span = fTs[tStart];
- int index = tStart < tEnd ? span.fToAngleIndex : span.fFromAngleIndex;
- return index >= 0 ? &angle(index) : NULL;
+ return tStart < tEnd ? span.fToAngle : span.fFromAngle;
}
// FIXME: create some sort of macro or template that avoids casting
@@ -278,11 +286,19 @@
SkOpSegment* other);
const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
const SkPoint& pt);
+ const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind,
+ const SkPoint& pt, const SkPoint& oPt);
+ void alignMultiples(SkTDArray<AlignedSpan>* aligned);
bool alignSpan(int index, double thisT, const SkPoint& thisPt);
void alignSpanState(int start, int end);
- const SkOpAngle& angle(int index) const;
bool betweenTs(int lesser, double testT, int greater) const;
+ void blindCancel(const SkCoincidence& coincidence, SkOpSegment* other);
+ void blindCoincident(const SkCoincidence& coincidence, SkOpSegment* other);
bool calcAngles();
+ double calcMissingTEnd(const SkOpSegment* ref, double loEnd, double min, double max,
+ double hiEnd, const SkOpSegment* other, int thisEnd);
+ double calcMissingTStart(const SkOpSegment* ref, double loEnd, double min, double max,
+ double hiEnd, const SkOpSegment* other, int thisEnd);
void checkDuplicates();
void checkEnds();
void checkMultiples();
@@ -301,6 +317,7 @@
bool* unsortable);
SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
int findExactT(double t, const SkOpSegment* ) const;
+ int findOtherT(double t, const SkOpSegment* ) const;
int findT(double t, const SkPoint& , const SkOpSegment* ) const;
SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool firstPass);
void fixOtherTIndex();
@@ -321,6 +338,7 @@
void markDoneUnary(int index);
bool nextCandidate(int* start, int* end) const;
int nextSpan(int from, int step) const;
+ void pinT(const SkPoint& pt, double* t);
void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
void sortAngles();
@@ -334,9 +352,6 @@
int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;
int windSum(const SkOpAngle* angle) const;
// available for testing only
-#if DEBUG_VALIDATE
- bool debugContains(const SkOpAngle* ) const;
-#endif
#if defined(SK_DEBUG) || !FORCE_RELEASE
int debugID() const {
return fID;
@@ -358,6 +373,7 @@
const SkTDArray<SkOpSpan>& debugSpans() const;
void debugValidate() const;
// available to testing only
+ const SkOpAngle* debugLastAngle() const;
void dumpAngles() const;
void dumpContour(int firstID, int lastID) const;
void dumpPts() const;
@@ -382,18 +398,22 @@
bool activeWinding(int index, int endIndex, int* sumWinding);
void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
- int addSingletonAngleDown(int start, SkOpSegment** otherPtr);
- int addSingletonAngleUp(int start, SkOpSegment** otherPtr);
- SkOpAngle* addSingletonAngles(int start, int step);
- void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
- const SkPoint& oPt);
+ SkOpAngle* addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** );
+ SkOpAngle* addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** );
+ SkOpAngle* addSingletonAngles(int step);
+ void alignSpan(const SkPoint& newPt, double newT, const SkOpSegment* other, double otherT,
+ const SkOpSegment* other2, SkOpSpan* oSpan, SkTDArray<AlignedSpan>* );
bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;
+ void bumpCoincidentBlind(bool binary, int index, int last);
void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index,
SkTArray<SkPoint, true>* outsideTs);
+ void bumpCoincidentOBlind(int index, int last);
void bumpCoincidentOther(const SkOpSpan& oTest, int* index,
SkTArray<SkPoint, true>* outsideTs);
bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
bool calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts);
+ bool checkForSmall(const SkOpSpan* span, const SkPoint& pt, double newT,
+ int* less, int* more) const;
void checkLinks(const SkOpSpan* ,
SkTArray<MissingSpan, true>* missingSpans) const;
static void CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan,
@@ -402,19 +422,26 @@
SkTArray<MissingSpan, true>* missingSpans);
int checkSetAngle(int tIndex) const;
void checkSmallCoincidence(const SkOpSpan& span, SkTArray<MissingSpan, true>* );
+ bool coincidentSmall(const SkPoint& pt, double t, const SkOpSegment* other) const;
bool clockwise(int tStart, int tEnd) const;
static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
SkOpAngle::IncludeType );
static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
SkOpAngle::IncludeType );
+ bool containsT(double t, const SkOpSegment* other, double otherT) const;
bool decrementSpan(SkOpSpan* span);
int findEndSpan(int endIndex) const;
int findStartSpan(int startIndex) const;
int firstActive(int tIndex) const;
const SkOpSpan& firstSpan(const SkOpSpan& thisSpan) const;
void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
+ bool inCoincidentSpan(double t, const SkOpSegment* other) const;
bool inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const;
+#if OLD_CHASE
bool isSimple(int end) const;
+#else
+ SkOpSegment* isSimple(int* end, int* step);
+#endif
bool isTiny(int index) const;
const SkOpSpan& lastSpan(const SkOpSpan& thisSpan) const;
void matchWindingValue(int tIndex, double t, bool borrowWind);
@@ -436,20 +463,15 @@
void markWinding(int index, int winding, int oppWinding);
bool monotonicInY(int tStart, int tEnd) const;
- bool multipleEnds() const {
- return fTs[count() - 2].fT == 1;
- }
+ bool multipleEnds() const { return fTs[count() - 2].fT == 1; }
+ bool multipleStarts() const { return fTs[1].fT == 0; }
- bool multipleStarts() const {
- return fTs[1].fT == 0;
- }
-
- bool multipleSpans(int end) const;
- SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
+ SkOpSegment* nextChase(int* index, int* step, int* min, SkOpSpan** last);
int nextExactSpan(int from, int step) const;
bool serpentine(int tStart, int tEnd) const;
- void setFromAngleIndex(int endIndex, int angleIndex);
- void setToAngleIndex(int endIndex, int angleIndex);
+ void setCoincidentRange(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
+ void setFromAngle(int endIndex, SkOpAngle* );
+ void setToAngle(int endIndex, SkOpAngle* );
void setUpWindings(int index, int endIndex, int* sumMiWinding,
int* maxWinding, int* sumWinding);
void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
@@ -509,14 +531,13 @@
SkPathOpsBounds fBounds;
// FIXME: can't convert to SkTArray because it uses insert
SkTDArray<SkOpSpan> fTs; // 2+ (always includes t=0 t=1) -- at least (number of spans) + 1
-// FIXME: replace both with bucket storage that allows direct immovable pointers to angles
- SkTArray<SkOpAngle, true> fSingletonAngles; // 0 or 2 -- allocated for singletons
- SkTArray<SkOpAngle, true> fAngles; // 0 or 2+ -- (number of non-zero spans) * 2
+ SkOpAngleSet fAngles; // empty or 2+ -- (number of non-zero spans) * 2
// OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value
int fDoneSpans; // quick check that segment is finished
// OPTIMIZATION: force the following to be byte-sized
SkPath::Verb fVerb;
bool fLoop; // set if cubic intersects itself
+ bool fMultiples; // set if curve intersects multiple other curves at one interior point
bool fOperand;
bool fXor; // set if original contour had even-odd fill
bool fOppXor; // set if opposite operand had even-odd fill
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index 1ffdc0e..d9ce44e 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -9,23 +9,27 @@
#include "SkPoint.h"
+class SkOpAngle;
class SkOpSegment;
struct SkOpSpan {
- SkOpSegment* fOther;
SkPoint fPt; // computed when the curves are intersected
double fT;
double fOtherT; // value at fOther[fOtherIndex].fT
+ SkOpSegment* fOther;
+ SkOpAngle* fFromAngle; // (if t > 0) index into segment's angle array going negative in t
+ SkOpAngle* fToAngle; // (if t < 1) index into segment's angle array going positive in t
int fOtherIndex; // can't be used during intersection
- int fFromAngleIndex; // (if t > 0) index into segment's angle array going negative in t
- int fToAngleIndex; // (if t < 1) index into segment's angle array going positive in t
int fWindSum; // accumulated from contours surrounding this one.
int fOppSum; // for binary operators: the opposite winding sum
int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here
bool fChased; // set after span has been added to chase array
+ bool fCoincident; // set if span is bumped -- if set additional points aren't inserted
bool fDone; // if set, this span to next higher T has been processed
bool fLoop; // set when a cubic loops back to this point
+ bool fMultiple; // set if this is one of mutiple spans with identical t and pt values
+ bool fNear; // set if opposite end point is near but not equal to this one
bool fSmall; // if set, consecutive points are almost equal
bool fTiny; // if set, consecutive points are equal but consecutive ts are not precisely equal
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 0e9e1be..9a8a2cf 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -10,6 +10,29 @@
#include "SkPathWriter.h"
#include "SkTSort.h"
+static void alignMultiples(SkTArray<SkOpContour*, true>* contourList,
+ SkTDArray<SkOpSegment::AlignedSpan>* aligned) {
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ if (contour->hasMultiples()) {
+ contour->alignMultiples(aligned);
+ }
+ }
+}
+
+static void alignCoincidence(SkTArray<SkOpContour*, true>* contourList,
+ const SkTDArray<SkOpSegment::AlignedSpan>& aligned) {
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ int count = aligned.count();
+ for (int index = 0; index < count; ++index) {
+ contour->alignCoincidence(aligned[index]);
+ }
+ }
+}
+
static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, SkOpSegment** currentPtr,
int* indexPtr, int* endIndexPtr, double* bestHit, SkScalar* bestDx,
bool* tryAgain, double* midPtr, bool opp) {
@@ -185,7 +208,7 @@
if (SkOpSegment::UseInnerWinding(maxWinding, winding)) {
maxWinding = winding;
}
- segment->markAndChaseWinding(angle, maxWinding, 0);
+ (void) segment->markAndChaseWinding(angle, maxWinding, 0);
break;
}
}
@@ -204,9 +227,8 @@
}
#endif
-static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourList,
- int* index, int* endIndex, SkPoint* topLeft, bool* unsortable,
- bool* done, bool firstPass) {
+static SkOpSegment* findTopSegment(const SkTArray<SkOpContour*, true>& contourList, int* index,
+ int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) {
SkOpSegment* result;
const SkOpSegment* lastTopStart = NULL;
int lastIndex = -1, lastEndIndex = -1;
@@ -249,28 +271,27 @@
lastEndIndex = *endIndex;
}
} while (!result);
-#if 0
- if (result) {
- *unsortable = false;
- }
-#endif
return result;
}
static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList,
- SkOpSegment** current, int* index, int* endIndex, double* tHit,
- SkScalar* hitDx, bool* tryAgain, bool opp) {
+ SkOpSegment** currentPtr, int* indexPtr, int* endIndexPtr, double* tHit,
+ SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) {
double test = 0.9;
int contourWinding;
do {
- contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx,
- tryAgain, &test, opp);
+ contourWinding = contourRangeCheckY(contourList, currentPtr, indexPtr, endIndexPtr,
+ tHit, hitDx, tryAgain, &test, opp);
if (contourWinding != SK_MinS32 || *tryAgain) {
return contourWinding;
}
+ if (*currentPtr && (*currentPtr)->isVertical()) {
+ *onlyVertical = true;
+ return contourWinding;
+ }
test /= 2;
} while (!approximately_negative(test));
- SkASSERT(0); // should be OK to comment out, but interested when this hits
+ SkASSERT(0); // FIXME: incomplete functionality
return contourWinding;
}
@@ -296,30 +317,34 @@
SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
- int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) {
- SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
+ int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical,
+ bool firstPass) {
+ SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
done, firstPass);
if (!current) {
return NULL;
}
- const int index = *indexPtr;
+ const int startIndex = *indexPtr;
const int endIndex = *endIndexPtr;
if (*firstContour) {
- current->initWinding(index, endIndex, angleIncludeType);
+ current->initWinding(startIndex, endIndex, angleIncludeType);
*firstContour = false;
return current;
}
- int minIndex = SkMin32(index, endIndex);
+ int minIndex = SkMin32(startIndex, endIndex);
int sumWinding = current->windSum(minIndex);
- if (sumWinding != SK_MinS32) {
- return current;
+ if (sumWinding == SK_MinS32) {
+ int index = endIndex;
+ int oIndex = startIndex;
+ do {
+ const SkOpSpan& span = current->span(index);
+ if ((oIndex < index ? span.fFromAngle : span.fToAngle) == NULL) {
+ current->addSimpleAngle(index);
+ }
+ sumWinding = current->computeSum(oIndex, index, angleIncludeType);
+ SkTSwap(index, oIndex);
+ } while (sumWinding == SK_MinS32 && index == startIndex);
}
- SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32);
- const SkOpSpan& span = current->span(endIndex);
- if ((index < endIndex ? span.fFromAngleIndex : span.fToAngleIndex) < 0) {
- current->addSimpleAngle(endIndex);
- }
- sumWinding = current->computeSum(index, endIndex, angleIncludeType);
if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) {
return current;
}
@@ -340,7 +365,10 @@
SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
tryAgain = false;
contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit,
- &hitDx, &tryAgain, false);
+ &hitDx, &tryAgain, onlyVertical, false);
+ if (*onlyVertical) {
+ return current;
+ }
if (tryAgain) {
continue;
}
@@ -348,7 +376,7 @@
break;
}
oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit,
- &hitOppDx, &tryAgain, true);
+ &hitOppDx, &tryAgain, NULL, true);
} while (tryAgain);
current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding,
hitOppDx);
@@ -387,14 +415,15 @@
}
}
-static void checkMultiples(SkTArray<SkOpContour*, true>* contourList) {
- // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
- // instead, look to see if the connecting curve intersected at that same end.
+static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) {
+ bool hasMultiples = false;
int contourCount = (*contourList).count();
for (int cTest = 0; cTest < contourCount; ++cTest) {
SkOpContour* contour = (*contourList)[cTest];
contour->checkMultiples();
+ hasMultiples |= contour->hasMultiples();
}
+ return hasMultiples;
}
// A small interval of a pair of curves may collapse to lines for each, triggering coincidence
@@ -675,12 +704,17 @@
SkOpContour::debugShowWindingValues(contourList);
#endif
fixOtherTIndex(contourList);
- checkEnds(contourList);
- checkMultiples(contourList);
- checkDuplicates(contourList);
- checkTiny(contourList);
- checkSmall(contourList);
- joinCoincidence(contourList);
+ checkEnds(contourList); // check if connecting curve intersected at the same end
+ bool hasM = checkMultiples(contourList); // check if intersections agree on t and point values
+ SkTDArray<SkOpSegment::AlignedSpan> aligned;
+ if (hasM) {
+ alignMultiples(contourList, &aligned); // align pairs of identical points
+ alignCoincidence(contourList, aligned);
+ }
+ checkDuplicates(contourList); // check if spans have the same number on the other end
+ checkTiny(contourList); // if pair have the same end points, mark them as parallel
+ checkSmall(contourList); // a pair of curves with a small span may turn into coincident lines
+ joinCoincidence(contourList); // join curves that connect to a coincident pair
sortSegments(contourList);
if (!calcAngles(contourList)) {
return false;
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index 6a7bb72..0d8cfc4 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 firstPass);
+ bool* unsortable, bool* done, bool* onlyVertical, 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/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 56813b8..9d82dff 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -104,68 +104,7 @@
#if DEBUG_SORT
void SkOpAngle::debugLoop() const {
- const SkOpAngle* first = this;
- const SkOpAngle* next = this;
- do {
- next->debugOne(true);
- SkDebugf("\n");
- next = next->fNext;
- } while (next && next != first);
-}
-
-void SkOpAngle::debugOne(bool functionHeader) const {
-// fSegment->debugValidate();
- const SkOpSpan& mSpan = fSegment->span(SkMin32(fStart, fEnd));
- if (functionHeader) {
- SkDebugf("%s ", __FUNCTION__);
- }
- SkDebugf("[%d", fSegment->debugID());
-#if DEBUG_ANGLE
- SkDebugf("/%d", fID);
-#endif
- SkDebugf("] next=");
- if (fNext) {
- SkDebugf("%d", fNext->fSegment->debugID());
-#if DEBUG_ANGLE
- SkDebugf("/%d", fNext->fID);
-#endif
- } else {
- SkDebugf("?");
- }
- SkDebugf(" sect=%d/%d ", fSectorStart, fSectorEnd);
- SkDebugf(" s=%1.9g [%d] e=%1.9g [%d]", fSegment->span(fStart).fT, fStart,
- fSegment->span(fEnd).fT, fEnd);
- SkDebugf(" sgn=%d windVal=%d", sign(), mSpan.fWindValue);
-
-#if DEBUG_WINDING
- SkDebugf(" windSum=");
- SkPathOpsDebug::WindingPrintf(mSpan.fWindSum);
-#endif
- if (mSpan.fOppValue != 0 || mSpan.fOppSum != SK_MinS32) {
- SkDebugf(" oppVal=%d", mSpan.fOppValue);
-#if DEBUG_WINDING
- SkDebugf(" oppSum=");
- SkPathOpsDebug::WindingPrintf(mSpan.fOppSum);
-#endif
- }
- if (mSpan.fDone) {
- SkDebugf(" done");
- }
- if (unorderable()) {
- SkDebugf(" unorderable");
- }
- if (small()) {
- SkDebugf(" small");
- }
- if (mSpan.fTiny) {
- SkDebugf(" tiny");
- }
- if (fSegment->operand()) {
- SkDebugf(" operand");
- }
- if (fStop) {
- SkDebugf(" stop");
- }
+ dumpLoop();
}
#endif
@@ -174,12 +113,12 @@
SK_ALWAYSBREAK(fSegment == compare->fSegment);
const SkOpSpan& startSpan = fSegment->span(fStart);
const SkOpSpan& oStartSpan = fSegment->span(compare->fStart);
- SK_ALWAYSBREAK(startSpan.fToAngleIndex == oStartSpan.fToAngleIndex);
- SK_ALWAYSBREAK(startSpan.fFromAngleIndex == oStartSpan.fFromAngleIndex);
+ SK_ALWAYSBREAK(startSpan.fToAngle == oStartSpan.fToAngle);
+ SK_ALWAYSBREAK(startSpan.fFromAngle == oStartSpan.fFromAngle);
const SkOpSpan& endSpan = fSegment->span(fEnd);
const SkOpSpan& oEndSpan = fSegment->span(compare->fEnd);
- SK_ALWAYSBREAK(endSpan.fToAngleIndex == oEndSpan.fToAngleIndex);
- SK_ALWAYSBREAK(endSpan.fFromAngleIndex == oEndSpan.fFromAngleIndex);
+ SK_ALWAYSBREAK(endSpan.fToAngle == oEndSpan.fToAngle);
+ SK_ALWAYSBREAK(endSpan.fFromAngle == oEndSpan.fFromAngle);
}
#endif
@@ -189,7 +128,7 @@
const SkOpAngle* next = first;
SkTDArray<const SkOpAngle*>(angles);
do {
- SK_ALWAYSBREAK(next->fSegment->debugContains(next));
+// SK_ALWAYSBREAK(next->fSegment->debugContains(next));
angles.push(next);
next = next->next();
if (next == first) {
@@ -377,22 +316,6 @@
}
#endif
-#if DEBUG_VALIDATE
-bool SkOpSegment::debugContains(const SkOpAngle* angle) const {
- for (int index = 0; index < fAngles.count(); ++index) {
- if (&fAngles[index] == angle) {
- return true;
- }
- }
- for (int index = 0; index < fSingletonAngles.count(); ++index) {
- if (&fSingletonAngles[index] == angle) {
- return true;
- }
- }
- return false;
-}
-#endif
-
#if DEBUG_SWAP_TOP
int SkOpSegment::debugInflections(int tStart, int tEnd) const {
if (fVerb != SkPath::kCubic_Verb) {
@@ -404,6 +327,19 @@
}
#endif
+const SkOpAngle* SkOpSegment::debugLastAngle() const {
+ const SkOpAngle* result = NULL;
+ for (int index = 0; index < count(); ++index) {
+ const SkOpSpan& span = this->span(index);
+ if (span.fToAngle) {
+ SkASSERT(!result);
+ result = span.fToAngle;
+ }
+ }
+ SkASSERT(result);
+ return result;
+}
+
void SkOpSegment::debugReset() {
fTs.reset();
fAngles.reset();
@@ -539,7 +475,7 @@
} else {
SkDebugf("%d", span.fWindSum);
}
- SkDebugf(" windValue=%d\n", span.fWindValue);
+ SkDebugf(" windValue=%d oppValue=%d\n", span.fWindValue, span.fOppValue);
}
#endif
@@ -590,6 +526,7 @@
SK_ALWAYSBREAK(&fTs[i] == &otherSpan.fOther->fTs[otherSpan.fOtherIndex]);
done += span.fDone;
if (last) {
+ SK_ALWAYSBREAK(last->fT != span.fT || last->fOther != span.fOther);
bool tsEqual = last->fT == span.fT;
bool tsPreciselyEqual = precisely_equal(last->fT, span.fT);
SK_ALWAYSBREAK(!tsEqual || tsPreciselyEqual);
@@ -616,8 +553,8 @@
hasLoop |= last->fLoop;
}
SK_ALWAYSBREAK(done == fDoneSpans);
- if (fAngles.count() ) {
- fAngles.begin()->debugValidateLoop();
- }
+// if (fAngles.count() ) {
+// fAngles.begin()->debugValidateLoop();
+// }
#endif
}
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index bb54039..9dc562f 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -51,6 +51,7 @@
#define DEBUG_CONCIDENT 0
#define DEBUG_CROSS 0
#define DEBUG_CUBIC_BINARY_SEARCH 0
+#define DEBUG_DUPLICATES 0
#define DEBUG_FLAT_QUADS 0
#define DEBUG_FLOW 0
#define DEBUG_LIMIT_WIND_SUM 0
@@ -86,6 +87,7 @@
#define DEBUG_CONCIDENT 1
#define DEBUG_CROSS 01
#define DEBUG_CUBIC_BINARY_SEARCH 1
+#define DEBUG_DUPLICATES 1
#define DEBUG_FLAT_QUADS 0
#define DEBUG_FLOW 1
#define DEBUG_LIMIT_WIND_SUM 4
@@ -123,7 +125,7 @@
#define CUBIC_DEBUG_DATA(c) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY
#define QUAD_DEBUG_DATA(q) q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY
#define LINE_DEBUG_DATA(l) l[0].fX, l[0].fY, l[1].fX, l[1].fY
-#define PT_DEBUG_DATA(i, n) i.pt(n).fX, i.pt(n).fY
+#define PT_DEBUG_DATA(i, n) i.pt(n).asSkPoint().fX, i.pt(n).asSkPoint().fY
#ifndef DEBUG_TEST
#define DEBUG_TEST 0
@@ -168,14 +170,18 @@
static void BumpTestName(char* );
#endif
static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name);
- static void DumpAngles(const SkTArray<class SkOpAngle, true>& angles);
- static void DumpAngles(const SkTArray<class SkOpAngle* , true>& angles);
+ static void DumpCoincidence(const SkTArray<class SkOpContour, true>& contours);
+ static void DumpCoincidence(const SkTArray<class SkOpContour* , true>& contours);
static void DumpContours(const SkTArray<class SkOpContour, true>& contours);
static void DumpContours(const SkTArray<class SkOpContour* , true>& contours);
static void DumpContourAngles(const SkTArray<class SkOpContour, true>& contours);
static void DumpContourAngles(const SkTArray<class SkOpContour* , true>& contours);
+ static void DumpContourPt(const SkTArray<class SkOpContour, true>& contours, int id);
+ static void DumpContourPt(const SkTArray<class SkOpContour* , true>& contours, int id);
static void DumpContourPts(const SkTArray<class SkOpContour, true>& contours);
static void DumpContourPts(const SkTArray<class SkOpContour* , true>& contours);
+ static void DumpContourSpan(const SkTArray<class SkOpContour, true>& contours, int id);
+ static void DumpContourSpan(const SkTArray<class SkOpContour* , true>& contours, int id);
static void DumpContourSpans(const SkTArray<class SkOpContour, true>& contours);
static void DumpContourSpans(const SkTArray<class SkOpContour* , true>& contours);
static void DumpSpans(const SkTDArray<struct SkOpSpan *>& );
@@ -183,34 +189,44 @@
};
// shorthand for calling from debugger
-void Dump(const SkTArray<class SkOpAngle, true>& angles);
-void Dump(const SkTArray<class SkOpAngle* , true>& angles);
-void Dump(const SkTArray<class SkOpAngle, true>* angles);
-void Dump(const SkTArray<class SkOpAngle* , true>* angles);
-
void Dump(const SkTArray<class SkOpContour, true>& contours);
void Dump(const SkTArray<class SkOpContour* , true>& contours);
void Dump(const SkTArray<class SkOpContour, true>* contours);
void Dump(const SkTArray<class SkOpContour* , true>* contours);
-void Dump(const SkTDArray<SkOpSpan *>& chaseArray);
-void Dump(const SkTDArray<SkOpSpan *>* chaseArray);
+void Dump(const SkTDArray<SkOpSpan* >& chase);
+void Dump(const SkTDArray<SkOpSpan* >* chase);
void DumpAngles(const SkTArray<class SkOpContour, true>& contours);
void DumpAngles(const SkTArray<class SkOpContour* , true>& contours);
void DumpAngles(const SkTArray<class SkOpContour, true>* contours);
void DumpAngles(const SkTArray<class SkOpContour* , true>* contours);
+void DumpCoin(const SkTArray<class SkOpContour, true>& contours);
+void DumpCoin(const SkTArray<class SkOpContour* , true>& contours);
+void DumpCoin(const SkTArray<class SkOpContour, true>* contours);
+void DumpCoin(const SkTArray<class SkOpContour* , true>* contours);
+
void DumpPts(const SkTArray<class SkOpContour, true>& contours);
void DumpPts(const SkTArray<class SkOpContour* , true>& contours);
void DumpPts(const SkTArray<class SkOpContour, true>* contours);
void DumpPts(const SkTArray<class SkOpContour* , true>* contours);
+void DumpPt(const SkTArray<class SkOpContour, true>& contours, int segmentID);
+void DumpPt(const SkTArray<class SkOpContour* , true>& contours, int segmentID);
+void DumpPt(const SkTArray<class SkOpContour, true>* contours, int segmentID);
+void DumpPt(const SkTArray<class SkOpContour* , true>* contours, int segmentID);
+
void DumpSpans(const SkTArray<class SkOpContour, true>& contours);
void DumpSpans(const SkTArray<class SkOpContour* , true>& contours);
void DumpSpans(const SkTArray<class SkOpContour, true>* contours);
void DumpSpans(const SkTArray<class SkOpContour* , true>* contours);
+void DumpSpan(const SkTArray<class SkOpContour, true>& contours, int segmentID);
+void DumpSpan(const SkTArray<class SkOpContour* , true>& contours, int segmentID);
+void DumpSpan(const SkTArray<class SkOpContour, true>* contours, int segmentID);
+void DumpSpan(const SkTArray<class SkOpContour* , true>* contours, int segmentID);
+
// generates tools/path_sorter.htm and path_visualizer.htm compatible data
void DumpQ(const struct SkDQuad& quad1, const struct SkDQuad& quad2, int testNo);
diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp
index 7587fda..6229619 100644
--- a/src/pathops/SkPathOpsLine.cpp
+++ b/src/pathops/SkPathOpsLine.cpp
@@ -63,7 +63,7 @@
return -1;
}
-double SkDLine::nearPoint(const SkDPoint& xy) const {
+double SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const {
if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
|| !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
return -1;
@@ -86,6 +86,9 @@
if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
return -1;
}
+ if (unequal) {
+ *unequal = (float) largest != (float) (largest + dist);
+ }
t = SkPinT(t);
SkASSERT(between(0, t, 1));
return t;
diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h
index e4ed0c9..74eb615 100644
--- a/src/pathops/SkPathOpsLine.h
+++ b/src/pathops/SkPathOpsLine.h
@@ -30,7 +30,7 @@
static double ExactPointH(const SkDPoint& xy, double left, double right, double y);
static double ExactPointV(const SkDPoint& xy, double top, double bottom, double x);
double isLeft(const SkDPoint& pt) const;
- double nearPoint(const SkDPoint& xy) const;
+ double nearPoint(const SkDPoint& xy, bool* unequal) const;
bool nearRay(const SkDPoint& xy) const;
static double NearPointH(const SkDPoint& xy, double left, double right, double y);
static double NearPointV(const SkDPoint& xy, double top, double bottom, double x);
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 5af4753..4c6923a 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -41,6 +41,9 @@
}
// find first angle, initialize winding to computed fWindSum
const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
+ if (!angle) {
+ continue;
+ }
const SkOpAngle* firstAngle = angle;
SkDEBUGCODE(bool loop = false);
int winding;
@@ -70,6 +73,7 @@
*tIndex = start;
*endIndex = end;
}
+ // OPTIMIZATION: should this also add to the chase?
(void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
oppSumWinding, angle);
}
@@ -125,9 +129,10 @@
do {
int index, endIndex;
bool topDone;
+ bool onlyVertical = false;
lastTopLeft = topLeft;
SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
- &index, &endIndex, &topLeft, &topUnsortable, &topDone, firstPass);
+ &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
if (!current) {
if ((!topUnsortable || firstPass) && !topDone) {
SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
@@ -142,29 +147,33 @@
continue;
}
break;
+ } else if (onlyVertical) {
+ break;
}
firstPass = !topUnsortable || lastTopLeft != topLeft;
- SkTDArray<SkOpSpan*> chaseArray;
+ SkTDArray<SkOpSpan*> chase;
do {
if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
do {
if (!unsortable && current->done()) {
- if (simple->isEmpty()) {
- simple->init();
- }
break;
}
SkASSERT(unsortable || !current->done());
int nextStart = index;
int nextEnd = endIndex;
- SkOpSegment* next = current->findNextOp(&chaseArray, &nextStart, &nextEnd,
+ SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
&unsortable, op, xorMask, xorOpMask);
if (!next) {
if (!unsortable && simple->hasMove()
&& current->verb() != SkPath::kLine_Verb
&& !simple->isClosed()) {
current->addCurveTo(index, endIndex, simple, true);
- SkASSERT(simple->isClosed());
+ #if DEBUG_ACTIVE_SPANS
+ if (!simple->isClosed()) {
+ DebugShowActiveSpans(contourList);
+ }
+ #endif
+// SkASSERT(simple->isClosed());
}
break;
}
@@ -195,11 +204,16 @@
SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
if (last && !last->fChased && !last->fLoop) {
last->fChased = true;
- SkASSERT(!SkPathOpsDebug::ChaseContains(chaseArray, last));
- *chaseArray.append() = 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->span(last->fOtherIndex).fOther->debugID(), last->fWindSum,
+ last->fSmall);
+#endif
}
}
- current = findChaseOp(chaseArray, &index, &endIndex);
+ current = findChaseOp(chase, &index, &endIndex);
#if DEBUG_ACTIVE_SPANS
DebugShowActiveSpans(contourList);
#endif
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index 336fb62..5c2e3a5 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -148,14 +148,12 @@
return AlmostBequalUlps((double) largest, largest + dist); // is dist within ULPS tolerance?
}
-#ifdef SK_DEBUG
static bool RoughlyEqual(const SkPoint& a, const SkPoint& b) {
if (approximately_equal(a.fX, b.fX) && approximately_equal(a.fY, b.fY)) {
return true;
}
return RoughlyEqualUlps(a.fX, b.fX) && RoughlyEqualUlps(a.fY, b.fY);
}
-#endif
bool approximatelyPEqual(const SkDPoint& a) const {
if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) {
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 0917b69..57090ac 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -19,9 +19,10 @@
do {
int index, endIndex;
bool topDone;
+ bool onlyVertical = false;
lastTopLeft = topLeft;
SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
- &index, &endIndex, &topLeft, &topUnsortable, &topDone, firstPass);
+ &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
if (!current) {
if ((!topUnsortable || firstPass) && !topDone) {
SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
@@ -29,22 +30,21 @@
continue;
}
break;
+ } else if (onlyVertical) {
+ break;
}
firstPass = !topUnsortable || lastTopLeft != topLeft;
- SkTDArray<SkOpSpan*> chaseArray;
+ SkTDArray<SkOpSpan*> chase;
do {
if (current->activeWinding(index, endIndex)) {
do {
if (!unsortable && current->done()) {
- if (simple->isEmpty()) {
- simple->init();
- break;
- }
+ break;
}
SkASSERT(unsortable || !current->done());
int nextStart = index;
int nextEnd = endIndex;
- SkOpSegment* next = current->findNextWinding(&chaseArray, &nextStart, &nextEnd,
+ SkOpSegment* next = current->findNextWinding(&chase, &nextStart, &nextEnd,
&unsortable);
if (!next) {
if (!unsortable && simple->hasMove()
@@ -67,7 +67,7 @@
} while (!simple->isClosed() && (!unsortable
|| !current->done(SkMin32(index, endIndex))));
if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
- SkASSERT(unsortable || simple->isEmpty());
+// SkASSERT(unsortable || simple->isEmpty());
int min = SkMin32(index, endIndex);
if (!current->done(min)) {
current->addCurveTo(index, endIndex, simple, true);
@@ -79,13 +79,17 @@
SkOpSpan* last = current->markAndChaseDoneUnary(index, endIndex);
if (last && !last->fChased && !last->fLoop) {
last->fChased = true;
- SkASSERT(!SkPathOpsDebug::ChaseContains(chaseArray, last));
+ SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
// assert that last isn't already in array
- *chaseArray.append() = last;
+ *chase.append() = last;
+#if DEBUG_WINDING
+ SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
+ last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum,
+ last->fSmall);
+#endif
}
}
- SkTDArray<SkOpSpan *>* chaseArrayPtr = &chaseArray;
- current = FindChase(chaseArrayPtr, &index, &endIndex);
+ current = FindChase(&chase, &index, &endIndex);
#if DEBUG_ACTIVE_SPANS
DebugShowActiveSpans(contourList);
#endif
diff --git a/src/pathops/SkPathOpsTriangle.cpp b/src/pathops/SkPathOpsTriangle.cpp
index 7db4831..77845e0 100644
--- a/src/pathops/SkPathOpsTriangle.cpp
+++ b/src/pathops/SkPathOpsTriangle.cpp
@@ -23,7 +23,7 @@
double dot12 = v1.dot(v2);
// original code doesn't handle degenerate input; isn't symmetric with inclusion of corner pts;
-// introduces necessary error with divide; doesn't short circuit on early answer
+// introduces error with divide; doesn't short circuit on early answer
#if 0
// Compute barycentric coordinates
double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 4f8bd15..9662784 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -91,6 +91,11 @@
const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16;
const double ROUGH_EPSILON = FLT_EPSILON * 64;
const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256;
+const double WAY_ROUGH_EPSILON = FLT_EPSILON * 2048;
+
+inline bool zero_or_one(double x) {
+ return x == 0 || x == 1;
+}
inline bool approximately_zero(double x) {
return fabs(x) < FLT_EPSILON;
@@ -297,12 +302,16 @@
return (a - b) * (c - b) <= 0;
}
+inline bool roughly_equal(double x, double y) {
+ return fabs(x - y) < ROUGH_EPSILON;
+}
+
inline bool more_roughly_equal(double x, double y) {
return fabs(x - y) < MORE_ROUGH_EPSILON;
}
-inline bool roughly_equal(double x, double y) {
- return fabs(x - y) < ROUGH_EPSILON;
+inline bool way_roughly_equal(double x, double y) {
+ return fabs(x - y) < WAY_ROUGH_EPSILON;
}
struct SkDPoint;