save work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@3141 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/ConvexHull.cpp b/experimental/Intersection/ConvexHull.cpp
index b03eb46..6cdbe60 100644
--- a/experimental/Intersection/ConvexHull.cpp
+++ b/experimental/Intersection/ConvexHull.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "IntersectionUtilities.h"
/* Given a cubic, find the convex hull described by the end and control points.
diff --git a/experimental/Intersection/ConvexHull_Test.cpp b/experimental/Intersection/ConvexHull_Test.cpp
index 74329c7..4eb524b 100644
--- a/experimental/Intersection/ConvexHull_Test.cpp
+++ b/experimental/Intersection/ConvexHull_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersection_Tests.h"
#include "IntersectionUtilities.h"
diff --git a/experimental/Intersection/CubicBezierClip.cpp b/experimental/Intersection/CubicBezierClip.cpp
index 1b5c60c..4ed1369 100644
--- a/experimental/Intersection/CubicBezierClip.cpp
+++ b/experimental/Intersection/CubicBezierClip.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "LineParameters.h"
#include <algorithm> // used for std::swap
diff --git a/experimental/Intersection/CubicBezierClip_Test.cpp b/experimental/Intersection/CubicBezierClip_Test.cpp
index 1e7942d..d45a026 100644
--- a/experimental/Intersection/CubicBezierClip_Test.cpp
+++ b/experimental/Intersection/CubicBezierClip_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "CubicIntersection_TestData.h"
#include "Intersection_Tests.h"
diff --git a/experimental/Intersection/CubicBounds.cpp b/experimental/Intersection/CubicBounds.cpp
new file mode 100644
index 0000000..3534425
--- /dev/null
+++ b/experimental/Intersection/CubicBounds.cpp
@@ -0,0 +1,10 @@
+/*
+ * CubicBounds.cpp
+ * edge
+ *
+ * Created by Cary Clark on 1/27/12.
+ * Copyright 2012 __MyCompanyName__. All rights reserved.
+ *
+ */
+
+
diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp
index c41e0d7..13c4726 100644
--- a/experimental/Intersection/CubicIntersection.cpp
+++ b/experimental/Intersection/CubicIntersection.cpp
@@ -1,70 +1,20 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersections.h"
+#include "IntersectionUtilities.h"
#include "LineIntersection.h"
-static bool chop(const Cubic& smaller, const Cubic& larger,
- Intersections& intersections, double minT, double maxT);
-
-static bool intersect(const Cubic& smaller, const Cubic& larger,
- Intersections& intersections) {
- // FIXME: carry order with cubic so we don't call it repeatedly
- Cubic smallResult;
- if (reduceOrder(smaller, smallResult, kReduceOrder_NoQuadraticsAllowed) <= 2) {
- Cubic largeResult;
- if (reduceOrder(larger, largeResult, kReduceOrder_NoQuadraticsAllowed) <= 2) {
- _Point pt;
- const _Line& smallLine = (const _Line&) smallResult;
- const _Line& largeLine = (const _Line&) largeResult;
- if (!lineIntersect(smallLine, largeLine, &pt)) {
- return false;
- }
- double smallT = t_at(smallLine, pt);
- double largeT = t_at(largeLine, pt);
- intersections.add(smallT, largeT);
- return true;
- }
- }
- double minT, maxT;
- if (!bezier_clip(smaller, larger, minT, maxT)) {
- if (minT == maxT) {
- intersections.add(minT, 0.5);
- return true;
- }
- return false;
- }
- return chop(larger, smaller, intersections, minT, maxT);
+class CubicIntersections : public Intersections {
+public:
+
+CubicIntersections(const Cubic& c1, const Cubic& c2, Intersections& i)
+ : cubic1(c1)
+ , cubic2(c2)
+ , intersections(i)
+ , depth(0)
+ , splits(0) {
}
-bool chop(const Cubic& smaller, const Cubic& larger,
- Intersections& intersections, double minT, double maxT) {
- intersections.swap();
- if (maxT - minT > 0.8) { // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf Multiple intersections
- CubicPair cubicPair;
- chop_at(larger, cubicPair, 0.5);
- int used = intersections.used();
- if (intersect(cubicPair.first(), smaller, intersections)) {
- intersections.offset(used, 0, 0.5);
- }
- used = intersections.used();
- if (intersect(cubicPair.second(), smaller, intersections)) {
- intersections.offset(used, 0.5, 1);
- }
- intersections.swap();
- return intersections.intersected();
- }
- Cubic cut;
- sub_divide(smaller, minT, maxT, cut);
- int used = intersections.used();
- bool result = intersect(cut, larger, intersections);
- if (result) {
- intersections.offset(used, minT, maxT);
- }
- intersections.swap();
- return result;
-}
-
-bool intersectStart(const Cubic& cubic1, const Cubic& cubic2,
- Intersections& intersections) {
+bool intersect() {
double minT1, minT2, maxT1, maxT2;
if (!bezier_clip(cubic2, cubic1, minT1, maxT1)) {
return false;
@@ -72,9 +22,133 @@
if (!bezier_clip(cubic1, cubic2, minT2, maxT2)) {
return false;
}
+ int split;
if (maxT1 - minT1 < maxT2 - minT2) {
intersections.swap();
- return chop(cubic1, cubic2, intersections, minT1, maxT1);
- }
- return chop(cubic2, cubic1, intersections, minT2, maxT2);
+ minT2 = 0;
+ maxT2 = 1;
+ split = maxT1 - minT1 > tClipLimit;
+ } else {
+ minT1 = 0;
+ maxT1 = 1;
+ split = (maxT2 - minT2 > tClipLimit) << 1;
+ }
+ return chop(minT1, maxT1, minT2, maxT2, split);
}
+
+protected:
+
+bool intersect(double minT1, double maxT1, double minT2, double maxT2) {
+ Cubic smaller, larger;
+ // FIXME: carry last subdivide and reduceOrder result with cubic
+ sub_divide(cubic1, minT1, maxT1, intersections.swapped() ? larger : smaller);
+ sub_divide(cubic2, minT2, maxT2, intersections.swapped() ? smaller : larger);
+ Cubic smallResult;
+ if (reduceOrder(smaller, smallResult,
+ kReduceOrder_NoQuadraticsAllowed) <= 2) {
+ Cubic largeResult;
+ if (reduceOrder(larger, largeResult,
+ kReduceOrder_NoQuadraticsAllowed) <= 2) {
+ const _Line& smallLine = (const _Line&) smallResult;
+ const _Line& largeLine = (const _Line&) largeResult;
+ double smallT[2];
+ double largeT[2];
+ // FIXME: this doesn't detect or deal with coincident lines
+ if (!::intersect(smallLine, largeLine, smallT, largeT)) {
+ return false;
+ }
+ if (intersections.swapped()) {
+ smallT[0] = interp(minT2, maxT2, smallT[0]);
+ largeT[0] = interp(minT1, maxT1, largeT[0]);
+ } else {
+ smallT[0] = interp(minT1, maxT1, smallT[0]);
+ largeT[0] = interp(minT2, maxT2, largeT[0]);
+ }
+ intersections.add(smallT[0], largeT[0]);
+ return true;
+ }
+ }
+ double minT, maxT;
+ if (!bezier_clip(smaller, larger, minT, maxT)) {
+ if (minT == maxT) {
+ if (intersections.swapped()) {
+ minT1 = (minT1 + maxT1) / 2;
+ minT2 = interp(minT2, maxT2, minT);
+ } else {
+ minT1 = interp(minT1, maxT1, minT);
+ minT2 = (minT2 + maxT2) / 2;
+ }
+ intersections.add(minT1, minT2);
+ return true;
+ }
+ return false;
+ }
+
+ int split;
+ if (intersections.swapped()) {
+ double newMinT1 = interp(minT1, maxT1, minT);
+ double newMaxT1 = interp(minT1, maxT1, maxT);
+ split = (newMaxT1 - newMinT1 > (maxT1 - minT1) * tClipLimit) << 1;
+#define VERBOSE 0
+#if VERBOSE
+ printf("%s d=%d s=%d new1=(%g,%g) old1=(%g,%g) split=%d\n",
+ __FUNCTION__, depth, splits, newMinT1, newMaxT1, minT1, maxT1,
+ split);
+#endif
+ minT1 = newMinT1;
+ maxT1 = newMaxT1;
+ } else {
+ double newMinT2 = interp(minT2, maxT2, minT);
+ double newMaxT2 = interp(minT2, maxT2, maxT);
+ split = newMaxT2 - newMinT2 > (maxT2 - minT2) * tClipLimit;
+#if VERBOSE
+ printf("%s d=%d s=%d new2=(%g,%g) old2=(%g,%g) split=%d\n",
+ __FUNCTION__, depth, splits, newMinT2, newMaxT2, minT2, maxT2,
+ split);
+#endif
+ minT2 = newMinT2;
+ maxT2 = newMaxT2;
+ }
+ return chop(minT1, maxT1, minT2, maxT2, split);
+}
+
+bool chop(double minT1, double maxT1, double minT2, double maxT2, int split) {
+ ++depth;
+ intersections.swap();
+ if (split) {
+ ++splits;
+ if (split & 2) {
+ double middle1 = (maxT1 + minT1) / 2;
+ intersect(minT1, middle1, minT2, maxT2);
+ intersect(middle1, maxT1, minT2, maxT2);
+ } else {
+ double middle2 = (maxT2 + minT2) / 2;
+ intersect(minT1, maxT1, minT2, middle2);
+ intersect(minT1, maxT1, middle2, maxT2);
+ }
+ --splits;
+ intersections.swap();
+ --depth;
+ return intersections.intersected();
+ }
+ bool result = intersect(minT1, maxT1, minT2, maxT2);
+ intersections.swap();
+ --depth;
+ return result;
+}
+
+private:
+
+static const double tClipLimit = 0.8; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf see Multiple intersections
+const Cubic& cubic1;
+const Cubic& cubic2;
+Intersections& intersections;
+int depth;
+int splits;
+};
+
+bool intersect(const Cubic& c1, const Cubic& c2, Intersections& i) {
+ CubicIntersections c(c1, c2, i);
+ return c.intersect();
+}
+
diff --git a/experimental/Intersection/CubicIntersection_Test.cpp b/experimental/Intersection/CubicIntersection_Test.cpp
index 208fbaa..005e777 100644
--- a/experimental/Intersection/CubicIntersection_Test.cpp
+++ b/experimental/Intersection/CubicIntersection_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "CubicIntersection_TestData.h"
#include "Intersection_Tests.h"
#include "Intersections.h"
@@ -26,7 +26,7 @@
continue;
}
Intersections tIntersections;
- intersectStartT(reduce1, reduce2, tIntersections);
+ intersect(reduce1, reduce2, tIntersections);
if (!tIntersections.intersected()) {
printf("%s [%d] no intersection\n", __FUNCTION__, (int) index);
continue;
diff --git a/experimental/Intersection/CubicParameterization.cpp b/experimental/Intersection/CubicParameterization.cpp
index c14dd7e..bb75771 100644
--- a/experimental/Intersection/CubicParameterization.cpp
+++ b/experimental/Intersection/CubicParameterization.cpp
@@ -1,4 +1,5 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
+#include "CubicUtilities.h"
/* from http://tom.cs.byu.edu/~tom/papers/cvgip84.pdf 4.1
*
@@ -55,10 +56,10 @@
*/
enum {
- xxx_coeff,
- xxy_coeff,
- xyy_coeff,
- yyy_coeff,
+ xxx_coeff, // A
+ xxy_coeff, // B
+ xyy_coeff, // C
+ yyy_coeff, // D
xx_coeff,
xy_coeff,
yy_coeff,
@@ -68,6 +69,9 @@
coeff_count
};
+#define USE_SYVESTER 0 // if 0, use control-point base parametric form
+#if USE_SYVESTER
+
// FIXME: factoring version unwritten
// static bool straight_forward = true;
@@ -90,7 +94,7 @@
* Rather than edit the lines below, please edit the code there instead.
*/
// start of generated code
-static double calc_E(double a, double b, double c, double d,
+static double calc_xx(double a, double b, double c, double d,
double e, double f, double g, double h) {
return
-3 * d * e * e * e
@@ -102,7 +106,7 @@
+ 3 * a * e * e * h;
}
-static double calc_F(double a, double b, double c, double d,
+static double calc_xy(double a, double b, double c, double d,
double e, double f, double g, double h) {
return
-3 * b * c * e * e
@@ -115,7 +119,7 @@
- 6 * a * a * e * h;
}
-static double calc_G(double a, double b, double c, double d,
+static double calc_yy(double a, double b, double c, double d,
double e, double f, double g, double h) {
return
-b * b * b * e
@@ -127,7 +131,7 @@
+ 3 * a * a * a * h;
}
-static double calc_H(double a, double b, double c, double d,
+static double calc_x(double a, double b, double c, double d,
double e, double f, double g, double h) {
return
3 * d * d * e * e * e
@@ -153,7 +157,7 @@
+ 3 * a * a * e * h * h;
}
-static double calc_I(double a, double b, double c, double d,
+static double calc_y(double a, double b, double c, double d,
double e, double f, double g, double h) {
return
-c * c * c * e * e
@@ -179,7 +183,7 @@
- 3 * a * a * a * h * h;
}
-static double calc_J(double a, double b, double c, double d,
+static double calc_c(double a, double b, double c, double d,
double e, double f, double g, double h) {
return
-d * d * d * e * e * e
@@ -219,11 +223,129 @@
}
// end of generated code
+#else
+
+/* more Mathematica generated code. This takes a different tack, starting with
+ the control-point based parametric formulas. The C code is unoptimized --
+ in this form, this is a proof of concept (since the other code didn't work)
+*/
+static double calc_c(double a, double b, double c, double d,
+ double e, double f, double g, double h) {
+ return
+d*d*d*e*e*e - 3*d*d*(3*c*e*e*f + 3*b*e*(-3*f*f + 2*e*g) + a*(9*f*f*f - 9*e*f*g + e*e*h)) -
+ h*(27*c*c*c*e*e - 27*c*c*(3*b*e*f - 3*a*f*f + 2*a*e*g) +
+ h*(-27*b*b*b*e + 27*a*b*b*f - 9*a*a*b*g + a*a*a*h) +
+ 9*c*(9*b*b*e*g + a*b*(-9*f*g + 3*e*h) + a*a*(3*g*g - 2*f*h))) +
+ 3*d*(9*c*c*e*e*g + 9*b*b*e*(3*g*g - 2*f*h) + 3*a*b*(-9*f*g*g + 6*f*f*h + e*g*h) +
+ a*a*(9*g*g*g - 9*f*g*h + e*h*h) + 3*c*(3*b*e*(-3*f*g + e*h) + a*(9*f*f*g - 6*e*g*g - e*f*h)))
+ ;
+}
+
+// - Power(e - 3*f + 3*g - h,3)*Power(x,3)
+static double calc_xxx(double e3f3gh) {
+ return -e3f3gh * e3f3gh * e3f3gh;
+}
+
+static double calc_y(double a, double b, double c, double d,
+ double e, double f, double g, double h) {
+ return
++ 3*(6*b*d*d*e*e - d*d*d*e*e + 18*b*b*d*e*f - 18*b*d*d*e*f -
+ 9*b*d*d*f*f - 54*b*b*d*e*g + 12*b*d*d*e*g - 27*b*b*d*g*g - 18*b*b*b*e*h + 18*b*b*d*e*h +
+ 18*b*b*d*f*h + a*a*a*h*h - 9*b*b*b*h*h + 9*c*c*c*e*(e + 2*h) +
+ a*a*(-3*b*h*(2*g + h) + d*(-27*g*g + 9*g*h - h*(2*e + h) + 9*f*(g + h))) +
+ a*(9*b*b*h*(2*f + h) - 3*b*d*(6*f*f - 6*f*(3*g - 2*h) + g*(-9*g + h) + e*(g + h)) +
+ d*d*(e*e + 9*f*(3*f - g) + e*(-9*f - 9*g + 2*h))) -
+ 9*c*c*(d*e*(e + 2*g) + 3*b*(f*h + e*(f + h)) + a*(-3*f*f - 6*f*h + 2*(g*h + e*(g + h)))) +
+ 3*c*(d*d*e*(e + 2*f) + a*a*(3*g*g + 6*g*h - 2*h*(2*f + h)) + 9*b*b*(g*h + e*(g + h)) +
+ a*d*(-9*f*f - 18*f*g + 6*g*g + f*h + e*(f + 12*g + h)) +
+ b*(d*(-3*e*e + 9*f*g + e*(9*f + 9*g - 6*h)) + 3*a*(h*(2*e - 3*g + h) - 3*f*(g + h))))) // *y
+ ;
+}
+
+static double calc_yy(double a, double b, double c, double d,
+ double e, double f, double g, double h) {
+ return
+- 3*(18*c*c*c*e - 18*c*c*d*e + 6*c*d*d*e - d*d*d*e + 3*c*d*d*f - 9*c*c*d*g + a*a*a*h + 9*c*c*c*h -
+ 9*b*b*b*(e + 2*h) - a*a*(d*(e - 9*f + 18*g - 7*h) + 3*c*(2*f - 6*g + h)) +
+ a*(-9*c*c*(2*e - 6*f + 2*g - h) + d*d*(-7*e + 18*f - 9*g + h) + 3*c*d*(7*e - 17*f + 3*g + h)) +
+ 9*b*b*(3*c*(e + g + h) + a*(f + 2*h) - d*(e - 2*(f - 3*g + h))) -
+ 3*b*(-(d*d*(e - 6*f + 2*g)) - 3*c*d*(e + 3*f + 3*g - h) + 9*c*c*(e + f + h) + a*a*(g + 2*h) +
+ a*(c*(-3*e + 9*f + 9*g + 3*h) + d*(e + 3*f - 17*g + 7*h)))) // *Power(y,2)
+ ;
+}
+
+// + Power(a - 3*b + 3*c - d,3)*Power(y,3)
+static double calc_yyy(double a3b3cd) {
+ return a3b3cd * a3b3cd * a3b3cd;
+}
+
+static double calc_xx(double a, double b, double c, double d,
+ double e, double f, double g, double h) {
+ return
+// + Power(x,2)*
+(-3*(-9*b*e*f*f + 9*a*f*f*f + 6*b*e*e*g - 9*a*e*f*g + 27*b*e*f*g - 27*a*f*f*g + 18*a*e*g*g - 54*b*e*g*g +
+ 27*a*f*g*g + 27*b*f*g*g - 18*a*g*g*g + a*e*e*h - 9*b*e*e*h + 3*a*e*f*h + 9*b*e*f*h + 9*a*f*f*h -
+ 18*b*f*f*h - 21*a*e*g*h + 51*b*e*g*h - 9*a*f*g*h - 27*b*f*g*h + 18*a*g*g*h + 7*a*e*h*h - 18*b*e*h*h - 3*a*f*h*h +
+ 18*b*f*h*h - 6*a*g*h*h - 3*b*g*h*h + a*h*h*h +
+ 3*c*(-9*f*f*(g - 2*h) + 3*g*g*h - f*h*(9*g + 2*h) + e*e*(f - 6*g + 6*h) +
+ e*(9*f*g + 6*g*g - 17*f*h - 3*g*h + 3*h*h)) -
+ d*(e*e*e + e*e*(-6*f - 3*g + 7*h) - 9*(2*f - g)*(f*f + g*g - f*(g + h)) +
+ e*(18*f*f + 9*g*g + 3*g*h + h*h - 3*f*(3*g + 7*h)))) )
+ ;
+}
+
+// + Power(x,2)*(3*(a - 3*b + 3*c - d)*Power(e - 3*f + 3*g - h,2)*y)
+static double calc_xxy(double a3b3cd, double e3f3gh) {
+ return 3 * a3b3cd * e3f3gh * e3f3gh;
+}
+
+static double calc_x(double a, double b, double c, double d,
+ double e, double f, double g, double h) {
+ return
+// + x*
+(-3*(27*b*b*e*g*g - 27*a*b*f*g*g + 9*a*a*g*g*g - 18*b*b*e*f*h + 18*a*b*f*f*h + 3*a*b*e*g*h -
+ 27*b*b*e*g*h - 9*a*a*f*g*h + 27*a*b*f*g*h - 9*a*a*g*g*h + a*a*e*h*h - 9*a*b*e*h*h +
+ 27*b*b*e*h*h + 6*a*a*f*h*h - 18*a*b*f*h*h - 9*b*b*f*h*h + 3*a*a*g*h*h +
+ 6*a*b*g*h*h - a*a*h*h*h + 9*c*c*(e*e*(g - 3*h) - 3*f*f*h + e*(3*f + 2*g)*h) +
+ d*d*(e*e*e - 9*f*f*f + 9*e*f*(f + g) - e*e*(3*f + 6*g + h)) +
+ d*(-3*c*(-9*f*f*g + e*e*(2*f - 6*g - 3*h) + e*(9*f*g + 6*g*g + f*h)) +
+ a*(-18*f*f*f - 18*e*g*g + 18*g*g*g - 2*e*e*h + 3*e*g*h + 2*e*h*h + 9*f*f*(3*g + 2*h) +
+ 3*f*(6*e*g - 9*g*g - e*h - 6*g*h)) - 3*b*(9*f*g*g + e*e*(4*g - 3*h) - 6*f*f*h -
+ e*(6*f*f + g*(18*g + h) - 3*f*(3*g + 4*h)))) +
+ 3*c*(3*b*(e*e*h + 3*f*g*h - e*(3*f*g - 6*f*h + 6*g*h + h*h)) +
+ a*(9*f*f*(g - 2*h) + f*h*(-e + 9*g + 4*h) - 3*(2*g*g*h + e*(2*g*g - 4*g*h + h*h))))) )
+ ;
+}
+
+static double calc_xy(double a, double b, double c, double d,
+ double e, double f, double g, double h) {
+ return
+// + x*3*
+(-2*a*d*e*e - 7*d*d*e*e + 15*a*d*e*f + 21*d*d*e*f - 9*a*d*f*f - 18*d*d*f*f - 15*a*d*e*g -
+ 3*d*d*e*g - 9*a*a*f*g + 9*d*d*f*g + 18*a*a*g*g + 9*a*d*g*g + 2*a*a*e*h - 2*d*d*e*h +
+ 3*a*a*f*h + 15*a*d*f*h - 21*a*a*g*h - 15*a*d*g*h + 7*a*a*h*h + 2*a*d*h*h -
+ 9*c*c*(2*e*e + 3*f*f + 3*f*h - 2*g*h + e*(-3*f - 4*g + h)) +
+ 9*b*b*(3*g*g - 3*g*h + 2*h*(-2*f + h) + e*(-2*f + 3*g + h)) +
+ 3*b*(3*c*(e*e + 3*e*(f - 3*g) + (9*f - 3*g - h)*h) + a*(6*f*f + e*g - 9*f*g - 9*g*g - 5*e*h + 9*f*h + 14*g*h - 7*h*h) +
+ d*(-e*e + 12*f*f - 27*f*g + e*(-9*f + 20*g - 5*h) + g*(9*g + h))) +
+ 3*c*(a*(-(e*f) - 9*f*f + 27*f*g - 12*g*g + 5*e*h - 20*f*h + 9*g*h + h*h) +
+ d*(7*e*e + 9*f*f + 9*f*g - 6*g*g - f*h + e*(-14*f - 9*g + 5*h)))) // *y
+ ;
+}
+
+// - x*3*Power(a - 3*b + 3*c - d,2)*(e - 3*f + 3*g - h)*Power(y,2)
+static double calc_xyy(double a3b3cd, double e3f3gh) {
+ return -3 * a3b3cd * a3b3cd * e3f3gh;
+}
+
+#endif
+
static double (*calc_proc[])(double a, double b, double c, double d,
double e, double f, double g, double h) = {
- calc_E, calc_F, calc_G, calc_H, calc_I, calc_J
+ calc_xx, calc_xy, calc_yy, calc_x, calc_y, calc_c
};
+#if USE_SYVESTER
/* Control points to parametric coefficients
s = 1 - t
Attt + 3Btts + 3Ctss + Dsss ==
@@ -281,9 +403,24 @@
const bool try_alt = true;
+#else
+
+static void calc_ABCD(double a, double b, double c, double d,
+ double e, double f, double g, double h,
+ double p[coeff_count]) {
+ double a3b3cd = a - 3 * (b - c) - d;
+ double e3f3gh = e - 3 * (f - g) - h;
+ p[xxx_coeff] = calc_xxx(e3f3gh);
+ p[xxy_coeff] = calc_xxy(a3b3cd, e3f3gh);
+ p[xyy_coeff] = calc_xyy(a3b3cd, e3f3gh);
+ p[yyy_coeff] = calc_yyy(a3b3cd);
+}
+#endif
+
bool implicit_matches(const Cubic& one, const Cubic& two) {
double p1[coeff_count]; // a'xxx , b'xxy , c'xyy , d'xx , e'xy , f'yy, etc.
double p2[coeff_count];
+#if USE_SYVESTER
double a1, b1, c1, d1;
if (try_alt)
alt_set_abcd(&one[0].x, a1, b1, c1, d1);
@@ -306,14 +443,36 @@
else
set_abcd(&two[0].y, e2, f2, g2, h2);
calc_ABCD(a2, e2, p2);
+#else
+ double a1 = one[0].x;
+ double b1 = one[1].x;
+ double c1 = one[2].x;
+ double d1 = one[3].x;
+ double e1 = one[0].y;
+ double f1 = one[1].y;
+ double g1 = one[2].y;
+ double h1 = one[3].y;
+ calc_ABCD(a1, b1, c1, d1, e1, f1, g1, h1, p1);
+ double a2 = two[0].x;
+ double b2 = two[1].x;
+ double c2 = two[2].x;
+ double d2 = two[3].x;
+ double e2 = two[0].y;
+ double f2 = two[1].y;
+ double g2 = two[2].y;
+ double h2 = two[3].y;
+ calc_ABCD(a2, b2, c2, d2, e2, f2, g2, h2, p2);
+#endif
int first = 0;
for (int index = 0; index < coeff_count; ++index) {
+#if USE_SYVESTER
if (!try_alt && index == xx_coeff) {
calc_bc(d1, b1, c1);
calc_bc(h1, f1, g1);
calc_bc(d2, b2, c2);
calc_bc(h2, f2, g2);
}
+#endif
if (index >= xx_coeff) {
int procIndex = index - xx_coeff;
p1[index] = (*calc_proc[procIndex])(a1, b1, c1, d1, e1, f1, g1, h1);
@@ -336,8 +495,12 @@
static double tangent(const double* cubic, double t) {
double a, b, c, d;
+#if USE_SYVESTER
set_abcd(cubic, a, b, c, d);
calc_bc(d, b, c);
+#else
+ coefficients(cubic, a, b, c, d);
+#endif
return 3 * a * t * t + 2 * b * t + c;
}
diff --git a/experimental/Intersection/CubicParameterizationCode.cpp b/experimental/Intersection/CubicParameterizationCode.cpp
index d799b15..15767dd 100644
--- a/experimental/Intersection/CubicParameterizationCode.cpp
+++ b/experimental/Intersection/CubicParameterizationCode.cpp
@@ -70,9 +70,83 @@
" 3 a^2 d e y^2 + a b^2 f y^2 - 2 a^2 c f y^2 - a^2 b g y^2 + "
" 3 a^3 h y^2 + 3 a^2 e x y^2 - a^3 y^3";
-
const size_t len2 = sizeof(result2) - 1;
+/* Given: r1 = Resultant[
+ * a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - x,
+ * e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, t]
+ * Collect[r1, {x, y}, Simplify]
+ * CForm[%]
+ * then use regex to replace Power\(([a-h]),3\) with \1*\1*\1
+ * and Power\(([a-h]),2\) with \1*\1
+ * yields:
+
+d*d*d*e*e*e - 3*d*d*(3*c*e*e*f + 3*b*e*(-3*f*f + 2*e*g) + a*(9*f*f*f - 9*e*f*g + e*e*h)) -
+ h*(27*c*c*c*e*e - 27*c*c*(3*b*e*f - 3*a*f*f + 2*a*e*g) +
+ h*(-27*b*b*b*e + 27*a*b*b*f - 9*a*a*b*g + a*a*a*h) +
+ 9*c*(9*b*b*e*g + a*b*(-9*f*g + 3*e*h) + a*a*(3*g*g - 2*f*h))) +
+ 3*d*(9*c*c*e*e*g + 9*b*b*e*(3*g*g - 2*f*h) + 3*a*b*(-9*f*g*g + 6*f*f*h + e*g*h) +
+ a*a*(9*g*g*g - 9*f*g*h + e*h*h) + 3*c*(3*b*e*(-3*f*g + e*h) + a*(9*f*f*g - 6*e*g*g - e*f*h)))
+
+- Power(e - 3*f + 3*g - h,3)*Power(x,3)
+
++ 3*(6*b*d*d*e*e - d*d*d*e*e + 18*b*b*d*e*f - 18*b*d*d*e*f -
+ 9*b*d*d*f*f - 54*b*b*d*e*g + 12*b*d*d*e*g - 27*b*b*d*g*g - 18*b*b*b*e*h + 18*b*b*d*e*h +
+ 18*b*b*d*f*h + a*a*a*h*h - 9*b*b*b*h*h + 9*c*c*c*e*(e + 2*h) +
+ a*a*(-3*b*h*(2*g + h) + d*(-27*g*g + 9*g*h - h*(2*e + h) + 9*f*(g + h))) +
+ a*(9*b*b*h*(2*f + h) - 3*b*d*(6*f*f - 6*f*(3*g - 2*h) + g*(-9*g + h) + e*(g + h)) +
+ d*d*(e*e + 9*f*(3*f - g) + e*(-9*f - 9*g + 2*h))) -
+ 9*c*c*(d*e*(e + 2*g) + 3*b*(f*h + e*(f + h)) + a*(-3*f*f - 6*f*h + 2*(g*h + e*(g + h)))) +
+ 3*c*(d*d*e*(e + 2*f) + a*a*(3*g*g + 6*g*h - 2*h*(2*f + h)) + 9*b*b*(g*h + e*(g + h)) +
+ a*d*(-9*f*f - 18*f*g + 6*g*g + f*h + e*(f + 12*g + h)) +
+ b*(d*(-3*e*e + 9*f*g + e*(9*f + 9*g - 6*h)) + 3*a*(h*(2*e - 3*g + h) - 3*f*(g + h)))))*y
+
+- 3*(18*c*c*c*e - 18*c*c*d*e + 6*c*d*d*e - d*d*d*e + 3*c*d*d*f - 9*c*c*d*g + a*a*a*h + 9*c*c*c*h -
+ 9*b*b*b*(e + 2*h) - a*a*(d*(e - 9*f + 18*g - 7*h) + 3*c*(2*f - 6*g + h)) +
+ a*(-9*c*c*(2*e - 6*f + 2*g - h) + d*d*(-7*e + 18*f - 9*g + h) + 3*c*d*(7*e - 17*f + 3*g + h)) +
+ 9*b*b*(3*c*(e + g + h) + a*(f + 2*h) - d*(e - 2*(f - 3*g + h))) -
+ 3*b*(-(d*d*(e - 6*f + 2*g)) - 3*c*d*(e + 3*f + 3*g - h) + 9*c*c*(e + f + h) + a*a*(g + 2*h) +
+ a*(c*(-3*e + 9*f + 9*g + 3*h) + d*(e + 3*f - 17*g + 7*h))))*Power(y,2)
+
++ Power(a - 3*b + 3*c - d,3)*Power(y,3)
+
++ Power(x,2)*(-3*(-9*b*e*f*f + 9*a*f*f*f + 6*b*e*e*g - 9*a*e*f*g + 27*b*e*f*g - 27*a*f*f*g + 18*a*e*g*g - 54*b*e*g*g +
+ 27*a*f*g*g + 27*b*f*g*g - 18*a*g*g*g + a*e*e*h - 9*b*e*e*h + 3*a*e*f*h + 9*b*e*f*h + 9*a*f*f*h -
+ 18*b*f*f*h - 21*a*e*g*h + 51*b*e*g*h - 9*a*f*g*h - 27*b*f*g*h + 18*a*g*g*h + 7*a*e*h*h - 18*b*e*h*h - 3*a*f*h*h +
+ 18*b*f*h*h - 6*a*g*h*h - 3*b*g*h*h + a*h*h*h +
+ 3*c*(-9*f*f*(g - 2*h) + 3*g*g*h - f*h*(9*g + 2*h) + e*e*(f - 6*g + 6*h) +
+ e*(9*f*g + 6*g*g - 17*f*h - 3*g*h + 3*h*h)) -
+ d*(e*e*e + e*e*(-6*f - 3*g + 7*h) - 9*(2*f - g)*(f*f + g*g - f*(g + h)) +
+ e*(18*f*f + 9*g*g + 3*g*h + h*h - 3*f*(3*g + 7*h)))) )
+
++ Power(x,2)*(3*(a - 3*b + 3*c - d)*Power(e - 3*f + 3*g - h,2)*y)
+
++ x*(-3*(27*b*b*e*g*g - 27*a*b*f*g*g + 9*a*a*g*g*g - 18*b*b*e*f*h + 18*a*b*f*f*h + 3*a*b*e*g*h -
+ 27*b*b*e*g*h - 9*a*a*f*g*h + 27*a*b*f*g*h - 9*a*a*g*g*h + a*a*e*h*h - 9*a*b*e*h*h +
+ 27*b*b*e*h*h + 6*a*a*f*h*h - 18*a*b*f*h*h - 9*b*b*f*h*h + 3*a*a*g*h*h +
+ 6*a*b*g*h*h - a*a*h*h*h + 9*c*c*(e*e*(g - 3*h) - 3*f*f*h + e*(3*f + 2*g)*h) +
+ d*d*(e*e*e - 9*f*f*f + 9*e*f*(f + g) - e*e*(3*f + 6*g + h)) +
+ d*(-3*c*(-9*f*f*g + e*e*(2*f - 6*g - 3*h) + e*(9*f*g + 6*g*g + f*h)) +
+ a*(-18*f*f*f - 18*e*g*g + 18*g*g*g - 2*e*e*h + 3*e*g*h + 2*e*h*h + 9*f*f*(3*g + 2*h) +
+ 3*f*(6*e*g - 9*g*g - e*h - 6*g*h)) - 3*b*(9*f*g*g + e*e*(4*g - 3*h) - 6*f*f*h -
+ e*(6*f*f + g*(18*g + h) - 3*f*(3*g + 4*h)))) +
+ 3*c*(3*b*(e*e*h + 3*f*g*h - e*(3*f*g - 6*f*h + 6*g*h + h*h)) +
+ a*(9*f*f*(g - 2*h) + f*h*(-e + 9*g + 4*h) - 3*(2*g*g*h + e*(2*g*g - 4*g*h + h*h))))) )
+
++ x*3*(-2*a*d*e*e - 7*d*d*e*e + 15*a*d*e*f + 21*d*d*e*f - 9*a*d*f*f - 18*d*d*f*f - 15*a*d*e*g -
+ 3*d*d*e*g - 9*a*a*f*g + 9*d*d*f*g + 18*a*a*g*g + 9*a*d*g*g + 2*a*a*e*h - 2*d*d*e*h +
+ 3*a*a*f*h + 15*a*d*f*h - 21*a*a*g*h - 15*a*d*g*h + 7*a*a*h*h + 2*a*d*h*h -
+ 9*c*c*(2*e*e + 3*f*f + 3*f*h - 2*g*h + e*(-3*f - 4*g + h)) +
+ 9*b*b*(3*g*g - 3*g*h + 2*h*(-2*f + h) + e*(-2*f + 3*g + h)) +
+ 3*b*(3*c*(e*e + 3*e*(f - 3*g) + (9*f - 3*g - h)*h) + a*(6*f*f + e*g - 9*f*g - 9*g*g - 5*e*h + 9*f*h + 14*g*h - 7*h*h) +
+ d*(-e*e + 12*f*f - 27*f*g + e*(-9*f + 20*g - 5*h) + g*(9*g + h))) +
+ 3*c*(a*(-(e*f) - 9*f*f + 27*f*g - 12*g*g + 5*e*h - 20*f*h + 9*g*h + h*h) +
+ d*(7*e*e + 9*f*f + 9*f*g - 6*g*g - f*h + e*(-14*f - 9*g + 5*h))))*y
+
+- x*3*Power(a - 3*b + 3*c - d,2)*(e - 3*f + 3*g - h)*Power(y,2)
+
+*/
+
const int factors = 8;
struct coeff {
diff --git a/experimental/Intersection/CubicParameterization_Test.cpp b/experimental/Intersection/CubicParameterization_Test.cpp
index 18322c8..716aaec 100644
--- a/experimental/Intersection/CubicParameterization_Test.cpp
+++ b/experimental/Intersection/CubicParameterization_Test.cpp
@@ -1,5 +1,6 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersection_Tests.h"
+#include "Parameterization_Test.h"
#include "TestUtilities.h"
const Quadratic quadratics[] = {
@@ -47,16 +48,16 @@
// The on curve points of each cubic should be on both parameterized cubics.
const Cubic cubics[] = {
{
- {1, -1},
- {.333, 1},
- {-.333, -1},
- {-1, 1}
+ { 1, -1},
+ { 1.0/3, 1},
+ {-1.0/3, -1},
+ {-1, 1}
},
{
- {-1, 1},
- {-.333, -1},
- {.333, 1},
- {1, -1}
+ {-1, 1},
+ {-1.0/3, -1},
+ { 1.0/3, 1},
+ { 1, -1}
},
{
{0, 2},
@@ -98,5 +99,8 @@
__FUNCTION__, index, inner);
}
}
+ if (!implicit_matches(cubics[index], cubics[index ^ 1])) {
+ printf("%s %d\n", __FUNCTION__, (int)index);
+ }
}
}
diff --git a/experimental/Intersection/CubicParameterization_TestUtility.cpp b/experimental/Intersection/CubicParameterization_TestUtility.cpp
index 2423a7c..356ca88 100644
--- a/experimental/Intersection/CubicParameterization_TestUtility.cpp
+++ b/experimental/Intersection/CubicParameterization_TestUtility.cpp
@@ -1,7 +1,10 @@
// included by CubicParameterization.cpp
// accesses internal functions to validate parameterized coefficients
+#include "Parameterization_Test.h"
+
static void parameter_coeffs(const Cubic& cubic, double coeffs[coeff_count]) {
+#if USE_SYVESTER
double ax, bx, cx, dx;
if (try_alt)
alt_set_abcd(&cubic[0].x, ax, bx, cx, dx);
@@ -15,6 +18,17 @@
calc_ABCD(ax, ay, coeffs);
if (!try_alt) calc_bc(dx, bx, cx);
if (!try_alt) calc_bc(dy, by, cy);
+#else
+ double ax = cubic[0].x;
+ double bx = cubic[1].x;
+ double cx = cubic[2].x;
+ double dx = cubic[3].x;
+ double ay = cubic[0].y;
+ double by = cubic[1].y;
+ double cy = cubic[2].y;
+ double dy = cubic[3].y;
+ calc_ABCD(ax, bx, cx, dx, ay, by, cy, dy, coeffs);
+#endif
for (int index = xx_coeff; index < coeff_count; ++index) {
int procIndex = index - xx_coeff;
coeffs[index] = (*calc_proc[procIndex])(ax, bx, cx, dx, ay, by, cy, dy);
diff --git a/experimental/Intersection/CubicReduceOrder.cpp b/experimental/Intersection/CubicReduceOrder.cpp
index b7e0ea9..fee179a 100644
--- a/experimental/Intersection/CubicReduceOrder.cpp
+++ b/experimental/Intersection/CubicReduceOrder.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Extrema.h"
#include "IntersectionUtilities.h"
#include "LineParameters.h"
diff --git a/experimental/Intersection/CubicReduceOrder_Test.cpp b/experimental/Intersection/CubicReduceOrder_Test.cpp
index 1957ba1..98662e2 100644
--- a/experimental/Intersection/CubicReduceOrder_Test.cpp
+++ b/experimental/Intersection/CubicReduceOrder_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "CubicIntersection_TestData.h"
#include "Intersection_Tests.h"
#include "QuadraticIntersection_TestData.h"
diff --git a/experimental/Intersection/CubicSubDivide.cpp b/experimental/Intersection/CubicSubDivide.cpp
index b8202fe..0c6ed42 100644
--- a/experimental/Intersection/CubicSubDivide.cpp
+++ b/experimental/Intersection/CubicSubDivide.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "IntersectionUtilities.h"
/*
diff --git a/experimental/Intersection/CubicUtilities.cpp b/experimental/Intersection/CubicUtilities.cpp
new file mode 100644
index 0000000..3fab29e
--- /dev/null
+++ b/experimental/Intersection/CubicUtilities.cpp
@@ -0,0 +1,76 @@
+#include "CubicUtilities.h"
+#include "DataTypes.h"
+#include "QuadraticUtilities.h"
+
+void coefficients(const double* cubic, double& A, double& B, double& C, double& D) {
+ A = cubic[6]; // d
+ B = cubic[4] * 3; // 3*c
+ C = cubic[2] * 3; // 3*b
+ D = cubic[0]; // a
+ A -= D - C + B; // A = -a + 3*b - 3*c + d
+ B += 3 * D - 2 * C; // B = 3*a - 6*b + 3*c
+ C -= 3 * D; // C = -3*a + 3*b
+}
+
+// cubic roots
+
+const double PI = 4 * atan(1);
+
+static bool is_unit_interval(double x) {
+ return x > 0 && x < 1;
+}
+
+// from SkGeometry.cpp (and Numeric Solutions, 5.6)
+int cubicRoots(double A, double B, double C, double D, double t[3]) {
+ if (approximately_zero(A)) { // we're just a quadratic
+ return quadraticRoots(B, C, D, t);
+ }
+ double a, b, c;
+ {
+ double invA = 1 / A;
+ a = B * invA;
+ b = C * invA;
+ c = D * invA;
+ }
+ double a2 = a * a;
+ double Q = (a2 - b * 3) / 9;
+ double R = (2 * a2 * a - 9 * a * b + 27 * c) / 54;
+ double Q3 = Q * Q * Q;
+ double R2MinusQ3 = R * R - Q3;
+ double adiv3 = a / 3;
+ double* roots = t;
+ double r;
+
+ if (R2MinusQ3 < 0) // we have 3 real roots
+ {
+ double theta = acos(R / sqrt(Q3));
+ double neg2RootQ = -2 * sqrt(Q);
+
+ r = neg2RootQ * cos(theta / 3) - adiv3;
+ if (is_unit_interval(r))
+ *roots++ = r;
+
+ r = neg2RootQ * cos((theta + 2 * PI) / 3) - adiv3;
+ if (is_unit_interval(r))
+ *roots++ = r;
+
+ r = neg2RootQ * cos((theta - 2 * PI) / 3) - adiv3;
+ if (is_unit_interval(r))
+ *roots++ = r;
+ }
+ else // we have 1 real root
+ {
+ double A = fabs(R) + sqrt(R2MinusQ3);
+ A = cube_root(A);
+ if (R > 0) {
+ A = -A;
+ }
+ if (A != 0) {
+ A += Q / A;
+ }
+ r = A - adiv3;
+ if (is_unit_interval(r))
+ *roots++ = r;
+ }
+ return (int)(roots - t);
+}
diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h
index db887a5..7a99c95 100644
--- a/experimental/Intersection/CubicUtilities.h
+++ b/experimental/Intersection/CubicUtilities.h
@@ -1,2 +1,3 @@
double cube_root(double x);
+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]);
diff --git a/experimental/Intersection/CurveIntersection.h b/experimental/Intersection/CurveIntersection.h
new file mode 100644
index 0000000..d6ca837
--- /dev/null
+++ b/experimental/Intersection/CurveIntersection.h
@@ -0,0 +1,34 @@
+#include "DataTypes.h"
+
+class Intersections;
+
+// unit-testable utilities
+bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT);
+bool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT);
+void chop_at(const Cubic& src, CubicPair& dst, double t);
+void chop_at(const Quadratic& src, QuadraticPair& dst, double t);
+int convex_hull(const Cubic& cubic, char order[4]);
+bool convex_x_hull(const Cubic& cubic, char connectTo0[2], char connectTo3[2]);
+bool implicit_matches(const Cubic& cubic1, const Cubic& cubic2);
+bool implicit_matches(const _Line& line1, const _Line& line2);
+bool implicit_matches(const Quadratic& quad1, const Quadratic& quad2);
+void sub_divide(const Cubic& src, double t1, double t2, Cubic& dst);
+void sub_divide(const _Line& src, double t1, double t2, Cubic& dst);
+void sub_divide(const Quadratic& src, double t1, double t2, Quadratic& dst);
+void tangent(const Cubic& cubic, double t, _Point& result);
+void tangent(const _Line& line, _Point& result);
+void tangent(const Quadratic& quad, double t, _Point& result);
+
+// main functions
+enum ReduceOrder_Flags {
+ kReduceOrder_NoQuadraticsAllowed,
+ kReduceOrder_QuadraticsAllowed
+};
+int reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Flags );
+int reduceOrder(const _Line& line, _Line& reduction);
+int reduceOrder(const Quadratic& quad, Quadratic& reduction);
+int horizontalIntersect(const Cubic& cubic, double y, double tRange[3]);
+bool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& );
+int intersect(const Cubic& cubic, const _Line& line, double cRange[3], double lRange[3]);
+bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& );
+bool intersect(const Quadratic& quad, const _Line& line, Intersections& );
diff --git a/experimental/Intersection/DataTypes.cpp b/experimental/Intersection/DataTypes.cpp
index 4cb2275..8f46e8e 100644
--- a/experimental/Intersection/DataTypes.cpp
+++ b/experimental/Intersection/DataTypes.cpp
@@ -72,3 +72,30 @@
setMinMax(x, p1.y, p2.y, bottomFlags, minX, maxX);
}
}
+
+void xy_at_t(const Cubic& cubic, double t, double& x, double& y) {
+ double one_t = 1 - t;
+ double one_t2 = one_t * one_t;
+ double a = one_t2 * one_t;
+ double b = 3 * one_t2 * t;
+ double t2 = t * t;
+ double c = 3 * one_t * t2;
+ double d = t2 * t;
+ x = a * cubic[0].x + b * cubic[1].x + c * cubic[2].x + d * cubic[3].x;
+ y = a * cubic[0].y + b * cubic[1].y + c * cubic[2].y + d * cubic[3].y;
+}
+
+void xy_at_t(const _Line& line, double t, double& x, double& y) {
+ double one_t = 1 - t;
+ x = one_t * line[0].x + t * line[1].x;
+ y = one_t * line[0].y + t * line[1].y;
+}
+
+void xy_at_t(const Quadratic& quad, double t, double& x, double& y) {
+ double one_t = 1 - t;
+ double a = one_t * one_t;
+ double b = 2 * one_t * t;
+ double c = t * t;
+ x = a * quad[0].x + b * quad[1].x + c * quad[2].x;
+ y = a * quad[0].y + b * quad[1].y + c * quad[2].y;
+}
diff --git a/experimental/Intersection/DataTypes.h b/experimental/Intersection/DataTypes.h
index b1cbdf7..94373cd 100644
--- a/experimental/Intersection/DataTypes.h
+++ b/experimental/Intersection/DataTypes.h
@@ -80,11 +80,20 @@
}
}
+ void set(const _Point& pt) {
+ left = right = pt.x;
+ top = bottom = pt.y;
+ }
+
void setBounds(const _Line& line) {
- left = right = line[0].x;
- top = bottom = line[0].y;
+ set(line[0]);
add(line[1]);
}
+
+ void setBounds(const Cubic& );
+ void setBounds(const Quadratic& );
+ void setRawBounds(const Cubic& );
+ void setRawBounds(const Quadratic& );
};
struct CubicPair {
@@ -110,5 +119,8 @@
double t_at(const _Line&, const _Point& );
void x_at(const _Point& p1, const _Point& p2, double minY, double maxY,
int flags, double& tMin, double& tMax);
+void xy_at_t(const Cubic& , double t, double& x, double& y);
+void xy_at_t(const _Line& , double t, double& x, double& y);
+void xy_at_t(const Quadratic& , double t, double& x, double& y);
#endif // __DataTypes_h__
diff --git a/experimental/Intersection/EdgeWalker.cpp b/experimental/Intersection/EdgeWalker.cpp
new file mode 100644
index 0000000..bf090e7
--- /dev/null
+++ b/experimental/Intersection/EdgeWalker.cpp
@@ -0,0 +1,498 @@
+
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "LineIntersection.h"
+#include "SkPath.h"
+#include "SkRect.h"
+#include "SkTArray.h"
+#include "SkTDArray.h"
+#include "TSearch.h"
+
+static int lineIntersect(const SkPoint a[2], const SkPoint b[2],
+ double aRange[2], double bRange[2]) {
+ _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}};
+ return intersect(aLine, bLine, aRange, bRange);
+}
+
+static int lineIntersect(const SkPoint a[2], SkScalar y, double aRange[2]) {
+ _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}};
+ return horizontalIntersect(aLine, y, aRange);
+}
+
+// functions
+void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray);
+void simplify(const SkPath& path, bool asFill, SkPath& simple);
+/*
+list of edges
+bounds for edge
+sort
+active T
+
+if a contour's bounds is outside of the active area, no need to create edges
+*/
+
+/* given one or more paths,
+ find the bounds of each contour, select the active contours
+ for each active contour, compute a set of edges
+ each edge corresponds to one or more lines and curves
+ leave edges unbroken as long as possible
+ when breaking edges, compute the t at the break but leave the control points alone
+
+ */
+
+void contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) {
+ SkPath::Iter iter(path, false);
+ SkPoint pts[4];
+ SkPath::Verb verb;
+ SkRect bounds;
+ bounds.setEmpty();
+ int count = 0;
+ while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+ switch (verb) {
+ case SkPath::kMove_Verb:
+ if (!bounds.isEmpty()) {
+ *boundsArray.append() = bounds;
+ }
+ bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY);
+ count = 0;
+ break;
+ case SkPath::kLine_Verb:
+ count = 1;
+ break;
+ case SkPath::kQuad_Verb:
+ count = 2;
+ break;
+ case SkPath::kCubic_Verb:
+ count = 3;
+ break;
+ case SkPath::kClose_Verb:
+ count = 0;
+ break;
+ default:
+ SkDEBUGFAIL("bad verb");
+ return;
+ }
+ for (int i = 1; i <= count; ++i) {
+ bounds.growToInclude(pts[i].fX, pts[i].fY);
+ }
+ }
+}
+
+// Bounds, unlike Rect, does not consider a vertical line to be empty.
+struct Bounds : public SkRect {
+ static bool Intersects(const Bounds& a, const Bounds& b) {
+ return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
+ a.fTop <= b.fBottom && b.fTop <= a.fBottom;
+ }
+};
+
+struct Edge;
+
+struct Intercepts {
+ SkTDArray<double> fTs;
+};
+
+struct Edge {
+ bool operator<(const Edge& rh) const {
+ return fBounds.fTop == rh.fBounds.fTop
+ ? fBounds.fLeft < rh.fBounds.fLeft
+ : fBounds.fTop < rh.fBounds.fTop;
+ }
+
+ void add(double* ts, size_t count, int verbIndex) {
+ Intercepts& intercepts = fIntercepts[verbIndex];
+ // FIXME: in the pathological case where there is a ton of intercepts, binary search?
+ for (size_t index = 0; index < count; ++index) {
+ double t = ts[index];
+ size_t tCount = intercepts.fTs.count();
+ for (size_t idx2 = 0; idx2 < tCount; ++idx2) {
+ if (t <= intercepts.fTs[idx2]) {
+ if (t < intercepts.fTs[idx2]) {
+ *intercepts.fTs.insert(idx2) = t;
+ break;
+ }
+ }
+ }
+ if (tCount == 0 || t > intercepts.fTs[tCount - 1]) {
+ *intercepts.fTs.append() = t;
+ }
+ }
+ }
+
+ bool cached(const Edge* edge) {
+ // FIXME: in the pathological case where there is a ton of edges, binary search?
+ size_t count = fCached.count();
+ for (size_t index = 0; index < count; ++index) {
+ if (edge == fCached[index]) {
+ return true;
+ }
+ if (edge < fCached[index]) {
+ *fCached.insert(index) = edge;
+ return false;
+ }
+ }
+ *fCached.append() = edge;
+ return false;
+ }
+
+ void complete(signed char winding) {
+ SkPoint* ptPtr = fPts.begin();
+ SkPoint* ptLast = fPts.end();
+ if (ptPtr == ptLast) {
+ SkDebugf("empty edge\n");
+ SkASSERT(0);
+ // FIXME: delete empty edge?
+ return;
+ }
+ fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY);
+ ++ptPtr;
+ while (ptPtr != ptLast) {
+ fBounds.growToInclude(ptPtr->fX, ptPtr->fY);
+ ++ptPtr;
+ }
+ fIntercepts.push_back_n(1);
+ fWinding = winding;
+ }
+
+ // temporary data : move this to a separate struct?
+ SkTDArray<const Edge*> fCached; // list of edges already intercepted
+ SkTArray<Intercepts> fIntercepts; // one per verb
+
+
+ // persistent data
+ SkTDArray<SkPoint> fPts;
+ SkTDArray<uint8_t> fVerbs;
+ Bounds fBounds;
+ signed char fWinding;
+};
+
+class EdgeBuilder {
+public:
+
+EdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<Edge>& edges)
+ : fPath(path)
+ , fCurrentEdge(NULL)
+ , fEdges(edges)
+ , fIgnoreHorizontal(ignoreHorizontal)
+{
+ walk();
+}
+
+protected:
+
+void addEdge() {
+ fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]);
+ fPtOffset = 1;
+ *fCurrentEdge->fVerbs.append() = fVerb;
+}
+
+int direction(int count) {
+ fPtCount = count;
+ fIgnorableHorizontal = fIgnoreHorizontal && isHorizontal();
+ if (fIgnorableHorizontal) {
+ return 0;
+ }
+ int last = count - 1;
+ return fPts[0].fY == fPts[last].fY
+ ? fPts[0].fX == fPts[last].fX ? 0 : fPts[0].fX > fPts[last].fX
+ ? 1 : -1 : fPts[0].fY > fPts[last].fY ? 1 : -1;
+}
+
+bool isHorizontal() {
+ SkScalar y = fPts[0].fY;
+ for (int i = 1; i < fPtCount; ++i) {
+ if (fPts[i].fY != y) {
+ return false;
+ }
+ }
+ return true;
+}
+
+void startEdge() {
+ fCurrentEdge = fEdges.push_back_n(1);
+ fWinding = 0;
+ fPtOffset = 0;
+}
+
+void walk() {
+ SkPath::Iter iter(fPath, true);
+ int winding = 0;
+ while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) {
+ switch (fVerb) {
+ case SkPath::kMove_Verb:
+ winding = 0;
+ startEdge();
+ continue;
+ case SkPath::kLine_Verb:
+ winding = direction(2);
+ break;
+ case SkPath::kQuad_Verb:
+ winding = direction(3);
+ break;
+ case SkPath::kCubic_Verb:
+ winding = direction(4);
+ break;
+ case SkPath::kClose_Verb:
+ if (fCurrentEdge->fVerbs.count()) {
+ fCurrentEdge->complete(fWinding);
+ }
+ continue;
+ default:
+ SkDEBUGFAIL("bad verb");
+ return;
+ }
+ if (fIgnorableHorizontal) {
+ continue;
+ }
+ if (fWinding + winding == 0) {
+ // FIXME: if prior verb or this verb is a horizontal line, reverse
+ // it instead of starting a new edge
+ fCurrentEdge->complete(fWinding);
+ startEdge();
+ }
+ fWinding = winding;
+ addEdge();
+ }
+ fCurrentEdge->complete(fWinding);
+}
+
+private:
+ const SkPath& fPath;
+ Edge* fCurrentEdge;
+ SkTArray<Edge>& fEdges;
+ SkPoint fPts[4];
+ SkPath::Verb fVerb;
+ int fPtCount;
+ int fPtOffset;
+ int8_t fWinding;
+ bool fIgnorableHorizontal;
+ bool fIgnoreHorizontal;
+};
+
+class WorkEdge {
+public:
+ WorkEdge(const Edge* edge) {
+ fVerbStart = edge->fVerbs.begin();
+ if ((fWinding = edge->fWinding) > 0) {
+ fPts = edge->fPts.begin();
+ fVerb = fVerbStart;
+ fVerbEnd = edge->fVerbs.end();
+ } else {
+ fPts = edge->fPts.end();
+ fVerb = edge->fVerbs.end();
+ fVerbEnd = fVerbStart;
+ next();
+ }
+ }
+
+ SkScalar bottom() const {
+ return fPts[fWinding > 0 ? verb() : 0].fY;
+ }
+
+ bool next() {
+ if (fWinding > 0) {
+ fPts += *fVerb;
+ return ++fVerb != fVerbEnd;
+ } else {
+ if (fVerb == fVerbEnd) {
+ return false;
+ }
+ fPts -= *--fVerb;
+ return true;
+ }
+ }
+
+ const SkPoint* points() const {
+ return fPts;
+ }
+
+ SkPath::Verb verb() const {
+ return (SkPath::Verb) *fVerb;
+ }
+
+ int verbIndex() const {
+ return fVerb - fVerbStart;
+ }
+
+protected:
+ const SkPoint* fPts;
+ const uint8_t* fVerb;
+ const uint8_t* fVerbEnd;
+ const uint8_t* fVerbStart;
+ int8_t fWinding;
+};
+
+struct ActiveEdge {
+ void init(const Edge* test) {
+ fEdge = test;
+ if (!fEdge->fIntercepts.count()) {
+ fBounds = test->fBounds;
+ fPtStart = 0;
+ fPtEnd = test->fPts.count();
+ fVerbStart = 0;
+ fVerbEnd = test->fVerbs.count();
+ fTStart = 0;
+ fTEnd = SK_Scalar1;
+ } else {
+ // FIXME: initialize from intercepts
+
+ }
+ }
+
+ const Edge* fEdge;
+ SkRect fBounds;
+ int fPtStart;
+ int fPtEnd;
+ int fVerbStart;
+ int fVerbEnd;
+ SkScalar fTStart;
+ SkScalar fTEnd;
+};
+
+void simplify(const SkPath& path, bool asFill, SkPath& simple) {
+ // turn path into list of edges increasing in y
+ // if an edge is a quad or a cubic with a y extrema, note it, but leave it unbroken
+ // once we have a list, sort it, then walk the list (walk edges twice that have y extrema's on top)
+ // and detect crossings -- look for raw bounds that cross over, then tight bounds that cross
+ SkTArray<Edge> edges;
+ EdgeBuilder builder(path, asFill, edges);
+ size_t edgeCount = edges.count();
+ simple.reset();
+ if (edgeCount == 0) {
+ return;
+ }
+ // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
+ int windingMask = (path.getFillType() & 1) ? 1 : -1;
+ SkTDArray<Edge*> edgeList;
+ for (size_t index = 0; index < edgeCount; ++index) {
+ *edgeList.append() = &edges[index];
+ }
+ Edge edgeSentinel;
+ edgeSentinel.fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
+ *edgeList.append() = &edgeSentinel;
+ ++edgeCount;
+ QSort<Edge>(edgeList.begin(), edgeCount);
+ Edge** currentPtr = edgeList.begin();
+ Edge* current = *currentPtr;
+ SkScalar y = current->fBounds.fTop;
+ SkScalar bottom = current->fBounds.fBottom;
+ // walk the sorted edges from top to bottom, computing accumulated winding
+ do {
+ // find the list of edges that cross y
+ Edge** lastPtr = currentPtr; // find the edge below the bottom of the first set
+ Edge* last = *lastPtr;
+ while (lastPtr != edgeList.end()) {
+ if (bottom <= last->fBounds.fTop) {
+ break;
+ }
+ SkScalar lastTop = last->fBounds.fTop;
+ // OPTIMIZATION: Shortening the bottom is only interesting when filling
+ // and when the edge is to the left of a longer edge. If it's a framing
+ // edge, or part of the right, it won't effect the longer edges.
+ if (lastTop > y) {
+ if (bottom > lastTop) {
+ bottom = lastTop;
+ break;
+ }
+ } else if (bottom > last->fBounds.fBottom) {
+ bottom = last->fBounds.fBottom;
+ }
+ last = *++lastPtr;
+ }
+ if (asFill && lastPtr - currentPtr <= 1) {
+ SkDebugf("expect 2 or more edges\n");
+ SkASSERT(0);
+ return;
+ }
+ // find any intersections in the range of active edges
+ Edge** testPtr = currentPtr;
+ Edge* test = *testPtr;
+ while (testPtr != lastPtr) {
+ if (test->fBounds.fBottom > bottom) {
+ WorkEdge wt(test);
+ do {
+ // FIXME: add all combinations of curve types
+ if (wt.verb() == SkPath::kLine_Verb) {
+ double wtTs[2];
+ int pts = lineIntersect(wt.points(), bottom, wtTs);
+ if (pts) {
+ test->add(wtTs, pts, wt.verbIndex());
+ }
+ }
+ } while (wt.next());
+ }
+ test = *++testPtr;
+ }
+ testPtr = currentPtr;
+ test = *testPtr;
+ while (testPtr != lastPtr - 1) {
+ Edge* next = *++testPtr;
+ // OPTIMIZATION: if test and next is inside the winding of outer
+ // edges such that intersecting them is irrelevent, skip them.
+ if (!test->cached(next)
+ && Bounds::Intersects(test->fBounds, next->fBounds)) {
+ WorkEdge wt(test);
+ WorkEdge wn(next);
+ do {
+ // FIXME: add all combinations of curve types
+ if (wt.verb() == SkPath::kLine_Verb && wn.verb() == SkPath::kLine_Verb) {
+ double wtTs[2], wnTs[2];
+ int pts = lineIntersect(wt.points(), wn.points(), wtTs, wnTs);
+ if (pts) {
+ test->add(wtTs, pts, wt.verbIndex());
+ next->add(wnTs, pts, wn.verbIndex());
+ }
+ }
+ } while (wt.bottom() <= wn.bottom() ? wt.next() : wn.next());
+ }
+ test = next;
+ }
+ // stitch edge and t range that satisfies operation
+ int winding = 0;
+ testPtr = currentPtr;
+ test = *testPtr;
+ while (testPtr != lastPtr - 1) {
+ int lastWinding = winding;
+ winding += test->fWinding;
+ if ((lastWinding & windingMask) == 0 || (winding & windingMask) == 0) {
+ // append pts, verbs, in front of or behind output
+ // a verb may have one or more inter-T value, but only break
+ // curve if curve at t changes winding inclusion
+ ;
+ }
+ test = *++testPtr;
+ }
+ y = bottom;
+ while ((*currentPtr)->fBounds.fBottom >= y) {
+ ++currentPtr;
+ }
+ } while (*currentPtr != &edgeSentinel);
+ // assemble output path from string of pts, verbs
+ ;
+}
+
+void testSimplify();
+
+void testSimplify() {
+ SkPath path, out;
+ path.setFillType(SkPath::kWinding_FillType);
+ path.addRect(10, 10, 30, 30);
+ path.addRect(20, 20, 40, 40);
+ simplify(path, true, out);
+ path = out;
+ path.addRect(30, 10, 40, 20);
+ path.addRect(10, 30, 20, 40);
+ simplify(path, true, out);
+ path = out;
+ path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction);
+ simplify(path, true, out);
+ if (!out.isEmpty()) {
+ SkDebugf("expected empty\n");
+ }
+}
diff --git a/experimental/Intersection/Inline_Tests.cpp b/experimental/Intersection/Inline_Tests.cpp
index d8b0e49..39f4e62 100644
--- a/experimental/Intersection/Inline_Tests.cpp
+++ b/experimental/Intersection/Inline_Tests.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersection_Tests.h"
#include "IntersectionUtilities.h"
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index e213de4..f27a3cf 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -2,6 +2,7 @@
#include "Intersection_Tests.h"
void cubecode_test(int test);
+void testSimplify();
void Intersection_Tests() {
cubecode_test(1);
@@ -16,6 +17,8 @@
LineQuadraticIntersection_Test();
LineCubicIntersection_Test();
+ testSimplify();
+
QuadraticCoincidence_Test();
QuadraticReduceOrder_Test();
QuadraticBezierClip_Test();
@@ -26,4 +29,5 @@
CubicReduceOrder_Test();
CubicBezierClip_Test();
CubicIntersection_Test();
+
}
diff --git a/experimental/Intersection/LineCubicIntersection.cpp b/experimental/Intersection/LineCubicIntersection.cpp
index f37507b..500a91e 100644
--- a/experimental/Intersection/LineCubicIntersection.cpp
+++ b/experimental/Intersection/LineCubicIntersection.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "CubicUtilities.h"
#include "Intersections.h"
#include "LineUtilities.h"
@@ -20,7 +20,7 @@
(in) Resultant[
a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - x,
- e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - i*x - j, x]
+ e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - i*x - j, x]
(out) -e + j +
3 e t - 3 f t -
3 e t^2 + 6 f t^2 - 3 g t^2 +
@@ -34,7 +34,7 @@
(in) Resultant[
a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - i*y - j,
- e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y]
+ e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y]
(out) a - j -
3 a t + 3 b t +
3 a t^2 - 6 b t^2 + 3 c t^2 -
@@ -58,35 +58,36 @@
B = 3*( ( a - 2*b + c ) - i*( e - 2*f + g ) )
C = 3*( (-a + b ) - i*(-e + f ) )
D = ( ( a ) - i*( e ) - j )
+
+For horizontal lines:
+(in) Resultant[
+ a*(1 - t)^3 + 3*b*(1 - t)^2*t + 3*c*(1 - t)*t^2 + d*t^3 - j,
+ e*(1 - t)^3 + 3*f*(1 - t)^2*t + 3*g*(1 - t)*t^2 + h*t^3 - y, y]
+(out) e - j -
+ 3 e t + 3 f t +
+ 3 e t^2 - 6 f t^2 + 3 g t^2 -
+ e t^3 + 3 f t^3 - 3 g t^3 + h t^3
+So the cubic coefficients are:
+
*/
class LineCubicIntersections : public Intersections {
public:
-LineCubicIntersections(const Cubic& c, const _Line& l, Intersections& i)
+LineCubicIntersections(const Cubic& c, const _Line& l, double r[3])
: cubic(c)
, line(l)
- , intersections(i) {
+ , range(r) {
}
-bool intersect() {
+int intersect() {
double slope;
double axisIntercept;
moreHorizontal = implicitLine(line, slope, axisIntercept);
- double A = cubic[3].x; // d
- double B = cubic[2].x * 3; // 3*c
- double C = cubic[1].x * 3; // 3*b
- double D = cubic[0].x; // a
- A -= D - C + B; // A = -a + 3*b - 3*c + d
- B += 3 * D - 2 * C; // B = 3*a - 6*b + 3*c
- C -= 3 * D; // C = -3*a + 3*b
- double E = cubic[3].y; // h
- double F = cubic[2].y * 3; // 3*g
- double G = cubic[1].y * 3; // 3*f
- double H = cubic[0].y; // e
- E -= H - G + F; // E = -e + 3*f - 3*g + h
- F += 3 * H - 2 * G; // F = 3*e - 6*f + 3*g
- G -= 3 * H; // G = -3*e + 3*f
+ double A, B, C, D;
+ coefficients(&cubic[0].x, A, B, C, D);
+ double E, F, G, H;
+ coefficients(&cubic[0].y, E, F, G, H);
if (moreHorizontal) {
A = A * slope - E;
B = B * slope - F;
@@ -98,16 +99,16 @@
C = C - G * slope;
D = D - H * slope - axisIntercept;
}
- double t[3];
- int roots = cubicRoots(A, B, C, D, t);
- for (int x = 0; x < roots; ++x) {
- intersections.add(t[x], findLineT(t[x]));
- }
- return roots > 0;
+ return cubicRoots(A, B, C, D, range);
}
-protected:
-
+int horizontalIntersect(double axisIntercept) {
+ double A, B, C, D;
+ coefficients(&cubic[0].y, A, B, C, D);
+ D -= axisIntercept;
+ return cubicRoots(A, B, C, D, range);
+}
+
double findLineT(double t) {
const double* cPtr;
const double* lPtr;
@@ -118,6 +119,7 @@
cPtr = &cubic[0].y;
lPtr = &line[0].y;
}
+ // FIXME: should fold the following in with TestUtilities.cpp xy_at_t()
double s = 1 - t;
double cubicVal = cPtr[0] * s * s * s + 3 * cPtr[2] * s * s * t
+ 3 * cPtr[4] * s * t * t + cPtr[6] * t * t * t;
@@ -128,12 +130,26 @@
const Cubic& cubic;
const _Line& line;
-Intersections& intersections;
+double* range;
bool moreHorizontal;
};
+
+int horizontalIntersect(const Cubic& cubic, double y, double tRange[3]) {
+ LineCubicIntersections c(cubic, *((_Line*) 0), tRange);
+ return c.horizontalIntersect(y);
+}
-bool intersectStart(const Cubic& cubic, const _Line& line, Intersections& i) {
- LineCubicIntersections c(cubic, line, i);
- return c.intersect();
+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)) {
+ roots = c.horizontalIntersect(line[0].y);
+ } else {
+ roots = c.intersect();
+ }
+ for (int index = 0; index < roots; ++index) {
+ lRange[index] = c.findLineT(cRange[index]);
+ }
+ return roots;
}
diff --git a/experimental/Intersection/LineCubicIntersection_Test.cpp b/experimental/Intersection/LineCubicIntersection_Test.cpp
index 3f2c622..f05dbd6 100644
--- a/experimental/Intersection/LineCubicIntersection_Test.cpp
+++ b/experimental/Intersection/LineCubicIntersection_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersection_Tests.h"
#include "Intersections.h"
#include "LineUtilities.h"
@@ -30,24 +30,22 @@
printf("[%d] line order=%d\n", (int) index, order2);
}
if (order1 == 4 && order2 == 2) {
- Intersections intersections;
- intersectStart(reduce1, reduce2, intersections);
- if (intersections.intersected()) {
- for (int pt = 0; pt < intersections.used(); ++pt) {
- double tt1 = intersections.fT[0][pt];
- double tx1, ty1;
- xy_at_t(cubic, tt1, tx1, ty1);
- double tt2 = intersections.fT[1][pt];
- double tx2, ty2;
- xy_at_t(line, tt2, tx2, ty2);
- if (!approximately_equal(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)) {
- printf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
- __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2);
- }
+ double range1[2], range2[2];
+ int roots = intersect(reduce1, reduce2, range1, range2);
+ for (int pt = 0; pt < roots; ++pt) {
+ double tt1 = range1[pt];
+ double tx1, ty1;
+ xy_at_t(cubic, tt1, tx1, ty1);
+ double tt2 = range2[pt];
+ double tx2, ty2;
+ xy_at_t(line, tt2, tx2, ty2);
+ if (!approximately_equal(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)) {
+ 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 c9bc616..99b9e82 100644
--- a/experimental/Intersection/LineIntersection.cpp
+++ b/experimental/Intersection/LineIntersection.cpp
@@ -1,113 +1,104 @@
#include "DataTypes.h"
#include "LineIntersection.h"
-#include "LineParameters.h"
+#include <algorithm> // used for std::swap
-static bool no_intersection(_Point* result) {
- result->x = 0;
- result->y = 0;
- return false;
-}
-
/*
Determine the intersection point of two line segments
Return FALSE if the lines don't intersect
from: http://paulbourke.net/geometry/lineline2d/
- min: 8 subs, 4 muls, 4 cmps
*/
-bool lineIntersect(const _Line& a, const _Line& b, _Point* result) {
- LineParameters paramsA, paramsB;
+int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]) {
double axLen = a[1].x - a[0].x;
double ayLen = a[1].y - a[0].y;
double bxLen = b[1].x - b[0].x;
double byLen = b[1].y - b[0].y;
+ /* Slopes match when denom goes to zero:
+ axLen / ayLen == bxLen / byLen
+ (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
+ byLen * axLen == ayLen * bxLen
+ byLen * axLen - ayLen * bxLen == 0 ( == denom )
+ */
double denom = byLen * axLen - ayLen * bxLen;
- if (approximately_zero_squared(denom)) { // is either 'a' or 'b' a point?
- bool aIsPoint = approximately_zero(axLen) && approximately_zero(ayLen);
- bool bIsPoint = approximately_zero(bxLen) && approximately_zero(byLen);
- if (aIsPoint & bIsPoint) {
- if (!approximately_equal(a[0].x, b[0].x)
- || !approximately_equal(a[0].y, b[0].y)) {
- return no_intersection(result);
- }
- } else {
- double ptToLineDistance;
- if (aIsPoint) {
- paramsB.lineEndPoints(b);
- ptToLineDistance = paramsB.pointDistance(a[0]);
+ if (approximately_zero_squared(denom)) {
+ /* See if the axis intercepts match:
+ ay - ax * ayLen / axLen == by - bx * ayLen / axLen
+ axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
+ axLen * ay - ax * ayLen == axLen * by - bx * ayLen
+ */
+ if (approximately_equal_squared(axLen * a[0].y - ayLen * a[0].x,
+ axLen * b[0].y - ayLen * b[0].x)) {
+ const double* aPtr;
+ const double* bPtr;
+ if (fabs(axLen) > fabs(ayLen) || fabs(bxLen) > fabs(byLen)) {
+ aPtr = &a[0].x;
+ bPtr = &b[0].x;
} else {
- paramsA.lineEndPoints(a);
- ptToLineDistance = paramsA.pointDistance(b[0]);
+ aPtr = &a[0].y;
+ bPtr = &b[0].y;
}
- if (!approximately_zero(ptToLineDistance)) {
- return no_intersection(result);
+ double aMin = aPtr[0];
+ double aMax = aPtr[2];
+ double bMin = bPtr[0];
+ double bMax = bPtr[2];
+ if (aMin > aMax) {
+ std::swap(aMin, aMax);
}
+ if (bMin > bMax) {
+ std::swap(bMin, bMax);
+ }
+ if (aMax < bMin || bMax < aMin) {
+ return 0;
+ }
+ if (aRange) {
+ aRange[0] = bMin <= aMin ? 0 : (bMin - aMin) / (aMax - aMin);
+ aRange[1] = bMax >= aMax ? 1 : (bMax - aMin) / (aMax - aMin);
+ }
+ if (bRange) {
+ bRange[0] = aMin <= bMin ? 0 : (aMin - bMin) / (bMax - bMin);
+ bRange[1] = aMax >= bMax ? 1 : (aMax - bMin) / (bMax - bMin);
+ }
+ return 2;
}
- if (aIsPoint) {
- result->x = a[0].x;
- result->y = a[0].y;
- } else {
- result->x = b[0].x;
- result->y = b[0].y;
- }
- return true;
}
double ab0y = a[0].y - b[0].y;
double ab0x = a[0].x - b[0].x;
double numerA = ab0y * bxLen - byLen * ab0x;
- double numerB;
if (numerA < 0 && denom > numerA || numerA > 0 && denom < numerA) {
- return no_intersection(result);
+ return 0;
}
- numerB = ab0y * axLen - ayLen * ab0x;
+ double numerB = ab0y * axLen - ayLen * ab0x;
if (numerB < 0 && denom > numerB || numerB > 0 && denom < numerB) {
- return no_intersection(result);
+ return 0;
}
- /* Are the line coincident? See if they overlap */
- // FIXME: allow returning range of coincidence, instead of or in
- // addition to midpoint
- paramsA.lineEndPoints(a);
- double b0dist = paramsA.pointDistance(b[0]);
- bool b0on = approximately_zero_squared(b0dist);
- double b1dist = paramsA.pointDistance(b[1]);
- bool b1on = approximately_zero_squared(b1dist);
- if (b0on | b1on) {
- if (b0on & b1on) {
- result->x = (b[0].x + b[1].x) / 2;
- result->y = (b[0].y + b[1].y) / 2;
- return true;
- }
- paramsB.lineEndPoints(b);
- double a0dist = paramsB.pointDistance(a[0]);
- bool a0on = approximately_zero_squared(a0dist);
- double a1dist = paramsB.pointDistance(a[1]);
- bool a1on = approximately_zero_squared(a1dist);
- if (a0on | a1on) {
- if (a0on & a1on) {
- result->x = (a[0].x + a[1].x) / 2;
- result->y = (a[0].y + a[1].y) / 2;
- return true;
- }
- const _Point& aPt = a0on ? a[0] : a[1];
- const _Point& bPt = b0on ? b[0] : b[1];
- if (aPt.approximatelyEqual(bPt)) {
- *result = aPt;
- return true;
- }
- result->x = (aPt.x + bPt.x) / 2;
- result->y = (aPt.y + bPt.y) / 2;
- return true;
- }
- }
-
/* Is the intersection along the the segments */
- double mua = numerA / denom;
- result->x = a[0].x + mua * (a[1].x - a[0].x);
- result->y = a[0].y + mua * (a[1].y - a[0].y);
- return true;
+ if (aRange) {
+ aRange[0] = numerA / denom;
+ }
+ if (bRange) {
+ bRange[0] = numerB / denom;
+ }
+ return 1;
}
+int horizontalIntersect(const _Line& line, double y, double tRange[2]) {
+ double min = line[0].y;
+ double max = line[1].y;
+ if (min > max) {
+ std::swap(min, max);
+ }
+ if (min > y || max < y) {
+ return 0;
+ }
+ if (approximately_equal(min, max)) {
+ tRange[0] = 0;
+ tRange[1] = 1;
+ return 2;
+ }
+ tRange[0] = (y - line[0].y) / (line[1].y - line[0].y);
+ return 1;
+}
// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
// 4 subs, 2 muls, 1 cmp
diff --git a/experimental/Intersection/LineIntersection.h b/experimental/Intersection/LineIntersection.h
index c1246a5..dfae7ef 100644
--- a/experimental/Intersection/LineIntersection.h
+++ b/experimental/Intersection/LineIntersection.h
@@ -1,5 +1,6 @@
#include "DataTypes.h"
-bool lineIntersect(const _Line& a, const _Line& b, _Point* result);
+int horizontalIntersect(const _Line& line, double y, double tRange[2]);
+int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]);
bool testIntersect(const _Line& a, const _Line& b);
diff --git a/experimental/Intersection/LineIntersection_Test.cpp b/experimental/Intersection/LineIntersection_Test.cpp
index 2af74d2..04b55be 100644
--- a/experimental/Intersection/LineIntersection_Test.cpp
+++ b/experimental/Intersection/LineIntersection_Test.cpp
@@ -1,25 +1,65 @@
-#include "CubicIntersection_Tests.h"
+#include "Intersection_Tests.h"
#include "LineIntersection.h"
// FIXME: add tests for intersecting, non-intersecting, degenerate, coincident
const _Line tests[][2] = {
+ {{{0, 0}, {1, 0}}, {{1, 0}, {0, 0}}},
+ {{{0, 0}, {0, 0}}, {{0, 0}, {1, 0}}},
+ {{{0, 1}, {0, 1}}, {{0, 0}, {0, 2}}},
+ {{{0, 0}, {1, 0}}, {{0, 0}, {2, 0}}},
+ {{{1, 1}, {2, 2}}, {{0, 0}, {3, 3}}},
{{{166.86950047022856, 112.69654129527828}, {166.86948801592692, 112.69655741235339}},
- {{166.86960700313026, 112.6965477747386}, {166.86925794355412, 112.69656471103423}}},
+ {{166.86960700313026, 112.6965477747386}, {166.86925794355412, 112.69656471103423}}}
};
const size_t tests_count = sizeof(tests) / sizeof(tests[0]);
+const _Line noIntersect[][2] = {
+ {{{0, 0}, {1, 0}}, {{3, 0}, {2, 0}}},
+ {{{0, 0}, {0, 0}}, {{1, 0}, {2, 0}}},
+ {{{0, 1}, {0, 1}}, {{0, 3}, {0, 2}}},
+ {{{0, 0}, {1, 0}}, {{2, 0}, {3, 0}}},
+ {{{1, 1}, {2, 2}}, {{4, 4}, {3, 3}}},
+};
+
+const size_t noIntersect_count = sizeof(noIntersect) / sizeof(noIntersect[0]);
+
static size_t firstLineIntersectionTest = 0;
+static size_t firstNoIntersectionTest = 0;
void LineIntersection_Test() {
- for (size_t index = firstLineIntersectionTest; index < tests_count; ++index) {
+ size_t index;
+ for (index = firstLineIntersectionTest; index < tests_count; ++index) {
const _Line& line1 = tests[index][0];
const _Line& line2 = tests[index][1];
- _Point result;
- lineIntersect(line1, line2, &result);
- // FIXME: validate results
- // see if result is between start and end of both lines
- // see if result is on both lines
- // printf("%s (%g,%g)\n", __FUNCTION__, result.x, result.y);
+ double t1[2], t2[2];
+ int pts = intersect(line1, line2, t1, t2);
+ if (!pts) {
+ printf("%s [%zu] no intersection found\n", __FUNCTION__, index);
+ }
+ for (int i = 0; i < pts; ++i) {
+ _Point result1, result2;
+ xy_at_t(line1, t1[i], result1.x, result1.y);
+ xy_at_t(line2, t2[i], result2.x, result2.y);
+ if (!result1.approximatelyEqual(result2)) {
+ if (pts == 1) {
+ printf("%s [%zu] not equal\n", __FUNCTION__, index);
+ } else {
+ xy_at_t(line2, t2[i ^ 1], result2.x, result2.y);
+ if (!result1.approximatelyEqual(result2)) {
+ printf("%s [%zu] not equal\n", __FUNCTION__, index);
+ }
+ }
+ }
+ }
+ }
+ for (index = firstNoIntersectionTest; index < noIntersect_count; ++index) {
+ const _Line& line1 = noIntersect[index][0];
+ const _Line& line2 = noIntersect[index][1];
+ double t1[2], t2[2];
+ int pts = intersect(line1, line2, t1, t2);
+ if (pts) {
+ printf("%s [%zu] no intersection expected\n", __FUNCTION__, index);
+ }
}
}
diff --git a/experimental/Intersection/LineParameterization.cpp b/experimental/Intersection/LineParameterization.cpp
new file mode 100644
index 0000000..4455cf2
--- /dev/null
+++ b/experimental/Intersection/LineParameterization.cpp
@@ -0,0 +1,34 @@
+#include "CurveIntersection.h"
+
+/* This rejects coincidence with two muls, two adds, and one cmp.
+ Coincident candidates will take another four muls and two adds, but may still
+ fail if they don't overlap. (The overlap test isn't performed here.)
+ */
+bool implicit_matches(const _Line& one, const _Line& two) {
+ _Point oneD, twoD;
+ tangent(one, oneD);
+ tangent(two, twoD);
+ /* See if the slopes match, i.e.
+ dx1 / dy1 == dx2 / dy2
+ (dy1 * dy2) * dx1 / dy1 == (dy1 * dy2) * dx2 / dy2
+ dy2 * dx1 == dy1 * dx2
+ */
+ if (!approximately_equal(oneD.x * twoD.y, twoD.x * oneD.y)) {
+ return false;
+ }
+ /* See if the axis intercepts match, i.e.
+ y0 - x0 * dy / dx == y1 - x1 * dy / dx
+ 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,
+ oneD.x * two[0].y - oneD.y * two[0].x)) {
+ return false;
+ }
+ return true;
+}
+
+void tangent(const _Line& line, _Point& result) {
+ result.x = line[0].x - line[1].x;
+ result.y = line[0].y - line[1].y;
+}
diff --git a/experimental/Intersection/LineParameteters_Test.cpp b/experimental/Intersection/LineParameteters_Test.cpp
index 5e0b4ac..f806250 100644
--- a/experimental/Intersection/LineParameteters_Test.cpp
+++ b/experimental/Intersection/LineParameteters_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection_Tests.h"
+#include "Intersection_Tests.h"
#include "LineParameters.h"
diff --git a/experimental/Intersection/LineQuadraticIntersection.cpp b/experimental/Intersection/LineQuadraticIntersection.cpp
index 02810ac..0d6477b 100644
--- a/experimental/Intersection/LineQuadraticIntersection.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersections.h"
#include "LineUtilities.h"
#include "QuadraticUtilities.h"
@@ -157,7 +157,7 @@
};
-bool intersectStart(const Quadratic& quad, const _Line& line, Intersections& i) {
+bool intersect(const Quadratic& quad, const _Line& line, Intersections& i) {
LineQuadraticIntersections q(quad, line, i);
return q.intersect();
}
diff --git a/experimental/Intersection/LineQuadraticIntersection_Test.cpp b/experimental/Intersection/LineQuadraticIntersection_Test.cpp
index aa1094f..017a44e 100644
--- a/experimental/Intersection/LineQuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/LineQuadraticIntersection_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersection_Tests.h"
#include "Intersections.h"
#include "LineUtilities.h"
@@ -31,7 +31,7 @@
}
if (order1 == 3 && order2 == 2) {
Intersections intersections;
- intersectStart(reduce1, reduce2, intersections);
+ intersect(reduce1, reduce2, intersections);
if (intersections.intersected()) {
for (int pt = 0; pt < intersections.used(); ++pt) {
double tt1 = intersections.fT[0][pt];
diff --git a/experimental/Intersection/LineUtilities.cpp b/experimental/Intersection/LineUtilities.cpp
index 9f782b1..f70352a 100644
--- a/experimental/Intersection/LineUtilities.cpp
+++ b/experimental/Intersection/LineUtilities.cpp
@@ -1,14 +1,15 @@
+#include "CurveIntersection.h"
#include "LineUtilities.h"
bool implicitLine(const _Line& line, double& slope, double& axisIntercept) {
- double lineDx = line[1].x - line[0].x;
- double lineDy = line[1].y - line[0].y;
- bool moreHorizontal = fabs(lineDx) > fabs(lineDy);
+ _Point delta;
+ tangent(line, delta);
+ bool moreHorizontal = fabs(delta.x) > fabs(delta.y);
if (moreHorizontal) {
- slope = lineDy / lineDx;
+ slope = delta.y / delta.x;
axisIntercept = line[0].y - slope * line[0].x;
} else {
- slope = lineDx / lineDy;
+ slope = delta.x / delta.y;
axisIntercept = line[0].x - slope * line[0].y;
}
return moreHorizontal;
diff --git a/experimental/Intersection/Parameterization_Test.h b/experimental/Intersection/Parameterization_Test.h
new file mode 100644
index 0000000..6ea4f68
--- /dev/null
+++ b/experimental/Intersection/Parameterization_Test.h
@@ -0,0 +1,6 @@
+#include "DataTypes.h"
+
+// utilities used only for unit testing
+bool point_on_parameterized_curve(const Cubic& cubic, const _Point& point);
+bool point_on_parameterized_line(const _Line& line, const _Point& point);
+bool point_on_parameterized_curve(const Quadratic& quad, const _Point& point);
diff --git a/experimental/Intersection/QuadraticBezierClip.cpp b/experimental/Intersection/QuadraticBezierClip.cpp
index fc3acfe..d9d984d 100644
--- a/experimental/Intersection/QuadraticBezierClip.cpp
+++ b/experimental/Intersection/QuadraticBezierClip.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "LineParameters.h"
#include <algorithm> // used for std::swap
diff --git a/experimental/Intersection/QuadraticBezierClip_Test.cpp b/experimental/Intersection/QuadraticBezierClip_Test.cpp
index 894d899..a9561fd 100644
--- a/experimental/Intersection/QuadraticBezierClip_Test.cpp
+++ b/experimental/Intersection/QuadraticBezierClip_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersection_Tests.h"
#include "QuadraticIntersection_TestData.h"
diff --git a/experimental/Intersection/QuadraticIntersection.cpp b/experimental/Intersection/QuadraticIntersection.cpp
index ab552e0..634d083 100644
--- a/experimental/Intersection/QuadraticIntersection.cpp
+++ b/experimental/Intersection/QuadraticIntersection.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersections.h"
#include "IntersectionUtilities.h"
#include "LineIntersection.h"
@@ -47,22 +47,21 @@
if (reduceOrder(smaller, smallResult) <= 2) {
Quadratic largeResult;
if (reduceOrder(larger, largeResult) <= 2) {
- _Point pt;
+ double smallT[2], largeT[2];
const _Line& smallLine = (const _Line&) smallResult;
const _Line& largeLine = (const _Line&) largeResult;
- if (!lineIntersect(smallLine, largeLine, &pt)) {
+ // FIXME: this doesn't detect or deal with coincident lines
+ if (!::intersect(smallLine, largeLine, smallT, largeT)) {
return false;
}
- double smallT = t_at(smallLine, pt);
- double largeT = t_at(largeLine, pt);
if (intersections.swapped()) {
- smallT = interp(minT2, maxT2, smallT);
- largeT = interp(minT1, maxT1, largeT);
+ smallT[0] = interp(minT2, maxT2, smallT[0]);
+ largeT[0] = interp(minT1, maxT1, largeT[0]);
} else {
- smallT = interp(minT1, maxT1, smallT);
- largeT = interp(minT2, maxT2, largeT);
+ smallT[0] = interp(minT1, maxT1, smallT[0]);
+ largeT[0] = interp(minT2, maxT2, largeT[0]);
}
- intersections.add(smallT, largeT);
+ intersections.add(smallT[0], largeT[0]);
return true;
}
}
@@ -138,7 +137,7 @@
int splits;
};
-bool intersectStart(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
+bool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& i) {
QuadraticIntersections q(q1, q2, i);
return q.intersect();
}
diff --git a/experimental/Intersection/QuadraticIntersection_Test.cpp b/experimental/Intersection/QuadraticIntersection_Test.cpp
index 7e171f0..63b7338 100644
--- a/experimental/Intersection/QuadraticIntersection_Test.cpp
+++ b/experimental/Intersection/QuadraticIntersection_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersection_Tests.h"
#include "Intersections.h"
#include "QuadraticIntersection_TestData.h"
@@ -21,7 +21,7 @@
}
if (order1 == 3 && order2 == 3) {
Intersections intersections;
- intersectStart(reduce1, reduce2, intersections);
+ intersect(reduce1, reduce2, intersections);
if (intersections.intersected()) {
for (int pt = 0; pt < intersections.used(); ++pt) {
double tt1 = intersections.fT[0][pt];
diff --git a/experimental/Intersection/QuadraticParameterization.cpp b/experimental/Intersection/QuadraticParameterization.cpp
index 1c08fcb..fb45b17 100644
--- a/experimental/Intersection/QuadraticParameterization.cpp
+++ b/experimental/Intersection/QuadraticParameterization.cpp
@@ -1,10 +1,10 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "QuadraticUtilities.h"
/* from http://tom.cs.byu.edu/~tom/papers/cvgip84.pdf 4.1
*
* This paper proves that Syvester's method can compute the implicit form of
- * the quadratic from the parameterzied form.
+ * the quadratic from the parameterized form.
*
* Given x = a*t*t + b*t + c (the parameterized form)
* y = d*t*t + e*t + f
diff --git a/experimental/Intersection/QuadraticParameterization_Test.cpp b/experimental/Intersection/QuadraticParameterization_Test.cpp
index ddf73b4..e355140 100644
--- a/experimental/Intersection/QuadraticParameterization_Test.cpp
+++ b/experimental/Intersection/QuadraticParameterization_Test.cpp
@@ -1,5 +1,6 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersection_Tests.h"
+#include "Parameterization_Test.h"
const Quadratic quadratics[] = {
{{0, 0}, {1, 0}, {1, 1}},
diff --git a/experimental/Intersection/QuadraticParameterization_TestUtility.cpp b/experimental/Intersection/QuadraticParameterization_TestUtility.cpp
index 326b28e..08a562b 100644
--- a/experimental/Intersection/QuadraticParameterization_TestUtility.cpp
+++ b/experimental/Intersection/QuadraticParameterization_TestUtility.cpp
@@ -1,6 +1,8 @@
// included by QuadraticParameterization.cpp
// accesses internal functions to validate parameterized coefficients
+#include "Parameterization_Test.h"
+
bool point_on_parameterized_curve(const Quadratic& quad, const _Point& point) {
double coeffs[coeff_count];
implicit_coefficients(quad, coeffs);
diff --git a/experimental/Intersection/QuadraticReduceOrder.cpp b/experimental/Intersection/QuadraticReduceOrder.cpp
index 02d1956..e6ce044 100644
--- a/experimental/Intersection/QuadraticReduceOrder.cpp
+++ b/experimental/Intersection/QuadraticReduceOrder.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Extrema.h"
#include "IntersectionUtilities.h"
#include "LineParameters.h"
diff --git a/experimental/Intersection/QuadraticReduceOrder_Test.cpp b/experimental/Intersection/QuadraticReduceOrder_Test.cpp
index 6e92329..397342b 100644
--- a/experimental/Intersection/QuadraticReduceOrder_Test.cpp
+++ b/experimental/Intersection/QuadraticReduceOrder_Test.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "Intersection_Tests.h"
#include "QuadraticIntersection_TestData.h"
#include "TestUtilities.h"
diff --git a/experimental/Intersection/QuadraticSubDivide.cpp b/experimental/Intersection/QuadraticSubDivide.cpp
index 947f7d8..7c3164e 100644
--- a/experimental/Intersection/QuadraticSubDivide.cpp
+++ b/experimental/Intersection/QuadraticSubDivide.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "IntersectionUtilities.h"
/*
diff --git a/experimental/Intersection/RectUtilities.cpp b/experimental/Intersection/RectUtilities.cpp
new file mode 100644
index 0000000..e7bda02
--- /dev/null
+++ b/experimental/Intersection/RectUtilities.cpp
@@ -0,0 +1,44 @@
+#include "DataTypes.h"
+#include "Extrema.h"
+
+void _Rect::setBounds(const Cubic& cubic) {
+ set(cubic[0]);
+ add(cubic[3]);
+ double tValues[4];
+ int roots = SkFindCubicExtrema(cubic[0].x, cubic[1].x, cubic[2].x,
+ cubic[3].x, tValues);
+ roots += SkFindCubicExtrema(cubic[0].y, cubic[1].y, cubic[2].y, cubic[3].y,
+ &tValues[roots]);
+ for (int x = 0; x < roots; ++x) {
+ _Point result;
+ xy_at_t(cubic, tValues[x], result.x, result.y);
+ add(result);
+ }
+}
+
+void _Rect::setRawBounds(const Cubic& cubic) {
+ set(cubic[0]);
+ for (int x = 1; x < 4; ++x) {
+ add(cubic[x]);
+ }
+}
+
+void _Rect::setBounds(const Quadratic& quad) {
+ set(quad[0]);
+ add(quad[2]);
+ double tValues[2];
+ int roots = SkFindQuadExtrema(quad[0].x, quad[1].x, quad[2].x, tValues);
+ roots += SkFindQuadExtrema(quad[0].y, quad[1].y, quad[2].y, &tValues[roots]);
+ for (int x = 0; x < roots; ++x) {
+ _Point result;
+ xy_at_t(quad, tValues[x], result.x, result.y);
+ add(result);
+ }
+}
+
+void _Rect::setRawBounds(const Quadratic& quad) {
+ set(quad[0]);
+ for (int x = 1; x < 3; ++x) {
+ add(quad[x]);
+ }
+}
diff --git a/experimental/Intersection/TSearch.h b/experimental/Intersection/TSearch.h
new file mode 100644
index 0000000..53242c3
--- /dev/null
+++ b/experimental/Intersection/TSearch.h
@@ -0,0 +1,78 @@
+#include "SkTypes.h"
+
+// FIXME: Move this templated version into SKTSearch.h
+
+template <typename T>
+static void QSort_Partition(T** first, T** last)
+{
+ T** left = first;
+ T** rite = last;
+ T** pivot = left;
+
+ while (left <= rite) {
+ while (left < last && **left < **pivot)
+ left += 1;
+ while (first < rite && **pivot < **rite)
+ rite -= 1;
+ if (left <= rite) {
+ if (left < rite) {
+ SkTSwap(*left, *rite);
+ }
+ left += 1;
+ rite -= 1;
+ }
+ }
+ if (first < rite)
+ QSort_Partition(first, rite);
+ if (left < last)
+ QSort_Partition(left, last);
+}
+
+template <typename T>
+void QSort(T** base, size_t count)
+{
+ SkASSERT(base);
+
+ if (count <= 1) {
+ return;
+ }
+ QSort_Partition(base, base + (count - 1));
+}
+
+template <typename T>
+static void QSort_Partition(T* first, T* last, bool (*lessThan)(const T*, const T*))
+{
+ T* left = first;
+ T* rite = last;
+ T* pivot = left;
+
+ while (left <= rite) {
+ while (left < last && lessThan(left, pivot) < 0)
+ left += 1;
+ while (first < rite && lessThan(rite, pivot) > 0)
+ rite -= 1;
+ if (left <= rite) {
+ if (left < rite) {
+ SkTSwap(*left, *rite);
+ }
+ left += 1;
+ rite -= 1;
+ }
+ }
+ if (first < rite)
+ QSort_Partition(first, rite, lessThan);
+ if (left < last)
+ QSort_Partition(left, last, lessThan);
+}
+
+template <typename T>
+void QSort(T* base, size_t count, bool (*lessThan)(const T*, const T*))
+{
+ SkASSERT(base);
+ SkASSERT(lessThan);
+
+ if (count <= 1) {
+ return;
+ }
+ QSort_Partition(base, base + (count - 1), lessThan);
+}
diff --git a/experimental/Intersection/TestUtilities.cpp b/experimental/Intersection/TestUtilities.cpp
index e09e107..a0aceb3 100644
--- a/experimental/Intersection/TestUtilities.cpp
+++ b/experimental/Intersection/TestUtilities.cpp
@@ -1,4 +1,4 @@
-#include "CubicIntersection.h"
+#include "CurveIntersection.h"
#include "TestUtilities.h"
void quad_to_cubic(const Quadratic& quad, Cubic& cubic) {
@@ -56,30 +56,3 @@
|| (cubic[0].y >= cubic[1].y && cubic[0].y >= cubic[2].y && cubic[1].y >= cubic[3].y && cubic[2].x >= cubic[3].y));
}
-void xy_at_t(const Cubic& cubic, double t, double& x, double& y) {
- double one_t = 1 - t;
- double one_t2 = one_t * one_t;
- double a = one_t2 * one_t;
- double b = 3 * one_t2 * t;
- double t2 = t * t;
- double c = 3 * one_t * t2;
- double d = t2 * t;
- x = a * cubic[0].x + b * cubic[1].x + c * cubic[2].x + d * cubic[3].x;
- y = a * cubic[0].y + b * cubic[1].y + c * cubic[2].y + d * cubic[3].y;
-}
-
-void xy_at_t(const _Line& line, double t, double& x, double& y) {
- double one_t = 1 - t;
- x = one_t * line[0].x + t * line[1].x;
- y = one_t * line[0].y + t * line[1].y;
-}
-
-void xy_at_t(const Quadratic& quad, double t, double& x, double& y) {
- double one_t = 1 - t;
- double a = one_t * one_t;
- double b = 2 * one_t * t;
- double c = t * t;
- x = a * quad[0].x + b * quad[1].x + c * quad[2].x;
- y = a * quad[0].y + b * quad[1].y + c * quad[2].y;
-}
-
diff --git a/experimental/Intersection/TestUtilities.h b/experimental/Intersection/TestUtilities.h
index b5bdae5..6c878e3 100644
--- a/experimental/Intersection/TestUtilities.h
+++ b/experimental/Intersection/TestUtilities.h
@@ -3,6 +3,3 @@
bool controls_inside(const Cubic& );
void find_tight_bounds(const Cubic& , _Rect& );
void quad_to_cubic(const Quadratic& , Cubic& );
-void xy_at_t(const Cubic& , double t, double& x, double& y);
-void xy_at_t(const _Line& , double t, double& x, double& y);
-void xy_at_t(const Quadratic& , double t, double& x, double& y);
diff --git a/experimental/Intersection/edge.xcodeproj/project.pbxproj b/experimental/Intersection/edge.xcodeproj/project.pbxproj
index 6f2460c..2b24fa1 100644
--- a/experimental/Intersection/edge.xcodeproj/project.pbxproj
+++ b/experimental/Intersection/edge.xcodeproj/project.pbxproj
@@ -15,10 +15,13 @@
FE7131C414CF5A960008E392 /* LineQuadraticIntersection_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7131C314CF5A960008E392 /* LineQuadraticIntersection_Test.cpp */; };
FE7131EE14D03AED0008E392 /* LineCubicIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7131ED14D03AED0008E392 /* LineCubicIntersection.cpp */; };
FE71324214D047670008E392 /* QuadraticUtilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71324114D047670008E392 /* QuadraticUtilities.cpp */; };
- FE71324F14D04D460008E392 /* CubicRoots.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA54114BC838600B35E2C /* CubicRoots.cpp */; };
+ FE71324F14D04D460008E392 /* CubicUtilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA54114BC838600B35E2C /* CubicUtilities.cpp */; };
FE71325014D04D480008E392 /* CubeRoot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FECAA53014BB934700B35E2C /* CubeRoot.cpp */; };
FE71325F14D050D80008E392 /* LineUtilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71325E14D050D80008E392 /* LineUtilities.cpp */; };
FE71334214D06B0F0008E392 /* LineCubicIntersection_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71334114D06B0F0008E392 /* LineCubicIntersection_Test.cpp */; };
+ FE7134F514D1E7C70008E392 /* LineParameterization.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE7134F414D1E7C70008E392 /* LineParameterization.cpp */; };
+ FE71351314D2E9F50008E392 /* RectUtilities.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71351214D2E9F50008E392 /* RectUtilities.cpp */; };
+ FE71358614D309E90008E392 /* EdgeWalker.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FE71358514D309E90008E392 /* EdgeWalker.cpp */; };
FEA5F4E21498000C005052F9 /* libports.a in Frameworks */ = {isa = PBXBuildFile; fileRef = FEA5F4E11497FFF6005052F9 /* libports.a */; };
FEA671D013C4A21600FE6FC1 /* AGL.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = FEA671CF13C4A21600FE6FC1 /* AGL.framework */; };
FEA671D813C4A21600FE6FC1 /* Foundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = FEA671D713C4A21600FE6FC1 /* Foundation.framework */; };
@@ -31,8 +34,7 @@
FEC1191B148683330086BF1F /* Extrema.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC1191A148683330086BF1F /* Extrema.cpp */; };
FEC1195514869DCA0086BF1F /* LineIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC1195414869DC90086BF1F /* LineIntersection.cpp */; };
FEC11E3E148D65780086BF1F /* CubicSubDivide.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC11E3D148D65780086BF1F /* CubicSubDivide.cpp */; };
- FEC11F84148E7C9C0086BF1F /* junk.htm in Resources */ = {isa = PBXBuildFile; fileRef = FEC11F83148E7C9C0086BF1F /* junk.htm */; };
- FEC12116148EB4EC0086BF1F /* CubicIntersectionT.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC12115148EB4EC0086BF1F /* CubicIntersectionT.cpp */; };
+ FEC12116148EB4EC0086BF1F /* CubicIntersection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC12115148EB4EC0086BF1F /* CubicIntersection.cpp */; };
FEC1211B148EB5200086BF1F /* CubicBezierClip.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC1211A148EB5200086BF1F /* CubicBezierClip.cpp */; };
FEC1238F149000100086BF1F /* LineParameteters_Test.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEC1238E149000100086BF1F /* LineParameteters_Test.cpp */; };
FEC123A6149001A00086BF1F /* SkAntiEdge.cpp in Sources */ = {isa = PBXBuildFile; fileRef = FEA670F013C49E2200FE6FC1 /* SkAntiEdge.cpp */; };
@@ -222,10 +224,8 @@
256AC3F00F4B6AF500CF3369 /* edge_Prefix.pch */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = edge_Prefix.pch; sourceTree = "<group>"; };
8D1107310486CEB800E47090 /* edge-Info.plist */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.plist.xml; path = "edge-Info.plist"; sourceTree = "<group>"; };
8D1107320486CEB800E47090 /* edge.app */ = {isa = PBXFileReference; explicitFileType = wrapper.application; includeInIndex = 0; path = edge.app; sourceTree = BUILT_PRODUCTS_DIR; };
- FE3201C6144DCC68006DDA67 /* skia_mac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = skia_mac.mm; path = ../../skia/trunk/src/utils/mac/skia_mac.mm; sourceTree = SOURCE_ROOT; };
- FE3201C7144DCC68006DDA67 /* SkOSWindow_Mac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkOSWindow_Mac.mm; path = ../../skia/trunk/src/utils/mac/SkOSWindow_Mac.mm; sourceTree = SOURCE_ROOT; };
- FE3EBE41149A337700D76FDE /* x.svg */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; name = x.svg; path = ../../../../tera/x.svg; sourceTree = SOURCE_ROOT; };
- FE3EBE6E149A7F4D00D76FDE /* valgrind.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; name = valgrind.txt; path = ../../../../tera/valgrind.txt; sourceTree = SOURCE_ROOT; };
+ FE3201C6144DCC68006DDA67 /* skia_mac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = skia_mac.mm; path = ../../src/utils/mac/skia_mac.mm; sourceTree = SOURCE_ROOT; };
+ FE3201C7144DCC68006DDA67 /* SkOSWindow_Mac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkOSWindow_Mac.mm; path = ../../src/utils/mac/SkOSWindow_Mac.mm; sourceTree = SOURCE_ROOT; };
FE4FE7411492417500A12A34 /* IntersectionUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = IntersectionUtilities.cpp; sourceTree = "<group>"; };
FE7130A014CE0EEB0008E392 /* LineQuadraticIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineQuadraticIntersection.cpp; sourceTree = "<group>"; };
FE7131C314CF5A960008E392 /* LineQuadraticIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineQuadraticIntersection_Test.cpp; sourceTree = "<group>"; };
@@ -235,10 +235,15 @@
FE71325D14D050D80008E392 /* LineUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LineUtilities.h; sourceTree = "<group>"; };
FE71325E14D050D80008E392 /* LineUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineUtilities.cpp; sourceTree = "<group>"; };
FE71334114D06B0F0008E392 /* LineCubicIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineCubicIntersection_Test.cpp; sourceTree = "<group>"; };
- FEA5F4D91497FFF6005052F9 /* ports.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = ports.xcodeproj; path = ../../skia/trunk/out/gyp/ports.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FE7134DF14D1E5680008E392 /* Parameterization_Test.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Parameterization_Test.h; sourceTree = "<group>"; };
+ FE7134F414D1E7C70008E392 /* LineParameterization.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineParameterization.cpp; sourceTree = "<group>"; };
+ FE71351214D2E9F50008E392 /* RectUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RectUtilities.cpp; sourceTree = "<group>"; };
+ FE71358514D309E90008E392 /* EdgeWalker.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalker.cpp; sourceTree = "<group>"; };
+ FE713C6114D9879B0008E392 /* TSearch.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TSearch.h; sourceTree = "<group>"; };
+ FEA5F4D91497FFF6005052F9 /* ports.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = ports.xcodeproj; path = ../../out/gyp/ports.xcodeproj; sourceTree = SOURCE_ROOT; };
FEA670F013C49E2200FE6FC1 /* SkAntiEdge.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SkAntiEdge.cpp; sourceTree = "<group>"; };
FEA670F113C49E2200FE6FC1 /* SkAntiEdge.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SkAntiEdge.h; sourceTree = "<group>"; };
- FEA6710713C4A13900FE6FC1 /* gyp */ = {isa = PBXFileReference; lastKnownFileType = folder; name = gyp; path = ../../skia/trunk/out/gyp; sourceTree = SOURCE_ROOT; };
+ FEA6710713C4A13900FE6FC1 /* gyp */ = {isa = PBXFileReference; lastKnownFileType = folder; name = gyp; path = ../../out/gyp; sourceTree = SOURCE_ROOT; };
FEA671CF13C4A21600FE6FC1 /* AGL.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = AGL.framework; path = System/Library/Frameworks/AGL.framework; sourceTree = SDKROOT; };
FEA671D113C4A21600FE6FC1 /* ApplicationServices.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = ApplicationServices.framework; path = System/Library/Frameworks/ApplicationServices.framework; sourceTree = SDKROOT; };
FEA671D713C4A21600FE6FC1 /* Foundation.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = Foundation.framework; path = System/Library/Frameworks/Foundation.framework; sourceTree = SDKROOT; };
@@ -256,8 +261,7 @@
FEC11A851487D2650086BF1F /* LineParameters.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LineParameters.h; sourceTree = "<group>"; };
FEC11A881487D2F50086BF1F /* IntersectionUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IntersectionUtilities.h; sourceTree = "<group>"; };
FEC11E3D148D65780086BF1F /* CubicSubDivide.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicSubDivide.cpp; sourceTree = "<group>"; };
- FEC11F83148E7C9C0086BF1F /* junk.htm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; name = junk.htm; path = ../../../../tera/htm_backups/junk.htm; sourceTree = SOURCE_ROOT; };
- FEC12115148EB4EC0086BF1F /* CubicIntersectionT.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersectionT.cpp; sourceTree = "<group>"; };
+ FEC12115148EB4EC0086BF1F /* CubicIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection.cpp; sourceTree = "<group>"; };
FEC1211A148EB5200086BF1F /* CubicBezierClip.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicBezierClip.cpp; sourceTree = "<group>"; };
FEC1238E149000100086BF1F /* LineParameteters_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineParameteters_Test.cpp; sourceTree = "<group>"; };
FEC12CDF14913E650086BF1F /* LineIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineIntersection_Test.cpp; sourceTree = "<group>"; };
@@ -270,7 +274,7 @@
FECAA52114BB527000B35E2C /* QuadraticIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticIntersection.cpp; sourceTree = "<group>"; };
FECAA52B14BB6B0900B35E2C /* QuadraticUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = QuadraticUtilities.h; sourceTree = "<group>"; };
FECAA53014BB934700B35E2C /* CubeRoot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubeRoot.cpp; sourceTree = "<group>"; };
- FECAA54114BC838600B35E2C /* CubicRoots.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicRoots.cpp; sourceTree = "<group>"; };
+ FECAA54114BC838600B35E2C /* CubicUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicUtilities.cpp; sourceTree = "<group>"; };
FECAA56C14BCA23200B35E2C /* QuadraticReduceOrder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticReduceOrder.cpp; sourceTree = "<group>"; };
FECAA58314BCBD4E00B35E2C /* QuadraticBezierClip.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticBezierClip.cpp; sourceTree = "<group>"; };
FECAA67814BCDBD600B35E2C /* QuadraticBezierClip_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticBezierClip_Test.cpp; sourceTree = "<group>"; };
@@ -281,29 +285,28 @@
FECAAB7F14BDFAFD00B35E2C /* CubicParameterization_TestUtility.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicParameterization_TestUtility.cpp; sourceTree = "<group>"; };
FECAACA614BE1C6100B35E2C /* QuadraticParameterization_TestUtility.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticParameterization_TestUtility.cpp; sourceTree = "<group>"; };
FED53C381483CB9400F6359E /* Inline_Tests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Inline_Tests.cpp; sourceTree = "<group>"; };
- FEE103331416542A006952D6 /* CubicIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection.cpp; sourceTree = "<group>"; };
- FEED723C144DD2250059E97B /* SampleApp.xib */ = {isa = PBXFileReference; lastKnownFileType = file.xib; name = SampleApp.xib; path = ../../skia/trunk/src/utils/mac/SampleApp.xib; sourceTree = SOURCE_ROOT; };
- FEED723D144DD2250059E97B /* SampleAppDelegate.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SampleAppDelegate.mm; path = ../../skia/trunk/src/utils/mac/SampleAppDelegate.mm; sourceTree = SOURCE_ROOT; };
- FEED723E144DD2250059E97B /* SkEventNotifier.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkEventNotifier.mm; path = ../../skia/trunk/src/utils/mac/SkEventNotifier.mm; sourceTree = SOURCE_ROOT; };
- FEED723F144DD2250059E97B /* SkNSView.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkNSView.mm; path = ../../skia/trunk/src/utils/mac/SkNSView.mm; sourceTree = SOURCE_ROOT; };
- FEED7240144DD2250059E97B /* SkOptionsTableView.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkOptionsTableView.mm; path = ../../skia/trunk/src/utils/mac/SkOptionsTableView.mm; sourceTree = SOURCE_ROOT; };
- FEED7241144DD2250059E97B /* SkSampleNSView.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkSampleNSView.mm; path = ../../skia/trunk/src/utils/mac/SkSampleNSView.mm; sourceTree = SOURCE_ROOT; };
- FEED7242144DD2250059E97B /* SkTextFieldCell.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = SkTextFieldCell.m; path = ../../skia/trunk/src/utils/mac/SkTextFieldCell.m; sourceTree = SOURCE_ROOT; };
- FEED725D144DD38D0059E97B /* views.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = views.xcodeproj; path = ../../skia/trunk/out/gyp/views.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEED7263144DD3EA0059E97B /* animator.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = animator.xcodeproj; path = ../../skia/trunk/out/gyp/animator.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEED7269144DD4050059E97B /* experimental.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = experimental.xcodeproj; path = ../../skia/trunk/out/gyp/experimental.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEED726F144DD4140059E97B /* gpu.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = gpu.xcodeproj; path = ../../skia/trunk/out/gyp/gpu.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEED7279144DD4200059E97B /* images.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = images.xcodeproj; path = ../../skia/trunk/out/gyp/images.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEED727F144DD4300059E97B /* libtess.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = libtess.xcodeproj; path = ../../skia/trunk/out/gyp/libtess.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEED7285144DD4440059E97B /* pdf.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = pdf.xcodeproj; path = ../../skia/trunk/out/gyp/pdf.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEED728B144DD44D0059E97B /* svg.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = svg.xcodeproj; path = ../../skia/trunk/out/gyp/svg.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEED729C144DD4A80059E97B /* xml.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = xml.xcodeproj; path = ../../skia/trunk/out/gyp/xml.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEED723C144DD2250059E97B /* SampleApp.xib */ = {isa = PBXFileReference; lastKnownFileType = file.xib; name = SampleApp.xib; path = ../../src/utils/mac/SampleApp.xib; sourceTree = SOURCE_ROOT; };
+ FEED723D144DD2250059E97B /* SampleAppDelegate.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SampleAppDelegate.mm; path = ../../src/utils/mac/SampleAppDelegate.mm; sourceTree = SOURCE_ROOT; };
+ FEED723E144DD2250059E97B /* SkEventNotifier.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkEventNotifier.mm; path = ../../src/utils/mac/SkEventNotifier.mm; sourceTree = SOURCE_ROOT; };
+ FEED723F144DD2250059E97B /* SkNSView.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkNSView.mm; path = ../../src/utils/mac/SkNSView.mm; sourceTree = SOURCE_ROOT; };
+ FEED7240144DD2250059E97B /* SkOptionsTableView.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkOptionsTableView.mm; path = ../../src/utils/mac/SkOptionsTableView.mm; sourceTree = SOURCE_ROOT; };
+ FEED7241144DD2250059E97B /* SkSampleNSView.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = SkSampleNSView.mm; path = ../../src/utils/mac/SkSampleNSView.mm; sourceTree = SOURCE_ROOT; };
+ FEED7242144DD2250059E97B /* SkTextFieldCell.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = SkTextFieldCell.m; path = ../../src/utils/mac/SkTextFieldCell.m; sourceTree = SOURCE_ROOT; };
+ FEED725D144DD38D0059E97B /* views.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = views.xcodeproj; path = ../../out/gyp/views.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEED7263144DD3EA0059E97B /* animator.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = animator.xcodeproj; path = ../../out/gyp/animator.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEED7269144DD4050059E97B /* experimental.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = experimental.xcodeproj; path = ../../out/gyp/experimental.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEED726F144DD4140059E97B /* gpu.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = gpu.xcodeproj; path = ../../out/gyp/gpu.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEED7279144DD4200059E97B /* images.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = images.xcodeproj; path = ../../out/gyp/images.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEED727F144DD4300059E97B /* libtess.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = libtess.xcodeproj; path = ../../out/gyp/libtess.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEED7285144DD4440059E97B /* pdf.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = pdf.xcodeproj; path = ../../out/gyp/pdf.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEED728B144DD44D0059E97B /* svg.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = svg.xcodeproj; path = ../../out/gyp/svg.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEED729C144DD4A80059E97B /* xml.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = xml.xcodeproj; path = ../../out/gyp/xml.xcodeproj; sourceTree = SOURCE_ROOT; };
FEED7583144DD6360059E97B /* Cocoa.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = Cocoa.framework; path = /System/Library/Frameworks/Cocoa.framework; sourceTree = "<absolute>"; };
FEED75DC144DD6590059E97B /* QuartzCore.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = QuartzCore.framework; path = /System/Library/Frameworks/QuartzCore.framework; sourceTree = "<absolute>"; };
FEED75DE144DD6840059E97B /* libz.dylib */ = {isa = PBXFileReference; lastKnownFileType = "compiled.mach-o.dylib"; name = libz.dylib; path = /usr/lib/libz.dylib; sourceTree = "<absolute>"; };
FEED7625144F22E20059E97B /* CubicReduceOrder_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicReduceOrder_Test.cpp; sourceTree = "<group>"; };
FEED762B144F236C0059E97B /* CubicIntersection_TestData.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection_TestData.cpp; sourceTree = "<group>"; };
- FEED762F144F23CA0059E97B /* CubicIntersection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CubicIntersection.h; sourceTree = "<group>"; };
+ FEED762F144F23CA0059E97B /* CurveIntersection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CurveIntersection.h; sourceTree = "<group>"; };
FEED7632144F25150059E97B /* CubicIntersection_TestData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CubicIntersection_TestData.h; sourceTree = "<group>"; };
FEED764B144F29BD0059E97B /* TestUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TestUtilities.cpp; sourceTree = "<group>"; };
FEED764F144F2A160059E97B /* DataTypes.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DataTypes.h; sourceTree = "<group>"; };
@@ -312,10 +315,10 @@
FEED7689144F2E7D0059E97B /* CubicIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection_Test.cpp; sourceTree = "<group>"; };
FEED76C0144F3E7F0059E97B /* ConvexHull_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ConvexHull_Test.cpp; sourceTree = "<group>"; };
FEED76ED144F66E90059E97B /* Intersection_Tests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Intersection_Tests.cpp; sourceTree = "<group>"; };
- FEF87C1213E040E000335C58 /* core.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = core.xcodeproj; path = ../../skia/trunk/out/gyp/core.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEF87C1B13E040F100335C58 /* effects.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = effects.xcodeproj; path = ../../skia/trunk/out/gyp/effects.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEF87C2413E0410900335C58 /* opts.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = opts.xcodeproj; path = ../../skia/trunk/out/gyp/opts.xcodeproj; sourceTree = SOURCE_ROOT; };
- FEF87C3313E0412600335C58 /* utils.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = utils.xcodeproj; path = ../../skia/trunk/out/gyp/utils.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEF87C1213E040E000335C58 /* core.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = core.xcodeproj; path = ../../out/gyp/core.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEF87C1B13E040F100335C58 /* effects.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = effects.xcodeproj; path = ../../out/gyp/effects.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEF87C2413E0410900335C58 /* opts.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = opts.xcodeproj; path = ../../out/gyp/opts.xcodeproj; sourceTree = SOURCE_ROOT; };
+ FEF87C3313E0412600335C58 /* utils.xcodeproj */ = {isa = PBXFileReference; lastKnownFileType = "wrapper.pb-project"; name = utils.xcodeproj; path = ../../out/gyp/utils.xcodeproj; sourceTree = SOURCE_ROOT; };
/* End PBXFileReference section */
/* Begin PBXFrameworksBuildPhase section */
@@ -362,12 +365,10 @@
29B97314FDCFA39411CA2CEA /* edge */ = {
isa = PBXGroup;
children = (
- FE3EBE6E149A7F4D00D76FDE /* valgrind.txt */,
- FE3EBE41149A337700D76FDE /* x.svg */,
- FEC11F83148E7C9C0086BF1F /* junk.htm */,
FEA670EF13C49D7600FE6FC1 /* views */,
FEC123A7149001B20086BF1F /* AntiEdge */,
- 29B97315FDCFA39411CA2CEA /* CubicIntersection */,
+ 29B97315FDCFA39411CA2CEA /* Intersection */,
+ FE71354F14D305FD0008E392 /* ShapeOps */,
FEC123A5149001540086BF1F /* Tests */,
29B97317FDCFA39411CA2CEA /* Resources */,
29B97323FDCFA39411CA2CEA /* Frameworks */,
@@ -391,21 +392,20 @@
name = edge;
sourceTree = "<group>";
};
- 29B97315FDCFA39411CA2CEA /* CubicIntersection */ = {
+ 29B97315FDCFA39411CA2CEA /* Intersection */ = {
isa = PBXGroup;
children = (
FEC118B7148666670086BF1F /* ConvexHull.cpp */,
FECAA53014BB934700B35E2C /* CubeRoot.cpp */,
FEC1211A148EB5200086BF1F /* CubicBezierClip.cpp */,
- FEED762F144F23CA0059E97B /* CubicIntersection.h */,
- FEE103331416542A006952D6 /* CubicIntersection.cpp */,
- FEC12115148EB4EC0086BF1F /* CubicIntersectionT.cpp */,
+ FEC12115148EB4EC0086BF1F /* CubicIntersection.cpp */,
FECA983F14AA044100B35E2C /* CubicParameterization.cpp */,
FECA997B14AB966900B35E2C /* CubicParameterizationCode.cpp */,
FEC11910148682200086BF1F /* CubicReduceOrder.cpp */,
- FECAA54114BC838600B35E2C /* CubicRoots.cpp */,
+ FECAA54114BC838600B35E2C /* CubicUtilities.cpp */,
FEC11E3D148D65780086BF1F /* CubicSubDivide.cpp */,
FE71325114D04D7A0008E392 /* CubicUtilities.h */,
+ FEED762F144F23CA0059E97B /* CurveIntersection.h */,
FEED764F144F2A160059E97B /* DataTypes.h */,
FEC118C1148668F30086BF1F /* DataTypes.cpp */,
FEC1191E148683850086BF1F /* Extrema.h */,
@@ -415,7 +415,10 @@
FE4FE7411492417500A12A34 /* IntersectionUtilities.cpp */,
FEC1195314869DC90086BF1F /* LineIntersection.h */,
FEC1195414869DC90086BF1F /* LineIntersection.cpp */,
+ FE7134F414D1E7C70008E392 /* LineParameterization.cpp */,
FEC11A851487D2650086BF1F /* LineParameters.h */,
+ FE71325D14D050D80008E392 /* LineUtilities.h */,
+ FE71325E14D050D80008E392 /* LineUtilities.cpp */,
FE7131ED14D03AED0008E392 /* LineCubicIntersection.cpp */,
FE7130A014CE0EEB0008E392 /* LineQuadraticIntersection.cpp */,
FECAA58314BCBD4E00B35E2C /* QuadraticBezierClip.cpp */,
@@ -425,10 +428,9 @@
FECA987714AA319300B35E2C /* QuadraticSubDivide.cpp */,
FECAA52B14BB6B0900B35E2C /* QuadraticUtilities.h */,
FE71324114D047670008E392 /* QuadraticUtilities.cpp */,
- FE71325D14D050D80008E392 /* LineUtilities.h */,
- FE71325E14D050D80008E392 /* LineUtilities.cpp */,
+ FE71351214D2E9F50008E392 /* RectUtilities.cpp */,
);
- name = CubicIntersection;
+ name = Intersection;
sourceTree = "<group>";
};
29B97317FDCFA39411CA2CEA /* Resources */ = {
@@ -455,6 +457,15 @@
name = Frameworks;
sourceTree = "<group>";
};
+ FE71354F14D305FD0008E392 /* ShapeOps */ = {
+ isa = PBXGroup;
+ children = (
+ FE71358514D309E90008E392 /* EdgeWalker.cpp */,
+ FE713C6114D9879B0008E392 /* TSearch.h */,
+ );
+ name = ShapeOps;
+ sourceTree = "<group>";
+ };
FEA5F4DA1497FFF6005052F9 /* Products */ = {
isa = PBXGroup;
children = (
@@ -497,6 +508,7 @@
FEC12CDF14913E650086BF1F /* LineIntersection_Test.cpp */,
FEC1238E149000100086BF1F /* LineParameteters_Test.cpp */,
FE7131C314CF5A960008E392 /* LineQuadraticIntersection_Test.cpp */,
+ FE7134DF14D1E5680008E392 /* Parameterization_Test.h */,
FECAA67814BCDBD600B35E2C /* QuadraticBezierClip_Test.cpp */,
FECAA6C614BDCE9B00B35E2C /* QuadraticIntersection_Test.cpp */,
FECAA68314BCDE2600B35E2C /* QuadraticIntersection_TestData.h */,
@@ -849,7 +861,6 @@
8D11072B0486CEB800E47090 /* InfoPlist.strings in Resources */,
1DDD58160DA1D0A300B32029 /* MainMenu.xib in Resources */,
FEED72B0144DD5710059E97B /* SampleApp.xib in Resources */,
- FEC11F84148E7C9C0086BF1F /* junk.htm in Resources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
@@ -879,7 +890,7 @@
FEC1191B148683330086BF1F /* Extrema.cpp in Sources */,
FEC1195514869DCA0086BF1F /* LineIntersection.cpp in Sources */,
FEC11E3E148D65780086BF1F /* CubicSubDivide.cpp in Sources */,
- FEC12116148EB4EC0086BF1F /* CubicIntersectionT.cpp in Sources */,
+ FEC12116148EB4EC0086BF1F /* CubicIntersection.cpp in Sources */,
FEC1211B148EB5200086BF1F /* CubicBezierClip.cpp in Sources */,
FEC1238F149000100086BF1F /* LineParameteters_Test.cpp in Sources */,
FEC123A6149001A00086BF1F /* SkAntiEdge.cpp in Sources */,
@@ -901,10 +912,13 @@
FE7131C414CF5A960008E392 /* LineQuadraticIntersection_Test.cpp in Sources */,
FE7131EE14D03AED0008E392 /* LineCubicIntersection.cpp in Sources */,
FE71324214D047670008E392 /* QuadraticUtilities.cpp in Sources */,
- FE71324F14D04D460008E392 /* CubicRoots.cpp in Sources */,
+ FE71324F14D04D460008E392 /* CubicUtilities.cpp in Sources */,
FE71325014D04D480008E392 /* CubeRoot.cpp in Sources */,
FE71325F14D050D80008E392 /* LineUtilities.cpp in Sources */,
FE71334214D06B0F0008E392 /* LineCubicIntersection_Test.cpp in Sources */,
+ FE7134F514D1E7C70008E392 /* LineParameterization.cpp in Sources */,
+ FE71351314D2E9F50008E392 /* RectUtilities.cpp in Sources */,
+ FE71358614D309E90008E392 /* EdgeWalker.cpp in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
@@ -969,8 +983,8 @@
INSTALL_PATH = "$(HOME)/Applications";
LIBRARY_SEARCH_PATHS = (
"$(inherited)",
- "\"$(SRCROOT)/../../skia/xcode/core/build/Debug\"",
- "\"$(SRCROOT)/../../skia/xcode/maccore/build/Debug\"",
+ "\"$(SRCROOT)/../../../xcode/core/build/Debug\"",
+ "\"$(SRCROOT)/../../../xcode/maccore/build/Debug\"",
);
PREBINDING = NO;
PRODUCT_NAME = edge;
@@ -992,8 +1006,8 @@
INSTALL_PATH = "$(HOME)/Applications";
LIBRARY_SEARCH_PATHS = (
"$(inherited)",
- "\"$(SRCROOT)/../../skia/xcode/core/build/Debug\"",
- "\"$(SRCROOT)/../../skia/xcode/maccore/build/Debug\"",
+ "\"$(SRCROOT)/../../../xcode/core/build/Debug\"",
+ "\"$(SRCROOT)/../../../xcode/maccore/build/Debug\"",
);
PRODUCT_NAME = edge;
};
@@ -1038,7 +1052,7 @@
PREBINDING = YES;
PRECOMPS_INCLUDE_HEADERS_FROM_BUILT_PRODUCTS_DIR = YES;
SDKROOT = "";
- USER_HEADER_SEARCH_PATHS = "../../skia/trunk/gpu/include ../../skia/trunk/src/core ../../skia/trunk/include/** ../../skia/trunk/gm";
+ USER_HEADER_SEARCH_PATHS = "../../gpu/include ../../src/core ../../include/** ../../gm";
};
name = Debug;
};