work in progress for shape operations

A    experimental/Intersection
A    experimental/Intersection/Intersections.h
A    experimental/Intersection/DataTypes.cpp
A    experimental/Intersection/QuadraticReduceOrder.cpp
A    experimental/Intersection/IntersectionUtilities.cpp
A    experimental/Intersection/CubicIntersection_Tests.h
A    experimental/Intersection/LineParameteters_Test.cpp
A    experimental/Intersection/ReduceOrder.cpp
A    experimental/Intersection/QuadraticIntersection.cpp
A    experimental/Intersection/Extrema.h
A    experimental/Intersection/CubicIntersection_TestData.h
A    experimental/Intersection/QuadraticParameterization_Test.cpp
A    experimental/Intersection/TestUtilities.cpp
A    experimental/Intersection/CubicRoots.cpp
A    experimental/Intersection/QuadraticParameterization.cpp
A    experimental/Intersection/QuadraticSubDivide.cpp
A    experimental/Intersection/LineIntersection_Test.cpp
A    experimental/Intersection/LineIntersection.cpp
A    experimental/Intersection/CubicParameterizationCode.cpp
A    experimental/Intersection/LineParameters.h
A    experimental/Intersection/CubicIntersection.h
A    experimental/Intersection/CubeRoot.cpp
A    experimental/Intersection/SkAntiEdge.h
A    experimental/Intersection/ConvexHull_Test.cpp
A    experimental/Intersection/CubicBezierClip_Test.cpp
A    experimental/Intersection/CubicIntersection_Tests.cpp
A    experimental/Intersection/CubicBezierClip.cpp
A    experimental/Intersection/CubicIntersectionT.cpp
A    experimental/Intersection/Inline_Tests.cpp
A    experimental/Intersection/ReduceOrder_Test.cpp
A    experimental/Intersection/QuadraticIntersection_TestData.h
A    experimental/Intersection/DataTypes.h
A    experimental/Intersection/Extrema.cpp
A    experimental/Intersection/EdgeApp.cpp
A    experimental/Intersection/CubicIntersection_TestData.cpp
A    experimental/Intersection/IntersectionUtilities.h
A    experimental/Intersection/CubicReduceOrder.cpp
A    experimental/Intersection/CubicCoincidence.cpp
A    experimental/Intersection/CubicIntersection_Test.cpp
A    experimental/Intersection/CubicIntersection.cpp
A    experimental/Intersection/QuadraticUtilities.h
A    experimental/Intersection/SkAntiEdge.cpp
A    experimental/Intersection/TestUtilities.h
A    experimental/Intersection/CubicParameterization_Test.cpp
A    experimental/Intersection/LineIntersection.h
A    experimental/Intersection/CubicSubDivide.cpp
A    experimental/Intersection/CubicParameterization.cpp
A    experimental/Intersection/QuadraticBezierClip_Test.cpp
A    experimental/Intersection/QuadraticBezierClip.cpp
A    experimental/Intersection/BezierClip_Test.cpp
A    experimental/Intersection/ConvexHull.cpp
A    experimental/Intersection/BezierClip.cpp
A    experimental/Intersection/QuadraticIntersection_TestData.cpp



git-svn-id: http://skia.googlecode.com/svn/trunk@3005 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 77 insertions, 0 deletions

diff --git a/experimental/Intersection/Extrema.cpp b/experimental/Intersection/Extrema.cpp
new file mode 100644
index 0000000000..0b850607d4
--- /dev/null
+++ b/experimental/Intersection/Extrema.cpp
@@ -0,0 +1,77 @@
+#include "DataTypes.h"
+#include "Extrema.h"
+
+static int valid_unit_divide(double numer, double denom, double* ratio)
+{
+    if (numer < 0)
+    {
+        numer = -numer;
+        denom = -denom;
+    }
+
+    if (denom == 0 || numer == 0 || numer >= denom)
+        return 0;
+
+    double r = numer / denom;
+    if (r == 0) // catch underflow if numer <<<< denom
+        return 0;
+    *ratio = r;
+    return 1;
+}
+
+/** From Numerical Recipes in C.
+
+    Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C])
+    x1 = Q / A
+    x2 = C / Q
+*/
+static int SkFindUnitQuadRoots(double A, double B, double C, double roots[2])
+{
+    if (A == 0)
+        return valid_unit_divide(-C, B, roots);
+
+    double* r = roots;
+
+    double R = B*B - 4*A*C;
+    if (R < 0) {  // complex roots
+        return 0;
+    }
+    R = sqrt(R);
+
+    double Q = (B < 0) ? -(B-R)/2 : -(B+R)/2;
+    r += valid_unit_divide(Q, A, r);
+    r += valid_unit_divide(C, Q, r);
+    if (r - roots == 2 && approximately_equal(roots[0], roots[1])) { // nearly-equal?
+        r -= 1; // skip the double root
+    }
+    return (int)(r - roots);
+}
+
+/** Cubic'(t) = At^2 + Bt + C, where
+    A = 3(-a + 3(b - c) + d)
+    B = 6(a - 2b + c)
+    C = 3(b - a)
+    Solve for t, keeping only those that fit betwee 0 < t < 1
+*/
+int SkFindCubicExtrema(double a, double b, double c, double d, double tValues[2])
+{
+    // we divide A,B,C by 3 to simplify
+    double A = d - a + 3*(b - c);
+    double B = 2*(a - b - b + c);
+    double C = b - a;
+
+    return SkFindUnitQuadRoots(A, B, C, tValues);
+}
+
+/** Quad'(t) = At + B, where
+    A = 2(a - 2b + c)
+    B = 2(b - a)
+    Solve for t, only if it fits between 0 < t < 1
+*/
+int SkFindQuadExtrema(double a, double b, double c, double tValue[1])
+{
+    /*  At + B == 0
+        t = -B / A
+    */
+    return valid_unit_divide(a - b, a - b - b + c, tValue);
+}