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/ReduceOrder_Test.cpp b/experimental/Intersection/ReduceOrder_Test.cpp
new file mode 100644
index 0000000..04aea1a
--- /dev/null
+++ b/experimental/Intersection/ReduceOrder_Test.cpp
@@ -0,0 +1,137 @@
+#include "CubicIntersection.h"
+#include "CubicIntersection_TestData.h"
+#include "CubicIntersection_Tests.h"
+#include "TestUtilities.h"
+
+void ReduceOrder_Test() {
+ size_t index;
+ Cubic reduce;
+ int order;
+ enum {
+ RunAll,
+ RunPointDegenerates,
+ RunNotPointDegenerates,
+ RunLines,
+ RunNotLines,
+ RunModEpsilonLines,
+ RunLessEpsilonLines,
+ RunNegEpsilonLines,
+ RunQuadraticLines,
+ RunQuadraticModLines,
+ RunComputedLines,
+ RunNone
+ } run = RunAll;
+ int firstTestIndex = 0;
+#if 0
+ run = RunComputedLines;
+ firstTestIndex = 18;
+#endif
+ int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates ? firstTestIndex : INT_MAX;
+ int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates ? firstTestIndex : INT_MAX;
+ int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : INT_MAX;
+ int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : INT_MAX;
+ int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines ? firstTestIndex : INT_MAX;
+ int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines ? firstTestIndex : INT_MAX;
+ int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines ? firstTestIndex : INT_MAX;
+ int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines ? firstTestIndex : INT_MAX;
+ int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines ? firstTestIndex : INT_MAX;
+ int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines ? firstTestIndex : INT_MAX;
+
+ for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
+ const Cubic& cubic = pointDegenerates[index];
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (order != 1) {
+ printf("[%d] pointDegenerates order=%d\n", (int) index, order);
+ }
+ }
+ for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
+ const Cubic& cubic = notPointDegenerates[index];
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (order == 1) {
+ printf("[%d] notPointDegenerates order=%d\n", (int) index, order);
+ }
+ }
+ for (index = firstLinesTest; index < lines_count; ++index) {
+ const Cubic& cubic = lines[index];
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (order != 2) {
+ printf("[%d] lines order=%d\n", (int) index, order);
+ }
+ }
+ for (index = firstNotLinesTest; index < notLines_count; ++index) {
+ const Cubic& cubic = notLines[index];
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (order == 2) {
+ printf("[%d] notLines order=%d\n", (int) index, order);
+ }
+ }
+ for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
+ const Cubic& cubic = modEpsilonLines[index];
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (order == 2) {
+ printf("[%d] line mod by epsilon order=%d\n", (int) index, order);
+ }
+ }
+ for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
+ const Cubic& cubic = lessEpsilonLines[index];
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (order != 2) {
+ printf("[%d] line less by epsilon/2 order=%d\n", (int) index, order);
+ }
+ }
+ for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
+ const Cubic& cubic = negEpsilonLines[index];
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (order != 2) {
+ printf("[%d] line neg by epsilon/2 order=%d\n", (int) index, order);
+ }
+ }
+ for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
+ const Quadratic& quad = quadraticLines[index];
+ Cubic cubic;
+ quad_to_cubic(quad, cubic);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (order != 2) {
+ printf("[%d] line quad order=%d\n", (int) index, order);
+ }
+ }
+ for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
+ const Quadratic& quad = quadraticModEpsilonLines[index];
+ Cubic cubic;
+ quad_to_cubic(quad, cubic);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (order != 3) {
+ printf("[%d] line mod quad order=%d\n", (int) index, order);
+ }
+ }
+
+ // test if computed line end points are valid
+ for (index = firstComputedLinesTest; index < lines_count; ++index) {
+ const Cubic& cubic = lines[index];
+ bool controlsInside = controls_inside(cubic);
+ order = reduceOrder(cubic, reduce, kReduceOrder_QuadraticsAllowed);
+ if (reduce[0].x == reduce[1].x && reduce[0].y == reduce[1].y) {
+ printf("[%d] line computed ends match order=%d\n", (int) index, order);
+ }
+ if (controlsInside) {
+ if ( reduce[0].x != cubic[0].x && reduce[0].x != cubic[3].x
+ || reduce[0].y != cubic[0].y && reduce[0].y != cubic[3].y
+ || reduce[1].x != cubic[0].x && reduce[1].x != cubic[3].x
+ || reduce[1].y != cubic[0].y && reduce[1].y != cubic[3].y) {
+ printf("[%d] line computed ends order=%d\n", (int) index, order);
+ }
+ } else {
+ // binary search for extrema, compare against actual results
+ // while a control point is outside of bounding box formed by end points, split
+ _Rect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX};
+ find_tight_bounds(cubic, bounds);
+ if ( !approximately_equal(reduce[0].x, bounds.left) && !approximately_equal(reduce[0].x, bounds.right)
+ || !approximately_equal(reduce[0].y, bounds.top) && !approximately_equal(reduce[0].y, bounds.bottom)
+ || !approximately_equal(reduce[1].x, bounds.left) && !approximately_equal(reduce[1].x, bounds.right)
+ || !approximately_equal(reduce[1].y, bounds.top) && !approximately_equal(reduce[1].y, bounds.bottom)) {
+ printf("[%d] line computed tight bounds order=%d\n", (int) index, order);
+ }
+
+ }
+ }
+}