1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "Simplify.h"
9
10namespace SimplifyAngleTest {
11
12#include "Simplify.cpp"
13
14} // end of SimplifyAngleTest namespace
15
16#include "Intersection_Tests.h"
17
18static const SkPoint lines[][2] = {
19    { { 10,  10}, { 10,  20} },
20    { { 10,  10}, { 20,  10} },
21    { { 10,  10}, {-20,  10} },
22    { { 10,  10}, { 10, -20} },
23    { { 10,  10}, { 20,  20} },
24    { { 10,  10}, {-20, -20} },
25    { { 10,  10}, {-20,  40} },
26    { { 10,  10}, { 40, -20} }
27};
28
29static const size_t lineCount = sizeof(lines) / sizeof(lines[0]);
30
31static const SkPoint quads[][3] = {
32    {{ 1,  1}, { 2,  2}, { 1,  3}}, // 0
33    {{ 1,  1}, { 3,  3}, { 1,  5}}, // 1
34    {{ 1,  1}, { 4,  4}, { 1,  7}}, // 2
35    {{ 1,  1}, { 5,  5}, { 9,  9}}, // 3
36    {{ 1,  1}, { 4,  4}, { 7,  1}}, // 4
37    {{ 1,  1}, { 3,  3}, { 5,  1}}, // 5
38    {{ 1,  1}, { 2,  2}, { 3,  1}}, // 6
39};
40
41static const size_t quadCount = sizeof(quads) / sizeof(quads[0]);
42
43static const SkPoint cubics[][4] = {
44    {{ 1,  1}, { 2,  2}, { 2,  3}, { 1,  4}},
45    {{ 1,  1}, { 3,  3}, { 3,  5}, { 1,  7}},
46    {{ 1,  1}, { 4,  4}, { 4,  7}, { 1,  10}},
47    {{ 1,  1}, { 5,  5}, { 8,  8}, { 9,  9}},
48    {{ 1,  1}, { 4,  4}, { 7,  4}, { 10, 1}},
49    {{ 1,  1}, { 3,  3}, { 5,  3}, { 7,  1}},
50    {{ 1,  1}, { 2,  2}, { 3,  2}, { 4,  1}},
51};
52
53static const size_t cubicCount = sizeof(cubics) / sizeof(cubics[0]);
54
55struct segment {
56    SkPath::Verb verb;
57    SkPoint pts[4];
58};
59
60static const segment segmentTest1[] = {
61    {SkPath::kLine_Verb, {{2, 1}, {1, 0}        }},
62    {SkPath::kQuad_Verb, {{2, 1}, {1, 0}, {0, 0}}},
63    {SkPath::kQuad_Verb, {{2, 1}, {3, 2}, {2, 3}}},
64    {SkPath::kLine_Verb, {{2, 1}, {3, 2}        }},
65    {SkPath::kMove_Verb                          }
66};
67
68static const segment segmentTest2[] = {
69    {SkPath::kLine_Verb, {{1, 0}, {0, 0}        }},
70    {SkPath::kQuad_Verb, {{1, 0}, {1.89897954f, 0.898979485f}, {2.39387703f, 1.59591794f}}},
71    {SkPath::kLine_Verb, {{1, 0}, {3, 2}        }},
72    {SkPath::kMove_Verb                          }
73};
74
75static const segment segmentTest3[] = {
76    {SkPath::kQuad_Verb, {{0, 0}, {2, 0}, {0, 1}}},
77    {SkPath::kQuad_Verb, {{0, 0}, {1, 0}, {0, 1}}},
78    {SkPath::kMove_Verb                          }
79};
80
81static const segment* segmentTests[] = {
82    segmentTest3,
83    segmentTest2,
84    segmentTest1,
85};
86
87static const size_t segmentTestCount = sizeof(segmentTests) / sizeof(segmentTests[0]);
88
89static void testSegments(bool testFlat) {
90    for (size_t testIndex = 0; testIndex < segmentTestCount; ++testIndex) {
91        const segment* segPtr = segmentTests[testIndex];
92        SimplifyAngleTest::Angle lesser, greater;
93        int index = 0;
94        do {
95            int next = index + 1;
96            SkTDArray<SimplifyAngleTest::Span> dummy;
97            lesser.set(segPtr[index].pts, segPtr[index].verb, NULL, index, next, dummy);
98            if (segPtr[next].verb == SkPath::kMove_Verb) {
99                break;
100            }
101            greater.set(segPtr[next].pts, segPtr[next].verb, NULL, index, next, dummy);
102            bool result = lesser < greater;
103            SkASSERT(result);
104            index = next;
105        } while (true);
106    }
107}
108
109static void testLines(bool testFlat) {
110    // create angles in a circle
111    SkTDArray<SimplifyAngleTest::Angle> angles;
112    SkTDArray<SimplifyAngleTest::Angle* > angleList;
113    SkTDArray<double> arcTans;
114    size_t x;
115    for (x = 0; x < lineCount; ++x) {
116        SimplifyAngleTest::Angle* angle = angles.append();
117        SkTDArray<SimplifyAngleTest::Span> dummy;
118        angle->set(lines[x], SkPath::kLine_Verb, 0, x, x + 1, dummy);
119        double arcTan = atan2(lines[x][0].fX - lines[x][1].fX,
120                lines[x][0].fY - lines[x][1].fY);
121        arcTans.push(arcTan);
122    }
123    for (x = 0; x < lineCount; ++x) {
124        angleList.push(&angles[x]);
125    }
126    QSort<SimplifyAngleTest::Angle>(angleList.begin(), angleList.end() - 1);
127    bool first = true;
128    bool wrap = false;
129    double base, last;
130    for (size_t x = 0; x < lineCount; ++x) {
131        const SimplifyAngleTest::Angle* angle = angleList[x];
132        int span = angle->start();
133//        SkDebugf("%s [%d] %1.9g (%1.9g,%1.9g %1.9g,%1.9g)\n", __FUNCTION__,
134//                span, arcTans[span], lines[span][0].fX, lines[span][0].fY,
135//                lines[span][1].fX, lines[span][1].fY);
136        if (first) {
137            base = last = arcTans[span];
138            first = false;
139            continue;
140        }
141        if (last < arcTans[span]) {
142            last = arcTans[span];
143            continue;
144        }
145        if (!wrap) {
146            if (base < arcTans[span]) {
147                SkDebugf("%s !wrap [%d] %g\n", __FUNCTION__, span, arcTans[span]);
148                SkASSERT(0);
149            }
150            last = arcTans[span];
151            wrap = true;
152            continue;
153        }
154        SkDebugf("%s wrap [%d] %g\n", __FUNCTION__, span, arcTans[span]);
155        SkASSERT(0);
156    }
157}
158
159static void testQuads(bool testFlat) {
160    SkTDArray<SimplifyAngleTest::Angle> angles;
161    SkTDArray<SimplifyAngleTest::Angle* > angleList;
162    size_t x;
163    for (x = 0; x < quadCount; ++x) {
164        SimplifyAngleTest::Angle* angle = angles.append();
165        SkTDArray<SimplifyAngleTest::Span> dummy;
166        angle->set(quads[x], SkPath::kQuad_Verb, 0, x, x + 1, dummy);
167   }
168    for (x = 0; x < quadCount; ++x) {
169        angleList.push(&angles[x]);
170    }
171    QSort<SimplifyAngleTest::Angle>(angleList.begin(), angleList.end() - 1);
172    for (size_t x = 0; x < quadCount; ++x) {
173        *angleList[x] < *angleList[x + 1];
174        SkASSERT(x == quadCount - 1 || *angleList[x] < *angleList[x + 1]);
175        const SimplifyAngleTest::Angle* angle = angleList[x];
176        if ((int) x != angle->start()) {
177            SkDebugf("%s [%d] [%d]\n", __FUNCTION__, x, angle->start());
178            SkASSERT(0);
179        }
180    }
181}
182
183static void testCubics(bool testFlat) {
184    SkTDArray<SimplifyAngleTest::Angle> angles;
185    SkTDArray<SimplifyAngleTest::Angle* > angleList;
186    for (size_t x = 0; x < cubicCount; ++x) {
187        SimplifyAngleTest::Angle* angle = angles.append();
188            SkTDArray<SimplifyAngleTest::Span> dummy;
189        angle->set(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1, dummy);
190        angleList.push(angle);
191    }
192    QSort<SimplifyAngleTest::Angle>(angleList.begin(), angleList.end() - 1);
193    for (size_t x = 0; x < cubicCount; ++x) {
194        const SimplifyAngleTest::Angle* angle = angleList[x];
195        if ((int) x != angle->start()) {
196            SkDebugf("%s [%d] [%d]\n", __FUNCTION__, x, angle->start());
197            SkASSERT(0);
198        }
199    }
200}
201
202struct segmentWithT {
203    SkPath::Verb verb;
204    SkPoint pts[4];
205    double ts[2];
206};
207
208
209static const segmentWithT oneOffTest1[] = {
210    {SkPath::kQuad_Verb, {{391.653534f, 183.286819f}, {391.653534f, 157.724487f}, {405.469604f, 141.372879f}},
211        {0.62346946335026932, 0.62344389027237135}},
212    {SkPath::kQuad_Verb, {{399.365234f, 171.695801f}, {399.365234f, 140.337967f}, {375.976227f, 140.337967f}},
213        {0.31638302676995866, 0.31637992418411398}},
214    {SkPath::kMove_Verb }
215};
216
217static const segmentWithT oneOffTest2[] = {
218    {SkPath::kQuad_Verb, {{399.070374f, 151.722f}, {391.101532f, 163.002533f}, {391.101532f, 182.665863f}},
219        {0.13793711854916513, 0.13790171160614006}},
220    {SkPath::kQuad_Verb, {{391.653534f, 183.286819f}, {391.653534f, 157.724487f}, {405.469604f, 141.372879f}},
221        {0.62344389027237135, 0.62346946335026932}},
222    {SkPath::kMove_Verb }
223};
224
225static const segmentWithT oneOffTest3[] = {
226    {SkPath::kQuad_Verb, {{399.365234f, 171.695801f}, {399.365234f, 140.337967f}, {375.976227f, 140.337967f}},
227        {0.31637992418411398, 0.31638302676995866, }},
228    {SkPath::kQuad_Verb, {{399.070374f, 151.722f}, {391.101532f, 163.002533f}, {391.101532f, 182.665863f}},
229        {0.13790171160614006, 0.13793711854916513}},
230    {SkPath::kMove_Verb }
231};
232
233static const segmentWithT oneOffTest4[] = {
234    {SkPath::kCubic_Verb, {{1,2}, {1,3}, {1,0}, {5,3}}, {0.134792, 0}},
235    {SkPath::kCubic_Verb, {{0,1}, {3,5}, {2,1}, {3,1}}, {0.134792094, 0}},
236    {SkPath::kCubic_Verb, {{0,1}, {3,5}, {2,1}, {3,1}}, {0.134792094, 0.551812363}},
237    {SkPath::kCubic_Verb, {{1,2}, {1,3}, {1,0}, {5,3}}, {0.134792, 0.333333333}},
238    {SkPath::kMove_Verb }
239};
240
241static const segmentWithT* oneOffTests[] = {
242    oneOffTest1,
243    oneOffTest2,
244    oneOffTest3,
245    oneOffTest4,
246};
247
248static const size_t oneOffTestCount = sizeof(oneOffTests) / sizeof(oneOffTests[0]);
249
250static void oneOffTest(bool testFlat) {
251    for (size_t testIndex = 0; testIndex < oneOffTestCount; ++testIndex) {
252        const segmentWithT* segPtr = oneOffTests[testIndex];
253        SimplifyAngleTest::Angle lesser, greater;
254        int index = 0;
255        do {
256            int next = index + 1;
257            SkTDArray<SimplifyAngleTest::Span> dummy; // FIXME
258            lesser.set(segPtr[index].pts, segPtr[index].verb, 0, index, next, dummy); // FIXME: segPtr[index].ts[0], segPtr[index].ts[1]);
259            if (segPtr[next].verb == SkPath::kMove_Verb) {
260                break;
261            }
262            greater.set(segPtr[next].pts, segPtr[next].verb, 0, index, next, dummy); // FIXME: segPtr[next].ts[0], segPtr[next].ts[1]);
263            bool result = lesser < greater;
264            SkASSERT(result);
265            index = next;
266        } while (true);
267    }
268    SkDebugf("%s finished\n", __FUNCTION__);
269}
270
271#if 0 // seems too complicated for this to be useful (didn't finish writing/debugging this)
272// this (trys to) take a pair of curves, construct segments/spans, and verify that they sort correctly
273static void oneOffTestNew() {
274    const segmentWithT* segPtr = oneOffTest4;
275    SimplifyAngleTest::Segment segOne, segTwo;
276    segOne.init(segPtr[0].pts, segPtr[0].verb, false, false);
277    segTwo.init(segPtr[1].pts, segPtr[1].verb, false, false);
278    int index = 0;
279    do {
280        int next = index + 1;
281        if (segPtr[index].verb == SkPath::kMove_Verb) {
282            break;
283        }
284        SkPoint sub[4];
285        (*SegmentSubDivide[segPtr[index].verb])(segPtr[index].pts, segPtr[index].ts[0],
286                segPtr[index].ts[1], sub);
287        if (memcmp(segPtr[index].pts, segPtr[0].pts, sizeof(SkPoint) * (segPtr[index].verb + 1) == 0) {
288            segOne.addT(&segTwo, sub[0], segPtr[index].ts[0]);
289            segOne.addT(&segTwo, sub[segPtr[index].verb], segPtr[index].ts[1]);
290        } else {
291            segTwo.addT(&segOne, sub[0], segPtr[index].ts[0]);
292            segTwo.addT(&v, sub[segPtr[index].verb], segPtr[index].ts[1]);
293        }
294    } while (true);
295    SimplifyAngleTest::Angle lesser, greater;
296    do {
297        int next = index + 1;
298        if (segPtr[next].verb == SkPath::kMove_Verb) {
299            break;
300        }
301        SkPoint one[4], two[4];
302        bool use1 = memcmp(segPtr[index].pts, segPtr[0].pts, sizeof(SkPoint) * (segPtr[index].verb + 1) == 0;
303        lesser.set(segPtr[index].pts, segPtr[index].verb, use1 ? &segOne : &segTwo, index, next, dummy);
304        use1 = memcmp(segPtr[next].pts, segPtr[0].pts, sizeof(SkPoint) * (segPtr[next].verb + 1) == 0;
305        greater.set(segPtr[next].pts, segPtr[next].verb, use1 ? &segOne : &segTwo, index, next, dummy);
306        bool result = lesser < greater;
307        SkASSERT(result);
308        index = next;
309    } while (true);
310    SkDebugf("%s finished\n", __FUNCTION__);
311}
312#endif
313
314static void (*tests[])(bool) = {
315    oneOffTest,
316    testSegments,
317    testLines,
318    testQuads,
319    testCubics
320};
321
322static const size_t testCount = sizeof(tests) / sizeof(tests[0]);
323
324static void (*firstTest)(bool) = 0;
325static bool skipAll = false;
326
327void SimplifyAngle_Test() {
328    if (skipAll) {
329        return;
330    }
331    size_t index = 0;
332    if (firstTest) {
333        while (index < testCount && tests[index] != firstTest) {
334            ++index;
335        }
336    }
337    bool firstTestComplete = false;
338    for ( ; index < testCount; ++index) {
339        (*tests[index])(false); // set to true to exercise setFlat
340        firstTestComplete = true;
341    }
342}
343