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, 164 insertions, 0 deletions

diff --git a/experimental/Intersection/QuadraticReduceOrder.cpp b/experimental/Intersection/QuadraticReduceOrder.cpp
new file mode 100644
index 0000000000..02d19565f1
--- /dev/null
+++ b/experimental/Intersection/QuadraticReduceOrder.cpp
@@ -0,0 +1,164 @@
+#include "CubicIntersection.h"
+#include "Extrema.h"
+#include "IntersectionUtilities.h"
+#include "LineParameters.h"
+
+static double interp_quad_coords(double a, double b, double c, double t)
+{
+    double ab = interp(a, b, t);
+    double bc = interp(b, c, t);
+    return interp(ab, bc, t);
+}
+
+static int coincident_line(const Quadratic& quad, Quadratic& reduction) {
+    reduction[0] = reduction[1] = quad[0];
+    return 1;
+}
+
+static int vertical_line(const Quadratic& quad, Quadratic& reduction) {
+    double tValue;
+    reduction[0] = quad[0];
+    reduction[1] = quad[2];
+    int smaller = reduction[1].y > reduction[0].y;
+    int larger = smaller ^ 1;
+    if (SkFindQuadExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue)) {
+        double yExtrema = interp_quad_coords(quad[0].y, quad[1].y, quad[2].y, tValue);
+        if (reduction[smaller].y > yExtrema) {
+            reduction[smaller].y = yExtrema;
+        } else if (reduction[larger].y < yExtrema) {
+            reduction[larger].y = yExtrema;
+        }
+    }
+    return 2;
+}
+
+static int horizontal_line(const Quadratic& quad, Quadratic& reduction) {
+    double tValue;
+    reduction[0] = quad[0];
+    reduction[1] = quad[2];
+    int smaller = reduction[1].x > reduction[0].x;
+    int larger = smaller ^ 1;
+    if (SkFindQuadExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue)) {
+        double xExtrema = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue);
+        if (reduction[smaller].x > xExtrema) {
+            reduction[smaller].x = xExtrema;
+        }  else if (reduction[larger].x < xExtrema) {
+            reduction[larger].x = xExtrema;
+        }
+    }
+    return 2;
+}
+
+static int check_linear(const Quadratic& quad, Quadratic& reduction,
+        int minX, int maxX, int minY, int maxY) {
+    int startIndex = 0;
+    int endIndex = 2;
+    while (quad[startIndex].approximatelyEqual(quad[endIndex])) {
+        --endIndex;
+        if (endIndex == 0) {
+            printf("%s shouldn't get here if all four points are about equal", __FUNCTION__);
+            assert(0);
+        }
+    }
+    LineParameters lineParameters;
+    lineParameters.quadEndPoints(quad, startIndex, endIndex);
+    double normalSquared = lineParameters.normalSquared();
+    double distance = lineParameters.controlPtDistance(quad); // not normalized
+    double limit = normalSquared * SquaredEpsilon;
+    double distSq = distance * distance;
+    if (distSq > limit) {
+        return 0;
+    }
+    // four are colinear: return line formed by outside
+    reduction[0] = quad[0];
+    reduction[1] = quad[2];
+    int sameSide;
+    bool useX = quad[maxX].x - quad[minX].x >= quad[maxY].y - quad[minY].y;
+    if (useX) {
+        sameSide = sign(quad[0].x - quad[1].x) + sign(quad[2].x - quad[1].x);
+    } else {
+        sameSide = sign(quad[0].y - quad[1].y) + sign(quad[2].y - quad[1].y);
+    }
+    if ((sameSide & 3) != 2) {
+        return 2;
+    }
+    double tValue;
+    int root;
+    if (useX) {
+        root = SkFindQuadExtrema(quad[0].x, quad[1].x, quad[2].x, &tValue);
+    } else {
+        root = SkFindQuadExtrema(quad[0].y, quad[1].y, quad[2].y, &tValue);
+    }
+    if (root) {
+        _Point extrema;
+        extrema.x = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue);
+        extrema.y = interp_quad_coords(quad[0].x, quad[1].x, quad[2].x, tValue);
+        // sameSide > 0 means mid is smaller than either [0] or [2], so replace smaller
+        int replace;
+        if (useX) {
+            if (extrema.x < quad[0].x ^ extrema.x < quad[2].x) {
+                return 2;
+            }
+            replace = (extrema.x < quad[0].x | extrema.x < quad[2].x)
+                    ^ quad[0].x < quad[2].x;
+        } else {
+            if (extrema.y < quad[0].y ^ extrema.y < quad[2].y) {
+                return 2;
+            }
+            replace = (extrema.y < quad[0].y | extrema.y < quad[2].y)
+                    ^ quad[0].y < quad[2].y;
+        }
+        reduction[replace] = extrema;
+    }
+    return 2;
+}
+
+// reduce to a quadratic or smaller
+// look for identical points
+// look for all four points in a line 
+    // note that three points in a line doesn't simplify a cubic
+// look for approximation with single quadratic
+    // save approximation with multiple quadratics for later
+int reduceOrder(const Quadratic& quad, Quadratic& reduction) {
+    int index, minX, maxX, minY, maxY;
+    int minXSet, minYSet;
+    minX = maxX = minY = maxY = 0;
+    minXSet = minYSet = 0;
+    for (index = 1; index < 3; ++index) {
+        if (quad[minX].x > quad[index].x) {
+            minX = index;
+        }
+        if (quad[minY].y > quad[index].y) {
+            minY = index;
+        }
+        if (quad[maxX].x < quad[index].x) {
+            maxX = index;
+        }
+        if (quad[maxY].y < quad[index].y) {
+            maxY = index;
+        }
+    }
+    for (index = 0; index < 3; ++index) {
+        if (approximately_equal(quad[index].x, quad[minX].x)) {
+            minXSet |= 1 << index;
+        }
+        if (approximately_equal(quad[index].y, quad[minY].y)) {
+            minYSet |= 1 << index;
+        }
+    }
+    if (minXSet == 0xF) { // test for vertical line
+        if (minYSet == 0xF) { // return 1 if all four are coincident
+            return coincident_line(quad, reduction);
+        }
+        return vertical_line(quad, reduction);
+    }
+    if (minYSet == 0xF) { // test for horizontal line
+        return horizontal_line(quad, reduction);
+    }
+    int result = check_linear(quad, reduction, minX, maxX, minY, maxY);
+    if (result) {
+        return result;
+    }
+    memcpy(reduction, quad, sizeof(Quadratic));
+    return 3;
+}