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
diff --git a/experimental/Intersection/CubicIntersection.cpp b/experimental/Intersection/CubicIntersection.cpp
new file mode 100644
index 0000000..c41e0d7
--- /dev/null
+++ b/experimental/Intersection/CubicIntersection.cpp
@@ -0,0 +1,80 @@
+#include "CubicIntersection.h"
+#include "Intersections.h"
+#include "LineIntersection.h"
+
+static bool chop(const Cubic& smaller, const Cubic& larger,
+ Intersections& intersections, double minT, double maxT);
+
+static bool intersect(const Cubic& smaller, const Cubic& larger,
+ Intersections& intersections) {
+ // FIXME: carry order with cubic so we don't call it repeatedly
+ Cubic smallResult;
+ if (reduceOrder(smaller, smallResult, kReduceOrder_NoQuadraticsAllowed) <= 2) {
+ Cubic largeResult;
+ if (reduceOrder(larger, largeResult, kReduceOrder_NoQuadraticsAllowed) <= 2) {
+ _Point pt;
+ const _Line& smallLine = (const _Line&) smallResult;
+ const _Line& largeLine = (const _Line&) largeResult;
+ if (!lineIntersect(smallLine, largeLine, &pt)) {
+ return false;
+ }
+ double smallT = t_at(smallLine, pt);
+ double largeT = t_at(largeLine, pt);
+ intersections.add(smallT, largeT);
+ return true;
+ }
+ }
+ double minT, maxT;
+ if (!bezier_clip(smaller, larger, minT, maxT)) {
+ if (minT == maxT) {
+ intersections.add(minT, 0.5);
+ return true;
+ }
+ return false;
+ }
+ return chop(larger, smaller, intersections, minT, maxT);
+}
+
+bool chop(const Cubic& smaller, const Cubic& larger,
+ Intersections& intersections, double minT, double maxT) {
+ intersections.swap();
+ if (maxT - minT > 0.8) { // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf Multiple intersections
+ CubicPair cubicPair;
+ chop_at(larger, cubicPair, 0.5);
+ int used = intersections.used();
+ if (intersect(cubicPair.first(), smaller, intersections)) {
+ intersections.offset(used, 0, 0.5);
+ }
+ used = intersections.used();
+ if (intersect(cubicPair.second(), smaller, intersections)) {
+ intersections.offset(used, 0.5, 1);
+ }
+ intersections.swap();
+ return intersections.intersected();
+ }
+ Cubic cut;
+ sub_divide(smaller, minT, maxT, cut);
+ int used = intersections.used();
+ bool result = intersect(cut, larger, intersections);
+ if (result) {
+ intersections.offset(used, minT, maxT);
+ }
+ intersections.swap();
+ return result;
+}
+
+bool intersectStart(const Cubic& cubic1, const Cubic& cubic2,
+ Intersections& intersections) {
+ 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);
+}