blob: e83a52f650f5aae92cc9215a7f58a8ca083186cc [file] [log] [blame]
caryclark@google.comb45a1b42012-05-18 20:50:33 +00001/*
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
caryclark@google.comc899ad92012-08-23 15:24:42 +000055struct 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
caryclark@google.com3350c3c2012-08-24 15:24:36 +000068static 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
caryclark@google.com32546db2012-08-31 20:55:07 +000075static 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
caryclark@google.comc899ad92012-08-23 15:24:42 +000081static const segment* segmentTests[] = {
caryclark@google.com32546db2012-08-31 20:55:07 +000082 segmentTest3,
caryclark@google.com3350c3c2012-08-24 15:24:36 +000083 segmentTest2,
84 segmentTest1,
caryclark@google.comc899ad92012-08-23 15:24:42 +000085};
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;
caryclark@google.com6aea33f2012-10-09 14:11:58 +000096 SkTDArray<SimplifyAngleTest::Span> dummy;
97 lesser.set(segPtr[index].pts, segPtr[index].verb, NULL, index, next, dummy);
caryclark@google.comc899ad92012-08-23 15:24:42 +000098 if (segPtr[next].verb == SkPath::kMove_Verb) {
99 break;
100 }
caryclark@google.com6aea33f2012-10-09 14:11:58 +0000101 greater.set(segPtr[next].pts, segPtr[next].verb, NULL, index, next, dummy);
caryclark@google.comc899ad92012-08-23 15:24:42 +0000102 bool result = lesser < greater;
103 SkASSERT(result);
104 index = next;
105 } while (true);
106 }
107}
108
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000109static 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();
caryclark@google.com6aea33f2012-10-09 14:11:58 +0000117 SkTDArray<SimplifyAngleTest::Span> dummy;
118 angle->set(lines[x], SkPath::kLine_Verb, 0, x, x + 1, dummy);
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000119 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();
caryclark@google.com6aea33f2012-10-09 14:11:58 +0000165 SkTDArray<SimplifyAngleTest::Span> dummy;
166 angle->set(quads[x], SkPath::kQuad_Verb, 0, x, x + 1, dummy);
caryclark@google.com3350c3c2012-08-24 15:24:36 +0000167 }
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000168 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];
caryclark@google.comf25edfe2012-06-01 18:20:10 +0000176 if ((int) x != angle->start()) {
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000177 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();
caryclark@google.com6aea33f2012-10-09 14:11:58 +0000188 SkTDArray<SimplifyAngleTest::Span> dummy;
189 angle->set(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1, dummy);
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000190 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];
caryclark@google.comf25edfe2012-06-01 18:20:10 +0000195 if ((int) x != angle->start()) {
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000196 SkDebugf("%s [%d] [%d]\n", __FUNCTION__, x, angle->start());
197 SkASSERT(0);
198 }
199 }
200}
201
caryclark@google.com6aea33f2012-10-09 14:11:58 +0000202struct 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
caryclark@google.com4aaaaea2013-02-28 16:12:39 +0000233static 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
caryclark@google.com6aea33f2012-10-09 14:11:58 +0000241static const segmentWithT* oneOffTests[] = {
242 oneOffTest1,
243 oneOffTest2,
244 oneOffTest3,
caryclark@google.com4aaaaea2013-02-28 16:12:39 +0000245 oneOffTest4,
caryclark@google.com6aea33f2012-10-09 14:11:58 +0000246};
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
caryclark@google.com4aaaaea2013-02-28 16:12:39 +0000271#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
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000314static void (*tests[])(bool) = {
caryclark@google.com6aea33f2012-10-09 14:11:58 +0000315 oneOffTest,
caryclark@google.comc899ad92012-08-23 15:24:42 +0000316 testSegments,
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000317 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) {
caryclark@google.comc899ad92012-08-23 15:24:42 +0000339 (*tests[index])(false); // set to true to exercise setFlat
caryclark@google.comb45a1b42012-05-18 20:50:33 +0000340 firstTestComplete = true;
341 }
caryclark@google.coma3f05fa2012-06-01 17:44:28 +0000342}