aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
-rw-r--r--experimental/Intersection/CubicIntersection_Test.cpp4
-rw-r--r--experimental/Intersection/CubicParameterization.cpp3
-rw-r--r--experimental/Intersection/CubicReduceOrder.cpp10
-rw-r--r--experimental/Intersection/CubicReduceOrder_Test.cpp8
-rw-r--r--experimental/Intersection/CubicSubDivide.cpp15
-rw-r--r--experimental/Intersection/CubicToQuadratics.cpp115
-rw-r--r--experimental/Intersection/CubicToQuadratics_Test.cpp119
-rw-r--r--experimental/Intersection/CubicUtilities.cpp1
-rw-r--r--experimental/Intersection/CubicUtilities.h2
-rw-r--r--experimental/Intersection/DataTypes.h2
-rw-r--r--experimental/Intersection/Extrema.cpp2
-rw-r--r--experimental/Intersection/Intersection_Tests.cpp1
-rw-r--r--experimental/Intersection/Intersection_Tests.h1
-rw-r--r--experimental/Intersection/LineCubicIntersection.cpp2
-rw-r--r--experimental/Intersection/LineCubicIntersection_Test.cpp4
-rw-r--r--experimental/Intersection/LineIntersection.cpp5
-rw-r--r--experimental/Intersection/LineParameterization.cpp4
-rw-r--r--experimental/Intersection/LineParameteters_Test.cpp5
-rw-r--r--experimental/Intersection/LineQuadraticIntersection.cpp4
-rw-r--r--experimental/Intersection/LineQuadraticIntersection_Test.cpp8
-rw-r--r--experimental/Intersection/LineUtilities.cpp2
-rw-r--r--experimental/Intersection/QuadraticIntersection.cpp16
-rw-r--r--experimental/Intersection/QuadraticParameterization.cpp3
-rw-r--r--experimental/Intersection/QuadraticReduceOrder.cpp4
-rw-r--r--experimental/Intersection/Simplify.cpp14
-rw-r--r--gyp/shapeops_edge.gyp2
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 = &sub;
+ }
+ 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',