diff options
29 files changed, 783 insertions, 284 deletions
diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp index 511879cd70..6e049708ac 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -15,11 +15,12 @@ #include "SkTSort.h" #if ONE_OFF_DEBUG -static const double tLimits1[2][2] = {{0.36, 0.37}, {0.63, 0.64}}; +static const double tLimits1[2][2] = {{0.388600450, 0.388600452}, {0.245852802, 0.245852804}}; static const double tLimits2[2][2] = {{-0.865211397, -0.865215212}, {-0.865207696, -0.865208078}}; #endif -#define DEBUG_QUAD_PART 0 +#define DEBUG_QUAD_PART ONE_OFF_DEBUG && 1 +#define DEBUG_QUAD_PART_SHOW_SIMPLE DEBUG_QUAD_PART && 0 #define SWAP_TOP_DEBUG 0 static const int kCubicToQuadSubdivisionDepth = 8; // slots reserved for cubic to quads subdivision @@ -31,25 +32,27 @@ static int quadPart(const SkDCubic& cubic, double tStart, double tEnd, SkReduceO // extremely shallow quadratic? int order = reducer->reduce(quad, SkReduceOrder::kFill_Style); #if DEBUG_QUAD_PART - SkDebugf("%s cubic=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)" - " t=(%1.17g,%1.17g)\n", __FUNCTION__, cubic[0].fX, cubic[0].fY, + SkDebugf("%s cubic=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" + " t=(%1.9g,%1.9g)\n", __FUNCTION__, cubic[0].fX, cubic[0].fY, cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY, cubic[3].fX, cubic[3].fY, tStart, tEnd); - SkDebugf("%s part=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)" - " quad=(%1.17g,%1.17g %1.17g,%1.17g %1.17g,%1.17g)\n", __FUNCTION__, + SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n" + " {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", part[0].fX, part[0].fY, part[1].fX, part[1].fY, part[2].fX, part[2].fY, part[3].fX, part[3].fY, quad[0].fX, quad[0].fY, quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY); - SkDebugf("%s simple=(%1.17g,%1.17g", __FUNCTION__, reducer->fQuad[0].fX, reducer->fQuad[0].fY); +#if DEBUG_QUAD_PART_SHOW_SIMPLE + SkDebugf("%s simple=(%1.9g,%1.9g", __FUNCTION__, reducer->fQuad[0].fX, reducer->fQuad[0].fY); if (order > 1) { - SkDebugf(" %1.17g,%1.17g", reducer->fQuad[1].fX, reducer->fQuad[1].fY); + SkDebugf(" %1.9g,%1.9g", reducer->fQuad[1].fX, reducer->fQuad[1].fY); } if (order > 2) { - SkDebugf(" %1.17g,%1.17g", reducer->fQuad[2].fX, reducer->fQuad[2].fY); + SkDebugf(" %1.9g,%1.9g", reducer->fQuad[2].fX, reducer->fQuad[2].fY); } SkDebugf(")\n"); SkASSERT(order < 4 && order > 0); #endif +#endif return order; } @@ -240,7 +243,7 @@ static void intersect(const SkDCubic& cubic1, double t1s, double t1e, const SkDC i.used(), i.used() > 0 ? i[0][i.used() - 1] : -1); #endif } - intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i); + // intersect(cubic1, c1Min, c1Max, cubic2, c2Min, c2Max, offset, i); // FIXME: if no intersection is found, either quadratics intersected where // cubics did not, or the intersection was missed. In the former case, expect // the quadratics to be nearly parallel at the point of intersection, and check diff --git a/src/pathops/SkDCubicLineIntersection.cpp b/src/pathops/SkDCubicLineIntersection.cpp index f86a21ccc1..dc80479f60 100644 --- a/src/pathops/SkDCubicLineIntersection.cpp +++ b/src/pathops/SkDCubicLineIntersection.cpp @@ -80,7 +80,12 @@ public: LineCubicIntersections(const SkDCubic& c, const SkDLine& l, SkIntersections& i) : cubic(c) , line(l) - , intersections(i) { + , intersections(i) + , fAllowNear(true) { +} + +void allowNear(bool allow) { + fAllowNear = allow; } // see parallel routine in line quadratic intersections @@ -97,7 +102,7 @@ int intersectRay(double roots[3]) { } int intersect() { - addEndPoints(); + addExactEndPoints(); double rootVals[3]; int roots = intersectRay(rootVals); for (int index = 0; index < roots; ++index) { @@ -113,6 +118,9 @@ int intersect() { intersections.insert(cubicT, lineT, pt); } } + if (fAllowNear) { + addNearEndPoints(); + } return intersections.used(); } @@ -124,7 +132,7 @@ int horizontalIntersect(double axisIntercept, double roots[3]) { } int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { - addHorizontalEndPoints(left, right, axisIntercept); + addExactHorizontalEndPoints(left, right, axisIntercept); double rootVals[3]; int roots = horizontalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { @@ -135,6 +143,9 @@ int horizontalIntersect(double axisIntercept, double left, double right, bool fl intersections.insert(cubicT, lineT, pt); } } + if (fAllowNear) { + addNearHorizontalEndPoints(left, right, axisIntercept); + } if (flipped) { intersections.flip(); } @@ -149,7 +160,7 @@ int verticalIntersect(double axisIntercept, double roots[3]) { } int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { - addVerticalEndPoints(top, bottom, axisIntercept); + addExactVerticalEndPoints(top, bottom, axisIntercept); double rootVals[3]; int roots = verticalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { @@ -160,6 +171,9 @@ int verticalIntersect(double axisIntercept, double top, double bottom, bool flip intersections.insert(cubicT, lineT, pt); } } + if (fAllowNear) { + addNearVerticalEndPoints(top, bottom, axisIntercept); + } if (flipped) { intersections.flip(); } @@ -168,65 +182,81 @@ int verticalIntersect(double axisIntercept, double top, double bottom, bool flip protected: -void addEndPoints() { +void addExactEndPoints() { for (int cIndex = 0; cIndex < 4; cIndex += 3) { - bool foundEnd = false; - for (int lIndex = 0; lIndex < 2; lIndex++) { - if (cubic[cIndex] == line[lIndex]) { - intersections.insert(cIndex >> 1, lIndex, line[lIndex]); - foundEnd = true; - } - } - // for the test case this was written for, the dist / error ratio was 170.6667 - // it looks like the cubic stops short of touching the line, but this fixed it. - if (foundEnd) { + double lineT = line.exactPoint(cubic[cIndex]); + if (lineT < 0) { continue; } - // See if the cubic end touches the line. - double dist = line.isLeft(cubic[cIndex]); // this distance isn't cartesian - SkDVector lineLen = line[1] - line[0]; // the x/y magnitudes of the line - // compute the ULPS of the larger of the x/y deltas - double larger = SkTMax(SkTAbs(lineLen.fX), SkTAbs(lineLen.fY)); - if (!RoughlyEqualUlps(larger, larger + dist)) { // is the dist within ULPS tolerance? + double cubicT = (double) (cIndex >> 1); + intersections.insert(cubicT, lineT, cubic[cIndex]); + } +} + +void addNearEndPoints() { + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + double cubicT = (double) (cIndex >> 1); + if (intersections.hasT(cubicT)) { continue; } - double lineT = findLineT(cIndex >> 1); - if (!between(0, lineT, 1)) { + double lineT = line.nearPoint(cubic[cIndex]); + if (lineT < 0) { continue; } - SkDPoint linePt = line.xyAtT(lineT); - if (linePt.approximatelyEqual(cubic[cIndex])) { - intersections.insert(cIndex >> 1, lineT, cubic[cIndex]); - } + intersections.insert(cubicT, lineT, cubic[cIndex]); } } -void addHorizontalEndPoints(double left, double right, double y) { +void addExactHorizontalEndPoints(double left, double right, double y) { for (int cIndex = 0; cIndex < 4; cIndex += 3) { - if (cubic[cIndex].fY != y) { + double lineT = SkDLine::ExactPointH(cubic[cIndex], left, right, y); + if (lineT < 0) { continue; } - if (cubic[cIndex].fX == left) { - intersections.insert(cIndex >> 1, 0, cubic[cIndex]); + double cubicT = (double) (cIndex >> 1); + intersections.insert(cubicT, lineT, cubic[cIndex]); + } +} + +void addNearHorizontalEndPoints(double left, double right, double y) { + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + double cubicT = (double) (cIndex >> 1); + if (intersections.hasT(cubicT)) { + continue; } - if (cubic[cIndex].fX == right) { - intersections.insert(cIndex >> 1, 1, cubic[cIndex]); + double lineT = SkDLine::NearPointH(cubic[cIndex], left, right, y); + if (lineT < 0) { + continue; } + intersections.insert(cubicT, lineT, cubic[cIndex]); } + // FIXME: see if line end is nearly on cubic } -void addVerticalEndPoints(double top, double bottom, double x) { +void addExactVerticalEndPoints(double top, double bottom, double x) { for (int cIndex = 0; cIndex < 4; cIndex += 3) { - if (cubic[cIndex].fX != x) { + double lineT = SkDLine::ExactPointV(cubic[cIndex], top, bottom, x); + if (lineT < 0) { continue; } - if (cubic[cIndex].fY == top) { - intersections.insert(cIndex >> 1, 0, cubic[cIndex]); + double cubicT = (double) (cIndex >> 1); + intersections.insert(cubicT, lineT, cubic[cIndex]); + } +} + +void addNearVerticalEndPoints(double top, double bottom, double x) { + for (int cIndex = 0; cIndex < 4; cIndex += 3) { + double cubicT = (double) (cIndex >> 1); + if (intersections.hasT(cubicT)) { + continue; } - if (cubic[cIndex].fY == bottom) { - intersections.insert(cIndex >> 1, 1, cubic[cIndex]); + double lineT = SkDLine::NearPointV(cubic[cIndex], top, bottom, x); + if (lineT < 0) { + continue; } + intersections.insert(cubicT, lineT, cubic[cIndex]); } + // FIXME: see if line end is nearly on cubic } double findLineT(double t) { @@ -264,6 +294,7 @@ private: const SkDCubic& cubic; const SkDLine& line; SkIntersections& intersections; +bool fAllowNear; }; int SkIntersections::horizontal(const SkDCubic& cubic, double left, double right, double y, @@ -280,6 +311,7 @@ int SkIntersections::vertical(const SkDCubic& cubic, double top, double bottom, int SkIntersections::intersect(const SkDCubic& cubic, const SkDLine& line) { LineCubicIntersections c(cubic, line, *this); + c.allowNear(fAllowNear); return c.intersect(); } diff --git a/src/pathops/SkDLineIntersection.cpp b/src/pathops/SkDLineIntersection.cpp index 3b88b88702..faa7c1d392 100644 --- a/src/pathops/SkDLineIntersection.cpp +++ b/src/pathops/SkDLineIntersection.cpp @@ -75,47 +75,19 @@ int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { return computePoints(a, used); } -static bool checkEndPoint(double x, double y, const SkDLine& l, double* tPtr, int useX) { - if (!between(l[0].fX, x, l[1].fX) || !between(l[0].fY, y, l[1].fY)) { - return false; - } - double xLen = l[1].fX - l[0].fX; - double yLen = l[1].fY - l[0].fY; - if (useX < 0) { - useX = SkTAbs(xLen) > SkTAbs(yLen); - } - // OPTIMIZATION: do between test before divide - double t = useX ? (x - l[0].fX) / xLen : (y - l[0].fY) / yLen; - if (!between(0, t, 1)) { - return false; - } - double opp = useX ? (1 - t) * l[0].fY + t * l[1].fY : (1 - t) * l[0].fX + t * l[1].fX; - if (!AlmostEqualUlps(opp, useX ? y : x)) { - return false; - } - *tPtr = t; - return true; -} - // note that this only works if both lines are neither horizontal nor vertical int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { // see if end points intersect the opposite line double t; for (int iA = 0; iA < 2; ++iA) { - if (!checkEndPoint(a[iA].fX, a[iA].fY, b, &t, -1)) { - continue; + if ((t = b.exactPoint(a[iA])) >= 0) { + insert(iA, t, a[iA]); } - insert(iA, t, a[iA]); } for (int iB = 0; iB < 2; ++iB) { - if (!checkEndPoint(b[iB].fX, b[iB].fY, a, &t, -1)) { - continue; + if ((t = a.exactPoint(b[iB])) >= 0) { + insert(t, iB, b[iB]); } - insert(t, iB, b[iB]); - } - if (used() > 0) { - SkASSERT(fUsed <= 2); - return used(); // coincident lines are returned here } /* Determine the intersection point of two line segments Return FALSE if the lines don't intersect @@ -131,166 +103,198 @@ int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { 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; - bool mayNotOverlap = (numerA < 0 && denom > numerA) || (numerA > 0 && denom < numerA) - || (numerB < 0 && denom > numerB) || (numerB > 0 && denom < numerB); - numerA /= denom; - numerB /= denom; - if ((!approximately_zero(denom) || (!approximately_zero_inverse(numerA) - && !approximately_zero_inverse(numerB))) && !sk_double_isnan(numerA) - && !sk_double_isnan(numerB)) { - if (mayNotOverlap) { - return 0; + if (0 != denom) { + 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; + if (between(0, numerA, denom) && between(0, numerB, denom)) { + fT[0][0] = numerA / denom; + fT[1][0] = numerB / denom; + return computePoints(a, 1); } - fT[0][0] = numerA; - fT[1][0] = numerB; - fPt[0] = a.xyAtT(numerA); - return computePoints(a, 1); } - return 0; + if (fAllowNear || 0 == denom) { + for (int iA = 0; iA < 2; ++iA) { + if ((t = b.nearPoint(a[iA])) >= 0) { + insert(iA, t, a[iA]); + } + } + for (int iB = 0; iB < 2; ++iB) { + if ((t = a.nearPoint(b[iB])) >= 0) { + insert(t, iB, b[iB]); + } + } + } + return fUsed; } -int SkIntersections::horizontal(const SkDLine& line, double y) { +static int horizontal_coincident(const SkDLine& line, double y) { double min = line[0].fY; double max = line[1].fY; if (min > max) { SkTSwap(min, max); } if (min > y || max < y) { - return fUsed = 0; + return 0; } if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) { - fT[0][0] = 0; - fT[0][1] = 1; - return fUsed = 2; + return 2; } - fT[0][0] = (y - line[0].fY) / (line[1].fY - line[0].fY); - return fUsed = 1; + return 1; } -static bool checkEndPointH(const SkDPoint& end, double left, double right, - double y, bool flipped, double* tPtr) { - if (!between(left, end.fX, right) || !AlmostEqualUlps(y, end.fY)) { - return false; +static double horizontal_intercept(const SkDLine& line, double y) { + return (y - line[0].fY) / (line[1].fY - line[0].fY); +} + +int SkIntersections::horizontal(const SkDLine& line, double y) { + int horizontalType = horizontal_coincident(line, y); + if (horizontalType == 1) { + fT[0][0] = horizontal_intercept(line, y); + } else if (horizontalType == 2) { + fT[0][0] = 0; + fT[0][1] = 1; } - double t = (end.fX - left) / (right - left); - SkASSERT(between(0, t, 1)); - *tPtr = flipped ? 1 - t : t; - return true; + return fUsed = horizontalType; } int SkIntersections::horizontal(const SkDLine& line, double left, double right, double y, bool flipped) { // see if end points intersect the opposite line double t; - if (checkEndPoint(left, y, line, &t, true)) { - insert(t, flipped, left, y); + const SkDPoint leftPt = { left, y }; + if ((t = line.exactPoint(leftPt)) >= 0) { + insert(t, (double) flipped, leftPt); } if (left != right) { - if (checkEndPoint(right, y, line, &t, true)) { - insert(t, !flipped, right, y); + const SkDPoint rightPt = { right, y }; + if ((t = line.exactPoint(rightPt)) >= 0) { + insert(t, (double) !flipped, rightPt); } for (int index = 0; index < 2; ++index) { - if (!checkEndPointH(line[index], left, right, y, flipped, &t)) { - continue; + if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) { + insert((double) index, flipped ? 1 - t : t, line[index]); } - insert(index, t, line[index]); } } - if (used() > 0) { - SkASSERT(fUsed <= 2); - return used(); // coincident lines are returned here + int result = horizontal_coincident(line, y); + if (result == 1 && fUsed == 0) { + fT[0][0] = horizontal_intercept(line, y); + double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX); + if (between(left, xIntercept, right)) { + fT[1][0] = (xIntercept - left) / (right - left); + if (flipped) { + // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX + for (int index = 0; index < result; ++index) { + fT[1][index] = 1 - fT[1][index]; + } + } + return computePoints(line, result); + } } - int result = horizontal(line, y); - if (!result) { - return 0; + if (!fAllowNear && result != 2) { + return fUsed; } - SkASSERT(result == 1); - double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX); - if (!precisely_between(left, xIntercept, right)) { - return fUsed = 0; + if ((t = line.nearPoint(leftPt)) >= 0) { + insert(t, (double) flipped, leftPt); } - fT[1][0] = (xIntercept - left) / (right - left); - if (flipped) { - // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX - for (int index = 0; index < result; ++index) { - fT[1][index] = 1 - fT[1][index]; + if (left != right) { + const SkDPoint rightPt = { right, y }; + if ((t = line.nearPoint(rightPt)) >= 0) { + insert(t, (double) !flipped, rightPt); + } + for (int index = 0; index < 2; ++index) { + if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) { + insert((double) index, flipped ? 1 - t : t, line[index]); + } } } - return computePoints(line, result); + return fUsed; } -int SkIntersections::vertical(const SkDLine& line, double x) { +static int vertical_coincident(const SkDLine& line, double x) { double min = line[0].fX; double max = line[1].fX; if (min > max) { SkTSwap(min, max); } if (!precisely_between(min, x, max)) { - return fUsed = 0; + return 0; } if (AlmostEqualUlps(min, max)) { - fT[0][0] = 0; - fT[0][1] = 1; - return fUsed = 2; + return 2; } - fT[0][0] = (x - line[0].fX) / (line[1].fX - line[0].fX); - return fUsed = 1; + return 1; } -static bool checkEndPointV(const SkDPoint& end, double top, double bottom, - double x, bool flipped, double* tPtr) { - if (!between(top, end.fY, bottom) || !AlmostEqualUlps(x, end.fX)) { - return false; +static double vertical_intercept(const SkDLine& line, double x) { + return (x - line[0].fX) / (line[1].fX - line[0].fX); +} + +int SkIntersections::vertical(const SkDLine& line, double x) { + int verticalType = vertical_coincident(line, x); + if (verticalType == 1) { + fT[0][0] = vertical_intercept(line, x); + } else if (verticalType == 2) { + fT[0][0] = 0; + fT[0][1] = 1; } - double t = (end.fY - top) / (bottom - top); - SkASSERT(between(0, t, 1)); - *tPtr = flipped ? 1 - t : t; - return true; + return fUsed = verticalType; } int SkIntersections::vertical(const SkDLine& line, double top, double bottom, - double x, bool flipped) { + double x, bool flipped) { // see if end points intersect the opposite line double t; - if (checkEndPoint(x, top, line, &t, false)) { - insert(t, flipped, x, top); + SkDPoint topPt = { x, top }; + if ((t = line.exactPoint(topPt)) >= 0) { + insert(t, (double) flipped, topPt); } if (top != bottom) { - if (checkEndPoint(x, bottom,line, &t, false)) { - insert(t, !flipped, x, bottom); + SkDPoint bottomPt = { x, bottom }; + if ((t = line.exactPoint(bottomPt)) >= 0) { + insert(t, (double) !flipped, bottomPt); } for (int index = 0; index < 2; ++index) { - if (!checkEndPointV(line[index], top, bottom, x, flipped, &t)) { - continue; + if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) { + insert((double) index, flipped ? 1 - t : t, line[index]); } - insert( index, t, line[index]); } } - if (used() > 0) { - SkASSERT(fUsed <= 2); - return used(); // coincident lines are returned here + int result = vertical_coincident(line, x); + if (result == 1 && fUsed == 0) { + fT[0][0] = vertical_intercept(line, x); + double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY); + if (between(top, yIntercept, bottom)) { + fT[1][0] = (yIntercept - top) / (bottom - top); + if (flipped) { + // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY + for (int index = 0; index < result; ++index) { + fT[1][index] = 1 - fT[1][index]; + } + } + return computePoints(line, result); + } } - int result = vertical(line, x); - if (!result) { - return 0; + if (!fAllowNear && result != 2) { + return fUsed; } - SkASSERT(result == 1); - double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY); - if (!precisely_between(top, yIntercept, bottom)) { - return fUsed = 0; + if ((t = line.nearPoint(topPt)) >= 0) { + insert(t, (double) flipped, topPt); } - fT[1][0] = (yIntercept - top) / (bottom - top); - if (flipped) { - // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY - for (int index = 0; index < result; ++index) { - fT[1][index] = 1 - fT[1][index]; + if (top != bottom) { + SkDPoint bottomPt = { x, bottom }; + if ((t = line.nearPoint(bottomPt)) >= 0) { + insert(t, (double) !flipped, bottomPt); + } + for (int index = 0; index < 2; ++index) { + if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) { + insert((double) index, flipped ? 1 - t : t, line[index]); + } } } - return computePoints(line, result); + return fUsed; } // from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py diff --git a/src/pathops/SkDQuadIntersection.cpp b/src/pathops/SkDQuadIntersection.cpp index 54c8b4979b..124c7dab06 100644 --- a/src/pathops/SkDQuadIntersection.cpp +++ b/src/pathops/SkDQuadIntersection.cpp @@ -127,6 +127,7 @@ static bool add_intercept(const SkDQuad& q1, const SkDQuad& q2, double tMin, dou line[0] -= dxdy; line[1] += dxdy; SkIntersections rootTs; + rootTs.allowNear(false); int roots = rootTs.intersect(q1, line); if (roots == 0) { if (subDivide) { @@ -154,6 +155,7 @@ static bool is_linear_inner(const SkDQuad& q1, double t1s, double t1e, const SkD SkSTArray<kTestCount * 2, double, true> tsFound; for (size_t index = 0; index < kTestCount; ++index) { SkIntersections rootTs; + rootTs.allowNear(false); int roots = rootTs.intersect(q2, *testLines[index]); for (int idx2 = 0; idx2 < roots; ++idx2) { double t = rootTs[0][idx2]; diff --git a/src/pathops/SkDQuadLineIntersection.cpp b/src/pathops/SkDQuadLineIntersection.cpp index 98e38621e0..9df2dc248a 100644 --- a/src/pathops/SkDQuadLineIntersection.cpp +++ b/src/pathops/SkDQuadLineIntersection.cpp @@ -92,7 +92,12 @@ public: LineQuadraticIntersections(const SkDQuad& q, const SkDLine& l, SkIntersections* i) : quad(q) , line(l) - , intersections(i) { + , intersections(i) + , fAllowNear(true) { + } + + void allowNear(bool allow) { + fAllowNear = allow; } int intersectRay(double roots[2]) { @@ -126,7 +131,7 @@ public: } int intersect() { - addEndPoints(); + addExactEndPoints(); double rootVals[2]; int roots = intersectRay(rootVals); for (int index = 0; index < roots; ++index) { @@ -137,6 +142,9 @@ public: intersections->insert(quadT, lineT, pt); } } + if (fAllowNear) { + addNearEndPoints(); + } return intersections->used(); } @@ -151,7 +159,7 @@ public: } int horizontalIntersect(double axisIntercept, double left, double right, bool flipped) { - addHorizontalEndPoints(left, right, axisIntercept); + addExactHorizontalEndPoints(left, right, axisIntercept); double rootVals[2]; int roots = horizontalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { @@ -162,6 +170,9 @@ public: intersections->insert(quadT, lineT, pt); } } + if (fAllowNear) { + addNearHorizontalEndPoints(left, right, axisIntercept); + } if (flipped) { intersections->flip(); } @@ -179,7 +190,7 @@ public: } int verticalIntersect(double axisIntercept, double top, double bottom, bool flipped) { - addVerticalEndPoints(top, bottom, axisIntercept); + addExactVerticalEndPoints(top, bottom, axisIntercept); double rootVals[2]; int roots = verticalIntersect(axisIntercept, rootVals); for (int index = 0; index < roots; ++index) { @@ -190,6 +201,9 @@ public: intersections->insert(quadT, lineT, pt); } } + if (fAllowNear) { + addNearVerticalEndPoints(top, bottom, axisIntercept); + } if (flipped) { intersections->flip(); } @@ -198,73 +212,88 @@ public: protected: // add endpoints first to get zero and one t values exactly - void addEndPoints() { + void addExactEndPoints() { for (int qIndex = 0; qIndex < 3; qIndex += 2) { - bool foundEnd = false; - for (int lIndex = 0; lIndex < 2; lIndex++) { - if (quad[qIndex] == line[lIndex]) { - intersections->insert(qIndex >> 1, lIndex, line[lIndex]); - foundEnd = true; - } - } - if (foundEnd) { + double lineT = line.exactPoint(quad[qIndex]); + if (lineT < 0) { continue; } - // See if the quad end touches the line. - double dist = line.isLeft(quad[qIndex]); // this distance isn't cartesian - SkDVector lineLen = line[1] - line[0]; // the x/y magnitudes of the line - // compute the ULPS of the larger of the x/y deltas - double larger = SkTMax(SkTAbs(lineLen.fX), SkTAbs(lineLen.fY)); - if (!RoughlyEqualUlps(larger, larger + dist)) { // is the dist within ULPS tolerance? + double quadT = (double) (qIndex >> 1); + intersections->insert(quadT, lineT, quad[qIndex]); + } + } + + void addNearEndPoints() { + for (int qIndex = 0; qIndex < 3; qIndex += 2) { + double quadT = (double) (qIndex >> 1); + if (intersections->hasT(quadT)) { continue; } - double lineT = findLineT(qIndex >> 1); - if (!between(0, lineT, 1)) { + double lineT = line.nearPoint(quad[qIndex]); + if (lineT < 0) { continue; } - SkDPoint linePt = line.xyAtT(lineT); - if (linePt.approximatelyEqual(quad[qIndex])) { - intersections->insert(qIndex >> 1, lineT, quad[qIndex]); + intersections->insert(quadT, lineT, quad[qIndex]); + } + // FIXME: see if line end is nearly on quad + } + + void addExactHorizontalEndPoints(double left, double right, double y) { + for (int qIndex = 0; qIndex < 3; qIndex += 2) { + double lineT = SkDLine::ExactPointH(quad[qIndex], left, right, y); + if (lineT < 0) { + continue; } + double quadT = (double) (qIndex >> 1); + intersections->insert(quadT, lineT, quad[qIndex]); } } - void addHorizontalEndPoints(double left, double right, double y) { + void addNearHorizontalEndPoints(double left, double right, double y) { for (int qIndex = 0; qIndex < 3; qIndex += 2) { - if (!AlmostEqualUlps(quad[qIndex].fY, y)) { + double quadT = (double) (qIndex >> 1); + if (intersections->hasT(quadT)) { continue; } - double x = quad[qIndex].fX; - if (between(left, x, right)) { - double t = (x - left) / (right - left); - intersections->insert(qIndex >> 1, t, quad[qIndex]); + double lineT = SkDLine::NearPointH(quad[qIndex], left, right, y); + if (lineT < 0) { + continue; } + intersections->insert(quadT, lineT, quad[qIndex]); } + // FIXME: see if line end is nearly on quad } - void addVerticalEndPoints(double top, double bottom, double x) { + void addExactVerticalEndPoints(double top, double bottom, double x) { for (int qIndex = 0; qIndex < 3; qIndex += 2) { - if (!AlmostEqualUlps(quad[qIndex].fX, x)) { + double lineT = SkDLine::ExactPointV(quad[qIndex], top, bottom, x); + if (lineT < 0) { continue; } - double y = quad[qIndex].fY; - if (between(top, y, bottom)) { - double t = (y - top) / (bottom - top); - intersections->insert(qIndex >> 1, t, quad[qIndex]); + double quadT = (double) (qIndex >> 1); + intersections->insert(quadT, lineT, quad[qIndex]); + } + } + + void addNearVerticalEndPoints(double top, double bottom, double x) { + for (int qIndex = 0; qIndex < 3; qIndex += 2) { + double quadT = (double) (qIndex >> 1); + if (intersections->hasT(quadT)) { + continue; + } + double lineT = SkDLine::NearPointV(quad[qIndex], top, bottom, x); + if (lineT < 0) { + continue; } + intersections->insert(quadT, lineT, quad[qIndex]); } + // FIXME: see if line end is nearly on quad } double findLineT(double t) { SkDPoint xy = quad.xyAtT(t); double dx = line[1].fX - line[0].fX; double dy = line[1].fY - line[0].fY; -#if 0 - if (fabs(dx) > fabs(dy)) { - return (xy.fX - line[0].fX) / dx; - } - return (xy.fY - line[0].fY) / dy; -#else double dxT = (xy.fX - line[0].fX) / dx; double dyT = (xy.fY - line[0].fY) / dy; if (!between(FLT_EPSILON, dxT, 1 - FLT_EPSILON) && between(0, dyT, 1)) { @@ -274,7 +303,6 @@ protected: return dxT; } return fabs(dx) > fabs(dy) ? dxT : dyT; -#endif } static bool PinTs(double* quadT, double* lineT) { @@ -284,16 +312,8 @@ protected: if (!approximately_zero_or_more(*lineT)) { return false; } - if (precisely_less_than_zero(*quadT)) { - *quadT = 0; - } else if (precisely_greater_than_one(*quadT)) { - *quadT = 1; - } - if (precisely_less_than_zero(*lineT)) { - *lineT = 0; - } else if (precisely_greater_than_one(*lineT)) { - *lineT = 1; - } + *quadT = SkPinT(*quadT); + *lineT = SkPinT(*lineT); return true; } @@ -301,6 +321,7 @@ private: const SkDQuad& quad; const SkDLine& line; SkIntersections* intersections; + bool fAllowNear; }; // utility for pairs of coincident quads @@ -355,6 +376,7 @@ int SkIntersections::vertical(const SkDQuad& quad, double top, double bottom, do int SkIntersections::intersect(const SkDQuad& quad, const SkDLine& line) { LineQuadraticIntersections q(quad, line, this); + q.allowNear(fAllowNear); return q.intersect(); } diff --git a/src/pathops/SkIntersections.cpp b/src/pathops/SkIntersections.cpp index af6cc080ef..fe23316683 100644 --- a/src/pathops/SkIntersections.cpp +++ b/src/pathops/SkIntersections.cpp @@ -156,7 +156,7 @@ void SkIntersections::insertCoincidentPair(double s1, double e1, double s2, doub insertCoincident(e1, e2, endPt); } -int SkIntersections::insert(double one, double two, double x, double y) { +int SkIntersections::insert(double one, double two, const SkDPoint& pt) { if (fIsCoincident[0] == 3 && between(fT[0][0], one, fT[0][1])) { // For now, don't allow a mix of coincident and non-coincident intersections return -1; @@ -166,15 +166,17 @@ int SkIntersections::insert(double one, double two, double x, double y) { for (index = 0; index < fUsed; ++index) { double oldOne = fT[0][index]; double oldTwo = fT[1][index]; - if (roughly_equal(oldOne, one) && roughly_equal(oldTwo, two)) { + if (one == oldOne && two == oldTwo) { + return -1; + } + if (more_roughly_equal(oldOne, one) && more_roughly_equal(oldTwo, two)) { if ((precisely_zero(one) && !precisely_zero(oldOne)) || (precisely_equal(one, 1) && !precisely_equal(oldOne, 1)) || (precisely_zero(two) && !precisely_zero(oldTwo)) || (precisely_equal(two, 1) && !precisely_equal(oldTwo, 1))) { fT[0][index] = one; fT[1][index] = two; - fPt[index].fX = x; - fPt[index].fY = y; + fPt[index] = pt; } return -1; } @@ -196,18 +198,13 @@ int SkIntersections::insert(double one, double two, double x, double y) { fIsCoincident[0] += fIsCoincident[0] & ~((1 << index) - 1); fIsCoincident[1] += fIsCoincident[1] & ~((1 << index) - 1); } - fPt[index].fX = x; - fPt[index].fY = y; + fPt[index] = pt; fT[0][index] = one; fT[1][index] = two; ++fUsed; return index; } -int SkIntersections::insert(double one, double two, const SkDPoint& pt) { - return insert(one, two, pt.fX, pt.fY); -} - void SkIntersections::insertCoincident(double one, double two, const SkDPoint& pt) { int index = insertSwap(one, two, pt); int bit = 1 << index; diff --git a/src/pathops/SkIntersections.h b/src/pathops/SkIntersections.h index c0bb61fef0..de3d44cd70 100644 --- a/src/pathops/SkIntersections.h +++ b/src/pathops/SkIntersections.h @@ -45,6 +45,10 @@ public: SkDEBUGCODE(fDepth = i.fDepth); } + void allowNear(bool nearAllowed) { + fAllowNear = nearAllowed; + } + int cubic(const SkPoint a[4]) { SkDCubic cubic; cubic.set(a); @@ -88,6 +92,11 @@ public: return intersect(cubic, quad); } + bool hasT(double t) const { + SkASSERT(t == 0 || t == 1); + return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1); + } + int insertSwap(double one, double two, const SkDPoint& pt) { if (fSwap) { return insert(two, one, pt); @@ -96,14 +105,6 @@ public: } } - int insertSwap(double one, double two, double x, double y) { - if (fSwap) { - return insert(two, one, x, y); - } else { - return insert(one, two, x, y); - } - } - bool isCoincident(int index) { return (fIsCoincident[0] & 1 << index) != 0; } @@ -166,6 +167,7 @@ public: // leaves flip, swap alone void reset() { + fAllowNear = true; fUsed = 0; } @@ -204,7 +206,6 @@ public: int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]); // FIXME : does not respect swap int insert(double one, double two, const SkDPoint& pt); - int insert(double one, double two, double x, double y); // start if index == 0 : end if index == 1 void insertCoincident(double one, double two, const SkDPoint& pt); void insertCoincidentPair(double s1, double e1, double s2, double e2, @@ -248,6 +249,7 @@ private: double fT[2][9]; uint16_t fIsCoincident[2]; // bit arrays, one bit set for each coincident T unsigned char fUsed; + bool fAllowNear; bool fSwap; #ifdef SK_DEBUG int fDepth; diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h index 84f0eb10dd..456e6c0068 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -90,6 +90,20 @@ public: void calcCoincidentWinding(); + void checkEnds() { + if (!fContainsCurves) { + return; + } + int segmentCount = fSegments.count(); + for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { + SkOpSegment* segment = &fSegments[sIndex]; + if (segment->verb() == SkPath::kLine_Verb) { + continue; + } + fSegments[sIndex].checkEnds(); + } + } + void complete() { setBounds(); fContainsIntercepts = false; diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 8bd4cc275a..5b20749957 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -209,7 +209,7 @@ bool SkOpSegment::activeWinding(int index, int endIndex, int* maxWinding, int* s void SkOpSegment::addAngle(SkTArray<SkOpAngle, true>* anglesPtr, int start, int end) const { SkASSERT(start != end); SkOpAngle& angle = anglesPtr->push_back(); -#if DEBUG_ANGLE +#if 0 && DEBUG_ANGLE // computed pt and actual pt may differ by more than approx eq SkTArray<SkOpAngle, true>& angles = *anglesPtr; if (angles.count() > 1) { const SkOpSegment* aSeg = angles[0].segment(); @@ -1080,6 +1080,86 @@ bool SkOpSegment::bumpSpan(SkOpSpan* span, int windDelta, int oppDelta) { return false; } +// look to see if the curve end intersects an intermediary that intersects the other +void SkOpSegment::checkEnds() { +#if 1 + return; // FIXME: suspect we will need the code below to make intersections consistent +#else + SkTDArray<SkOpSpan> missingSpans; + int count = fTs.count(); + for (int index = 0; index < count; ++index) { + const SkOpSpan& span = fTs[index]; + const SkOpSegment* other = span.fOther; + const SkOpSpan* otherSpan = &other->fTs[span.fOtherIndex]; + double otherT = otherSpan->fT; + if (otherT != 0 && otherT != 1) { + continue; + } + int peekStart = span.fOtherIndex; + while (peekStart > 0) { + const SkOpSpan* peeker = &other->fTs[peekStart - 1]; + if (peeker->fT != otherT) { + break; + } + --peekStart; + } + int otherLast = other->fTs.count() - 1; + int peekLast = span.fOtherIndex; + while (peekLast < otherLast) { + const SkOpSpan* peeker = &other->fTs[peekLast + 1]; + if (peeker->fT != otherT) { + break; + } + ++peekLast; + } + if (peekStart == peekLast) { + continue; + } + double t = span.fT; + int tStart = index; + while (tStart > 0 && t == fTs[tStart - 1].fT) { + --tStart; + } + int tLast = index; + int last = count - 1; + while (tLast < last && t == fTs[tLast + 1].fT) { + ++tLast; + } + for (int peekIndex = peekStart; peekIndex <= peekLast; ++peekIndex) { + if (peekIndex == span.fOtherIndex) { + continue; + } + const SkOpSpan& peekSpan = other->fTs[peekIndex]; + SkOpSegment* match = peekSpan.fOther; + const double matchT = peekSpan.fOtherT; + for (int tIndex = tStart; tIndex <= tLast; ++tIndex) { + const SkOpSpan& tSpan = fTs[tIndex]; + if (tSpan.fOther == match && tSpan.fOtherT == matchT) { + goto nextPeeker; + } + } + // this segment is missing a entry that the other contains + // remember so we can add the missing one and recompute the indices + SkOpSpan* missing = missingSpans.append(); + missing->fT = t; + missing->fOther = match; + missing->fOtherT = matchT; + missing->fPt = peekSpan.fPt; + } +nextPeeker: + ; + } + int missingCount = missingSpans.count(); + for (int index = 0; index < missingCount; ++index) { + const SkOpSpan& missing = missingSpans[index]; + addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing.fPt); + } + if (missingCount > 0) { + fixOtherTIndex(); + } +#endif +} + bool SkOpSegment::equalPoints(int greaterTIndex, int lesserTIndex) { SkASSERT(greaterTIndex >= lesserTIndex); double greaterT = fTs[greaterTIndex].fT; diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 3cbd29e77e..7e5e644f1d 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -254,6 +254,7 @@ public: const SkPoint& oPt); int addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT); bool betweenTs(int lesser, double testT, int greater) const; + void checkEnds(); int computeSum(int startIndex, int endIndex, bool binary); int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, double mid, bool opp, bool current) const; diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index 5a30c3a98e..9a92b00acd 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -344,6 +344,16 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bo return current; } +void CheckEnds(SkTArray<SkOpContour*, true>* contourList) { + // it's hard to determine if the end of a cubic or conic nearly intersects another curve. + // instead, look to see if the connecting curve intersected at that same end. + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->checkEnds(); + } +} + void FixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) { int contourCount = (*contourList).count(); for (int cTest = 0; cTest < contourCount; ++cTest) { diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h index 569edb7e32..4ba4af2300 100644 --- a/src/pathops/SkPathOpsCommon.h +++ b/src/pathops/SkPathOpsCommon.h @@ -13,6 +13,7 @@ class SkPathWriter; void Assemble(const SkPathWriter& path, SkPathWriter* simple); +void CheckEnds(SkTArray<SkOpContour*, true>* contourList); // FIXME: find chase uses insert, so it can't be converted to SkTArray yet SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex); SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, bool* firstContour, diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index 5484147c3a..05fe241e0f 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -103,10 +103,10 @@ extern int gDebugMaxWindValue; DEBUG_SORT_SINGLE | DEBUG_PATH_CONSTRUCTION) #if DEBUG_AS_C_CODE -#define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}" -#define QUAD_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}" -#define LINE_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}}" -#define PT_DEBUG_STR "{{%1.17g,%1.17g}}" +#define CUBIC_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}" +#define QUAD_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}" +#define LINE_DEBUG_STR "{{%1.9g,%1.9g}, {%1.9g,%1.9g}}" +#define PT_DEBUG_STR "{{%1.9g,%1.9g}}" #else #define CUBIC_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" #define QUAD_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" diff --git a/src/pathops/SkPathOpsLine.cpp b/src/pathops/SkPathOpsLine.cpp index b7c91c991d..47c0565b69 100644 --- a/src/pathops/SkPathOpsLine.cpp +++ b/src/pathops/SkPathOpsLine.cpp @@ -41,8 +41,99 @@ double SkDLine::isLeft(const SkDPoint& pt) const { return p0.cross(p2); } +// OPTIMIZE: assert if t is 0 or 1 (caller shouldn't pass only 0/1) SkDPoint SkDLine::xyAtT(double t) const { double one_t = 1 - t; SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY }; return result; } + +double SkDLine::exactPoint(const SkDPoint& xy) const { + if (xy == fPts[0]) { // do cheapest test first + return 0; + } + if (xy == fPts[1]) { + return 1; + } + return -1; +} + +double SkDLine::nearPoint(const SkDPoint& xy) const { + if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX) + || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) { + return -1; + } + // project a perpendicular ray from the point to the line; find the T on the line + SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line + double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay + SkDVector ab0 = xy - fPts[0]; + double numer = len.fX * ab0.fX + ab0.fY * len.fY; + if (!between(0, numer, denom)) { + return -1; + } + double t = numer / denom; + SkDPoint realPt = xyAtT(t); + SkDVector distU = xy - realPt; + double distSq = distU.fX * distU.fX + distU.fY * distU.fY; + double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? + // find the ordinal in the original line with the largest unsigned exponent + double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); + double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); + largest = SkTMax(largest, -tiniest); + if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? + return -1; + } + t = SkPinT(t); + SkASSERT(between(0, t, 1)); + return t; +} + +double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) { + if (xy.fY == y) { + if (xy.fX == left) { + return 0; + } + if (xy.fX == right) { + return 1; + } + } + return -1; +} + +double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) { + if (!AlmostEqualUlps(xy.fY, y)) { + return -1; + } + if (!AlmostBetweenUlps(left, xy.fX, right)) { + return -1; + } + double t = (xy.fX - left) / (right - left); + t = SkPinT(t); + SkASSERT(between(0, t, 1)); + return t; +} + +double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) { + if (xy.fX == x) { + if (xy.fY == top) { + return 0; + } + if (xy.fY == bottom) { + return 1; + } + } + return -1; +} + +double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) { + if (!AlmostEqualUlps(xy.fX, x)) { + return -1; + } + if (!AlmostBetweenUlps(top, xy.fY, bottom)) { + return -1; + } + double t = (xy.fY - top) / (bottom - top); + t = SkPinT(t); + SkASSERT(between(0, t, 1)); + return t; +} diff --git a/src/pathops/SkPathOpsLine.h b/src/pathops/SkPathOpsLine.h index 34bb6587d3..c5ac7fdb09 100644 --- a/src/pathops/SkPathOpsLine.h +++ b/src/pathops/SkPathOpsLine.h @@ -12,21 +12,28 @@ struct SkDLine { SkDPoint fPts[2]; + const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 2); return fPts[n]; } + SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 2); return fPts[n]; } + void set(const SkPoint pts[2]) { fPts[0] = pts[0]; fPts[1] = pts[1]; } - const SkDPoint& operator[](int n) const { SkASSERT(n >= 0 && n < 2); return fPts[n]; } - SkDPoint& operator[](int n) { SkASSERT(n >= 0 && n < 2); return fPts[n]; } - - double isLeft(const SkDPoint& pt) const; - SkDLine subDivide(double t1, double t2) const; static SkDLine SubDivide(const SkPoint a[2], double t1, double t2) { SkDLine line; line.set(a); return line.subDivide(t1, t2); } + + double exactPoint(const SkDPoint& xy) const; + static double ExactPointH(const SkDPoint& xy, double left, double right, double y); + static double ExactPointV(const SkDPoint& xy, double top, double bottom, double x); + double isLeft(const SkDPoint& pt) const; + double nearPoint(const SkDPoint& xy) const; + static double NearPointH(const SkDPoint& xy, double left, double right, double y); + static double NearPointV(const SkDPoint& xy, double top, double bottom, double x); + SkDLine subDivide(double t1, double t2) const; SkDPoint xyAtT(double t) const; private: SkDVector tangent() const { return fPts[0] - fPts[1]; } diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp index 0df4859cdf..71efeeea8c 100644 --- a/src/pathops/SkPathOpsOp.cpp +++ b/src/pathops/SkPathOpsOp.cpp @@ -299,6 +299,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) { SkOpContour::debugShowWindingValues(contourList); #endif FixOtherTIndex(&contourList); + CheckEnds(&contourList); SortSegments(&contourList); #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY DebugShowActiveSpans(contourList); diff --git a/src/pathops/SkPathOpsQuad.cpp b/src/pathops/SkPathOpsQuad.cpp index 3cbc28abf4..636e3854fd 100644 --- a/src/pathops/SkPathOpsQuad.cpp +++ b/src/pathops/SkPathOpsQuad.cpp @@ -164,6 +164,7 @@ SkDVector SkDQuad::dxdyAtT(double t) const { return result; } +// OPTIMIZE: assert if caller passes in t == 0 / t == 1 ? SkDPoint SkDQuad::xyAtT(double t) const { double one_t = 1 - t; double a = one_t * one_t; diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp index fd40c38503..488778904f 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -185,6 +185,7 @@ bool Simplify(const SkPath& path, SkPath* result) { // eat through coincident edges CoincidenceCheck(&contourList, 0); FixOtherTIndex(&contourList); + CheckEnds(&contourList); SortSegments(&contourList); #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY DebugShowActiveSpans(contourList); diff --git a/src/pathops/SkPathOpsTypes.cpp b/src/pathops/SkPathOpsTypes.cpp index 999e1b215d..a076d155f2 100644 --- a/src/pathops/SkPathOpsTypes.cpp +++ b/src/pathops/SkPathOpsTypes.cpp @@ -16,8 +16,7 @@ static bool equal_ulps(float A, float B, int epsilon) { floatIntA.fFloat = A; floatIntB.fFloat = B; // Different signs means they do not match. - if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) - { + if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { // Check for equality to make sure +0 == -0 return A == B; } @@ -26,6 +25,18 @@ static bool equal_ulps(float A, float B, int epsilon) { return ulpsDiff <= epsilon; } +static bool less_ulps(float A, float B, int epsilon) { + SkFloatIntUnion floatIntA, floatIntB; + floatIntA.fFloat = A; + floatIntB.fFloat = B; + // Check different signs with float epsilon since we only care if they're both close to 0. + if ((floatIntA.fSignBitInt < 0) != (floatIntB.fSignBitInt < 0)) { + return A <= B + FLT_EPSILON * epsilon; + } + // Find the difference in ULPs. + return floatIntA.fSignBitInt <= floatIntB.fSignBitInt + epsilon; +} + bool AlmostEqualUlps(float A, float B) { const int UlpsEpsilon = 16; return equal_ulps(A, B, UlpsEpsilon); @@ -36,6 +47,12 @@ bool RoughlyEqualUlps(float A, float B) { return equal_ulps(A, B, UlpsEpsilon); } +bool AlmostBetweenUlps(float a, float b, float c) { + const int UlpsEpsilon = 1; + return a <= c ? less_ulps(a, b, UlpsEpsilon) && less_ulps(b, c, UlpsEpsilon) + : less_ulps(b, a, UlpsEpsilon) && less_ulps(c, b, UlpsEpsilon); +} + // cube root approximation using bit hack for 64-bit float // adapted from Kahan's cbrt static double cbrt_5d(double d) { diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h index 20641d3345..c988691e26 100644 --- a/src/pathops/SkPathOpsTypes.h +++ b/src/pathops/SkPathOpsTypes.h @@ -33,6 +33,11 @@ inline bool RoughlyEqualUlps(double A, double B) { return RoughlyEqualUlps(SkDoubleToScalar(A), SkDoubleToScalar(B)); } +bool AlmostBetweenUlps(float a, float b, float c); +inline bool AlmostBetweenUlps(double A, double B, double C) { + return AlmostBetweenUlps(SkDoubleToScalar(A), SkDoubleToScalar(B), SkDoubleToScalar(C)); +} + // FLT_EPSILON == 1.19209290E-07 == 1 / (2 ^ 23) // DBL_EPSILON == 2.22045e-16 const double FLT_EPSILON_CUBED = FLT_EPSILON * FLT_EPSILON * FLT_EPSILON; @@ -260,4 +265,8 @@ inline int SkDSideBit(double x) { return 1 << SKDSide(x); } +inline double SkPinT(double t) { + return precisely_less_than_zero(t) ? 0 : precisely_greater_than_one(t) ? 1 : t; +} + #endif diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp index e00ba1674c..db8e5758f5 100644 --- a/tests/PathOpsCubicIntersectionTest.cpp +++ b/tests/PathOpsCubicIntersectionTest.cpp @@ -163,6 +163,39 @@ static const SkDCubic testSet[] = { const size_t testSetCount = SK_ARRAY_COUNT(testSet); static const SkDCubic newTestSet[] = { +{{{1.0516976506771041, 2.9684399028541346 },
+ {1.0604363140895228, 2.9633503074444141 },
+ {1.0692548215065762, 2.9580354426587459 },
+ {1.0781560339512140, 2.9525043684031349 }}},
+
+{{{1.0523038101345104, 2.9523755204833737 },
+ {1.0607035288264237, 2.9580853881628375 },
+ {1.0690530472271964, 2.9633896794787749 },
+ {1.0773566568712512, 2.9682969775000219 }}},
+ +{{{1.0386522625066592, 2.9759024812329078 },
+ {1.0559713690392631, 2.9661782500838885 },
+ {1.0736041309019990, 2.9555348259177858 },
+ {1.0915734362784633, 2.9440446879826569 }}},
+
+{{{1.0396670794879301, 2.9435062123457261 },
+ {1.0565690546812769, 2.9557413250983462 },
+ {1.0732616463413533, 2.9663369676594282 },
+ {1.0897791867435489, 2.9753618045797472 }}},
+ +{{{0.8685656183311091, 3.0409266475785208 },
+ {0.99189542936395292, 3.0212163698184424 },
+ {1.1302108367493320, 2.9265646471747306 },
+ {1.2952305904872474, 2.7940808546473788 }}},
+
+{{{0.85437872843682727, 2.7536036928549055 },
+ {1.0045584590592620, 2.9493041024831705 },
+ {1.1336998329885613, 3.0248027987251747 },
+ {1.2593809752247314, 3.0152560315809107 }}},
+ +{{{0, 1}, {1, 6}, {1, 0}, {6, 2}}},
+{{{0, 1}, {2, 6}, {1, 0}, {6, 1}}},
+ {{{134,11414}, {131.990234375,11414}, {130.32666015625,11415.482421875}, {130.04275512695312,11417.4130859375}}}, {{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}}, @@ -297,11 +330,6 @@ static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) { oneOff(reporter, cubic1, cubic2); } -static void oneOffTest(skiatest::Reporter* reporter) { - newOneOff(reporter, 0, 1); - oneOff(reporter, 14, 16); -} - static void oneOffTests(skiatest::Reporter* reporter) { for (size_t outer = 0; outer < testSetCount - 1; ++outer) { for (size_t inner = outer + 1; inner < testSetCount; ++inner) { @@ -515,8 +543,11 @@ static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) { } } +static void PathOpsCubicIntersectionOneOffTest(skiatest::Reporter* reporter) { + newOneOff(reporter, 6, 7); +} + static void PathOpsCubicIntersectionTest(skiatest::Reporter* reporter) { - oneOffTest(reporter); oneOffTests(reporter); cubicIntersectionSelfTest(reporter); standardTestCases(reporter); @@ -526,3 +557,5 @@ static void PathOpsCubicIntersectionTest(skiatest::Reporter* reporter) { #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionTest) + +DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionOneOffTest) diff --git a/tests/PathOpsCubicLineIntersectionTest.cpp b/tests/PathOpsCubicLineIntersectionTest.cpp index 29c04ae7b8..245f8a6674 100644 --- a/tests/PathOpsCubicLineIntersectionTest.cpp +++ b/tests/PathOpsCubicLineIntersectionTest.cpp @@ -14,6 +14,10 @@ static struct lineCubic { SkDCubic cubic; SkDLine line; } lineCubicTests[] = { +#if 0 + {{{{258, 122}, {260.761414, 122}, { 263, 124.238579}, {263, 127}}}, + {{{259.82843, 125.17157}, {261.535522, 123.46447}}}}, +#endif {{{{1006.6951293945312,291}, {1023.263671875,291}, {1033.8402099609375,304.43145751953125}, {1030.318359375,321}}}, {{{979.30487060546875,561}, {1036.695068359375,291}}}}, @@ -67,7 +71,7 @@ static void PathOpsCubicLineIntersectionTest(skiatest::Reporter* reporter) { } } -static void PathOpsCubicLineIntersectionTestOne(skiatest::Reporter* reporter) { +static void PathOpsCubicLineIntersectionOneOffTest(skiatest::Reporter* reporter) { int iIndex = 0; testOne(reporter, iIndex); const SkDCubic& cubic = lineCubicTests[iIndex].cubic; @@ -95,4 +99,4 @@ static void PathOpsCubicLineIntersectionTestOne(skiatest::Reporter* reporter) { #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsCubicLineIntersectionTest) -DEFINE_TESTCLASS_SHORT(PathOpsCubicLineIntersectionTestOne) +DEFINE_TESTCLASS_SHORT(PathOpsCubicLineIntersectionOneOffTest) diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp index 7a7dcb3759..93280d746d 100644 --- a/tests/PathOpsExtendedTest.cpp +++ b/tests/PathOpsExtendedTest.cpp @@ -52,24 +52,54 @@ static const char* gFillTypeStr[] = { "kInverseEvenOdd_FillType" }; +static void output_scalar(SkScalar num) { + if (num == (int) num) { + SkDebugf("%d", (int) num); + } else { + SkString str; + str.printf("%1.9g", num); + int width = str.size(); + const char* cStr = str.c_str(); + while (cStr[width - 1] == '0') { + --width; + } + str.resize(width); + SkDebugf("%sf", str.c_str()); + } +} + +static void output_points(const SkPoint* pts, int count) { + for (int index = 0; index < count; ++index) { + output_scalar(pts[index].fX); + SkDebugf(", "); + output_scalar(pts[index].fY); + if (index + 1 < count) { + SkDebugf(", "); + } + } + SkDebugf(");\n"); +} + static void showPathContours(SkPath::RawIter& iter, const char* pathName) { uint8_t verb; SkPoint pts[4]; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { switch (verb) { case SkPath::kMove_Verb: - SkDebugf(" %s.moveTo(%#1.9gf, %#1.9gf);\n", pathName, pts[0].fX, pts[0].fY); + SkDebugf(" %s.moveTo(", pathName); + output_points(&pts[0], 1); continue; case SkPath::kLine_Verb: - SkDebugf(" %s.lineTo(%#1.9gf, %#1.9gf);\n", pathName, pts[1].fX, pts[1].fY); + SkDebugf(" %s.lineTo(", pathName); + output_points(&pts[1], 1); break; case SkPath::kQuad_Verb: - SkDebugf(" %s.quadTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", pathName, - pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); + SkDebugf(" %s.quadTo(", pathName); + output_points(&pts[1], 2); break; case SkPath::kCubic_Verb: - SkDebugf(" %s.cubicTo(%#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf, %#1.9gf);\n", - pathName, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY); + SkDebugf(" %s.cubicTo(", pathName); + output_points(&pts[1], 3); break; case SkPath::kClose_Verb: SkDebugf(" %s.close();\n", pathName); @@ -116,24 +146,40 @@ static void showPathData(const SkPath& path) { SkPath::RawIter iter(path); uint8_t verb; SkPoint pts[4]; + SkPoint firstPt, lastPt; + bool firstPtSet = false; + bool lastPtSet = true; while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { switch (verb) { case SkPath::kMove_Verb: + firstPt = pts[0]; + firstPtSet = true; continue; case SkPath::kLine_Verb: SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY); + lastPt = pts[1]; + lastPtSet = true; break; case SkPath::kQuad_Verb: SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); + lastPt = pts[2]; + lastPtSet = true; break; case SkPath::kCubic_Verb: SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", pts[0].fX, pts[0].fY, pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY, pts[3].fX, pts[3].fY); + lastPt = pts[3]; + lastPtSet = true; break; case SkPath::kClose_Verb: + if (firstPtSet && lastPtSet && firstPt != lastPt) { + SkDebugf("{{%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", lastPt.fX, lastPt.fY, + firstPt.fX, firstPt.fY); + } + firstPtSet = lastPtSet = false; break; default: SkDEBUGFAIL("bad verb"); @@ -521,6 +567,7 @@ bool testPathOp(skiatest::Reporter* reporter, const SkPath& a, const SkPath& b, const SkPathOp shapeOp, const char* testName) { #if DEBUG_SHOW_TEST_NAME if (testName == NULL) { + SkDebugf("\n"); showPathData(a); showOp(shapeOp); showPathData(b); diff --git a/tests/PathOpsLineParametetersTest.cpp b/tests/PathOpsLineParametetersTest.cpp index 3b223ae89f..c8f8be7699 100644 --- a/tests/PathOpsLineParametetersTest.cpp +++ b/tests/PathOpsLineParametetersTest.cpp @@ -68,7 +68,7 @@ static void PathOpsLineParametersTest(skiatest::Reporter* reporter) { if (AlmostEqualUlps(fabs(normalizedDistance[inner]), answers[index][inner])) { continue; } - SkDebugf("%s [%d,%d] normalizedDistance:%1.10g != answer:%g\n", + SkDebugf("%s [%d,%d] normalizedDistance:%1.9g != answer:%g\n", __FUNCTION__, static_cast<int>(index), (int)inner, normalizedDistance[inner], answers[index][inner]); REPORTER_ASSERT(reporter, 0); diff --git a/tests/PathOpsOpCubicThreadedTest.cpp b/tests/PathOpsOpCubicThreadedTest.cpp index 3448ee94cb..0ccb89d8e8 100644 --- a/tests/PathOpsOpCubicThreadedTest.cpp +++ b/tests/PathOpsOpCubicThreadedTest.cpp @@ -9,6 +9,9 @@ static void testOpCubicsMain(PathOpsThreadState* data) { +#if DEBUG_SHOW_TEST_NAME + strncpy(DEBUG_FILENAME_STRING, "", DEBUG_FILENAME_STRING_LENGTH); +#endif SkASSERT(data); PathOpsThreadState& state = *data; char pathStr[1024]; // gdb: set print elements 400 diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index e06bc8f57c..098b3864fc 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -1733,9 +1733,116 @@ static void skphealth_com76(skiatest::Reporter* reporter) { #endif } +static void skpahrefs_com88(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(1099.82886f, 7.17117119f);
+ path.lineTo(1099.12134f, 7.87867832f);
+ path.cubicTo(1099.66418f, 8.42157173f, 1100.00000f, 9.17157173f, 1100.00000f, 10.0000000f);
+ path.lineTo(1100.00000f, 28.0000000f);
+ path.cubicTo(1100.00000f, 29.6568546f, 1098.65686f, 31.0000000f, 1097.00000f, 31.0000000f);
+ path.lineTo(1088.00000f, 31.0000000f);
+ path.lineTo(1088.00000f, 32.0000000f);
+ path.lineTo(1097.00000f, 32.0000000f);
+ path.quadTo(1098.65686f, 32.0000000f, 1099.82886f, 30.8288002f);
+ path.quadTo(1101.00000f, 29.6568546f, 1101.00000f, 28.0000000f);
+ path.lineTo(1101.00000f, 10.0000000f);
+ path.quadTo(1101.00000f, 8.34314537f, 1099.82886f, 7.17119980f);
+ path.lineTo(1099.82886f, 7.17117119f);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1101.00000f, 6.00000000f);
+ pathB.lineTo(1088.00000f, 6.00000000f);
+ pathB.lineTo(1088.00000f, 19.0000000f);
+ pathB.lineTo(1101.00000f, 32.0000000f);
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+ +static void skpahrefs_com29(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(1037.17114f, 7.17119980f);
+ path.quadTo(1038.34314f, 6.00000000f, 1040.00000f, 6.00000000f);
+ path.lineTo(1074.00000f, 6.00000000f);
+ path.lineTo(1074.00000f, 32.0000000f);
+ path.lineTo(1040.00000f, 32.0000000f);
+ path.quadTo(1038.34314f, 32.0000000f, 1037.17114f, 30.8288002f);
+ path.quadTo(1036.00000f, 29.6568546f, 1036.00000f, 28.0000000f);
+ path.lineTo(1036.00000f, 10.0000000f);
+ path.quadTo(1036.00000f, 8.34314537f, 1037.17114f, 7.17119980f);
+ path.close();
+ path.moveTo(1037.00000f, 10.0000000f);
+ path.cubicTo(1037.00000f, 8.34314537f, 1038.34314f, 7.00000000f, 1040.00000f, 7.00000000f);
+ path.lineTo(1073.00000f, 7.00000000f);
+ path.lineTo(1073.00000f, 31.0000000f);
+ path.lineTo(1040.00000f, 31.0000000f);
+ path.cubicTo(1038.34314f, 31.0000000f, 1037.00000f, 29.6568546f, 1037.00000f, 28.0000000f);
+ path.lineTo(1037.00000f, 10.0000000f);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(1036.00000f, 32.0000000f);
+ pathB.lineTo(1049.00000f, 19.0000000f);
+ pathB.lineTo(1073.00000f, 31.0000000f);
+ pathB.lineTo(1074.00000f, 32.0000000f);
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+ +static void cubicOp85d(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.moveTo(0,1);
+ path.cubicTo(1,6, 1,0, 6,2);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(0,1);
+ pathB.cubicTo(2,6, 1,0, 6,1);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kDifference_PathOp);
+} + +#if 0 // FIXME +// this fails because the pair of nearly coincident cubics intersect at the ends +// but the line connected to one of the cubics at the same point does not intersect +// the other +static void skpkkiste_to98(skiatest::Reporter* reporter) {
+ SkPath path;
+ path.setFillType(SkPath::kEvenOdd_FillType);
+ path.moveTo(96, 122);
+ path.cubicTo(94.6192932f, 122, 93.3692932f, 122.559647f, 92.4644699f, 123.46447f);
+ path.lineTo(94.1715698f, 125.17157f);
+ path.cubicTo(94.8954315f, 124.447708f, 95.8954315f, 124, 97, 124);
+ path.lineTo(257, 124);
+ path.cubicTo(258.104553f, 124, 259.104584f, 124.447708f, 259.82843f, 125.17157f);
+ path.lineTo(261.535522f, 123.46447f);
+ path.cubicTo(260.630707f, 122.559647f, 259.380707f, 122, 258, 122);
+ path.lineTo(96, 122);
+ path.close();
+ SkPath pathB;
+ pathB.setFillType(SkPath::kWinding_FillType);
+ pathB.moveTo(258, 122);
+ pathB.cubicTo(260.761414f, 122, 263, 124.238579f, 263, 127);
+ pathB.lineTo(263, 284);
+ pathB.cubicTo(263, 286.761414f, 260.761414f, 289, 258, 289);
+ pathB.lineTo(96, 289);
+ pathB.cubicTo(93.2385788f, 289, 91, 286.761414f, 91, 284);
+ pathB.lineTo(91, 127);
+ pathB.cubicTo(91, 124.238579f, 93.2385788f, 122, 96, 122);
+ pathB.lineTo(258, 122);
+ pathB.close();
+ testPathOp(reporter, path, pathB, kIntersect_PathOp);
+}
+#endif + static void (*firstTest)(skiatest::Reporter* ) = 0; static struct TestDesc tests[] = { +// TEST(skpkkiste_to98), + TEST(skpahrefs_com29), + TEST(cubicOp85d), + TEST(skpahrefs_com88), TEST(skphealth_com76), TEST(skpancestry_com1), TEST(skpbyte_com1), diff --git a/tests/PathOpsQuadIntersectionTest.cpp b/tests/PathOpsQuadIntersectionTest.cpp index 4bb0b343f0..c454b4d81b 100644 --- a/tests/PathOpsQuadIntersectionTest.cpp +++ b/tests/PathOpsQuadIntersectionTest.cpp @@ -50,6 +50,9 @@ static void standardTestCases(skiatest::Reporter* reporter) { } static const SkDQuad testSet[] = { + {{{0.647069409,2.97691634}, {0.946860918,3.17625612}, {1.46875407,2.65105457}}},
+ {{{0,1}, {0.723699095,2.82756208}, {1.08907197,2.97497449}}},
+ {{{131.37418,11414.9825}, {130.28798,11415.9328}, {130.042755,11417.4131}}}, {{{130.585787,11418.4142}, {130.021447,11417.8498}, {130,11417}}}, @@ -264,7 +267,7 @@ static void oneOffTest1(skiatest::Reporter* reporter, size_t outer, size_t inner } } -static void QuadraticIntersection_OneOffTest(skiatest::Reporter* reporter) { +static void PathOpsQuadIntersectionOneOffTest(skiatest::Reporter* reporter) { oneOffTest1(reporter, 0, 1); } @@ -471,10 +474,10 @@ static void PathOpsQuadIntersectionTest(skiatest::Reporter* reporter) { standardTestCases(reporter); if (false) QuadraticIntersection_IntersectionFinder(); if (false) QuadraticIntersection_PointFinder(); - if (false) QuadraticIntersection_OneOffTest(reporter); } #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionTest) -DEFINE_TESTCLASS_SHORT(QuadraticIntersection_OneOffTest) + +DEFINE_TESTCLASS_SHORT(PathOpsQuadIntersectionOneOffTest) diff --git a/tests/PathOpsQuadLineIntersectionTest.cpp b/tests/PathOpsQuadLineIntersectionTest.cpp index 16153404c4..4227ee5277 100644 --- a/tests/PathOpsQuadLineIntersectionTest.cpp +++ b/tests/PathOpsQuadLineIntersectionTest.cpp @@ -58,11 +58,13 @@ static struct oneLineQuad { SkDQuad quad; SkDLine line; } oneOffs[] = { + {{{{1101, 10}, {1101, 8.3431453704833984}, {1099.828857421875, 7.1711997985839844}}}, + {{{1099.828857421875,7.1711711883544922}, {1099.121337890625,7.8786783218383789}}}}, {{{{973, 507}, {973, 508.24264526367187}, {972.12158203125, 509.12161254882812}}}, {{{930, 467}, {973, 510}}}}, {{{{369.848602, 145.680267}, {382.360413, 121.298294}, {406.207703, 121.298294}}}, - {{{406.207703, 121.298294}, {348.781738, 123.864815}}}} - }; + {{{406.207703, 121.298294}, {348.781738, 123.864815}}}}, +}; static size_t oneOffs_count = SK_ARRAY_COUNT(oneOffs); @@ -83,8 +85,11 @@ static void testOneOffs(skiatest::Reporter* reporter) { } } -static void PathOpsQuadLineIntersectionTest(skiatest::Reporter* reporter) { +static void PathOpsQuadLineIntersectionTestOne(skiatest::Reporter* reporter) { testOneOffs(reporter); +} + +static void PathOpsQuadLineIntersectionTest(skiatest::Reporter* reporter) { for (size_t index = 0; index < lineQuadTests_count; ++index) { int iIndex = static_cast<int>(index); const SkDQuad& quad = lineQuadTests[index].quad; @@ -131,3 +136,5 @@ static void PathOpsQuadLineIntersectionTest(skiatest::Reporter* reporter) { #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsQuadLineIntersectionTest) + +DEFINE_TESTCLASS_SHORT(PathOpsQuadLineIntersectionTestOne) diff --git a/tests/PathOpsSkpClipTest.cpp b/tests/PathOpsSkpClipTest.cpp index f46ad976d5..f9d33e16f8 100644 --- a/tests/PathOpsSkpClipTest.cpp +++ b/tests/PathOpsSkpClipTest.cpp @@ -88,7 +88,7 @@ static void testOne(const SkString& filename) { SkDELETE(pic); } -const char skipBefore[] = "http___health_com.skp"; +const char skipBefore[] = "http___kkiste_to.skp"; static void PathOpsSkpClipTest(skiatest::Reporter* reporter) { SkOSFile::Iter iter(pictDir, "skp"); @@ -138,7 +138,7 @@ static void PathOpsSkpClipThreadedTest(skiatest::Reporter* reporter) { testRunner.render(); } -static void PathOpsSkpClipTestOne(skiatest::Reporter* reporter) { +static void PathOpsSkpClipOneOffTest(skiatest::Reporter* reporter) { SkString filename(skipBefore); testOne(filename); } @@ -146,6 +146,6 @@ static void PathOpsSkpClipTestOne(skiatest::Reporter* reporter) { #include "TestClassDef.h" DEFINE_TESTCLASS_SHORT(PathOpsSkpClipTest) -DEFINE_TESTCLASS_SHORT(PathOpsSkpClipTestOne) +DEFINE_TESTCLASS_SHORT(PathOpsSkpClipOneOffTest) DEFINE_TESTCLASS_SHORT(PathOpsSkpClipThreadedTest) |