path ops -- fix skp bugs
This fixes a series of bugs discovered by running
the small set of Skia skp files through pathops
to flatten the clips.
Review URL: https://codereview.chromium.org/14798004
git-svn-id: http://skia.googlecode.com/svn/trunk@9042 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp
index 9efd4d6..1884d4e 100644
--- a/src/pathops/SkAddIntersections.cpp
+++ b/src/pathops/SkAddIntersections.cpp
@@ -208,7 +208,7 @@
case SkIntersectionHelper::kLine_Segment: {
pts = ts.lineHorizontal(wn.pts(), wt.left(),
wt.right(), wt.y(), wt.xFlipped());
- debugShowLineIntersection(pts, wt, wn, ts);
+ debugShowLineIntersection(pts, wn, wt, ts);
break;
}
case SkIntersectionHelper::kQuad_Segment: {
@@ -235,7 +235,7 @@
case SkIntersectionHelper::kLine_Segment: {
pts = ts.lineVertical(wn.pts(), wt.top(),
wt.bottom(), wt.x(), wt.yFlipped());
- debugShowLineIntersection(pts, wt, wn, ts);
+ debugShowLineIntersection(pts, wn, wt, ts);
break;
}
case SkIntersectionHelper::kQuad_Segment: {
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp
index 10d4e71..922c103 100644
--- a/src/pathops/SkDCubicIntersection.cpp
+++ b/src/pathops/SkDCubicIntersection.cpp
@@ -138,7 +138,6 @@
}
} else {
double offset = precisionScale / 16; // FIME: const is arbitrary: test, refine
-#if 1
double c1Bottom = tIdx == 0 ? 0 :
(t1Start + (t1 - t1Start) * locals[0][tIdx - 1] + to1) / 2;
double c1Min = SkTMax(c1Bottom, to1 - offset);
@@ -240,46 +239,6 @@
i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1);
#endif
}
-#else
- double c1Bottom = tIdx == 0 ? 0 :
- (t1Start + (t1 - t1Start) * locals.fT[0][tIdx - 1] + to1) / 2;
- double c1Min = SkTMax(c1Bottom, to1 - offset);
- double c1Top = tIdx == tCount - 1 ? 1 :
- (t1Start + (t1 - t1Start) * locals.fT[0][tIdx + 1] + to1) / 2;
- double c1Max = SkTMin(c1Top, to1 + offset);
- double c2Bottom = tIdx == 0 ? to2 :
- (t2Start + (t2 - t2Start) * locals.fT[1][tIdx - 1] + to2) / 2;
- double c2Top = tIdx == tCount - 1 ? to2 :
- (t2Start + (t2 - t2Start) * locals.fT[1][tIdx + 1] + to2) / 2;
- if (c2Bottom > c2Top) {
- SkTSwap(c2Bottom, c2Top);
- }
- if (c2Bottom == to2) {
- c2Bottom = 0;
- }
- if (c2Top == to2) {
- c2Top = 1;
- }
- double c2Min = SkTMax(c2Bottom, to2 - offset);
- double c2Max = SkTMin(c2Top, to2 + offset);
- #if ONE_OFF_DEBUG
- SkDebugf("%s contains1=%d/%d contains2=%d/%d\n", __FUNCTION__,
- c1Min <= 0.210357794 && 0.210357794 <= c1Max
- && c2Min <= 0.223476406 && 0.223476406 <= c2Max,
- to1 - offset <= 0.210357794 && 0.210357794 <= to1 + offset
- && to2 - offset <= 0.223476406 && 0.223476406 <= to2 + offset,
- c1Min <= 0.211324707 && 0.211324707 <= c1Max
- && c2Min <= 0.211327209 && 0.211327209 <= c2Max,
- to1 - offset <= 0.211324707 && 0.211324707 <= to1 + offset
- && to2 - offset <= 0.211327209 && 0.211327209 <= to2 + offset);
- SkDebugf("%s c1Bottom=%1.9g c1Top=%1.9g c2Bottom=%1.9g c2Top=%1.9g"
- " 1-o=%1.9g 1+o=%1.9g 2-o=%1.9g 2+o=%1.9g offset=%1.9g\n",
- __FUNCTION__, c1Bottom, c1Top, c2Bottom, c2Top,
- to1 - offset, to1 + offset, to2 - offset, to2 + offset, offset);
- SkDebugf("%s to1=%1.9g to2=%1.9g c1Min=%1.9g c1Max=%1.9g c2Min=%1.9g"
- " c2Max=%1.9g\n", __FUNCTION__, to1, to2, c1Min, c1Max, c2Min, c2Max);
- #endif
-#endif
intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i);
// FIXME: if no intersection is found, either quadratics intersected where
// cubics did not, or the intersection was missed. In the former case, expect
@@ -303,9 +262,11 @@
const SkDRect& bounds2, SkIntersections& i) {
SkDLine line;
int t1Index = start ? 0 : 3;
- line[0] = cubic1[t1Index];
// don't bother if the two cubics are connnected
+#if 1
SkTDArray<double> tVals; // OPTIMIZE: replace with hard-sized array
+ line[0] = cubic1[t1Index];
+ // this variant looks for intersections with the end point and lines parallel to other points
for (int index = 0; index < 4; ++index) {
if (index == t1Index) {
continue;
@@ -335,7 +296,7 @@
i.insert(start ? 0 : 1, foundT, line[0]);
}
} else {
- *tVals.append() = local[0][idx2];
+ *tVals.append() = foundT;
}
}
}
@@ -362,6 +323,57 @@
}
tIdx = tLast + 1;
} while (tIdx < tVals.count());
+#else
+ const SkDPoint& endPt = cubic1[t1Index];
+ if (!bounds2.contains(endPt)) {
+ return;
+ }
+ // this variant looks for intersections within an 'x' of the endpoint
+ double delta = SkTMax(bounds2.width(), bounds2.height());
+ for (int index = 0; index < 2; ++index) {
+ if (index == 0) {
+ line[0].fY = line[1].fY = endPt.fY;
+ line[0].fX = endPt.fX - delta;
+ line[1].fX = endPt.fX + delta;
+ } else {
+ line[0].fX = line[1].fX = cubic1[t1Index].fX;
+ line[0].fY = endPt.fY - delta;
+ line[1].fY = endPt.fY + delta;
+ }
+ SkIntersections local;
+ local.intersectRay(cubic2, line); // OPTIMIZE: special for horizontal/vertical lines
+ int used = local.used();
+ for (int index = 0; index < used; ++index) {
+ double foundT = local[0][index];
+ if (approximately_less_than_zero(foundT) || approximately_greater_than_one(foundT)) {
+ continue;
+ }
+ if (!local.pt(index).approximatelyEqual(endPt)) {
+ continue;
+ }
+ if (i.swapped()) { // FIXME: insert should respect swap
+ i.insert(foundT, start ? 0 : 1, endPt);
+ } else {
+ i.insert(start ? 0 : 1, foundT, endPt);
+ }
+ return;
+ }
+ }
+// the above doesn't catch when the end of the cubic missed the other cubic because the quad
+// approximation moved too far away, so something like the below is still needed. The enabled
+// code above tries to avoid this heavy lifting unless the convex hull intersected the cubic.
+ double tMin1 = start ? 0 : 1 - LINE_FRACTION;
+ double tMax1 = start ? LINE_FRACTION : 1;
+ double tMin2 = SkTMax(foundT - LINE_FRACTION, 0.0);
+ double tMax2 = SkTMin(foundT + LINE_FRACTION, 1.0);
+ int lastUsed = i.used();
+ intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i);
+ if (lastUsed == i.used()) {
+ tMin2 = SkTMax(foundT - (1.0 / SkDCubic::gPrecisionUnit), 0.0);
+ tMax2 = SkTMin(foundT + (1.0 / SkDCubic::gPrecisionUnit), 1.0);
+ intersect(cubic1, tMin1, tMax1, cubic2, tMin2, tMax2, 1, i);
+ }
+#endif
return;
}
diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp
index 5df3aca..11876f8 100644
--- a/src/pathops/SkDCubicLineIntersection.cpp
+++ b/src/pathops/SkDCubicLineIntersection.cpp
@@ -257,5 +257,9 @@
int SkIntersections::intersectRay(const SkDCubic& cubic, const SkDLine& line) {
LineCubicIntersections c(cubic, line, *this);
- return c.intersectRay(fT[0]);
+ fUsed = c.intersectRay(fT[0]);
+ for (int index = 0; index < fUsed; ++index) {
+ fPt[index] = cubic.xyAtT(fT[0][index]);
+ }
+ return fUsed;
}
diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp
index 5fd7d61..b1e1783 100644
--- a/src/pathops/SkDLineIntersection.cpp
+++ b/src/pathops/SkDLineIntersection.cpp
@@ -142,27 +142,6 @@
return fUsed = 1;
}
-// OPTIMIZATION Given: dy = line[1].fY - line[0].fY
-// and: xIntercept / (y - line[0].fY) == (line[1].fX - line[0].fX) / dy
-// then: xIntercept * dy == (line[1].fX - line[0].fX) * (y - line[0].fY)
-// Assuming that dy is always > 0, the line segment intercepts if:
-// left * dy <= xIntercept * dy <= right * dy
-// thus: left * dy <= (line[1].fX - line[0].fX) * (y - line[0].fY) <= right * dy
-// (clever as this is, it does not give us the t value, so may be useful only
-// as a quick reject -- and maybe not then; it takes 3 muls, 3 adds, 2 cmps)
-int SkIntersections::horizontal(const SkDLine& line, double left, double right, double y) {
- int result = horizontal(line, y);
- if (result != 1) {
- SkASSERT(0);
- return result;
- }
- double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
- if (!precisely_between(left, xIntercept, right)) {
- return fUsed = 0;
- }
- return result;
-}
-
int SkIntersections::horizontal(const SkDLine& line, double left, double right,
double y, bool flipped) {
int result = horizontal(line, y);
diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp
index e7e77e6..afaa155 100644
--- a/src/pathops/SkDQuadLineIntersection.cpp
+++ b/src/pathops/SkDQuadLineIntersection.cpp
@@ -329,5 +329,9 @@
int SkIntersections::intersectRay(const SkDQuad& quad, const SkDLine& line) {
LineQuadraticIntersections q(quad, line, this);
- return q.intersectRay(fT[0]);
+ fUsed = q.intersectRay(fT[0]);
+ for (int index = 0; index < fUsed; ++index) {
+ fPt[index] = quad.xyAtT(fT[0][index]);
+ }
+ return fUsed;
}
diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h
index a677a38..83ff6b1 100644
--- a/src/pathops/SkIntersections.h
+++ b/src/pathops/SkIntersections.h
@@ -188,7 +188,6 @@
int cubicRay(const SkPoint pts[4], const SkDLine& line);
void flip();
int horizontal(const SkDLine&, double y);
- int horizontal(const SkDLine&, double left, double right, double y);
int horizontal(const SkDLine&, double left, double right, double y, bool flipped);
int horizontal(const SkDQuad&, double left, double right, double y, bool flipped);
int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]);
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index 65af383..750520a 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -9,6 +9,10 @@
#include "SkPathOpsCurve.h"
#include "SkTSort.h"
+#if DEBUG_SORT || DEBUG_SORT_SINGLE
+#include "SkOpSegment.h"
+#endif
+
// FIXME: this is bogus for quads and cubics
// if the quads and cubics' line from end pt to ctrl pt are coincident,
// there's no obvious way to determine the curve ordering from the
@@ -27,14 +31,10 @@
maybe I could set up LineParameters lazily
*/
-bool SkOpAngle::operator<(const SkOpAngle& rh) const {
- double y = dy();
- double ry = rh.dy();
+static int simple_compare(double x, double y, double rx, double ry) {
if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ?
return y < 0;
}
- double x = dx();
- double rx = rh.dx();
if (y == 0 && ry == 0 && x * rx < 0) {
return x < rx;
}
@@ -48,6 +48,18 @@
&& !approximately_zero_squared(cmp)) {
return cmp < 0;
}
+ return -1;
+}
+
+bool SkOpAngle::operator<(const SkOpAngle& rh) const {
+ double x = dx();
+ double y = dy();
+ double rx = rh.dx();
+ double ry = rh.dy();
+ int simple = simple_compare(x, y, rx, ry);
+ if (simple >= 0) {
+ return simple;
+ }
// at this point, the initial tangent line is coincident
// see if edges curl away from each other
if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide)
@@ -93,8 +105,10 @@
SkIntersections i, ri;
int roots, rroots;
bool flip = false;
+ bool useThis;
+ bool leftLessThanRight = fSide > 0;
do {
- bool useThis = (len < rlen) ^ flip;
+ useThis = (len < rlen) ^ flip;
const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart;
SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb;
ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ?
@@ -113,28 +127,65 @@
rh.fUnsortable = true;
return this < &rh; // even with no solution, return a stable sort
}
- SkDPoint loc;
+ SkASSERT(fSide != 0 && rh.fSide != 0);
+ SkASSERT(fSide * rh.fSide > 0); // both are the same sign
+ SkDPoint lLoc;
double best = SK_ScalarInfinity;
- SkDVector dxy;
- double dist;
- int index;
- for (index = 0; index < roots; ++index) {
- loc = (*CurveDPointAtT[fVerb])(fPts, i[0][index]);
- dxy = loc - ray[0];
- dist = dxy.lengthSquared();
+#if DEBUG_SORT
+ SkDebugf("lh=%d rh=%d use-lh=%d ray={{%1.9g,%1.9g}, {%1.9g,%1.9g}} %c\n",
+ fSegment->debugID(), rh.fSegment->debugID(), useThis, ray[0].fX, ray[0].fY,
+ ray[1].fX, ray[1].fY, "-+"[fSide > 0]);
+#endif
+ for (int index = 0; index < roots; ++index) {
+ SkDPoint loc = i.pt(index);
+ SkDVector dxy = loc - ray[0];
+ double dist = dxy.lengthSquared();
+#if DEBUG_SORT
+ SkDebugf("best=%1.9g dist=%1.9g loc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n",
+ best, dist, loc.fX, loc.fY, dxy.fX, dxy.fY);
+#endif
if (best > dist) {
+ lLoc = loc;
best = dist;
}
}
- for (index = 0; index < rroots; ++index) {
- loc = (*CurveDPointAtT[rh.fVerb])(rh.fPts, ri[0][index]);
- dxy = loc - ray[0];
- dist = dxy.lengthSquared();
+ flip = false;
+ SkDPoint rLoc;
+ for (int index = 0; index < rroots; ++index) {
+ rLoc = ri.pt(index);
+ SkDVector dxy = rLoc - ray[0];
+ double dist = dxy.lengthSquared();
+#if DEBUG_SORT
+ SkDebugf("best=%1.9g dist=%1.9g %c=(fSide < 0) rLoc={%1.9g,%1.9g} dxy={%1.9g,%1.9g}\n",
+ best, dist, "><"[fSide < 0], rLoc.fX, rLoc.fY, dxy.fX, dxy.fY);
+#endif
if (best > dist) {
- return fSide < 0;
+ flip = true;
+ break;
}
}
- return fSide > 0;
+ #if 0
+ SkDVector lRay = lLoc - fCurvePart[0];
+ SkDVector rRay = rLoc - fCurvePart[0];
+ int rayDir = simple_compare(lRay.fX, lRay.fY, rRay.fX, rRay.fY);
+ SkASSERT(rayDir >= 0);
+ if (rayDir < 0) {
+ fUnsortable = true;
+ rh.fUnsortable = true;
+ return this < &rh; // even with no solution, return a stable sort
+ }
+#endif
+ if (flip) {
+ leftLessThanRight = !leftLessThanRight;
+ // rayDir = !rayDir;
+ }
+#if 0 && (DEBUG_SORT || DEBUG_SORT_SINGLE)
+ SkDebugf("%d %c %d (fSide %c 0) loc={{%1.9g,%1.9g}, {%1.9g,%1.9g}} flip=%d rayDir=%d\n",
+ fSegment->debugID(), "><"[leftLessThanRight], rh.fSegment->debugID(),
+ "<>"[fSide > 0], lLoc.fX, lLoc.fY, rLoc.fX, rLoc.fY, flip, rayDir);
+#endif
+// SkASSERT(leftLessThanRight == (bool) rayDir);
+ return leftLessThanRight;
}
bool SkOpAngle::lengthen() {
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index 1aee405..6266c65 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -64,38 +64,36 @@
#endif
double startT = coincidence.fTs[0][0];
double endT = coincidence.fTs[0][1];
- bool cancelers;
- if ((cancelers = startT > endT)) {
+ bool startSwapped, oStartSwapped, cancelers;
+ if ((cancelers = startSwapped = startT > endT)) {
SkTSwap(startT, endT);
- SkTSwap(coincidence.fPts[0], coincidence.fPts[1]);
}
SkASSERT(!approximately_negative(endT - startT));
double oStartT = coincidence.fTs[1][0];
double oEndT = coincidence.fTs[1][1];
- if (oStartT > oEndT) {
- SkTSwap<double>(oStartT, oEndT);
+ if ((oStartSwapped = oStartT > oEndT)) {
+ SkTSwap(oStartT, oEndT);
cancelers ^= true;
}
SkASSERT(!approximately_negative(oEndT - oStartT));
- bool opp = fOperand ^ otherContour->fOperand;
- if (cancelers && !opp) {
+ if (cancelers) {
// make sure startT and endT have t entries
if (startT > 0 || oEndT < 1
|| thisOne.isMissing(startT) || other.isMissing(oEndT)) {
- thisOne.addTPair(startT, &other, oEndT, true, coincidence.fPts[0]);
+ thisOne.addTPair(startT, &other, oEndT, true, coincidence.fPts[startSwapped]);
}
if (oStartT > 0 || endT < 1
|| thisOne.isMissing(endT) || other.isMissing(oStartT)) {
- other.addTPair(oStartT, &thisOne, endT, true, coincidence.fPts[1]);
+ other.addTPair(oStartT, &thisOne, endT, true, coincidence.fPts[oStartSwapped]);
}
} else {
if (startT > 0 || oStartT > 0
|| thisOne.isMissing(startT) || other.isMissing(oStartT)) {
- thisOne.addTPair(startT, &other, oStartT, true, coincidence.fPts[0]);
+ thisOne.addTPair(startT, &other, oStartT, true, coincidence.fPts[startSwapped]);
}
if (endT < 1 || oEndT < 1
|| thisOne.isMissing(endT) || other.isMissing(oEndT)) {
- other.addTPair(oEndT, &thisOne, endT, true, coincidence.fPts[1]);
+ other.addTPair(oEndT, &thisOne, endT, true, coincidence.fPts[!oStartSwapped]);
}
}
#if DEBUG_CONCIDENT
@@ -135,8 +133,7 @@
cancelers ^= true;
}
SkASSERT(!approximately_negative(oEndT - oStartT));
- bool opp = fOperand ^ otherContour->fOperand;
- if (cancelers && !opp) {
+ if (cancelers) {
// make sure startT and endT have t entries
if (!thisOne.done() && !other.done()) {
thisOne.addTCancel(startT, endT, &other, oStartT, oEndT);
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index 2f1dbd5..c90c218 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -204,7 +204,7 @@
}
#endif
-#if DEBUG_ACTIVE_SPANS
+#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void debugShowActiveSpans() {
for (int index = 0; index < fSegments.count(); ++index) {
fSegments[index].debugShowActiveSpans();
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index b5702cb..bcefd71 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -450,6 +450,11 @@
span->fT = newT;
span->fOther = other;
span->fPt = pt;
+#if 0
+ // cubics, for instance, may not be exact enough to satisfy this check (e.g., cubicOp69d)
+ SkASSERT(approximately_equal(xyAtT(newT).fX, pt.fX)
+ && approximately_equal(xyAtT(newT).fY, pt.fY));
+#endif
span->fWindSum = SK_MinS32;
span->fOppSum = SK_MinS32;
span->fWindValue = 1;
@@ -533,13 +538,16 @@
// set spans from start to end to decrement by one
// note this walks other backwards
-// FIMXE: there's probably an edge case that can be constructed where
+// FIXME: there's probably an edge case that can be constructed where
// two span in one segment are separated by float epsilon on one span but
// not the other, if one segment is very small. For this
// case the counts asserted below may or may not be enough to separate the
// spans. Even if the counts work out, what if the spans aren't correctly
// sorted? It feels better in such a case to match the span's other span
// pointer since both coincident segments must contain the same spans.
+// FIXME? It seems that decrementing by one will fail for complex paths that
+// have three or more coincident edges. Shouldn't this subtract the difference
+// between the winding values?
void SkOpSegment::addTCancel(double startT, double endT, SkOpSegment* other,
double oStartT, double oEndT) {
SkASSERT(!approximately_negative(endT - startT));
@@ -558,14 +566,19 @@
SkTDArray<double> outsideTs;
SkTDArray<double> oOutsideTs;
do {
- bool decrement = test->fWindValue && oTest->fWindValue && !binary;
+ 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;
do {
if (decrement) {
- decrementSpan(span);
+ if (binary && bigger) {
+ span->fOppValue--;
+ } else {
+ decrementSpan(span);
+ }
} else if (track && span->fT < 1 && oTestT < 1) {
TrackOutside(&outsideTs, span->fT, oTestT);
}
@@ -581,7 +594,11 @@
SkASSERT(originalWindValue == oSpan->fWindValue);
#endif
if (decrement) {
- other->decrementSpan(oSpan);
+ if (binary && !bigger) {
+ oSpan->fOppValue--;
+ } else {
+ other->decrementSpan(oSpan);
+ }
} else if (track && oSpan->fT < 1 && testT < 1) {
TrackOutside(&oOutsideTs, oSpan->fT, testT);
}
@@ -758,14 +775,14 @@
void SkOpSegment::addTwoAngles(int start, int end, SkTDArray<SkOpAngle>* angles) const {
// add edge leading into junction
int min = SkMin32(end, start);
- if (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0) {
+ if (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0) {
addAngle(angles, end, start);
}
// add edge leading away from junction
int step = SkSign32(end - start);
int tIndex = nextExactSpan(end, step);
min = SkMin32(end, tIndex);
- if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0)) {
+ if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue != 0)) {
addAngle(angles, end, tIndex);
}
}
@@ -912,6 +929,10 @@
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)) {
@@ -920,6 +941,10 @@
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);
}
@@ -2241,6 +2266,10 @@
int otherEnd = other->nextExactSpan(*index, step);
SkASSERT(otherEnd >= 0);
*min = SkMin32(*index, otherEnd);
+ if (other->fTs[*min].fTiny) {
+ *last = NULL;
+ return NULL;
+ }
return other;
}
@@ -2489,7 +2518,7 @@
}
void SkOpSegment::zeroSpan(SkOpSpan* span) {
- SkASSERT(span->fWindValue > 0 || span->fOppValue > 0);
+ SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
span->fWindValue = 0;
span->fOppValue = 0;
SkASSERT(!span->fDone);
@@ -2557,7 +2586,7 @@
}
#endif
-#if DEBUG_ACTIVE_SPANS
+#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void SkOpSegment::debugShowActiveSpans() const {
if (done()) {
return;
@@ -2572,6 +2601,7 @@
if (fTs[i].fDone) {
continue;
}
+ SkASSERT(i < fTs.count() - 1);
#if DEBUG_ACTIVE_SPANS_SHORT_FORM
if (lastId == fID && lastT == fTs[i].fT) {
continue;
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 093bf60..d2322c8 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -240,6 +240,8 @@
void addTCoincident(double startT, double endT, SkOpSegment* other, double oStartT,
double oEndT);
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;
int computeSum(int startIndex, int endIndex, bool binary);
@@ -292,7 +294,7 @@
return fID;
}
#endif
-#if DEBUG_ACTIVE_SPANS
+#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void debugShowActiveSpans() const;
#endif
#if DEBUG_SORT || DEBUG_SWAP_TOP
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index f1ed169..a089d7c 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -206,7 +206,7 @@
return NULL;
}
-#if DEBUG_ACTIVE_SPANS
+#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void DebugShowActiveSpans(SkTDArray<SkOpContour*>& contourList) {
int index;
for (index = 0; index < contourList.count(); ++ index) {
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index 5a46807..8bbe232 100644
--- a/src/pathops/SkPathOpsCommon.h
+++ b/src/pathops/SkPathOpsCommon.h
@@ -22,7 +22,7 @@
bool evenOdd, bool oppEvenOdd);
void SortSegments(SkTDArray<SkOpContour*>* contourList);
-#if DEBUG_ACTIVE_SPANS
+#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void DebugShowActiveSpans(SkTDArray<SkOpContour*>& contourList);
#endif
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index ece3b14..2d0962b 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -6,6 +6,7 @@
*/
#include "SkPathOpsDebug.h"
+#include "SkPath.h"
#if defined SK_DEBUG || !FORCE_RELEASE
@@ -59,3 +60,65 @@
#if DEBUG_ACTIVE_OP
const char* kPathOpStr[] = {"diff", "sect", "union", "xor"};
#endif
+
+#if DEBUG_SHOW_PATH
+static void showPathContours(SkPath::Iter& iter, const char* pathName) {
+ uint8_t verb;
+ SkPoint pts[4];
+ while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+ switch (verb) {
+ case SkPath::kMove_Verb:
+ SkDebugf("%s.moveTo(%#1.9gf, %#1.9gf);\n", pathName, pts[0].fX, pts[0].fY);
+ continue;
+ case SkPath::kLine_Verb:
+ SkDebugf("%s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY);
+ break;
+ case SkPath::kQuad_Verb:
+ SkDebugf("%s.quadTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", pathName,
+ pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY);
+ break;
+ case SkPath::kCubic_Verb:
+ SkDebugf("%s.cubicTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n",
+ pathName, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY);
+ break;
+ case SkPath::kClose_Verb:
+ SkDebugf("%s.close();\n", pathName);
+ break;
+ default:
+ SkDEBUGFAIL("bad verb");
+ return;
+ }
+ }
+}
+
+static const char* gFillTypeStr[] = {
+ "kWinding_FillType",
+ "kEvenOdd_FillType",
+ "kInverseWinding_FillType",
+ "kInverseEvenOdd_FillType"
+};
+
+void ShowPath(const SkPath& path, const char* pathName) {
+ SkPath::Iter iter(path, true);
+ SkPath::FillType fillType = path.getFillType();
+ SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType);
+ SkDebugf("SkPath %s;\n", pathName);
+ SkDebugf("%s.setFillType(SkPath::%s);\n", pathName, gFillTypeStr[fillType]);
+ iter.setPath(path, true);
+ showPathContours(iter, pathName);
+}
+
+static const char* gOpStrs[] = {
+ "kDifference_PathOp",
+ "kIntersect_PathOp",
+ "kUnion_PathOp",
+ "kXor_PathOp",
+ "kReverseDifference_PathOp",
+};
+
+void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo) {
+ SkDebugf("SkPath result;\n");
+ SkDebugf("bool success = Op(%s, %s, %s, &result);\n", pathOne, pathTwo, gOpStrs[op]);
+ SkDebugf("SkASSERT(success);\n");
+}
+#endif
diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h
index b11bd76..61b59c3 100644
--- a/src/pathops/SkPathOpsDebug.h
+++ b/src/pathops/SkPathOpsDebug.h
@@ -7,6 +7,7 @@
#ifndef SkPathOpsDebug_DEFINED
#define SkPathOpsDebug_DEFINED
+#include "SkPathOps.h"
#include "SkTypes.h"
#ifdef SK_RELEASE
@@ -42,7 +43,8 @@
#define DEBUG_ACTIVE_OP 0
#define DEBUG_ACTIVE_SPANS 0
-#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
+#define DEBUG_ACTIVE_SPANS_FIRST_ONLY 0
+#define DEBUG_ACTIVE_SPANS_SHORT_FORM 1
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_ADD_T_PAIR 0
#define DEBUG_ANGLE 0
@@ -54,10 +56,12 @@
#define DEBUG_FLOW 0
#define DEBUG_MARK_DONE 0
#define DEBUG_PATH_CONSTRUCTION 0
+#define DEBUG_SHOW_PATH 0
#define DEBUG_SHOW_TEST_NAME 0
#define DEBUG_SHOW_TEST_PROGRESS 0
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 0
+#define DEBUG_SORT_SINGLE 0
#define DEBUG_SWAP_TOP 0
#define DEBUG_UNSORTABLE 0
#define DEBUG_WIND_BUMP 0
@@ -68,6 +72,7 @@
#define DEBUG_ACTIVE_OP 1
#define DEBUG_ACTIVE_SPANS 1
+#define DEBUG_ACTIVE_SPANS_FIRST_ONLY 0
#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
#define DEBUG_ADD_INTERSECTING_TS 1
#define DEBUG_ADD_T_PAIR 1
@@ -80,10 +85,12 @@
#define DEBUG_FLOW 1
#define DEBUG_MARK_DONE 1
#define DEBUG_PATH_CONSTRUCTION 1
+#define DEBUG_SHOW_PATH 0
#define DEBUG_SHOW_TEST_NAME 1
#define DEBUG_SHOW_TEST_PROGRESS 1
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 1
+#define DEBUG_SORT_SINGLE 0
#define DEBUG_SWAP_TOP 1
#define DEBUG_UNSORTABLE 1
#define DEBUG_WIND_BUMP 0
@@ -93,7 +100,7 @@
#endif
#define DEBUG_DUMP (DEBUG_ACTIVE_OP | DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | \
- DEBUG_PATH_CONSTRUCTION)
+ DEBUG_SORT_SINGLE | DEBUG_PATH_CONSTRUCTION)
#if DEBUG_AS_C_CODE
#define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
@@ -136,4 +143,9 @@
#define DEBUG_TEST 0
#endif
+#if DEBUG_SHOW_PATH
+void ShowPath(const SkPath& path, const char* pathName);
+void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo);
+#endif
+
#endif
diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 80e698c..db55635 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -149,11 +149,15 @@
do {
if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
do {
- #if DEBUG_ACTIVE_SPANS
if (!unsortable && current->done()) {
+ #if DEBUG_ACTIVE_SPANS
DebugShowActiveSpans(contourList);
- }
#endif
+ if (simple->isEmpty()) {
+ simple->init();
+ break;
+ }
+ }
SkASSERT(unsortable || !current->done());
int nextStart = index;
int nextEnd = endIndex;
@@ -177,10 +181,10 @@
current = next;
index = nextStart;
endIndex = nextEnd;
- } while (!simple->isClosed() && ((!unsortable)
+ } while (!simple->isClosed() && (!unsortable
|| !current->done(SkMin32(index, endIndex))));
if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
- SkASSERT(unsortable);
+ SkASSERT(unsortable || simple->isEmpty());
int min = SkMin32(index, endIndex);
if (!current->done(min)) {
current->addCurveTo(index, endIndex, simple, true);
@@ -227,6 +231,11 @@
};
bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
+#if DEBUG_SHOW_PATH
+ ShowPath(one, "path");
+ ShowPath(two, "pathB");
+ ShowOp(op, "path", "pathB");
+#endif
op = gOpInverse[op][one.isInverseFillType()][two.isInverseFillType()];
SkPath::FillType fillType = gOutInverse[op][one.isInverseFillType()][two.isInverseFillType()]
? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
@@ -288,7 +297,7 @@
#endif
FixOtherTIndex(&contourList);
SortSegments(&contourList);
-#if DEBUG_ACTIVE_SPANS
+#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
DebugShowActiveSpans(contourList);
#endif
// construct closed contours
diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h
index aca38d8..23734c9 100644
--- a/src/pathops/SkPathOpsPoint.h
+++ b/src/pathops/SkPathOpsPoint.h
@@ -10,6 +10,10 @@
#include "SkPathOpsTypes.h"
#include "SkPoint.h"
+inline bool AlmostEqualUlps(const SkPoint& pt1, const SkPoint& pt2) {
+ return AlmostEqualUlps(pt1.fX, pt2.fX) && AlmostEqualUlps(pt1.fY, pt2.fY);
+}
+
struct SkDVector {
double fX, fY;
diff --git a/src/pathops/SkPathOpsRect.h b/src/pathops/SkPathOpsRect.h
index 7b516a4..2c47f43 100644
--- a/src/pathops/SkPathOpsRect.h
+++ b/src/pathops/SkPathOpsRect.h
@@ -27,7 +27,6 @@
}
}
- // FIXME: used by debugging only ?
bool contains(const SkDPoint& pt) const {
return approximately_between(fLeft, pt.fX, fRight)
&& approximately_between(fTop, pt.fY, fBottom);
@@ -46,6 +45,14 @@
fTop = fBottom = pt.fY;
}
+ double width() const {
+ return fRight - fLeft;
+ }
+
+ double height() const {
+ return fBottom - fTop;
+ }
+
void setBounds(const SkDLine&);
void setBounds(const SkDCubic&);
void setBounds(const SkDQuad&);
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index cb00aff..9a319e0 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -32,11 +32,15 @@
do {
if (current->activeWinding(index, endIndex)) {
do {
- #if DEBUG_ACTIVE_SPANS
if (!unsortable && current->done()) {
+ #if DEBUG_ACTIVE_SPANS
DebugShowActiveSpans(contourList);
- }
#endif
+ if (simple->isEmpty()) {
+ simple->init();
+ break;
+ }
+ }
SkASSERT(unsortable || !current->done());
int nextStart = index;
int nextEnd = endIndex;
@@ -63,7 +67,7 @@
} while (!simple->isClosed() && (!unsortable
|| !current->done(SkMin32(index, endIndex))));
if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
- SkASSERT(unsortable);
+ SkASSERT(unsortable || simple->isEmpty());
int min = SkMin32(index, endIndex);
if (!current->done(min)) {
current->addCurveTo(index, endIndex, simple, true);
@@ -182,7 +186,7 @@
CoincidenceCheck(&contourList, 0);
FixOtherTIndex(&contourList);
SortSegments(&contourList);
-#if DEBUG_ACTIVE_SPANS
+#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
DebugShowActiveSpans(contourList);
#endif
// construct closed contours
diff --git a/src/pathops/SkPathWriter.cpp b/src/pathops/SkPathWriter.cpp
index e367228..5559026 100644
--- a/src/pathops/SkPathWriter.cpp
+++ b/src/pathops/SkPathWriter.cpp
@@ -4,7 +4,7 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
-#include "SkPathOpsTypes.h"
+#include "SkPathOpsPoint.h"
#include "SkPathWriter.h"
// wrap path to keep track of whether the contour is initialized and non-empty
@@ -37,6 +37,11 @@
void SkPathWriter::cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) {
lineTo();
+ if (fEmpty && AlmostEqualUlps(fDefer[0], pt1) && AlmostEqualUlps(pt1, pt2)
+ && AlmostEqualUlps(pt2, pt3)) {
+ deferredLine(pt3);
+ return;
+ }
moveTo();
fDefer[1] = pt3;
nudge();
@@ -116,6 +121,10 @@
void SkPathWriter::quadTo(const SkPoint& pt1, const SkPoint& pt2) {
lineTo();
+ if (fEmpty && AlmostEqualUlps(fDefer[0], pt1) && AlmostEqualUlps(pt1, pt2)) {
+ deferredLine(pt2);
+ return;
+ }
moveTo();
fDefer[1] = pt2;
nudge();
diff --git a/src/pathops/SkPathWriter.h b/src/pathops/SkPathWriter.h
index f90a580..5747082 100644
--- a/src/pathops/SkPathWriter.h
+++ b/src/pathops/SkPathWriter.h
@@ -20,6 +20,7 @@
bool hasMove() const;
void init();
bool isClosed() const;
+ bool isEmpty() const { return fEmpty; }
void lineTo();
const SkPath* nativePath() const;
void nudge();