diff options
32 files changed, 1200 insertions, 447 deletions
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp index 922c1030d1..5106bbba98 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -426,6 +426,35 @@ int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) { && pt[0].approximatelyEqual(pt[1])) { removeOne(used() - 2); } + // vet the pairs of t values to see if the mid value is also on the curve. If so, mark + // the span as coincident + if (fUsed >= 2 && !coincidentUsed()) { + int last = fUsed - 1; + int match = 0; + for (int index = 0; index < last; ++index) { + double mid1 = (fT[0][index] + fT[0][index + 1]) / 2; + double mid2 = (fT[1][index] + fT[1][index + 1]) / 2; + pt[0] = c1.xyAtT(mid1); + pt[1] = c2.xyAtT(mid2); + if (pt[0].approximatelyEqual(pt[1])) { + match |= 1 << index; + } + } + if (match) { + if (((match + 1) & match) != 0) { + SkDebugf("%s coincident hole\n", __FUNCTION__); + } + // for now, assume that everything from start to finish is coincident + if (fUsed > 2) { + fPt[1] = fPt[last]; + fT[0][1] = fT[0][last]; + fT[1][1] = fT[1][last]; + fIsCoincident[0] = 0x03; + fIsCoincident[1] = 0x03; + fUsed = 2; + } + } + } return fUsed; } diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index b1e1783e57..13c0dbbef4 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -34,6 +34,47 @@ int SkIntersections::computePoints(const SkDLine& line, int used) { return fUsed; } +int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { + double axLen = a[1].fX - a[0].fX; + double ayLen = a[1].fY - a[0].fY; + double bxLen = b[1].fX - b[0].fX; + double byLen = b[1].fY - b[0].fY; + /* Slopes match when denom goes to zero: + axLen / ayLen == bxLen / byLen + (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen + byLen * axLen == ayLen * bxLen + byLen * axLen - ayLen * bxLen == 0 ( == denom ) + */ + double denom = byLen * axLen - ayLen * bxLen; + double ab0y = a[0].fY - b[0].fY; + double ab0x = a[0].fX - b[0].fX; + double numerA = ab0y * bxLen - byLen * ab0x; + double numerB = ab0y * axLen - ayLen * ab0x; + numerA /= denom; + numerB /= denom; + int used; + if (!approximately_zero(denom)) { + fT[0][0] = numerA; + fT[1][0] = numerB; + used = 1; + } else { + /* See if the axis intercepts match: + ay - ax * ayLen / axLen == by - bx * ayLen / axLen + axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen) + axLen * ay - ax * ayLen == axLen * by - bx * ayLen + */ + if (!AlmostEqualUlps(axLen * a[0].fY - ayLen * a[0].fX, + axLen * b[0].fY - ayLen * b[0].fX)) { + return fUsed = 0; + } + // there's no great answer for intersection points for coincident rays, but return something + fT[0][0] = fT[1][0] = 0; + fT[1][0] = fT[1][1] = 1; + used = 2; + } + return computePoints(a, used); +} + /* Determine the intersection point of two line segments Return FALSE if the lines don't intersect diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp index 5df08ac069..b6a1761781 100644 --- a/src/pathops/SkDQuadIntersection.cpp +++ b/src/pathops/SkDQuadIntersection.cpp @@ -19,12 +19,14 @@ * 0 = A(at^2+bt+c)(at^2+bt+c)+B(at^2+bt+c)(dt^2+et+f)+C(dt^2+et+f)(dt^2+et+f)+D(at^2+bt+c)+E(dt^2+et+f)+F */ -static int findRoots(const SkDQuadImplicit& i, const SkDQuad& q2, double roots[4], - bool oneHint, int firstCubicRoot) { +static int findRoots(const SkDQuadImplicit& i, const SkDQuad& quad, double roots[4], + bool oneHint, bool flip, int firstCubicRoot) { + SkDQuad flipped; + const SkDQuad& q = flip ? (flipped = quad.flip()) : quad; double a, b, c; - SkDQuad::SetABC(&q2[0].fX, &a, &b, &c); + SkDQuad::SetABC(&q[0].fX, &a, &b, &c); double d, e, f; - SkDQuad::SetABC(&q2[0].fY, &d, &e, &f); + SkDQuad::SetABC(&q[0].fY, &d, &e, &f); const double t4 = i.x2() * a * a + i.xy() * a * d + i.y2() * d * d; @@ -48,10 +50,15 @@ static int findRoots(const SkDQuadImplicit& i, const SkDQuad& q2, double roots[4 + i.y() * f + i.c(); int rootCount = SkReducedQuarticRoots(t4, t3, t2, t1, t0, oneHint, roots); - if (rootCount >= 0) { - return rootCount; + if (rootCount < 0) { + rootCount = SkQuarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots); } - return SkQuarticRootsReal(firstCubicRoot, t4, t3, t2, t1, t0, roots); + if (flip) { + for (int index = 0; index < rootCount; ++index) { + roots[index] = 1 - roots[index]; + } + } + return rootCount; } static int addValidRoots(const double roots[4], const int count, double valid[4]) { @@ -403,9 +410,11 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { return fUsed; } int index; - bool useCubic = q1[0] == q2[0] || q1[0] == q2[2] || q1[2] == q2[0]; + bool flip1 = q1[2] == q2[0]; + bool flip2 = q1[0] == q2[2]; + bool useCubic = q1[0] == q2[0]; double roots1[4]; - int rootCount = findRoots(i2, q1, roots1, useCubic, 0); + int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 double roots1Copy[4]; int r1Count = addValidRoots(roots1, rootCount, roots1Copy); @@ -414,7 +423,7 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { pts1[index] = q1.xyAtT(roots1Copy[index]); } double roots2[4]; - int rootCount2 = findRoots(i1, q2, roots2, useCubic, 0); + int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); double roots2Copy[4]; int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); SkDPoint pts2[4]; @@ -427,9 +436,9 @@ int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { insert(roots1Copy[0], roots2Copy[0], pts1[0]); } else if (pts1[0].moreRoughlyEqual(pts2[0])) { // experiment: try to find intersection by chasing t - rootCount = findRoots(i2, q1, roots1, useCubic, 0); + rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); (void) addValidRoots(roots1, rootCount, roots1Copy); - rootCount2 = findRoots(i1, q2, roots2, useCubic, 0); + rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); (void) addValidRoots(roots2, rootCount2, roots2Copy); if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) { insert(roots1Copy[0], roots2Copy[0], pts1[0]); diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index 72f801bb1b..ace8474d1d 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -23,7 +23,7 @@ int (SkIntersections::*CurveRay[])(const SkPoint[], const SkDLine&) = { int SkIntersections::coincidentUsed() const { if (!fIsCoincident[0]) { - SkASSERT(!fIsCoincident[0]); + SkASSERT(!fIsCoincident[1]); return 0; } int count = 0; diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index 83ff6b1549..23470d7884 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -207,9 +207,10 @@ public: int intersect(const SkDCubic&, const SkDLine&); int intersect(const SkDCubic&, const SkDQuad&); int intersect(const SkDCubic&, const SkDCubic&); - int intersectRay(const SkDCubic& , const SkDLine&); - int intersectRay(const SkDQuad& , const SkDLine&); - static SkDPoint Line(const SkDLine& , const SkDLine&); + int intersectRay(const SkDLine&, const SkDLine&); + int intersectRay(const SkDQuad&, const SkDLine&); + int intersectRay(const SkDCubic&, const SkDLine&); + static SkDPoint Line(const SkDLine&, const SkDLine&); void offset(int base, double start, double end); void quickRemoveOne(int index, int replace); static bool Test(const SkDLine& , const SkDLine&); diff --git a/src/pathops/SkLineParameters.h b/src/pathops/SkLineParameters.h index 5139c6c6cf..8824e54bb1 100644 --- a/src/pathops/SkLineParameters.h +++ b/src/pathops/SkLineParameters.h @@ -24,28 +24,37 @@ class SkLineParameters { public: void cubicEndPoints(const SkDCubic& pts) { - cubicEndPoints(pts, 0, 3); + cubicEndPoints(pts, 0, 1); + if (dx() == 0 && dy() == 0) { + cubicEndPoints(pts, 0, 2); + if (dx() == 0 && dy() == 0) { + cubicEndPoints(pts, 0, 3); + } + } } void cubicEndPoints(const SkDCubic& pts, int s, int e) { - a = approximately_pin(pts[s].fY - pts[e].fY); - b = approximately_pin(pts[e].fX - pts[s].fX); + a = pts[s].fY - pts[e].fY; + b = pts[e].fX - pts[s].fX; c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; } void lineEndPoints(const SkDLine& pts) { - a = approximately_pin(pts[0].fY - pts[1].fY); - b = approximately_pin(pts[1].fX - pts[0].fX); + a = pts[0].fY - pts[1].fY; + b = pts[1].fX - pts[0].fX; c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY; } void quadEndPoints(const SkDQuad& pts) { - quadEndPoints(pts, 0, 2); + quadEndPoints(pts, 0, 1); + if (dx() == 0 && dy() == 0) { + quadEndPoints(pts, 0, 2); + } } void quadEndPoints(const SkDQuad& pts, int s, int e) { - a = approximately_pin(pts[s].fY - pts[e].fY); - b = approximately_pin(pts[e].fX - pts[s].fX); + a = pts[s].fY - pts[e].fY; + b = pts[e].fX - pts[s].fX; c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; } diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp index dee2906b7f..c295bfb9d8 100644 --- a/src/pathops/SkOpAngle.cpp +++ b/src/pathops/SkOpAngle.cpp @@ -6,95 +6,169 @@ */ #include "SkIntersections.h" #include "SkOpAngle.h" +#include "SkOpSegment.h" #include "SkPathOpsCurve.h" #include "SkTSort.h" -#if DEBUG_SORT || DEBUG_SORT_SINGLE -#include "SkOpSegment.h" +#if DEBUG_ANGLE +#include "SkString.h" + +static const char funcName[] = "SkOpSegment::operator<"; +static const int bugChar = strlen(funcName) + 1; +#endif + +/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest + positive y. The largest angle has a positive x and a zero y. */ + +#if DEBUG_ANGLE + static bool CompareResult(SkString* bugOut, const char* append, bool compare) { + bugOut->appendf(append); + bugOut->writable_str()[bugChar] = "><"[compare]; + SkDebugf("%s\n", bugOut->c_str()); + return compare; + } + + #define COMPARE_RESULT(append, compare) CompareResult(&bugOut, append, compare) +#else + #define COMPARE_RESULT(append, compare) compare #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 -// derivatives alone. In particular, if one quadratic's coincident tangent -// is longer than the other curve, the final control point can place the -// longer curve on either side of the shorter one. -// Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf -// may provide some help, but nothing has been figured out yet. +bool SkOpAngle::calcSlop(double x, double y, double rx, double ry, bool* result) const{ + double absX = fabs(x); + double absY = fabs(y); + double length = absX < absY ? absX / 2 + absY : absX + absY / 2; + int exponent; + (void) frexp(length, &exponent); + double epsilon = ldexp(FLT_EPSILON, exponent); + SkPath::Verb verb = fSegment->verb(); + SkASSERT(verb == SkPath::kQuad_Verb || verb == SkPath::kCubic_Verb); + // FIXME: the quad and cubic factors are made up ; determine actual values + double slop = verb == SkPath::kQuad_Verb ? 4 * epsilon : 512 * epsilon; + double xSlop = slop; + double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ? + double x1 = x - xSlop; + double y1 = y + ySlop; + double x_ry1 = x1 * ry; + double rx_y1 = rx * y1; + *result = x_ry1 < rx_y1; + double x2 = x + xSlop; + double y2 = y - ySlop; + double x_ry2 = x2 * ry; + double rx_y2 = rx * y2; + bool less2 = x_ry2 < rx_y2; + return *result == less2; +} -/*( +/* for quads and cubics, set up a parameterized line (e.g. LineParameters ) for points [0] to [1]. See if point [2] is on that line, or on one side or the other. If it both quads' end points are on the same side, choose the shorter tangent. If the tangents are equal, choose the better second tangent angle -maybe I could set up LineParameters lazily +FIXME: maybe I could set up LineParameters lazily */ -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; - } - if (y == 0 && ry == 0 && x * rx < 0) { - return x < rx; - } - double x_ry = x * ry; - double rx_y = rx * y; - double cmp = x_ry - rx_y; - if (!approximately_zero(cmp)) { - return cmp < 0; - } - if (approximately_zero(x_ry) && approximately_zero(rx_y) - && !approximately_zero_squared(cmp)) { - return cmp < 0; - } - return -1; -} - -bool SkOpAngle::operator<(const SkOpAngle& rh) const { - double x = dx(); +bool SkOpAngle::operator<(const SkOpAngle& rh) const { // this/lh: left-hand; rh: right-hand double y = dy(); - double rx = rh.dx(); double ry = rh.dy(); - int simple = simple_compare(x, y, rx, ry); - if (simple >= 0) { - return simple; +#if DEBUG_ANGLE + SkString bugOut; + bugOut.printf("%s _ id=%d segId=%d tStart=%1.9g tEnd=%1.9g" + " | id=%d segId=%d tStart=%1.9g tEnd=%1.9g ", funcName, + fID, fSegment->debugID(), fSegment->t(fStart), fSegment->t(fEnd), + rh.fID, rh.fSegment->debugID(), rh.fSegment->t(rh.fStart), rh.fSegment->t(rh.fEnd)); +#endif + double y_ry = y * ry; + if (y_ry < 0) { // if y's are opposite signs, we can do a quick return + return COMPARE_RESULT("1 y * ry < 0", y < 0); } - // 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) - || !approximately_zero(rh.fSide))) { - // FIXME: running demo will trigger this assertion - // (don't know if commenting out will trigger further assertion or not) - // commenting it out allows demo to run in release, though - return fSide < rh.fSide; + // at this point, both y's must be the same sign, or one (or both) is zero + double x = dx(); + double rx = rh.dx(); + if (x * rx < 0) { // if x's are opposite signs, use y to determine first or second half + if (y < 0 && ry < 0) { // if y's are negative, lh x is smaller if positive + return COMPARE_RESULT("2 x_rx < 0 && y < 0 ...", x > 0); + } + if (y >= 0 && ry >= 0) { // if y's are zero or positive, lh x is smaller if negative + return COMPARE_RESULT("3 x_rx < 0 && y >= 0 ...", x < 0); + } + SkASSERT((y == 0) ^ (ry == 0)); // if one y is zero and one is negative, neg y is smaller + return COMPARE_RESULT("4 x_rx < 0 && y == 0 ...", y < 0); } - // see if either curve can be lengthened and try the tangent compare again - if (/* cmp && */ (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical - && (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting + // at this point, both x's must be the same sign, or one (or both) is zero + if (y_ry == 0) { // if either y is zero + if (y + ry < 0) { // if the other y is less than zero, it must be smaller + return COMPARE_RESULT("5 y_ry == 0 && y + ry < 0", y < 0); + } + if (y + ry > 0) { // if a y is greater than zero and an x is positive, non zero is smaller + return COMPARE_RESULT("6 y_ry == 0 && y + ry > 0", (x + rx > 0) ^ (y == 0)); + } + // at this point, both y's are zero, so lines are coincident or one is degenerate + SkASSERT(x * rx != 0); // and a degenerate line should haven't gotten this far + } + // see if either curve can be lengthened before trying the tangent + if (fSegment->other(fEnd) != rh.fSegment // tangents not absolutely identical + && rh.fSegment->other(rh.fEnd) != fSegment) { // and not intersecting SkOpAngle longer = *this; SkOpAngle rhLonger = rh; - if (longer.lengthen() | rhLonger.lengthen()) { - return longer < rhLonger; + if ((longer.lengthen(rh) | rhLonger.lengthen(*this)) // lengthen both + && (fUnorderable || !longer.fUnorderable) + && (rh.fUnorderable || !rhLonger.fUnorderable)) { +#if DEBUG_ANGLE + bugOut.prepend(" "); +#endif + return COMPARE_RESULT("10 longer.lengthen(rh) ...", longer < rhLonger); + } + } + if (y_ry != 0) { // if they aren't coincident, look for a stable cross product + // at this point, y's are the same sign, neither is zero + // and x's are the same sign, or one (or both) is zero + double x_ry = x * ry; + double rx_y = rx * y; + if (!fComputed && !rh.fComputed) { + if (!AlmostEqualUlps(x_ry, rx_y)) { + return COMPARE_RESULT("7 !fComputed && !rh.fComputed", x_ry < rx_y); + } + } else { + // if the vector was a result of subdividing a curve, see if it is stable + bool sloppy1 = x_ry < rx_y; + bool sloppy2 = !sloppy1; + if ((!fComputed || calcSlop(x, y, rx, ry, &sloppy1)) + && (!rh.fComputed || rh.calcSlop(rx, ry, x, y, &sloppy2)) + && sloppy1 != sloppy2) { + return COMPARE_RESULT("8 CalcSlop(x, y ...", sloppy1); + } } } - if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y)) - || (rh.fVerb == SkPath::kLine_Verb - && approximately_zero(rx) && approximately_zero(ry))) { + if (fSide * rh.fSide == 0) { + SkASSERT(fSide + rh.fSide != 0); + return COMPARE_RESULT("9 fSide * rh.fSide == 0 ...", fSide < rh.fSide); + } + // at this point, the initial tangent line is nearly coincident + // see if edges curl away from each other + if (fSide * rh.fSide < 0 && (!approximately_zero(fSide) || !approximately_zero(rh.fSide))) { + return COMPARE_RESULT("9b fSide * rh.fSide < 0 ...", fSide < rh.fSide); + } + if (fUnsortable || rh.fUnsortable) { + // even with no solution, return a stable sort + return COMPARE_RESULT("11 fUnsortable || rh.fUnsortable", this < &rh); + } + SkPath::Verb verb = fSegment->verb(); + SkPath::Verb rVerb = rh.fSegment->verb(); + if ((verb == SkPath::kLine_Verb && approximately_zero(y) && approximately_zero(x)) + || (rVerb == SkPath::kLine_Verb + && approximately_zero(ry) && approximately_zero(rx))) { // See general unsortable comment below. This case can happen when // one line has a non-zero change in t but no change in x and y. fUnsortable = true; - rh.fUnsortable = true; - return this < &rh; // even with no solution, return a stable sort + return COMPARE_RESULT("12 verb == SkPath::kLine_Verb ...", this < &rh); } - if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny - || (*fSpans)[SkMin32(fStart, fEnd)].fTiny) { + if (fSegment->isTiny(this) || rh.fSegment->isTiny(&rh)) { fUnsortable = true; - rh.fUnsortable = true; - return this < &rh; // even with no solution, return a stable sort + return COMPARE_RESULT("13 verb == fSegment->isTiny(this) ...", this < &rh); } - SkASSERT(fVerb >= SkPath::kQuad_Verb); - SkASSERT(rh.fVerb >= SkPath::kQuad_Verb); + SkASSERT(verb >= SkPath::kQuad_Verb); + SkASSERT(rVerb >= SkPath::kQuad_Verb); // FIXME: until I can think of something better, project a ray from the // end of the shorter tangent to midway between the end points // through both curves and use the resulting angle to sort @@ -110,22 +184,20 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { do { useThis = (len < rlen) ^ flip; const SkDCubic& part = useThis ? fCurvePart : rh.fCurvePart; - SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb; + SkPath::Verb partVerb = useThis ? verb : rVerb; ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ? part[2] : part[1]; - ray[1].fX = (part[0].fX + part[SkPathOpsVerbToPoints(partVerb)].fX) / 2; - ray[1].fY = (part[0].fY + part[SkPathOpsVerbToPoints(partVerb)].fY) / 2; + ray[1] = SkDPoint::Mid(part[0], part[SkPathOpsVerbToPoints(partVerb)]); SkASSERT(ray[0] != ray[1]); - roots = (i.*CurveRay[SkPathOpsVerbToPoints(fVerb)])(fPts, ray); - rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rh.fVerb)])(rh.fPts, ray); + roots = (i.*CurveRay[SkPathOpsVerbToPoints(verb)])(fSegment->pts(), ray); + rroots = (ri.*CurveRay[SkPathOpsVerbToPoints(rVerb)])(rh.fSegment->pts(), ray); } while ((roots == 0 || rroots == 0) && (flip ^= true)); if (roots == 0 || rroots == 0) { // FIXME: we don't have a solution in this case. The interim solution // is to mark the edges as unsortable, exclude them from this and // future computations, and allow the returned path to be fragmented fUnsortable = true; - rh.fUnsortable = true; - return this < &rh; // even with no solution, return a stable sort + return COMPARE_RESULT("roots == 0 || rroots == 0", this < &rh); } SkASSERT(fSide != 0 && rh.fSide != 0); SkASSERT(fSide * rh.fSide > 0); // both are the same sign @@ -164,105 +236,96 @@ bool SkOpAngle::operator<(const SkOpAngle& rh) const { break; } } - #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) { + 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; + return COMPARE_RESULT("14 leftLessThanRight", leftLessThanRight); } -bool SkOpAngle::lengthen() { - int newEnd = fEnd; - if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) { - fEnd = newEnd; - setSpans(); - return true; - } - return false; +bool SkOpAngle::isHorizontal() const { + return dy() == 0 && fSegment->verb() == SkPath::kLine_Verb; } -bool SkOpAngle::reverseLengthen() { - if (fReversed) { +// lengthen cannot cross opposite angle +bool SkOpAngle::lengthen(const SkOpAngle& opp) { + if (fSegment->other(fEnd) == opp.fSegment) { return false; } - int newEnd = fStart; - if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) { + // FIXME: make this a while loop instead and make it as large as possible? + int newEnd = fEnd; + if (fStart < fEnd ? ++newEnd < fSegment->count() : --newEnd >= 0) { fEnd = newEnd; - fReversed = true; setSpans(); return true; } return false; } -void SkOpAngle::set(const SkPoint* orig, SkPath::Verb verb, const SkOpSegment* segment, - int start, int end, const SkTDArray<SkOpSpan>& spans) { +void SkOpAngle::set(const SkOpSegment* segment, int start, int end) { fSegment = segment; fStart = start; fEnd = end; - fPts = orig; - fVerb = verb; - fSpans = &spans; - fReversed = false; - fUnsortable = false; setSpans(); } - void SkOpAngle::setSpans() { - double startT = (*fSpans)[fStart].fT; - double endT = (*fSpans)[fEnd].fT; - switch (fVerb) { + fUnorderable = false; + if (fSegment->verb() == SkPath::kLine_Verb) { + fUnsortable = false; + } else { + // if start-1 exists and is tiny, then start pt may have moved + int smaller = SkMin32(fStart, fEnd); + int tinyCheck = smaller; + while (tinyCheck > 0 && fSegment->isTiny(tinyCheck - 1)) { + --tinyCheck; + } + if ((fUnsortable = smaller > 0 && tinyCheck == 0)) { + return; + } + int larger = SkMax32(fStart, fEnd); + tinyCheck = larger; + int max = fSegment->count() - 1; + while (tinyCheck < max && fSegment->isTiny(tinyCheck + 1)) { + ++tinyCheck; + } + if ((fUnsortable = larger < max && tinyCheck == max)) { + return; + } + } + fComputed = fSegment->subDivide(fStart, fEnd, &fCurvePart); + // FIXME: slight errors in subdivision cause sort trouble later on. As an experiment, try + // rounding the curve part to float precision here + // fCurvePart.round(fSegment->verb()); + switch (fSegment->verb()) { case SkPath::kLine_Verb: { - SkDLine l = SkDLine::SubDivide(fPts, startT, endT); // OPTIMIZATION: for pure line compares, we never need fTangent1.c - fTangent1.lineEndPoints(l); + fTangent1.lineEndPoints(*SkTCast<SkDLine*>(&fCurvePart)); fSide = 0; } break; case SkPath::kQuad_Verb: { SkDQuad& quad = *SkTCast<SkDQuad*>(&fCurvePart); - quad = SkDQuad::SubDivide(fPts, startT, endT); - fTangent1.quadEndPoints(quad, 0, 1); - if (dx() == 0 && dy() == 0) { - fTangent1.quadEndPoints(quad); - } + fTangent1.quadEndPoints(quad); fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only - } break; - case SkPath::kCubic_Verb: { - // int nextC = 2; - fCurvePart = SkDCubic::SubDivide(fPts, startT, endT); - fTangent1.cubicEndPoints(fCurvePart, 0, 1); - if (dx() == 0 && dy() == 0) { - fTangent1.cubicEndPoints(fCurvePart, 0, 2); - // nextC = 3; - if (dx() == 0 && dy() == 0) { - fTangent1.cubicEndPoints(fCurvePart, 0, 3); + if (fComputed && dx() > 0 && approximately_zero(dy())) { + SkDCubic origCurve; // can't use segment's curve in place since it may be flipped + int last = fSegment->count() - 1; + fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); + SkLineParameters origTan; + origTan.quadEndPoints(*SkTCast<SkDQuad*>(&origCurve)); + if ((fUnorderable = origTan.dx() <= 0 + || (dy() != origTan.dy() && dy() * origTan.dy() <= 0))) { // signs match? + return; } } - // fSide = -fTangent1.pointDistance(fCurvePart[nextC]); // compare sign only - // if (nextC == 2 && approximately_zero(fSide)) { - // fSide = -fTangent1.pointDistance(fCurvePart[3]); - // } + } break; + case SkPath::kCubic_Verb: { + fTangent1.cubicEndPoints(fCurvePart); double testTs[4]; // OPTIMIZATION: keep inflections precomputed with cubic segment? - int testCount = SkDCubic::FindInflections(fPts, testTs); + const SkPoint* pts = fSegment->pts(); + int testCount = SkDCubic::FindInflections(pts, testTs); + double startT = fSegment->t(fStart); + double endT = fSegment->t(fEnd); double limitT = endT; int index; for (index = 0; index < testCount; ++index) { @@ -287,35 +350,62 @@ void SkOpAngle::setSpans() { testT = (testT + testTs[testIndex + 1]) / 2; } // OPTIMIZE: could avoid call for t == startT, endT - SkDPoint pt = dcubic_xy_at_t(fPts, testT); + SkDPoint pt = dcubic_xy_at_t(pts, testT); double testSide = fTangent1.pointDistance(pt); if (fabs(bestSide) < fabs(testSide)) { bestSide = testSide; } } fSide = -bestSide; // compare sign only + if (fComputed && dx() > 0 && approximately_zero(dy())) { + SkDCubic origCurve; // can't use segment's curve in place since it may be flipped + int last = fSegment->count() - 1; + fSegment->subDivide(fStart < fEnd ? 0 : last, fStart < fEnd ? last : 0, &origCurve); + SkLineParameters origTan; + origTan.cubicEndPoints(origCurve); + if ((fUnorderable = origTan.dx() <= 0)) { + fUnsortable = fSegment->isTiny(this); + return; + } + // if one is < 0 and the other is >= 0 + if ((fUnorderable = (dy() < 0) ^ (origTan.dy() < 0))) { + fUnsortable = fSegment->isTiny(this); + return; + } + SkDCubicPair split = origCurve.chopAt(startT); + SkLineParameters splitTan; + splitTan.cubicEndPoints(fStart < fEnd ? split.second() : split.first()); + if ((fUnorderable = splitTan.dx() <= 0)) { + fUnsortable = fSegment->isTiny(this); + return; + } + // if one is < 0 and the other is >= 0 + if ((fUnorderable = (dy() < 0) ^ (splitTan.dy() < 0))) { + fUnsortable = fSegment->isTiny(this); + return; + } + } } break; default: SkASSERT(0); } - fUnsortable = dx() == 0 && dy() == 0; - if (fUnsortable) { + if ((fUnsortable = approximately_zero(dx()) && approximately_zero(dy()))) { return; } SkASSERT(fStart != fEnd); int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro? for (int index = fStart; index != fEnd; index += step) { #if 1 - const SkOpSpan& thisSpan = (*fSpans)[index]; - const SkOpSpan& nextSpan = (*fSpans)[index + step]; + const SkOpSpan& thisSpan = fSegment->span(index); + const SkOpSpan& nextSpan = fSegment->span(index + step); if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) { continue; } fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd; #if DEBUG_UNSORTABLE if (fUnsortable) { - SkPoint iPt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, thisSpan.fT); - SkPoint ePt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, nextSpan.fT); + SkPoint iPt = fSegment->xyAtT(index); + SkPoint ePt = fSegment->xyAtT(index + step); SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); } @@ -330,8 +420,8 @@ void SkOpAngle::setSpans() { } #if 1 #if DEBUG_UNSORTABLE - SkPoint iPt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, startT); - SkPoint ePt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, endT); + SkPoint iPt = fSegment->xyAtT(fStart); + SkPoint ePt = fSegment->xyAtT(fEnd); SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__, fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY); #endif diff --git a/src/pathops/SkOpAngle.h b/src/pathops/SkOpAngle.h index 00520ecf43..cca1a224dd 100644 --- a/src/pathops/SkOpAngle.h +++ b/src/pathops/SkOpAngle.h @@ -8,10 +8,10 @@ #define SkOpAngle_DEFINED #include "SkLineParameters.h" -#include "SkOpSpan.h" #include "SkPath.h" #include "SkPathOpsCubic.h" -#include "SkTDArray.h" + +class SkOpSegment; // sorting angles // given angles of {dx dy ddx ddy dddx dddy} sort them @@ -19,6 +19,8 @@ class SkOpAngle { public: bool operator<(const SkOpAngle& rh) const; + bool calcSlop(double x, double y, double rx, double ry, bool* result) const; + double dx() const { return fTangent1.dx(); } @@ -31,17 +33,9 @@ public: return fEnd; } - bool isHorizontal() const { - return dy() == 0 && fVerb == SkPath::kLine_Verb; - } - - bool lengthen(); - bool reverseLengthen(); - - void set(const SkPoint* orig, SkPath::Verb verb, const SkOpSegment* segment, - int start, int end, const SkTDArray<SkOpSpan>& spans); + bool isHorizontal() const; - void setSpans(); + void set(const SkOpSegment* segment, int start, int end); SkOpSegment* segment() const { return const_cast<SkOpSegment*>(fSegment); @@ -51,44 +45,47 @@ public: return SkSign32(fStart - fEnd); } - const SkTDArray<SkOpSpan>* spans() const { - return fSpans; - } - int start() const { return fStart; } + bool unorderable() const { + return fUnorderable; + } + bool unsortable() const { return fUnsortable; } #if DEBUG_ANGLE - const SkPoint* pts() const { - return fPts; - } - - SkPath::Verb verb() const { - return fVerb; - } - void debugShow(const SkPoint& a) const { SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide); } + + void setID(int id) { + fID = id; + } #endif private: - const SkPoint* fPts; + bool lengthen(const SkOpAngle& ); + void setSpans(); + SkDCubic fCurvePart; - SkPath::Verb fVerb; double fSide; SkLineParameters fTangent1; - const SkTDArray<SkOpSpan>* fSpans; const SkOpSegment* fSegment; int fStart; int fEnd; - bool fReversed; + bool fComputed; // tangent is computed, may contain some error + // if subdividing a quad or cubic causes the tangent to go from the maximum angle to the + // minimum, mark it unorderable. It still can be sorted, which is good enough for find-top + // but can't be ordered, and therefore can't be used to compute winding + bool fUnorderable; mutable bool fUnsortable; // this alone is editable by the less than operator +#if DEBUG_ANGLE + int fID; +#endif }; #endif diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 817732e0e5..a9e20fd11a 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -209,19 +209,22 @@ void SkOpSegment::addAngle(SkTDArray<SkOpAngle>* anglesPtr, int start, int end) SkOpAngle* angle = anglesPtr->append(); #if DEBUG_ANGLE SkTDArray<SkOpAngle>& angles = *anglesPtr; - if (angles.count() > 1 && !fTs[start].fTiny) { - SkPoint angle0Pt = (*CurvePointAtT[SkPathOpsVerbToPoints(angles[0].verb())])(angles[0].pts(), - (*angles[0].spans())[angles[0].start()].fT); - SkPoint newPt = (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[start].fT); - bool match = AlmostEqualUlps(angle0Pt.fX, newPt.fX); - match &= AlmostEqualUlps(angle0Pt.fY, newPt.fY); - if (!match) { - SkDebugf("%s no match\n", __FUNCTION__); - SkASSERT(0); + if (angles.count() > 1) { + const SkOpSegment* aSeg = angles[0].segment(); + int aStart = angles[0].start(); + if (!aSeg->fTs[aStart].fTiny) { + const SkPoint& angle0Pt = aSeg->xyAtT(aStart); + SkDPoint newPt = (*CurveDPointAtT[SkPathOpsVerbToPoints(aSeg->fVerb)])(aSeg->fPts, + aSeg->fTs[aStart].fT); +#if ONE_OFF_DEBUG + SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g)\n", __FUNCTION__, + aSeg->fTs[aStart].fT, newPt.fX, newPt.fY, angle0Pt.fX, angle0Pt.fY); +#endif + SkASSERT(newPt.approximatelyEqual(angle0Pt)); } } #endif - angle->set(fPts, fVerb, this, start, end, fTs); + angle->set(this, start, end); } void SkOpSegment::addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd) { @@ -853,7 +856,8 @@ int SkOpSegment::computeSum(int startIndex, int endIndex, bool binary) { // OPTIMIZATION: check all angles to see if any have computed wind sum // before sorting (early exit if none) SkTDArray<SkOpAngle*> sorted; - bool sortable = SortAngles(angles, &sorted); + // FIXME?: Not sure if this sort must be ordered or if the relaxed ordering is OK ... + bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); #if DEBUG_SORT sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0); #endif @@ -979,7 +983,8 @@ int SkOpSegment::crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hi SkIntersections intersections; // OPTIMIZE: use specialty function that intersects ray with curve, // returning t values only for curve (we don't care about t on ray) - int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, top, bottom, basePt.fX, false); + int pts = (intersections.*CurveVertical[SkPathOpsVerbToPoints(fVerb)]) + (fPts, top, bottom, basePt.fX, false); if (pts == 0 || (current && pts == 1)) { return bestTIndex; } @@ -1126,6 +1131,9 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart } while (precisely_zero(startT - other->fTs[*nextEnd].fT)); SkASSERT(step < 0 ? *nextEnd >= 0 : *nextEnd < other->fTs.count()); + if (other->isTiny(SkMin32(*nextStart, *nextEnd))) { + return NULL; + } return other; } // more than one viable candidate -- measure angles to find best @@ -1135,7 +1143,7 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart addTwoAngles(startIndex, end, &angles); buildAngles(end, &angles, true); SkTDArray<SkOpAngle*> sorted; - bool sortable = SortAngles(angles, &sorted); + bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); int angleCount = angles.count(); int firstIndex = findStartingEdge(sorted, startIndex, end); SkASSERT(firstIndex >= 0); @@ -1177,12 +1185,12 @@ SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart if (activeAngle) { ++activeCount; if (!foundAngle || (foundDone && activeCount & 1)) { - if (nextSegment->tiny(nextAngle)) { + if (nextSegment->isTiny(nextAngle)) { *unsortable = true; return NULL; } foundAngle = nextAngle; - foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle); + foundDone = nextSegment->done(nextAngle) && !nextSegment->isTiny(nextAngle); } } if (nextSegment->done()) { @@ -1257,7 +1265,7 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next addTwoAngles(startIndex, end, &angles); buildAngles(end, &angles, true); SkTDArray<SkOpAngle*> sorted; - bool sortable = SortAngles(angles, &sorted); + bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); int angleCount = angles.count(); int firstIndex = findStartingEdge(sorted, startIndex, end); SkASSERT(firstIndex >= 0); @@ -1294,7 +1302,7 @@ SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpan*>* chase, int* next if (activeAngle) { ++activeCount; if (!foundAngle || (foundDone && activeCount & 1)) { - if (nextSegment->tiny(nextAngle)) { + if (nextSegment->isTiny(nextAngle)) { *unsortable = true; return NULL; } @@ -1386,7 +1394,7 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort addTwoAngles(startIndex, end, &angles); buildAngles(end, &angles, false); SkTDArray<SkOpAngle*> sorted; - bool sortable = SortAngles(angles, &sorted); + bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMustBeOrdered_SortAngleKind); if (!sortable) { *unsortable = true; #if DEBUG_SORT @@ -1416,7 +1424,7 @@ SkOpSegment* SkOpSegment::findNextXor(int* nextStart, int* nextEnd, bool* unsort nextSegment = nextAngle->segment(); ++activeCount; if (!foundAngle || (foundDone && activeCount & 1)) { - if (nextSegment->tiny(nextAngle)) { + if (nextSegment->isTiny(nextAngle)) { *unsortable = true; return NULL; } @@ -1628,7 +1636,7 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort addTwoAngles(end, firstT, &angles); buildAngles(firstT, &angles, true); SkTDArray<SkOpAngle*> sorted; - bool sortable = SortAngles(angles, &sorted); + bool sortable = SortAngles(angles, &sorted, SkOpSegment::kMayBeUnordered_SortAngleKind); int first = SK_MaxS32; SkScalar top = SK_ScalarMax; int count = sorted.count(); @@ -2081,7 +2089,8 @@ bool SkOpSegment::clockwise(int tStart, int tEnd) const { SkASSERT(fVerb != SkPath::kLine_Verb); SkPoint edge[4]; subDivide(tStart, tEnd, edge); - double sum = (edge[0].fX - edge[SkPathOpsVerbToPoints(fVerb)].fX) * (edge[0].fY + edge[SkPathOpsVerbToPoints(fVerb)].fY); + int points = SkPathOpsVerbToPoints(fVerb); + double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY); if (fVerb == SkPath::kCubic_Verb) { SkScalar lesser = SkTMin<SkScalar>(edge[0].fY, edge[3].fY); if (edge[1].fY < lesser && edge[2].fY < lesser) { @@ -2095,7 +2104,7 @@ bool SkOpSegment::clockwise(int tStart, int tEnd) const { } } } - for (int idx = 0; idx < SkPathOpsVerbToPoints(fVerb); ++idx){ + for (int idx = 0; idx < points; ++idx){ sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY); } return sum <= 0; @@ -2334,8 +2343,8 @@ void SkOpSegment::setUpWindings(int index, int endIndex, int* sumMiWinding, int* // exclusion in find top and others. This could be optimized to only mark // adjacent spans that unsortable. However, this makes it difficult to later // determine starting points for edge detection in find top and the like. -bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles, - SkTDArray<SkOpAngle*>* angleList) { +bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList, + SortAngleKind orderKind) { bool sortable = true; int angleCount = angles.count(); int angleIndex; @@ -2343,12 +2352,17 @@ bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles, for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { const SkOpAngle& angle = angles[angleIndex]; *angleList->append() = const_cast<SkOpAngle*>(&angle); - sortable &= !angle.unsortable(); +#if DEBUG_ANGLE + (*(angleList->end() - 1))->setID(angleIndex); +#endif + sortable &= !(angle.unsortable() || (orderKind == kMustBeOrdered_SortAngleKind + && angle.unorderable())); } if (sortable) { SkTQSort<SkOpAngle>(angleList->begin(), angleList->end() - 1); for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { - if (angles[angleIndex].unsortable()) { + if (angles[angleIndex].unsortable() || (orderKind == kMustBeOrdered_SortAngleKind + && angles[angleIndex].unorderable())) { sortable = false; break; } @@ -2363,20 +2377,80 @@ bool SkOpSegment::SortAngles(const SkTDArray<SkOpAngle>& angles, return sortable; } -void SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const { +// return true if midpoints were computed +bool SkOpSegment::subDivide(int start, int end, SkPoint edge[4]) const { + SkASSERT(start != end); edge[0] = fTs[start].fPt; - edge[SkPathOpsVerbToPoints(fVerb)] = fTs[end].fPt; - if (fVerb == SkPath::kQuad_Verb || fVerb == SkPath::kCubic_Verb) { - SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[SkPathOpsVerbToPoints(fVerb)].fX, edge[SkPathOpsVerbToPoints(fVerb)].fY }}; + int points = SkPathOpsVerbToPoints(fVerb); + edge[points] = fTs[end].fPt; + if (fVerb == SkPath::kLine_Verb) { + return false; + } + double startT = fTs[start].fT; + double endT = fTs[end].fT; + if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { + // don't compute midpoints if we already have them if (fVerb == SkPath::kQuad_Verb) { - edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], fTs[start].fT, - fTs[end].fT).asSkPoint(); - } else { - SkDCubic::SubDivide(fPts, sub[0], sub[1], fTs[start].fT, fTs[end].fT, sub); - edge[1] = sub[0].asSkPoint(); - edge[2] = sub[1].asSkPoint(); + edge[1] = fPts[1]; + return false; } + SkASSERT(fVerb == SkPath::kCubic_Verb); + if (start < end) { + edge[1] = fPts[1]; + edge[2] = fPts[2]; + return false; + } + edge[1] = fPts[2]; + edge[2] = fPts[1]; + return false; + } + const SkDPoint sub[2] = {{ edge[0].fX, edge[0].fY}, {edge[points].fX, edge[points].fY }}; + if (fVerb == SkPath::kQuad_Verb) { + edge[1] = SkDQuad::SubDivide(fPts, sub[0], sub[1], startT, endT).asSkPoint(); + } else { + SkASSERT(fVerb == SkPath::kCubic_Verb); + SkDPoint ctrl[2]; + SkDCubic::SubDivide(fPts, sub[0], sub[1], startT, endT, ctrl); + edge[1] = ctrl[0].asSkPoint(); + edge[2] = ctrl[1].asSkPoint(); } + return true; +} + +// return true if midpoints were computed +bool SkOpSegment::subDivide(int start, int end, SkDCubic* result) const { + SkASSERT(start != end); + (*result)[0].set(fTs[start].fPt); + int points = SkPathOpsVerbToPoints(fVerb); + (*result)[points].set(fTs[end].fPt); + if (fVerb == SkPath::kLine_Verb) { + return false; + } + double startT = fTs[start].fT; + double endT = fTs[end].fT; + if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { + // don't compute midpoints if we already have them + if (fVerb == SkPath::kQuad_Verb) { + (*result)[1].set(fPts[1]); + return false; + } + SkASSERT(fVerb == SkPath::kCubic_Verb); + if (start < end) { + (*result)[1].set(fPts[1]); + (*result)[2].set(fPts[2]); + return false; + } + (*result)[1].set(fPts[2]); + (*result)[2].set(fPts[1]); + return false; + } + if (fVerb == SkPath::kQuad_Verb) { + (*result)[1] = SkDQuad::SubDivide(fPts, (*result)[0], (*result)[2], startT, endT); + } else { + SkASSERT(fVerb == SkPath::kCubic_Verb); + SkDCubic::SubDivide(fPts, (*result)[0], (*result)[3], startT, endT, &(*result)[1]); + } + return true; } void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const { @@ -2385,13 +2459,17 @@ void SkOpSegment::subDivideBounds(int start, int end, SkPathOpsBounds* bounds) c (bounds->*SetCurveBounds[SkPathOpsVerbToPoints(fVerb)])(edge); } -bool SkOpSegment::tiny(const SkOpAngle* angle) const { +bool SkOpSegment::isTiny(const SkOpAngle* angle) const { int start = angle->start(); int end = angle->end(); const SkOpSpan& mSpan = fTs[SkMin32(start, end)]; return mSpan.fTiny; } +bool SkOpSegment::isTiny(int index) const { + return fTs[index].fTiny; +} + void SkOpSegment::TrackOutside(SkTDArray<double>* outsideTs, double end, double start) { int outCount = outsideTs->count(); if (outCount == 0 || !approximately_negative(end - (*outsideTs)[outCount - 2])) { @@ -2735,8 +2813,8 @@ void SkOpSegment::debugShowSort(const char* fun, const SkTDArray<SkOpAngle*>& an } SkDebugf("%s [%d] %s", __FUNCTION__, index, angle.unsortable() ? "*** UNSORTABLE *** " : ""); - #if COMPACT_DEBUG_SORT - SkDebugf("id=%d %s start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)", + #if DEBUG_SORT_COMPACT + SkDebugf("id=%d %s start=%d (%1.9g,%1.9g) end=%d (%1.9g,%1.9g)", segment.fID, kLVerbStr[SkPathOpsVerbToPoints(segment.fVerb)], start, segment.xAtT(&sSpan), segment.yAtT(&sSpan), end, segment.xAtT(&eSpan), segment.yAtT(&eSpan)); diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index e489acfb02..b26bad14a6 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -8,6 +8,7 @@ #define SkOpSegment_DEFINE #include "SkOpAngle.h" +#include "SkOpSpan.h" #include "SkPathOpsBounds.h" #include "SkPathOpsCurve.h" #include "SkTDArray.h" @@ -40,6 +41,10 @@ public: return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1; } + int count() const { + return fTs.count(); + } + bool done() const { SkASSERT(fDoneSpans <= fTs.count()); return fDoneSpans == fTs.count(); @@ -120,6 +125,10 @@ public: return fTs[lesser].fOppValue; } + const SkOpSegment* other(int index) const { + return fTs[index].fOther; + } + const SkPoint* pts() const { return fPts; } @@ -262,6 +271,8 @@ public: bool isLinear(int start, int end) const; bool isMissing(double startT) const; bool isSimple(int end) const; + bool isTiny(const SkOpAngle* angle) const; + bool isTiny(int index) const; SkOpSpan* markAndChaseDoneBinary(int index, int endIndex); SkOpSpan* markAndChaseDoneUnary(int index, int endIndex); SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding); @@ -279,8 +290,14 @@ public: int nextSpan(int from, int step) const; void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding); - static bool SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList); - void subDivide(int start, int end, SkPoint edge[4]) const; + enum SortAngleKind { + kMustBeOrdered_SortAngleKind, // required for winding calc + kMayBeUnordered_SortAngleKind // ok for find top + }; + static bool SortAngles(const SkTDArray<SkOpAngle>& angles, SkTDArray<SkOpAngle*>* angleList, + SortAngleKind ); + bool subDivide(int start, int end, SkPoint edge[4]) const; + bool subDivide(int start, int end, SkDCubic* result) const; void undoneSpan(int* start, int* end); int updateOppWindingReverse(const SkOpAngle* angle) const; int updateWindingReverse(const SkOpAngle* angle) const; @@ -348,7 +365,6 @@ private: SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last); bool serpentine(int tStart, int tEnd) const; void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const; - bool tiny(const SkOpAngle* angle) const; static void TrackOutside(SkTDArray<double>* outsideTs, double end, double start); int updateOppWinding(int index, int endIndex) const; int updateOppWinding(const SkOpAngle* angle) const; diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index a089d7c7f2..9215cbc84a 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -134,7 +134,8 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) continue; } SkTDArray<SkOpAngle*> sorted; - bool sortable = SkOpSegment::SortAngles(angles, &sorted); + bool sortable = SkOpSegment::SortAngles(angles, &sorted, + SkOpSegment::kMayBeUnordered_SortAngleKind); int angleCount = sorted.count(); #if DEBUG_SORT sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0); diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp index 674213c383..c644a67117 100644 --- a/src/pathops/SkPathOpsCubic.cpp +++ b/src/pathops/SkPathOpsCubic.cpp @@ -403,11 +403,23 @@ SkDCubic SkDCubic::subDivide(double t1, double t2) const { /* by = */ dst[1].fY = (my * 2 - ny) / 18; /* cx = */ dst[2].fX = (nx * 2 - mx) / 18; /* cy = */ dst[2].fY = (ny * 2 - my) / 18; + // FIXME: call align() ? return dst; } +void SkDCubic::align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const { + if (fPts[endIndex].fX == fPts[ctrlIndex].fX) { + dstPt->fX = fPts[endIndex].fX; + } + if (fPts[endIndex].fY == fPts[ctrlIndex].fY) { + dstPt->fY = fPts[endIndex].fY; + } +} + void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d, double t1, double t2, SkDPoint dst[2]) const { + SkASSERT(t1 != t2); +#if 0 double ex = interp_cubic_coords(&fPts[0].fX, (t1 * 2 + t2) / 3); double ey = interp_cubic_coords(&fPts[0].fY, (t1 * 2 + t2) / 3); double fx = interp_cubic_coords(&fPts[0].fX, (t1 + t2 * 2) / 3); @@ -420,6 +432,30 @@ void SkDCubic::subDivide(const SkDPoint& a, const SkDPoint& d, /* by = */ dst[0].fY = (my * 2 - ny) / 18; /* cx = */ dst[1].fX = (nx * 2 - mx) / 18; /* cy = */ dst[1].fY = (ny * 2 - my) / 18; +#else + // this approach assumes that the control points computed directly are accurate enough + SkDCubic sub = subDivide(t1, t2); + dst[0] = sub[1] + (a - sub[0]); + dst[1] = sub[2] + (d - sub[3]); +#endif + if (t1 == 0 || t2 == 0) { + align(0, 1, t1 == 0 ? &dst[0] : &dst[1]); + } + if (t1 == 1 || t2 == 1) { + align(3, 2, t1 == 1 ? &dst[0] : &dst[1]); + } + if (precisely_subdivide_equal(dst[0].fX, a.fX)) { + dst[0].fX = a.fX; + } + if (precisely_subdivide_equal(dst[0].fY, a.fY)) { + dst[0].fY = a.fY; + } + if (precisely_subdivide_equal(dst[1].fX, d.fX)) { + dst[1].fX = d.fX; + } + if (precisely_subdivide_equal(dst[1].fY, d.fY)) { + dst[1].fY = d.fY; + } } /* classic one t subdivision */ diff --git a/src/pathops/SkPathOpsCubic.h b/src/pathops/SkPathOpsCubic.h index 37492ddbba..c884ea9714 100644 --- a/src/pathops/SkPathOpsCubic.h +++ b/src/pathops/SkPathOpsCubic.h @@ -8,6 +8,7 @@ #ifndef SkPathOpsCubic_DEFINED #define SkPathOpsCubic_DEFINED +#include "SkPath.h" #include "SkPathOpsPoint.h" #include "SkTDArray.h" @@ -32,6 +33,7 @@ struct SkDCubic { const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 4); return fPts[n]; } SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 4); return fPts[n]; } + void align(int endIndex, int ctrlIndex, SkDPoint* dstPt) const; double calcPrecision() const; SkDCubicPair chopAt(double t) const; bool clockwise() const; diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 2d0962b1e4..6c8ca954f1 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -68,21 +68,21 @@ static void showPathContours(SkPath::Iter& iter, const char* pathName) { 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); + 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); + 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, + 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", + 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); + SkDebugf(" %s.close();\n", pathName); break; default: SkDEBUGFAIL("bad verb"); @@ -98,12 +98,17 @@ static const char* gFillTypeStr[] = { "kInverseEvenOdd_FillType" }; + +void ShowFunctionHeader() { + SkDebugf("\nstatic void test#(skiatest::Reporter* reporter) {\n"); +} + 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]); + SkDebugf(" SkPath %s;\n", pathName); + SkDebugf(" %s.setFillType(SkPath::%s);\n", pathName, gFillTypeStr[fillType]); iter.setPath(path, true); showPathContours(iter, pathName); } @@ -117,8 +122,7 @@ static const char* gOpStrs[] = { }; 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"); + SkDebugf(" testPathOp(reporter, %s, %s, %s);\n", pathOne, pathTwo, gOpStrs[op]); + SkDebugf("}\n"); } #endif diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index 61b59c3189..cc1b8ead95 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -61,6 +61,7 @@ extern int gDebugMaxWindValue; #define DEBUG_SHOW_TEST_PROGRESS 0 #define DEBUG_SHOW_WINDING 0 #define DEBUG_SORT 0 +#define DEBUG_SORT_COMPACT 0 #define DEBUG_SORT_SINGLE 0 #define DEBUG_SWAP_TOP 0 #define DEBUG_UNSORTABLE 0 @@ -73,7 +74,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_ACTIVE_SPANS_SHORT_FORM 1 #define DEBUG_ADD_INTERSECTING_TS 1 #define DEBUG_ADD_T_PAIR 1 #define DEBUG_ANGLE 1 @@ -90,6 +91,7 @@ extern int gDebugMaxWindValue; #define DEBUG_SHOW_TEST_PROGRESS 1 #define DEBUG_SHOW_WINDING 0 #define DEBUG_SORT 1 +#define DEBUG_SORT_COMPACT 0 #define DEBUG_SORT_SINGLE 0 #define DEBUG_SWAP_TOP 1 #define DEBUG_UNSORTABLE 1 @@ -144,6 +146,7 @@ extern const char* kPathOpStr[]; #endif #if DEBUG_SHOW_PATH +void ShowFunctionHeader(); void ShowPath(const SkPath& path, const char* pathName); void ShowOp(SkPathOp op, const char* pathOne, const char* pathTwo); #endif diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index db55635d89..f030765a61 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -37,7 +37,8 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int& nextStart, int continue; } SkTDArray<SkOpAngle*> sorted; - bool sortable = SkOpSegment::SortAngles(angles, &sorted); + bool sortable = SkOpSegment::SortAngles(angles, &sorted, + SkOpSegment::kMayBeUnordered_SortAngleKind); int angleCount = sorted.count(); #if DEBUG_SORT sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0); @@ -232,6 +233,7 @@ 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 + ShowFunctionHeader(); ShowPath(one, "path"); ShowPath(two, "pathB"); ShowOp(op, "path", "pathB"); diff --git a/src/pathops/SkPathOpsPoint.h b/src/pathops/SkPathOpsPoint.h index 23734c98b5..534154f199 100644 --- a/src/pathops/SkPathOpsPoint.h +++ b/src/pathops/SkPathOpsPoint.h @@ -117,8 +117,8 @@ struct SkDPoint { return true; } double inv = 1 / denom; - return approximately_equal(fX * inv, a.fX * inv) - && approximately_equal(fY * inv, a.fY * inv); + return approximately_equal_double(fX * inv, a.fX * inv) + && approximately_equal_double(fY * inv, a.fY * inv); } bool approximatelyEqualHalf(const SkDPoint& a) const { @@ -151,6 +151,13 @@ struct SkDPoint { return temp.lengthSquared(); } + static SkDPoint Mid(const SkDPoint& a, const SkDPoint& b) { + SkDPoint result; + result.fX = (a.fX + b.fX) / 2; + result.fY = (a.fY + b.fY) / 2; + return result; + } + double moreRoughlyEqual(const SkDPoint& a) const { return more_roughly_equal(a.fY, fY) && more_roughly_equal(a.fX, fX); } diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp index 685f49e160..ce89469062 100644 --- a/src/pathops/SkPathOpsQuad.cpp +++ b/src/pathops/SkPathOpsQuad.cpp @@ -4,6 +4,7 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ +#include "SkIntersections.h" #include "SkLineParameters.h" #include "SkPathOpsCubic.h" #include "SkPathOpsQuad.h" @@ -220,12 +221,53 @@ SkDQuad SkDQuad::subDivide(double t1, double t2) const { return dst; } +void SkDQuad::align(int endIndex, SkDPoint* dstPt) const { + if (fPts[endIndex].fX == fPts[1].fX) { + dstPt->fX = fPts[endIndex].fX; + } + if (fPts[endIndex].fY == fPts[1].fY) { + dstPt->fY = fPts[endIndex].fY; + } +} + SkDPoint SkDQuad::subDivide(const SkDPoint& a, const SkDPoint& c, double t1, double t2) const { + SkASSERT(t1 != t2); SkDPoint b; +#if 0 + // this approach assumes that the control point computed directly is accurate enough double dx = interp_quad_coords(&fPts[0].fX, (t1 + t2) / 2); double dy = interp_quad_coords(&fPts[0].fY, (t1 + t2) / 2); b.fX = 2 * dx - (a.fX + c.fX) / 2; b.fY = 2 * dy - (a.fY + c.fY) / 2; +#else + SkDQuad sub = subDivide(t1, t2); + SkDLine b0 = {{a, sub[1] + (a - sub[0])}}; + SkDLine b1 = {{c, sub[1] + (c - sub[2])}}; + SkIntersections i; + i.intersectRay(b0, b1); + if (i.used() == 1) { + b = i.pt(0); + } else { + SkASSERT(i.used() == 2 || i.used() == 0); + b = SkDPoint::Mid(b0[1], b1[1]); + } +#endif + if (t1 == 0 || t2 == 0) { + align(0, &b); + } + if (t1 == 1 || t2 == 1) { + align(2, &b); + } + if (precisely_subdivide_equal(b.fX, a.fX)) { + b.fX = a.fX; + } else if (precisely_subdivide_equal(b.fX, c.fX)) { + b.fX = c.fX; + } + if (precisely_subdivide_equal(b.fY, a.fY)) { + b.fY = a.fY; + } else if (precisely_subdivide_equal(b.fY, c.fY)) { + b.fY = c.fY; + } return b; } diff --git a/src/pathops/SkPathOpsQuad.h b/src/pathops/SkPathOpsQuad.h index d5ca0c7443..d06f3449bf 100644 --- a/src/pathops/SkPathOpsQuad.h +++ b/src/pathops/SkPathOpsQuad.h @@ -19,6 +19,11 @@ struct SkDQuadPair { struct SkDQuad { SkDPoint fPts[3]; + SkDQuad flip() const { + SkDQuad result = {{fPts[2], fPts[1], fPts[0]}}; + return result; + } + void set(const SkPoint pts[3]) { fPts[0] = pts[0]; fPts[1] = pts[1]; @@ -29,6 +34,7 @@ struct SkDQuad { SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 3); return fPts[n]; } static int AddValidTs(double s[], int realRoots, double* t); + void align(int endIndex, SkDPoint* dstPt) const; SkDQuadPair chopAt(double t) const; SkDVector dxdyAtT(double t) const; static int FindExtrema(double a, double b, double c, double tValue[1]); diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp index 199d7be14b..b071ca5371 100644 --- a/src/pathops/SkPathOpsTypes.cpp +++ b/src/pathops/SkPathOpsTypes.cpp @@ -4,36 +4,31 @@ * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ +#include "SkFloatBits.h" #include "SkPathOpsTypes.h" const int UlpsEpsilon = 16; // from http://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/ -union SkPathOpsUlpsFloat { - int32_t fInt; - float fFloat; - - SkPathOpsUlpsFloat(float num = 0.0f) : fFloat(num) {} - bool negative() const { return fInt < 0; } -}; - +// FIXME: move to SkFloatBits.h bool AlmostEqualUlps(float A, float B) { - SkPathOpsUlpsFloat uA(A); - SkPathOpsUlpsFloat uB(B); + SkFloatIntUnion floatIntA, floatIntB; + floatIntA.fFloat = A; + floatIntB.fFloat = B; // Different signs means they do not match. - if (uA.negative() != uB.negative()) + if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { // Check for equality to make sure +0 == -0 return A == B; } // Find the difference in ULPs. - int ulpsDiff = abs(uA.fInt - uB.fInt); + int ulpsDiff = abs(floatIntA.fSignBitInt - floatIntB.fSignBitInt); return ulpsDiff <= UlpsEpsilon; } // cube root approximation using bit hack for 64-bit float // adapted from Kahan's cbrt -static double cbrt_5d(double d) { +static double cbrt_5d(double d) { const unsigned int B1 = 715094163; double t = 0.0; unsigned int* pt = (unsigned int*) &t; @@ -43,7 +38,7 @@ static double cbrt_5d(double d) { } // iterative cube root approximation using Halley's method (double) -static double cbrta_halleyd(const double a, const double R) { +static double cbrta_halleyd(const double a, const double R) { const double a3 = a * a * a; const double b = a * (a3 + R + R) / (a3 + a3 + R); return b; diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index 0f689d818e..6ead79455c 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -7,8 +7,6 @@ #ifndef SkPathOpsTypes_DEFINED #define SkPathOpsTypes_DEFINED -#define SK_CONIC_SUPPORT_ENABLED 1 - #include <float.h> // for FLT_EPSILON #include <math.h> // for fabs, sqrt @@ -25,7 +23,7 @@ enum SkPathOpsMask { }; // Use Almost Equal when comparing coordinates. Use epsilon to compare T values. -extern bool AlmostEqualUlps(float A, float B); +bool AlmostEqualUlps(float A, float B); inline bool AlmostEqualUlps(double A, double B) { return AlmostEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B)); } @@ -34,10 +32,12 @@ inline bool AlmostEqualUlps(double A, double B) { // DBL_EPSILON == 2.22045e-16 const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON; const double FLT_EPSILON_HALF = FLT_EPSILON / 2; +const double FLT_EPSILON_DOUBLE = FLT_EPSILON * 2; const double FLT_EPSILON_SQUARED = FLT_EPSILON * FLT_EPSILON; const double FLT_EPSILON_SQRT = sqrt(FLT_EPSILON); const double FLT_EPSILON_INVERSE = 1 / FLT_EPSILON; const double DBL_EPSILON_ERR = DBL_EPSILON * 4; // FIXME: tune -- allow a few bits of error +const double DBL_EPSILON_SUBDIVIDE_ERR = DBL_EPSILON * 16; const double ROUGH_EPSILON = FLT_EPSILON * 64; const double MORE_ROUGH_EPSILON = FLT_EPSILON * 256; @@ -49,6 +49,10 @@ inline bool precisely_zero(double x) { return fabs(x) < DBL_EPSILON_ERR; } +inline bool precisely_subdivide_zero(double x) { + return fabs(x) < DBL_EPSILON_SUBDIVIDE_ERR; +} + inline bool approximately_zero(float x) { return fabs(x) < FLT_EPSILON; } @@ -61,6 +65,10 @@ inline bool approximately_zero_half(double x) { return fabs(x) < FLT_EPSILON_HALF; } +inline bool approximately_zero_double(double x) { + return fabs(x) < FLT_EPSILON_DOUBLE; +} + inline bool approximately_zero_squared(double x) { return fabs(x) < FLT_EPSILON_SQUARED; } @@ -69,6 +77,10 @@ inline bool approximately_zero_sqrt(double x) { return fabs(x) < FLT_EPSILON_SQRT; } +inline bool roughly_zero(double x) { + return fabs(x) < ROUGH_EPSILON; +} + inline bool approximately_zero_inverse(double x) { return fabs(x) > FLT_EPSILON_INVERSE; } @@ -88,10 +100,18 @@ inline bool precisely_equal(double x, double y) { return precisely_zero(x - y); } +inline bool precisely_subdivide_equal(double x, double y) { + return precisely_subdivide_zero(x - y); +} + inline bool approximately_equal_half(double x, double y) { return approximately_zero_half(x - y); } +inline bool approximately_equal_double(double x, double y) { + return approximately_zero_double(x - y); +} + inline bool approximately_equal_squared(double x, double y) { return approximately_equal(x, y); } @@ -112,14 +132,6 @@ inline bool approximately_lesser_or_equal(double x, double y) { return x - FLT_EPSILON < y; } -inline double approximately_pin(double x) { - return approximately_zero(x) ? 0 : x; -} - -inline float approximately_pin(float x) { - return approximately_zero(x) ? 0 : x; -} - inline bool approximately_greater_than_one(double x) { return x > 1 - FLT_EPSILON; } @@ -192,8 +204,6 @@ struct SkDTriangle; struct SkDCubic; struct SkDRect; -#if SK_CONIC_SUPPORT_ENABLED - inline SkPath::Verb SkPathOpsPointsToVerb(int points) { int verb = (1 << points) >> 1; #ifdef SK_DEBUG @@ -221,18 +231,6 @@ inline int SkPathOpsVerbToPoints(SkPath::Verb verb) { return points; } -#else - -inline SkPath::Verb SkOpPointsToVerb(int points) { - return (SkPath::Verb) (points); -} - -inline SkPath::Verb SkOpVerbToPoints(SkPath::Verb verb) { - return (int) verb ; -} - -#endif - inline double SkDInterp(double A, double B, double t) { return A + (B - A) * t; } diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp index 003b8c8317..ad91c87557 100644 --- a/tests/PathOpsAngleTest.cpp +++ b/tests/PathOpsAngleTest.cpp @@ -5,6 +5,7 @@ * found in the LICENSE file. */ #include "SkOpSegment.h" +#include "SkTArray.h" #include "Test.h" static const SkPoint cubics[][4] = { @@ -22,11 +23,18 @@ static const SkPoint cubics[][4] = { /* 10 */ {{0,1}, {1,3}, {1,0}, {6,4}}, /* 11 */ {{0,1}, {2,3}, {2,1}, {4,3}}, /* 12 */ {{1,2}, {3,4}, {1,0}, {3,2}}, +/* 13 */ {{0,1}, {4,6}, {4,3}, {5,4}}, +/* 14 */ {{806,11419}, {806.962890625,11419}, {807.76690673828125,11418.3193359375}, {807.957275390625,11417.4130859375}}, +/* 15 */ {{808,11417}, {808,11418.1044921875}, {807.10455322265625,11419}, {806,11419}}, +/* 16 */ {{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}, +/* 17 */ {{130.04275512695312,11417.4130859375}, {130.23312377929687,11418.3193359375}, {131.03707885742187,11419}, {132,11419}}, }; static const SkPoint quads[][3] = { /* 0 */ {{12.3423996f, 228.342407f}, {10, 230.686295f}, {10, 234}}, /* 1 */ {{304.24319458007812f,591.75677490234375f}, {306,593.51470947265625f}, {306,596}}, +/* 2 */ {{0,0}, {3,1}, {0,3}}, +/* 3 */ {{0,1}, {3,1}, {0,2}}, }; static const SkPoint lines[][2] = { @@ -40,6 +48,7 @@ static const SkPoint lines[][2] = { /* 7 */ {{192,4}, {243,4}}, /* 8 */ {{4,3}, {0,1}}, /* 9 */ {{3,2}, {1,2}}, +/* 10 */ {{6,4}, {3,4}}, }; struct SortSet { @@ -47,133 +56,214 @@ struct SortSet { int ptCount; double tStart; double tEnd; + SkPoint endPt; }; static const SortSet set1[] = { - {cubics[0], 4, 0.66666987081928919, 0.875}, - {lines[0], 2, 0.574070336, 0.388888889}, - {cubics[0], 4, 0.66666987081928919, 0.4050371120499307 }, - {lines[0], 2, 0.574070336, 0.9140625}, + {cubics[0], 4, 0.66666987081928919, 0.875, {0, 0}}, + {lines[0], 2, 0.574070336, 0.388888889, {0, 0}}, + {cubics[0], 4, 0.66666987081928919, 0.4050371120499307, {0, 0}}, + {lines[0], 2, 0.574070336, 0.9140625, {0, 0}}, +}; + +static const SortSet set1a[] = { + {cubics[0], 4, 0.666666667, 0.405037112, {4.58007812f,2.83203125f}}, + {lines[0], 2, 0.574074074, 0.9140625, {4.44444466f,2.77777767f}}, }; static const SortSet set2[] = { - {cubics[0], 4, 0.666666667, 0.875}, - {lines[0], 2, 0.574074074, 0.388888889}, - {cubics[0], 4, 0.666666667, 0.405037112}, - {lines[0], 2, 0.574074074, 0.9140625}, + {cubics[0], 4, 0.666666667, 0.875, {0, 0}}, + {lines[0], 2, 0.574074074, 0.388888889, {0, 0}}, + {cubics[0], 4, 0.666666667, 0.405037112, {0, 0}}, + {lines[0], 2, 0.574074074, 0.9140625, {0, 0}}, }; static const SortSet set3[] = { - {cubics[1], 4, 0, 1}, - {quads[0], 3, 1, 0}, + {cubics[1], 4, 0, 1, {0, 0}}, + {quads[0], 3, 1, 0, {0, 0}}, }; static const SortSet set4[] = { - {cubics[2], 4, 0.812114222, 1}, - {cubics[3], 4, 0.0684734759, 0}, + {cubics[2], 4, 0.812114222, 1, {0, 0}}, + {cubics[3], 4, 0.0684734759, 0, {0, 0}}, }; static const SortSet set5[] = { - {lines[1], 2, 0.777777778, 1}, - {quads[1], 3, 1, 4.34137342e-06}, - {lines[2], 2, 0, 1}, + {lines[1], 2, 0.777777778, 1, {0, 0}}, + {quads[1], 3, 1, 4.34137342e-06, {0, 0}}, + {lines[2], 2, 0, 1, {0, 0}}, +}; + +static const SortSet set5a[] = { + {lines[1], 2, 0.777777778, 1, {306,590}}, + {quads[1], 3, 1, 4.34137342e-06, {304.243195f,591.756775f}}, + {lines[2], 2, 0, 1, {306,617}}, }; static const SortSet set6[] = { - {lines[3], 2, 0.407407407, 0.554627832}, - {cubics[4], 4, 0.666666667, 0.548022446}, - {lines[3], 2, 0.407407407, 0}, - {cubics[4], 4, 0.666666667, 1}, + {lines[3], 2, 0.407407407, 0.554627832, {0, 0}}, + {cubics[4], 4, 0.666666667, 0.548022446, {0, 0}}, + {lines[3], 2, 0.407407407, 0, {0, 0}}, + {cubics[4], 4, 0.666666667, 1, {0, 0}}, +}; + +static const SortSet set6a[] = { + {lines[3], 2, 0.407407407, 0.554627832, {2.6722331f,2.33611655f}}, + {cubics[4], 4, 0.666666667, 0.548022446, {2.61642241f,2.83718514f}}, + {lines[3], 2, 0.407407407, 0, {6,4}}, + {cubics[4], 4, 0.666666667, 1, {6,4}}, }; static const SortSet set7[] = { - {cubics[5], 4, 0.545233342, 0.545454545}, - {cubics[6], 4, 0.484938134, 0.484805744}, - {cubics[5], 4, 0.545233342, 0}, - {cubics[6], 4, 0.484938134, 0.545454545}, + {cubics[5], 4, 0.545233342, 0.545454545, {0, 0}}, + {cubics[6], 4, 0.484938134, 0.484805744, {0, 0}}, + {cubics[5], 4, 0.545233342, 0, {0, 0}}, + {cubics[6], 4, 0.484938134, 0.545454545, {0, 0}}, }; static const SortSet set8[] = { - {cubics[7], 4, 0.5, 0.522986744 }, - {lines[4], 2, 0.75, 1}, - {cubics[7], 4, 0.5, 0}, - {lines[4], 2, 0.75, 0.737654321}, + {cubics[7], 4, 0.5, 0.522986744, {0, 0}}, + {lines[4], 2, 0.75, 1, {0, 0}}, + {cubics[7], 4, 0.5, 0, {0, 0}}, + {lines[4], 2, 0.75, 0.737654321, {0, 0}}, +}; + +static const SortSet set8a[] = { + {cubics[7], 4, 0.5, 0.522986744, {1.60668361f,0.965592742f}}, + {lines[4], 2, 0.75, 1, {0,1}}, + {cubics[7], 4, 0.5, 0, {0,1}}, + {lines[4], 2, 0.75, 0.737654321, {1.57407403f,1}}, }; static const SortSet set9[] = { - {cubics[8], 4, 0.4, 1}, - {lines[5], 2, 0.36, 0}, - {cubics[8], 4, 0.4, 0.394675838}, - {lines[5], 2, 0.36, 0.363999782}, + {cubics[8], 4, 0.4, 1, {0, 0}}, + {lines[5], 2, 0.36, 0, {0, 0}}, + {cubics[8], 4, 0.4, 0.394675838, {0, 0}}, + {lines[5], 2, 0.36, 0.363999782, {0, 0}}, }; static const SortSet set10[] = { - {lines[6], 2, 0.947368421, 1}, - {cubics[9], 4, 1, 0.500000357}, - {lines[7], 2, 0, 1}, + {lines[6], 2, 0.947368421, 1, {0, 0}}, + {cubics[9], 4, 1, 0.500000357, {0, 0}}, + {lines[7], 2, 0, 1, {0, 0}}, }; static const SortSet set11[] = { - {lines[3], 2, 0.75, 1}, - {cubics[10], 4, 0.5, 0.228744269}, - {lines[3], 2, 0.75, 0.627112191}, - {cubics[10], 4, 0.5, 0.6339746}, + {lines[3], 2, 0.75, 1, {0, 0}}, + {cubics[10], 4, 0.5, 0.228744269, {0, 0}}, + {lines[3], 2, 0.75, 0.627112191, {0, 0}}, + {cubics[10], 4, 0.5, 0.6339746, {0, 0}}, }; static const SortSet set12[] = { - {cubics[12], 4, 0.5, 1}, - {lines[8], 2, 0.5, 1}, - {cubics[11], 4, 0.5, 0}, - {lines[9], 2, 0.5, 1}, - {cubics[12], 4, 0.5, 0}, - {lines[8], 2, 0.5, 0}, - {cubics[11], 4, 0.5, 1}, - {lines[9], 2, 0.5, 0}, + {cubics[12], 4, 0.5, 1, {0, 0}}, + {lines[8], 2, 0.5, 1, {0, 0}}, + {cubics[11], 4, 0.5, 0, {0, 0}}, + {lines[9], 2, 0.5, 1, {0, 0}}, + {cubics[12], 4, 0.5, 0, {0, 0}}, + {lines[8], 2, 0.5, 0, {0, 0}}, + {cubics[11], 4, 0.5, 1, {0, 0}}, + {lines[9], 2, 0.5, 0, {0, 0}}, +}; + +static const SortSet set13[] = { + {cubics[13], 4, 0.5, 0.400631046, {0, 0}}, + {lines[10], 2, 0.791666667, 0.928, {0, 0}}, + {lines[10], 2, 0.791666667, 0.333333333, {0, 0}}, + {cubics[13], 4, 0.5, 0.866666667, {0, 0}}, +}; + +static const SortSet set14[] = { + {quads[2], 3, 0.5, 0.310102051, {0, 0}}, + {quads[3], 3, 0.5, 0.2, {0, 0}}, + {quads[3], 3, 0.5, 0.770156212, {0, 0}}, + {quads[2], 3, 0.5, 0.7, {0, 0}}, +}; + +static const SortSet set15[] = { + {cubics[14], 4, 0.93081374, 1, {0, 0}}, + {cubics[15], 4, 0.188518131, 0, {0, 0}}, + {cubics[14], 4, 0.93081374, 0, {0, 0}}, +}; + +static const SortSet set16[] = { + {cubics[17], 4, 0.0682619216, 0, {130.042755f,11417.4131f}}, + {cubics[16], 4, 0.812302088, 1, {130,11417}}, + {cubics[17], 4, 0.0682619216, 1, {132,11419}}, }; struct SortSetTests { + const char* name; const SortSet* set; size_t count; + SkPoint startPt; }; +#define TEST_ENTRY(name) #name, name, SK_ARRAY_COUNT(name) + static const SortSetTests tests[] = { - { set12, SK_ARRAY_COUNT(set12) }, - { set11, SK_ARRAY_COUNT(set11) }, - { set10, SK_ARRAY_COUNT(set10) }, - { set9, SK_ARRAY_COUNT(set9) }, - { set8, SK_ARRAY_COUNT(set8) }, - { set7, SK_ARRAY_COUNT(set7) }, - { set6, SK_ARRAY_COUNT(set6) }, - { set2, SK_ARRAY_COUNT(set2) }, - { set5, SK_ARRAY_COUNT(set5) }, - { set4, SK_ARRAY_COUNT(set4) }, - { set3, SK_ARRAY_COUNT(set3) }, - { set1, SK_ARRAY_COUNT(set1) }, -}; - -static void setup(const SortSet* set, const size_t idx, SkPoint const ** data, - SkOpSegment* seg, int* ts) { + { TEST_ENTRY(set16), {130.090179f,11417.5957f} }, +// { TEST_ENTRY(set15), {0, 0}}, + { TEST_ENTRY(set14), {0, 0}}, + { TEST_ENTRY(set13), {0, 0}}, + { TEST_ENTRY(set12), {0, 0}}, + { TEST_ENTRY(set11), {0, 0}}, + { TEST_ENTRY(set10), {0, 0}}, + { TEST_ENTRY(set9), {0, 0}}, + { TEST_ENTRY(set6a), {3.55555558f,2.77777767f} }, + { TEST_ENTRY(set8a), {1.5f,1} }, + { TEST_ENTRY(set8), {0, 0}}, + { TEST_ENTRY(set7), {0, 0}}, + { TEST_ENTRY(set6a), {3.55555558f,2.77777767f} }, + { TEST_ENTRY(set6), {0, 0}}, + { TEST_ENTRY(set5a), {306,596} }, + { TEST_ENTRY(set5), {0, 0}}, +// { TEST_ENTRY(set4), {0, 0}}, + { TEST_ENTRY(set3), {0, 0}}, + { TEST_ENTRY(set2), {0, 0}}, +// { TEST_ENTRY(set1a), {3.70370364f,3.14814806f} }, + { TEST_ENTRY(set1), {0, 0}}, +}; + +#undef TEST_ENTRY + +static void setup(const SortSet* set, const size_t idx, + SkOpSegment* seg, int* ts, const SkPoint& startPt) { SkPoint start, end; - *data = set[idx].ptData; + const SkPoint* data = set[idx].ptData; + bool useIntersectPt = startPt.fX != 0 || startPt.fY != 0; + if (useIntersectPt) { + start = startPt; + end = set[idx].endPt; + } switch(set[idx].ptCount) { case 2: { - seg->addLine(*data, false, false); + seg->addLine(data, false, false); SkDLine dLine; dLine.set(set[idx].ptData); + if (useIntersectPt) { + break; + } start = dLine.xyAtT(set[idx].tStart).asSkPoint(); end = dLine.xyAtT(set[idx].tEnd).asSkPoint(); } break; case 3: { - seg->addQuad(*data, false, false); + seg->addQuad(data, false, false); SkDQuad dQuad; dQuad.set(set[idx].ptData); + if (useIntersectPt) { + break; + } start = dQuad.xyAtT(set[idx].tStart).asSkPoint(); end = dQuad.xyAtT(set[idx].tEnd).asSkPoint(); } break; case 4: { - seg->addCubic(*data, false, false); + seg->addCubic(data, false, false); SkDCubic dCubic; dCubic.set(set[idx].ptData); + if (useIntersectPt) { + break; + } start = dCubic.xyAtT(set[idx].tStart).asSkPoint(); end = dCubic.xyAtT(set[idx].tEnd).asSkPoint(); } break; @@ -182,13 +272,11 @@ static void setup(const SortSet* set, const size_t idx, SkPoint const ** data, 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); + if (tStart != 0 && tEnd != 0) { + seg->addT(NULL, set[idx].ptData[0], 0); } - double tRight = tStart < tEnd ? 1 : 0; - if (tStart != tRight && tEnd != tRight) { - seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], tRight); + if (tStart != 1 && tEnd != 1) { + seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], 1); } int tIndex = 0; do { @@ -207,30 +295,153 @@ static void setup(const SortSet* set, const size_t idx, SkPoint const ** data, static void PathOpsAngleTest(skiatest::Reporter* reporter) { for (size_t index = 0; index < SK_ARRAY_COUNT(tests); ++index) { const SortSetTests& test = tests[index]; - for (size_t idxL = 0; idxL < test.count - 1; ++idxL) { - SkOpSegment lesser, greater; - int lesserTs[2], greaterTs[2]; - const SkPoint* lesserData, * greaterData; + SkTDArray<SkOpAngle> angles; + bool unsortable = false; + bool unorderable = false; + SkTArray<SkOpSegment> segs; + for (size_t idx = 0; idx < test.count; ++idx) { + int ts[2]; const SortSet* set = test.set; - setup(set, idxL, &lesserData, &lesser, lesserTs); - size_t idxG = idxL + 1; - setup(set, idxG, &greaterData, &greater, greaterTs); - SkOpAngle first, second; - first.set(lesserData, SkPathOpsPointsToVerb(set[idxL].ptCount - 1), &lesser, - lesserTs[0], lesserTs[1], lesser.spans()); - second.set(greaterData, SkPathOpsPointsToVerb(set[idxG].ptCount - 1), &greater, - greaterTs[0], greaterTs[1], greater.spans()); - bool compare = first < second; - if (!compare) { - SkDebugf("%s test[%d]: lesser[%d] > greater[%d]\n", __FUNCTION__, - index, idxL, idxG); - compare = first < second; + SkOpSegment& seg = segs.push_back(); + setup(set, idx, &seg, ts, test.startPt); + SkOpAngle* angle = angles.append(); + angle->set(&seg, ts[0], ts[1]); +#if DEBUG_ANGLE + angle->setID(idx); +#endif + if (angle->unsortable()) { +#if DEBUG_ANGLE + SkDebugf("%s test[%s]: angle[%d] unsortable\n", __FUNCTION__, test.name, idx); +#endif + unsortable = true; + } + if (angle->unorderable()) { +#if DEBUG_ANGLE + SkDebugf("%s test[%s]: angle[%d] unorderable\n", __FUNCTION__, test.name, idx); +#endif + unorderable = true; } - REPORTER_ASSERT(reporter, compare); reporter->bumpTestCount(); } + if (unsortable || unorderable) { + continue; + } +#if DEBUG_ANGLE + SkDebugf("%s test[%s]\n", __FUNCTION__, test.name); +#endif + for (size_t idxL = 0; idxL < test.count; ++idxL) { + const SkOpAngle& first = angles[idxL]; + for (size_t idxG = 0; idxG < test.count; ++idxG) { + if (idxL == idxG) { + continue; + } + const SkOpAngle& second = angles[idxG]; + bool compare = first < second; + if (idxL < idxG) { + if (!compare) { + SkDebugf("%s test[%s]: first[%d] > second[%d]\n", __FUNCTION__, + test.name, idxL, idxG); + compare = first < second; + } + REPORTER_ASSERT(reporter, compare); + } else { + SkASSERT(idxL > idxG); + if (compare) { + SkDebugf("%s test[%s]: first[%d] < second[%d]\n", __FUNCTION__, + test.name, idxL, idxG); + compare = first < second; + } + REPORTER_ASSERT(reporter, !compare); + } + compare = second < first; + if (idxL < idxG) { + if (compare) { + SkDebugf("%s test[%s]: second[%d] < first[%d]\n", __FUNCTION__, + test.name, idxL, idxG); + compare = second < first; + } + REPORTER_ASSERT(reporter, !compare); + } else { + SkASSERT(idxL > idxG); + if (!compare) { + SkDebugf("%s test[%s]: second[%d] > first[%d]\n", __FUNCTION__, + test.name, idxL, idxG); + compare = second < first; + } + REPORTER_ASSERT(reporter, compare); + } + } + } + reporter->bumpTestCount(); + } +} + +#if 0 +static int find_slop(double x, double y, double rx, double ry) { + int slopBits = 0; + bool less1, less2; + double absX = fabs(x); + double absY = fabs(y); + double length = absX < absY ? absX / 2 + absY : absX + absY / 2; + int exponent; + (void) frexp(length, &exponent); + double epsilon = ldexp(FLT_EPSILON, exponent); + do { + // get the length as the larger plus half the smaller (both same signs) + // find the ulps of the length + // compute the offsets from there + double xSlop = epsilon * slopBits; + double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ? + double x1 = x - xSlop; + double y1 = y + ySlop; + double x_ry1 = x1 * ry; + double rx_y1 = rx * y1; + less1 = x_ry1 < rx_y1; + double x2 = x + xSlop; + double y2 = y - ySlop; + double x_ry2 = x2 * ry; + double rx_y2 = rx * y2; + less2 = x_ry2 < rx_y2; + } while (less1 == less2 && ++slopBits); + return slopBits; +} + +// from http://stackoverflow.com/questions/1427422/cheap-algorithm-to-find-measure-of-angle-between-vectors +static double diamond_angle(double y, double x) +{ + if (y >= 0) + return (x >= 0 ? y/(x+y) : 1-x/(-x+y)); + else + return (x < 0 ? 2-y/(-x-y) : 3+x/(x-y)); +} + +static const double slopTests[][4] = { + // x y rx ry + {-0.058554756452593892, -0.18804585843827226, -0.018568569646021160, -0.059615294434479438}, + {-0.0013717412948608398, 0.0041152238845825195, -0.00045837944195925573, 0.0013753175735478074}, + {-2.1033774145221198, -1.4046019261273715e-008, -0.70062688352066704, -1.2706324683777995e-008}, +}; + +static void PathOpsAngleFindSlop(skiatest::Reporter* reporter) { + for (size_t index = 0; index < SK_ARRAY_COUNT(slopTests); ++index) { + const double* slopTest = slopTests[index]; + double x = slopTest[0]; + double y = slopTest[1]; + double rx = slopTest[2]; + double ry = slopTest[3]; + SkDebugf("%s xy %d=%d\n", __FUNCTION__, (int) index, find_slop(x, y, rx, ry)); + SkDebugf("%s rxy %d=%d\n", __FUNCTION__, (int) index, find_slop(rx, ry, x, y)); + double angle = diamond_angle(y, x); + double rAngle = diamond_angle(ry, rx); + double diff = fabs(angle - rAngle); + SkDebugf("%s diamond xy=%1.9g rxy=%1.9g diff=%1.9g factor=%d\n", __FUNCTION__, + angle, rAngle, diff, (int) (diff / FLT_EPSILON)); + } } +#endif #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsAngleTest) + +// DEFINE_TESTCLASS_SHORT(PathOpsAngleFindSlop) diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp index 58d7d98024..b0d6bd881b 100644 --- a/tests/PathOpsCubicIntersectionTest.cpp +++ b/tests/PathOpsCubicIntersectionTest.cpp @@ -163,6 +163,12 @@ static const SkDCubic testSet[] = { const size_t testSetCount = SK_ARRAY_COUNT(testSet); static const SkDCubic newTestSet[] = { +{{{134,11414}, {131.990234375,11414}, {130.32666015625,11415.482421875}, {130.04275512695312,11417.4130859375}}}, +{{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}}, + +{{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}}, +{{{130.04275512695312,11417.4130859375}, {130.23312377929687,11418.3193359375}, {131.03707885742187,11419}, {132,11419}}}, + {{{0, 1}, {2, 3}, {5, 1}, {4, 3}}}, {{{1, 5}, {3, 4}, {1, 0}, {3, 2}}}, @@ -231,10 +237,10 @@ const size_t newTestSetCount = SK_ARRAY_COUNT(newTestSet); static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const SkDCubic& cubic2) { #if ONE_OFF_DEBUG SkDebugf("computed quadratics given\n"); - SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", + SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY); - SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", + SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY); #endif @@ -244,7 +250,7 @@ static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const S SkDebugf("computed quadratics set 1\n"); for (int index = 0; index < quads1.count(); ++index) { const SkDQuad& q = quads1[index]; - SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", q[0].fX, q[0].fY, + SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY); } #endif @@ -254,7 +260,7 @@ static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const S SkDebugf("computed quadratics set 2\n"); for (int index = 0; index < quads2.count(); ++index) { const SkDQuad& q = quads2[index]; - SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", q[0].fX, q[0].fY, + SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY); } #endif @@ -267,12 +273,15 @@ static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const S xy1 = cubic1.xyAtT(tt1); tt2 = intersections[1][pt3]; xy2 = cubic2.xyAtT(tt2); + const SkDPoint& iPt = intersections.pt(pt3); #if ONE_OFF_DEBUG SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", - __FUNCTION__, tt1, xy1.fX, xy1.fY, intersections.pt(pt3).fX, - intersections.pt(pt3).fY, xy2.fX, xy2.fY, tt2); + __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX, + iPt.fY, xy2.fX, xy2.fY, tt2); #endif - REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); + REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt)); + REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt)); + REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); } } diff --git a/tests/PathOpsCubicToQuadsTest.cpp b/tests/PathOpsCubicToQuadsTest.cpp index f18784fb54..f738e0790d 100644 --- a/tests/PathOpsCubicToQuadsTest.cpp +++ b/tests/PathOpsCubicToQuadsTest.cpp @@ -20,7 +20,7 @@ static void test(skiatest::Reporter* reporter, const SkDCubic* cubics, const cha double precision = cubic.calcPrecision(); SkTDArray<SkDQuad> quads; CubicToQuads(cubic, precision, quads); - if (quads.count() != 1) { + if (quads.count() != 1 && quads.count() != 2) { SkDebugf("%s [%d] cubic to quadratics failed count=%d\n", name, static_cast<int>(index), quads.count()); } @@ -36,11 +36,11 @@ static void test(skiatest::Reporter* reporter, const SkDQuad* quadTests, const c double precision = cubic.calcPrecision(); SkTDArray<SkDQuad> quads; CubicToQuads(cubic, precision, quads); - if (quads.count() != 1) { + if (quads.count() != 1 && quads.count() != 2) { SkDebugf("%s [%d] cubic to quadratics failed count=%d\n", name, static_cast<int>(index), quads.count()); } - REPORTER_ASSERT(reporter, quads.count() == 1); + REPORTER_ASSERT(reporter, quads.count() <= 2); } } diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp index 71631c110a..a9ca58b1e9 100644 --- a/tests/PathOpsExtendedTest.cpp +++ b/tests/PathOpsExtendedTest.cpp @@ -45,27 +45,27 @@ static bool gComparePaths = true; static bool gComparePathsAssert = true; static bool gPathStrAssert = true; -static void showPathContours(SkPath::Iter& iter) { +static void showPathContours(SkPath::Iter& iter, const char* suffix) { uint8_t verb; SkPoint pts[4]; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { switch (verb) { case SkPath::kMove_Verb: - SkDebugf("path.moveTo(%1.9g,%1.9g);\n", pts[0].fX, pts[0].fY); + SkDebugf(" path%s.moveTo(%1.9g,%1.9g);\n", suffix, pts[0].fX, pts[0].fY); continue; case SkPath::kLine_Verb: - SkDebugf("path.lineTo(%1.9g,%1.9g);\n", pts[1].fX, pts[1].fY); + SkDebugf(" path%s.lineTo(%1.9g,%1.9g);\n", suffix, pts[1].fX, pts[1].fY); break; case SkPath::kQuad_Verb: - SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n", + SkDebugf(" path%s.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n", suffix, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); break; case SkPath::kCubic_Verb: - SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n", + SkDebugf(" path%s.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n", suffix, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY); break; case SkPath::kClose_Verb: - SkDebugf("path.close();\n"); + SkDebugf(" path%s.close();\n", suffix); break; default: SkDEBUGFAIL("bad verb"); @@ -74,11 +74,6 @@ static void showPathContours(SkPath::Iter& iter) { } } -void showPath(const SkPath& path, const char* str) { - SkDebugf("%s\n", !str ? "original:" : str); - showPath(path); -} - static const char* fillTypeStr[] = { "kWinding_FillType", "kEvenOdd_FillType", @@ -86,7 +81,7 @@ static const char* fillTypeStr[] = { "kInverseEvenOdd_FillType" }; -void showPath(const SkPath& path) { +static void showPath(const SkPath& path, const char* suffix) { SkPath::Iter iter(path, true); #define SUPPORT_RECT_CONTOUR_DETECTION 0 #if SUPPORT_RECT_CONTOUR_DETECTION @@ -108,12 +103,13 @@ void showPath(const SkPath& path) { #endif SkPath::FillType fillType = path.getFillType(); SkASSERT(fillType >= SkPath::kWinding_FillType && fillType <= SkPath::kInverseEvenOdd_FillType); - SkDebugf("path.setFillType(%s);\n", fillTypeStr[fillType]); + SkDebugf(" path%s.setFillType(SkPath::%s);\n", suffix, fillTypeStr[fillType]); iter.setPath(path, true); - showPathContours(iter); + showPathContours(iter, suffix); } -void showPathData(const SkPath& path) { +#if DEBUG_SHOW_TEST_NAME +static void showPathData(const SkPath& path) { SkPath::Iter iter(path, true); uint8_t verb; SkPoint pts[4]; @@ -142,6 +138,7 @@ void showPathData(const SkPath& path) { } } } +#endif void showOp(const SkPathOp op) { switch (op) { @@ -165,6 +162,7 @@ void showOp(const SkPathOp op) { } } +#if 0 static void showPath(const SkPath& path, const char* str, const SkMatrix& scale) { SkPath scaled; SkMatrix inverse; @@ -175,6 +173,7 @@ static void showPath(const SkPath& path, const char* str, const SkMatrix& scale) path.transform(inverse, &scaled); showPath(scaled, str); } +#endif #if DEBUG_SHOW_TEST_NAME static char hexorator(int x) { @@ -326,8 +325,8 @@ bool drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths) { static void showSimplifiedPath(const SkPath& one, const SkPath& two, const SkPath& scaledOne, const SkPath& scaledTwo) { - showPath(one, "original:"); - showPath(two, "simplified:"); + showPath(one, ""); + // showPath(two, "simplified:"); drawAsciiPaths(scaledOne, scaledTwo, true); } @@ -355,12 +354,15 @@ static void showPathOpPath(const SkPath& one, const SkPath& two, const SkPath& a const SkPath& scaledOne, const SkPath& scaledTwo, const SkPathOp shapeOp, const SkMatrix& scale) { SkASSERT((unsigned) shapeOp < SK_ARRAY_COUNT(opStrs)); - showPath(a, "minuend:"); - SkDebugf("op: %s\n", opStrs[shapeOp]); - showPath(b, "subtrahend:"); + SkDebugf("static void xOp#%s(skiatest::Reporter* reporter) {\n", opSuffixes[shapeOp]); + SkDebugf(" SkPath path, pathB;\n"); + showPath(a, ""); + showPath(b, "B"); + SkDebugf(" testPathOp(reporter, path, pathB, %s);\n", opStrs[shapeOp]); + SkDebugf("}\n"); // the region often isn't very helpful since it approximates curves with a lot of line-tos - if (0) showPath(scaledOne, "region:", scale); - showPath(two, "op result:"); + // if (0) showPath(scaledOne, "region:", scale); + // showPath(two, "op result:"); drawAsciiPaths(scaledOne, scaledTwo, true); } @@ -448,7 +450,7 @@ bool testSimplify(SkPath& path, bool useXor, SkPath& out, PathOpsThreadState& st SkPath::FillType fillType = useXor ? SkPath::kEvenOdd_FillType : SkPath::kWinding_FillType; path.setFillType(fillType); if (gShowPath) { - showPath(path); + showPath(path, ""); } if (!Simplify(path, &out)) { SkDebugf("%s did not expect failure\n", __FUNCTION__); diff --git a/tests/PathOpsExtendedTest.h b/tests/PathOpsExtendedTest.h index 5644c9415e..5e91dc1fd3 100644 --- a/tests/PathOpsExtendedTest.h +++ b/tests/PathOpsExtendedTest.h @@ -26,9 +26,6 @@ struct TestDesc { extern int comparePaths(const SkPath& one, const SkPath& two, SkBitmap& bitmap); extern bool drawAsciiPaths(const SkPath& one, const SkPath& two, bool drawPaths); extern void showOp(const SkPathOp op); -extern void showPath(const SkPath& path, const char* str); -extern void showPath(const SkPath& path); -extern void showPathData(const SkPath& path); extern bool testPathOp(skiatest::Reporter* reporter, const SkPath& a, const SkPath& b, const SkPathOp ); extern bool testSimplify(SkPath& path, bool useXor, SkPath& out, PathOpsThreadState& state, diff --git a/tests/PathOpsLineParametetersTest.cpp b/tests/PathOpsLineParametetersTest.cpp index 0361e1aea6..3b223ae89f 100644 --- a/tests/PathOpsLineParametetersTest.cpp +++ b/tests/PathOpsLineParametetersTest.cpp @@ -40,7 +40,7 @@ static void PathOpsLineParametersTest(skiatest::Reporter* reporter) { for (size_t index = 0; index < tests_count; ++index) { SkLineParameters lineParameters; const SkDCubic& cubic = tests[index]; - lineParameters.cubicEndPoints(cubic); + lineParameters.cubicEndPoints(cubic, 0, 3); double denormalizedDistance[2]; denormalizedDistance[0] = lineParameters.controlPtDistance(cubic, 1); denormalizedDistance[1] = lineParameters.controlPtDistance(cubic, 2); diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index 48ed866a90..9a48f7812f 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -1385,6 +1385,21 @@ static void cubicOp73d(skiatest::Reporter* reporter) { testPathOp(reporter, path, pathB, kDifference_PathOp); } +static void cubicOp74d(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(1,5, 5,1, 5,1); + path.lineTo(0,1); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1,5); + pathB.cubicTo(1,5, 1,0, 5,1); + pathB.lineTo(1,5); + pathB.close(); + testPathOp(reporter, path, pathB, kDifference_PathOp); +} + static void cubicOp75d(skiatest::Reporter* reporter) { SkPath path, pathB; path.setFillType(SkPath::kWinding_FillType); @@ -1400,6 +1415,19 @@ static void cubicOp75d(skiatest::Reporter* reporter) { testPathOp(reporter, path, pathB, kDifference_PathOp); } +static void cubicOp76u(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(0,2, 2,0, 5,3); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(0,2); + pathB.cubicTo(3,5, 1,0, 2,0); + pathB.close(); + testPathOp(reporter, path, pathB, kUnion_PathOp); +} + static void cubicOp77i(skiatest::Reporter* reporter) { SkPath path, pathB; path.setFillType(SkPath::kEvenOdd_FillType); @@ -1430,19 +1458,6 @@ static void cubicOp78u(skiatest::Reporter* reporter) { testPathOp(reporter, path, pathB, kUnion_PathOp); } -static void cubicOp79d(skiatest::Reporter* reporter) { - SkPath path, pathB; - path.setFillType(SkPath::kWinding_FillType); - path.moveTo(0,2); - path.cubicTo(0,1, 3,-0.1f, 1,0); - path.close(); - pathB.setFillType(SkPath::kWinding_FillType); - pathB.moveTo(0,3); - pathB.cubicTo(0,1, 2,0, 1,0); - pathB.close(); - testPathOp(reporter, path, pathB, kDifference_PathOp); -} - static void cubicOp79u(skiatest::Reporter* reporter) { SkPath path, pathB; path.setFillType(SkPath::kWinding_FillType); @@ -1471,6 +1486,19 @@ static void cubicOp80i(skiatest::Reporter* reporter) { testPathOp(reporter, path, pathB, kIntersect_PathOp); } +static void cubicOp81d(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,1); + path.cubicTo(4,6, 4,3, 5,4); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(3,4); + pathB.cubicTo(4,5, 1,0, 6,4); + pathB.close(); + testPathOp(reporter, path, pathB, kDifference_PathOp); +} + static void cubicOp82i(skiatest::Reporter* reporter) { SkPath path, pathB; path.setFillType(SkPath::kEvenOdd_FillType); @@ -1486,30 +1514,110 @@ static void cubicOp82i(skiatest::Reporter* reporter) { testPathOp(reporter, path, pathB, kIntersect_PathOp); } -static void cubicOp81d(skiatest::Reporter* reporter) { +static void cubicOp83i(skiatest::Reporter* reporter) { SkPath path, pathB; path.setFillType(SkPath::kWinding_FillType); path.moveTo(0,1); - path.cubicTo(4,6, 4,3, 5,4); + path.cubicTo(0,3, 2,1, 4,1); + path.lineTo(0,1); path.close(); pathB.setFillType(SkPath::kWinding_FillType); - pathB.moveTo(3,4); - pathB.cubicTo(4,5, 1,0, 6,4); + pathB.moveTo(1,2); + pathB.cubicTo(1,4, 1,0, 3,0); + pathB.lineTo(1,2); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +static void cubicOp84d(skiatest::Reporter* reporter) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0,4); + path.cubicTo(2,3, 6,3, 3,2); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(3,6); + pathB.cubicTo(2,3, 4,0, 3,2); pathB.close(); testPathOp(reporter, path, pathB, kDifference_PathOp); } -static void (*firstTest)(skiatest::Reporter* ) = cubicOp81d; +static void skpClip1(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(1126.17114f, 877.171204f); + path.quadTo(1127.34314f, 876.000000f, 1129.00000f, 876.000000f); + path.lineTo(1243.00000f, 876.000000f); + path.quadTo(1244.65686f, 876.000000f, 1245.82886f, 877.171204f); + path.quadTo(1247.00000f, 878.343140f, 1247.00000f, 880.000000f); + path.lineTo(1247.00000f, 907.000000f); + path.lineTo(1246.00000f, 907.000000f); + path.lineTo(1246.00000f, 880.000000f); + path.cubicTo(1246.00000f, 878.343140f, 1244.65686f, 877.000000f, 1243.00000f, 877.000000f); + path.lineTo(1129.00000f, 877.000000f); + path.cubicTo(1127.34314f, 877.000000f, 1126.00000f, 878.343140f, 1126.00000f, 880.000000f); + path.lineTo(1126.00000f, 907.000000f); + path.lineTo(1125.00000f, 907.000000f); + path.lineTo(1125.00000f, 880.000000f); + path.quadTo(1125.00000f, 878.343140f, 1126.17114f, 877.171204f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1247.00000f, 876.000000f); + pathB.lineTo(1231.00000f, 892.000000f); + pathB.lineTo(1246.00000f, 907.000000f); + pathB.lineTo(1247.00000f, 907.000000f); + pathB.lineTo(1247.00000f, 876.000000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} + +#if 1 // FIXME: work in progress -- coincident cubic undetected +static void skpClip2(skiatest::Reporter* reporter) { + SkPath path; + path.setFillType(SkPath::kEvenOdd_FillType); + path.moveTo(134.000000f, 11414.0000f); + path.cubicTo(131.990234f, 11414.0000f, 130.326660f, 11415.4824f, 130.042755f, 11417.4131f); + path.cubicTo(130.233124f, 11418.3193f, 131.037079f, 11419.0000f, 132.000000f, 11419.0000f); + path.lineTo(806.000000f, 11419.0000f); + path.cubicTo(806.962891f, 11419.0000f, 807.766907f, 11418.3193f, 807.957275f, 11417.4131f); + path.cubicTo(807.673401f, 11415.4824f, 806.009766f, 11414.0000f, 804.000000f, 11414.0000f); + path.lineTo(134.000000f, 11414.0000f); + path.close(); + SkPath pathB; + pathB.setFillType(SkPath::kInverseWinding_FillType); + pathB.moveTo(132.000000f, 11415.0000f); + pathB.lineTo(806.000000f, 11415.0000f); + pathB.cubicTo(807.104553f, 11415.0000f, 808.000000f, 11415.4473f, 808.000000f, 11416.0000f); + pathB.lineTo(808.000000f, 11417.0000f); + pathB.cubicTo(808.000000f, 11418.1045f, 807.104553f, 11419.0000f, 806.000000f, 11419.0000f); + pathB.lineTo(132.000000f, 11419.0000f); + pathB.cubicTo(130.895432f, 11419.0000f, 130.000000f, 11418.1045f, 130.000000f, 11417.0000f); + pathB.lineTo(130.000000f, 11416.0000f); + pathB.cubicTo(130.000000f, 11415.4473f, 130.895432f, 11415.0000f, 132.000000f, 11415.0000f); + pathB.close(); + testPathOp(reporter, path, pathB, kIntersect_PathOp); +} +#endif + +static void (*firstTest)(skiatest::Reporter* ) = 0; static struct TestDesc tests[] = { +#if 1 // FIXME: work in progress -- coincident cubic undetected + TEST(skpClip2), +#endif + TEST(skpClip1), + TEST(cubicOp84d), + TEST(cubicOp83i), TEST(cubicOp82i), TEST(cubicOp81d), TEST(cubicOp80i), TEST(cubicOp79u), - TEST(cubicOp79d), TEST(cubicOp78u), TEST(cubicOp77i), + TEST(cubicOp76u), TEST(cubicOp75d), + TEST(cubicOp74d), TEST(cubicOp73d), TEST(cubicOp72i), TEST(cubicOp71d), diff --git a/tests/PathOpsQuadIntersectionTest.cpp b/tests/PathOpsQuadIntersectionTest.cpp index 4276051c6c..4bb0b343f0 100644 --- a/tests/PathOpsQuadIntersectionTest.cpp +++ b/tests/PathOpsQuadIntersectionTest.cpp @@ -50,6 +50,19 @@ static void standardTestCases(skiatest::Reporter* reporter) { } static const SkDQuad testSet[] = { + {{{131.37418,11414.9825}, {130.28798,11415.9328}, {130.042755,11417.4131}}}, + {{{130.585787,11418.4142}, {130.021447,11417.8498}, {130,11417}}}, + + {{{130.73167037963867, 11418.546386718750}, {131.26360225677490, 11418.985778808592}, + {132, 11419 }}}, + {{{132, 11419}, {131.15012693405151, 11418.978546142578}, + {130.58578681945801, 11418.414184570313}}}, + + {{{132, 11419}, + {130.73167037963867, 11418.546386718750}, {131.26360225677490, 11418.985778808592}}}, + {{{131.15012693405151, 11418.978546142578}, + {130.58578681945801, 11418.414184570313}, {132, 11419}}}, + {{{3.0774019473063863, 3.35198509346713}, {3.0757503498668397, 3.327320623945933}, {3.0744102085015879, 3.3025879417907196}}}, {{{3.053913680774329, 3.3310471586283938}, {3.0758730889691694, 3.3273466070370152}, @@ -252,7 +265,7 @@ static void oneOffTest1(skiatest::Reporter* reporter, size_t outer, size_t inner } static void QuadraticIntersection_OneOffTest(skiatest::Reporter* reporter) { - oneOffTest1(reporter, 43, 47); + oneOffTest1(reporter, 0, 1); } static void oneOffTests(skiatest::Reporter* reporter) { diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp index f4a332e231..fe5f4e145d 100644 --- a/tests/PathOpsSimplifyTest.cpp +++ b/tests/PathOpsSimplifyTest.cpp @@ -3772,9 +3772,51 @@ static void testQuad7(skiatest::Reporter* reporter) { testSimplify(reporter, path); } -static void (*firstTest)(skiatest::Reporter* ) = testQuadratic85; +static void testQuadLineIntersect1(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(0, 0); + path.quadTo(3, 1, 0, 3); + path.lineTo(2, 3); + path.close(); + path.moveTo(2, 0); + path.lineTo(0, 1); + path.quadTo(3, 1, 0, 2); + path.close(); + testSimplify(reporter, path); +} + +static void testQuadLineIntersect2(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(0, 0); + path.quadTo(3, 1, 0, 3); + path.lineTo(0, 3); + path.close(); + path.moveTo(2, 0); + path.lineTo(0, 1); + path.quadTo(3, 1, 0, 2); + path.close(); + testSimplify(reporter, path); +} + +static void testQuadLineIntersect3(skiatest::Reporter* reporter) { + SkPath path; + path.moveTo(0, 0); + path.quadTo(3, 1, 0, 3); + path.lineTo(1, 3); + path.close(); + path.moveTo(2, 0); + path.lineTo(0, 1); + path.quadTo(3, 1, 0, 2); + path.close(); + testSimplify(reporter, path); +} + +static void (*firstTest)(skiatest::Reporter* ) = 0; static TestDesc tests[] = { + TEST(testQuadLineIntersect1), + TEST(testQuadLineIntersect2), + TEST(testQuadLineIntersect3), TEST(testQuad7), TEST(testQuad6), TEST(testQuad5), diff --git a/tests/PathOpsSkpClipTest.cpp b/tests/PathOpsSkpClipTest.cpp index d14cde54ce..98e55539ef 100644 --- a/tests/PathOpsSkpClipTest.cpp +++ b/tests/PathOpsSkpClipTest.cpp @@ -1,6 +1,7 @@ #include "SkBitmap.h" #include "SkDevice.h" #include "SkCanvas.h" +#include "SkImageDecoder.h" #include "SkImageEncoder.h" #include "SkStream.h" #include "SkOSFile.h" @@ -18,14 +19,14 @@ static void make_filepath(SkString* path, const char* dir, const SkString& 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"; + const char pictDir[] = "D:\\skp"; + const char outSkpClipDir[] = "D:\\skpClip"; + const char outOldClipDir[] = "D:\\oldClip"; SkOSFile::Iter iter(pictDir, "skp"); SkString filename; while (iter.next(&filename)) { -#if 0 - if (strcmp(filename.c_str(), "tabl_androidpolice.skp")) { +#if 01 + if (strcmp(filename.c_str(), "desk_15min-lt.skp")) { continue; } #endif @@ -35,7 +36,11 @@ const char pictDir[] = "C:\\Users\\caryclark\\skp"; if (!stream.isValid()) { continue; } - SkPicture* pic = SkNEW_ARGS(SkPicture, (&stream)); + bool success; + SkPicture* pic = SkNEW_ARGS(SkPicture, (&stream, &success, &SkImageDecoder::DecodeMemory)); + if (!success) { + continue; + } int width = pic->width(); int height = pic->height(); SkBitmap bitmap; diff --git a/tests/PathOpsTestCommon.cpp b/tests/PathOpsTestCommon.cpp index 86f6859c6b..aab7d6ea25 100644 --- a/tests/PathOpsTestCommon.cpp +++ b/tests/PathOpsTestCommon.cpp @@ -10,7 +10,7 @@ void CubicToQuads(const SkDCubic& cubic, double precision, SkTDArray<SkDQuad>& quads) { SkTDArray<double> ts; cubic.toQuadraticTs(precision, &ts); - if (ts.count() <= 1) { + if (ts.count() <= 0) { SkDQuad quad = cubic.toQuad(); *quads.append() = quad; return; |