1#include "CubicIntersection_TestData.h"
2#include "CubicUtilities.h"
3#include "Intersection_Tests.h"
4#include "QuadraticIntersection_TestData.h"
5#include "TestUtilities.h"
6#include "SkGeometry.h"
7
8static void test(const Cubic* cubics, const char* name, int firstTest, size_t testCount) {
9    SkTDArray<Quadratic> quads;
10    for (size_t index = firstTest; index < testCount; ++index) {
11        const Cubic& cubic = cubics[index];
12        double precision = calcPrecision(cubic);
13        (void) cubic_to_quadratics(cubic, precision, quads);
14        if (quads.count() != 1) {
15            printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index,
16                    quads.count());
17        }
18    }
19}
20
21static void test(const Quadratic* quadTests, const char* name, int firstTest, size_t testCount) {
22    SkTDArray<Quadratic> quads;
23    for (size_t index = firstTest; index < testCount; ++index) {
24        const Quadratic& quad = quadTests[index];
25        Cubic cubic;
26        quad_to_cubic(quad, cubic);
27        double precision = calcPrecision(cubic);
28        (void) cubic_to_quadratics(cubic, precision, quads);
29        if (quads.count() != 1) {
30            printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index,
31                    quads.count());
32        }
33    }
34}
35
36static void testC(const Cubic* cubics, const char* name, int firstTest, size_t testCount) {
37    SkTDArray<Quadratic> quads;
38    // test if computed line end points are valid
39    for (size_t index = firstTest; index < testCount; ++index) {
40        const Cubic& cubic = cubics[index];
41        double precision = calcPrecision(cubic);
42        int order = cubic_to_quadratics(cubic, precision, quads);
43        SkASSERT(order != 4);
44        if (order < 3) {
45            continue;
46        }
47        if (!AlmostEqualUlps(cubic[0].x, quads[0][0].x)
48                || !AlmostEqualUlps(cubic[0].y, quads[0][0].y)) {
49            printf("[%d] unmatched start\n", (int) index);
50        }
51        int last = quads.count() - 1;
52        if (!AlmostEqualUlps(cubic[3].x, quads[last][2].x)
53                || !AlmostEqualUlps(cubic[3].y, quads[last][2].y)) {
54            printf("[%d] unmatched end\n", (int) index);
55        }
56    }
57}
58
59static void testC(const Cubic(* cubics)[2], const char* name, int firstTest, size_t testCount) {
60    SkTDArray<Quadratic> quads;
61    for (size_t index = firstTest; index < testCount; ++index) {
62        for (int idx2 = 0; idx2 < 2; ++idx2) {
63            const Cubic& cubic = cubics[index][idx2];
64            double precision = calcPrecision(cubic);
65            int order = cubic_to_quadratics(cubic, precision, quads);
66        SkASSERT(order != 4);
67        if (order < 3) {
68                continue;
69            }
70            if (!AlmostEqualUlps(cubic[0].x, quads[0][0].x)
71                    || !AlmostEqualUlps(cubic[0].y, quads[0][0].y)) {
72                printf("[%d][%d] unmatched start\n", (int) index, idx2);
73            }
74            int last = quads.count() - 1;
75            if (!AlmostEqualUlps(cubic[3].x, quads[last][2].x)
76                    || !AlmostEqualUlps(cubic[3].y, quads[last][2].y)) {
77                printf("[%d][%d] unmatched end\n", (int) index, idx2);
78            }
79        }
80    }
81}
82
83void CubicToQuadratics_Test() {
84    enum {
85        RunAll,
86        RunPointDegenerates,
87        RunNotPointDegenerates,
88        RunLines,
89        RunNotLines,
90        RunModEpsilonLines,
91        RunLessEpsilonLines,
92        RunNegEpsilonLines,
93        RunQuadraticLines,
94        RunQuadraticModLines,
95        RunComputedLines,
96        RunComputedTests,
97        RunNone
98    } run = RunAll;
99    int firstTestIndex = 0;
100#if 0
101    run = RunComputedLines;
102    firstTestIndex = 18;
103#endif
104    int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates ? firstTestIndex : SK_MaxS32;
105    int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates ? firstTestIndex : SK_MaxS32;
106    int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : SK_MaxS32;
107    int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : SK_MaxS32;
108    int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines ? firstTestIndex : SK_MaxS32;
109    int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines ? firstTestIndex : SK_MaxS32;
110    int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines ? firstTestIndex : SK_MaxS32;
111    int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines ? firstTestIndex : SK_MaxS32;
112    int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines ? firstTestIndex : SK_MaxS32;
113    int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines ? firstTestIndex : SK_MaxS32;
114    int firstComputedCubicsTest = run == RunAll ? 0 : run == RunComputedTests ? firstTestIndex : SK_MaxS32;
115
116    test(pointDegenerates, "pointDegenerates", firstPointDegeneratesTest, pointDegenerates_count);
117    test(notPointDegenerates, "notPointDegenerates", firstNotPointDegeneratesTest, notPointDegenerates_count);
118    test(lines, "lines", firstLinesTest, lines_count);
119    test(notLines, "notLines", firstNotLinesTest, notLines_count);
120    test(modEpsilonLines, "modEpsilonLines", firstModEpsilonTest, modEpsilonLines_count);
121    test(lessEpsilonLines, "lessEpsilonLines", firstLessEpsilonTest, lessEpsilonLines_count);
122    test(negEpsilonLines, "negEpsilonLines", firstNegEpsilonTest, negEpsilonLines_count);
123    test(quadraticLines, "quadraticLines", firstQuadraticLineTest, quadraticLines_count);
124    test(quadraticModEpsilonLines, "quadraticModEpsilonLines", firstQuadraticModLineTest,
125            quadraticModEpsilonLines_count);
126    testC(lines, "computed lines", firstComputedLinesTest, lines_count);
127    testC(tests, "computed tests", firstComputedCubicsTest, tests_count);
128    printf("%s end\n", __FUNCTION__);
129}
130
131static Cubic locals[] = {
132{{0, 1}, {1.9274705288631189e-19, 1.0000000000000002}, {0.0017190297609673323, 0.99828097023903239},
133 {0.0053709083094631276, 0.99505672974365911}},
134
135 {{14.5975863, 41.632436}, {16.3518929, 26.2639684}, {18.5165519, 7.68775139}, {8.03767257, 89.1628526}},
136 {{69.7292014, 38.6877352}, {24.7648688, 23.1501713}, {84.9283191, 90.2588441}, {80.392774, 61.3533852}},
137 {{
138    60.776536520932126,
139    71.249307306133829
140  }, {
141    87.107894191103014,
142    22.377669868235323
143  }, {
144    1.4974754310666936,
145    68.069569937917208
146  }, {
147    45.261946574441133,
148    17.536076632112298
149  }},
150};
151
152static size_t localsCount = sizeof(locals) / sizeof(locals[0]);
153
154#define DEBUG_CRASH 0
155#define TEST_AVERAGE_END_POINTS 0 // must take const off to test
156extern const bool AVERAGE_END_POINTS;
157
158static void oneOff(size_t x) {
159    const Cubic& cubic = locals[x];
160    const SkPoint skcubic[4] = {{(float) cubic[0].x, (float) cubic[0].y},
161            {(float) cubic[1].x, (float) cubic[1].y}, {(float) cubic[2].x, (float) cubic[2].y},
162            {(float) cubic[3].x, (float) cubic[3].y}};
163    SkScalar skinflect[2];
164    int skin = SkFindCubicInflections(skcubic, skinflect);
165    SkDebugf("%s %d %1.9g\n", __FUNCTION__, skin, skinflect[0]);
166    SkTDArray<Quadratic> quads;
167    double precision = calcPrecision(cubic);
168    (void) cubic_to_quadratics(cubic, precision, quads);
169    SkDebugf("%s quads=%d\n", __FUNCTION__, quads.count());
170}
171
172void CubicsToQuadratics_OneOffTests() {
173    for (size_t x = 0; x < localsCount; ++x) {
174        oneOff(x);
175    }
176}
177
178void CubicsToQuadratics_OneOffTest() {
179    oneOff(0);
180}
181
182void CubicsToQuadratics_RandTest() {
183    srand(0);
184    const int arrayMax = 8;
185    const int sampleMax = 10;
186    const int tests = 1000000; // 10000000;
187    int quadDist[arrayMax];
188    bzero(quadDist, sizeof(quadDist));
189    Cubic samples[arrayMax][sampleMax];
190    int sampleCount[arrayMax];
191    bzero(sampleCount, sizeof(sampleCount));
192    for (int x = 0; x < tests; ++x) {
193        Cubic cubic;
194        for (int i = 0; i < 4; ++i) {
195            cubic[i].x = (double) rand() / RAND_MAX * 100;
196            cubic[i].y = (double) rand() / RAND_MAX * 100;
197        }
198    #if DEBUG_CRASH
199        char str[1024];
200        sprintf(str, "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n",
201                cubic[0].x, cubic[0].y,  cubic[1].x, cubic[1].y, cubic[2].x, cubic[2].y,
202                cubic[3].x, cubic[3].y);
203    #endif
204        SkTDArray<Quadratic> quads;
205        double precision = calcPrecision(cubic);
206        (void) cubic_to_quadratics(cubic, precision, quads);
207        int count = quads.count();
208        SkASSERT(count > 0);
209        SkASSERT(--count < arrayMax);
210        quadDist[count]++;
211        int sCount = sampleCount[count];
212        if (sCount < sampleMax) {
213            memcpy(samples[count][sCount], cubic, sizeof(Cubic));
214            sampleCount[count]++;
215        }
216    }
217    for (int x = 0; x < arrayMax; ++x) {
218        if (!quadDist[x]) {
219            continue;
220        }
221        SkDebugf("%d %1.9g%%\n", x + 1, (double) quadDist[x] / tests * 100);
222    }
223    SkDebugf("\n");
224    for (int x = 0; x < arrayMax; ++x) {
225        for (int y = 0; y < sampleCount[x]; ++y) {
226#if TEST_AVERAGE_END_POINTS
227            for (int w = 0; w < 2; ++w) {
228                AVERAGE_END_POINTS = w;
229#else
230                int w = 0;
231#endif
232                SkDebugf("<div id=\"cubic%dx%d%s\">\n", x + 1, y, w ? "x" : "");
233                const Cubic& cubic = samples[x][y];
234                SkDebugf("{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n",
235                    cubic[0].x, cubic[0].y,  cubic[1].x, cubic[1].y, cubic[2].x, cubic[2].y,
236                    cubic[3].x, cubic[3].y);
237                SkTDArray<Quadratic> quads;
238                double precision = calcPrecision(cubic);
239                (void) cubic_to_quadratics(cubic, precision, quads);
240                for (int z = 0; z < quads.count(); ++z) {
241                    const Quadratic& quad = quads[z];
242                    SkDebugf("{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n",
243                        quad[0].x, quad[0].y,  quad[1].x, quad[1].y, quad[2].x, quad[2].y);
244                }
245                SkDebugf("</div>\n\n");
246#if TEST_AVERAGE_END_POINTS
247            }
248#endif
249        }
250    }
251    SkDebugf("</div>\n\n");
252    SkDebugf("<script type=\"text/javascript\">\n\n");
253    SkDebugf("var testDivs = [\n");
254    for (int x = 0; x < arrayMax; ++x) {
255        for (int y = 0; y < sampleCount[x]; ++y) {
256#if TEST_AVERAGE_END_POINTS
257            for (int w = 0; w < 2; ++w) {
258#else
259            int w = 0;
260#endif
261                SkDebugf("    cubic%dx%d%s,\n", x + 1, y, w ? "x" : "");
262#if TEST_AVERAGE_END_POINTS
263            }
264#endif
265        }
266    }
267    SkDebugf("\n\n\n");
268    SkDebugf("%s end\n", __FUNCTION__);
269}
270