diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/pathops/SkAddIntersections.cpp | 4 | ||||
-rw-r--r-- | src/pathops/SkDCubicIntersection.cpp | 98 | ||||
-rw-r--r-- | src/pathops/SkDCubicLineIntersection.cpp | 6 | ||||
-rw-r--r-- | src/pathops/SkDLineIntersection.cpp | 21 | ||||
-rw-r--r-- | src/pathops/SkDQuadLineIntersection.cpp | 6 | ||||
-rw-r--r-- | src/pathops/SkIntersections.h | 1 | ||||
-rw-r--r-- | src/pathops/SkOpAngle.cpp | 91 | ||||
-rw-r--r-- | src/pathops/SkOpContour.cpp | 23 | ||||
-rw-r--r-- | src/pathops/SkOpContour.h | 2 | ||||
-rw-r--r-- | src/pathops/SkOpSegment.cpp | 46 | ||||
-rw-r--r-- | src/pathops/SkOpSegment.h | 4 | ||||
-rw-r--r-- | src/pathops/SkPathOpsCommon.cpp | 2 | ||||
-rw-r--r-- | src/pathops/SkPathOpsCommon.h | 2 | ||||
-rw-r--r-- | src/pathops/SkPathOpsDebug.cpp | 63 | ||||
-rw-r--r-- | src/pathops/SkPathOpsDebug.h | 16 | ||||
-rw-r--r-- | src/pathops/SkPathOpsOp.cpp | 19 | ||||
-rw-r--r-- | src/pathops/SkPathOpsPoint.h | 4 | ||||
-rw-r--r-- | src/pathops/SkPathOpsRect.h | 9 | ||||
-rw-r--r-- | src/pathops/SkPathOpsSimplify.cpp | 12 | ||||
-rw-r--r-- | src/pathops/SkPathWriter.cpp | 11 | ||||
-rw-r--r-- | src/pathops/SkPathWriter.h | 1 |
21 files changed, 314 insertions, 127 deletions
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index 9efd4d63eb..1884d4e4a1 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -208,7 +208,7 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next) { 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 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next) { 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 10d4e71d03..922c1030d1 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -138,7 +138,6 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC } } 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 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC 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 @@ static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cub 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 @@ static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cub i.insert(start ? 0 : 1, foundT, line[0]); } } else { - *tVals.append() = local[0][idx2]; + *tVals.append() = foundT; } } } @@ -362,6 +323,57 @@ static void intersectEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cub } 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 5df3acacfd..11876f8d73 100644 --- a/src/pathops/SkDCubicLineIntersection.cpp +++ b/src/pathops/SkDCubicLineIntersection.cpp @@ -257,5 +257,9 @@ int SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) { 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 5fd7d61d7d..b1e1783e57 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -142,27 +142,6 @@ int SkIntersections::horizontal(const SkDLine& line, double y) { 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 e7e77e69e2..afaa1552e4 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -329,5 +329,9 @@ int SkIntersections::intersect(const SkDQuad& quad, const SkDLine& line) { 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 a677a38b43..83ff6b1549 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -188,7 +188,6 @@ public: 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 65af3830a6..750520a73f 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 @@ tangent angle 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 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { && !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 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { 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 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { 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 1aee4055c2..6266c65cf8 100644 --- a/src/pathops/SkOpContour.cpp +++ b/src/pathops/SkOpContour.cpp @@ -64,38 +64,36 @@ void SkOpContour::addCoincidentPoints() { #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 @@ void SkOpContour::calcCoincidentWinding() { 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 2f1dbd51fa..c90c218344 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -204,7 +204,7 @@ public: } #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 b5702cb7f8..bcefd71d60 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -450,6 +450,11 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { 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 @@ int SkOpSegment::addT(SkOpSegment* other, const SkPoint& pt, double newT) { // 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 @@ void SkOpSegment::addTCancel(double startT, double endT, SkOpSegment* other, 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 @@ void SkOpSegment::addTCancel(double startT, double endT, SkOpSegment* other, 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::addTPair(double t, SkOpSegment* other, double otherT, bool bor 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 @@ int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) { 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 @@ int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) { 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 @@ SkOpSegment* SkOpSegment::nextChase(int* index, const int step, int* min, SkOpSp 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 @@ int SkOpSegment::windValueAt(double t) const { } 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 @@ void SkOpSegment::debugShowTs() const { } #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 @@ void SkOpSegment::debugShowActiveSpans() const { 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 093bf600c3..d2322c8be1 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -240,6 +240,8 @@ public: 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 @@ public: 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 f1ed1697de..a089d7c7f2 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -206,7 +206,7 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) 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 5a468074ff..8bbe232fc7 100644 --- a/src/pathops/SkPathOpsCommon.h +++ b/src/pathops/SkPathOpsCommon.h @@ -22,7 +22,7 @@ void MakeContourList(SkTArray<SkOpContour>& contours, SkTDArray<SkOpContour*>& l 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 ece3b14fe2..2d0962b1e4 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 @@ int gDebugSortCount; #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 b11bd76cbc..61b59c3189 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 @@ extern int gDebugMaxWindValue; #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 @@ extern int gDebugMaxWindValue; #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 @@ extern int gDebugMaxWindValue; #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 @@ extern int gDebugMaxWindValue; #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 @@ extern int gDebugMaxWindValue; #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 @@ extern const char* kPathOpStr[]; #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 80e698ca5b..db55635d89 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -149,11 +149,15 @@ static bool bridgeOp(SkTDArray<SkOpContour*>& contourList, const SkPathOp op, 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 @@ static bool bridgeOp(SkTDArray<SkOpContour*>& contourList, const SkPathOp op, 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 @@ static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = { }; 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 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { #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 aca38d8900..23734c98b5 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 7b516a40f5..2c47f43b88 100644 --- a/src/pathops/SkPathOpsRect.h +++ b/src/pathops/SkPathOpsRect.h @@ -27,7 +27,6 @@ struct SkDRect { } } - // 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 @@ struct SkDRect { 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 cb00aff8a2..9a319e08ba 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -32,11 +32,15 @@ static bool bridgeWinding(SkTDArray<SkOpContour*>& contourList, SkPathWriter* si 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 @@ static bool bridgeWinding(SkTDArray<SkOpContour*>& contourList, SkPathWriter* si } 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 @@ bool Simplify(const SkPath& path, SkPath* result) { 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 e367228836..5559026119 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::close() { 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::nudge() { 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 f90a580f5c..574708231b 100644 --- a/src/pathops/SkPathWriter.h +++ b/src/pathops/SkPathWriter.h @@ -20,6 +20,7 @@ public: bool hasMove() const; void init(); bool isClosed() const; + bool isEmpty() const { return fEmpty; } void lineTo(); const SkPath* nativePath() const; void nudge(); |