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

diff --git a/experimental/Intersection/CubicBezierClip.cpp b/experimental/Intersection/CubicBezierClip.cpp
new file mode 100644
index 0000000000..1b5c60c182
--- /dev/null
+++ b/experimental/Intersection/CubicBezierClip.cpp
@@ -0,0 +1,83 @@
+#include "CubicIntersection.h"
+#include "LineParameters.h"
+#include <algorithm> // used for std::swap
+
+// return false if unable to clip (e.g., unable to create implicit line)
+// caller should subdivide, or create degenerate if the values are too small
+bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT) {
+    minT = 1;
+    maxT = 0;
+    // determine normalized implicit line equation for pt[0] to pt[3]
+    //   of the form ax + by + c = 0, where a*a + b*b == 1
+    
+    // find the implicit line equation parameters
+    LineParameters endLine;
+    endLine.cubicEndPoints(cubic1);
+    if (!endLine.normalize()) {
+        printf("line cannot be normalized: need more code here\n");
+        return false;
+    }
+
+    double distance[2];
+    endLine.controlPtDistance(cubic1, distance);
+    
+    // find fat line
+    double top = distance[0];
+    double bottom = distance[1];
+    if (top > bottom) {
+        std::swap(top, bottom);
+    }
+    if (top * bottom >= 0) {
+        const double scale = 3/4.0; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf (13)
+        if (top < 0) {
+            top *= scale;
+            bottom = 0;
+        } else {
+            top = 0;
+            bottom *= scale;
+        }
+    } else {
+        const double scale = 4/9.0; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf (15)
+        top *= scale;
+        bottom *= scale;
+    }
+    
+    // compute intersecting candidate distance
+    Cubic distance2y; // points with X of (0, 1/3, 2/3, 1)
+    endLine.cubicDistanceY(cubic2, distance2y);
+    
+    int flags = 0;
+    if (approximately_lesser(distance2y[0].y, top)) {
+        flags |= kFindTopMin;
+    } else if (approximately_greater(distance2y[0].y, bottom)) {
+        flags |= kFindBottomMin;
+    } else {
+        minT = 0;
+    }
+
+    if (approximately_lesser(distance2y[3].y, top)) {
+        flags |= kFindTopMax;
+    } else if (approximately_greater(distance2y[3].y, bottom)) {
+        flags |= kFindBottomMax;
+    } else {
+        maxT = 1;
+    }
+    // Find the intersection of distance convex hull and fat line.
+    char to_0[2];
+    char to_3[2];
+    bool do_1_2_edge = convex_x_hull(distance2y, to_0, to_3);
+    x_at(distance2y[0], distance2y[to_0[0]], top, bottom, flags, minT, maxT);
+    if (to_0[0] != to_0[1]) {
+        x_at(distance2y[0], distance2y[to_0[1]], top, bottom, flags, minT, maxT);
+    }
+    x_at(distance2y[to_3[0]], distance2y[3], top, bottom, flags, minT, maxT);
+    if (to_3[0] != to_3[1]) {
+        x_at(distance2y[to_3[1]], distance2y[3], top, bottom, flags, minT, maxT);
+    }
+    if (do_1_2_edge) {
+        x_at(distance2y[1], distance2y[2], top, bottom, flags, minT, maxT);
+    }
+    
+    return minT < maxT; // returns false if distance shows no intersection
+}
+