From a5e55925ea03e76885804bda77408a1d6f04c335 Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Tue, 7 May 2013 18:51:31 +0000 Subject: [PATCH] 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 --- gyp/pathops_unittest.gypi | 1 + src/pathops/SkAddIntersections.cpp | 4 +- src/pathops/SkDCubicIntersection.cpp | 98 +++++++----- src/pathops/SkDCubicLineIntersection.cpp | 6 +- src/pathops/SkDLineIntersection.cpp | 21 --- src/pathops/SkDQuadLineIntersection.cpp | 6 +- src/pathops/SkIntersections.h | 1 - src/pathops/SkOpAngle.cpp | 91 ++++++++--- src/pathops/SkOpContour.cpp | 23 ++- src/pathops/SkOpContour.h | 2 +- src/pathops/SkOpSegment.cpp | 46 +++++- src/pathops/SkOpSegment.h | 4 +- src/pathops/SkPathOpsCommon.cpp | 2 +- src/pathops/SkPathOpsCommon.h | 2 +- src/pathops/SkPathOpsDebug.cpp | 63 ++++++++ src/pathops/SkPathOpsDebug.h | 16 +- src/pathops/SkPathOpsOp.cpp | 19 ++- src/pathops/SkPathOpsPoint.h | 4 + src/pathops/SkPathOpsRect.h | 9 +- src/pathops/SkPathOpsSimplify.cpp | 12 +- src/pathops/SkPathWriter.cpp | 11 +- src/pathops/SkPathWriter.h | 1 + tests/PathOpsAngleTest.cpp | 70 ++++++--- tests/PathOpsCubicIntersectionTest.cpp | 5 +- tests/PathOpsCubicQuadIntersectionTest.cpp | 71 +++++++++ tests/PathOpsExtendedTest.cpp | 11 +- tests/PathOpsLineIntersectionTest.cpp | 56 +++++-- tests/PathOpsOpTest.cpp | 245 +++++++++++++++++++++++------ tests/PathOpsQuadLineIntersectionTest.cpp | 4 +- tests/PathOpsSimplifyTest.cpp | 85 +++++++++- tests/PathOpsSkpClipTest.cpp | 61 +++++++ tests/PathOpsThreadedCommon.cpp | 1 + tests/PathOpsThreadedCommon.h | 2 - 33 files changed, 840 insertions(+), 213 deletions(-) create mode 100644 tests/PathOpsCubicQuadIntersectionTest.cpp create mode 100644 tests/PathOpsSkpClipTest.cpp diff --git a/gyp/pathops_unittest.gypi b/gyp/pathops_unittest.gypi index 271edbf..dfbc89c 100644 --- a/gyp/pathops_unittest.gypi +++ b/gyp/pathops_unittest.gypi @@ -5,6 +5,7 @@ '../tests/PathOpsCubicIntersectionTest.cpp', '../tests/PathOpsCubicIntersectionTestData.cpp', '../tests/PathOpsCubicLineIntersectionTest.cpp', + '../tests/PathOpsCubicQuadIntersectionTest.cpp', '../tests/PathOpsCubicReduceOrderTest.cpp', '../tests/PathOpsCubicToQuadsTest.cpp', '../tests/PathOpsDCubicTest.cpp', 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 @@ 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 10d4e71..922c103 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 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 5df3aca..11876f8 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 5fd7d61..b1e1783 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 e7e77e6..afaa155 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 a677a38..83ff6b1 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 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 @@ 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 1aee405..6266c65 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(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 2f1dbd5..c90c218 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 b5702cb..bcefd71 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 outsideTs; SkTDArray 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* 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 093bf60..d2322c8 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 f1ed169..a089d7c 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -206,7 +206,7 @@ SkOpSegment* FindChase(SkTDArray& chase, int& tIndex, int& endIndex) return NULL; } -#if DEBUG_ACTIVE_SPANS +#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY void DebugShowActiveSpans(SkTDArray& 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 @@ void MakeContourList(SkTArray& contours, SkTDArray& l bool evenOdd, bool oppEvenOdd); void SortSegments(SkTDArray* contourList); -#if DEBUG_ACTIVE_SPANS +#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY void DebugShowActiveSpans(SkTDArray& 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 @@ 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 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 @@ 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 80e698c..db55635 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -149,11 +149,15 @@ static bool bridgeOp(SkTDArray& 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& 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 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 @@ 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 cb00aff..9a319e0 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -32,11 +32,15 @@ static bool bridgeWinding(SkTDArray& 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& 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 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::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 f90a580..5747082 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(); diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp index 6714ca4..e0331ec 100644 --- a/tests/PathOpsAngleTest.cpp +++ b/tests/PathOpsAngleTest.cpp @@ -8,11 +8,16 @@ #include "Test.h" static const SkPoint cubics[][4] = { - {{0, 1}, {2, 6}, {4, 2}, {5, 3}} + {{0, 1}, {2, 6}, {4, 2}, {5, 3}}, + {{10, 234}, {10, 229.581726f}, {13.5817204f, 226}, {18, 226}}, +}; + +static const SkPoint quads[][3] = { + {{12.3423996f, 228.342407f}, {10, 230.686295f}, {10, 234}}, }; static const SkPoint lines[][2] = { - {{6, 2}, {2, 4}} + {{6, 2}, {2, 4}}, }; struct SortSet { @@ -36,38 +41,61 @@ static const SortSet set2[] = { {lines[0], 2, 0.574074074, 0.9140625}, }; +static const SortSet set3[] = { + {cubics[1], 4, 0, 1}, + {quads[0], 3, 1, 0}, +}; + struct SortSetTests { const SortSet* set; size_t count; }; static const SortSetTests tests[] = { + { set3, SK_ARRAY_COUNT(set3) }, { set2, SK_ARRAY_COUNT(set2) }, - { set1, SK_ARRAY_COUNT(set1) } + { set1, SK_ARRAY_COUNT(set1) }, }; static void setup(const SortSet* set, const size_t idx, SkPoint const ** data, SkOpSegment* seg, int* ts) { SkPoint start, end; - if (set[idx].ptCount == 2) { - *data = set[idx].ptData; - seg->addLine(*data, false, false); - SkDLine dLine; - dLine.set(set[idx].ptData); - start = dLine.xyAtT(set[idx].tStart).asSkPoint(); - end = dLine.xyAtT(set[idx].tEnd).asSkPoint(); - } else if (set[idx].ptCount == 4) { - *data = set[idx].ptData; - seg->addCubic(*data, false, false); - SkDCubic dCubic; - dCubic.set(set[idx].ptData); - start = dCubic.xyAtT(set[idx].tStart).asSkPoint(); - end = dCubic.xyAtT(set[idx].tEnd).asSkPoint(); + *data = set[idx].ptData; + switch(set[idx].ptCount) { + case 2: { + seg->addLine(*data, false, false); + SkDLine dLine; + dLine.set(set[idx].ptData); + start = dLine.xyAtT(set[idx].tStart).asSkPoint(); + end = dLine.xyAtT(set[idx].tEnd).asSkPoint(); + } break; + case 3: { + seg->addQuad(*data, false, false); + SkDQuad dQuad; + dQuad.set(set[idx].ptData); + start = dQuad.xyAtT(set[idx].tStart).asSkPoint(); + end = dQuad.xyAtT(set[idx].tEnd).asSkPoint(); + } break; + case 4: { + seg->addCubic(*data, false, false); + SkDCubic dCubic; + dCubic.set(set[idx].ptData); + start = dCubic.xyAtT(set[idx].tStart).asSkPoint(); + end = dCubic.xyAtT(set[idx].tEnd).asSkPoint(); + } break; + } + double tStart = set[idx].tStart; + double tEnd = set[idx].tEnd; + seg->addT(NULL, start, tStart); + seg->addT(NULL, end, tEnd); + double tLeft = tStart < tEnd ? 0 : 1; + if (tStart != tLeft && tEnd != tLeft) { + seg->addT(NULL, set[idx].ptData[0], tLeft); + } + double tRight = tStart < tEnd ? 1 : 0; + if (tStart != tRight && tEnd != tRight) { + seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], tRight); } - seg->addT(NULL, start, set[idx].tStart); - seg->addT(NULL, end, set[idx].tEnd); - seg->addT(NULL, set[idx].ptData[0], 0); - seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], 1); int tIndex = 0; do { if (seg->t(tIndex) == set[idx].tStart) { diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp index 6af76c2..58d7d98 100644 --- a/tests/PathOpsCubicIntersectionTest.cpp +++ b/tests/PathOpsCubicIntersectionTest.cpp @@ -163,6 +163,9 @@ static const SkDCubic testSet[] = { const size_t testSetCount = SK_ARRAY_COUNT(testSet); static const SkDCubic newTestSet[] = { +{{{0, 1}, {2, 3}, {5, 1}, {4, 3}}}, +{{{1, 5}, {3, 4}, {1, 0}, {3, 2}}}, + {{{3, 5}, {1, 6}, {5, 0}, {3, 1}}}, {{{0, 5}, {1, 3}, {5, 3}, {6, 1}}}, @@ -286,8 +289,8 @@ static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) { } static void oneOffTest(skiatest::Reporter* reporter) { - oneOff(reporter, 14, 16); newOneOff(reporter, 0, 1); + oneOff(reporter, 14, 16); } static void oneOffTests(skiatest::Reporter* reporter) { diff --git a/tests/PathOpsCubicQuadIntersectionTest.cpp b/tests/PathOpsCubicQuadIntersectionTest.cpp new file mode 100644 index 0000000..8b47a8e --- /dev/null +++ b/tests/PathOpsCubicQuadIntersectionTest.cpp @@ -0,0 +1,71 @@ +/* + * Copyright 2013 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ +#include "SkIntersections.h" +#include "SkPathOpsCubic.h" +#include "SkPathOpsQuad.h" +#include "SkReduceOrder.h" +#include "Test.h" + +static struct lineCubic { + SkDCubic cubic; + SkDQuad quad; + int answerCount; + SkDPoint answers[2]; +} quadCubicTests[] = { + {{{{10,234}, {10,229.58172607421875}, {13.581720352172852,226}, {18,226}}}, + {{{18,226}, {14.686291694641113,226}, {12.342399597167969,228.3424072265625}}}, 1, + {{18,226}, {0,0}}}, + {{{{10,234}, {10,229.58172607421875}, {13.581720352172852,226}, {18,226}}}, + {{{12.342399597167969,228.3424072265625}, {10,230.68629455566406}, {10,234}}}, 1, + {{10,234}, {0,0}}}, +}; + +static const size_t quadCubicTests_count = SK_ARRAY_COUNT(quadCubicTests); + +static void PathOpsCubicQuadIntersectionTest(skiatest::Reporter* reporter) { + for (size_t index = 0; index < quadCubicTests_count; ++index) { + int iIndex = static_cast(index); + const SkDCubic& cubic = quadCubicTests[index].cubic; + const SkDQuad& quad = quadCubicTests[index].quad; + SkReduceOrder reduce1; + SkReduceOrder reduce2; + int order1 = reduce1.reduce(cubic, SkReduceOrder::kNo_Quadratics, + SkReduceOrder::kFill_Style); + int order2 = reduce2.reduce(quad, SkReduceOrder::kFill_Style); + if (order1 != 4) { + SkDebugf("[%d] cubic order=%d\n", iIndex, order1); + REPORTER_ASSERT(reporter, 0); + } + if (order2 != 3) { + SkDebugf("[%d] quad order=%d\n", iIndex, order2); + REPORTER_ASSERT(reporter, 0); + } + SkIntersections i; + int roots = i.intersect(cubic, quad); + SkASSERT(roots == quadCubicTests[index].answerCount); + for (int pt = 0; pt < roots; ++pt) { + double tt1 = i[0][pt]; + SkDPoint xy1 = cubic.xyAtT(tt1); + double tt2 = i[1][pt]; + SkDPoint xy2 = quad.xyAtT(tt2); + if (!xy1.approximatelyEqual(xy2)) { + SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", + __FUNCTION__, iIndex, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY); + } + REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); + bool found = false; + for (int idx2 = 0; idx2 < quadCubicTests[index].answerCount; ++idx2) { + found |= quadCubicTests[index].answers[idx2].approximatelyEqual(xy1); + } + REPORTER_ASSERT(reporter, found); + } + reporter->bumpTestCount(); + } +} + +#include "TestClassDef.h" +DEFINE_TESTCLASS_SHORT(PathOpsCubicQuadIntersectionTest) diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp index 8d7ca28..71631c1 100644 --- a/tests/PathOpsExtendedTest.cpp +++ b/tests/PathOpsExtendedTest.cpp @@ -12,6 +12,7 @@ #include "SkMatrix.h" #include "SkPaint.h" #include "SkStream.h" +#include "SkThreadPool.h" #ifdef SK_BUILD_FOR_MAC #include @@ -78,7 +79,7 @@ void showPath(const SkPath& path, const char* str) { showPath(path); } -const char* fillTypeStr[] = { +static const char* fillTypeStr[] = { "kWinding_FillType", "kEvenOdd_FillType", "kInverseWinding_FillType", @@ -478,7 +479,7 @@ bool testSimplify(SkPath& path, bool useXor, SkPath& out, PathOpsThreadState& st } bool testSimplify(skiatest::Reporter* reporter, const SkPath& path) { -#if FORCE_RELEASE == 0 +#if DEBUG_SHOW_TEST_NAME showPathData(path); #endif SkPath out; @@ -498,7 +499,7 @@ bool testSimplify(skiatest::Reporter* reporter, const SkPath& path) { bool testPathOp(skiatest::Reporter* reporter, const SkPath& a, const SkPath& b, const SkPathOp shapeOp) { -#if FORCE_RELEASE == 0 +#if DEBUG_SHOW_TEST_NAME showPathData(a); showOp(shapeOp); showPathData(b); @@ -595,7 +596,7 @@ void RunTestSet(skiatest::Reporter* reporter, TestDesc tests[], size_t count, while (index > 0 && tests[index].fun != firstTest) { --index; } -#if FORCE_RELEASE == 0 +#if DEBUG_SHOW_TEST_NAME SkDebugf("
\n", tests[index].str); SkDebugf(" %s [%s]\n", __FUNCTION__, tests[index].str); #endif @@ -605,7 +606,7 @@ void RunTestSet(skiatest::Reporter* reporter, TestDesc tests[], size_t count, size_t last = reverse ? 0 : count - 1; do { if (tests[index].fun != firstTest) { - #if FORCE_RELEASE == 0 + #if DEBUG_SHOW_TEST_NAME SkDebugf("
\n", tests[index].str); SkDebugf(" %s [%s]\n", __FUNCTION__, tests[index].str); #endif diff --git a/tests/PathOpsLineIntersectionTest.cpp b/tests/PathOpsLineIntersectionTest.cpp index 675ce9d..b1bb667 100644 --- a/tests/PathOpsLineIntersectionTest.cpp +++ b/tests/PathOpsLineIntersectionTest.cpp @@ -10,6 +10,8 @@ // FIXME: add tests for intersecting, non-intersecting, degenerate, coincident static const SkDLine tests[][2] = { + {{{{192, 4}, {243, 4}}}, {{{246, 4}, {189, 4}}}}, + {{{{246, 4}, {189, 4}}}, {{{192, 4}, {243, 4}}}}, {{{{5, 0}, {0, 5}}}, {{{5, 4}, {1, 4}}}}, {{{{0, 0}, {1, 0}}}, {{{1, 0}, {0, 0}}}}, {{{{0, 0}, {0, 0}}}, {{{0, 0}, {1, 0}}}}, @@ -32,6 +34,20 @@ static const SkDLine noIntersect[][2] = { static const size_t noIntersect_count = SK_ARRAY_COUNT(noIntersect); +static void check_results(skiatest::Reporter* reporter, const SkDLine& line1, const SkDLine& line2, + const SkIntersections& ts) { + for (int i = 0; i < ts.used(); ++i) { + SkDPoint result1 = line1.xyAtT(ts[0][i]); + SkDPoint result2 = line2.xyAtT(ts[1][i]); + if (!result1.approximatelyEqual(result2)) { + REPORTER_ASSERT(reporter, ts.used() != 1); + result2 = line2.xyAtT(ts[1][i ^ 1]); + REPORTER_ASSERT(reporter, result1.approximatelyEqual(result2)); + REPORTER_ASSERT(reporter, result1.approximatelyEqual(ts.pt(i).asSkPoint())); + } + } +} + static void PathOpsLineIntersectionTest(skiatest::Reporter* reporter) { size_t index; for (index = 0; index < tests_count; ++index) { @@ -40,14 +56,34 @@ static void PathOpsLineIntersectionTest(skiatest::Reporter* reporter) { SkIntersections ts; int pts = ts.intersect(line1, line2); REPORTER_ASSERT(reporter, pts); - for (int i = 0; i < pts; ++i) { - SkDPoint result1 = line1.xyAtT(ts[0][i]); - SkDPoint result2 = line2.xyAtT(ts[1][i]); - if (!result1.approximatelyEqual(result2)) { - REPORTER_ASSERT(reporter, pts != 1); - result2 = line2.xyAtT(ts[1][i ^ 1]); - REPORTER_ASSERT(reporter, result1.approximatelyEqual(result2)); - } + REPORTER_ASSERT(reporter, pts == ts.used()); + check_results(reporter, line1, line2, ts); + if (line1[0] == line1[1] || line2[0] == line2[1]) { + continue; + } + if (line1[0].fY == line1[1].fY) { + double left = SkTMin(line1[0].fX, line1[1].fX); + double right = SkTMax(line1[0].fX, line1[1].fX); + ts.horizontal(line2, left, right, line1[0].fY, line1[0].fX != left); + check_results(reporter, line2, line1, ts); + } + if (line2[0].fY == line2[1].fY) { + double left = SkTMin(line2[0].fX, line2[1].fX); + double right = SkTMax(line2[0].fX, line2[1].fX); + ts.horizontal(line1, left, right, line2[0].fY, line2[0].fX != left); + check_results(reporter, line1, line2, ts); + } + if (line1[0].fX == line1[1].fX) { + double top = SkTMin(line1[0].fY, line1[1].fY); + double bottom = SkTMax(line1[0].fY, line1[1].fY); + ts.vertical(line2, top, bottom, line1[0].fX, line1[0].fY != top); + check_results(reporter, line2, line1, ts); + } + if (line2[0].fX == line2[1].fX) { + double top = SkTMin(line2[0].fY, line2[1].fY); + double bottom = SkTMax(line2[0].fY, line2[1].fY); + ts.vertical(line1, top, bottom, line2[0].fX, line2[0].fY != top); + check_results(reporter, line1, line2, ts); } } for (index = 0; index < noIntersect_count; ++index) { @@ -55,7 +91,9 @@ static void PathOpsLineIntersectionTest(skiatest::Reporter* reporter) { const SkDLine& line2 = noIntersect[index][1]; SkIntersections ts; int pts = ts.intersect(line1, line2); - REPORTER_ASSERT(reporter, !pts); } + REPORTER_ASSERT(reporter, !pts); + REPORTER_ASSERT(reporter, pts == ts.used()); + } } #include "TestClassDef.h" diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index 995bf16..08dff90 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -1153,43 +1153,206 @@ SkPathOp ops[] = { }; static void rRect1(skiatest::Reporter* reporter) { - SkScalar xA = SkFloatToScalar(0.65f); - SkScalar xB = SkFloatToScalar(10.65f); - SkScalar xC = SkFloatToScalar(20.65f); - SkScalar xD = SkFloatToScalar(30.65f); - SkScalar xE = SkFloatToScalar(40.65f); - SkScalar xF = SkFloatToScalar(50.65f); - - SkScalar yA = SkFloatToScalar(0.65f); - SkScalar yB = SkFloatToScalar(10.65f); - SkScalar yC = SkFloatToScalar(20.65f); - SkScalar yD = SkFloatToScalar(30.65f); - SkScalar yE = SkFloatToScalar(40.65f); - SkScalar yF = SkFloatToScalar(50.65f); - SkPath paths[5]; - SkRect rects[5]; - rects[0].set(xB, yB, xE, yE); - paths[0].addRoundRect(rects[0], SkIntToScalar(5), SkIntToScalar(5)); // red - rects[1].set(xA, yA, xD, yD); - paths[1].addRoundRect(rects[1], SkIntToScalar(5), SkIntToScalar(5)); // green - rects[2].set(xC, yA, xF, yD); - paths[2].addRoundRect(rects[2], SkIntToScalar(5), SkIntToScalar(5)); // blue - rects[3].set(xA, yC, xD, yF); - paths[3].addRoundRect(rects[3], SkIntToScalar(5), SkIntToScalar(5)); // yellow - rects[4].set(xC, yC, xF, yF); - paths[4].addRoundRect(rects[4], SkIntToScalar(5), SkIntToScalar(5)); // cyan - SkPath path; - path.setFillType(SkPath::kInverseEvenOdd_FillType); - for (int index = 0; index < 5; ++index) { - testPathOp(reporter, path, paths[index], ops[index]); - Op(path, paths[index], ops[index], &path); - } + SkScalar xA = SkFloatToScalar(0.65f); + SkScalar xB = SkFloatToScalar(10.65f); + SkScalar xC = SkFloatToScalar(20.65f); + SkScalar xD = SkFloatToScalar(30.65f); + SkScalar xE = SkFloatToScalar(40.65f); + SkScalar xF = SkFloatToScalar(50.65f); + + SkScalar yA = SkFloatToScalar(0.65f); + SkScalar yB = SkFloatToScalar(10.65f); + SkScalar yC = SkFloatToScalar(20.65f); + SkScalar yD = SkFloatToScalar(30.65f); + SkScalar yE = SkFloatToScalar(40.65f); + SkScalar yF = SkFloatToScalar(50.65f); + SkPath paths[5]; + SkRect rects[5]; + rects[0].set(xB, yB, xE, yE); + paths[0].addRoundRect(rects[0], SkIntToScalar(5), SkIntToScalar(5)); // red + rects[1].set(xA, yA, xD, yD); + paths[1].addRoundRect(rects[1], SkIntToScalar(5), SkIntToScalar(5)); // green + rects[2].set(xC, yA, xF, yD); + paths[2].addRoundRect(rects[2], SkIntToScalar(5), SkIntToScalar(5)); // blue + rects[3].set(xA, yC, xD, yF); + paths[3].addRoundRect(rects[3], SkIntToScalar(5), SkIntToScalar(5)); // yellow + rects[4].set(xC, yC, xF, yF); + paths[4].addRoundRect(rects[4], SkIntToScalar(5), SkIntToScalar(5)); // cyan + SkPath path; + path.setFillType(SkPath::kInverseEvenOdd_FillType); + for (int index = 0; index < 5; ++index) { + testPathOp(reporter, path, paths[index], ops[index]); + Op(path, paths[index], ops[index], &path); + } +} + +static void skp1(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(189,7); + path.cubicTo(189,5.34314585f, 190.34314f,4, 192,4); + path.lineTo(243,4); + path.cubicTo(244.65686f,4, 246,5.34314585f, 246,7); + path.lineTo(246,21); + path.cubicTo(246,22.6568546f, 244.65686f,24, 243,24); + path.lineTo(192,24); + path.cubicTo(190.34314f,24, 189,22.6568546f, 189,21); + path.lineTo(189,7); + path.close(); + path.moveTo(191,8); + path.cubicTo(191,6.89543009f, 191.895432f,6, 193,6); + path.lineTo(242,6); + path.cubicTo(243.104568f,6, 244,6.89543009f, 244,8); + path.lineTo(244,20); + path.cubicTo(244,21.1045704f, 243.104568f,22, 242,22); + path.lineTo(193,22); + path.cubicTo(191.895432f,22, 191,21.1045704f, 191,20); + path.lineTo(191,8); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(189,4); + pathB.lineTo(199,14); + pathB.lineTo(236,14); + pathB.lineTo(246,4); + pathB.lineTo(189,4); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void skp2(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(253.000000f, 11757.0000f); + path.lineTo(253.000000f, 222.000000f); + path.lineTo(823.000000f, 222.000000f); + path.lineTo(823.000000f, 11757.0000f); + path.lineTo(253.000000f, 11757.0000f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(258.000000f, 1028.00000f); + pathB.lineTo(258.000000f, 1027.00000f); + pathB.lineTo(823.000000f, 1027.00000f); + pathB.lineTo(823.000000f, 1028.00000f); + pathB.lineTo(258.000000f, 1028.00000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void skp3(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(717.000000f, 507.000000f); + path.lineTo(717.000000f, 425.000000f); + path.lineTo(973.000000f, 425.000000f); + path.lineTo(973.000000f, 507.000000f); + path.quadTo(973.000000f, 508.242645f, 972.121582f, 509.121613f); + path.quadTo(971.242615f, 510.000000f, 970.000000f, 510.000000f); + path.lineTo(720.000000f, 510.000000f); + path.quadTo(718.757385f, 510.000000f, 717.878418f, 509.121613f); + path.quadTo(717.000000f, 508.242645f, 717.000000f, 507.000000f); + path.close(); + path.moveTo(719.000000f, 426.000000f); + path.lineTo(971.000000f, 426.000000f); + path.lineTo(971.000000f, 506.000000f); + path.cubicTo(971.000000f, 507.104584f, 970.104553f, 508.000000f, 969.000000f, 508.000000f); + path.lineTo(721.000000f, 508.000000f); + path.cubicTo(719.895447f, 508.000000f, 719.000000f, 507.104584f, 719.000000f, 506.000000f); + path.lineTo(719.000000f, 426.000000f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(717.000000f, 510.000000f); + pathB.lineTo(760.000000f, 467.000000f); + pathB.lineTo(930.000000f, 467.000000f); + pathB.lineTo(973.000000f, 510.000000f); + pathB.lineTo(717.000000f, 510.000000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void skp4(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(230.756805f, 591.756775f); + path.quadTo(232.514725f, 590.000000f, 235.000000f, 590.000000f); + path.lineTo(300.000000f, 590.000000f); + path.quadTo(302.485291f, 590.000000f, 304.243195f, 591.756775f); + path.quadTo(306.000000f, 593.514709f, 306.000000f, 596.000000f); + path.lineTo(306.000000f, 617.000000f); + path.lineTo(229.000000f, 617.000000f); + path.lineTo(229.000000f, 596.000000f); + path.quadTo(229.000000f, 593.514709f, 230.756805f, 591.756775f); + path.close(); + path.moveTo(231.000000f, 597.000000f); + path.cubicTo(231.000000f, 594.238586f, 233.238571f, 592.000000f, 236.000000f, 592.000000f); + path.lineTo(299.000000f, 592.000000f); + path.cubicTo(301.761414f, 592.000000f, 304.000000f, 594.238586f, 304.000000f, 597.000000f); + path.lineTo(304.000000f, 616.000000f); + path.lineTo(231.000000f, 616.000000f); + path.lineTo(231.000000f, 597.000000f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(306.000000f, 590.000000f); + pathB.lineTo(292.000000f, 604.000000f); + pathB.lineTo(305.000000f, 617.000000f); + pathB.lineTo(306.000000f, 617.000000f); + pathB.lineTo(306.000000f, 590.000000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void skp5(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(18.0000000f, 226.000000f); + path.quadTo(14.6862917f, 226.000000f, 12.3423996f, 228.342407f); + path.quadTo(10.0000000f, 230.686295f, 10.0000000f, 234.000000f); + path.lineTo(10.0000000f, 253.000000f); + path.lineTo(1247.00000f, 253.000000f); + path.lineTo(1247.00000f, 234.000000f); + path.quadTo(1247.00000f, 230.686295f, 1244.65759f, 228.342407f); + path.quadTo(1242.31372f, 226.000000f, 1239.00000f, 226.000000f); + path.lineTo(18.0000000f, 226.000000f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kInverseWinding_FillType); + pathB.moveTo(18.0000000f, 226.000000f); + pathB.lineTo(1239.00000f, 226.000000f); + pathB.cubicTo(1243.41833f, 226.000000f, 1247.00000f, 229.581726f, 1247.00000f, 234.000000f); + pathB.lineTo(1247.00000f, 252.000000f); + pathB.lineTo(10.0000000f, 252.000000f); + pathB.lineTo(10.0000000f, 234.000000f); + pathB.cubicTo(10.0000000f, 229.581726f, 13.5817204f, 226.000000f, 18.0000000f, 226.000000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void cubicOp70d(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(0,5, 4,0, 5,0); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,4); + pathB.cubicTo(0,5, 1,0, 5,0); + pathB.close(); + testPathOp(reporter, path, pathB, kDifference_PathOp); } static void (*firstTest)(skiatest::Reporter* ) = 0; static struct TestDesc tests[] = { + TEST(skp5), + TEST(skp4), + TEST(skp3), + TEST(skp2), + TEST(skp1), TEST(rRect1), + TEST(cubicOp70d), TEST(cubicOp69d), TEST(cubicOp68u), TEST(cubicOp67u), @@ -1288,21 +1451,11 @@ static struct TestDesc tests[] = { static const size_t testCount = SK_ARRAY_COUNT(tests); static struct TestDesc subTests[] = { - TEST(cubicOp43d), - TEST(quadOp9d), - TEST(cubicOp9d), - TEST(cubicOp1i), - TEST(cubicOp10d), - TEST(cubicOp11d), - TEST(cubicOp15d), - TEST(cubicOp18d), - TEST(cubicOp22d), - TEST(cubicOp23d), - TEST(cubicOp24d), - TEST(cubicOp28u), - TEST(cubicOp33i), - TEST(cubicOp36u), - TEST(cubicOp40d), + TEST(cubicOp6d), + TEST(cubicOp8d), + TEST(cubicOp70d), + TEST(cubicOp16d), + TEST(skp5), }; static const size_t subTestCount = SK_ARRAY_COUNT(subTests); diff --git a/tests/PathOpsQuadLineIntersectionTest.cpp b/tests/PathOpsQuadLineIntersectionTest.cpp index 37c8ef3..1615340 100644 --- a/tests/PathOpsQuadLineIntersectionTest.cpp +++ b/tests/PathOpsQuadLineIntersectionTest.cpp @@ -58,6 +58,8 @@ static struct oneLineQuad { SkDQuad quad; SkDLine line; } oneOffs[] = { + {{{{973, 507}, {973, 508.24264526367187}, {972.12158203125, 509.12161254882812}}}, + {{{930, 467}, {973, 510}}}}, {{{{369.848602, 145.680267}, {382.360413, 121.298294}, {406.207703, 121.298294}}}, {{{406.207703, 121.298294}, {348.781738, 123.864815}}}} }; @@ -65,11 +67,11 @@ static struct oneLineQuad { static size_t oneOffs_count = SK_ARRAY_COUNT(oneOffs); static void testOneOffs(skiatest::Reporter* reporter) { - SkIntersections intersections; bool flipped = false; for (size_t index = 0; index < oneOffs_count; ++index) { const SkDQuad& quad = oneOffs[index].quad; const SkDLine& line = oneOffs[index].line; + SkIntersections intersections; int result = doIntersect(intersections, quad, line, flipped); for (int inner = 0; inner < result; ++inner) { double quadT = intersections[0][inner]; diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp index c0d13c8..ce2c89b 100644 --- a/tests/PathOpsSimplifyTest.cpp +++ b/tests/PathOpsSimplifyTest.cpp @@ -3695,9 +3695,92 @@ static void testAddTCoincident2(skiatest::Reporter* reporter) { testSimplify(reporter, path); } +static void testQuad2(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(1, 0); + path.quadTo(0, 1, 3, 2); + path.lineTo(2, 3); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 0); + path.quadTo(0, 1, 1, 1); + path.close(); +} + +static void testQuad3(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(1, 0); + path.quadTo(0, 1, 3, 2); + path.lineTo(3, 3); + path.close(); + path.moveTo(0, 0); + path.lineTo(1, 0); + path.quadTo(0, 1, 1, 1); + path.close(); + testSimplify(reporter, path); +} + +static void testQuad4(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(2, 0); + path.quadTo(0, 1, 1, 1); + path.lineTo(3, 3); + path.close(); + path.moveTo(0, 0); + path.lineTo(2, 0); + path.quadTo(0, 1, 2, 2); + path.close(); + testSimplify(reporter, path); +} + +static void testQuad5(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(2, 0); + path.quadTo(0, 1, 2, 2); + path.lineTo(1, 3); + path.close(); + path.moveTo(0, 0); + path.lineTo(2, 0); + path.quadTo(0, 1, 1, 1); + path.close(); + testSimplify(reporter, path); +} + +static void testQuad6(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(2, 0); + path.quadTo(0, 1, 2, 2); + path.lineTo(1, 3); + path.close(); + path.moveTo(1, 0); + path.lineTo(2, 0); + path.quadTo(0, 1, 1, 1); + path.close(); + testSimplify(reporter, path); +} + +static void testQuad7(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(3, 0); + path.quadTo(0, 1, 1, 1); + path.lineTo(1, 3); + path.close(); + path.moveTo(1, 0); + path.lineTo(3, 0); + path.quadTo(0, 1, 1, 2); + path.close(); + testSimplify(reporter, path); +} + static void (*firstTest)(skiatest::Reporter* ) = 0; static TestDesc tests[] = { + TEST(testQuad7), + TEST(testQuad6), + TEST(testQuad5), + TEST(testQuad4), + TEST(testQuad3), + TEST(testQuad2), TEST(testAddTCoincident2), TEST(testAddTCoincident1), TEST(testTriangles2), @@ -3707,7 +3790,7 @@ static TestDesc tests[] = { TEST(testQuadratic95), TEST(testQuadratic94), TEST(testQuadralateral2), - TEST(testQuad1), // FIXME: fails, need to investigate + TEST(testQuad1), TEST(testCubic2), TEST(testCubic1), TEST(testQuadralateral1), diff --git a/tests/PathOpsSkpClipTest.cpp b/tests/PathOpsSkpClipTest.cpp new file mode 100644 index 0000000..595a91a --- /dev/null +++ b/tests/PathOpsSkpClipTest.cpp @@ -0,0 +1,61 @@ +#include "SkBitmap.h" +#include "SkDevice.h" +#include "SkCanvas.h" +#include "SkImageEncoder.h" +#include "SkStream.h" +#include "SkOSFile.h" +#include "SkPicture.h" +#include "SkString.h" +#include "Test.h" + +static void make_filepath(SkString* path, const char* dir, const SkString& name) { + size_t len = strlen(dir); + path->set(dir); + if (len > 0 && dir[len - 1] != '/') { + path->append("\\"); + } + path->append(name); +} + +static void PathOpsSkpClipTest(skiatest::Reporter* reporter) { +const char pictDir[] = "C:\\Users\\caryclark\\skp"; + const char outSkpClipDir[] = "C:\\Users\\caryclark\\skpClip"; + const char outOldClipDir[] = "C:\\Users\\caryclark\\oldClip"; + SkOSFile::Iter iter(pictDir, "skp"); + SkString filename; + while (iter.next(&filename)) { +#if 0 + if (strcmp(filename.c_str(), "tabl_androidpolice.skp")) { + continue; + } +#endif + SkString path; + make_filepath(&path, pictDir, filename); + SkFILEStream stream(path.c_str()); + if (!stream.isValid()) { + continue; + } + SkPicture* pic = SkNEW_ARGS(SkPicture, (&stream)); + int width = pic->width(); + int height = pic->height(); + SkBitmap bitmap; + bitmap.setConfig(SkBitmap::kARGB_8888_Config, width, height); + bitmap.allocPixels(); + SkCanvas canvas(bitmap); + filename.remove(filename.size() - 3, 3); + filename.append("png"); + for (int i = 0; i < 2; ++i) { + bool useOp = i ? true : false; + canvas.setAllowSimplifyClip(useOp); + pic->draw(&canvas); + SkString outFile; + make_filepath(&outFile, useOp ? outSkpClipDir : outOldClipDir, filename); + SkImageEncoder::EncodeFile(outFile.c_str(), bitmap, SkImageEncoder::kPNG_Type, 100); + } + SkDELETE(pic); + reporter->bumpTestCount(); + } +} + +#include "TestClassDef.h" +DEFINE_TESTCLASS_SHORT(PathOpsSkpClipTest) diff --git a/tests/PathOpsThreadedCommon.cpp b/tests/PathOpsThreadedCommon.cpp index 9b5240c..0abf816 100644 --- a/tests/PathOpsThreadedCommon.cpp +++ b/tests/PathOpsThreadedCommon.cpp @@ -7,6 +7,7 @@ #include "PathOpsExtendedTest.h" #include "PathOpsThreadedCommon.h" +#include "SkThreadPool.h" PathOpsThreadedTestRunner::~PathOpsThreadedTestRunner() { for (int index = 0; index < fRunnables.count(); index++) { diff --git a/tests/PathOpsThreadedCommon.h b/tests/PathOpsThreadedCommon.h index 7b9f482..833f24f 100644 --- a/tests/PathOpsThreadedCommon.h +++ b/tests/PathOpsThreadedCommon.h @@ -7,10 +7,8 @@ #ifndef PathOpsThreadedCommon_DEFINED #define PathOpsThreadedCommon_DEFINED -#include "SkCountdown.h" #include "SkRunnable.h" #include "SkTDArray.h" -#include "SkThreadPool.h" #define PATH_STR_SIZE 512 -- 2.7.4