diff options
26 files changed, 305 insertions, 51 deletions
diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp index 983c4e3002..256529c939 100644 --- a/experimental/Intersection/CubicIntersection_Test.cpp +++ b/experimental/Intersection/CubicIntersection_Test.cpp @@ -45,11 +45,11 @@ void CubicIntersection_Test() { double tt2 = tIntersections.fT[1][pt]; double tx2, ty2; xy_at_t(cubic2, tt2, tx2, ty2); - if (!approximately_equal(tx1, tx2)) { + if (!AlmostEqualUlps(tx1, tx2)) { printf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); } - if (!approximately_equal(ty1, ty2)) { + if (!AlmostEqualUlps(ty1, ty2)) { printf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n", __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); } diff --git a/experimental/Intersection/CubicParameterization.cpp b/experimental/Intersection/CubicParameterization.cpp index 2bae8b6dcd..e44b121ddb 100644 --- a/experimental/Intersection/CubicParameterization.cpp +++ b/experimental/Intersection/CubicParameterization.cpp @@ -491,8 +491,7 @@ bool implicit_matches(const Cubic& one, const Cubic& two) { if (first == index) { continue; } - if (!approximately_equal(p1[index] * p2[first], - p1[first] * p2[index])) { + if (!AlmostEqualUlps(p1[index] * p2[first], p1[first] * p2[index])) { return false; } } diff --git a/experimental/Intersection/CubicReduceOrder.cpp b/experimental/Intersection/CubicReduceOrder.cpp index 294d18c440..d1775d89f2 100644 --- a/experimental/Intersection/CubicReduceOrder.cpp +++ b/experimental/Intersection/CubicReduceOrder.cpp @@ -69,13 +69,13 @@ static int check_quadratic(const Cubic& cubic, Cubic& reduction) { double dx10 = cubic[1].x - cubic[0].x; double dx23 = cubic[2].x - cubic[3].x; double midX = cubic[0].x + dx10 * 3 / 2; - if (!approximately_equal(midX - cubic[3].x, dx23 * 3 / 2)) { + if (!AlmostEqualUlps(midX - cubic[3].x, dx23 * 3 / 2)) { return 0; } double dy10 = cubic[1].y - cubic[0].y; double dy23 = cubic[2].y - cubic[3].y; double midY = cubic[0].y + dy10 * 3 / 2; - if (!approximately_equal(midY - cubic[3].y, dy23 * 3 / 2)) { + if (!AlmostEqualUlps(midY - cubic[3].y, dy23 * 3 / 2)) { return 0; } reduction[0] = cubic[0]; @@ -92,7 +92,7 @@ static int check_linear(const Cubic& cubic, Cubic& reduction, while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) { --endIndex; if (endIndex == 0) { - printf("%s shouldn't get here if all four points are about equal", __FUNCTION__); + printf("%s shouldn't get here if all four points are about equal\n", __FUNCTION__); assert(0); } } @@ -213,10 +213,10 @@ int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Flags allowQua } } for (index = 0; index < 4; ++index) { - if (approximately_equal(cubic[index].x, cubic[minX].x)) { + if (AlmostEqualUlps(cubic[index].x, cubic[minX].x)) { minXSet |= 1 << index; } - if (approximately_equal(cubic[index].y, cubic[minY].y)) { + if (AlmostEqualUlps(cubic[index].y, cubic[minY].y)) { minYSet |= 1 << index; } } diff --git a/experimental/Intersection/CubicReduceOrder_Test.cpp b/experimental/Intersection/CubicReduceOrder_Test.cpp index 29811568f6..17d9c4714d 100644 --- a/experimental/Intersection/CubicReduceOrder_Test.cpp +++ b/experimental/Intersection/CubicReduceOrder_Test.cpp @@ -132,10 +132,10 @@ void CubicReduceOrder_Test() { // while a control point is outside of bounding box formed by end points, split _Rect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX}; find_tight_bounds(cubic, bounds); - if ( (!approximately_equal(reduce[0].x, bounds.left) && !approximately_equal(reduce[0].x, bounds.right)) - || (!approximately_equal(reduce[0].y, bounds.top) && !approximately_equal(reduce[0].y, bounds.bottom)) - || (!approximately_equal(reduce[1].x, bounds.left) && !approximately_equal(reduce[1].x, bounds.right)) - || (!approximately_equal(reduce[1].y, bounds.top) && !approximately_equal(reduce[1].y, bounds.bottom))) { + if ( (!AlmostEqualUlps(reduce[0].x, bounds.left) && !AlmostEqualUlps(reduce[0].x, bounds.right)) + || (!AlmostEqualUlps(reduce[0].y, bounds.top) && !AlmostEqualUlps(reduce[0].y, bounds.bottom)) + || (!AlmostEqualUlps(reduce[1].x, bounds.left) && !AlmostEqualUlps(reduce[1].x, bounds.right)) + || (!AlmostEqualUlps(reduce[1].y, bounds.top) && !AlmostEqualUlps(reduce[1].y, bounds.bottom))) { printf("[%d] line computed tight bounds order=%d\n", (int) index, order); } diff --git a/experimental/Intersection/CubicSubDivide.cpp b/experimental/Intersection/CubicSubDivide.cpp index e363a0d67b..fa2025f621 100644 --- a/experimental/Intersection/CubicSubDivide.cpp +++ b/experimental/Intersection/CubicSubDivide.cpp @@ -104,6 +104,21 @@ static void interp_cubic_coords(const double* src, double* dst, double t) void chop_at(const Cubic& src, CubicPair& dst, double t) { + if (t == 0.5) { + dst.pts[0] = src[0]; + dst.pts[1].x = (src[0].x + src[1].x) / 2; + dst.pts[1].y = (src[0].y + src[1].y) / 2; + dst.pts[2].x = (src[0].x + 2 * src[1].x + src[2].x) / 4; + dst.pts[2].y = (src[0].y + 2 * src[1].y + src[2].y) / 4; + dst.pts[3].x = (src[0].x + 3 * (src[1].x + src[2].x) + src[3].x) / 8; + dst.pts[3].y = (src[0].y + 3 * (src[1].y + src[2].y) + src[3].y) / 8; + dst.pts[4].x = (src[1].x + 2 * src[2].x + src[3].x) / 4; + dst.pts[4].y = (src[1].y + 2 * src[2].y + src[3].y) / 4; + dst.pts[5].x = (src[2].x + src[3].x) / 2; + dst.pts[5].y = (src[2].y + src[3].y) / 2; + dst.pts[6] = src[3]; + return; + } interp_cubic_coords(&src[0].x, &dst.pts[0].x, t); interp_cubic_coords(&src[0].y, &dst.pts[0].y, t); } diff --git a/experimental/Intersection/CubicToQuadratics.cpp b/experimental/Intersection/CubicToQuadratics.cpp new file mode 100644 index 0000000000..e3b97ffb79 --- /dev/null +++ b/experimental/Intersection/CubicToQuadratics.cpp @@ -0,0 +1,115 @@ +/* +http://stackoverflow.com/questions/2009160/how-do-i-convert-the-2-control-points-of-a-cubic-curve-to-the-single-control-poi +*/ + +/* +Let's call the control points of the cubic Q0..Q3 and the control points of the quadratic P0..P2. +Then for degree elevation, the equations are: + +Q0 = P0 +Q1 = 1/3 P0 + 2/3 P1 +Q2 = 2/3 P1 + 1/3 P2 +Q3 = P2 +In your case you have Q0..Q3 and you're solving for P0..P2. There are two ways to compute P1 from + the equations above: + +P1 = 3/2 Q1 - 1/2 Q0 +P1 = 3/2 Q2 - 1/2 Q3 +If this is a degree-elevated cubic, then both equations will give the same answer for P1. Since + it's likely not, your best bet is to average them. So, + +P1 = -1/4 Q0 + 3/4 Q1 + 3/4 Q2 - 1/4 Q3 + + +Cubic defined by: P1/2 - anchor points, C1/C2 control points +|x| is the euclidean norm of x +mid-point approx of cubic: a quad that shares the same anchors with the cubic and has the + control point at C = (3·C2 - P2 + 3·C1 - P1)/4 + +Algorithm + +pick an absolute precision (prec) +Compute the Tdiv as the root of (cubic) equation +sqrt(3)/18 · |P2 - 3·C2 + 3·C1 - P1|/2 · Tdiv ^ 3 = prec +if Tdiv < 0.5 divide the cubic at Tdiv. First segment [0..Tdiv] can be approximated with by a + quadratic, with a defect less than prec, by the mid-point approximation. + Repeat from step 2 with the second resulted segment (corresponding to 1-Tdiv) +0.5<=Tdiv<1 - simply divide the cubic in two. The two halves can be approximated by the mid-point + approximation +Tdiv>=1 - the entire cubic can be approximated by the mid-point approximation + +confirmed by (maybe stolen from) +http://www.caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html + +*/ + +#include "CubicUtilities.h" +#include "CurveIntersection.h" + +static double calcTDiv(const Cubic& cubic, double start) { + const double adjust = sqrt(3) / 36; + Cubic sub; + const Cubic* cPtr; + if (start == 0) { + cPtr = &cubic; + } else { + // OPTIMIZE: special-case half-split ? + sub_divide(cubic, start, 1, sub); + cPtr = ⊂ + } + const Cubic& c = *cPtr; + double dx = c[3].x - 3 * (c[2].x - c[1].x) - c[0].x; + double dy = c[3].y - 3 * (c[2].y - c[1].y) - c[0].y; + double dist = sqrt(dx * dx + dy * dy); + double tDiv3 = FLT_EPSILON / (adjust * dist); + return cube_root(tDiv3); +} + +static void demote(const Cubic& cubic, Quadratic& quad) { + quad[0] = cubic[0]; + quad[1].x = (cubic[3].x - 3 * (cubic[2].x - cubic[1].x) - cubic[0].x) / 4; + quad[1].y = (cubic[3].y - 3 * (cubic[2].y - cubic[1].y) - cubic[0].y) / 4; + quad[2] = cubic[3]; +} + +int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics) { + quadratics.setCount(1); // FIXME: every place I have setCount(), I also want setReserve() + Cubic reduced; + int order = reduceOrder(cubic, reduced, kReduceOrder_QuadraticsAllowed); + if (order < 3) { + memcpy(quadratics[0], reduced, order * sizeof(_Point)); + return order; + } + double tDiv = calcTDiv(cubic, 0); + if (approximately_greater_than_one(tDiv)) { + demote(cubic, quadratics[0]); + return 2; + } + if (tDiv >= 0.5) { + CubicPair pair; + chop_at(cubic, pair, 0.5); + quadratics.setCount(2); + demote(pair.first(), quadratics[0]); + demote(pair.second(), quadratics[1]); + return 2; + } + double start = 0; + int index = -1; + // if we iterate but make little progress, check to see if the curve is flat + // or if the control points are tangent to each other + do { + Cubic part; + sub_divide(part, start, tDiv, part); + quadratics.append(); + demote(part, quadratics[++index]); + if (tDiv == 1) { + break; + } + start = tDiv; + tDiv = calcTDiv(cubic, start); + if (tDiv > 1) { + tDiv = 1; + } + } while (true); + return 2; +} diff --git a/experimental/Intersection/CubicToQuadratics_Test.cpp b/experimental/Intersection/CubicToQuadratics_Test.cpp new file mode 100644 index 0000000000..61f6f7d11b --- /dev/null +++ b/experimental/Intersection/CubicToQuadratics_Test.cpp @@ -0,0 +1,119 @@ +#include "CubicIntersection_TestData.h" +#include "CubicUtilities.h" +#include "Intersection_Tests.h" +#include "QuadraticIntersection_TestData.h" +#include "TestUtilities.h" + +void CubicToQuadratics_Test() { + size_t index; + enum { + RunAll, + RunPointDegenerates, + RunNotPointDegenerates, + RunLines, + RunNotLines, + RunModEpsilonLines, + RunLessEpsilonLines, + RunNegEpsilonLines, + RunQuadraticLines, + RunQuadraticModLines, + RunComputedLines, + RunNone + } run = RunAll; + int firstTestIndex = 0; +#if 0 + run = RunComputedLines; + firstTestIndex = 18; +#endif + int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates ? firstTestIndex : INT_MAX; + int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates ? firstTestIndex : INT_MAX; + int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : INT_MAX; + int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : INT_MAX; + int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines ? firstTestIndex : INT_MAX; + int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines ? firstTestIndex : INT_MAX; + int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines ? firstTestIndex : INT_MAX; + int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines ? firstTestIndex : INT_MAX; + int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines ? firstTestIndex : INT_MAX; + int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines ? firstTestIndex : INT_MAX; + SkTDArray<Quadratic> quads; + for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) { + const Cubic& cubic = pointDegenerates[index]; + cubic_to_quadratics(cubic, quads); + if (quads.count() != 1) { + printf("[%d] pointDegenerates count=%d\n", (int) index, quads.count()); + } + } + for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) { + const Cubic& cubic = notPointDegenerates[index]; + cubic_to_quadratics(cubic, quads); + if (quads.count() != 1) { + printf("[%d] notPointDegenerates count=%d\n", (int) index, quads.count()); + } + } + for (index = firstLinesTest; index < lines_count; ++index) { + const Cubic& cubic = lines[index]; + cubic_to_quadratics(cubic, quads); + if (quads.count() != 1) { + printf("[%d] lines count=%d\n", (int) index, quads.count()); + } + } + for (index = firstNotLinesTest; index < notLines_count; ++index) { + const Cubic& cubic = notLines[index]; + cubic_to_quadratics(cubic, quads); + if (quads.count() != 1) { + printf("[%d] notLines order=%d\n", (int) index, quads.count()); + } + } + for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) { + const Cubic& cubic = modEpsilonLines[index]; + cubic_to_quadratics(cubic, quads); + if (quads.count() != 1) { + printf("[%d] line mod by epsilon order=%d\n", (int) index, quads.count()); + } + } + for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) { + const Cubic& cubic = lessEpsilonLines[index]; + cubic_to_quadratics(cubic, quads); + if (quads.count() != 1) { + printf("[%d] line less by epsilon/2 order=%d\n", (int) index, quads.count()); + } + } + for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) { + const Cubic& cubic = negEpsilonLines[index]; + cubic_to_quadratics(cubic, quads); + if (quads.count() != 1) { + printf("[%d] line neg by epsilon/2 order=%d\n", (int) index, quads.count()); + } + } + for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) { + const Quadratic& quad = quadraticLines[index]; + Cubic cubic; + quad_to_cubic(quad, cubic); + cubic_to_quadratics(cubic, quads); + if (quads.count() != 1) { + printf("[%d] line quad order=%d\n", (int) index, quads.count()); + } + } + for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) { + const Quadratic& quad = quadraticModEpsilonLines[index]; + Cubic cubic; + quad_to_cubic(quad, cubic); + cubic_to_quadratics(cubic, quads); + if (quads.count() != 1) { + printf("[%d] line mod quad order=%d\n", (int) index, quads.count()); + } + } + + // test if computed line end points are valid + for (index = firstComputedLinesTest; index < lines_count; ++index) { + const Cubic& cubic = lines[index]; + cubic_to_quadratics(cubic, quads); + if (cubic[0].x != quads[0][0].x && cubic[0].y != quads[0][0].y) { + printf("[%d] unmatched start\n", (int) index); + } + int last = quads.count() - 1; + if (cubic[3].x != quads[last][2].x && cubic[3].y != quads[last][2].y) { + printf("[%d] unmatched end\n", (int) index); + } + } +} diff --git a/experimental/Intersection/CubicUtilities.cpp b/experimental/Intersection/CubicUtilities.cpp index 657d4a3f73..958cabb316 100644 --- a/experimental/Intersection/CubicUtilities.cpp +++ b/experimental/Intersection/CubicUtilities.cpp @@ -5,7 +5,6 @@ * found in the LICENSE file. */ #include "CubicUtilities.h" -#include "DataTypes.h" #include "QuadraticUtilities.h" void coefficients(const double* cubic, double& A, double& B, double& C, double& D) { diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h index ffaeeb2879..2e345ea3ff 100644 --- a/experimental/Intersection/CubicUtilities.h +++ b/experimental/Intersection/CubicUtilities.h @@ -8,8 +8,10 @@ #define CUBIC_UTILITIES_H #include "DataTypes.h" +#include "SkTDArray.h" double cube_root(double x); +int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics); void coefficients(const double* cubic, double& A, double& B, double& C, double& D); int cubicRoots(double A, double B, double C, double D, double t[3]); double derivativeAtT(const double* cubic, double t); diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h index 33d88fa007..265e3b769c 100644 --- a/experimental/Intersection/DataTypes.h +++ b/experimental/Intersection/DataTypes.h @@ -19,6 +19,8 @@ #include <sys/types.h> extern bool AlmostEqualUlps(float A, float B); +inline bool AlmostEqualUlps(double A, double B) { return AlmostEqualUlps((float) A, (float) B); } + // FIXME: delete int UlpsDiff(float A, float B); int FloatAsInt(float A); diff --git a/experimental/Intersection/Extrema.cpp b/experimental/Intersection/Extrema.cpp index 780d877756..7a41ddf77d 100644 --- a/experimental/Intersection/Extrema.cpp +++ b/experimental/Intersection/Extrema.cpp @@ -45,7 +45,7 @@ static int findUnitQuadRoots(double A, double B, double C, double roots[2]) double Q = (B < 0) ? -(B-R)/2 : -(B+R)/2; r += validUnitDivide(Q, A, r); r += validUnitDivide(C, Q, r); - if (r - roots == 2 && approximately_equal(roots[0], roots[1])) { // nearly-equal? + if (r - roots == 2 && AlmostEqualUlps(roots[0], roots[1])) { // nearly-equal? r -= 1; // skip the double root } return (int)(r - roots); diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp index c7ec3109e4..67758f6216 100644 --- a/experimental/Intersection/Intersection_Tests.cpp +++ b/experimental/Intersection/Intersection_Tests.cpp @@ -15,6 +15,7 @@ void cubecode_test(int test); void Intersection_Tests() { int testsRun = 0; + CubicToQuadratics_Test(); SimplifyNew_Test(); Simplify4x4RectsThreaded_Test(testsRun); Simplify4x4QuadraticsThreaded_Test(testsRun); diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h index 46e6b7b355..682d7cdb84 100644 --- a/experimental/Intersection/Intersection_Tests.h +++ b/experimental/Intersection/Intersection_Tests.h @@ -16,6 +16,7 @@ void CubicCoincidence_Test(); void CubicIntersection_Test(); void CubicParameterization_Test(); void CubicReduceOrder_Test(); +void CubicToQuadratics_Test(); void Inline_Tests(); void Intersection_Tests(); void LineCubicIntersection_Test(); diff --git a/experimental/Intersection/LineCubicIntersection.cpp b/experimental/Intersection/LineCubicIntersection.cpp index 3111dddbf1..91a0b7df92 100644 --- a/experimental/Intersection/LineCubicIntersection.cpp +++ b/experimental/Intersection/LineCubicIntersection.cpp @@ -224,7 +224,7 @@ int verticalIntersect(const Cubic& cubic, double top, double bottom, double x, int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]) { LineCubicIntersections c(cubic, line, cRange); int roots; - if (approximately_equal(line[0].y, line[1].y)) { + if (AlmostEqualUlps(line[0].y, line[1].y)) { roots = c.horizontalIntersect(line[0].y); } else { roots = c.intersect(); diff --git a/experimental/Intersection/LineCubicIntersection_Test.cpp b/experimental/Intersection/LineCubicIntersection_Test.cpp index cc993a7797..48754ddc1d 100644 --- a/experimental/Intersection/LineCubicIntersection_Test.cpp +++ b/experimental/Intersection/LineCubicIntersection_Test.cpp @@ -45,11 +45,11 @@ void LineCubicIntersection_Test() { double tt2 = range2[pt]; double tx2, ty2; xy_at_t(line, tt2, tx2, ty2); - if (!approximately_equal(tx1, tx2)) { + if (!AlmostEqualUlps(tx1, tx2)) { printf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); } - if (!approximately_equal(ty1, ty2)) { + if (!AlmostEqualUlps(ty1, ty2)) { printf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n", __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); } diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp index bb06ff742f..ab23c442ce 100644 --- a/experimental/Intersection/LineIntersection.cpp +++ b/experimental/Intersection/LineIntersection.cpp @@ -34,6 +34,7 @@ int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2] axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen) axLen * ay - ax * ayLen == axLen * by - bx * ayLen */ + // FIXME: need to use AlmostEqualUlps variant instead if (approximately_equal_squared(axLen * a[0].y - ayLen * a[0].x, axLen * b[0].y - ayLen * b[0].x)) { const double* aPtr; @@ -124,7 +125,7 @@ int horizontalIntersect(const _Line& line, double y, double tRange[2]) { if (min > y || max < y) { return 0; } - if (approximately_equal(min, max)) { + if (AlmostEqualUlps(min, max)) { tRange[0] = 0; tRange[1] = 1; return 2; @@ -235,7 +236,7 @@ static int verticalIntersect(const _Line& line, double x, double tRange[2]) { if (min > x || max < x) { return 0; } - if (approximately_equal(min, max)) { + if (AlmostEqualUlps(min, max)) { tRange[0] = 0; tRange[1] = 1; return 2; diff --git a/experimental/Intersection/LineParameterization.cpp b/experimental/Intersection/LineParameterization.cpp index 4ef6fbde79..197394530b 100644 --- a/experimental/Intersection/LineParameterization.cpp +++ b/experimental/Intersection/LineParameterization.cpp @@ -19,7 +19,7 @@ bool implicit_matches(const _Line& one, const _Line& two) { (dy1 * dy2) * dx1 / dy1 == (dy1 * dy2) * dx2 / dy2 dy2 * dx1 == dy1 * dx2 */ - if (!approximately_equal(oneD.x * twoD.y, twoD.x * oneD.y)) { + if (!AlmostEqualUlps(oneD.x * twoD.y, twoD.x * oneD.y)) { return false; } /* See if the axis intercepts match, i.e. @@ -27,7 +27,7 @@ bool implicit_matches(const _Line& one, const _Line& two) { dx * (y0 - x0 * dy / dx) == dx * (y1 - x1 * dy / dx) dx * y0 - x0 * dy == dx * y1 - x1 * dy */ - if (!approximately_equal(oneD.x * one[0].y - oneD.y * one[0].x, + if (!AlmostEqualUlps(oneD.x * one[0].y - oneD.y * one[0].x, oneD.x * two[0].y - oneD.y * two[0].x)) { return false; } diff --git a/experimental/Intersection/LineParameteters_Test.cpp b/experimental/Intersection/LineParameteters_Test.cpp index e8adf33342..6d853255ac 100644 --- a/experimental/Intersection/LineParameteters_Test.cpp +++ b/experimental/Intersection/LineParameteters_Test.cpp @@ -53,7 +53,7 @@ void LineParameter_Test() { distSq *= distSq; double answersSq = answers[index][inner]; answersSq *= answersSq; - if (approximately_equal(distSq, normalSquared * answersSq)) { + if (AlmostEqualUlps(distSq, normalSquared * answersSq)) { continue; } printf("%s [%d,%d] denormalizedDistance:%g != answer:%g" @@ -66,8 +66,7 @@ void LineParameter_Test() { double normalizedDistance[2]; lineParameters.controlPtDistance(cubic, normalizedDistance); for (inner = 0; inner < 2; ++inner) { - if (approximately_equal(fabs(normalizedDistance[inner]), - answers[index][inner])) { + if (AlmostEqualUlps(fabs(normalizedDistance[inner]), answers[index][inner])) { continue; } printf("%s [%d,%d] normalizedDistance:%1.10g != answer:%g\n", diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp index b3303cf95e..00c3554327 100644 --- a/experimental/Intersection/LineQuadraticIntersection.cpp +++ b/experimental/Intersection/LineQuadraticIntersection.cpp @@ -298,7 +298,7 @@ static double horizontalIntersect(const Quadratic& quad, const _Point& pt) { double x; double t = rootVals[index]; xy_at_t(quad, t, x, *(double*) 0); - if (approximately_equal(x, pt.x)) { + if (AlmostEqualUlps(x, pt.x)) { return t; } } @@ -313,7 +313,7 @@ static double verticalIntersect(const Quadratic& quad, const _Point& pt) { double y; double t = rootVals[index]; xy_at_t(quad, t, *(double*) 0, y); - if (approximately_equal(y, pt.y)) { + if (AlmostEqualUlps(y, pt.y)) { return t; } } diff --git a/experimental/Intersection/LineQuadraticIntersection_Test.cpp b/experimental/Intersection/LineQuadraticIntersection_Test.cpp index 69227c3a40..6167c6d498 100644 --- a/experimental/Intersection/LineQuadraticIntersection_Test.cpp +++ b/experimental/Intersection/LineQuadraticIntersection_Test.cpp @@ -80,8 +80,8 @@ static void testOneOffs() { double lineT = intersections.fT[1][inner]; double lineX, lineY; xy_at_t(line, lineT, lineX, lineY); - assert(approximately_equal(quadX, lineX) - && approximately_equal(quadY, lineY)); + assert(AlmostEqualUlps(quadX, lineX) + && AlmostEqualUlps(quadY, lineY)); } } } @@ -120,12 +120,12 @@ void LineQuadraticIntersection_Test() { double tt2 = intersections.fT[1][pt]; SkASSERT(tt2 >= 0 && tt2 <= 1); xy_at_t(line, tt2, t2.x, t2.y); - if (!approximately_equal(t1.x, t2.x)) { + if (!AlmostEqualUlps(t1.x, t2.x)) { SkDebugf("%s [%d,%d] x!= t1=%1.9g (%1.9g,%1.9g) t2=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__, (int)index, pt, tt1, t1.x, t1.y, tt2, t2.x, t2.y); SkASSERT(0); } - if (!approximately_equal(t1.y, t2.y)) { + if (!AlmostEqualUlps(t1.y, t2.y)) { SkDebugf("%s [%d,%d] y!= t1=%1.9g (%1.9g,%1.9g) t2=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__, (int)index, pt, tt1, t1.x, t1.y, tt2, t2.x, t2.y); SkASSERT(0); diff --git a/experimental/Intersection/LineUtilities.cpp b/experimental/Intersection/LineUtilities.cpp index 25bd88dc54..fa756b3d3b 100644 --- a/experimental/Intersection/LineUtilities.cpp +++ b/experimental/Intersection/LineUtilities.cpp @@ -90,7 +90,7 @@ static void setMinMax(double x, int flags, double& minX, double& maxX) { void x_at(const _Point& p1, const _Point& p2, double top, double bottom, int flags, double& minX, double& maxX) { - if (approximately_equal(p1.y, p2.y)) { + if (AlmostEqualUlps(p1.y, p2.y)) { // It should be OK to bail early in this case. There's another edge // which shares this end point which can intersect without failing to // have a slope ... maybe diff --git a/experimental/Intersection/QuadraticIntersection.cpp b/experimental/Intersection/QuadraticIntersection.cpp index 800964d350..9c2dee38bf 100644 --- a/experimental/Intersection/QuadraticIntersection.cpp +++ b/experimental/Intersection/QuadraticIntersection.cpp @@ -72,22 +72,22 @@ bool intersect(double minT1, double maxT1, double minT2, double maxT2) { largeT = interp(minT2, maxT2, minT); xy_at_t(quad2, largeT, q2pt.x, q2pt.y); xy_at_t(quad1, minT1, q1pt.x, q1pt.y); - if (approximately_equal(q2pt.x, q1pt.x) && approximately_equal(q2pt.y, q1pt.y)) { + if (AlmostEqualUlps(q2pt.x, q1pt.x) && AlmostEqualUlps(q2pt.y, q1pt.y)) { smallT = minT1; } else { xy_at_t(quad1, maxT1, q1pt.x, q1pt.y); // FIXME: debug code - assert(approximately_equal(q2pt.x, q1pt.x) && approximately_equal(q2pt.y, q1pt.y)); + assert(AlmostEqualUlps(q2pt.x, q1pt.x) && AlmostEqualUlps(q2pt.y, q1pt.y)); smallT = maxT1; } } else { smallT = interp(minT1, maxT1, minT); xy_at_t(quad1, smallT, q1pt.x, q1pt.y); xy_at_t(quad2, minT2, q2pt.x, q2pt.y); - if (approximately_equal(q2pt.x, q1pt.x) && approximately_equal(q2pt.y, q1pt.y)) { + if (AlmostEqualUlps(q2pt.x, q1pt.x) && AlmostEqualUlps(q2pt.y, q1pt.y)) { largeT = minT2; } else { xy_at_t(quad2, maxT2, q2pt.x, q2pt.y); // FIXME: debug code - assert(approximately_equal(q2pt.x, q1pt.x) && approximately_equal(q2pt.y, q1pt.y)); + assert(AlmostEqualUlps(q2pt.x, q1pt.x) && AlmostEqualUlps(q2pt.y, q1pt.y)); largeT = maxT2; } } @@ -180,8 +180,8 @@ bool intersectAsLine(double minT1, double maxT1, double minT2, double maxT2, xy_at_t(treat1AsLine ? quad2 : quad1, midQuadT, midQuad.x, midQuad.y); double lineT = t_at(treat1AsLine ? line1 : line2, midQuad); xy_at_t(treat1AsLine ? line1 : line2, lineT, midLine.x, midLine.y); - if (approximately_equal(midQuad.x, midLine.x) - && approximately_equal(midQuad.y, midLine.y)) { + if (AlmostEqualUlps(midQuad.x, midLine.x) + && AlmostEqualUlps(midQuad.y, midLine.y)) { smallT1 = lq.fT[0][0]; largeT1 = lq.fT[1][0]; smallT2 = lq.fT[0][1]; @@ -331,7 +331,7 @@ static void hackToFixPartialCoincidence(const Quadratic& q1, const Quadratic& q2 _Line ends1; xy_at_t(q1, start1, ends1[0].x, ends1[0].y); xy_at_t(q1, end1, ends1[1].x, ends1[1].y); - if (!approximately_equal(ends1[0].x, ends1[1].x) || approximately_equal(ends1[0].y, ends1[1].y)) { + if (!AlmostEqualUlps(ends1[0].x, ends1[1].x) || AlmostEqualUlps(ends1[0].y, ends1[1].y)) { cIndex += 2; continue; } @@ -341,7 +341,7 @@ static void hackToFixPartialCoincidence(const Quadratic& q1, const Quadratic& q2 xy_at_t(q2, start2, ends2[0].x, ends2[0].y); xy_at_t(q2, end2, ends2[1].x, ends2[1].y); // again, approximately should be used with T values, not points FIXME - if (!approximately_equal(ends2[0].x, ends2[1].x) || approximately_equal(ends2[0].y, ends2[1].y)) { + if (!AlmostEqualUlps(ends2[0].x, ends2[1].x) || AlmostEqualUlps(ends2[0].y, ends2[1].y)) { cIndex += 2; continue; } diff --git a/experimental/Intersection/QuadraticParameterization.cpp b/experimental/Intersection/QuadraticParameterization.cpp index 8e7f1a2300..76441aa4d5 100644 --- a/experimental/Intersection/QuadraticParameterization.cpp +++ b/experimental/Intersection/QuadraticParameterization.cpp @@ -105,8 +105,7 @@ bool QuadImplicitForm::implicit_match(const QuadImplicitForm& p2) const { if (first == index) { continue; } - if (!approximately_equal(p[index] * p2.p[first], - p[first] * p2.p[index])) { + if (!AlmostEqualUlps(p[index] * p2.p[first], p[first] * p2.p[index])) { return false; } } diff --git a/experimental/Intersection/QuadraticReduceOrder.cpp b/experimental/Intersection/QuadraticReduceOrder.cpp index b68a68b3ac..aa1d0585dd 100644 --- a/experimental/Intersection/QuadraticReduceOrder.cpp +++ b/experimental/Intersection/QuadraticReduceOrder.cpp @@ -148,10 +148,10 @@ int reduceOrder(const Quadratic& quad, Quadratic& reduction) { } } for (index = 0; index < 3; ++index) { - if (approximately_equal(quad[index].x, quad[minX].x)) { + if (AlmostEqualUlps(quad[index].x, quad[minX].x)) { minXSet |= 1 << index; } - if (approximately_equal(quad[index].y, quad[minY].y)) { + if (AlmostEqualUlps(quad[index].y, quad[minY].y)) { minYSet |= 1 << index; } } diff --git a/experimental/Intersection/Simplify.cpp b/experimental/Intersection/Simplify.cpp index c798a3a5ca..e29b0df7c0 100644 --- a/experimental/Intersection/Simplify.cpp +++ b/experimental/Intersection/Simplify.cpp @@ -522,20 +522,20 @@ static bool LineVertical(const SkPoint a[2], double startT, double endT) { double x[2]; xy_at_t(aLine, startT, x[0], *(double*) 0); xy_at_t(aLine, endT, x[1], *(double*) 0); - return approximately_equal((float) x[0], (float) x[1]); + return AlmostEqualUlps((float) x[0], (float) x[1]); } static bool QuadVertical(const SkPoint a[3], double startT, double endT) { SkPoint dst[3]; QuadSubDivide(a, startT, endT, dst); - return approximately_equal(dst[0].fX, dst[1].fX) && approximately_equal(dst[1].fX, dst[2].fX); + return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX); } static bool CubicVertical(const SkPoint a[4], double startT, double endT) { SkPoint dst[4]; CubicSubDivide(a, startT, endT, dst); - return approximately_equal(dst[0].fX, dst[1].fX) && approximately_equal(dst[1].fX, dst[2].fX) - && approximately_equal(dst[2].fX, dst[3].fX); + return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX) + && AlmostEqualUlps(dst[2].fX, dst[3].fX); } static bool (* const SegmentVertical[])(const SkPoint [], double , double) = { @@ -1285,8 +1285,8 @@ public: (*SegmentXYAtT[angles[0].verb()])(angles[0].pts(), (*angles[0].spans())[angles[0].start()].fT, &angle0Pt); (*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt); - SkASSERT(approximately_equal(angle0Pt.fX, newPt.fX)); - SkASSERT(approximately_equal(angle0Pt.fY, newPt.fY)); + SkASSERT(AlmostEqualUlps(angle0Pt.fX, newPt.fX)); + SkASSERT(AlmostEqualUlps(angle0Pt.fY, newPt.fY)); } #endif angle->set(fPts, fVerb, this, start, end, fTs); @@ -1979,7 +1979,7 @@ public: } if (fBounds.fLeft == fBounds.fRight) { // if vertical, and directly above test point, wait for another one - return approximately_equal(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex; + return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex; } // intersect ray starting at basePt with edge Intersections intersections; diff --git a/gyp/shapeops_edge.gyp b/gyp/shapeops_edge.gyp index 854287650f..4066d4bc8f 100644 --- a/gyp/shapeops_edge.gyp +++ b/gyp/shapeops_edge.gyp @@ -29,6 +29,8 @@ '../experimental/Intersection/CubicReduceOrder.cpp', '../experimental/Intersection/CubicReduceOrder_Test.cpp', '../experimental/Intersection/CubicSubDivide.cpp', + '../experimental/Intersection/CubicToQuadratics.cpp', + '../experimental/Intersection/CubicToQuadratics_Test.cpp', '../experimental/Intersection/CubicUtilities.cpp', '../experimental/Intersection/DataTypes.cpp', '../experimental/Intersection/EdgeMain.cpp', |