From c682590538a27d73489bc91c098e000fdfb07ccf Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Fri, 3 Feb 2012 22:07:47 +0000 Subject: [PATCH] save work in progress git-svn-id: http://skia.googlecode.com/svn/trunk@3141 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/ConvexHull.cpp | 2 +- experimental/Intersection/ConvexHull_Test.cpp | 2 +- experimental/Intersection/CubicBezierClip.cpp | 2 +- experimental/Intersection/CubicBezierClip_Test.cpp | 2 +- experimental/Intersection/CubicBounds.cpp | 10 + experimental/Intersection/CubicIntersection.cpp | 170 +++++-- .../Intersection/CubicIntersection_Test.cpp | 4 +- .../Intersection/CubicParameterization.cpp | 187 +++++++- .../Intersection/CubicParameterizationCode.cpp | 76 +++- .../Intersection/CubicParameterization_Test.cpp | 22 +- .../CubicParameterization_TestUtility.cpp | 14 + experimental/Intersection/CubicReduceOrder.cpp | 2 +- .../Intersection/CubicReduceOrder_Test.cpp | 2 +- experimental/Intersection/CubicSubDivide.cpp | 2 +- experimental/Intersection/CubicUtilities.cpp | 76 ++++ experimental/Intersection/CubicUtilities.h | 1 + experimental/Intersection/CurveIntersection.h | 34 ++ experimental/Intersection/DataTypes.cpp | 27 ++ experimental/Intersection/DataTypes.h | 16 +- experimental/Intersection/EdgeWalker.cpp | 498 +++++++++++++++++++++ experimental/Intersection/Inline_Tests.cpp | 2 +- experimental/Intersection/Intersection_Tests.cpp | 4 + .../Intersection/LineCubicIntersection.cpp | 80 ++-- .../Intersection/LineCubicIntersection_Test.cpp | 36 +- experimental/Intersection/LineIntersection.cpp | 151 +++---- experimental/Intersection/LineIntersection.h | 3 +- .../Intersection/LineIntersection_Test.cpp | 58 ++- experimental/Intersection/LineParameterization.cpp | 34 ++ .../Intersection/LineParameteters_Test.cpp | 2 +- .../Intersection/LineQuadraticIntersection.cpp | 4 +- .../LineQuadraticIntersection_Test.cpp | 4 +- experimental/Intersection/LineUtilities.cpp | 11 +- experimental/Intersection/Parameterization_Test.h | 6 + experimental/Intersection/QuadraticBezierClip.cpp | 2 +- .../Intersection/QuadraticBezierClip_Test.cpp | 2 +- .../Intersection/QuadraticIntersection.cpp | 21 +- .../Intersection/QuadraticIntersection_Test.cpp | 4 +- .../Intersection/QuadraticParameterization.cpp | 4 +- .../QuadraticParameterization_Test.cpp | 3 +- .../QuadraticParameterization_TestUtility.cpp | 2 + experimental/Intersection/QuadraticReduceOrder.cpp | 2 +- .../Intersection/QuadraticReduceOrder_Test.cpp | 2 +- experimental/Intersection/QuadraticSubDivide.cpp | 2 +- experimental/Intersection/RectUtilities.cpp | 44 ++ experimental/Intersection/TSearch.h | 78 ++++ experimental/Intersection/TestUtilities.cpp | 29 +- experimental/Intersection/TestUtilities.h | 3 - .../Intersection/edge.xcodeproj/project.pbxproj | 122 ++--- 48 files changed, 1525 insertions(+), 339 deletions(-) create mode 100644 experimental/Intersection/CubicBounds.cpp create mode 100644 experimental/Intersection/CubicUtilities.cpp create mode 100644 experimental/Intersection/CurveIntersection.h create mode 100644 experimental/Intersection/EdgeWalker.cpp create mode 100644 experimental/Intersection/LineParameterization.cpp create mode 100644 experimental/Intersection/Parameterization_Test.h create mode 100644 experimental/Intersection/RectUtilities.cpp create mode 100644 experimental/Intersection/TSearch.h 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 // 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,80 +1,154 @@ -#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); +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 intersect() { + double minT1, minT2, maxT1, maxT2; + if (!bezier_clip(cubic2, cubic1, minT1, maxT1)) { + return false; + } + if (!bezier_clip(cubic1, cubic2, minT2, maxT2)) { + return false; + } + int split; + if (maxT1 - minT1 < maxT2 - minT2) { + intersections.swap(); + 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: -static bool intersect(const Cubic& smaller, const Cubic& larger, - Intersections& intersections) { - // FIXME: carry order with cubic so we don't call it repeatedly +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) { + if (reduceOrder(smaller, smallResult, + kReduceOrder_NoQuadraticsAllowed) <= 2) { Cubic largeResult; - if (reduceOrder(larger, largeResult, kReduceOrder_NoQuadraticsAllowed) <= 2) { - _Point pt; + if (reduceOrder(larger, largeResult, + kReduceOrder_NoQuadraticsAllowed) <= 2) { const _Line& smallLine = (const _Line&) smallResult; const _Line& largeLine = (const _Line&) largeResult; - if (!lineIntersect(smallLine, largeLine, &pt)) { + double smallT[2]; + double largeT[2]; + // 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); - intersections.add(smallT, largeT); + 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) { - intersections.add(minT, 0.5); + 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; } - return chop(larger, smaller, intersections, minT, maxT); + + 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(const Cubic& smaller, const Cubic& larger, - Intersections& intersections, double minT, double maxT) { +bool chop(double minT1, double maxT1, double minT2, double maxT2, int split) { + ++depth; 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); + 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(); } - 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); - } + bool result = intersect(minT1, maxT1, minT2, maxT2); intersections.swap(); + --depth; return result; } -bool intersectStart(const Cubic& cubic1, const Cubic& cubic2, - Intersections& intersections) { - double minT1, minT2, maxT1, maxT2; - if (!bezier_clip(cubic2, cubic1, minT1, maxT1)) { - return false; - } - if (!bezier_clip(cubic1, cubic2, minT2, maxT2)) { - return false; - } - if (maxT1 - minT1 < maxT2 - minT2) { - intersections.swap(); - return chop(cubic1, cubic2, intersections, minT1, maxT1); - } - return chop(cubic2, cubic1, intersections, minT2, maxT2); +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 @@ void CubicIntersection_Test() { 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 @@ enum { 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 @@ static void calc_ABCD(double a, double e, double p[coeff_count]) { * 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 @@ static double calc_E(double a, double b, double c, double d, + 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 @@ static double calc_F(double a, double b, double c, double d, - 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 @@ static double calc_G(double a, double b, double c, double d, + 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 @@ static double calc_H(double a, double b, double c, double d, + 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 @@ static double calc_I(double a, double b, double c, double d, - 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 @@ static double calc_J(double a, double b, double c, double d, } // 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 @@ static void alt_set_abcd(const double* cubic, double& a, double& b, double& c, 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 @@ bool implicit_matches(const Cubic& one, const Cubic& two) { 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 @@ bool implicit_matches(const Cubic& one, const Cubic& two) { 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 @@ const char result2[] = " 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 @@ void CubicCoincidence_Test() { // 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 @@ void CubicParameterization_Test() { __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 @@ static void parameter_coeffs(const Cubic& cubic, double coeffs[coeff_count]) { 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 @@ void x_at(const _Point& p1, const _Point& p2, double top, double bottom, 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 @@ struct _Rect { } } + 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 @@ bool rotate(const Cubic& cubic, int zero, int index, Cubic& rotPath); 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& 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& 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 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 fCached; // list of edges already intercepted + SkTArray fIntercepts; // one per verb + + + // persistent data + SkTDArray fPts; + SkTDArray fVerbs; + Bounds fBounds; + signed char fWinding; +}; + +class EdgeBuilder { +public: + +EdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray& 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& 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 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 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(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 @@ void Intersection_Tests() { LineQuadraticIntersection_Test(); LineCubicIntersection_Test(); + testSimplify(); + QuadraticCoincidence_Test(); QuadraticReduceOrder_Test(); QuadraticBezierClip_Test(); @@ -26,4 +29,5 @@ void Intersection_Tests() { 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 @@ line: (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 @@ if i goes to infinity, we can rewrite the line in terms of x. Mathematica: (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 @@ The near-vertical case, in terms of: Ax^3 + Bx^2 + Cx + D == 0 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 @@ bool intersect() { 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); +} + +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); } -protected: - double findLineT(double t) { const double* cPtr; const double* lPtr; @@ -118,6 +119,7 @@ double findLineT(double t) { 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 @@ private: 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 @@ void LineCubicIntersection_Test() { 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 // 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); - } - /* 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; - } + return 0; } - /* 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 moreHorizontal; }; -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 @@ void LineQuadraticIntersection_Test() { } 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 // 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 @@ bool intersect(double minT1, double maxT1, double minT2, double maxT2) { 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 depth; 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 @@ void QuadraticIntersection_Test() { } 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 +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 +void QSort(T** base, size_t count) +{ + SkASSERT(base); + + if (count <= 1) { + return; + } + QSort_Partition(base, base + (count - 1)); +} + +template +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 +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 @@ bool controls_inside(const Cubic& cubic) { || (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 = ""; }; 8D1107310486CEB800E47090 /* edge-Info.plist */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.plist.xml; path = "edge-Info.plist"; sourceTree = ""; }; 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 = ""; }; FE7130A014CE0EEB0008E392 /* LineQuadraticIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineQuadraticIntersection.cpp; sourceTree = ""; }; FE7131C314CF5A960008E392 /* LineQuadraticIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineQuadraticIntersection_Test.cpp; sourceTree = ""; }; @@ -235,10 +235,15 @@ FE71325D14D050D80008E392 /* LineUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LineUtilities.h; sourceTree = ""; }; FE71325E14D050D80008E392 /* LineUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineUtilities.cpp; sourceTree = ""; }; FE71334114D06B0F0008E392 /* LineCubicIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineCubicIntersection_Test.cpp; sourceTree = ""; }; - 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 = ""; }; + FE7134F414D1E7C70008E392 /* LineParameterization.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineParameterization.cpp; sourceTree = ""; }; + FE71351214D2E9F50008E392 /* RectUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RectUtilities.cpp; sourceTree = ""; }; + FE71358514D309E90008E392 /* EdgeWalker.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = EdgeWalker.cpp; sourceTree = ""; }; + FE713C6114D9879B0008E392 /* TSearch.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TSearch.h; sourceTree = ""; }; + 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 = ""; }; FEA670F113C49E2200FE6FC1 /* SkAntiEdge.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SkAntiEdge.h; sourceTree = ""; }; - 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 = ""; }; FEC11A881487D2F50086BF1F /* IntersectionUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IntersectionUtilities.h; sourceTree = ""; }; FEC11E3D148D65780086BF1F /* CubicSubDivide.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicSubDivide.cpp; sourceTree = ""; }; - 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 = ""; }; + FEC12115148EB4EC0086BF1F /* CubicIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection.cpp; sourceTree = ""; }; FEC1211A148EB5200086BF1F /* CubicBezierClip.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicBezierClip.cpp; sourceTree = ""; }; FEC1238E149000100086BF1F /* LineParameteters_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineParameteters_Test.cpp; sourceTree = ""; }; FEC12CDF14913E650086BF1F /* LineIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LineIntersection_Test.cpp; sourceTree = ""; }; @@ -270,7 +274,7 @@ FECAA52114BB527000B35E2C /* QuadraticIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticIntersection.cpp; sourceTree = ""; }; FECAA52B14BB6B0900B35E2C /* QuadraticUtilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = QuadraticUtilities.h; sourceTree = ""; }; FECAA53014BB934700B35E2C /* CubeRoot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubeRoot.cpp; sourceTree = ""; }; - FECAA54114BC838600B35E2C /* CubicRoots.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicRoots.cpp; sourceTree = ""; }; + FECAA54114BC838600B35E2C /* CubicUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicUtilities.cpp; sourceTree = ""; }; FECAA56C14BCA23200B35E2C /* QuadraticReduceOrder.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticReduceOrder.cpp; sourceTree = ""; }; FECAA58314BCBD4E00B35E2C /* QuadraticBezierClip.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticBezierClip.cpp; sourceTree = ""; }; FECAA67814BCDBD600B35E2C /* QuadraticBezierClip_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticBezierClip_Test.cpp; sourceTree = ""; }; @@ -281,29 +285,28 @@ FECAAB7F14BDFAFD00B35E2C /* CubicParameterization_TestUtility.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicParameterization_TestUtility.cpp; sourceTree = ""; }; FECAACA614BE1C6100B35E2C /* QuadraticParameterization_TestUtility.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = QuadraticParameterization_TestUtility.cpp; sourceTree = ""; }; FED53C381483CB9400F6359E /* Inline_Tests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Inline_Tests.cpp; sourceTree = ""; }; - FEE103331416542A006952D6 /* CubicIntersection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection.cpp; sourceTree = ""; }; - 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 = ""; }; FEED75DC144DD6590059E97B /* QuartzCore.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = QuartzCore.framework; path = /System/Library/Frameworks/QuartzCore.framework; sourceTree = ""; }; FEED75DE144DD6840059E97B /* libz.dylib */ = {isa = PBXFileReference; lastKnownFileType = "compiled.mach-o.dylib"; name = libz.dylib; path = /usr/lib/libz.dylib; sourceTree = ""; }; FEED7625144F22E20059E97B /* CubicReduceOrder_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicReduceOrder_Test.cpp; sourceTree = ""; }; FEED762B144F236C0059E97B /* CubicIntersection_TestData.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection_TestData.cpp; sourceTree = ""; }; - FEED762F144F23CA0059E97B /* CubicIntersection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CubicIntersection.h; sourceTree = ""; }; + FEED762F144F23CA0059E97B /* CurveIntersection.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CurveIntersection.h; sourceTree = ""; }; FEED7632144F25150059E97B /* CubicIntersection_TestData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CubicIntersection_TestData.h; sourceTree = ""; }; FEED764B144F29BD0059E97B /* TestUtilities.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TestUtilities.cpp; sourceTree = ""; }; FEED764F144F2A160059E97B /* DataTypes.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DataTypes.h; sourceTree = ""; }; @@ -312,10 +315,10 @@ FEED7689144F2E7D0059E97B /* CubicIntersection_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CubicIntersection_Test.cpp; sourceTree = ""; }; FEED76C0144F3E7F0059E97B /* ConvexHull_Test.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ConvexHull_Test.cpp; sourceTree = ""; }; FEED76ED144F66E90059E97B /* Intersection_Tests.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Intersection_Tests.cpp; sourceTree = ""; }; - 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 = ""; }; - 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 = ""; }; 29B97317FDCFA39411CA2CEA /* Resources */ = { @@ -455,6 +457,15 @@ name = Frameworks; sourceTree = ""; }; + FE71354F14D305FD0008E392 /* ShapeOps */ = { + isa = PBXGroup; + children = ( + FE71358514D309E90008E392 /* EdgeWalker.cpp */, + FE713C6114D9879B0008E392 /* TSearch.h */, + ); + name = ShapeOps; + sourceTree = ""; + }; 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; }; -- 2.7.4