aboutsummaryrefslogtreecommitdiffhomepage
path: root/experimental
diff options
context:
space:
mode:
Diffstat (limited to 'experimental')
-rw-r--r--experimental/Intersection/CubicToQuadratics.cpp18
-rw-r--r--experimental/Intersection/CubicToQuadratics_Test.cpp219
-rw-r--r--experimental/Intersection/CubicUtilities.h3
-rw-r--r--experimental/Intersection/Intersection_Tests.cpp1
-rw-r--r--experimental/Intersection/Intersection_Tests.h1
5 files changed, 156 insertions, 86 deletions
diff --git a/experimental/Intersection/CubicToQuadratics.cpp b/experimental/Intersection/CubicToQuadratics.cpp
index 7cea4d441c..424836c633 100644
--- a/experimental/Intersection/CubicToQuadratics.cpp
+++ b/experimental/Intersection/CubicToQuadratics.cpp
@@ -46,7 +46,7 @@ http://www.caffeineowl.com/graphics/2d/vectorial/cubic2quad01.html
#include "CubicUtilities.h"
#include "CurveIntersection.h"
-static double calcTDiv(const Cubic& cubic, double start) {
+static double calcTDiv(const Cubic& cubic, double precision, double start) {
const double adjust = sqrt(3) / 36;
Cubic sub;
const Cubic* cPtr;
@@ -61,7 +61,7 @@ static double calcTDiv(const Cubic& cubic, double start) {
double dx = c[3].x - 3 * (c[2].x - c[1].x) - c[0].x;
double dy = c[3].y - 3 * (c[2].y - c[1].y) - c[0].y;
double dist = sqrt(dx * dx + dy * dy);
- double tDiv3 = FLT_EPSILON / (adjust * dist);
+ double tDiv3 = precision / (adjust * dist);
return cube_root(tDiv3);
}
@@ -72,7 +72,7 @@ static void demote(const Cubic& cubic, Quadratic& quad) {
quad[2] = cubic[3];
}
-int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics) {
+int cubic_to_quadratics(const Cubic& cubic, double precision, SkTDArray<Quadratic>& quadratics) {
quadratics.setCount(1); // FIXME: every place I have setCount(), I also want setReserve()
Cubic reduced;
int order = reduceOrder(cubic, reduced, kReduceOrder_QuadraticsAllowed);
@@ -80,10 +80,10 @@ int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics) {
memcpy(quadratics[0], reduced, order * sizeof(_Point));
return order;
}
- double tDiv = calcTDiv(cubic, 0);
+ double tDiv = calcTDiv(cubic, precision, 0);
if (approximately_greater_than_one(tDiv)) {
demote(cubic, quadratics[0]);
- return 2;
+ return 3;
}
if (tDiv >= 0.5) {
CubicPair pair;
@@ -91,7 +91,7 @@ int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics) {
quadratics.setCount(2);
demote(pair.first(), quadratics[0]);
demote(pair.second(), quadratics[1]);
- return 2;
+ return 3;
}
double start = 0;
int index = -1;
@@ -99,17 +99,17 @@ int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics) {
// or if the control points are tangent to each other
do {
Cubic part;
- sub_divide(part, start, tDiv, part);
+ sub_divide(cubic, start, tDiv, part);
quadratics.append();
demote(part, quadratics[++index]);
if (tDiv == 1) {
break;
}
start = tDiv;
- tDiv = calcTDiv(cubic, start);
+ tDiv = calcTDiv(cubic, precision, start);
if (tDiv > 1) {
tDiv = 1;
}
} while (true);
- return 2;
+ return 3;
}
diff --git a/experimental/Intersection/CubicToQuadratics_Test.cpp b/experimental/Intersection/CubicToQuadratics_Test.cpp
index 61f6f7d11b..c4dc96a39e 100644
--- a/experimental/Intersection/CubicToQuadratics_Test.cpp
+++ b/experimental/Intersection/CubicToQuadratics_Test.cpp
@@ -4,8 +4,90 @@
#include "QuadraticIntersection_TestData.h"
#include "TestUtilities.h"
+static double calcPrecision(const Cubic& cubic) {
+ _Rect dRect;
+ dRect.setBounds(cubic);
+ double width = dRect.right - dRect.left;
+ double height = dRect.bottom - dRect.top;
+ return (width > height ? width : height) / 256;
+}
+
+static void test(const Cubic(& cubics)[], const char* name, int firstTest, size_t testCount) {
+ SkTDArray<Quadratic> quads;
+ for (size_t index = firstTest; index < testCount; ++index) {
+ const Cubic& cubic = cubics[index];
+ double precision = calcPrecision(cubic);
+ cubic_to_quadratics(cubic, precision, quads);
+ if (quads.count() != 1) {
+ printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index,
+ quads.count());
+ }
+ }
+}
+
+static void test(const Quadratic(& quadTests)[], const char* name, int firstTest, size_t testCount) {
+ SkTDArray<Quadratic> quads;
+ for (size_t index = firstTest; index < testCount; ++index) {
+ const Quadratic& quad = quadTests[index];
+ Cubic cubic;
+ quad_to_cubic(quad, cubic);
+ double precision = calcPrecision(cubic);
+ cubic_to_quadratics(cubic, precision, quads);
+ if (quads.count() != 1) {
+ printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index,
+ quads.count());
+ }
+ }
+}
+
+static void testC(const Cubic(& cubics)[], const char* name, int firstTest, size_t testCount) {
+ SkTDArray<Quadratic> quads;
+ // test if computed line end points are valid
+ for (size_t index = firstTest; index < testCount; ++index) {
+ const Cubic& cubic = cubics[index];
+ double precision = calcPrecision(cubic);
+ int order = cubic_to_quadratics(cubic, precision, quads);
+ assert(order != 4);
+ if (order < 3) {
+ continue;
+ }
+ if (!AlmostEqualUlps(cubic[0].x, quads[0][0].x)
+ || !AlmostEqualUlps(cubic[0].y, quads[0][0].y)) {
+ printf("[%d] unmatched start\n", (int) index);
+ }
+ int last = quads.count() - 1;
+ if (!AlmostEqualUlps(cubic[3].x, quads[last][2].x)
+ || !AlmostEqualUlps(cubic[3].y, quads[last][2].y)) {
+ printf("[%d] unmatched end\n", (int) index);
+ }
+ }
+}
+
+static void testC(const Cubic(& cubics)[][2], const char* name, int firstTest, size_t testCount) {
+ SkTDArray<Quadratic> quads;
+ for (size_t index = firstTest; index < testCount; ++index) {
+ for (int idx2 = 0; idx2 < 2; ++idx2) {
+ const Cubic& cubic = cubics[index][idx2];
+ double precision = calcPrecision(cubic);
+ int order = cubic_to_quadratics(cubic, precision, quads);
+ assert(order != 4);
+ if (order < 3) {
+ continue;
+ }
+ if (!AlmostEqualUlps(cubic[0].x, quads[0][0].x)
+ || !AlmostEqualUlps(cubic[0].y, quads[0][0].y)) {
+ printf("[%d][%d] unmatched start\n", (int) index, idx2);
+ }
+ int last = quads.count() - 1;
+ if (!AlmostEqualUlps(cubic[3].x, quads[last][2].x)
+ || !AlmostEqualUlps(cubic[3].y, quads[last][2].y)) {
+ printf("[%d][%d] unmatched end\n", (int) index, idx2);
+ }
+ }
+ }
+}
+
void CubicToQuadratics_Test() {
- size_t index;
enum {
RunAll,
RunPointDegenerates,
@@ -18,6 +100,7 @@ void CubicToQuadratics_Test() {
RunQuadraticLines,
RunQuadraticModLines,
RunComputedLines,
+ RunComputedTests,
RunNone
} run = RunAll;
int firstTestIndex = 0;
@@ -35,85 +118,69 @@ void CubicToQuadratics_Test() {
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;
- SkTDArray<Quadratic> quads;
- for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
- const Cubic& cubic = pointDegenerates[index];
- cubic_to_quadratics(cubic, quads);
- if (quads.count() != 1) {
- printf("[%d] pointDegenerates count=%d\n", (int) index, quads.count());
- }
- }
- for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
- const Cubic& cubic = notPointDegenerates[index];
- cubic_to_quadratics(cubic, quads);
- if (quads.count() != 1) {
- printf("[%d] notPointDegenerates count=%d\n", (int) index, quads.count());
- }
- }
- for (index = firstLinesTest; index < lines_count; ++index) {
- const Cubic& cubic = lines[index];
- cubic_to_quadratics(cubic, quads);
- if (quads.count() != 1) {
- printf("[%d] lines count=%d\n", (int) index, quads.count());
- }
- }
- for (index = firstNotLinesTest; index < notLines_count; ++index) {
- const Cubic& cubic = notLines[index];
- cubic_to_quadratics(cubic, quads);
- if (quads.count() != 1) {
- printf("[%d] notLines order=%d\n", (int) index, quads.count());
- }
- }
- for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
- const Cubic& cubic = modEpsilonLines[index];
- cubic_to_quadratics(cubic, quads);
- if (quads.count() != 1) {
- printf("[%d] line mod by epsilon order=%d\n", (int) index, quads.count());
- }
- }
- for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
- const Cubic& cubic = lessEpsilonLines[index];
- cubic_to_quadratics(cubic, quads);
- if (quads.count() != 1) {
- printf("[%d] line less by epsilon/2 order=%d\n", (int) index, quads.count());
- }
- }
- for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
- const Cubic& cubic = negEpsilonLines[index];
- cubic_to_quadratics(cubic, quads);
- if (quads.count() != 1) {
- printf("[%d] line neg by epsilon/2 order=%d\n", (int) index, quads.count());
- }
- }
- for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
- const Quadratic& quad = quadraticLines[index];
- Cubic cubic;
- quad_to_cubic(quad, cubic);
- cubic_to_quadratics(cubic, quads);
- if (quads.count() != 1) {
- printf("[%d] line quad order=%d\n", (int) index, quads.count());
- }
+ int firstComputedCubicsTest = run == RunAll ? 0 : run == RunComputedTests ? firstTestIndex : INT_MAX;
+
+ test(pointDegenerates, "pointDegenerates", firstPointDegeneratesTest, pointDegenerates_count);
+ test(notPointDegenerates, "notPointDegenerates", firstNotPointDegeneratesTest, notPointDegenerates_count);
+ test(lines, "lines", firstLinesTest, lines_count);
+ test(notLines, "notLines", firstNotLinesTest, notLines_count);
+ test(modEpsilonLines, "modEpsilonLines", firstModEpsilonTest, modEpsilonLines_count);
+ test(lessEpsilonLines, "lessEpsilonLines", firstLessEpsilonTest, lessEpsilonLines_count);
+ test(negEpsilonLines, "negEpsilonLines", firstNegEpsilonTest, negEpsilonLines_count);
+ test(quadraticLines, "quadraticLines", firstQuadraticLineTest, quadraticLines_count);
+ test(quadraticModEpsilonLines, "quadraticModEpsilonLines", firstQuadraticModLineTest,
+ quadraticModEpsilonLines_count);
+ testC(lines, "computed lines", firstComputedLinesTest, lines_count);
+ testC(tests, "computed tests", firstComputedCubicsTest, tests_count);
+ printf("%s end\n", __FUNCTION__);
+}
+
+static Cubic locals[] = {
+ {{
+ 60.776536520932126,
+ 71.249307306133829
+ }, {
+ 87.107894191103014,
+ 22.377669868235323
+ }, {
+ 1.4974754310666936,
+ 68.069569937917208
+ }, {
+ 45.261946574441133,
+ 17.536076632112298
+ }}
+};
+
+static size_t localsCount = sizeof(locals) / sizeof(locals[0]);
+
+void CubicsToQuadratics_RandTest() {
+ for (size_t x = 0; x < localsCount; ++x) {
+ const Cubic& cubic = locals[x];
+ SkTDArray<Quadratic> quads;
+ double precision = calcPrecision(cubic);
+ cubic_to_quadratics(cubic, precision, quads);
}
- for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
- const Quadratic& quad = quadraticModEpsilonLines[index];
+ srand(0);
+ const int arrayMax = 1000;
+ const int tests = 1000000;
+ int quadDist[arrayMax];
+ bzero(quadDist, sizeof(quadDist));
+ for (int x = 0; x < tests; ++x) {
Cubic cubic;
- quad_to_cubic(quad, cubic);
- cubic_to_quadratics(cubic, quads);
- if (quads.count() != 1) {
- printf("[%d] line mod quad order=%d\n", (int) index, quads.count());
+ for (int i = 0; i < 4; ++i) {
+ cubic[i].x = (double) rand() / RAND_MAX * 100;
+ cubic[i].y = (double) rand() / RAND_MAX * 100;
}
+ SkTDArray<Quadratic> quads;
+ double precision = calcPrecision(cubic);
+ cubic_to_quadratics(cubic, precision, quads);
+ assert(quads.count() < arrayMax);
+ quadDist[quads.count()]++;
}
-
- // test if computed line end points are valid
- for (index = firstComputedLinesTest; index < lines_count; ++index) {
- const Cubic& cubic = lines[index];
- cubic_to_quadratics(cubic, quads);
- if (cubic[0].x != quads[0][0].x && cubic[0].y != quads[0][0].y) {
- printf("[%d] unmatched start\n", (int) index);
- }
- int last = quads.count() - 1;
- if (cubic[3].x != quads[last][2].x && cubic[3].y != quads[last][2].y) {
- printf("[%d] unmatched end\n", (int) index);
+ for (int x = 0; x < arrayMax; ++x) {
+ if (!quadDist[x]) {
+ continue;
}
+ printf("%d 1.9%g%%\n", x, (double) quadDist[x] / tests * 100);
}
}
diff --git a/experimental/Intersection/CubicUtilities.h b/experimental/Intersection/CubicUtilities.h
index 2e345ea3ff..890ff00732 100644
--- a/experimental/Intersection/CubicUtilities.h
+++ b/experimental/Intersection/CubicUtilities.h
@@ -11,7 +11,8 @@
#include "SkTDArray.h"
double cube_root(double x);
-int cubic_to_quadratics(const Cubic& cubic, SkTDArray<Quadratic>& quadratics);
+int cubic_to_quadratics(const Cubic& cubic, double precision,
+ SkTDArray<Quadratic>& quadratics);
void coefficients(const double* cubic, double& A, double& B, double& C, double& D);
int cubicRoots(double A, double B, double C, double D, double t[3]);
double derivativeAtT(const double* cubic, double t);
diff --git a/experimental/Intersection/Intersection_Tests.cpp b/experimental/Intersection/Intersection_Tests.cpp
index 67758f6216..6bad957f31 100644
--- a/experimental/Intersection/Intersection_Tests.cpp
+++ b/experimental/Intersection/Intersection_Tests.cpp
@@ -15,6 +15,7 @@ void cubecode_test(int test);
void Intersection_Tests() {
int testsRun = 0;
+ CubicsToQuadratics_RandTest();
CubicToQuadratics_Test();
SimplifyNew_Test();
Simplify4x4RectsThreaded_Test(testsRun);
diff --git a/experimental/Intersection/Intersection_Tests.h b/experimental/Intersection/Intersection_Tests.h
index 682d7cdb84..7da4e097f5 100644
--- a/experimental/Intersection/Intersection_Tests.h
+++ b/experimental/Intersection/Intersection_Tests.h
@@ -16,6 +16,7 @@ void CubicCoincidence_Test();
void CubicIntersection_Test();
void CubicParameterization_Test();
void CubicReduceOrder_Test();
+void CubicsToQuadratics_RandTest();
void CubicToQuadratics_Test();
void Inline_Tests();
void Intersection_Tests();
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-19 09:42:32 +0000