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/TestUtilities.cpp b/experimental/Intersection/TestUtilities.cpp
new file mode 100644
index 0000000..5e3c18e
--- /dev/null
+++ b/experimental/Intersection/TestUtilities.cpp
@@ -0,0 +1,69 @@
+#include "CubicIntersection.h"
+#include "TestUtilities.h"
+
+void quad_to_cubic(const Quadratic& quad, Cubic& cubic) {
+ cubic[0] = quad[0];
+ cubic[1].x = quad[0].x / 3 + quad[1].x * 2 / 3;
+ cubic[1].y = quad[0].y / 3 + quad[1].y * 2 / 3;
+ cubic[2].x = quad[2].x / 3 + quad[1].x * 2 / 3;
+ cubic[2].y = quad[2].y / 3 + quad[1].y * 2 / 3;
+ cubic[3] = quad[2];
+}
+
+static bool tiny(const Cubic& cubic) {
+ int index, minX, maxX, minY, maxY;
+ minX = maxX = minY = maxY = 0;
+ for (index = 1; index < 4; ++index) {
+ if (cubic[minX].x > cubic[index].x) {
+ minX = index;
+ }
+ if (cubic[minY].y > cubic[index].y) {
+ minY = index;
+ }
+ if (cubic[maxX].x < cubic[index].x) {
+ maxX = index;
+ }
+ if (cubic[maxY].y < cubic[index].y) {
+ maxY = index;
+ }
+ }
+ return approximately_equal(cubic[maxX].x, cubic[minX].x)
+ && approximately_equal(cubic[maxY].y, cubic[minY].y);
+}
+
+void find_tight_bounds(const Cubic& cubic, _Rect& bounds) {
+ CubicPair cubicPair;
+ chop_at(cubic, cubicPair, 0.5);
+ if (!tiny(cubicPair.first()) && !controls_inside(cubicPair.first())) {
+ find_tight_bounds(cubicPair.first(), bounds);
+ } else {
+ bounds.add(cubicPair.first()[0]);
+ bounds.add(cubicPair.first()[3]);
+ }
+ if (!tiny(cubicPair.second()) && !controls_inside(cubicPair.second())) {
+ find_tight_bounds(cubicPair.second(), bounds);
+ } else {
+ bounds.add(cubicPair.second()[0]);
+ bounds.add(cubicPair.second()[3]);
+ }
+}
+
+bool controls_inside(const Cubic& cubic) {
+ return
+ ((cubic[0].x <= cubic[1].x && cubic[0].x <= cubic[2].x && cubic[1].x <= cubic[3].x && cubic[2].x <= cubic[3].x)
+ || (cubic[0].x >= cubic[1].x && cubic[0].x >= cubic[2].x && cubic[1].x >= cubic[3].x && cubic[2].x >= cubic[3].x))
+ && ((cubic[0].y <= cubic[1].y && cubic[0].y <= cubic[2].y && cubic[1].y <= cubic[3].y && cubic[2].y <= cubic[3].y)
+ || (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;
+}