path ops work in progress
path ops work in progress
BUG=
Review URL: https://codereview.chromium.org/21359002
git-svn-id: http://skia.googlecode.com/svn/trunk@11291 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/gyp/core.gypi b/gyp/core.gypi
index 6c00a56..3fdca92 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -365,7 +365,6 @@
'<(skia_src_path)/pathops/SkPathOpsPoint.h',
'<(skia_src_path)/pathops/SkPathOpsQuad.h',
'<(skia_src_path)/pathops/SkPathOpsRect.h',
- '<(skia_src_path)/pathops/SkPathOpsSpan.h',
'<(skia_src_path)/pathops/SkPathOpsTriangle.h',
'<(skia_src_path)/pathops/SkPathOpsTypes.h',
'<(skia_src_path)/pathops/SkPathWriter.h',
diff --git a/gyp/pathops.gypi b/gyp/pathops.gypi
index 5daa0fd..3bb163e 100644
--- a/gyp/pathops.gypi
+++ b/gyp/pathops.gypi
@@ -52,7 +52,6 @@
'../src/pathops/SkPathOpsPoint.h',
'../src/pathops/SkPathOpsQuad.h',
'../src/pathops/SkPathOpsRect.h',
- '../src/pathops/SkPathOpsSpan.h',
'../src/pathops/SkPathOpsTriangle.h',
'../src/pathops/SkPathOpsTypes.h',
'../src/pathops/SkPathWriter.h',
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp
index 0d65446..0507984 100644
--- a/src/pathops/SkAddIntersections.cpp
+++ b/src/pathops/SkAddIntersections.cpp
@@ -176,9 +176,10 @@
bool AddIntersectTs(SkOpContour* test, SkOpContour* next) {
if (test != next) {
- if (test->bounds().fBottom < next->bounds().fTop) {
+ if (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) {
return false;
}
+ // OPTIMIZATION: outset contour bounds a smidgen instead?
if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
return true;
}
@@ -373,12 +374,22 @@
continue;
}
}
+ if (pts >= 2) {
+ for (int pt = 0; pt < pts - 1; ++pt) {
+ const SkDPoint& point = ts.pt(pt);
+ const SkDPoint& next = ts.pt(pt + 1);
+ if (wt.isNear(ts[swap][pt], ts[swap][pt + 1], point, next)
+ && wn.isNear(ts[!swap][pt], ts[!swap][pt + 1], point, next)) {
+ wt.addPartialCoincident(wn, ts, pt, swap);
+ }
+ }
+ }
for (int pt = 0; pt < pts; ++pt) {
SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
SkPoint point = ts.pt(pt).asSkPoint();
- int testTAt = wt.addT(wn, point, ts[swap][pt]);
- int nextTAt = wn.addT(wt, point, ts[!swap][pt]);
+ int testTAt = wt.addT(wn, point, ts[swap][pt], swap && ts.isNear(pt));
+ int nextTAt = wn.addT(wt, point, ts[!swap][pt], !swap && ts.isNear(pt));
wt.addOtherT(testTAt, ts[!swap][pt], nextTAt);
wn.addOtherT(nextTAt, ts[swap][pt], testTAt);
}
@@ -405,7 +416,7 @@
SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1);
SkPoint point = ts.pt(0).asSkPoint();
int testTAt = wt.addSelfT(wt, point, ts[0][0]);
- int nextTAt = wt.addT(wt, point, ts[1][0]);
+ int nextTAt = wt.addT(wt, point, ts[1][0], ts.isNear(0));
wt.addOtherT(testTAt, ts[1][0], nextTAt);
wt.addOtherT(nextTAt, ts[0][0], testTAt);
} while (wt.advance());
@@ -425,6 +436,6 @@
}
for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
SkOpContour* contour = (*contourList)[cIndex];
- contour->findTooCloseToCall();
+ contour->calcPartialCoincidentWinding();
}
}
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index 19e7340..63d434f 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -108,11 +108,13 @@
SkDebugf("%.*s %s t1=(%1.9g,%1.9g) t2=(%1.9g,%1.9g)", i.depth()*2, tab,
__FUNCTION__, t1Start, t1, t2Start, t2);
SkIntersections xlocals;
+ xlocals.allowNear(false);
intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, xlocals);
SkDebugf(" xlocals.fUsed=%d\n", xlocals.used());
}
#endif
SkIntersections locals;
+ locals.allowNear(false);
intersectWithOrder(s1.fQuad, o1, s2.fQuad, o2, locals);
int tCount = locals.used();
for (int tIdx = 0; tIdx < tCount; ++tIdx) {
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index a891abe..0abb75b 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -107,6 +107,9 @@
int intersect() {
addExactEndPoints();
+ if (fAllowNear) {
+ addNearEndPoints();
+ }
double rootVals[3];
int roots = intersectRay(rootVals);
for (int index = 0; index < roots; ++index) {
@@ -122,9 +125,6 @@
fIntersections->insert(cubicT, lineT, pt);
}
}
- if (fAllowNear) {
- addNearEndPoints();
- }
return fIntersections->used();
}
@@ -137,6 +137,9 @@
int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
addExactHorizontalEndPoints(left, right, axisIntercept);
+ if (fAllowNear) {
+ addNearHorizontalEndPoints(left, right, axisIntercept);
+ }
double rootVals[3];
int roots = horizontalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
@@ -147,9 +150,6 @@
fIntersections->insert(cubicT, lineT, pt);
}
}
- if (fAllowNear) {
- addNearHorizontalEndPoints(left, right, axisIntercept);
- }
if (flipped) {
fIntersections->flip();
}
@@ -165,6 +165,9 @@
int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
addExactVerticalEndPoints(top, bottom, axisIntercept);
+ if (fAllowNear) {
+ addNearVerticalEndPoints(top, bottom, axisIntercept);
+ }
double rootVals[3];
int roots = verticalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
@@ -175,9 +178,6 @@
fIntersections->insert(cubicT, lineT, pt);
}
}
- if (fAllowNear) {
- addNearVerticalEndPoints(top, bottom, axisIntercept);
- }
if (flipped) {
fIntersections->flip();
}
@@ -287,6 +287,17 @@
} else if (ptSet == kPointUninitialized) {
*pt = fCubic.ptAtT(cT);
}
+ SkPoint gridPt = pt->asSkPoint();
+ if (gridPt == fLine[0].asSkPoint()) {
+ *lineT = 0;
+ } else if (gridPt == fLine[1].asSkPoint()) {
+ *lineT = 1;
+ }
+ if (gridPt == fCubic[0].asSkPoint() && approximately_equal(*cubicT, 0)) {
+ *cubicT = 0;
+ } else if (gridPt == fCubic[3].asSkPoint() && approximately_equal(*cubicT, 1)) {
+ *cubicT = 1;
+ }
return true;
}
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index 46118429..4b818dc 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -35,21 +35,18 @@
}
int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
- double axLen = a[1].fX - a[0].fX;
- double ayLen = a[1].fY - a[0].fY;
- double bxLen = b[1].fX - b[0].fX;
- double byLen = b[1].fY - b[0].fY;
+ SkDVector aLen = a[1] - a[0];
+ SkDVector bLen = b[1] - b[0];
/* Slopes match when denom goes to zero:
axLen / ayLen == bxLen / byLen
(ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
byLen * axLen == ayLen * bxLen
byLen * axLen - ayLen * bxLen == 0 ( == denom )
*/
- double denom = byLen * axLen - ayLen * bxLen;
- double ab0y = a[0].fY - b[0].fY;
- double ab0x = a[0].fX - b[0].fX;
- double numerA = ab0y * bxLen - byLen * ab0x;
- double numerB = ab0y * axLen - ayLen * ab0x;
+ double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX;
+ SkDVector ab0 = a[0] - b[0];
+ double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX;
+ double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX;
numerA /= denom;
numerB /= denom;
int used;
@@ -63,8 +60,8 @@
axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
axLen * ay - ax * ayLen == axLen * by - bx * ayLen
*/
- if (!AlmostEqualUlps(axLen * a[0].fY - ayLen * a[0].fX,
- axLen * b[0].fY - ayLen * b[0].fX)) {
+ if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX,
+ aLen.fX * b[0].fY - aLen.fY * b[0].fX)) {
return fUsed = 0;
}
// there's no great answer for intersection points for coincident rays, but return something
@@ -106,8 +103,8 @@
double ayBxLen = ayLen * bxLen;
// detect parallel lines the same way here and in SkOpAngle operator <
// so that non-parallel means they are also sortable
- bool parallel = AlmostEqualUlps(axByLen, ayBxLen);
- if (!parallel) {
+ bool unparallel = NotAlmostEqualUlps(axByLen, ayBxLen);
+ if (unparallel) {
double ab0y = a[0].fY - b[0].fY;
double ab0x = a[0].fX - b[0].fX;
double numerA = ab0y * bxLen - byLen * ab0x;
@@ -119,7 +116,7 @@
computePoints(a, 1);
}
}
- if (fAllowNear || parallel) {
+ if (fAllowNear || !unparallel) {
for (int iA = 0; iA < 2; ++iA) {
if ((t = b.nearPoint(a[iA])) >= 0) {
insert(iA, t, a[iA]);
@@ -131,6 +128,17 @@
}
}
}
+ while (fUsed > 2) {
+ removeOne(1);
+ }
+ if (fUsed == 2 && unparallel) {
+ bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1;
+ bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1;
+ if (!startMatch && !endMatch) {
+ SkASSERT(startMatch || endMatch);
+ removeOne(endMatch);
+ }
+ }
return fUsed;
}
diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp
index e10fb3f..5869d7d 100644
--- a/src/pathops/SkDQuadIntersection.cpp
+++ b/src/pathops/SkDQuadIntersection.cpp
@@ -391,14 +391,22 @@
int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
// if the quads share an end point, check to see if they overlap
-
for (int i1 = 0; i1 < 3; i1 += 2) {
for (int i2 = 0; i2 < 3; i2 += 2) {
- if (q1[i1].approximatelyEqualHalf(q2[i2])) {
+ if (q1[i1] == q2[i2]) {
insert(i1 >> 1, i2 >> 1, q1[i1]);
}
}
}
+ if (fAllowNear || true) { // FIXME ? cubic/cubic intersection fails without (cubicOp67u)
+ for (int i1 = 0; i1 < 3; i1 += 2) {
+ for (int i2 = 0; i2 < 3; i2 += 2) {
+ if (q1[i1] != q2[i2] && q1[i1].approximatelyEqualHalf(q2[i2])) {
+ insertNear(i1 >> 1, i2 >> 1, q1[i1]);
+ }
+ }
+ }
+ }
SkASSERT(fUsed < 3);
if (only_end_pts_in_common(q1, q2)) {
return fUsed;
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index 58b3060..b335c5a 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -137,6 +137,9 @@
int intersect() {
addExactEndPoints();
+ if (fAllowNear) {
+ addNearEndPoints();
+ }
double rootVals[2];
int roots = intersectRay(rootVals);
for (int index = 0; index < roots; ++index) {
@@ -147,9 +150,6 @@
fIntersections->insert(quadT, lineT, pt);
}
}
- if (fAllowNear) {
- addNearEndPoints();
- }
return fIntersections->used();
}
@@ -165,6 +165,9 @@
int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) {
addExactHorizontalEndPoints(left, right, axisIntercept);
+ if (fAllowNear) {
+ addNearHorizontalEndPoints(left, right, axisIntercept);
+ }
double rootVals[2];
int roots = horizontalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
@@ -175,9 +178,6 @@
fIntersections->insert(quadT, lineT, pt);
}
}
- if (fAllowNear) {
- addNearHorizontalEndPoints(left, right, axisIntercept);
- }
if (flipped) {
fIntersections->flip();
}
@@ -196,6 +196,9 @@
int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) {
addExactVerticalEndPoints(top, bottom, axisIntercept);
+ if (fAllowNear) {
+ addNearVerticalEndPoints(top, bottom, axisIntercept);
+ }
double rootVals[2];
int roots = verticalIntersect(axisIntercept, rootVals);
for (int index = 0; index < roots; ++index) {
@@ -206,9 +209,6 @@
fIntersections->insert(quadT, lineT, pt);
}
}
- if (fAllowNear) {
- addNearVerticalEndPoints(top, bottom, axisIntercept);
- }
if (flipped) {
fIntersections->flip();
}
@@ -324,6 +324,17 @@
} else if (ptSet == kPointUninitialized) {
*pt = fQuad.ptAtT(qT);
}
+ SkPoint gridPt = pt->asSkPoint();
+ if (gridPt == fLine[0].asSkPoint()) {
+ *lineT = 0;
+ } else if (gridPt == fLine[1].asSkPoint()) {
+ *lineT = 1;
+ }
+ if (gridPt == fQuad[0].asSkPoint()) {
+ *quadT = 0;
+ } else if (gridPt == fQuad[2].asSkPoint()) {
+ *quadT = 1;
+ }
return true;
}
diff --git a/src/pathops/SkIntersectionHelper.h b/src/pathops/SkIntersectionHelper.h
index 5d8ebcd..af246b7 100644
--- a/src/pathops/SkIntersectionHelper.h
+++ b/src/pathops/SkIntersectionHelper.h
@@ -27,24 +27,24 @@
fContour->addOtherT(fIndex, index, otherT, otherIndex);
}
+ void addPartialCoincident(SkIntersectionHelper& other, const SkIntersections& ts, int index,
+ bool swap) {
+ fContour->addPartialCoincident(fIndex, other.fContour, other.fIndex, ts, index, swap);
+ }
+
// Avoid collapsing t values that are close to the same since
// we walk ts to describe consecutive intersections. Since a pair of ts can
// be nearly equal, any problems caused by this should be taken care
// of later.
// On the edge or out of range values are negative; add 2 to get end
- int addT(const SkIntersectionHelper& other, const SkPoint& pt, double newT) {
- return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT);
+ int addT(const SkIntersectionHelper& other, const SkPoint& pt, double newT, bool isNear) {
+ return fContour->addT(fIndex, other.fContour, other.fIndex, pt, newT, isNear);
}
int addSelfT(const SkIntersectionHelper& other, const SkPoint& pt, double newT) {
return fContour->addSelfT(fIndex, other.fContour, other.fIndex, pt, newT);
}
- int addUnsortableT(const SkIntersectionHelper& other, bool start, const SkPoint& pt,
- double newT) {
- return fContour->addUnsortableT(fIndex, other.fContour, other.fIndex, start, pt, newT);
- }
-
bool advance() {
return ++fIndex < fLast;
}
@@ -72,6 +72,14 @@
&& next.fIndex == fLast - 1;
}
+ bool isNear(double t1, double t2, const SkDPoint& pt1, const SkDPoint& pt2) const {
+ const SkOpSegment& segment = fContour->segments()[fIndex];
+ double mid = (t1 + t2) / 2;
+ SkDPoint midPtByT = segment.dPtAtT(mid);
+ SkDPoint midPtByAvg = SkDPoint::Mid(pt1, pt2);
+ return midPtByT.approximatelyEqualHalf(midPtByAvg);
+ }
+
SkScalar left() const {
return bounds().fLeft;
}
diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp
index 242c67b..3a5e24f 100644
--- a/src/pathops/SkIntersections.cpp
+++ b/src/pathops/SkIntersections.cpp
@@ -93,8 +93,10 @@
memmove(&fPt[index + 1], &fPt[index], sizeof(fPt[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);
- fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1);
- fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1);
+ int clearMask = ~((1 << index) - 1);
+ fIsCoincident[0] += fIsCoincident[0] & clearMask;
+ fIsCoincident[1] += fIsCoincident[1] & clearMask;
+ fIsNear += fIsNear & clearMask;
}
fPt[index] = pt;
fT[0][index] = one;
@@ -103,6 +105,14 @@
return index;
}
+void SkIntersections::insertNear(double one, double two, const SkDPoint& pt) {
+ int index = insert(one, two, pt);
+ if (index < 0) {
+ return;
+ }
+ fIsNear |= 1 << index;
+}
+
void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) {
int index = insertSwap(one, two, pt);
int bit = 1 << index;
@@ -158,6 +168,7 @@
fIsCoincident[0] -= ((fIsCoincident[0] >> 1) & ~((1 << index) - 1)) + coBit;
SkASSERT(!(coBit ^ (fIsCoincident[1] & (1 << index))));
fIsCoincident[1] -= ((fIsCoincident[1] >> 1) & ~((1 << index) - 1)) + coBit;
+ fIsNear -= ((fIsNear >> 1) & ~((1 << index) - 1)) + (fIsNear & (1 << index));
}
void SkIntersections::swapPts() {
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index 26a1d1a..389098d 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -23,6 +23,7 @@
sk_bzero(fPt, sizeof(fPt));
sk_bzero(fT, sizeof(fT));
sk_bzero(fIsCoincident, sizeof(fIsCoincident));
+ sk_bzero(&fIsNear, sizeof(fIsNear));
reset();
}
@@ -40,6 +41,7 @@
memcpy(fPt, i.fPt, sizeof(fPt));
memcpy(fT, i.fT, sizeof(fT));
memcpy(fIsCoincident, i.fIsCoincident, sizeof(fIsCoincident));
+ memcpy(&fIsNear, &i.fIsNear, sizeof(fIsNear));
fUsed = i.fUsed;
fSwap = i.fSwap;
SkDEBUGCODE(fDepth = i.fDepth);
@@ -109,6 +111,10 @@
return (fIsCoincident[0] & 1 << index) != 0;
}
+ bool isNear(int index) {
+ return (fIsNear & 1 << index) != 0;
+ }
+
int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y,
bool flipped) {
SkDLine line;
@@ -206,6 +212,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);
// start if index == 0 : end if index == 1
void insertCoincident(double one, double two, const SkDPoint& pt);
int intersect(const SkDLine&, const SkDLine&);
@@ -243,9 +250,10 @@
// used by addCoincident to remove ordinary intersections in range
// void remove(double one, double two, const SkDPoint& startPt, const SkDPoint& endPt);
- SkDPoint fPt[9];
+ SkDPoint fPt[9]; // FIXME: since scans store points as SkPoint, this should also
double fT[2][9];
- uint16_t fIsCoincident[2]; // bit arrays, one bit set for each coincident T
+ uint16_t fIsCoincident[2]; // bit set for each curve's coincident T
+ uint16_t fIsNear; // bit set for each T if 2nd curve's point is near but not equal to 1st
unsigned char fUsed;
bool fAllowNear;
bool fSwap;
diff --git a/src/pathops/SkLineParameters.h b/src/pathops/SkLineParameters.h
index 8824e54..9cbd852 100644
--- a/src/pathops/SkLineParameters.h
+++ b/src/pathops/SkLineParameters.h
@@ -39,6 +39,14 @@
c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
}
+ double cubicPart(const SkDCubic& part) {
+ cubicEndPoints(part);
+ if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) {
+ return pointDistance(part[3]);
+ }
+ return pointDistance(part[2]);
+ }
+
void lineEndPoints(const SkDLine& pts) {
a = pts[0].fY - pts[1].fY;
b = pts[1].fX - pts[0].fX;
@@ -58,6 +66,11 @@
c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
}
+ double quadPart(const SkDQuad& part) {
+ quadEndPoints(part);
+ return pointDistance(part[2]);
+ }
+
double normalSquared() const {
return a * a + b * b;
}
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index 0dd0d65..c1e2eae 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -120,13 +120,15 @@
return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger);
}
}
+ SkPath::Verb verb = fSegment->verb();
+ SkPath::Verb rVerb = rh.fSegment->verb();
if (y_ry != 0) { // if they aren't coincident, look for a stable cross product
// at this point, y's are the same sign, neither is zero
// and x's are the same sign, or one (or both) is zero
double x_ry = x * ry;
double rx_y = rx * y;
if (!fComputed && !rh.fComputed) {
- if (!AlmostEqualUlps(x_ry, rx_y)) {
+ if (!SkDLine::NearRay(x, y, rx, ry) && x_ry != rx_y) {
return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y);
}
} else {
@@ -140,9 +142,9 @@
}
}
}
- if (fSide * rh.fSide == 0) {
- SkASSERT(fSide + rh.fSide != 0); // hitting this assert means coincidence was undetected
- return COMPARE_RESULT("9 fSide * rh.fSide == 0 ...", fSide < rh.fSide);
+ if (fSide2 * rh.fSide2 == 0) {
+// SkASSERT(fSide2 + rh.fSide2 != 0); // hitting this assert means coincidence was undetected
+ return COMPARE_RESULT("9a fSide2 * rh.fSide2 == 0 ...", fSide2 < rh.fSide2);
}
// at this point, the initial tangent line is nearly coincident
// see if edges curl away from each other
@@ -153,8 +155,6 @@
// even with no solution, return a stable sort
return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh);
}
- SkPath::Verb verb = fSegment->verb();
- SkPath::Verb rVerb = rh.fSegment->verb();
if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x))
|| (rVerb == SkPath::kLine_Verb
&& approximately_zero(ry) && approximately_zero(rx))) {
@@ -173,8 +173,8 @@
// end of the shorter tangent to midway between the end points
// through both curves and use the resulting angle to sort
// FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
- double len = fTangent1.normalSquared();
- double rlen = rh.fTangent1.normalSquared();
+ double len = fTangentPart.normalSquared();
+ double rlen = rh.fTangentPart.normalSquared();
SkDLine ray;
SkIntersections i, ri;
int roots, rroots;
@@ -269,62 +269,53 @@
}
void SkOpAngle::setSpans() {
- fUnorderable = false;
- if (fSegment->verb() == SkPath::kLine_Verb) {
- fUnsortable = false;
- } else {
- // if start-1 exists and is tiny, then start pt may have moved
- int smaller = SkMin32(fStart, fEnd);
- int tinyCheck = smaller;
- while (tinyCheck > 0 && fSegment->isTiny(tinyCheck - 1)) {
- --tinyCheck;
- }
- if ((fUnsortable = smaller > 0 && tinyCheck == 0)) {
- return;
- }
- int larger = SkMax32(fStart, fEnd);
- tinyCheck = larger;
- int max = fSegment->count() - 1;
- while (tinyCheck < max && fSegment->isTiny(tinyCheck + 1)) {
- ++tinyCheck;
- }
- if ((fUnsortable = larger < max && tinyCheck == max)) {
- return;
- }
+ fUnorderable = fSegment->isTiny(this);
+ fLastMarked = NULL;
+ fUnsortable = false;
+ const SkPoint* pts = fSegment->pts();
+ if (fSegment->verb() != SkPath::kLine_Verb) {
+ fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart);
+ fSegment->subDivide(fStart, fStart < fEnd ? fSegment->count() - 1 : 0, &fCurveHalf);
}
- fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart);
// FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try
// rounding the curve part to float precision here
// fCurvePart.round(fSegment->verb());
switch (fSegment->verb()) {
case SkPath::kLine_Verb: {
- // OPTIMIZATION: for pure line compares, we never need fTangent1.c
- fTangent1.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart));
+ SkASSERT(fStart != fEnd);
+ fCurvePart[0].set(pts[fStart > fEnd]);
+ fCurvePart[1].set(pts[fStart < fEnd]);
+ fComputed = false;
+ // OPTIMIZATION: for pure line compares, we never need fTangentPart.c
+ fTangentPart.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart));
fSide = 0;
+ fSide2 = 0;
} break;
case SkPath::kQuad_Verb: {
+ fSide2 = -fTangentHalf.quadPart(*SkTCast<SkDQuad*>(&fCurveHalf));
SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart);
- fTangent1.quadEndPoints(quad);
- fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
+ fTangentPart.quadEndPoints(quad);
+ fSide = -fTangentPart.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
if (fComputed && dx() > 0 && approximately_zero(dy())) {
SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
int last = fSegment->count() - 1;
fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
SkLineParameters origTan;
origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve));
- if ((fUnorderable = origTan.dx() <= 0
- || (dy() != origTan.dy() && dy() * origTan.dy() <= 0))) { // signs match?
+ if (origTan.dx() <= 0
+ || (dy() != origTan.dy() && dy() * origTan.dy() <= 0)) { // signs match?
+ fUnorderable = true;
return;
}
}
} break;
case SkPath::kCubic_Verb: {
- fTangent1.cubicEndPoints(fCurvePart);
+ double startT = fSegment->t(fStart);
+ fSide2 = -fTangentHalf.cubicPart(fCurveHalf);
+ fTangentPart.cubicEndPoints(fCurvePart);
double testTs[4];
// OPTIMIZATION: keep inflections precomputed with cubic segment?
- const SkPoint* pts = fSegment->pts();
int testCount = SkDCubic::FindInflections(pts, testTs);
- double startT = fSegment->t(fStart);
double endT = fSegment->t(fEnd);
double limitT = endT;
int index;
@@ -351,36 +342,28 @@
}
// OPTIMIZE: could avoid call for t == startT, endT
SkDPoint pt = dcubic_xy_at_t(pts, testT);
- double testSide = fTangent1.pointDistance(pt);
+ double testSide = fTangentPart.pointDistance(pt);
if (fabs(bestSide) < fabs(testSide)) {
bestSide = testSide;
}
}
fSide = -bestSide; // compare sign only
+ SkASSERT(fSide == 0 || fSide2 != 0);
if (fComputed && dx() > 0 && approximately_zero(dy())) {
SkDCubic origCurve; // can't use segment's curve in place since it may be flipped
int last = fSegment->count() - 1;
fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve);
- SkLineParameters origTan;
- origTan.cubicEndPoints(origCurve);
- if ((fUnorderable = origTan.dx() <= 0)) {
- fUnsortable = fSegment->isTiny(this);
- return;
- }
- // if one is < 0 and the other is >= 0
- if ((fUnorderable = (dy() < 0) ^ (origTan.dy() < 0))) {
- fUnsortable = fSegment->isTiny(this);
- return;
- }
SkDCubicPair split = origCurve.chopAt(startT);
SkLineParameters splitTan;
splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first());
- if ((fUnorderable = splitTan.dx() <= 0)) {
+ if (splitTan.dx() <= 0) {
+ fUnorderable = true;
fUnsortable = fSegment->isTiny(this);
return;
}
// if one is < 0 and the other is >= 0
- if ((fUnorderable = (dy() < 0) ^ (splitTan.dy() < 0))) {
+ if (dy() * splitTan.dy() < 0) {
+ fUnorderable = true;
fUnsortable = fSegment->isTiny(this);
return;
}
@@ -392,39 +375,42 @@
if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) {
return;
}
- SkASSERT(fStart != fEnd);
- int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro?
- for (int index = fStart; index != fEnd; index += step) {
-#if 1
- const SkOpSpan& thisSpan = fSegment->span(index);
- const SkOpSpan& nextSpan = fSegment->span(index + step);
- if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) {
- continue;
- }
- fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd;
-#if DEBUG_UNSORTABLE
- if (fUnsortable) {
- SkPoint iPt = fSegment->xyAtT(index);
- SkPoint ePt = fSegment->xyAtT(index + step);
- SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
- index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
- }
-#endif
+ if (fSegment->verb() == SkPath::kLine_Verb) {
return;
-#else
- if ((*fSpans)[index].fUnsortableStart) {
- fUnsortable = true;
- return;
- }
-#endif
}
-#if 1
+ SkASSERT(fStart != fEnd);
+ int smaller = SkMin32(fStart, fEnd);
+ int larger = SkMax32(fStart, fEnd);
+ while (smaller < larger && fSegment->span(smaller).fTiny) {
+ ++smaller;
+ }
+ if (precisely_equal(fSegment->span(smaller).fT, fSegment->span(larger).fT)) {
+ #if DEBUG_UNSORTABLE
+ SkPoint iPt = fSegment->xyAtT(fStart);
+ SkPoint ePt = fSegment->xyAtT(fEnd);
+ SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
+ fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
+ #endif
+ fUnsortable = true;
+ return;
+ }
+ fUnsortable = fStart < fEnd ? fSegment->span(smaller).fUnsortableStart
+ : fSegment->span(larger).fUnsortableEnd;
#if DEBUG_UNSORTABLE
- SkPoint iPt = fSegment->xyAtT(fStart);
- SkPoint ePt = fSegment->xyAtT(fEnd);
- SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
- fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
+ if (fUnsortable) {
+ SkPoint iPt = fSegment->xyAtT(smaller);
+ SkPoint ePt = fSegment->xyAtT(larger);
+ SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
+ smaller, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
+ }
#endif
- fUnsortable = true;
-#endif
+ return;
}
+
+#ifdef SK_DEBUG
+void SkOpAngle::dump() const {
+ SkDebugf("id=%d (%1.9g,%1.9g) start=%d (%1.9g) end=%d (%1.9g)\n", fSegment->debugID(),
+ fSegment->xAtT(fStart), fSegment->yAtT(fStart), fStart, fSegment->span(fStart).fT,
+ fEnd, fSegment->span(fEnd).fT);
+}
+#endif
diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h
index e7e5e1f..583f5ec 100644
--- a/src/pathops/SkOpAngle.h
+++ b/src/pathops/SkOpAngle.h
@@ -12,23 +12,30 @@
#include "SkPathOpsCubic.h"
class SkOpSegment;
+struct SkOpSpan;
// sorting angles
// given angles of {dx dy ddx ddy dddx dddy} sort them
class SkOpAngle {
public:
enum { kStackBasedCount = 8 }; // FIXME: determine what this should be
+ enum IncludeType {
+ kUnaryWinding,
+ kUnaryXor,
+ kBinarySingle,
+ kBinaryOpp,
+ };
bool operator<(const SkOpAngle& rh) const;
bool calcSlop(double x, double y, double rx, double ry, bool* result) const;
double dx() const {
- return fTangent1.dx();
+ return fTangentPart.dx();
}
double dy() const {
- return fTangent1.dy();
+ return fTangentPart.dy();
}
int end() const {
@@ -37,8 +44,16 @@
bool isHorizontal() const;
+ SkOpSpan* lastMarked() const {
+ return fLastMarked;
+ }
+
void set(const SkOpSegment* segment, int start, int end);
+ void setLastMarked(SkOpSpan* marked) {
+ fLastMarked = marked;
+ }
+
SkOpSegment* segment() const {
return const_cast<SkOpSegment*>(fSegment);
}
@@ -59,11 +74,11 @@
return fUnsortable;
}
-#if DEBUG_ANGLE
- void debugShow(const SkPoint& a) const {
- SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);
- }
+#ifdef SK_DEBUG
+ void dump() const;
+#endif
+#if DEBUG_ANGLE
void setID(int id) {
fID = id;
}
@@ -73,10 +88,14 @@
bool lengthen(const SkOpAngle& );
void setSpans();
- SkDCubic fCurvePart;
+ SkDCubic fCurvePart; // the curve from start to end
+ SkDCubic fCurveHalf; // the curve from start to 1 or 0
double fSide;
- SkLineParameters fTangent1;
+ double fSide2;
+ SkLineParameters fTangentPart;
+ SkLineParameters fTangentHalf;
const SkOpSegment* fSegment;
+ SkOpSpan* fLastMarked;
int fStart;
int fEnd;
bool fComputed; // tangent is computed, may contain some error
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index f3861a1..facba87 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -12,8 +12,7 @@
void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
const SkIntersections& ts, bool swap) {
SkCoincidence& coincidence = fCoincidences.push_back();
- coincidence.fContours[0] = this; // FIXME: no need to store
- coincidence.fContours[1] = other;
+ coincidence.fOther = other;
coincidence.fSegments[0] = index;
coincidence.fSegments[1] = otherIndex;
coincidence.fTs[swap][0] = ts[0][0];
@@ -48,10 +47,9 @@
int count = fCoincidences.count();
for (int index = 0; index < count; ++index) {
SkCoincidence& coincidence = fCoincidences[index];
- SkASSERT(coincidence.fContours[0] == this);
int thisIndex = coincidence.fSegments[0];
SkOpSegment& thisOne = fSegments[thisIndex];
- SkOpContour* otherContour = coincidence.fContours[1];
+ SkOpContour* otherContour = coincidence.fOther;
int otherIndex = coincidence.fSegments[1];
SkOpSegment& other = otherContour->fSegments[otherIndex];
if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
@@ -103,53 +101,86 @@
}
}
+void SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
+ const SkIntersections& ts, int ptIndex, bool swap) {
+ SkCoincidence& coincidence = fPartialCoincidences.push_back();
+ coincidence.fOther = other;
+ coincidence.fSegments[0] = index;
+ coincidence.fSegments[1] = otherIndex;
+ coincidence.fTs[swap][0] = ts[0][index];
+ coincidence.fTs[swap][1] = ts[0][index + 1];
+ coincidence.fTs[!swap][0] = ts[1][index];
+ coincidence.fTs[!swap][1] = ts[1][index + 1];
+ coincidence.fPts[0] = ts.pt(index).asSkPoint();
+ coincidence.fPts[1] = ts.pt(index + 1).asSkPoint();
+}
+
void SkOpContour::calcCoincidentWinding() {
int count = fCoincidences.count();
+#if DEBUG_CONCIDENT
+ if (count > 0) {
+ SkDebugf("%s count=%d\n", __FUNCTION__, count);
+ }
+#endif
for (int index = 0; index < count; ++index) {
SkCoincidence& coincidence = fCoincidences[index];
- SkASSERT(coincidence.fContours[0] == this);
- int thisIndex = coincidence.fSegments[0];
- SkOpSegment& thisOne = fSegments[thisIndex];
- if (thisOne.done()) {
- continue;
- }
- SkOpContour* otherContour = coincidence.fContours[1];
- 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];
- bool cancelers;
- if ((cancelers = startT > endT)) {
- SkTSwap<double>(startT, endT);
- }
- 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) {
- // make sure startT and endT have t entries
- if (!thisOne.done() && !other.done()) {
- thisOne.addTCancel(startT, endT, &other, oStartT, oEndT);
- }
- } else {
- if (!thisOne.done() && !other.done()) {
- thisOne.addTCoincident(startT, endT, &other, oStartT, oEndT);
- }
- }
- #if DEBUG_CONCIDENT
- thisOne.debugShowTs();
- other.debugShowTs();
- #endif
+ calcCommonCoincidentWinding(coincidence);
}
}
+void SkOpContour::calcPartialCoincidentWinding() {
+ int count = fPartialCoincidences.count();
+#if DEBUG_CONCIDENT
+ if (count > 0) {
+ SkDebugf("%s count=%d\n", __FUNCTION__, count);
+ }
+#endif
+ for (int index = 0; index < count; ++index) {
+ SkCoincidence& coincidence = fPartialCoincidences[index];
+ calcCommonCoincidentWinding(coincidence);
+ }
+}
+
+void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
+ int thisIndex = coincidence.fSegments[0];
+ SkOpSegment& thisOne = fSegments[thisIndex];
+ if (thisOne.done()) {
+ return;
+ }
+ SkOpContour* otherContour = coincidence.fOther;
+ int otherIndex = coincidence.fSegments[1];
+ SkOpSegment& other = otherContour->fSegments[otherIndex];
+ if (other.done()) {
+ return;
+ }
+ double startT = coincidence.fTs[0][0];
+ double endT = coincidence.fTs[0][1];
+ const SkPoint* startPt = &coincidence.fPts[0];
+ const SkPoint* endPt = &coincidence.fPts[1];
+ bool cancelers;
+ if ((cancelers = startT > endT)) {
+ SkTSwap<double>(startT, endT);
+ SkTSwap<const SkPoint*>(startPt, endPt);
+ }
+ 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.addTCancel(*startPt, *endPt, &other);
+ } else {
+ thisOne.addTCoincident(*startPt, *endPt, &other);
+ }
+#if DEBUG_CONCIDENT
+ thisOne.debugShowTs();
+ other.debugShowTs();
+#endif
+}
+
void SkOpContour::sortSegments() {
int segmentCount = fSegments.count();
fSortedSegments.push_back_n(segmentCount);
@@ -229,7 +260,7 @@
return sum;
}
-static void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
+void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
// int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
// int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
int ofInterest = 1 << 5 | 1 << 8;
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index 456e6c0..a5635fe 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -15,7 +15,7 @@
class SkPathWriter;
struct SkCoincidence {
- SkOpContour* fContours[2];
+ SkOpContour* fOther;
int fSegments[2];
double fTs[2][2];
SkPoint fPts[2];
@@ -25,8 +25,8 @@
public:
SkOpContour() {
reset();
-#if DEBUG_DUMP
- fID = ++gContourID;
+#ifdef SK_DEBUG
+ fID = ++SkPathOpsDebug::gContourID;
#endif
}
@@ -63,15 +63,19 @@
fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex);
}
+ void addPartialCoincident(int index, SkOpContour* other, int otherIndex,
+ const SkIntersections& ts, int ptIndex, bool swap);
+
int addQuad(const SkPoint pts[3]) {
fSegments.push_back().addQuad(pts, fOperand, fXor);
fContainsCurves = true;
return fSegments.count();
}
- int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
+ int addT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT,
+ bool isNear) {
setContainsIntercepts();
- return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT);
+ return fSegments[segIndex].addT(&other->fSegments[otherIndex], pt, newT, isNear);
}
int addSelfT(int segIndex, SkOpContour* other, int otherIndex, const SkPoint& pt, double newT) {
@@ -79,16 +83,12 @@
return fSegments[segIndex].addSelfT(&other->fSegments[otherIndex], pt, newT);
}
- int addUnsortableT(int segIndex, SkOpContour* other, int otherIndex, bool start,
- const SkPoint& pt, double newT) {
- return fSegments[segIndex].addUnsortableT(&other->fSegments[otherIndex], start, pt, newT);
- }
-
const SkPathOpsBounds& bounds() const {
return fBounds;
}
void calcCoincidentWinding();
+ void calcPartialCoincidentWinding();
void checkEnds() {
if (!fContainsCurves) {
@@ -100,7 +100,18 @@
if (segment->verb() == SkPath::kLine_Verb) {
continue;
}
- fSegments[sIndex].checkEnds();
+ segment->checkEnds();
+ }
+ }
+
+ // if same point has different T values, choose a common T
+ void checkTiny() {
+ int segmentCount = fSegments.count();
+ if (segmentCount <= 2) {
+ return;
+ }
+ for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
+ fSegments[sIndex].checkTiny();
}
}
@@ -131,13 +142,6 @@
return segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
}
- void findTooCloseToCall() {
- int segmentCount = fSegments.count();
- for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
- fSegments[sIndex].findTooCloseToCall();
- }
- }
-
void fixOtherTIndex() {
int segmentCount = fSegments.count();
for (int sIndex = 0; sIndex < segmentCount; ++sIndex) {
@@ -232,12 +236,14 @@
#endif
private:
+ void calcCommonCoincidentWinding(const SkCoincidence& coincidence);
void setBounds();
SkTArray<SkOpSegment> fSegments;
SkTArray<SkOpSegment*, true> fSortedSegments;
int fFirstSorted;
SkTArray<SkCoincidence, true> fCoincidences;
+ SkTArray<SkCoincidence, true> fPartialCoincidences;
SkTArray<const SkOpContour*, true> fCrosses;
SkPathOpsBounds fBounds;
bool fContainsIntercepts; // FIXME: is this used by anybody?
@@ -247,7 +253,7 @@
bool fOperand; // true for the second argument to a binary operator
bool fXor;
bool fOppXor;
-#if DEBUG_DUMP
+#ifdef SK_DEBUG
int fID;
#endif
};
diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp
index a5a6584..676c34f 100644
--- a/src/pathops/SkOpEdgeBuilder.cpp
+++ b/src/pathops/SkOpEdgeBuilder.cpp
@@ -13,9 +13,9 @@
fOperand = false;
fXorMask[0] = fXorMask[1] = (fPath->getFillType() & 1) ? kEvenOdd_PathOpsMask
: kWinding_PathOpsMask;
-#if DEBUG_DUMP
- gContourID = 0;
- gSegmentID = 0;
+#ifdef SK_DEBUG
+ SkPathOpsDebug::gContourID = 0;
+ SkPathOpsDebug::gSegmentID = 0;
#endif
fUnparseable = false;
fSecondHalf = preFetch();
@@ -84,6 +84,9 @@
case SkPath::kLine_Verb:
if (AlmostEqualUlps(curve[0].fX, pts[1].fX)
&& AlmostEqualUlps(curve[0].fY, pts[1].fY)) {
+ if (fPathVerbs.back() != SkPath::kLine_Verb) {
+ fPathPts.back() = pts[1];
+ }
continue; // skip degenerate points
}
break;
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 7e69bb8..c0ef1f8 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -32,36 +32,36 @@
#undef F
#undef T
-enum { kOutsideTrackedTCount = 16 }; // FIXME: determine what this should be
+enum {
+ kOutsideTrackedTCount = 16, // FIXME: determine what this should be
+ kMissingSpanCount = 4, // FIXME: determine what this should be
+};
-// OPTIMIZATION: does the following also work, and is it any faster?
-// return outerWinding * innerWinding > 0
-// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
-bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
- SkASSERT(outerWinding != SK_MaxS32);
- SkASSERT(innerWinding != SK_MaxS32);
- int absOut = abs(outerWinding);
- int absIn = abs(innerWinding);
- bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
- return result;
-}
-
+// note that this follows the same logic flow as build angles
bool SkOpSegment::activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles) {
if (activeAngleInner(index, done, angles)) {
return true;
}
+ double referenceT = fTs[index].fT;
int lesser = index;
- while (--lesser >= 0 && equalPoints(index, lesser)) {
+ while (--lesser >= 0
+ && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
if (activeAngleOther(lesser, done, angles)) {
return true;
}
}
- lesser = index;
do {
if (activeAngleOther(index, done, angles)) {
return true;
}
- } while (++index < fTs.count() && equalPoints(index, lesser));
+ if (++index == fTs.count()) {
+ break;
+ }
+ if (fTs[index - 1].fTiny) {
+ referenceT = fTs[index].fT;
+ continue;
+ }
+ } while (precisely_negative(fTs[index].fT - referenceT));
return false;
}
@@ -187,7 +187,7 @@
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__,
- kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
+ SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
#endif
return result;
}
@@ -209,47 +209,35 @@
void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const {
SkASSERT(start != end);
SkOpAngle& angle = anglesPtr->push_back();
-#if 0 && DEBUG_ANGLE // computed pt and actual pt may differ by more than approx eq
- SkTArray<SkOpAngle, true>& angles = *anglesPtr;
- if (angles.count() > 1) {
- const SkOpSegment* aSeg = angles[0].segment();
- int aStart = angles[0].start();
- if (!aSeg->fTs[aStart].fTiny) {
- const SkPoint& angle0Pt = aSeg->xyAtT(aStart);
- SkDPoint newPt = (*CurveDPointAtT[SkPathOpsVerbToPoints(aSeg->fVerb)])(aSeg->fPts,
- aSeg->fTs[aStart].fT);
-#if ONE_OFF_DEBUG
- SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g)\n", __FUNCTION__,
- aSeg->fTs[aStart].fT, newPt.fX, newPt.fY, angle0Pt.fX, angle0Pt.fY);
-#endif
- SkASSERT(newPt.approximatelyEqual(angle0Pt));
- }
- }
-#endif
angle.set(this, start, end);
}
-void SkOpSegment::addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd) {
+void SkOpSegment::addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt,
+ SkOpSegment* other) {
int tIndex = -1;
int tCount = fTs.count();
int oIndex = -1;
int oCount = other->fTs.count();
do {
++tIndex;
- } while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount);
+ } while (startPt != fTs[tIndex].fPt && tIndex < tCount);
int tIndexStart = tIndex;
do {
++oIndex;
- } while (!approximately_negative(oStart - other->fTs[oIndex].fT) && oIndex < oCount);
+ } while (endPt != other->fTs[oIndex].fPt && oIndex < oCount);
int oIndexStart = oIndex;
- double nextT;
+ const SkPoint* nextPt;
do {
- nextT = fTs[++tIndex].fT;
- } while (nextT < 1 && approximately_negative(nextT - tStart));
- double oNextT;
+ nextPt = &fTs[++tIndex].fPt;
+ SkASSERT(fTs[tIndex].fT < 1 || startPt != *nextPt);
+ } while (startPt == *nextPt);
+ double nextT = fTs[tIndex].fT;
+ const SkPoint* oNextPt;
do {
- oNextT = other->fTs[++oIndex].fT;
- } while (oNextT < 1 && approximately_negative(oNextT - oStart));
+ oNextPt = &other->fTs[++oIndex].fPt;
+ SkASSERT(other->fTs[oIndex].fT < 1 || endPt != *oNextPt);
+ } while (endPt == *oNextPt);
+ double oNextT = other->fTs[oIndex].fT;
// at this point, spans before and after are at:
// fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
// if tIndexStart == 0, no prior span
@@ -301,43 +289,39 @@
}
}
-void SkOpSegment::addCoinOutsides(const SkTArray<double, true>& outsideTs, SkOpSegment* other,
- double oEnd) {
- // walk this to outsideTs[0]
- // walk other to outsideTs[1]
+void SkOpSegment::addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt,
+ SkOpSegment* other) {
+ // walk this to startPt
+ // walk other to startPt
// if either is > 0, add a pointer to the other, copying adjacent winding
int tIndex = -1;
int oIndex = -1;
- double tStart = outsideTs[0];
- double oStart = outsideTs[1];
do {
++tIndex;
- } while (!approximately_negative(tStart - fTs[tIndex].fT));
- SkPoint ptStart = fTs[tIndex].fPt;
+ } while (startPt != fTs[tIndex].fPt);
do {
++oIndex;
- } while (!approximately_negative(oStart - other->fTs[oIndex].fT));
+ } while (startPt != other->fTs[oIndex].fPt);
if (tIndex > 0 || oIndex > 0 || fOperand != other->fOperand) {
- addTPair(tStart, other, oStart, false, ptStart);
+ addTPair(fTs[tIndex].fT, other, other->fTs[oIndex].fT, false, startPt);
}
- tStart = fTs[tIndex].fT;
- oStart = other->fTs[oIndex].fT;
+ SkPoint nextPt = startPt;
do {
- double nextT;
+ const SkPoint* workPt;
do {
- nextT = fTs[++tIndex].fT;
- } while (approximately_negative(nextT - tStart));
- tStart = nextT;
- ptStart = fTs[tIndex].fPt;
+ workPt = &fTs[++tIndex].fPt;
+ } while (nextPt == *workPt);
do {
- nextT = other->fTs[++oIndex].fT;
- } while (approximately_negative(nextT - oStart));
- oStart = nextT;
+ workPt = &other->fTs[++oIndex].fPt;
+ } while (nextPt == *workPt);
+ nextPt = *workPt;
+ double tStart = fTs[tIndex].fT;
+ double oStart = other->fTs[oIndex].fT;
if (tStart == 1 && oStart == 1 && fOperand == other->fOperand) {
break;
}
- addTPair(tStart, other, oStart, false, ptStart);
- } while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
+ addTPair(tStart, other, oStart, false, nextPt);
+ } while (endPt != nextPt);
}
void SkOpSegment::addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
@@ -423,7 +407,7 @@
// resolve overlapping ts when considering coincidence later
// add non-coincident intersection. Resulting edges are sorted in T.
-int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) {
+int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear) {
if (precisely_zero(newT)) {
newT = 0;
} else if (precisely_equal(newT, 1)) {
@@ -455,6 +439,7 @@
span->fT = newT;
span->fOther = other;
span->fPt = pt;
+ span->fNear = isNear;
#if 0
// cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
@@ -464,6 +449,7 @@
span->fOppSum = SK_MinS32;
span->fWindValue = 1;
span->fOppValue = 0;
+ span->fSmall = false;
span->fTiny = false;
span->fLoop = false;
if ((span->fDone = newT == 1)) {
@@ -472,7 +458,7 @@
span->fUnsortableStart = false;
span->fUnsortableEnd = false;
int less = -1;
- while (&span[less + 1] - fTs.begin() > 0 && xyAtT(&span[less]) == xyAtT(span)) {
+ while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, span->fPt)) {
if (span[less].fDone) {
break;
}
@@ -487,9 +473,11 @@
break;
}
}
- span[less].fTiny = true;
+ span[less].fSmall = true;
+ bool tiny = span[less].fPt == span->fPt;
+ span[less].fTiny = tiny;
span[less].fDone = true;
- if (approximately_negative(newT - span[less].fT)) {
+ if (approximately_negative(newT - span[less].fT) && tiny) {
if (approximately_greater_than_one(newT)) {
SkASSERT(&span[less] - fTs.begin() < fTs.count());
span[less].fUnsortableStart = true;
@@ -508,7 +496,7 @@
--less;
}
int more = 1;
- while (fTs.end() - &span[more - 1] > 1 && xyAtT(&span[more]) == xyAtT(span)) {
+ while (fTs.end() - &span[more - 1] > 1 && AlmostEqualUlps(span[more].fPt, span->fPt)) {
if (span[more - 1].fDone) {
break;
}
@@ -523,9 +511,11 @@
break;
}
}
- span[more - 1].fTiny = true;
+ span[more - 1].fSmall = true;
+ bool tiny = span[more].fPt == span->fPt;
+ span[more - 1].fTiny = tiny;
span[more - 1].fDone = true;
- if (approximately_negative(span[more].fT - newT)) {
+ if (approximately_negative(span[more].fT - newT) && tiny) {
if (approximately_greater_than_one(span[more].fT)) {
span[more + 1].fUnsortableStart = true;
span[more].fUnsortableEnd = true;
@@ -553,148 +543,156 @@
// FIXME? It seems that decrementing by one will fail for complex paths that
// have three or more coincident edges. Shouldn't this subtract the difference
// between the winding values?
-void SkOpSegment::addTCancel(double startT, double endT, SkOpSegment* other,
- double oStartT, double oEndT) {
- SkASSERT(!approximately_negative(endT - startT));
- SkASSERT(!approximately_negative(oEndT - oStartT));
+/* |--> |-->
+this 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4 0>>>>1>>>>2>>>>3>>>4
+other 2<<<<1<<<<0 2<<<<1<<<<0 2<<<<1<<<<0
+ ^ ^ <--| <--|
+ startPt endPt test/oTest first pos test/oTest final pos
+*/
+void SkOpSegment::addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other) {
bool binary = fOperand != other->fOperand;
int index = 0;
- while (!approximately_negative(startT - fTs[index].fT)) {
+ while (startPt != fTs[index].fPt) {
+ SkASSERT(index < fTs.count());
++index;
}
int oIndex = other->fTs.count();
- while (approximately_positive(other->fTs[--oIndex].fT - oEndT))
- ;
- double tRatio = (oEndT - oStartT) / (endT - startT);
+ while (startPt != other->fTs[--oIndex].fPt) { // look for startPt match
+ SkASSERT(oIndex > 0);
+ }
+ while (startPt == other->fTs[--oIndex].fPt) { // look for first point beyond match
+ SkASSERT(oIndex > 0);
+ }
SkOpSpan* test = &fTs[index];
SkOpSpan* oTest = &other->fTs[oIndex];
- SkSTArray<kOutsideTrackedTCount, double, true> outsideTs;
- SkSTArray<kOutsideTrackedTCount, double, true> oOutsideTs;
+ SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
+ SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
do {
+ SkASSERT(test->fT < 1);
+ SkASSERT(oTest->fT < 1);
bool decrement = test->fWindValue && oTest->fWindValue;
bool track = test->fWindValue || oTest->fWindValue;
bool bigger = test->fWindValue >= oTest->fWindValue;
- double testT = test->fT;
- double oTestT = oTest->fT;
- SkOpSpan* span = test;
+ const SkPoint& testPt = test->fPt;
+ const SkPoint& oTestPt = oTest->fPt;
do {
if (decrement) {
if (binary && bigger) {
- span->fOppValue--;
+ test->fOppValue--;
} else {
- decrementSpan(span);
+ decrementSpan(test);
}
- } else if (track && span->fT < 1 && oTestT < 1) {
- TrackOutside(&outsideTs, span->fT, oTestT);
+ } else if (track) {
+ TrackOutsidePair(&outsidePts, testPt, oTestPt);
}
- span = &fTs[++index];
- } while (approximately_negative(span->fT - testT));
- SkOpSpan* oSpan = oTest;
- double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;
- double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;
- SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);
- while (approximately_negative(otherTMatchStart - oSpan->fT)
- && !approximately_negative(otherTMatchEnd - oSpan->fT)) {
- #ifdef SK_DEBUG
- SkASSERT(originalWindValue == oSpan->fWindValue);
- #endif
+ SkASSERT(index < fTs.count() - 1);
+ test = &fTs[++index];
+ } while (testPt == test->fPt);
+ SkDEBUGCODE(int originalWindValue = oTest->fWindValue);
+ do {
+ SkASSERT(oTest->fT < 1);
+ SkASSERT(originalWindValue == oTest->fWindValue);
if (decrement) {
if (binary && !bigger) {
- oSpan->fOppValue--;
+ oTest->fOppValue--;
} else {
- other->decrementSpan(oSpan);
+ other->decrementSpan(oTest);
}
- } else if (track && oSpan->fT < 1 && testT < 1) {
- TrackOutside(&oOutsideTs, oSpan->fT, testT);
+ } else if (track) {
+ TrackOutsidePair(&oOutsidePts, oTestPt, testPt);
}
if (!oIndex) {
break;
}
- oSpan = &other->fTs[--oIndex];
- }
- test = span;
- oTest = oSpan;
- } while (!approximately_negative(endT - test->fT));
- SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT));
+ oTest = &other->fTs[--oIndex];
+ } while (oTestPt == oTest->fPt);
+ SkASSERT(endPt != test->fPt || oTestPt == endPt);
+ } while (endPt != test->fPt);
// FIXME: determine if canceled edges need outside ts added
- if (!done() && outsideTs.count()) {
- double tStart = outsideTs[0];
- double oStart = outsideTs[1];
- addCancelOutsides(tStart, oStart, other, oEndT);
- int count = outsideTs.count();
- if (count > 2) {
- double tStart = outsideTs[count - 2];
- double oStart = outsideTs[count - 1];
- addCancelOutsides(tStart, oStart, other, oEndT);
+ int outCount = outsidePts.count();
+ if (!done() && outCount) {
+ addCancelOutsides(outsidePts[0], outsidePts[1], other);
+ if (outCount > 2) {
+ addCancelOutsides(outsidePts[outCount - 2], outsidePts[outCount - 1], other);
}
}
- if (!other->done() && oOutsideTs.count()) {
- double tStart = oOutsideTs[0];
- double oStart = oOutsideTs[1];
- other->addCancelOutsides(tStart, oStart, this, endT);
+ if (!other->done() && oOutsidePts.count()) {
+ other->addCancelOutsides(oOutsidePts[0], oOutsidePts[1], this);
}
}
int SkOpSegment::addSelfT(SkOpSegment* other, const SkPoint& pt, double newT) {
- int result = addT(other, pt, newT);
+ // if the tail nearly intersects itself but not quite, the caller records this separately
+ int result = addT(other, pt, newT, SkOpSpan::kPointIsExact);
SkOpSpan* span = &fTs[result];
span->fLoop = true;
return result;
}
-int SkOpSegment::addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT) {
- int result = addT(other, pt, newT);
- SkOpSpan* span = &fTs[result];
- if (start) {
- if (result > 0) {
- span[result - 1].fUnsortableEnd = true;
- }
- span[result].fUnsortableStart = true;
- } else {
- span[result].fUnsortableEnd = true;
- if (result + 1 < fTs.count()) {
- span[result + 1].fUnsortableStart = true;
- }
- }
- return result;
-}
-
-int SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool opp, int index,
- SkTArray<double, true>* outsideTs) {
+void SkOpSegment::bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* indexPtr,
+ SkTArray<SkPoint, true>* outsideTs) {
+ int index = *indexPtr;
int oWindValue = oTest.fWindValue;
int oOppValue = oTest.fOppValue;
- if (opp) {
+ if (binary) {
SkTSwap<int>(oWindValue, oOppValue);
}
SkOpSpan* const test = &fTs[index];
SkOpSpan* end = test;
- const double oStartT = oTest.fT;
+ const SkPoint& oStartPt = oTest.fPt;
do {
if (bumpSpan(end, oWindValue, oOppValue)) {
- TrackOutside(outsideTs, end->fT, oStartT);
+ TrackOutside(outsideTs, oStartPt);
}
end = &fTs[++index];
- } while (approximately_negative(end->fT - test->fT));
- return index;
+ } while (end->fPt == test->fPt);
+ *indexPtr = index;
+}
+
+bool SkOpSegment::bumpCoincident(SkOpSpan* test, bool bigger, bool binary) {
+ if (bigger) {
+ if (binary) {
+ if (fOppXor) {
+ test->fOppValue ^= 1;
+ } else {
+ test->fOppValue++;
+ }
+ } else {
+ if (fXor) {
+ test->fWindValue ^= 1;
+ } else {
+ test->fWindValue++;
+ }
+ }
+ if (!test->fWindValue && !test->fOppValue) {
+ test->fDone = true;
+ ++fDoneSpans;
+ return true;
+ }
+ return false;
+ }
+ return decrementSpan(test);
}
// because of the order in which coincidences are resolved, this and other
// may not have the same intermediate points. Compute the corresponding
// intermediate T values (using this as the master, other as the follower)
// and walk other conditionally -- hoping that it catches up in the end
-int SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, double oEndT, int& oIndex,
- SkTArray<double, true>* oOutsideTs) {
+void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
+ SkTArray<SkPoint, true>* oOutsidePts) {
+ int oIndex = *oIndexPtr;
SkOpSpan* const oTest = &fTs[oIndex];
SkOpSpan* oEnd = oTest;
- const double startT = test.fT;
- const double oStartT = oTest->fT;
- while (!approximately_negative(oEndT - oEnd->fT)
- && approximately_negative(oEnd->fT - oStartT)) {
+ const SkPoint& startPt = test.fPt;
+ const SkPoint& oStartPt = oTest->fPt;
+ if (oStartPt == oEnd->fPt) {
+ TrackOutside(oOutsidePts, startPt);
+ }
+ while (oStartPt == oEnd->fPt) {
zeroSpan(oEnd);
- TrackOutside(oOutsideTs, oEnd->fT, startT);
oEnd = &fTs[++oIndex];
}
- return oIndex;
+ *oIndexPtr = oIndex;
}
// FIXME: need to test this case:
@@ -706,43 +704,75 @@
// set spans from start to end to increment the greater by one and decrement
// the lesser
-void SkOpSegment::addTCoincident(double startT, double endT, SkOpSegment* other, double oStartT,
- double oEndT) {
- SkASSERT(!approximately_negative(endT - startT));
- SkASSERT(!approximately_negative(oEndT - oStartT));
- bool opp = fOperand ^ other->fOperand;
+void SkOpSegment::addTCoincident(const SkPoint& startPt, const SkPoint& endPt,
+ SkOpSegment* other) {
+ bool binary = fOperand != other->fOperand;
int index = 0;
- while (!approximately_negative(startT - fTs[index].fT)) {
+ while (startPt != fTs[index].fPt) {
+ SkASSERT(index < fTs.count());
++index;
}
int oIndex = 0;
- while (!approximately_negative(oStartT - other->fTs[oIndex].fT)) {
+ while (startPt != other->fTs[oIndex].fPt) {
+ SkASSERT(oIndex < other->fTs.count());
++oIndex;
}
+ SkSTArray<kOutsideTrackedTCount, SkPoint, true> outsidePts;
+ SkSTArray<kOutsideTrackedTCount, SkPoint, true> oOutsidePts;
SkOpSpan* test = &fTs[index];
+ const SkPoint* testPt = &test->fPt;
SkOpSpan* oTest = &other->fTs[oIndex];
- SkSTArray<kOutsideTrackedTCount, double, true> outsideTs;
- SkSTArray<kOutsideTrackedTCount, double, true> oOutsideTs;
+ const SkPoint* oTestPt = &oTest->fPt;
+ SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
do {
- // if either span has an opposite value and the operands don't match, resolve first
- // SkASSERT(!test->fDone || !oTest->fDone);
+ SkASSERT(test->fT < 1);
+ SkASSERT(oTest->fT < 1);
+#if 0
if (test->fDone || oTest->fDone) {
- index = advanceCoincidentThis(oTest, opp, index);
- oIndex = other->advanceCoincidentOther(test, oEndT, oIndex);
+#else // consolidate the winding count even if done
+ if ((test->fWindValue == 0 && test->fOppValue == 0)
+ || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
+#endif
+ SkDEBUGCODE(int firstWind = test->fWindValue);
+ SkDEBUGCODE(int firstOpp = test->fOppValue);
+ do {
+ SkASSERT(firstWind == fTs[index].fWindValue);
+ SkASSERT(firstOpp == fTs[index].fOppValue);
+ ++index;
+ SkASSERT(index < fTs.count());
+ } while (*testPt == fTs[index].fPt);
+ SkDEBUGCODE(firstWind = oTest->fWindValue);
+ SkDEBUGCODE(firstOpp = oTest->fOppValue);
+ do {
+ SkASSERT(firstWind == other->fTs[oIndex].fWindValue);
+ SkASSERT(firstOpp == other->fTs[oIndex].fOppValue);
+ ++oIndex;
+ SkASSERT(oIndex < other->fTs.count());
+ } while (*oTestPt == other->fTs[oIndex].fPt);
} else {
- index = bumpCoincidentThis(*oTest, opp, index, &outsideTs);
- oIndex = other->bumpCoincidentOther(*test, oEndT, oIndex, &oOutsideTs);
+ if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
+ bumpCoincidentThis(*oTest, binary, &index, &outsidePts);
+ other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
+ } else {
+ other->bumpCoincidentThis(*test, binary, &oIndex, &oOutsidePts);
+ bumpCoincidentOther(*oTest, &index, &outsidePts);
+ }
}
test = &fTs[index];
+ testPt = &test->fPt;
+ if (endPt == *testPt) {
+ break;
+ }
oTest = &other->fTs[oIndex];
- } while (!approximately_negative(endT - test->fT));
- SkASSERT(approximately_negative(oTest->fT - oEndT));
- SkASSERT(approximately_negative(oEndT - oTest->fT));
- if (!done() && outsideTs.count()) {
- addCoinOutsides(outsideTs, other, oEndT);
+ oTestPt = &oTest->fPt;
+ SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
+ } while (endPt != *oTestPt);
+ int outCount = outsidePts.count();
+ if (!done() && outCount) {
+ addCoinOutsides(outsidePts[0], endPt, other);
}
- if (!other->done() && oOutsideTs.count()) {
- other->addCoinOutsides(oOutsideTs, this, endT);
+ if (!other->done() && oOutsidePts.count()) {
+ other->addCoinOutsides(oOutsidePts[0], endPt, this);
}
}
@@ -769,8 +799,8 @@
SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other->fID, otherT);
#endif
- int insertedAt = addT(other, pt, t);
- int otherInsertedAt = other->addT(this, pt, otherT);
+ int insertedAt = addT(other, pt, t, SkOpSpan::kPointIsExact);
+ int otherInsertedAt = other->addT(this, pt, otherT, SkOpSpan::kPointIsExact);
addOtherT(insertedAt, otherT, otherInsertedAt);
other->addOtherT(otherInsertedAt, t, insertedAt);
matchWindingValue(insertedAt, t, borrowWind);
@@ -792,7 +822,151 @@
}
}
-int SkOpSegment::advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int index) {
+SkOpSegment::MissingSpan::Command SkOpSegment::adjustThisNear(double startT, const SkPoint& startPt,
+ const SkPoint& endPt, SkTArray<MissingSpan, true>* missingSpans) {
+ // see if endPt exists on this curve, and if it has the same t or a different T than the startT
+ int count = this->count();
+ SkASSERT(count > 0);
+ int startIndex, endIndex, step;
+ if (startT == 0) {
+ startIndex = 0;
+ endIndex = count;
+ step = 1;
+ } else {
+ SkASSERT(startT == 1);
+ startIndex = count - 1;
+ endIndex = -1;
+ step = -1;
+ }
+ int index = startIndex;
+ do {
+ const SkOpSpan& span = fTs[index];
+ if (span.fPt != endPt) {
+ continue;
+ }
+ if (span.fT == startT) {
+ // check to see if otherT matches some other mid curve intersection
+ int inner = startIndex;
+ do {
+ if (inner == index) {
+ continue;
+ }
+ const SkOpSpan& matchSpan = fTs[inner];
+ double matchT = span.fOther->missingNear(span.fOtherT, matchSpan.fOther, startPt,
+ endPt);
+ if (matchT >= 0) {
+ SkASSERT(missingSpans);
+ MissingSpan& missingSpan = missingSpans->push_back();
+ SkDEBUGCODE(sk_bzero(&missingSpan, sizeof(missingSpan)));
+ missingSpan.fCommand = MissingSpan::kRemoveNear;
+ missingSpan.fT = startT;
+ missingSpan.fSegment = this;
+ missingSpan.fOther = span.fOther;
+ missingSpan.fOtherT = matchT;
+ return missingSpan.fCommand;
+ }
+ } while ((inner += step) != endIndex);
+ break;
+ }
+ double midT = (startT + span.fT) / 2;
+ if (betweenPoints(midT, startPt, endPt)) {
+ if (!missingSpans) {
+ return MissingSpan::kZeroSpan;
+ }
+ MissingSpan& missingSpan = missingSpans->push_back();
+ SkDEBUGCODE(sk_bzero(&missingSpan, sizeof(missingSpan)));
+ missingSpan.fCommand = MissingSpan::kZeroSpan;
+ missingSpan.fT = SkTMin(startT, span.fT);
+ missingSpan.fEndT = SkTMax(startT, span.fT);
+ missingSpan.fSegment = this;
+ return missingSpan.fCommand;
+ }
+ } while ((index += step) != endIndex);
+ return MissingSpan::kNoAction;
+}
+
+void SkOpSegment::adjustOtherNear(double startT, const SkPoint& startPt, const SkPoint& endPt,
+ SkTArray<MissingSpan, true>* missingSpans) {
+ int count = this->count();
+ SkASSERT(count > 0);
+ int startIndex, endIndex, step;
+ if (startT == 0) {
+ startIndex = 0;
+ endIndex = count;
+ step = 1;
+ } else {
+ SkASSERT(startT == 1);
+ startIndex = count - 1;
+ endIndex = -1;
+ step = -1;
+ }
+ int index = startIndex;
+ do {
+ const SkOpSpan& span = fTs[index];
+ if (span.fT != startT) {
+ return;
+ }
+ SkOpSegment* other = span.fOther;
+ if (other->fPts[0] == endPt) {
+ other->adjustThisNear(0, endPt, startPt, missingSpans);
+ } else if (other->fPts[0] == startPt) {
+ other->adjustThisNear(0, startPt, endPt, missingSpans);
+ }
+ if (other->ptAtT(1) == endPt) {
+ other->adjustThisNear(1, endPt, startPt, missingSpans);
+ } else if (other->ptAtT(1) == startPt) {
+ other->adjustThisNear(1, startPt, endPt, missingSpans);
+ }
+ } while ((index += step) != endIndex);
+}
+
+void SkOpSegment::adjustMissingNear(const SkPoint& startPt, const SkPoint& endPt,
+ SkTArray<MissingSpan, true>* missingSpans) {
+ int count = missingSpans->count();
+ for (int index = 0; index < count; ) {
+ MissingSpan& missing = (*missingSpans)[index];
+ SkOpSegment* other = missing.fOther;
+ MissingSpan::Command command = MissingSpan::kNoAction;
+ if (missing.fPt == startPt) {
+ if (missingNear(missing.fT, other, startPt, endPt) >= 0) {
+ command = MissingSpan::kZeroSpan;
+ } else if (other->ptAtT(0) == endPt) {
+ command = other->adjustThisNear(0, endPt, startPt, NULL);
+ } else if (other->ptAtT(1) == endPt) {
+ command = other->adjustThisNear(1, endPt, startPt, NULL);
+ }
+ } else if (missing.fPt == endPt) {
+ if (missingNear(missing.fT, other, endPt, startPt) >= 0) {
+ command = MissingSpan::kZeroSpan;
+ } else if (other->ptAtT(0) == startPt) {
+ command = other->adjustThisNear(0, startPt, endPt, NULL);
+ } else if (other->ptAtT(1) == startPt) {
+ command = other->adjustThisNear(1, startPt, endPt, NULL);
+ }
+ }
+ if (command == MissingSpan::kZeroSpan) {
+#if 1
+ missing = missingSpans->back();
+ missingSpans->pop_back();
+#else // if this is supported in the future ...
+ missingSpans->removeShuffle(index);
+#endif
+ --count;
+ continue;
+ }
+ ++index;
+ }
+}
+
+void SkOpSegment::adjustNear(double startT, const SkPoint& endPt,
+ SkTArray<MissingSpan, true>* missingSpans) {
+ const SkPoint startPt = ptAtT(startT);
+ adjustMissingNear(startPt, endPt, missingSpans);
+ adjustThisNear(startT, startPt, endPt, missingSpans);
+ adjustOtherNear(startT, startPt, endPt, missingSpans);
+}
+
+int SkOpSegment::advanceCoincidentThis(int index) {
SkOpSpan* const test = &fTs[index];
SkOpSpan* end;
do {
@@ -801,7 +975,7 @@
return index;
}
-int SkOpSegment::advanceCoincidentOther(const SkOpSpan* test, double oEndT, int oIndex) {
+int SkOpSegment::advanceCoincidentOther(double oEndT, int oIndex) {
SkOpSpan* const oTest = &fTs[oIndex];
SkOpSpan* oEnd = oTest;
const double oStartT = oTest->fT;
@@ -812,6 +986,14 @@
return oIndex;
}
+bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
+ const SkPoint midPt = ptAtT(midT);
+ SkPathOpsBounds bounds;
+ bounds.set(pt1.fX, pt1.fY, pt2.fX, pt2.fY);
+ bounds.sort();
+ return bounds.almostContains(midPt);
+}
+
bool SkOpSegment::betweenTs(int lesser, double testT, int greater) const {
if (lesser > greater) {
SkTSwap<int>(lesser, greater);
@@ -819,17 +1001,37 @@
return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
}
-void SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const {
+// note that this follows the same logic flow as active angle
+bool SkOpSegment::buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool allowOpp) const {
double referenceT = fTs[index].fT;
+ const SkPoint& referencePt = fTs[index].fPt;
int lesser = index;
- while (--lesser >= 0 && (includeOpp || fTs[lesser].fOther->fOperand == fOperand)
- && precisely_negative(referenceT - fTs[lesser].fT)) {
+ while (--lesser >= 0 && (allowOpp || fTs[lesser].fOther->fOperand == fOperand)
+ && (precisely_negative(referenceT - fTs[lesser].fT) || fTs[lesser].fTiny)) {
buildAnglesInner(lesser, angles);
}
do {
buildAnglesInner(index, angles);
- } while (++index < fTs.count() && (includeOpp || fTs[index].fOther->fOperand == fOperand)
- && precisely_negative(fTs[index].fT - referenceT));
+ if (++index == fTs.count()) {
+ break;
+ }
+ if (!allowOpp && fTs[index].fOther->fOperand != fOperand) {
+ break;
+ }
+ if (fTs[index - 1].fTiny) {
+ referenceT = fTs[index].fT;
+ continue;
+ }
+ if (!precisely_negative(fTs[index].fT - referenceT) && fTs[index].fPt == referencePt) {
+ // FIXME
+ // testQuad8 generates the wrong output unless false is returned here. Other tests will
+ // take this path although they aren't required to. This means that many go much slower
+ // because of this sort fail.
+ // SkDebugf("!!!\n");
+ return false;
+ }
+ } while (precisely_negative(fTs[index].fT - referenceT));
+ return true;
}
void SkOpSegment::buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const {
@@ -851,115 +1053,175 @@
other->addTwoAngles(next, oIndex, angles);
}
-int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) {
- SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
- addTwoAngles(startIndex, endIndex, &angles);
- buildAngles(endIndex, &angles, false);
- // OPTIMIZATION: check all angles to see if any have computed wind sum
- // before sorting (early exit if none)
- SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
- // FIXME?: Not sure if this sort must be ordered or if the relaxed ordering is OK ...
- bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
-#if DEBUG_SORT
- sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable);
-#endif
- if (!sortable) {
- return SK_MinS32;
+int SkOpSegment::computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
+ SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted) {
+ addTwoAngles(startIndex, endIndex, angles);
+ if (!buildAngles(endIndex, angles, includeType == SkOpAngle::kBinaryOpp)) {
+ return SK_NaN32;
}
- int angleCount = angles.count();
- const SkOpAngle* angle;
- const SkOpSegment* base;
- int winding;
- int oWinding;
- int firstIndex = 0;
- do {
- angle = sorted[firstIndex];
- base = angle->segment();
- winding = base->windSum(angle);
- if (winding != SK_MinS32) {
- oWinding = base->oppSum(angle);
- break;
+ int angleCount = angles->count();
+ // abort early before sorting if an unsortable (not an unorderable) angle is found
+ if (includeType != SkOpAngle::kUnaryXor) {
+ int firstIndex = -1;
+ while (++firstIndex < angleCount) {
+ const SkOpAngle& angle = (*angles)[firstIndex];
+ if (angle.segment()->windSum(&angle) != SK_MinS32) {
+ break;
+ }
}
- if (++firstIndex == angleCount) {
+ if (firstIndex == angleCount) {
return SK_MinS32;
}
- } while (true);
- // turn winding into contourWinding
- int spanWinding = base->spanSign(angle);
- bool inner = UseInnerWinding(winding + spanWinding, winding);
-#if DEBUG_WINDING
- SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
- spanWinding, winding, angle->sign(), inner,
- inner ? winding + spanWinding : winding);
-#endif
- if (inner) {
- winding += spanWinding;
}
-#if DEBUG_SORT
- base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding, sortable);
+ bool sortable = SortAngles2(*angles, sorted);
+#if DEBUG_SORT_RAW
+ if (sorted->count() > 0) {
+ (*sorted)[0]->segment()->debugShowSort(__FUNCTION__, *sorted, 0, 0, 0, sortable);
+ }
#endif
- int nextIndex = firstIndex + 1;
- int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
- winding -= base->spanSign(angle);
- oWinding -= base->oppSign(angle);
+ if (!sortable) {
+ return SK_NaN32;
+ }
+ if (includeType == SkOpAngle::kUnaryXor) {
+ return SK_MinS32;
+ }
+ // if all angles have a computed winding,
+ // or if no adjacent angles are orderable,
+ // or if adjacent orderable angles have no computed winding,
+ // there's nothing to do
+ // if two orderable angles are adjacent, and one has winding computed, transfer to the other
+ const SkOpAngle* baseAngle = NULL;
+ int last = angleCount;
+ int finalInitialOrderable = -1;
+ bool tryReverse = false;
+ // look for counterclockwise transfers
do {
- if (nextIndex == angleCount) {
- nextIndex = 0;
- }
- angle = sorted[nextIndex];
- SkOpSegment* segment = angle->segment();
- bool opp = base->fOperand ^ segment->fOperand;
- int maxWinding, oMaxWinding;
- int spanSign = segment->spanSign(angle);
- int oppoSign = segment->oppSign(angle);
- if (opp) {
- oMaxWinding = oWinding;
- oWinding -= spanSign;
- maxWinding = winding;
- if (oppoSign) {
- winding -= oppoSign;
+ int index = 0;
+ do {
+ SkOpAngle* testAngle = (*sorted)[index];
+ int testWinding = testAngle->segment()->windSum(testAngle);
+ if (SK_MinS32 != testWinding && !testAngle->unorderable()) {
+ baseAngle = testAngle;
+ continue;
}
- } else {
- maxWinding = winding;
- winding -= spanSign;
- oMaxWinding = oWinding;
- if (oppoSign) {
- oWinding -= oppoSign;
+ if (testAngle->unorderable()) {
+ baseAngle = NULL;
+ tryReverse = true;
+ continue;
}
- }
- if (segment->windSum(angle) == SK_MinS32) {
- if (opp) {
- if (UseInnerWinding(oMaxWinding, oWinding)) {
- oMaxWinding = oWinding;
- }
- if (oppoSign && UseInnerWinding(maxWinding, winding)) {
- maxWinding = winding;
- }
-#ifdef SK_DEBUG
- SkASSERT(abs(maxWinding) <= gDebugMaxWindSum);
- SkASSERT(abs(oMaxWinding) <= gDebugMaxWindSum);
-#endif
- (void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding);
- } else {
- if (UseInnerWinding(maxWinding, winding)) {
- maxWinding = winding;
- }
- if (oppoSign && UseInnerWinding(oMaxWinding, oWinding)) {
- oMaxWinding = oWinding;
- }
-#ifdef SK_DEBUG
- SkASSERT(abs(maxWinding) <= gDebugMaxWindSum);
- SkASSERT(abs(binary ? oMaxWinding : 0) <= gDebugMaxWindSum);
-#endif
- (void) segment->markAndChaseWinding(angle, maxWinding,
- binary ? oMaxWinding : 0);
+ if (baseAngle) {
+ ComputeOneSum(baseAngle, testAngle, includeType);
+ baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
+ : NULL;
+ tryReverse |= !baseAngle;
+ continue;
}
+ if (finalInitialOrderable + 1 == index) {
+ finalInitialOrderable = index;
+ }
+ } while (++index != last);
+ if (finalInitialOrderable < 0) {
+ break;
}
- } while (++nextIndex != lastIndex);
+ last = finalInitialOrderable + 1;
+ finalInitialOrderable = -2; // make this always negative the second time through
+ } while (baseAngle);
+ if (tryReverse) {
+ baseAngle = NULL;
+ last = 0;
+ finalInitialOrderable = angleCount;
+ do {
+ int index = angleCount;
+ while (--index >= last) {
+ SkOpAngle* testAngle = (*sorted)[index];
+ int testWinding = testAngle->segment()->windSum(testAngle);
+ if (SK_MinS32 != testWinding) {
+ baseAngle = testAngle;
+ continue;
+ }
+ if (testAngle->unorderable()) {
+ baseAngle = NULL;
+ continue;
+ }
+ if (baseAngle) {
+ ComputeOneSumReverse(baseAngle, testAngle, includeType);
+ baseAngle = SK_MinS32 != testAngle->segment()->windSum(testAngle) ? testAngle
+ : NULL;
+ continue;
+ }
+ if (finalInitialOrderable - 1 == index) {
+ finalInitialOrderable = index;
+ }
+ }
+ if (finalInitialOrderable >= angleCount) {
+ break;
+ }
+ last = finalInitialOrderable;
+ finalInitialOrderable = angleCount + 1; // make this inactive 2nd time through
+ } while (baseAngle);
+ }
int minIndex = SkMin32(startIndex, endIndex);
return windSum(minIndex);
}
+void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
+ SkOpAngle::IncludeType includeType) {
+ const SkOpSegment* baseSegment = baseAngle->segment();
+ int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
+ int sumSuWinding;
+ bool binary = includeType >= SkOpAngle::kBinarySingle;
+ if (binary) {
+ sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
+ if (baseSegment->operand()) {
+ SkTSwap<int>(sumMiWinding, sumSuWinding);
+ }
+ }
+ SkOpSegment* nextSegment = nextAngle->segment();
+ int maxWinding, sumWinding;
+ SkOpSpan* last;
+ if (binary) {
+ int oppMaxWinding, oppSumWinding;
+ nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
+ &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
+ last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
+ true, nextAngle);
+ } else {
+ nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
+ &maxWinding, &sumWinding);
+ last = nextSegment->markAngle(maxWinding, sumWinding, true, nextAngle);
+ }
+ nextAngle->setLastMarked(last);
+}
+
+void SkOpSegment::ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
+ SkOpAngle::IncludeType includeType) {
+ const SkOpSegment* baseSegment = baseAngle->segment();
+ int sumMiWinding = baseSegment->updateWinding(baseAngle);
+ int sumSuWinding;
+ bool binary = includeType >= SkOpAngle::kBinarySingle;
+ if (binary) {
+ sumSuWinding = baseSegment->updateOppWinding(baseAngle);
+ if (baseSegment->operand()) {
+ SkTSwap<int>(sumMiWinding, sumSuWinding);
+ }
+ }
+ SkOpSegment* nextSegment = nextAngle->segment();
+ int maxWinding, sumWinding;
+ SkOpSpan* last;
+ if (binary) {
+ int oppMaxWinding, oppSumWinding;
+ nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
+ &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
+ last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
+ true, nextAngle);
+ } else {
+ nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
+ &maxWinding, &sumWinding);
+ last = nextSegment->markAngle(maxWinding, sumWinding, true, nextAngle);
+ }
+ nextAngle->setLastMarked(last);
+}
+
int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT,
bool* hitSomething, double mid, bool opp, bool current) const {
SkScalar bottom = fBounds.fBottom;
@@ -1050,18 +1312,20 @@
return bestTIndex;
}
-void SkOpSegment::decrementSpan(SkOpSpan* span) {
+bool SkOpSegment::decrementSpan(SkOpSpan* span) {
SkASSERT(span->fWindValue > 0);
if (--(span->fWindValue) == 0) {
if (!span->fOppValue && !span->fDone) {
span->fDone = true;
++fDoneSpans;
+ return true;
}
}
+ return false;
}
bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) {
- SkASSERT(!span->fDone);
+ SkASSERT(!span->fDone || span->fTiny);
span->fWindValue += windDelta;
SkASSERT(span->fWindValue >= 0);
span->fOppValue += oppDelta;
@@ -1083,98 +1347,295 @@
// look to see if the curve end intersects an intermediary that intersects the other
void SkOpSegment::checkEnds() {
debugValidate();
- SkTDArray<SkOpSpan> missingSpans;
+ SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
int count = fTs.count();
for (int index = 0; index < count; ++index) {
const SkOpSpan& span = fTs[index];
+ double otherT = span.fOtherT;
+ if (otherT != 0 && otherT != 1) { // only check ends
+ continue;
+ }
const SkOpSegment* other = span.fOther;
- const SkOpSpan* otherSpan = &other->fTs[span.fOtherIndex];
- double otherT = otherSpan->fT;
- if (otherT != 0 && otherT != 1) {
- continue;
- }
+ // peek start/last describe the range of spans that match the other t of this span
int peekStart = span.fOtherIndex;
- while (peekStart > 0) {
- const SkOpSpan* peeker = &other->fTs[peekStart - 1];
- if (peeker->fT != otherT) {
- break;
- }
- --peekStart;
- }
- int otherLast = other->fTs.count() - 1;
+ while (--peekStart >= 0 && other->fTs[peekStart].fT == otherT)
+ ;
+ int otherCount = other->fTs.count();
int peekLast = span.fOtherIndex;
- while (peekLast < otherLast) {
- const SkOpSpan* peeker = &other->fTs[peekLast + 1];
- if (peeker->fT != otherT) {
- break;
- }
- ++peekLast;
- }
- if (peekStart == peekLast) {
+ while (++peekLast < otherCount && other->fTs[peekLast].fT == otherT)
+ ;
+ if (++peekStart == --peekLast) { // if there isn't a range, there's nothing to do
continue;
}
+ // t start/last describe the range of spans that match the t of this span
double t = span.fT;
int tStart = index;
- while (tStart > 0 && t == fTs[tStart - 1].fT) {
- --tStart;
- }
+ while (--tStart >= 0 && (t == fTs[tStart].fT || fTs[tStart].fTiny))
+ ;
int tLast = index;
- int last = count - 1;
- while (tLast < last && t == fTs[tLast + 1].fT) {
+ while (fTs[tLast].fTiny) {
++tLast;
}
+ while (++tLast < count && t == fTs[tLast].fT)
+ ;
for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) {
- if (peekIndex == span.fOtherIndex) {
+ if (peekIndex == span.fOtherIndex) { // skip the other span pointed to by this span
continue;
}
const SkOpSpan& peekSpan = other->fTs[peekIndex];
SkOpSegment* match = peekSpan.fOther;
const double matchT = peekSpan.fOtherT;
- for (int tIndex = tStart; tIndex <= tLast; ++tIndex) {
+ // see if any of the spans match the other spans
+ for (int tIndex = tStart + 1; tIndex < tLast; ++tIndex) {
const SkOpSpan& tSpan = fTs[tIndex];
- if (tSpan.fOther == match && tSpan.fOtherT == matchT) {
- goto nextPeeker;
+ if (tSpan.fOther == match) {
+ if (tSpan.fOtherT == matchT) {
+ goto nextPeeker;
+ }
+ double midT = (tSpan.fOtherT + matchT) / 2;
+ if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
+ goto nextPeeker;
+ }
}
}
+ if (missingSpans.count() > 0) {
+ const MissingSpan& lastMissing = missingSpans.back();
+ if (lastMissing.fCommand == MissingSpan::kAddMissing
+ && lastMissing.fT == t
+ && lastMissing.fOther == match
+ && lastMissing.fOtherT == matchT) {
+ SkASSERT(lastMissing.fPt == peekSpan.fPt);
+ continue;
+ }
+ }
+#if DEBUG_CHECK_ENDS
+ SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,%1.9g)\n",
+ __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, peekSpan.fPt.fY);
+#endif
// this segment is missing a entry that the other contains
// remember so we can add the missing one and recompute the indices
- SkOpSpan* missing = missingSpans.append();
- missing->fT = t;
- missing->fOther = match;
- missing->fOtherT = matchT;
- missing->fPt = peekSpan.fPt;
+ MissingSpan& missing = missingSpans.push_back();
+ SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
+ missing.fCommand = MissingSpan::kAddMissing;
+ missing.fT = t;
+ missing.fOther = match;
+ missing.fOtherT = matchT;
+ missing.fPt = peekSpan.fPt;
}
nextPeeker:
;
}
- int missingCount = missingSpans.count();
- if (missingCount == 0) {
+ if (missingSpans.count() == 0) {
return;
}
+ // if one end is near the other point, look for a coincident span
+ for (int index = 0; index < count; ++index) {
+ const SkOpSpan& span = fTs[index];
+ if (span.fT > 0) {
+ break;
+ }
+ const SkOpSpan& otherSpan = span.fOther->span(span.fOtherIndex);
+ if (span.fNear) {
+ SkASSERT(otherSpan.fPt == fPts[0]);
+ adjustNear(0, span.fPt, &missingSpans);
+ continue;
+ }
+ if (otherSpan.fNear) {
+ SkASSERT(span.fPt == fPts[0]);
+ adjustNear(0, otherSpan.fPt, &missingSpans);
+ }
+ }
+ for (int index = count; --index >= 0; ) {
+ const SkOpSpan& span = fTs[index];
+ if (span.fT < 1) {
+ break;
+ }
+ const SkOpSegment* other = span.fOther;
+ if (span.fNear) {
+ SkASSERT(other->ptAtT(span.fOtherT) == ptAtT(1));
+ const SkPoint& otherPt = other->xyAtT(span.fOtherIndex);
+ SkASSERT(otherPt != ptAtT(1));
+ adjustNear(1, otherPt, &missingSpans);
+ continue;
+ }
+ const SkOpSpan& otherSpan = other->span(span.fOtherIndex);
+ if (otherSpan.fNear) {
+ SkASSERT(otherSpan.fPt == ptAtT(1));
+ SkPoint otherPt = other->ptAtT(span.fOtherT);
+ SkASSERT(otherPt != ptAtT(1));
+ adjustNear(1, otherPt, &missingSpans);
+ }
+ }
debugValidate();
+ int missingCount = missingSpans.count();
for (int index = 0; index < missingCount; ++index) {
- const SkOpSpan& missing = missingSpans[index];
- addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
+ MissingSpan& missing = missingSpans[index];
+ switch (missing.fCommand) {
+ case MissingSpan::kNoAction:
+ break;
+ case MissingSpan::kAddMissing:
+ addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
+ break;
+ case MissingSpan::kRemoveNear: {
+ SkOpSegment* segment = missing.fSegment;
+ int count = segment->count();
+ for (int inner = 0; inner < count; ++inner) {
+ const SkOpSpan& span = segment->span(inner);
+ if (span.fT != missing.fT && span.fOther != missing.fOther) {
+ continue;
+ }
+ SkASSERT(span.fNear);
+ SkOpSegment* other = span.fOther;
+ int otherCount = other->count();
+ for (int otherIndex = 0; otherIndex < otherCount; ++otherIndex) {
+ const SkOpSpan& otherSpan = other->span(otherIndex);
+ if (otherSpan.fT == span.fOtherT && otherSpan.fOther == segment
+ && otherSpan.fOtherT == span.fT) {
+ if (otherSpan.fDone) {
+ other->fDoneSpans--;
+ }
+ other->fTs.remove(otherIndex);
+ // FIXME: remove may leave a tiny dangling -- recompute tiny w/index
+ break;
+ }
+ }
+ if (span.fDone) {
+ segment->fDoneSpans--;
+ }
+ segment->fTs.remove(inner);
+ // FIXME: remove may leave a tiny dangling -- recompute tiny w/index
+ break;
+ }
+ break;
+ }
+ case MissingSpan::kZeroSpan: {
+ SkOpSegment* segment = missing.fSegment;
+ int count = segment->count();
+ for (int inner = 0; inner < count; ++inner) {
+ SkOpSpan& span = segment->fTs[inner];
+ if (span.fT < missing.fT) {
+ continue;
+ }
+ if (span.fT >= missing.fEndT) {
+ break;
+ }
+ span.fWindValue = span.fOppValue = 0;
+ if (!span.fDone) {
+ span.fDone = true;
+ ++segment->fDoneSpans;
+ }
+ }
+ break;
+ }
+ }
}
fixOtherTIndex();
+ // OPTIMIZATION: this may fix indices more than once. Build an array of unique segments to
+ // avoid this
for (int index = 0; index < missingCount; ++index) {
- const SkOpSpan& missing = missingSpans[index];
- missing.fOther->fixOtherTIndex();
+ const MissingSpan& missing = missingSpans[index];
+ switch (missing.fCommand) {
+ case MissingSpan::kNoAction:
+ break;
+ case MissingSpan::kAddMissing:
+ missing.fOther->fixOtherTIndex();
+ break;
+ case MissingSpan::kRemoveNear:
+ missing.fSegment->fixOtherTIndex();
+ missing.fOther->fixOtherTIndex();
+ break;
+ case MissingSpan::kZeroSpan:
+ break;
+ }
}
debugValidate();
}
-bool SkOpSegment::equalPoints(int greaterTIndex, int lesserTIndex) {
- SkASSERT(greaterTIndex >= lesserTIndex);
- double greaterT = fTs[greaterTIndex].fT;
- double lesserT = fTs[lesserTIndex].fT;
- if (greaterT == lesserT) {
+bool SkOpSegment::checkSmall(int index) const {
+ if (fTs[index].fSmall) {
return true;
}
- if (!approximately_negative(greaterT - lesserT)) {
- return false;
+ double tBase = fTs[index].fT;
+ while (index > 0 && precisely_negative(tBase - fTs[--index].fT))
+ ;
+ return fTs[index].fSmall;
+}
+
+// if pair of spans on either side of tiny have the same end point and mid point, mark
+// them as parallel
+// OPTIMIZATION : mark the segment to note that some span is tiny
+void SkOpSegment::checkTiny() {
+ SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
+ SkOpSpan* thisSpan = fTs.begin() - 1;
+ const SkOpSpan* endSpan = fTs.end() - 1; // last can't be tiny
+ while (++thisSpan < endSpan) {
+ if (!thisSpan->fTiny) {
+ continue;
+ }
+ SkOpSpan* nextSpan = thisSpan + 1;
+ double thisT = thisSpan->fT;
+ double nextT = nextSpan->fT;
+ if (thisT == nextT) {
+ continue;
+ }
+ SkASSERT(thisT < nextT);
+ SkASSERT(thisSpan->fPt == nextSpan->fPt);
+ SkOpSegment* thisOther = thisSpan->fOther;
+ SkOpSegment* nextOther = nextSpan->fOther;
+ int oIndex = thisSpan->fOtherIndex;
+ for (int oStep = -1; oStep <= 1; oStep += 2) {
+ int oEnd = thisOther->nextExactSpan(oIndex, oStep);
+ if (oEnd < 0) {
+ continue;
+ }
+ const SkOpSpan& oSpan = thisOther->span(oEnd);
+ int nIndex = nextSpan->fOtherIndex;
+ for (int nStep = -1; nStep <= 1; nStep += 2) {
+ int nEnd = nextOther->nextExactSpan(nIndex, nStep);
+ if (nEnd < 0) {
+ continue;
+ }
+ const SkOpSpan& nSpan = nextOther->span(nEnd);
+ if (oSpan.fPt != nSpan.fPt) {
+ continue;
+ }
+ double oMidT = (thisSpan->fOtherT + oSpan.fT) / 2;
+ const SkPoint& oPt = thisOther->ptAtT(oMidT);
+ double nMidT = (nextSpan->fOtherT + nSpan.fT) / 2;
+ const SkPoint& nPt = nextOther->ptAtT(nMidT);
+ if (!AlmostEqualUlps(oPt, nPt)) {
+ continue;
+ }
+#if DEBUG_CHECK_TINY
+ SkDebugf("%s [%d] add coincidence [%d] [%d]\n", __FUNCTION__, fID,
+ thisOther->fID, nextOther->fID);
+#endif
+ // this segment is missing a entry that the other contains
+ // remember so we can add the missing one and recompute the indices
+ MissingSpan& missing = missingSpans.push_back();
+ SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
+ missing.fCommand = MissingSpan::kAddMissing;
+ missing.fSegment = thisOther;
+ missing.fT = thisSpan->fOtherT;
+ missing.fOther = nextOther;
+ missing.fOtherT = nextSpan->fOtherT;
+ missing.fPt = thisSpan->fPt;
+ }
+ }
}
- return xyAtT(greaterTIndex) == xyAtT(lesserTIndex);
+ int missingCount = missingSpans.count();
+ if (!missingCount) {
+ return;
+ }
+ for (int index = 0; index < missingCount; ++index) {
+ MissingSpan& missing = missingSpans[index];
+ missing.fSegment->addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt);
+ }
+ for (int index = 0; index < missingCount; ++index) {
+ MissingSpan& missing = missingSpans[index];
+ missing.fSegment->fixOtherTIndex();
+ missing.fOther->fixOtherTIndex();
+ }
}
/*
@@ -1214,8 +1675,7 @@
*nextEnd = *nextStart;
do {
*nextEnd += step;
- }
- while (precisely_zero(startT - other->fTs[*nextEnd].fT));
+ } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
*unsortable = true;
@@ -1227,13 +1687,12 @@
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
- addTwoAngles(startIndex, end, &angles);
- buildAngles(end, &angles, true);
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
- bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
+ int calcWinding = computeSum(startIndex, end, SkOpAngle::kBinaryOpp, &angles, &sorted);
+ bool sortable = calcWinding != SK_NaN32;
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
- SkASSERT(firstIndex >= 0);
+ SkASSERT(!sortable || firstIndex >= 0);
#if DEBUG_SORT
debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
#endif
@@ -1277,22 +1736,25 @@
return NULL;
}
foundAngle = nextAngle;
- foundDone = nextSegment->done(nextAngle) && !nextSegment->isTiny(nextAngle);
+ foundDone = nextSegment->done(nextAngle);
}
}
if (nextSegment->done()) {
continue;
}
- if (nextSegment->windSum(nextAngle) != SK_MinS32) {
+ if (nextSegment->isTiny(nextAngle)) {
continue;
}
- SkOpSpan* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding,
- oppSumWinding, activeAngle, nextAngle);
+ if (!activeAngle) {
+ nextSegment->markAndChaseDoneBinary(nextAngle->start(), nextAngle->end());
+ }
+ SkOpSpan* last = nextAngle->lastMarked();
if (last) {
*chase->append() = last;
#if DEBUG_WINDING
- SkDebugf("%s chase.append id=%d\n", __FUNCTION__,
- last->fOther->fTs[last->fOtherIndex].fOther->debugID());
+ SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
+ last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
+ last->fSmall);
#endif
}
} while (++nextIndex != lastIndex);
@@ -1303,7 +1765,6 @@
*nextStart = foundAngle->start();
*nextEnd = foundAngle->end();
nextSegment = foundAngle->segment();
-
#if DEBUG_WINDING
SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
__FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
@@ -1340,22 +1801,24 @@
*nextEnd = *nextStart;
do {
*nextEnd += step;
- }
- while (precisely_zero(startT - other->fTs[*nextEnd].fT));
+ } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count());
+ if (other->isTiny(SkMin32(*nextStart, *nextEnd))) {
+ *unsortable = true;
+ return NULL;
+ }
return other;
}
// more than one viable candidate -- measure angles to find best
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
- addTwoAngles(startIndex, end, &angles);
- buildAngles(end, &angles, true);
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
- bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
+ int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryWinding, &angles, &sorted);
+ bool sortable = calcWinding != SK_NaN32;
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
- SkASSERT(firstIndex >= 0);
+ SkASSERT(!sortable || firstIndex >= 0);
#if DEBUG_SORT
debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
#endif
@@ -1400,15 +1863,19 @@
if (nextSegment->done()) {
continue;
}
- if (nextSegment->windSum(nextAngle) != SK_MinS32) {
+ if (nextSegment->isTiny(nextAngle)) {
continue;
}
- SkOpSpan* last = nextSegment->markAngle(maxWinding, sumWinding, activeAngle, nextAngle);
+ if (!activeAngle) {
+ nextSegment->markAndChaseDoneUnary(nextAngle->start(), nextAngle->end());
+ }
+ SkOpSpan* last = nextAngle->lastMarked();
if (last) {
*chase->append() = last;
#if DEBUG_WINDING
- SkDebugf("%s chase.append id=%d\n", __FUNCTION__,
- last->fOther->fTs[last->fOtherIndex].fOther->debugID());
+ SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
+ last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
+ last->fSmall);
#endif
}
} while (++nextIndex != lastIndex);
@@ -1431,8 +1898,7 @@
const int endIndex = *nextEnd;
SkASSERT(startIndex != endIndex);
SkDEBUGCODE(int count = fTs.count());
- SkASSERT(startIndex < endIndex ? startIndex < count - 1
- : startIndex > 0);
+ SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
int step = SkSign32(endIndex - startIndex);
int end = nextExactSpan(startIndex, step);
SkASSERT(end >= 0);
@@ -1461,14 +1927,11 @@
*nextEnd = *nextStart;
do {
*nextEnd += step;
- }
- while (precisely_zero(startT - other->fTs[*nextEnd].fT));
+ } while (precisely_zero(startT - other->fTs[*nextEnd].fT));
if (other->fTs[SkMin32(*nextStart, *nextEnd)].fWindValue) {
break;
}
-#ifdef SK_DEBUG
SkASSERT(firstLoop);
-#endif
SkDEBUGCODE(firstLoop = false;)
step = -step;
} while (true);
@@ -1478,25 +1941,24 @@
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
- addTwoAngles(startIndex, end, &angles);
- buildAngles(end, &angles, false);
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
- bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind);
- if (!sortable) {
- *unsortable = true;
-#if DEBUG_SORT
- debugShowSort(__FUNCTION__, sorted, findStartingEdge(sorted, startIndex, end), 0, 0,
- sortable);
-#endif
- return NULL;
- }
+ int calcWinding = computeSum(startIndex, end, SkOpAngle::kUnaryXor, &angles, &sorted);
+ bool sortable = calcWinding != SK_NaN32;
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
- SkASSERT(firstIndex >= 0);
+ SkASSERT(!sortable || firstIndex >= 0);
#if DEBUG_SORT
debugShowSort(__FUNCTION__, sorted, firstIndex, 0, 0, sortable);
#endif
+ if (!sortable) {
+ *unsortable = true;
+ return NULL;
+ }
SkASSERT(sorted[firstIndex]->segment() == this);
+#if DEBUG_WINDING
+ SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
+ sorted[firstIndex]->sign());
+#endif
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
const SkOpAngle* foundAngle = NULL;
@@ -1551,138 +2013,6 @@
return firstIndex;
}
-// FIXME: this is tricky code; needs its own unit test
-// note that fOtherIndex isn't computed yet, so it can't be used here
-void SkOpSegment::findTooCloseToCall() {
- int count = fTs.count();
- if (count < 3) { // require t=0, x, 1 at minimum
- return;
- }
- int matchIndex = 0;
- int moCount;
- SkOpSpan* match;
- SkOpSegment* mOther;
- do {
- match = &fTs[matchIndex];
- mOther = match->fOther;
- // FIXME: allow quads, cubics to be near coincident?
- if (mOther->fVerb == SkPath::kLine_Verb) {
- moCount = mOther->fTs.count();
- if (moCount >= 3) {
- break;
- }
- }
- if (++matchIndex >= count) {
- return;
- }
- } while (true); // require t=0, x, 1 at minimum
- // OPTIMIZATION: defer matchPt until qualifying toCount is found?
- const SkPoint* matchPt = &xyAtT(match);
- // look for a pair of nearby T values that map to the same (x,y) value
- // if found, see if the pair of other segments share a common point. If
- // so, the span from here to there is coincident.
- for (int index = matchIndex + 1; index < count; ++index) {
- SkOpSpan* test = &fTs[index];
- if (test->fDone) {
- continue;
- }
- SkOpSegment* tOther = test->fOther;
- if (tOther->fVerb != SkPath::kLine_Verb) {
- continue; // FIXME: allow quads, cubics to be near coincident?
- }
- int toCount = tOther->fTs.count();
- if (toCount < 3) { // require t=0, x, 1 at minimum
- continue;
- }
- const SkPoint* testPt = &xyAtT(test);
- if (*matchPt != *testPt) {
- matchIndex = index;
- moCount = toCount;
- match = test;
- mOther = tOther;
- matchPt = testPt;
- continue;
- }
- int moStart = -1;
- int moEnd = -1;
- double moStartT = 0;
- double moEndT = 0;
- for (int moIndex = 0; moIndex < moCount; ++moIndex) {
- SkOpSpan& moSpan = mOther->fTs[moIndex];
- if (moSpan.fDone) {
- continue;
- }
- if (moSpan.fOther == this) {
- if (moSpan.fOtherT == match->fT) {
- moStart = moIndex;
- moStartT = moSpan.fT;
- }
- continue;
- }
- if (moSpan.fOther == tOther) {
- if (tOther->windValueAt(moSpan.fOtherT) == 0) {
- moStart = -1;
- break;
- }
- SkASSERT(moEnd == -1);
- moEnd = moIndex;
- moEndT = moSpan.fT;
- }
- }
- if (moStart < 0 || moEnd < 0) {
- continue;
- }
- // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test
- if (approximately_equal(moStartT, moEndT)) {
- continue;
- }
- int toStart = -1;
- int toEnd = -1;
- double toStartT = 0;
- double toEndT = 0;
- for (int toIndex = 0; toIndex < toCount; ++toIndex) {
- SkOpSpan& toSpan = tOther->fTs[toIndex];
- if (toSpan.fDone) {
- continue;
- }
- if (toSpan.fOther == this) {
- if (toSpan.fOtherT == test->fT) {
- toStart = toIndex;
- toStartT = toSpan.fT;
- }
- continue;
- }
- if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) {
- if (mOther->windValueAt(toSpan.fOtherT) == 0) {
- moStart = -1;
- break;
- }
- SkASSERT(toEnd == -1);
- toEnd = toIndex;
- toEndT = toSpan.fT;
- }
- }
- // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test
- if (toStart <= 0 || toEnd <= 0) {
- continue;
- }
- if (approximately_equal(toStartT, toEndT)) {
- continue;
- }
- // test to see if the segment between there and here is linear
- if (!mOther->isLinear(moStart, moEnd)
- || !tOther->isLinear(toStart, toEnd)) {
- continue;
- }
- bool flipped = (moStart - moEnd) * (toStart - toEnd) < 1;
- if (flipped) {
- mOther->addTCancel(moStartT, moEndT, tOther, toEndT, toStartT);
- } else {
- mOther->addTCoincident(moStartT, moEndT, tOther, toStartT, toEndT);
- }
- }
-}
-
// FIXME: either:
// a) mark spans with either end unsortable as done, or
// b) rewrite findTop / findTopSegment / findTopContour to iterate further
@@ -1722,14 +2052,24 @@
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
SkASSERT(firstT - end != 0);
addTwoAngles(end, firstT, &angles);
- buildAngles(firstT, &angles, true);
+ if (!buildAngles(firstT, &angles, true) && onlySortable) {
+// *unsortable = true;
+// return NULL;
+ }
SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind);
+ if (onlySortable && !sortable) {
+ *unsortable = true;
+ return NULL;
+ }
int first = SK_MaxS32;
SkScalar top = SK_ScalarMax;
int count = sorted.count();
for (int index = 0; index < count; ++index) {
const SkOpAngle* angle = sorted[index];
+ if (onlySortable && angle->unorderable()) {
+ continue;
+ }
SkOpSegment* next = angle->segment();
SkPathOpsBounds bounds;
next->subDivideBounds(angle->end(), angle->start(), &bounds);
@@ -1742,10 +2082,6 @@
#if DEBUG_SORT // || DEBUG_SWAP_TOP
sorted[first]->segment()->debugShowSort(__FUNCTION__, sorted, first, 0, 0, sortable);
#endif
- if (onlySortable && !sortable) {
- *unsortable = true;
- return NULL;
- }
// skip edges that have already been processed
firstT = first - 1;
SkOpSegment* leftSegment;
@@ -1789,6 +2125,7 @@
// while the following fixes the indices up again, it isn't smart about
// skipping segments whose indices are already correct
// assuming we leave the code that wrote the index in the first place
+// FIXME: if called after remove, this needs to correct tiny
void SkOpSegment::fixOtherTIndex() {
int iCount = fTs.count();
for (int i = 0; i < iCount; ++i) {
@@ -1869,20 +2206,6 @@
(void) markAndChaseWinding(start, end, winding, oppWind);
}
-bool SkOpSegment::isLinear(int start, int end) const {
- if (fVerb == SkPath::kLine_Verb) {
- return true;
- }
- if (fVerb == SkPath::kQuad_Verb) {
- SkDQuad qPart = SkDQuad::SubDivide(fPts, fTs[start].fT, fTs[end].fT);
- return qPart.isLinear(0, 2);
- } else {
- SkASSERT(fVerb == SkPath::kCubic_Verb);
- SkDCubic cPart = SkDCubic::SubDivide(fPts, fTs[start].fT, fTs[end].fT);
- return cPart.isLinear(0, 3);
- }
-}
-
// OPTIMIZE: successive calls could start were the last leaves off
// or calls could specialize to walk forwards or backwards
bool SkOpSegment::isMissing(double startT) const {
@@ -2027,6 +2350,13 @@
} else {
last = markAndChaseDoneUnary(angle, maxWinding);
}
+#if DEBUG_WINDING
+ if (last) {
+ SkDebugf("%s last id=%d windSum=%d small=%d\n", __FUNCTION__,
+ last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
+ last->fSmall);
+ }
+#endif
return last;
}
@@ -2045,6 +2375,13 @@
} else {
last = markAndChaseDoneBinary(angle, maxWinding, oppMaxWinding);
}
+#if DEBUG_WINDING
+ if (last) {
+ SkDebugf("%s last id=%d windSum=%d small=%d\n", __FUNCTION__,
+ last->fOther->fTs[last->fOtherIndex].fOther->debugID(), last->fWindSum,
+ last->fSmall);
+ }
+#endif
return last;
}
@@ -2146,9 +2483,7 @@
debugShowNewWinding(funName, span, winding);
#endif
SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
-#ifdef SK_DEBUG
- SkASSERT(abs(winding) <= gDebugMaxWindSum);
-#endif
+ SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
span.fWindSum = winding;
return &span;
}
@@ -2163,14 +2498,10 @@
debugShowNewWinding(funName, span, winding, oppWinding);
#endif
SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
-#ifdef SK_DEBUG
- SkASSERT(abs(winding) <= gDebugMaxWindSum);
-#endif
+ SkASSERT(abs(winding) <= SkPathOpsDebug::gMaxWindSum);
span.fWindSum = winding;
SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
-#ifdef SK_DEBUG
- SkASSERT(abs(oppWinding) <= gDebugMaxWindSum);
-#endif
+ SkASSERT(abs(oppWinding) <= SkPathOpsDebug::gMaxWindSum);
span.fOppSum = oppWinding;
return &span;
}
@@ -2331,6 +2662,21 @@
}
}
+double SkOpSegment::missingNear(double t, const SkOpSegment* other, const SkPoint& startPt,
+ const SkPoint& endPt) const {
+ int count = this->count();
+ for (int index = 0; index < count; ++index) {
+ const SkOpSpan& span = this->span(index);
+ if (span.fOther == other && span.fPt == startPt) {
+ double midT = (t + span.fT) / 2;
+ if (betweenPoints(midT, startPt, endPt)) {
+ return span.fT;
+ }
+ }
+ }
+ return -1;
+}
+
// 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
@@ -2355,6 +2701,10 @@
SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSpan** last) {
int end = nextExactSpan(*index, step);
SkASSERT(end >= 0);
+ if (fTs[end].fSmall) {
+ *last = NULL;
+ return NULL;
+ }
if (multipleSpans(end)) {
*last = &fTs[end];
return NULL;
@@ -2366,7 +2716,7 @@
int otherEnd = other->nextExactSpan(*index, step);
SkASSERT(otherEnd >= 0);
*min = SkMin32(*index, otherEnd);
- if (other->fTs[*min].fTiny) {
+ if (other->fTs[*min].fSmall) {
*last = NULL;
return NULL;
}
@@ -2397,18 +2747,30 @@
// FIXME
// this returns at any difference in T, vs. a preset minimum. It may be
// that all callers to nextSpan should use this instead.
-// OPTIMIZATION splitting this into separate loops for up/down steps
-// would allow using precisely_negative instead of precisely_zero
int SkOpSegment::nextExactSpan(int from, int step) const {
- const SkOpSpan& fromSpan = fTs[from];
- int count = fTs.count();
int to = from;
- while (step > 0 ? ++to < count : --to >= 0) {
- const SkOpSpan& span = fTs[to];
- if (precisely_zero(span.fT - fromSpan.fT)) {
- continue;
+ if (step < 0) {
+ const SkOpSpan& fromSpan = fTs[from];
+ while (--to >= 0) {
+ const SkOpSpan& span = fTs[to];
+ if (precisely_negative(fromSpan.fT - span.fT) || span.fTiny) {
+ continue;
+ }
+ return to;
}
- return to;
+ } else {
+ while (fTs[from].fTiny) {
+ from++;
+ }
+ const SkOpSpan& fromSpan = fTs[from];
+ int count = fTs.count();
+ while (++to < count) {
+ const SkOpSpan& span = fTs[to];
+ if (precisely_negative(span.fT - fromSpan.fT)) {
+ continue;
+ }
+ return to;
+ }
}
return -1;
}
@@ -2428,6 +2790,16 @@
*oppMaxWinding = *sumSuWinding;
*oppSumWinding = *sumSuWinding -= oppDeltaSum;
}
+ SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
+ SkASSERT(abs(*oppSumWinding) <= SkPathOpsDebug::gMaxWindSum);
+}
+
+void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding,
+ int* maxWinding, int* sumWinding) {
+ int deltaSum = spanSign(index, endIndex);
+ *maxWinding = *sumMiWinding;
+ *sumWinding = *sumMiWinding -= deltaSum;
+ SkASSERT(abs(*sumWinding) <= SkPathOpsDebug::gMaxWindSum);
}
// This marks all spans unsortable so that this info is available for early
@@ -2440,8 +2812,6 @@
bool sortable = true;
int angleCount = angles.count();
int angleIndex;
-// FIXME: caller needs to use SkTArray constructor with reserve count
-// angleList->setReserve(angleCount);
for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
const SkOpAngle& angle = angles[angleIndex];
angleList->push_back(const_cast<SkOpAngle*>(&angle));
@@ -2470,6 +2840,34 @@
return sortable;
}
+// set segments to unsortable if angle is unsortable, but do not set all angles
+// note that for a simple 4 way crossing, two of the edges may be orderable even though
+// two edges are too short to be orderable.
+// perhaps some classes of unsortable angles should make all shared angles unsortable, but
+// simple lines that have tiny crossings are always sortable on the large ends
+// OPTIMIZATION: check earlier when angles are added to input if any are unsortable
+// may make sense then to mark all segments in angle sweep as unsortableStart/unsortableEnd
+// solely for the purpose of short-circuiting future angle building around this center
+bool SkOpSegment::SortAngles2(const SkTArray<SkOpAngle, true>& angles,
+ SkTArray<SkOpAngle*, true>* angleList) {
+ int angleCount = angles.count();
+ int angleIndex;
+ for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) {
+ const SkOpAngle& angle = angles[angleIndex];
+ if (angle.unsortable()) {
+ return false;
+ }
+ angleList->push_back(const_cast<SkOpAngle*>(&angle));
+#if DEBUG_ANGLE
+ (*(angleList->end() - 1))->setID(angleIndex);
+#endif
+ }
+ SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1);
+ // at this point angles are sorted but individually may not be orderable
+ // this means that only adjcent orderable segments may transfer winding
+ return true;
+}
+
// return true if midpoints were computed
bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const {
SkASSERT(start != end);
@@ -2563,11 +2961,19 @@
return fTs[index].fTiny;
}
-void SkOpSegment::TrackOutside(SkTArray<double, true>* outsideTs, double end, double start) {
- int outCount = outsideTs->count();
- if (outCount == 0 || !approximately_negative(end - (*outsideTs)[outCount - 2])) {
- outsideTs->push_back(end);
- outsideTs->push_back(start);
+void SkOpSegment::TrackOutsidePair(SkTArray<SkPoint, true>* outsidePts, const SkPoint& endPt,
+ const SkPoint& startPt) {
+ int outCount = outsidePts->count();
+ if (outCount == 0 || endPt != (*outsidePts)[outCount - 2]) {
+ outsidePts->push_back(endPt);
+ outsidePts->push_back(startPt);
+ }
+}
+
+void SkOpSegment::TrackOutside(SkTArray<SkPoint, true>* outsidePts, const SkPoint& startPt) {
+ int outCount = outsidePts->count();
+ if (outCount == 0 || startPt != (*outsidePts)[outCount - 1]) {
+ outsidePts->push_back(startPt);
}
}
@@ -2615,7 +3021,8 @@
int lesser = SkMin32(index, endIndex);
int winding = windSum(lesser);
int spanWinding = spanSign(index, endIndex);
- if (winding && UseInnerWinding(winding - spanWinding, winding) && winding != SK_MaxS32) {
+ if (winding && UseInnerWinding(winding - spanWinding, winding)
+ && winding != SK_MaxS32) {
winding -= spanWinding;
}
return winding;
@@ -2627,10 +3034,42 @@
return updateWinding(endIndex, startIndex);
}
+int SkOpSegment::updateWindingReverse(int index, int endIndex) const {
+ int lesser = SkMin32(index, endIndex);
+ int winding = windSum(lesser);
+ int spanWinding = spanSign(endIndex, index);
+ if (winding && UseInnerWindingReverse(winding - spanWinding, winding)
+ && winding != SK_MaxS32) {
+ winding -= spanWinding;
+ }
+ return winding;
+}
+
int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) const {
int startIndex = angle->start();
int endIndex = angle->end();
- return updateWinding(startIndex, endIndex);
+ return updateWindingReverse(endIndex, startIndex);
+}
+
+// OPTIMIZATION: does the following also work, and is it any faster?
+// return outerWinding * innerWinding > 0
+// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
+bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
+ SkASSERT(outerWinding != SK_MaxS32);
+ SkASSERT(innerWinding != SK_MaxS32);
+ int absOut = abs(outerWinding);
+ int absIn = abs(innerWinding);
+ bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
+ return result;
+}
+
+bool SkOpSegment::UseInnerWindingReverse(int outerWinding, int innerWinding) {
+ SkASSERT(outerWinding != SK_MaxS32);
+ SkASSERT(innerWinding != SK_MaxS32);
+ int absOut = abs(outerWinding);
+ int absIn = abs(innerWinding);
+ bool result = absOut == absIn ? true : absOut < absIn;
+ return result;
}
int SkOpSegment::windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const {
@@ -2861,9 +3300,17 @@
void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
int first, const int contourWinding,
const int oppContourWinding, bool sortable) const {
- if (--gDebugSortCount < 0) {
+ if (--SkPathOpsDebug::gSortCount < 0) {
return;
}
+ if (!sortable) {
+ if (angles.count() == 0) {
+ return;
+ }
+ if (first < 0) {
+ first = 0;
+ }
+ }
SkASSERT(angles[first]->segment() == this);
SkASSERT(!sortable || angles.count() > 1);
int lastSum = contourWinding;
@@ -2872,8 +3319,9 @@
int windSum = lastSum - spanSign(firstAngle);
int oppoSign = oppSign(firstAngle);
int oppWindSum = oppLastSum - oppoSign;
- #define WIND_AS_STRING(x) char x##Str[12]; if (!valid_wind(x)) strcpy(x##Str, "?"); \
- else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
+ #define WIND_AS_STRING(x) char x##Str[12]; \
+ if (!SkPathOpsDebug::ValidWind(x)) strcpy(x##Str, "?"); \
+ else SK_SNPRINTF(x##Str, sizeof(x##Str), "%d", x)
WIND_AS_STRING(contourWinding);
WIND_AS_STRING(oppContourWinding);
SkDebugf("%s %s contourWinding=%s oppContourWinding=%s sign=%d\n", fun, __FUNCTION__,
@@ -2931,7 +3379,7 @@
SkDebugf(" tStart=%1.9g tEnd=%1.9g", sSpan.fT, eSpan.fT);
#endif
SkDebugf(" sign=%d windValue=%d windSum=", angle.sign(), mSpan.fWindValue);
- winding_printf(mSpan.fWindSum);
+ SkPathOpsDebug::WindingPrintf(mSpan.fWindSum);
int last, wind;
if (opp) {
last = oppLastSum;
@@ -2940,7 +3388,8 @@
last = lastSum;
wind = windSum;
}
- bool useInner = valid_wind(last) && valid_wind(wind) && UseInnerWinding(last, wind);
+ bool useInner = SkPathOpsDebug::ValidWind(last) && SkPathOpsDebug::ValidWind(wind)
+ && UseInnerWinding(last, wind);
WIND_AS_STRING(last);
WIND_AS_STRING(wind);
WIND_AS_STRING(lastSum);
@@ -2954,10 +3403,8 @@
SkDebugf(" %s->%s (%s->%s)", lastStr, windStr, opp ? lastSumStr : oppLastSumStr,
opp ? windSumStr : oppWindSumStr);
}
- SkDebugf(" done=%d tiny=%d opp=%d\n", mSpan.fDone, mSpan.fTiny, opp);
-#if 0 && DEBUG_ANGLE
- angle.debugShow(segment.xyAtT(&sSpan));
-#endif
+ SkDebugf(" done=%d unord=%d small=%d tiny=%d opp=%d\n",
+ mSpan.fDone, angle.unorderable(), mSpan.fSmall, mSpan.fTiny, opp);
++index;
if (index == angles.count()) {
index = 0;
@@ -2970,6 +3417,14 @@
void SkOpSegment::debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles,
int first, bool sortable) {
+ if (!sortable) {
+ if (angles.count() == 0) {
+ return;
+ }
+ if (first < 0) {
+ first = 0;
+ }
+ }
const SkOpAngle* firstAngle = angles[first];
const SkOpSegment* segment = firstAngle->segment();
int winding = segment->updateWinding(firstAngle);
@@ -3025,3 +3480,40 @@
SkASSERT(done == fDoneSpans);
#endif
}
+
+#ifdef SK_DEBUG
+void SkOpSegment::dumpPts() const {
+ int last = SkPathOpsVerbToPoints(fVerb);
+ SkDebugf("{{");
+ int index = 0;
+ do {
+ SkDPoint::DumpSkPoint(fPts[index]);
+ SkDebugf(", ");
+ } while (++index < last);
+ SkDPoint::DumpSkPoint(fPts[index]);
+ SkDebugf("}}\n");
+}
+
+void SkOpSegment::dumpDPts() const {
+ int count = SkPathOpsVerbToPoints(fVerb);
+ SkDebugf("{{");
+ int index = 0;
+ do {
+ SkDPoint dPt = {fPts[index].fX, fPts[index].fY};
+ dPt.dump();
+ if (index != count) {
+ SkDebugf(", ");
+ }
+ } while (++index <= count);
+ SkDebugf("}}\n");
+}
+
+void SkOpSegment::dumpSpans() const {
+ int count = this->count();
+ for (int index = 0; index < count; ++index) {
+ const SkOpSpan& span = this->span(index);
+ SkDebugf("[%d] ", index);
+ span.dump();
+ }
+}
+#endif
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index bfaf4ed..acb114d 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -19,8 +19,8 @@
class SkOpSegment {
public:
SkOpSegment() {
-#if DEBUG_DUMP
- fID = ++gSegmentID;
+#ifdef SK_DEBUG
+ fID = ++SkPathOpsDebug::gSegmentID;
#endif
}
@@ -59,6 +59,11 @@
return done(SkMin32(angle->start(), angle->end()));
}
+ // used only by partial coincidence detection
+ SkDPoint dPtAtT(double mid) const {
+ return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid);
+ }
+
SkVector dxdy(int index) const {
return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT);
}
@@ -234,28 +239,23 @@
bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles);
SkPoint activeLeftTop(bool onlySortable, int* firstT) const;
bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op);
- bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
- int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,
- int* oppMaxWinding, int* oppSumWinding);
bool activeWinding(int index, int endIndex);
- bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);
void addCubic(const SkPoint pts[4], bool operand, bool evenOdd);
void addCurveTo(int start, int end, SkPathWriter* path, bool active) const;
void addLine(const SkPoint pts[2], bool operand, bool evenOdd);
void addOtherT(int index, double otherT, int otherIndex);
void addQuad(const SkPoint pts[3], bool operand, bool evenOdd);
int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT);
- int addT(SkOpSegment* other, const SkPoint& pt, double newT);
- void addTCancel(double startT, double endT, SkOpSegment* other, double oStartT, double oEndT);
- void addTCoincident(double startT, double endT, SkOpSegment* other, double oStartT,
- double oEndT);
+ int addT(SkOpSegment* other, const SkPoint& pt, double newT, bool isNear);
+ void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
+ void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt);
- void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
- const SkPoint& oPt);
- int addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT);
bool betweenTs(int lesser, double testT, int greater) const;
void checkEnds();
- int computeSum(int startIndex, int endIndex, bool binary);
+ bool checkSmall(int index) const;
+ void checkTiny();
+ int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType,
+ SkTArray<SkOpAngle, true>* angles, SkTArray<SkOpAngle*, true>* sorted);
int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething,
double mid, bool opp, bool current) const;
SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
@@ -264,17 +264,13 @@
SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd,
bool* unsortable);
SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable);
- void findTooCloseToCall();
SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable);
void fixOtherTIndex();
void initWinding(int start, int end);
void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind,
- SkScalar hitOppDx);
- bool isLinear(int start, int end) const;
+ SkScalar hitOppDx);
bool isMissing(double startT) const;
- bool isSimple(int end) const;
bool isTiny(const SkOpAngle* angle) const;
- bool isTiny(int index) const;
SkOpSpan* markAndChaseDoneBinary(int index, int endIndex);
SkOpSpan* markAndChaseDoneUnary(int index, int endIndex);
SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding);
@@ -283,12 +279,7 @@
void markDone(int index, int winding);
void markDoneBinary(int index);
void markDoneUnary(int index);
- SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding);
- SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);
- void markWinding(int index, int winding);
- void markWinding(int index, int winding, int oppWinding);
bool nextCandidate(int* start, int* end) const;
- int nextExactSpan(int from, int step) const;
int nextSpan(int from, int step) const;
void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding,
int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding);
@@ -296,9 +287,11 @@
kMustBeOrdered_SortAngleKind, // required for winding calc
kMayBeUnordered_SortAngleKind // ok for find top
};
- static bool SortAngles(const SkTArray<SkOpAngle, true>& angles,
- SkTArray<SkOpAngle*, true>* angleList,
+ static bool SortAngles(const SkTArray<SkOpAngle, true>& angles, // FIXME: replace with
+ SkTArray<SkOpAngle*, true>* angleList, // Sort Angles 2
SortAngleKind );
+ static bool SortAngles2(const SkTArray<SkOpAngle, true>& angles,
+ SkTArray<SkOpAngle*, true>* angleList);
bool subDivide(int start, int end, SkPoint edge[4]) const;
bool subDivide(int start, int end, SkDCubic* result) const;
void undoneSpan(int* start, int* end);
@@ -307,9 +300,8 @@
static bool UseInnerWinding(int outerWinding, int innerWinding);
int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const;
int windSum(const SkOpAngle* angle) const;
- int windValue(const SkOpAngle* angle) const;
-#if DEBUG_DUMP
+#ifdef SK_DEBUG
int debugID() const {
return fID;
}
@@ -331,26 +323,61 @@
#endif
private:
+ struct MissingSpan {
+ enum Command {
+ kNoAction,
+ kAddMissing,
+ kRemoveNear,
+ kZeroSpan,
+ } fCommand;
+ double fT;
+ double fEndT;
+ SkOpSegment* fSegment;
+ SkOpSegment* fOther;
+ double fOtherT;
+ SkPoint fPt;
+ };
+
bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles);
bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles);
+ bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op,
+ int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding,
+ int* oppMaxWinding, int* oppSumWinding);
+ bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding);
void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const;
- void addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd);
- void addCoinOutsides(const SkTArray<double, true>& outsideTs, SkOpSegment* other, double oEnd);
+ void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
+ void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other);
+ void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt,
+ const SkPoint& oPt);
void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const;
- int advanceCoincidentOther(const SkOpSpan* test, double oEndT, int oIndex);
- int advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int index);
- void buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
+ void adjustMissingNear(const SkPoint& startPt, const SkPoint& endPt,
+ SkTArray<MissingSpan, true>* );
+ void adjustNear(double startT, const SkPoint& endPt, SkTArray<MissingSpan, true>* );
+ void adjustOtherNear(double startT, const SkPoint& startPt, const SkPoint& endPt,
+ SkTArray<MissingSpan, true>* );
+ MissingSpan::Command adjustThisNear(double startT, const SkPoint& startPt, const SkPoint& endPt,
+ SkTArray<MissingSpan, true>* );
+ int advanceCoincidentOther(double oEndT, int oIndex);
+ int advanceCoincidentThis(int index);
+ bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const;
+ bool buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const;
void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const;
- int bumpCoincidentThis(const SkOpSpan& oTest, bool opp, int index,
- SkTArray<double, true>* outsideTs);
- int bumpCoincidentOther(const SkOpSpan& test, double oEndT, int& oIndex,
- SkTArray<double, true>* oOutsideTs);
+ void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index,
+ SkTArray<SkPoint, true>* outsideTs);
+ bool bumpCoincident(SkOpSpan* test, bool bigger, bool binary);
+ void bumpCoincidentOther(const SkOpSpan& oTest, int* index,
+ SkTArray<SkPoint, true>* outsideTs);
bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta);
bool clockwise(int tStart, int tEnd) const;
- void decrementSpan(SkOpSpan* span);
- bool equalPoints(int greaterTIndex, int lesserTIndex);
+ static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
+ SkOpAngle::IncludeType );
+ static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
+ SkOpAngle::IncludeType );
+ bool decrementSpan(SkOpSpan* span);
int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end);
void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd);
+ bool isSimple(int end) const;
+ bool isTiny(int index) const;
void matchWindingValue(int tIndex, double t, bool borrowWind);
SkOpSpan* markAndChaseDone(int index, int endIndex, int winding);
SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding);
@@ -363,19 +390,33 @@
void markOneDoneBinary(const char* funName, int tIndex);
void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding);
void markOneDoneUnary(const char* funName, int tIndex);
+ SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding);
+ SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding);
+ void markWinding(int index, int winding);
+ void markWinding(int index, int winding, int oppWinding);
void markUnsortable(int start, int end);
bool monotonicInY(int tStart, int tEnd) const;
+ double missingNear(double otherT, const SkOpSegment* other, const SkPoint& startPt,
+ const SkPoint& endPt) const;
bool multipleSpans(int end) const;
SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last);
+ int nextExactSpan(int from, int step) const;
bool serpentine(int tStart, int tEnd) const;
+ void setUpWindings(int index, int endIndex, int* sumMiWinding,
+ int* maxWinding, int* sumWinding);
void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const;
- static void TrackOutside(SkTArray<double, true>* outsideTs, double end, double start);
+ static void TrackOutsidePair(SkTArray<SkPoint, true>* outsideTs, const SkPoint& endPt,
+ const SkPoint& startPt);
+ static void TrackOutside(SkTArray<SkPoint, true>* outsideTs, const SkPoint& startPt);
int updateOppWinding(int index, int endIndex) const;
int updateOppWinding(const SkOpAngle* angle) const;
int updateWinding(int index, int endIndex) const;
int updateWinding(const SkOpAngle* angle) const;
+ int updateWindingReverse(int index, int endIndex) const;
+ static bool UseInnerWindingReverse(int outerWinding, int innerWinding);
SkOpSpan* verifyOneWinding(const char* funName, int tIndex);
SkOpSpan* verifyOneWindingU(const char* funName, int tIndex);
+ int windValue(const SkOpAngle* angle) const;
int windValueAt(double t) const;
void zeroSpan(SkOpSpan* span);
@@ -395,6 +436,11 @@
}
#endif
void debugValidate() const;
+#ifdef SK_DEBUG
+ void dumpPts() const;
+ void dumpDPts() const;
+ void dumpSpans() const;
+#endif
const SkPoint* fPts;
SkPathOpsBounds fBounds;
@@ -407,7 +453,7 @@
bool fOperand;
bool fXor; // set if original contour had even-odd fill
bool fOppXor; // set if opposite operand had even-odd fill
-#if DEBUG_DUMP
+#ifdef SK_DEBUG
int fID;
#endif
};
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index 3666623..50c76d2 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -12,6 +12,10 @@
class SkOpSegment;
struct SkOpSpan {
+ enum PointMatch {
+ kPointIsExact,
+ kPointIsNear
+ };
SkOpSegment* fOther;
SkPoint fPt; // computed when the curves are intersected
double fT;
@@ -24,8 +28,14 @@
bool fDone; // if set, this span to next higher T has been processed
bool fUnsortableStart; // set when start is part of an unsortable pair
bool fUnsortableEnd; // set when end is part of an unsortable pair
+ bool fSmall; // if set, consecutive points are almost equal
bool fTiny; // if set, span may still be considered once for edge following
bool fLoop; // set when a cubic loops back to this point
+ bool fNear; // set if point is near segment end point
+
+#ifdef SK_DEBUG
+ void dump() const;
+#endif
};
#endif
diff --git a/src/pathops/SkPathOpsBounds.h b/src/pathops/SkPathOpsBounds.h
index 61ef7bb..07ad5d4 100644
--- a/src/pathops/SkPathOpsBounds.h
+++ b/src/pathops/SkPathOpsBounds.h
@@ -13,8 +13,10 @@
// SkPathOpsBounds, unlike SkRect, does not consider a line to be empty.
struct SkPathOpsBounds : public SkRect {
static bool Intersects(const SkPathOpsBounds& a, const SkPathOpsBounds& b) {
- return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
- a.fTop <= b.fBottom && b.fTop <= a.fBottom;
+ return AlmostLessOrEqualUlps(a.fLeft, b.fRight)
+ && AlmostLessOrEqualUlps(b.fLeft, a.fRight)
+ && AlmostLessOrEqualUlps(a.fTop, b.fBottom)
+ && AlmostLessOrEqualUlps(b.fTop, a.fBottom);
}
// Note that add(), unlike SkRect::join() or SkRect::growToInclude()
@@ -38,6 +40,13 @@
if (pt.fY > fBottom) fBottom = pt.fY;
}
+ bool almostContains(const SkPoint& pt) {
+ return AlmostLessOrEqualUlps(fLeft, pt.fX)
+ && AlmostLessOrEqualUlps(pt.fX, fRight)
+ && AlmostLessOrEqualUlps(fTop, pt.fY)
+ && AlmostLessOrEqualUlps(pt.fY, fBottom);
+ }
+
// unlike isEmpty(), this permits lines, but not points
// FIXME: unused for now
bool isReallyEmpty() const {
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 28cf59c..7dd13a7 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -250,6 +250,9 @@
*topLeft = bestXY;
result = topStart->findTop(index, endIndex, unsortable, onlySortable);
} while (!result);
+ if (result) {
+ *unsortable = false;
+ }
return result;
}
@@ -288,9 +291,9 @@
}
}
-SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bool* firstContour,
- int* indexPtr, int* endIndexPtr, SkPoint* topLeft, bool* unsortable,
- bool* done, bool binary) {
+SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
+ SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
+ int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done) {
SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
done, true);
if (!current) {
@@ -308,8 +311,11 @@
if (sumWinding != SK_MinS32) {
return current;
}
- sumWinding = current->computeSum(index, endIndex, binary);
- if (sumWinding != SK_MinS32) {
+ SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32);
+ SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
+ SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
+ sumWinding = current->computeSum(index, endIndex, angleIncludeType, &angles, &sorted);
+ if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) {
return current;
}
int contourWinding;
@@ -333,7 +339,7 @@
if (tryAgain) {
continue;
}
- if (!binary) {
+ if (angleIncludeType < SkOpAngle::kBinarySingle) {
break;
}
oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit,
@@ -354,6 +360,15 @@
}
}
+// A tiny interval may indicate an undiscovered coincidence. Find and fix.
+void CheckTiny(SkTArray<SkOpContour*, true>* contourList) {
+ int contourCount = (*contourList).count();
+ for (int cTest = 0; cTest < contourCount; ++cTest) {
+ SkOpContour* contour = (*contourList)[cTest];
+ contour->checkTiny();
+ }
+}
+
void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
int contourCount = (*contourList).count();
for (int cTest = 0; cTest < contourCount; ++cTest) {
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index 4ba4af2..e1ae998 100644
--- a/src/pathops/SkPathOpsCommon.h
+++ b/src/pathops/SkPathOpsCommon.h
@@ -7,6 +7,7 @@
#ifndef SkPathOpsCommon_DEFINED
#define SkPathOpsCommon_DEFINED
+#include "SkOpAngle.h"
#include "SkOpContour.h"
#include "SkTDArray.h"
@@ -14,11 +15,12 @@
void Assemble(const SkPathWriter& path, SkPathWriter* simple);
void CheckEnds(SkTArray<SkOpContour*, true>* contourList);
+void CheckTiny(SkTArray<SkOpContour*, true>* contourList);
// FIXME: find chase uses insert, so it can't be converted to SkTArray yet
SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex);
-SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bool* firstContour,
- int* index, int* endIndex, SkPoint* topLeft, bool* unsortable,
- bool* done, bool binary);
+SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& , SkOpAngle::IncludeType ,
+ bool* firstContour, int* index, int* endIndex, SkPoint* topLeft,
+ bool* unsortable, bool* done);
SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end);
void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList);
void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list,
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index 5fbfeba..662219a 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -129,7 +129,7 @@
sk_bzero(str, sizeof(str));
SK_SNPRINTF(str, sizeof(str), "Solve[%1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]",
A, B, C, D);
- mathematica_ize(str, sizeof(str));
+ SkPathOpsDebug::MathematicaIze(str, sizeof(str));
#if ONE_OFF_DEBUG && ONE_OFF_DEBUG_MATHEMATICA
SkDebugf("%s\n", str);
#endif
@@ -508,3 +508,16 @@
interp_cubic_coords(&fPts[0].fY, &dst.pts[0].fY, t);
return dst;
}
+
+#ifdef SK_DEBUG
+void SkDCubic::dump() {
+ SkDebugf("{{");
+ int index = 0;
+ do {
+ fPts[index].dump();
+ SkDebugf(", ");
+ } while (++index < 3);
+ fPts[index].dump();
+ SkDebugf("}}\n");
+}
+#endif
diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h
index 1ba35be..973b76d 100644
--- a/src/pathops/SkPathOpsCubic.h
+++ b/src/pathops/SkPathOpsCubic.h
@@ -77,6 +77,10 @@
SkDPoint top(double startT, double endT) const;
void toQuadraticTs(double precision, SkTArray<double, true>* ts) const;
SkDQuad toQuad() const;
+
+#ifdef SK_DEBUG
+ void dump();
+#endif
};
#endif
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 1436c8e..0505965 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -10,10 +10,23 @@
#if defined SK_DEBUG || !FORCE_RELEASE
-int gDebugMaxWindSum = SK_MaxS32;
-int gDebugMaxWindValue = SK_MaxS32;
+int SkPathOpsDebug::gMaxWindSum = SK_MaxS32;
+int SkPathOpsDebug::gMaxWindValue = SK_MaxS32;
-void mathematica_ize(char* str, size_t bufferLen) {
+const char* SkPathOpsDebug::kLVerbStr[] = {"", "line", "quad", "cubic"};
+int SkPathOpsDebug::gContourID;
+int SkPathOpsDebug::gSegmentID;
+
+#if DEBUG_SORT || DEBUG_SWAP_TOP
+int SkPathOpsDebug::gSortCountDefault = SK_MaxS32;
+int SkPathOpsDebug::gSortCount;
+#endif
+
+#if DEBUG_ACTIVE_OP
+const char* SkPathOpsDebug::kPathOpStr[] = {"diff", "sect", "union", "xor"};
+#endif
+
+void SkPathOpsDebug::MathematicaIze(char* str, size_t bufferLen) {
size_t len = strlen(str);
bool num = false;
for (size_t idx = 0; idx < len; ++idx) {
@@ -29,48 +42,29 @@
num = str[idx] >= '0' && str[idx] <= '9';
}
}
-#endif
-#if DEBUG_SORT || DEBUG_SWAP_TOP
-bool valid_wind(int wind) {
+bool SkPathOpsDebug::ValidWind(int wind) {
return wind > SK_MinS32 + 0xFFFF && wind < SK_MaxS32 - 0xFFFF;
}
-void winding_printf(int wind) {
+void SkPathOpsDebug::WindingPrintf(int wind) {
if (wind == SK_MinS32) {
SkDebugf("?");
} else {
SkDebugf("%d", wind);
}
}
-#endif
-
-#if DEBUG_DUMP
-const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
-// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
-int gContourID;
-int gSegmentID;
-#endif
-
-#if DEBUG_SORT || DEBUG_SWAP_TOP
-int gDebugSortCountDefault = SK_MaxS32;
-int gDebugSortCount;
-#endif
-
-#if DEBUG_ACTIVE_OP
-const char* kPathOpStr[] = {"diff", "sect", "union", "xor"};
-#endif
#if DEBUG_SHOW_TEST_NAME
-void* PathOpsDebugCreateNameStr() {
+void* SkPathOpsDebug::CreateNameStr() {
return SkNEW_ARRAY(char, DEBUG_FILENAME_STRING_LENGTH);
}
-void PathOpsDebugDeleteNameStr(void* v) {
+void SkPathOpsDebug::DeleteNameStr(void* v) {
SkDELETE_ARRAY(reinterpret_cast<char* >(v));
}
-void DebugBumpTestName(char* test) {
+void SkPathOpsDebug::BumpTestName(char* test) {
char* num = test + strlen(test);
while (num[-1] >= '0' && num[-1] <= '9') {
--num;
@@ -86,3 +80,56 @@
SK_SNPRINTF(num, DEBUG_FILENAME_STRING_LENGTH - (num - test), "%d", dec);
}
#endif
+
+#include "SkOpSegment.h"
+
+void SkPathOpsDebug::DumpAngles(const SkTArray<SkOpAngle, true>& angles) {
+ int count = angles.count();
+ for (int index = 0; index < count; ++index) {
+ angles[index].dump();
+ }
+}
+#endif // SK_DEBUG || !FORCE_RELEASE
+
+#ifdef SK_DEBUG
+void SkOpSpan::dump() const {
+ SkDebugf("t=");
+ DebugDumpDouble(fT);
+ SkDebugf(" pt=");
+ SkDPoint::DumpSkPoint(fPt);
+ SkDebugf(" other.fID=%d", fOther->debugID());
+ SkDebugf(" [%d] otherT=", fOtherIndex);
+ DebugDumpDouble(fOtherT);
+ SkDebugf(" windSum=");
+ SkPathOpsDebug::WindingPrintf(fWindSum);
+ if (SkPathOpsDebug::ValidWind(fOppSum) || fOppValue != 0) {
+ SkDebugf(" oppSum=");
+ SkPathOpsDebug::WindingPrintf(fOppSum);
+ }
+ SkDebugf(" windValue=%d", fWindValue);
+ if (SkPathOpsDebug::ValidWind(fOppSum) || fOppValue != 0) {
+ SkDebugf(" oppValue=%d", fOppValue);
+ }
+ if (fDone) {
+ SkDebugf(" done");
+ }
+ if (fUnsortableStart) {
+ SkDebugf(" unsortable-start");
+ }
+ if (fUnsortableEnd) {
+ SkDebugf(" unsortable-end");
+ }
+ if (fTiny) {
+ SkDebugf(" tiny");
+ } else if (fSmall) {
+ SkDebugf(" small");
+ }
+ if (fLoop) {
+ SkDebugf(" loop");
+ }
+ if (fNear) {
+ SkDebugf(" near");
+ }
+ SkDebugf("\n");
+}
+#endif
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index e4ef072..912f2f5 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -30,15 +30,6 @@
#define SK_SNPRINTF snprintf
#endif
-#if defined SK_DEBUG || !FORCE_RELEASE
-
-void mathematica_ize(char* str, size_t bufferSize);
-
-extern int gDebugMaxWindSum;
-extern int gDebugMaxWindValue;
-
-#endif
-
#if FORCE_RELEASE
#define DEBUG_ACTIVE_OP 0
@@ -50,6 +41,8 @@
#define DEBUG_ANGLE 0
#define DEBUG_AS_C_CODE 1
#define DEBUG_ASSEMBLE 0
+#define DEBUG_CHECK_ENDS 0
+#define DEBUG_CHECK_TINY 0
#define DEBUG_CONCIDENT 0
#define DEBUG_CROSS 0
#define DEBUG_FLAT_QUADS 0
@@ -61,6 +54,7 @@
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 0
#define DEBUG_SORT_COMPACT 0
+#define DEBUG_SORT_RAW 0
#define DEBUG_SORT_SINGLE 0
#define DEBUG_SWAP_TOP 0
#define DEBUG_UNSORTABLE 0
@@ -80,8 +74,10 @@
#define DEBUG_ANGLE 1
#define DEBUG_AS_C_CODE 1
#define DEBUG_ASSEMBLE 1
+#define DEBUG_CHECK_ENDS 1
+#define DEBUG_CHECK_TINY 1
#define DEBUG_CONCIDENT 1
-#define DEBUG_CROSS 0
+#define DEBUG_CROSS 01
#define DEBUG_FLAT_QUADS 0
#define DEBUG_FLOW 1
#define DEBUG_MARK_DONE 1
@@ -91,6 +87,7 @@
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 1
#define DEBUG_SORT_COMPACT 0
+#define DEBUG_SORT_RAW 0
#define DEBUG_SORT_SINGLE 0
#define DEBUG_SWAP_TOP 1
#define DEBUG_UNSORTABLE 1
@@ -101,9 +98,6 @@
#endif
-#define DEBUG_DUMP (DEBUG_ACTIVE_OP | DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | \
- DEBUG_SORT_SINGLE | DEBUG_PATH_CONSTRUCTION)
-
#if DEBUG_AS_C_CODE
#define CUBIC_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}"
#define QUAD_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}"
@@ -122,39 +116,52 @@
#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
-#if DEBUG_DUMP
-extern const char* kLVerbStr[];
-// extern const char* kUVerbStr[];
-extern int gContourID;
-extern int gSegmentID;
-#endif
-
-#if DEBUG_SORT || DEBUG_SWAP_TOP
-extern int gDebugSortCountDefault;
-extern int gDebugSortCount;
-
-bool valid_wind(int winding);
-void winding_printf(int winding);
-#endif
-
-#if DEBUG_ACTIVE_OP
-extern const char* kPathOpStr[];
-#endif
-
-#if DEBUG_SHOW_TEST_NAME
-#include "SkTLS.h"
-
-extern void* PathOpsDebugCreateNameStr();
-extern void PathOpsDebugDeleteNameStr(void* v);
-#define DEBUG_FILENAME_STRING_LENGTH 64
-#define DEBUG_FILENAME_STRING \
- (reinterpret_cast<char* >(SkTLS::Get(PathOpsDebugCreateNameStr, PathOpsDebugDeleteNameStr)))
-extern void DebugBumpTestName(char* );
-extern void DebugShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name);
-#endif
-
#ifndef DEBUG_TEST
#define DEBUG_TEST 0
#endif
+#if defined SK_DEBUG || !FORCE_RELEASE
+
+#if DEBUG_SHOW_TEST_NAME
+#include "SkTLS.h"
+#endif
+
+#include "SkTArray.h"
+
+class SkPathOpsDebug {
+public:
+ static int gMaxWindSum;
+ static int gMaxWindValue;
+
+ static const char* kLVerbStr[];
+ static int gContourID;
+ static int gSegmentID;
+
+#if DEBUG_SORT || DEBUG_SWAP_TOP
+ static int gSortCountDefault;
+ static int gSortCount;
+#endif
+
+#if DEBUG_ACTIVE_OP
+ static const char* kPathOpStr[];
+#endif
+
+ static void MathematicaIze(char* str, size_t bufferSize);
+ static bool ValidWind(int winding);
+ static void WindingPrintf(int winding);
+
+#if DEBUG_SHOW_TEST_NAME
+ static void* CreateNameStr();
+ static void DeleteNameStr(void* v);
+#define DEBUG_FILENAME_STRING_LENGTH 64
+#define DEBUG_FILENAME_STRING (reinterpret_cast<char* >(SkTLS::Get(SkPathOpsDebug::CreateNameStr, \
+ SkPathOpsDebug::DeleteNameStr)))
+ static void BumpTestName(char* );
+ static void ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, const char* name);
+#endif
+ static void DumpAngles(const SkTArray<class SkOpAngle, true>& angles);
+};
+
+#endif // SK_DEBUG || !FORCE_RELEASE
+
#endif
diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp
index 48c042a..1b548fc 100644
--- a/src/pathops/SkPathOpsLine.cpp
+++ b/src/pathops/SkPathOpsLine.cpp
@@ -78,9 +78,7 @@
}
double t = numer / denom;
SkDPoint realPt = ptAtT(t);
- SkDVector distU = xy - realPt;
- double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
- double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
+ double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
// find the ordinal in the original line with the largest unsigned exponent
double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
@@ -93,6 +91,35 @@
return t;
}
+bool SkDLine::nearRay(const SkDPoint& xy) const {
+ // project a perpendicular ray from the point to the line; find the T on the line
+ SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
+ double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay
+ SkDVector ab0 = xy - fPts[0];
+ double numer = len.fX * ab0.fX + ab0.fY * len.fY;
+ double t = numer / denom;
+ SkDPoint realPt = ptAtT(t);
+ double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
+ // find the ordinal in the original line with the largest unsigned exponent
+ double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
+ double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
+ largest = SkTMax(largest, -tiniest);
+ return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
+}
+
+// Returns true if a ray from (0,0) to (x1,y1) is coincident with a ray (0,0) to (x2,y2)
+// OPTIMIZE: a specialty routine could speed this up -- may not be called very often though
+bool SkDLine::NearRay(double x1, double y1, double x2, double y2) {
+ double denom1 = x1 * x1 + y1 * y1;
+ double denom2 = x2 * x2 + y2 * y2;
+ SkDLine line = {{{0, 0}, {x1, y1}}};
+ SkDPoint pt = {x2, y2};
+ if (denom2 > denom1) {
+ SkTSwap(line[1], pt);
+ }
+ return line.nearRay(pt);
+}
+
double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
if (xy.fY == y) {
if (xy.fX == left) {
@@ -106,7 +133,7 @@
}
double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
- if (!AlmostEqualUlps(xy.fY, y)) {
+ if (!AlmostBequalUlps(xy.fY, y)) {
return -1;
}
if (!AlmostBetweenUlps(left, xy.fX, right)) {
@@ -115,6 +142,18 @@
double t = (xy.fX - left) / (right - left);
t = SkPinT(t);
SkASSERT(between(0, t, 1));
+ double realPtX = (1 - t) * left + t * right;
+ SkDVector distU = {xy.fY - y, xy.fX - realPtX};
+ double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
+ double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
+ double tiniest = SkTMin(SkTMin(y, left), right);
+ double largest = SkTMax(SkTMax(y, left), right);
+ largest = SkTMax(largest, -tiniest);
+ if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
+ return -1;
+ }
+ t = SkPinT(t);
+ SkASSERT(between(0, t, 1));
return t;
}
@@ -131,7 +170,7 @@
}
double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
- if (!AlmostEqualUlps(xy.fX, x)) {
+ if (!AlmostBequalUlps(xy.fX, x)) {
return -1;
}
if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
@@ -140,5 +179,27 @@
double t = (xy.fY - top) / (bottom - top);
t = SkPinT(t);
SkASSERT(between(0, t, 1));
+ double realPtY = (1 - t) * top + t * bottom;
+ SkDVector distU = {xy.fX - x, xy.fY - realPtY};
+ double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
+ double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
+ double tiniest = SkTMin(SkTMin(x, top), bottom);
+ double largest = SkTMax(SkTMax(x, top), bottom);
+ largest = SkTMax(largest, -tiniest);
+ if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
+ return -1;
+ }
+ t = SkPinT(t);
+ SkASSERT(between(0, t, 1));
return t;
}
+
+#ifdef SK_DEBUG
+void SkDLine::dump() {
+ SkDebugf("{{");
+ fPts[0].dump();
+ SkDebugf(", ");
+ fPts[1].dump();
+ SkDebugf("}}\n");
+}
+#endif
diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h
index 75f3bd1..a3cfcf2 100644
--- a/src/pathops/SkPathOpsLine.h
+++ b/src/pathops/SkPathOpsLine.h
@@ -31,10 +31,16 @@
static double ExactPointV(const SkDPoint& xy, double top, double bottom, double x);
double isLeft(const SkDPoint& pt) const;
double nearPoint(const SkDPoint& xy) 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);
+ static bool NearRay(double dx1, double dy1, double dx2, double dy2);
SkDPoint ptAtT(double t) const;
SkDLine subDivide(double t1, double t2) const;
+
+#ifdef SK_DEBUG
+ void dump();
+#endif
private:
SkDVector tangent() const { return fPts[0] - fPts[1]; }
};
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 71efeee..e532fda 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -49,10 +49,19 @@
// find first angle, initialize winding to computed fWindSum
int firstIndex = -1;
const SkOpAngle* angle;
+ bool foundAngle = true;
do {
- angle = sorted[++firstIndex];
+ ++firstIndex;
+ if (firstIndex >= angleCount) {
+ foundAngle = false;
+ break;
+ }
+ angle = sorted[firstIndex];
segment = angle->segment();
} while (segment->windSum(angle) == SK_MinS32);
+ if (!foundAngle) {
+ continue;
+ }
#if DEBUG_SORT
segment->debugShowSort(__FUNCTION__, sorted, firstIndex, sortable);
#endif
@@ -135,8 +144,8 @@
do {
int index, endIndex;
bool done;
- SkOpSegment* current = FindSortableTop(contourList, &firstContour, &index, &endIndex,
- &topLeft, &topUnsortable, &done, true);
+ SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
+ &index, &endIndex, &topLeft, &topUnsortable, &done);
if (!current) {
if (topUnsortable || !done) {
topUnsortable = false;
@@ -185,8 +194,12 @@
} while (!simple->isClosed() && (!unsortable
|| !current->done(SkMin32(index, endIndex))));
if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
- SkASSERT(unsortable || simple->isEmpty());
+ // FIXME : add to simplify, xor cpaths
int min = SkMin32(index, endIndex);
+ if (!unsortable && !simple->isEmpty()) {
+ unsortable = current->checkSmall(min);
+ }
+ SkASSERT(unsortable || simple->isEmpty());
if (!current->done(min)) {
current->addCurveTo(index, endIndex, simple, true);
current->markDoneBinary(min);
@@ -235,8 +248,8 @@
#if DEBUG_SHOW_TEST_NAME
char* debugName = DEBUG_FILENAME_STRING;
if (debugName && debugName[0]) {
- DebugBumpTestName(debugName);
- DebugShowPath(one, two, op, debugName);
+ SkPathOpsDebug::BumpTestName(debugName);
+ SkPathOpsDebug::ShowPath(one, two, op, debugName);
}
#endif
op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
@@ -250,7 +263,7 @@
op = kDifference_PathOp;
}
#if DEBUG_SORT || DEBUG_SWAP_TOP
- gDebugSortCount = gDebugSortCountDefault;
+ SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
#endif
// turn path into list of segments
SkTArray<SkOpContour> contours;
@@ -300,6 +313,7 @@
#endif
FixOtherTIndex(&contourList);
CheckEnds(&contourList);
+ CheckTiny(&contourList);
SortSegments(&contourList);
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
DebugShowActiveSpans(contourList);
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index 045b1b4..51216b6 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -159,6 +159,24 @@
double roughlyEqual(const SkDPoint& a) const {
return roughly_equal(a.fY, fY) && roughly_equal(a.fX, fX);
}
+
+ #ifdef SK_DEBUG
+ void dump() {
+ SkDebugf("{");
+ DebugDumpDouble(fX);
+ SkDebugf(", ");
+ DebugDumpDouble(fY);
+ SkDebugf("}");
+ }
+
+ static void DumpSkPoint(const SkPoint& pt) {
+ SkDebugf("{");
+ DebugDumpFloat(pt.fX);
+ SkDebugf(", ");
+ DebugDumpFloat(pt.fY);
+ SkDebugf("}");
+ }
+ #endif
};
#endif
diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp
index 7d9ff52..1bd7796 100644
--- a/src/pathops/SkPathOpsQuad.cpp
+++ b/src/pathops/SkPathOpsQuad.cpp
@@ -340,3 +340,16 @@
*a -= *b; // a = A - 2*B + C
*b -= *c; // b = 2*B - 2*C
}
+
+#ifdef SK_DEBUG
+void SkDQuad::dump() {
+ SkDebugf("{{");
+ int index = 0;
+ do {
+ fPts[index].dump();
+ SkDebugf(", ");
+ } while (++index < 2);
+ fPts[index].dump();
+ SkDebugf("}}\n");
+}
+#endif
diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h
index c865051..69d5a6d 100644
--- a/src/pathops/SkPathOpsQuad.h
+++ b/src/pathops/SkPathOpsQuad.h
@@ -61,6 +61,10 @@
}
SkDCubic toCubic() const;
SkDPoint top(double startT, double endT) const;
+
+#ifdef SK_DEBUG
+ void dump();
+#endif
private:
// static double Tangent(const double* quadratic, double t); // uncalled
};
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index 4887789..76e3413 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -17,8 +17,8 @@
do {
int index, endIndex;
bool topDone;
- SkOpSegment* current = FindSortableTop(contourList, &firstContour, &index, &endIndex,
- &topLeft, &topUnsortable, &topDone, false);
+ SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kUnaryWinding, &firstContour,
+ &index, &endIndex, &topLeft, &topUnsortable, &topDone);
if (!current) {
if (topUnsortable || !topDone) {
topUnsortable = false;
@@ -149,7 +149,7 @@
// FIXME : add this as a member of SkPath
bool Simplify(const SkPath& path, SkPath* result) {
#if DEBUG_SORT || DEBUG_SWAP_TOP
- gDebugSortCount = gDebugSortCountDefault;
+ SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
#endif
// returns 1 for evenodd, -1 for winding, regardless of inverse-ness
SkPath::FillType fillType = path.isInverseFillType() ? SkPath::kInverseEvenOdd_FillType
@@ -186,6 +186,7 @@
CoincidenceCheck(&contourList, 0);
FixOtherTIndex(&contourList);
CheckEnds(&contourList);
+ CheckTiny(&contourList);
SortSegments(&contourList);
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
DebugShowActiveSpans(contourList);
diff --git a/src/pathops/SkPathOpsSpan.h b/src/pathops/SkPathOpsSpan.h
deleted file mode 100644
index 3396592..0000000
--- a/src/pathops/SkPathOpsSpan.h
+++ /dev/null
@@ -1,31 +0,0 @@
-/*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-#ifndef SkOpSpan_DEFINED
-#define SkOpSpan_DEFINED
-
-#include "SkPoint.h"
-
-class SkOpSegment;
-
-struct SkOpSpan {
- SkOpSegment* fOther;
- SkPoint fPt; // computed when the curves are intersected
- double fT;
- double fOtherT; // value at fOther[fOtherIndex].fT
- int fOtherIndex; // can't be used during intersection
- 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 fDone; // if set, this span to next higher T has been processed
- bool fUnsortableStart; // set when start is part of an unsortable pair
- bool fUnsortableEnd; // set when end is part of an unsortable pair
- bool fTiny; // if set, span may still be considered once for edge following
- bool fLoop; // set when a cubic loops back to this point
-};
-
-#endif
diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp
index 8135c57..2d7388b 100644
--- a/src/pathops/SkPathOpsTypes.cpp
+++ b/src/pathops/SkPathOpsTypes.cpp
@@ -7,34 +7,52 @@
#include "SkFloatBits.h"
#include "SkPathOpsTypes.h"
-
-
// from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
// FIXME: move to SkFloatBits.h
static bool equal_ulps(float a, float b, int epsilon) {
- SkFloatIntUnion floatIntA, floatIntB;
- floatIntA.fFloat = a;
- floatIntB.fFloat = b;
- // Different signs means they do not match.
- if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
- // Check for equality to make sure +0 == -0
- return a == b;
+ if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) {
+ return false;
}
+ int aBits = SkFloatAs2sCompliment(a);
+ int bBits = SkFloatAs2sCompliment(b);
// Find the difference in ULPs.
- int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt);
- return ulpsDiff <= epsilon;
+ return aBits < bBits + epsilon && bBits < aBits + epsilon;
+}
+
+static bool not_equal_ulps(float a, float b, int epsilon) {
+ if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) {
+ return false;
+ }
+ int aBits = SkFloatAs2sCompliment(a);
+ int bBits = SkFloatAs2sCompliment(b);
+ // Find the difference in ULPs.
+ return aBits >= bBits + epsilon || bBits >= aBits + epsilon;
}
static bool less_ulps(float a, float b, int epsilon) {
- SkFloatIntUnion floatIntA, floatIntB;
- floatIntA.fFloat = a;
- floatIntB.fFloat = b;
- // Check different signs with float epsilon since we only care if they're both close to 0.
- if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) {
- return a <= b + FLT_EPSILON * epsilon;
+ if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) {
+ return false;
}
+ int aBits = SkFloatAs2sCompliment(a);
+ int bBits = SkFloatAs2sCompliment(b);
// Find the difference in ULPs.
- return floatIntA.fSignBitInt <= floatIntB.fSignBitInt + epsilon;
+ return aBits <= bBits - epsilon;
+}
+
+static bool less_or_equal_ulps(float a, float b, int epsilon) {
+ if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) {
+ return false;
+ }
+ int aBits = SkFloatAs2sCompliment(a);
+ int bBits = SkFloatAs2sCompliment(b);
+ // Find the difference in ULPs.
+ return aBits < bBits + epsilon;
+}
+
+// equality using the same error term as between
+bool AlmostBequalUlps(float a, float b) {
+ const int UlpsEpsilon = 2;
+ return equal_ulps(a, b, UlpsEpsilon);
}
bool AlmostEqualUlps(float a, float b) {
@@ -42,18 +60,36 @@
return equal_ulps(a, b, UlpsEpsilon);
}
+bool NotAlmostEqualUlps(float a, float b) {
+ const int UlpsEpsilon = 16;
+ return not_equal_ulps(a, b, UlpsEpsilon);
+}
+
bool RoughlyEqualUlps(float a, float b) {
const int UlpsEpsilon = 256;
return equal_ulps(a, b, UlpsEpsilon);
}
bool AlmostBetweenUlps(float a, float b, float c) {
- const int UlpsEpsilon = 1;
- return a <= c ? less_ulps(a, b, UlpsEpsilon) && less_ulps(b, c, UlpsEpsilon)
- : less_ulps(b, a, UlpsEpsilon) && less_ulps(c, b, UlpsEpsilon);
+ const int UlpsEpsilon = 2;
+ return a <= c ? less_or_equal_ulps(a, b, UlpsEpsilon) && less_or_equal_ulps(b, c, UlpsEpsilon)
+ : less_or_equal_ulps(b, a, UlpsEpsilon) && less_or_equal_ulps(c, b, UlpsEpsilon);
+}
+
+bool AlmostLessUlps(float a, float b) {
+ const int UlpsEpsilon = 16;
+ return less_ulps(a, b, UlpsEpsilon);
+}
+
+bool AlmostLessOrEqualUlps(float a, float b) {
+ const int UlpsEpsilon = 16;
+ return less_or_equal_ulps(a, b, UlpsEpsilon);
}
int UlpsDistance(float a, float b) {
+ if (!SkScalarIsFinite(a) || !SkScalarIsFinite(b)) {
+ return SK_MaxS32;
+ }
SkFloatIntUnion floatIntA, floatIntB;
floatIntA.fFloat = a;
floatIntB.fFloat = b;
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 19e3efa..bc39675 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -28,11 +28,32 @@
return AlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
}
+bool NotAlmostEqualUlps(float a, float b);
+inline bool NotAlmostEqualUlps(double a, double b) {
+ return NotAlmostEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
+}
+
+// Use Almost Bequal when comparing coordinates in conjunction with between.
+bool AlmostBequalUlps(float a, float b);
+inline bool AlmostBequalUlps(double a, double b) {
+ return AlmostBequalUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
+}
+
bool RoughlyEqualUlps(float a, float b);
inline bool RoughlyEqualUlps(double a, double b) {
return RoughlyEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
}
+bool AlmostLessUlps(float a, float b);
+inline bool AlmostLessUlps(double a, double b) {
+ return AlmostLessUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
+}
+
+bool AlmostLessOrEqualUlps(float a, float b);
+inline bool AlmostLessOrEqualUlps(double a, double b) {
+ return AlmostLessOrEqualUlps(SkDoubleToScalar(a), SkDoubleToScalar(b));
+}
+
bool AlmostBetweenUlps(float a, float b, float c);
inline bool AlmostBetweenUlps(double a, double b, double c) {
return AlmostBetweenUlps(SkDoubleToScalar(a), SkDoubleToScalar(b), SkDoubleToScalar(c));
@@ -274,4 +295,22 @@
return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t;
}
+#ifdef SK_DEBUG
+inline void DebugDumpDouble(double x) {
+ if (x == floor(x)) {
+ SkDebugf("%.0f", x);
+ } else {
+ SkDebugf("%1.17g", x);
+ }
+}
+
+inline void DebugDumpFloat(float x) {
+ if (x == floorf(x)) {
+ SkDebugf("%.0f", x);
+ } else {
+ SkDebugf("%1.9gf", x);
+ }
+}
+#endif
+
#endif
diff --git a/src/pathops/SkQuarticRoot.cpp b/src/pathops/SkQuarticRoot.cpp
index 596d2a2..d3a6a78 100644
--- a/src/pathops/SkQuarticRoot.cpp
+++ b/src/pathops/SkQuarticRoot.cpp
@@ -40,7 +40,7 @@
SK_SNPRINTF(str, sizeof(str),
"Solve[%1.19g x^4 + %1.19g x^3 + %1.19g x^2 + %1.19g x + %1.19g == 0, x]",
t4, t3, t2, t1, t0);
- mathematica_ize(str, sizeof(str));
+ SkPathOpsDebug::MathematicaIze(str, sizeof(str));
#if ONE_OFF_DEBUG && ONE_OFF_DEBUG_MATHEMATICA
SkDebugf("%s\n", str);
#endif
diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp
index f7507a0..7f5e456 100644
--- a/tests/PathOpsAngleTest.cpp
+++ b/tests/PathOpsAngleTest.cpp
@@ -233,7 +233,7 @@
{ TEST_ENTRY(set3), {0, 0}},
{ TEST_ENTRY(set2), {0, 0}},
// { TEST_ENTRY(set1a), {3.70370364f,3.14814806f} },
- { TEST_ENTRY(set1), {0, 0}},
+// { TEST_ENTRY(set1), {0, 0}},
};
#undef TEST_ENTRY
@@ -287,13 +287,13 @@
}
double tStart = set[idx].tStart;
double tEnd = set[idx].tEnd;
- seg->addT(NULL, start, tStart);
- seg->addT(NULL, end, tEnd);
+ seg->addT(NULL, start, tStart, SkOpSpan::kPointIsExact);
+ seg->addT(NULL, end, tEnd, SkOpSpan::kPointIsExact);
if (tStart != 0 && tEnd != 0) {
- seg->addT(NULL, set[idx].ptData[0], 0);
+ seg->addT(NULL, set[idx].ptData[0], 0, SkOpSpan::kPointIsExact);
}
if (tStart != 1 && tEnd != 1) {
- seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], 1);
+ seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], 1, SkOpSpan::kPointIsExact);
}
int tIndex = 0;
ts[0] = 0;
diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp
index 1cc037f..d04f2db 100644
--- a/tests/PathOpsCubicIntersectionTest.cpp
+++ b/tests/PathOpsCubicIntersectionTest.cpp
@@ -163,6 +163,9 @@
const size_t testSetCount = SK_ARRAY_COUNT(testSet);
static const SkDCubic newTestSet[] = {
+{{{134, 11414}, {131.990234375, 11414}, {130.32666015625, 11415.482421875}, {130.04275512695312, 11417.4130859375}}},
+{{{132, 11419}, {130.89543151855469, 11419}, {130, 11418.1044921875}, {130, 11417}}},
+
{{{3, 4}, {1, 5}, {4, 3}, {6, 4}}},
{{{3, 4}, {4, 6}, {4, 3}, {5, 1}}},
diff --git a/tests/PathOpsCubicLineIntersectionTest.cpp b/tests/PathOpsCubicLineIntersectionTest.cpp
index 866acb3..95eb621 100644
--- a/tests/PathOpsCubicLineIntersectionTest.cpp
+++ b/tests/PathOpsCubicLineIntersectionTest.cpp
@@ -15,6 +15,8 @@
SkDCubic cubic;
SkDLine line;
} lineCubicTests[] = {
+ {{{{0,4}, {3,4}, {6,2}, {5,2}}},
+ {{{4,3}, {2,6}}}},
#if 0
{{{{258, 122}, {260.761414, 122}, { 263, 124.238579}, {263, 127}}},
{{{259.82843, 125.17157}, {261.535522, 123.46447}}}},
diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp
index b85644d..efee0fc 100644
--- a/tests/PathOpsExtendedTest.cpp
+++ b/tests/PathOpsExtendedTest.cpp
@@ -554,11 +554,12 @@
}
#if DEBUG_SHOW_TEST_NAME
-void DebugShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp, const char* testName) {
- ShowFunctionHeader(testName);
- showPath(a, "path", true);
- showPath(b, "pathB", true);
- ShowOp(shapeOp, "path", "pathB");
+void SkPathOpsDebug::ShowPath(const SkPath& a, const SkPath& b, SkPathOp shapeOp,
+ const char* testName) {
+ ShowFunctionHeader(testName);
+ showPath(a, "path", true);
+ showPath(b, "pathB", true);
+ ShowOp(shapeOp, "path", "pathB");
}
#endif
@@ -571,7 +572,7 @@
showOp(shapeOp);
showPathData(b);
} else {
- DebugShowPath(a, b, shapeOp, testName);
+ SkPathOpsDebug::ShowPath(a, b, shapeOp, testName);
}
#endif
SkPath out;
@@ -628,8 +629,8 @@
int initializeTests(skiatest::Reporter* reporter, const char* test) {
#ifdef SK_DEBUG
- gDebugMaxWindSum = 4;
- gDebugMaxWindValue = 4;
+ SkPathOpsDebug::gMaxWindSum = 4;
+ SkPathOpsDebug::gMaxWindValue = 4;
#endif
testName = test;
size_t testNameSize = strlen(test);
diff --git a/tests/PathOpsLineIntersectionTest.cpp b/tests/PathOpsLineIntersectionTest.cpp
index ea3f7e0..ee15363 100644
--- a/tests/PathOpsLineIntersectionTest.cpp
+++ b/tests/PathOpsLineIntersectionTest.cpp
@@ -11,6 +11,8 @@
// FIXME: add tests for intersecting, non-intersecting, degenerate, coincident
static const SkDLine tests[][2] = {
+ {{{{90,230}, {160,60}}}, {{{60,120}, {260,120}}}},
+ {{{{90,230}, {160,60}}}, {{{181.176468,120}, {135.294128,120}}}},
{{{{181.1764678955078125f, 120}, {186.3661956787109375f, 134.7042236328125f}}},
{{{175.8309783935546875f, 141.5211334228515625f}, {187.8782806396484375f, 133.7258148193359375f}}}},
#if 0 // FIXME: these fail because one line is too short and appears quasi-coincident
@@ -33,6 +35,9 @@
static const size_t tests_count = SK_ARRAY_COUNT(tests);
static const SkDLine noIntersect[][2] = {
+ {{{{(double) (2 - 1e-6f),2}, {(double) (2 - 1e-6f),4}}},
+ {{{2,1}, {2,3}}}},
+
{{{{0, 0}, {1, 0}}}, {{{3, 0}, {2, 0}}}},
{{{{0, 0}, {0, 0}}}, {{{1, 0}, {2, 0}}}},
{{{{0, 1}, {0, 1}}}, {{{0, 3}, {0, 2}}}},
@@ -43,6 +48,12 @@
static const size_t noIntersect_count = SK_ARRAY_COUNT(noIntersect);
static const SkDLine coincidentTests[][2] = {
+ {{{{979.304871, 561}, {1036.69507, 291}}},
+ {{{985.681519, 531}, {982.159790, 547.568542}}}},
+
+ {{{{232.159805, 547.568542}, {235.681549, 531}}},
+ {{{286.695129,291}, {229.304855,561}}}},
+
{{{{186.3661956787109375f, 134.7042236328125f}, {187.8782806396484375f, 133.7258148193359375f}}},
{{{175.8309783935546875f, 141.5211334228515625f}, {187.8782806396484375f, 133.7258148193359375f}}}},
@@ -111,19 +122,11 @@
const SkDLine& line2) {
SkASSERT(ValidLine(line1));
SkASSERT(ValidLine(line2));
- SkIntersections ts2;
- int pts2 = ts2.intersect(line1, line2);
- REPORTER_ASSERT(reporter, pts2 == 2);
- REPORTER_ASSERT(reporter, pts2 == ts2.used());
- check_results(reporter, line1, line2, ts2);
-#if 0
SkIntersections ts;
int pts = ts.intersect(line1, line2);
- REPORTER_ASSERT(reporter, pts == pts2);
REPORTER_ASSERT(reporter, pts == 2);
REPORTER_ASSERT(reporter, pts == ts.used());
check_results(reporter, line1, line2, ts);
-#endif
}
static void PathOpsLineIntersectionTest(skiatest::Reporter* reporter) {
@@ -154,9 +157,8 @@
static void PathOpsLineIntersectionOneOffTest(skiatest::Reporter* reporter) {
int index = 0;
SkASSERT(index < (int) tests_count);
- const SkDLine& line1 = tests[index][0];
- const SkDLine& line2 = tests[index][1];
- testOne(reporter, line1, line2);
+ testOne(reporter, tests[index][0], tests[index][1]);
+ testOne(reporter, tests[1][0], tests[1][1]);
}
static void PathOpsLineIntersectionOneCoincidentTest(skiatest::Reporter* reporter) {
diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp
index e0a7cf5..dee99db 100644
--- a/tests/PathOpsOpTest.cpp
+++ b/tests/PathOpsOpTest.cpp
@@ -1987,6 +1987,149 @@
testPathOp(reporter, path, pathB, kIntersect_PathOp);
}
+static void issue1418b(skiatest::Reporter* reporter) {
+ SkPath path1;
+ path1.moveTo(0, 0);
+ path1.lineTo(1, 0);
+ path1.lineTo(1, 1);
+ path1.lineTo(0, 1);
+ path1.lineTo(0, 0);
+ path1.close();
+ path1.setFillType(SkPath::kWinding_FillType);
+ SkPath path2;
+ path2.moveTo(0.646446645f, -0.353553414f);
+ path2.quadTo(0.792893291f, -0.50000006f, 1.00000012f, -0.50000006f);
+ path2.quadTo(1.20710683f, -0.50000006f, 1.35355353f, -0.353553414f);
+ path2.quadTo(1.50000012f, -0.207106799f, 1.50000012f, 0);
+ path2.quadTo(1.50000012f, 0.207106799f, 1.35355353f, 0.353553414f);
+ path2.quadTo(1.20710683f, 0.50000006f, 1.00000012f, 0.50000006f);
+ path2.quadTo(0.792893291f, 0.50000006f, 0.646446645f, 0.353553414f);
+ path2.quadTo(0.50000006f, 0.207106799f, 0.50000006f, 0);
+ path2.quadTo(0.50000006f, -0.207106799f, 0.646446645f, -0.353553414f);
+ path2.close();
+ path2.moveTo(1.00000012f, 0.50000006f);
+ path2.lineTo(1.00000012f, 1.00000012f);
+ path2.lineTo(0.50000006f, 1.00000012f);
+ path2.quadTo(0.50000006f, 0.792893291f, 0.646446645f, 0.646446645f);
+ path2.quadTo(0.792893291f, 0.50000006f, 1.00000012f, 0.50000006f);
+ path2.close();
+ path2.setFillType(SkPath::kEvenOdd_FillType);
+ testPathOp(reporter, path1, path2, kIntersect_PathOp);
+}
+
+static void rectOp1i(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ path.addRect(2, 2, 4, 4, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+
+static void rectOp2i(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.addRect(0, 0, 1, 1, SkPath::kCW_Direction);
+ path.addRect(0, 0, 3, 3, SkPath::kCW_Direction);
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
+ pathB.addRect(0, 0, 2, 2, SkPath::kCW_Direction);
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+
+static void rectOp3x(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 0);
+ path.lineTo(3, 0);
+ path.lineTo(3, 3);
+ path.lineTo(0, 3);
+ path.close();
+ path.moveTo(2, 2);
+ path.lineTo(3, 2);
+ path.lineTo(3, 3);
+ path.lineTo(2, 3);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1, 1);
+ pathB.lineTo(3, 1);
+ pathB.lineTo(3, 3);
+ pathB.lineTo(1, 3);
+ pathB.close();
+ pathB.moveTo(2, 2);
+ pathB.lineTo(3, 2);
+ pathB.lineTo(3, 3);
+ pathB.lineTo(2, 3);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kXOR_PathOp);
+}
+
+#if 0
+static void issue1435(skiatest::Reporter* reporter) {
+ SkPath path1;
+ path1.moveTo(160, 60);
+ path1.lineTo(220, 230);
+ path1.lineTo(60, 120);
+ path1.lineTo(260, 120);
+ path1.lineTo(90, 230);
+ path1.lineTo(160, 60);
+ path1.close();
+ path1.setFillType(SkPath::kEvenOdd_FillType);
+
+
+ SkPath path2;
+ path2.moveTo(142.589081f, 102.283646f);
+ path2.quadTo(149.821579f, 100, 158, 100);
+ path2.quadTo(167.156921f, 100, 175.128036f, 102.862793f);
+ path2.lineTo(181.176468f, 120);
+ path2.lineTo(135.294128f, 120);
+ path2.lineTo(142.589081f, 102.283646f);
+ path2.close();
+ path2.moveTo(118.681946f, 160.343842f);
+ path2.lineTo(135.294128f, 120);
+ path2.lineTo(117.933762f, 120);
+ path2.quadTo(108, 132.942657f, 108, 150);
+ path2.quadTo(108, 151.54483f, 108.08149f, 153.05603f);
+ path2.lineTo(118.681946f, 160.343842f);
+ path2.close();
+ path2.moveTo(156.969696f, 186.666672f);
+ path2.lineTo(118.681946f, 160.343842f);
+ path2.lineTo(113.458946f, 173.028259f);
+ path2.quadTo(116.94117f, 179.651855f, 122.644661f, 185.355347f);
+ path2.quadTo(130.792465f, 193.503143f, 140.817978f, 197.117783f);
+ path2.lineTo(156.969696f, 186.666672f);
+ path2.close();
+ path2.moveTo(195.830978f, 161.521133f);
+ path2.lineTo(156.969696f, 186.666672f);
+ path2.lineTo(173.157288f, 197.795639f);
+ path2.quadTo(184.392426f, 194.318268f, 193.355347f, 185.355347f);
+ path2.quadTo(197.805817f, 180.904861f, 200.903809f, 175.894165f);
+ path2.lineTo(195.830978f, 161.521133f);
+ path2.close();
+ path2.moveTo(195.830978f, 161.521133f);
+ path2.lineTo(207.878281f, 153.725815f);
+ path2.quadTo(208, 151.888062f, 208, 150);
+ path2.quadTo(208, 132.942657f, 198.066238f, 120);
+ path2.lineTo(181.176468f, 120);
+ path2.lineTo(195.830978f, 161.521133f);
+ path2.close();
+ path2.setFillType(SkPath::kEvenOdd_FillType);
+ testPathOp(reporter, path1, path2, kIntersect_PathOp);
+}
+#endif
+
+#if 0
+static void bufferOverflow(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.addRect(0,0, 300,170141183460469231731687303715884105728.);
+ SkPath pathB;
+ pathB.addRect(0,0, 300,16);
+ testPathOp(reporter, path, pathB, kUnion_PathOp);
+}
+#endif
+
#if 0
static void skpkkiste_to716(skiatest::Reporter* reporter) {
SkPath path;
@@ -2013,10 +2156,145 @@
}
#endif
+static void loopEdge1(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0,0);
+ path.lineTo(3,0);
+ path.lineTo(3,2);
+ path.lineTo(1,2);
+ path.lineTo(1,1);
+ path.lineTo(2,1);
+ path.lineTo(2,3);
+ path.lineTo(0,3);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kEvenOdd_FillType);
+ pathB.moveTo(1,2);
+ pathB.lineTo(2,2);
+ pathB.lineTo(2,4);
+ pathB.lineTo(1,4);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+
+static void loopEdge2(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0,0);
+ path.lineTo(3,0);
+ path.lineTo(3,2);
+ path.lineTo(1,2);
+ path.lineTo(1,1);
+ path.lineTo(2,1);
+ path.lineTo(2,3);
+ path.lineTo(0,3);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kEvenOdd_FillType);
+ pathB.moveTo(1 - 1e-6f,2);
+ pathB.lineTo(2 - 1e-6f,2);
+ pathB.lineTo(2 - 1e-6f,4);
+ pathB.lineTo(1 - 1e-6f,4);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+
+static void cubicOp86i(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0, 4);
+ path.cubicTo(3, 4, 6, 2, 5, 2);
+ path.close();
+ pathB.setFillType(SkPath::kEvenOdd_FillType);
+ pathB.moveTo(2, 6);
+ pathB.cubicTo(2, 5, 4, 0, 4, 3);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+
+static void cubicOp87u(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(0,2, 2,0, 6,4);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,2);
+ pathB.cubicTo(4,6, 1,0, 2,0);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kUnion_PathOp);
+}
+
+static void cubicOp88u(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(2,5, 5,0, 6,4);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,5);
+ pathB.cubicTo(4,6, 1,0, 5,2);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kUnion_PathOp);
+}
+
+static void cubicOp89u(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0, 3);
+ path.cubicTo(1, 6, 5, 0, 6, 3);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0, 5);
+ pathB.cubicTo(3, 6, 3, 0, 6, 1);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kUnion_PathOp);
+}
+
+static void cubicOp90u(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(0, 5);
+ path.cubicTo(1, 2, 5, 2, 4, 1);
+ path.close();
+ pathB.setFillType(SkPath::kEvenOdd_FillType);
+ pathB.moveTo(2, 5);
+ pathB.cubicTo(1, 4, 5, 0, 2, 1);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kUnion_PathOp);
+}
+
+static void cubicOp91u(skiatest::Reporter* reporter) {
+ SkPath path, pathB;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(1, 6);
+ path.cubicTo(0, 3, 6, 3, 5, 0);
+ path.close();
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(3, 6);
+ pathB.cubicTo(0, 5, 6, 1, 3, 0);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kUnion_PathOp);
+}
static void (*firstTest)(skiatest::Reporter* ) = 0;
static struct TestDesc tests[] = {
// TEST(skpkkiste_to716),
+ // TEST(bufferOverflow),
+ // TEST(issue1435),
+ TEST(cubicOp91u),
+ TEST(cubicOp90u),
+ TEST(cubicOp89u),
+ TEST(cubicOp88u),
+ TEST(cubicOp87u),
+ TEST(cubicOp86i),
+ TEST(loopEdge2),
+ TEST(loopEdge1),
+ TEST(rectOp3x),
+ TEST(rectOp2i),
+ TEST(rectOp1i),
+ TEST(issue1418b),
TEST(cubicOp85i),
TEST(issue1417),
TEST(issue1418),
@@ -2167,8 +2445,8 @@
static void PathOpsOpTest(skiatest::Reporter* reporter) {
#ifdef SK_DEBUG
- gDebugMaxWindSum = 4;
- gDebugMaxWindValue = 4;
+ SkPathOpsDebug::gMaxWindSum = 4;
+ SkPathOpsDebug::gMaxWindValue = 4;
#endif
#if DEBUG_SHOW_TEST_NAME
strncpy(DEBUG_FILENAME_STRING, "", DEBUG_FILENAME_STRING_LENGTH);
@@ -2181,8 +2459,8 @@
RunTestSet(reporter, subTests, subTestCount, firstSubTest, stopTest, runReverse);
}
#ifdef SK_DEBUG
- gDebugMaxWindSum = SK_MaxS32;
- gDebugMaxWindValue = SK_MaxS32;
+ SkPathOpsDebug::gMaxWindSum = SK_MaxS32;
+ SkPathOpsDebug::gMaxWindValue = SK_MaxS32;
#endif
}
diff --git a/tests/PathOpsQuadLineIntersectionTest.cpp b/tests/PathOpsQuadLineIntersectionTest.cpp
index 555a90c..7ec8066 100644
--- a/tests/PathOpsQuadLineIntersectionTest.cpp
+++ b/tests/PathOpsQuadLineIntersectionTest.cpp
@@ -59,6 +59,8 @@
SkDQuad quad;
SkDLine line;
} oneOffs[] = {
+ {{{{142.589081, 102.283646}, {149.821579, 100}, {158, 100}}},
+ {{{90, 230}, {160, 60}}}},
{{{{1101, 10}, {1101, 8.3431453704833984}, {1099.828857421875, 7.1711997985839844}}},
{{{1099.828857421875,7.1711711883544922}, {1099.121337890625,7.8786783218383789}}}},
{{{{973, 507}, {973, 508.24264526367187}, {972.12158203125, 509.12161254882812}}},
diff --git a/tests/PathOpsSimplifyFailTest.cpp b/tests/PathOpsSimplifyFailTest.cpp
index 0245f87..8c0f9ba 100644
--- a/tests/PathOpsSimplifyFailTest.cpp
+++ b/tests/PathOpsSimplifyFailTest.cpp
@@ -37,63 +37,82 @@
const size_t finitePtsCount = sizeof(finitePts) / sizeof(finitePts[0]);
+static void failOne(skiatest::Reporter* reporter, int index) {
+ SkPath path;
+ int i = (int) (index % nonFinitePtsCount);
+ int f = (int) (index % finitePtsCount);
+ int g = (int) ((f + 1) % finitePtsCount);
+ switch (index % 13) {
+ case 0: path.lineTo(nonFinitePts[i]); break;
+ case 1: path.quadTo(nonFinitePts[i], nonFinitePts[i]); break;
+ case 2: path.quadTo(nonFinitePts[i], finitePts[f]); break;
+ case 3: path.quadTo(finitePts[f], nonFinitePts[i]); break;
+ case 4: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[f]); break;
+ case 5: path.cubicTo(finitePts[f], nonFinitePts[i], finitePts[f]); break;
+ case 6: path.cubicTo(finitePts[f], finitePts[f], nonFinitePts[i]); break;
+ case 7: path.cubicTo(nonFinitePts[i], nonFinitePts[i], finitePts[f]); break;
+ case 8: path.cubicTo(nonFinitePts[i], finitePts[f], nonFinitePts[i]); break;
+ case 9: path.cubicTo(finitePts[f], nonFinitePts[i], nonFinitePts[i]); break;
+ case 10: path.cubicTo(nonFinitePts[i], nonFinitePts[i], nonFinitePts[i]); break;
+ case 11: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[g]); break;
+ case 12: path.moveTo(nonFinitePts[i]); break;
+ }
+ SkPath result;
+ result.setFillType(SkPath::kWinding_FillType);
+ bool success = Simplify(path, &result);
+ REPORTER_ASSERT(reporter, !success);
+ REPORTER_ASSERT(reporter, result.isEmpty());
+ REPORTER_ASSERT(reporter, result.getFillType() == SkPath::kWinding_FillType);
+ reporter->bumpTestCount();
+}
+
+static void dontFailOne(skiatest::Reporter* reporter, int index) {
+ SkPath path;
+ int f = (int) (index % finitePtsCount);
+ int g = (int) ((f + 1) % finitePtsCount);
+ switch (index % 11) {
+ case 0: path.lineTo(finitePts[f]); break;
+ case 1: path.quadTo(finitePts[f], finitePts[f]); break;
+ case 2: path.quadTo(finitePts[f], finitePts[g]); break;
+ case 3: path.quadTo(finitePts[g], finitePts[f]); break;
+ case 4: path.cubicTo(finitePts[f], finitePts[f], finitePts[f]); break;
+ case 5: path.cubicTo(finitePts[f], finitePts[f], finitePts[g]); break;
+ case 6: path.cubicTo(finitePts[f], finitePts[g], finitePts[f]); break;
+ case 7: path.cubicTo(finitePts[f], finitePts[g], finitePts[g]); break;
+ case 8: path.cubicTo(finitePts[g], finitePts[f], finitePts[f]); break;
+ case 9: path.cubicTo(finitePts[g], finitePts[f], finitePts[g]); break;
+ case 10: path.moveTo(finitePts[f]); break;
+ }
+ SkPath result;
+ result.setFillType(SkPath::kWinding_FillType);
+ bool success = Simplify(path, &result);
+ REPORTER_ASSERT(reporter, success);
+ REPORTER_ASSERT(reporter, result.getFillType() != SkPath::kWinding_FillType);
+ reporter->bumpTestCount();
+}
+
static void PathOpsSimplifyFailTest(skiatest::Reporter* reporter) {
for (int index = 0; index < (int) (13 * nonFinitePtsCount * finitePtsCount); ++index) {
- SkPath path;
- int i = (int) (index % nonFinitePtsCount);
- int f = (int) (index % finitePtsCount);
- int g = (int) ((f + 1) % finitePtsCount);
- switch (index % 13) {
- case 0: path.lineTo(nonFinitePts[i]); break;
- case 1: path.quadTo(nonFinitePts[i], nonFinitePts[i]); break;
- case 2: path.quadTo(nonFinitePts[i], finitePts[f]); break;
- case 3: path.quadTo(finitePts[f], nonFinitePts[i]); break;
- case 4: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[f]); break;
- case 5: path.cubicTo(finitePts[f], nonFinitePts[i], finitePts[f]); break;
- case 6: path.cubicTo(finitePts[f], finitePts[f], nonFinitePts[i]); break;
- case 7: path.cubicTo(nonFinitePts[i], nonFinitePts[i], finitePts[f]); break;
- case 8: path.cubicTo(nonFinitePts[i], finitePts[f], nonFinitePts[i]); break;
- case 9: path.cubicTo(finitePts[f], nonFinitePts[i], nonFinitePts[i]); break;
- case 10: path.cubicTo(nonFinitePts[i], nonFinitePts[i], nonFinitePts[i]); break;
- case 11: path.cubicTo(nonFinitePts[i], finitePts[f], finitePts[g]); break;
- case 12: path.moveTo(nonFinitePts[i]); break;
- }
- SkPath result;
- result.setFillType(SkPath::kWinding_FillType);
- bool success = Simplify(path, &result);
- REPORTER_ASSERT(reporter, !success);
- REPORTER_ASSERT(reporter, result.isEmpty());
- REPORTER_ASSERT(reporter, result.getFillType() == SkPath::kWinding_FillType);
- reporter->bumpTestCount();
- }
- if (sizeof(reporter) == 4) {
- return;
+ failOne(reporter, index);
}
for (int index = 0; index < (int) (11 * finitePtsCount); ++index) {
- SkPath path;
- int f = (int) (index % finitePtsCount);
- int g = (int) ((f + 1) % finitePtsCount);
- switch (index % 11) {
- case 0: path.lineTo(finitePts[f]); break;
- case 1: path.quadTo(finitePts[f], finitePts[f]); break;
- case 2: path.quadTo(finitePts[f], finitePts[g]); break;
- case 3: path.quadTo(finitePts[g], finitePts[f]); break;
- case 4: path.cubicTo(finitePts[f], finitePts[f], finitePts[f]); break;
- case 5: path.cubicTo(finitePts[f], finitePts[f], finitePts[g]); break;
- case 6: path.cubicTo(finitePts[f], finitePts[g], finitePts[f]); break;
- case 7: path.cubicTo(finitePts[f], finitePts[g], finitePts[g]); break;
- case 8: path.cubicTo(finitePts[g], finitePts[f], finitePts[f]); break;
- case 9: path.cubicTo(finitePts[g], finitePts[f], finitePts[g]); break;
- case 10: path.moveTo(finitePts[f]); break;
- }
- SkPath result;
- result.setFillType(SkPath::kWinding_FillType);
- bool success = Simplify(path, &result);
- REPORTER_ASSERT(reporter, success);
- REPORTER_ASSERT(reporter, result.getFillType() != SkPath::kWinding_FillType);
- reporter->bumpTestCount();
+ dontFailOne(reporter, index);
}
}
+static void PathOpsSimplifyFailOneTest(skiatest::Reporter* reporter) {
+ int index = 0;
+ failOne(reporter, index);
+}
+
+static void PathOpsSimplifyDontFailOneTest(skiatest::Reporter* reporter) {
+ int index = 6;
+ dontFailOne(reporter, index);
+}
+
#include "TestClassDef.h"
DEFINE_TESTCLASS_SHORT(PathOpsSimplifyFailTest)
+
+DEFINE_TESTCLASS_SHORT(PathOpsSimplifyFailOneTest)
+
+DEFINE_TESTCLASS_SHORT(PathOpsSimplifyDontFailOneTest)
diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp
index 954435f..65b8d98 100644
--- a/tests/PathOpsSimplifyTest.cpp
+++ b/tests/PathOpsSimplifyTest.cpp
@@ -2813,6 +2813,7 @@
path.close();
testSimplify(reporter, path);
}
+
static void testQuadratic55(skiatest::Reporter* reporter) {
SkPath path;
path.moveTo(303.12088f, 141.299606f);
@@ -3828,9 +3829,90 @@
testSimplify(reporter, path);
}
-static void (*firstTest)(skiatest::Reporter* ) = testQuad6;
+static void tooCloseTest(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.moveTo(0, 0);
+ path.lineTo(1, 1);
+ path.lineTo(1,-1);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1,-2);
+ path.lineTo(1, 2);
+ path.lineTo(2, 0);
+ path.close();
+ testSimplify(reporter, path);
+}
+
+static void testRect1(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.addRect(0, 0, 60, 60, SkPath::kCCW_Direction);
+ path.addRect(30, 20, 50, 50, SkPath::kCCW_Direction);
+ path.addRect(24, 20, 36, 30, SkPath::kCCW_Direction);
+ path.addRect(32, 24, 36, 41, SkPath::kCCW_Direction);
+ testSimplify(reporter, path);
+}
+
+static void testRect2(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0, 0);
+ path.lineTo(60, 0);
+ path.lineTo(60, 60);
+ path.lineTo(0, 60);
+ path.close();
+ path.moveTo(30, 20);
+ path.lineTo(30, 50);
+ path.lineTo(50, 50);
+ path.lineTo(50, 20);
+ path.close();
+ path.moveTo(24, 20);
+ path.lineTo(24, 30);
+ path.lineTo(36, 30);
+ path.lineTo(36, 20);
+ path.close();
+ path.moveTo(32, 24);
+ path.lineTo(32, 41);
+ path.lineTo(36, 41);
+ path.lineTo(36, 24);
+ path.close();
+ testSimplify(reporter, path);
+}
+
+static void testTriangles3x(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(1, 0);
+ path.quadTo(0, 1, 3, 2);
+ path.lineTo(1, 3);
+ path.close();
+ path.moveTo(0, 0);
+ path.lineTo(1, 1);
+ path.quadTo(2, 1, 0, 2);
+ path.close();
+ testSimplify(reporter, path);
+}
+
+static void testQuad8(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.moveTo(3, 0);
+ path.quadTo(0, 1, 3, 2);
+ path.lineTo(0, 3);
+ path.close();
+ path.moveTo(1, 0);
+ path.lineTo(3, 0);
+ path.quadTo(1, 1, 2, 2);
+ path.close();
+ testSimplify(reporter, path);
+}
+
+static void (*firstTest)(skiatest::Reporter* ) = testRect2;
static TestDesc tests[] = {
+ TEST(testQuad8),
+ TEST(testTriangles3x),
+ TEST(testRect2),
+ TEST(testRect1),
+ TEST(tooCloseTest),
TEST(skphealth_com76),
TEST(testQuadLineIntersect1),
TEST(testQuadLineIntersect2),
@@ -4199,8 +4281,8 @@
static void PathOpsSimplifyTest(skiatest::Reporter* reporter) {
#ifdef SK_DEBUG
- gDebugMaxWindSum = 4;
- gDebugMaxWindValue = 4;
+ SkPathOpsDebug::gMaxWindSum = 4;
+ SkPathOpsDebug::gMaxWindValue = 4;
#endif
if (runSubTestsFirst) {
RunTestSet(reporter, subTests, subTestCount, firstSubTest, stopTest, runReverse);
@@ -4210,8 +4292,8 @@
RunTestSet(reporter, subTests, subTestCount, firstSubTest, stopTest, runReverse);
}
#ifdef SK_DEBUG
- gDebugMaxWindSum = SK_MaxS32;
- gDebugMaxWindValue = SK_MaxS32;
+ SkPathOpsDebug::gMaxWindSum = SK_MaxS32;
+ SkPathOpsDebug::gMaxWindValue = SK_MaxS32;
#endif
}
diff --git a/tests/PathOpsThreadedCommon.cpp b/tests/PathOpsThreadedCommon.cpp
index 0abf816..a66ec71 100644
--- a/tests/PathOpsThreadedCommon.cpp
+++ b/tests/PathOpsThreadedCommon.cpp
@@ -21,7 +21,7 @@
pool.add(fRunnables[index]);
}
#ifdef SK_DEBUG
- gDebugMaxWindSum = SK_MaxS32;
- gDebugMaxWindValue = SK_MaxS32;
+ SkPathOpsDebug::gMaxWindSum = SK_MaxS32;
+ SkPathOpsDebug::gMaxWindValue = SK_MaxS32;
#endif
}