1
2 /*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8 #include "Test.h"
9 #include "../../src/core/SkConcaveToTriangles.h"
10 #include "SkGeometry.h"
11
GetIndexFromPoint(const SkPoint & pt,int numPts,const SkPoint * pts)12 static int GetIndexFromPoint(const SkPoint &pt,
13 int numPts, const SkPoint *pts) {
14 for (int i = 0; i < numPts; ++i)
15 if (pt.fX == pts[i].fX && pt.fY == pts[i].fY)
16 return i;
17 return -1;
18 }
19
20
21 bool gPrintTriangles = false; // Can we set this on the command line?
22
PrintTriangles(const SkTDArray<SkPoint> & triangles,int numPts,const SkPoint * pts,skiatest::Reporter * reporter)23 static void PrintTriangles(const SkTDArray<SkPoint> &triangles,
24 int numPts, const SkPoint *pts,
25 skiatest::Reporter* reporter) {
26 if (gPrintTriangles) {
27 SkPoint *p = triangles.begin();
28 int n = triangles.count();
29 REPORTER_ASSERT(reporter, n % 3 == 0);
30 n /= 3;
31 printf("%d Triangles:\n{\n", n);
32 for (; n-- != 0; p += 3)
33 printf(" { {%.7g, %.7g}, {%.7g, %.7g}, {%.7g, %.7g} }, "
34 "// { %2d, %2d, %2d }\n",
35 p[0].fX, p[0].fY,
36 p[1].fX, p[1].fY,
37 p[2].fX, p[2].fY,
38 GetIndexFromPoint(p[0], numPts, pts),
39 GetIndexFromPoint(p[1], numPts, pts),
40 GetIndexFromPoint(p[2], numPts, pts));
41 printf("}\n");
42 }
43 }
44
45
CompareTriangleList(int numTriangles,const float refTriangles[][3][2],const SkTDArray<SkPoint> & triangles)46 static bool CompareTriangleList(int numTriangles,
47 const float refTriangles[][3][2],
48 const SkTDArray<SkPoint> &triangles) {
49 if (triangles.count() != numTriangles * 3) {
50 printf("Expected %d triangles, not %d\n",
51 numTriangles, triangles.count() / 3);
52 return false;
53 }
54 int numErrors = 0;
55 for (int i = 0; i < numTriangles; ++i) {
56 const float *r = &refTriangles[i][0][0];
57 const SkScalar *t = &triangles[i * 3].fX;
58 bool equalTriangle = true;
59 for (int j = 6; j-- != 0; r++, t++)
60 if (SkFloatToScalar(*r) != *t)
61 equalTriangle = false;
62 if (equalTriangle == false) {
63 ++numErrors;
64 printf("Triangle %d differs\n", i);
65 }
66 }
67 if (numErrors > 0)
68 printf("%d triangles differ\n", numErrors);
69 return numErrors == 0;
70 }
71
72
73 #ifndef LEFT_HANDED_POLYGONS
74 static const SkPoint star[] = {
75 // Outer contour is clockwise if Y is down, counterclockwise if Y is up.
76 { SkFloatToScalar(110), SkFloatToScalar( 20) },
77 { SkFloatToScalar(100), SkFloatToScalar( 50) },
78 { SkFloatToScalar(130), SkFloatToScalar( 80) },
79 { SkFloatToScalar( 90), SkFloatToScalar( 80) },
80 { SkFloatToScalar( 70), SkFloatToScalar(120) },
81 { SkFloatToScalar( 50), SkFloatToScalar( 80) },
82 { SkFloatToScalar( 10), SkFloatToScalar( 80) },
83 { SkFloatToScalar( 40), SkFloatToScalar( 50) },
84 { SkFloatToScalar( 30), SkFloatToScalar( 20) },
85 { SkFloatToScalar( 70), SkFloatToScalar( 40) },
86 // Inner contour is counterclockwise if Y is down, clockwise if Y is up.
87 { SkFloatToScalar(110), SkFloatToScalar( 20) },
88 { SkFloatToScalar( 70), SkFloatToScalar( 50) },
89 { SkFloatToScalar( 60), SkFloatToScalar( 60) },
90 { SkFloatToScalar( 60), SkFloatToScalar( 70) },
91 { SkFloatToScalar( 80), SkFloatToScalar( 70) },
92 { SkFloatToScalar( 80), SkFloatToScalar( 60) },
93 { SkFloatToScalar( 70), SkFloatToScalar( 50) }
94 };
95 static const SkPoint plus[] = {
96 { SkFloatToScalar( 70), SkFloatToScalar( 10) },
97 { SkFloatToScalar( 70), SkFloatToScalar( 50) },
98 { SkFloatToScalar(110), SkFloatToScalar( 50) },
99 { SkFloatToScalar(110), SkFloatToScalar( 70) },
100 { SkFloatToScalar( 70), SkFloatToScalar( 70) },
101 { SkFloatToScalar( 70), SkFloatToScalar(110) },
102 { SkFloatToScalar( 50), SkFloatToScalar(110) },
103 { SkFloatToScalar( 50), SkFloatToScalar( 70) },
104 { SkFloatToScalar( 10), SkFloatToScalar( 70) },
105 { SkFloatToScalar( 10), SkFloatToScalar( 50) },
106 { SkFloatToScalar( 50), SkFloatToScalar( 50) },
107 { SkFloatToScalar( 50), SkFloatToScalar( 10) }
108 };
109 static const SkPoint zipper[] = {
110 { SkFloatToScalar( 10), SkFloatToScalar( 60) },
111 { SkFloatToScalar( 10), SkFloatToScalar( 10) },
112 { SkFloatToScalar( 20), SkFloatToScalar( 10) },
113 { SkFloatToScalar( 20), SkFloatToScalar( 50) },
114 { SkFloatToScalar( 30), SkFloatToScalar( 50) },
115 { SkFloatToScalar( 30), SkFloatToScalar( 10) },
116 { SkFloatToScalar( 60), SkFloatToScalar( 10) },
117 { SkFloatToScalar( 60), SkFloatToScalar( 50) },
118 { SkFloatToScalar( 70), SkFloatToScalar( 50) },
119 { SkFloatToScalar( 70), SkFloatToScalar( 10) },
120 { SkFloatToScalar(100), SkFloatToScalar( 10) },
121 { SkFloatToScalar(100), SkFloatToScalar( 50) },
122 { SkFloatToScalar(110), SkFloatToScalar( 50) },
123 { SkFloatToScalar(110), SkFloatToScalar( 10) },
124 { SkFloatToScalar(140), SkFloatToScalar( 10) },
125 { SkFloatToScalar(140), SkFloatToScalar( 60) },
126 { SkFloatToScalar(130), SkFloatToScalar( 60) },
127 { SkFloatToScalar(130), SkFloatToScalar( 20) },
128 { SkFloatToScalar(120), SkFloatToScalar( 20) },
129 { SkFloatToScalar(120), SkFloatToScalar( 60) },
130 { SkFloatToScalar( 90), SkFloatToScalar( 60) },
131 { SkFloatToScalar( 90), SkFloatToScalar( 20) },
132 { SkFloatToScalar( 80), SkFloatToScalar( 20) },
133 { SkFloatToScalar( 80), SkFloatToScalar( 60) },
134 { SkFloatToScalar( 50), SkFloatToScalar( 60) },
135 { SkFloatToScalar( 50), SkFloatToScalar( 20) },
136 { SkFloatToScalar( 40), SkFloatToScalar( 20) },
137 { SkFloatToScalar( 40), SkFloatToScalar( 60) }
138 };
139 #else // LEFT_HANDED_POLYGONS
140 static const SkPoint star[] = {
141 // Outer contour is counterclockwise if Y is down, clockwise if Y is up.
142 { SkFloatToScalar(110), SkFloatToScalar( 20) },
143 { SkFloatToScalar( 70), SkFloatToScalar( 40) },
144 { SkFloatToScalar( 30), SkFloatToScalar( 20) },
145 { SkFloatToScalar( 40), SkFloatToScalar( 50) },
146 { SkFloatToScalar( 10), SkFloatToScalar( 80) },
147 { SkFloatToScalar( 50), SkFloatToScalar( 80) },
148 { SkFloatToScalar( 70), SkFloatToScalar(120) },
149 { SkFloatToScalar( 90), SkFloatToScalar( 80) },
150 { SkFloatToScalar(130), SkFloatToScalar( 80) },
151 { SkFloatToScalar(100), SkFloatToScalar( 50) },
152 // Inner contour is clockwise if Y is down, counterclockwise if Y is up.
153 { SkFloatToScalar(110), SkFloatToScalar( 20) },
154 { SkFloatToScalar( 70), SkFloatToScalar( 50) },
155 { SkFloatToScalar( 80), SkFloatToScalar( 60) },
156 { SkFloatToScalar( 80), SkFloatToScalar( 70) },
157 { SkFloatToScalar( 60), SkFloatToScalar( 70) },
158 { SkFloatToScalar( 60), SkFloatToScalar( 60) },
159 { SkFloatToScalar( 70), SkFloatToScalar( 50) }
160 };
161 #endif // LEFT_HANDED_POLYGONS
162 #define kNumStarVertices 10
163 #define kNumStarHoleVertices (sizeof(star) / sizeof(star[0]))
164
165
166 // Star test
TestStarTriangulation(skiatest::Reporter * reporter)167 static void TestStarTriangulation(skiatest::Reporter* reporter) {
168 static const float refTriangles[][3][2] = {
169 { { 30, 20}, { 70, 40}, { 40, 50} }, // { 8, 9, 7 }
170 { {100, 50}, { 10, 80}, { 40, 50} }, // { 1, 6, 7 }
171 { {100, 50}, { 40, 50}, { 70, 40} }, // { 1, 7, 9 }
172 { {100, 50}, { 70, 40}, {110, 20} }, // { 1, 9, 0 }
173 { { 90, 80}, { 70, 120}, { 50, 80} }, // { 3, 4, 5 }
174 { {130, 80}, { 90, 80}, { 50, 80} }, // { 2, 3, 5 } degen
175 { {130, 80}, { 50, 80}, { 10, 80} }, // { 2, 5, 6 } degen
176 { {130, 80}, { 10, 80}, {100, 50} } // { 2, 6, 1 }
177 };
178 const size_t numRefTriangles = sizeof(refTriangles)
179 / (6 * sizeof(refTriangles[0][0][0]));
180 SkTDArray<SkPoint> triangles;
181 bool success = SkConcaveToTriangles(kNumStarVertices, star, &triangles);
182 PrintTriangles(triangles, kNumStarVertices, star, reporter);
183 success = CompareTriangleList(numRefTriangles, refTriangles, triangles)
184 && success;
185 reporter->report("Triangulate Star", success ? reporter->kPassed
186 : reporter->kFailed);
187 }
188
189
190 // Star with hole test
TestStarHoleTriangulation(skiatest::Reporter * reporter)191 static void TestStarHoleTriangulation(skiatest::Reporter* reporter) {
192 static const float refTriangles[][3][2] = {
193 { {100, 50}, { 80, 60}, { 70, 50} }, // { 1, 15, 16 }
194 { {100, 50}, { 70, 50}, {110, 20} }, // { 1, 16, 0 }
195 { { 30, 20}, { 70, 40}, { 40, 50} }, // { 8, 9, 7 }
196 { { 60, 70}, { 80, 70}, { 10, 80} }, // { 13, 14, 6 }
197 { { 60, 60}, { 60, 70}, { 10, 80} }, // { 12, 13, 6 }
198 { { 70, 50}, { 60, 60}, { 10, 80} }, // { 11, 12, 6 }
199 { { 70, 50}, { 10, 80}, { 40, 50} }, // { 11, 6, 7 }
200 { { 70, 50}, { 40, 50}, { 70, 40} }, // { 11, 7, 9 }
201 { { 70, 50}, { 70, 40}, {110, 20} }, // { 11, 9, 10 }
202 { { 90, 80}, { 70, 120}, { 50, 80} }, // { 3, 4, 5 }
203 { {130, 80}, { 90, 80}, { 50, 80} }, // { 2, 3, 5 } degen
204 { {130, 80}, { 50, 80}, { 10, 80} }, // { 2, 5, 6 } degen
205 { {130, 80}, { 10, 80}, { 80, 70} }, // { 2, 6, 14 }
206 { {130, 80}, { 80, 70}, { 80, 60} }, // { 2, 14, 15 }
207 { {130, 80}, { 80, 60}, {100, 50} } // { 2, 15, 1 }
208 };
209 const size_t numRefTriangles = sizeof(refTriangles)
210 / (6 * sizeof(refTriangles[0][0][0]));
211 SkTDArray<SkPoint> triangles;
212 bool success = SkConcaveToTriangles(kNumStarHoleVertices, star, &triangles);
213 PrintTriangles(triangles, kNumStarHoleVertices, star, reporter);
214 success = CompareTriangleList(numRefTriangles, refTriangles, triangles)
215 && success;
216 reporter->report("Triangulate Star With Hole", success ? reporter->kPassed
217 : reporter->kFailed);
218 }
219
220
221 // Plus test
TestPlusTriangulation(skiatest::Reporter * reporter)222 static void TestPlusTriangulation(skiatest::Reporter* reporter) {
223 static const float refTriangles[][3][2] = {
224 { { 50, 10}, { 70, 10}, { 50, 50} }, // { 11, 0, 10 }
225 { { 70, 50}, {110, 50}, { 10, 70} }, // { 1, 2, 8 }
226 { { 70, 50}, { 10, 70}, { 10, 50} }, // { 1, 8, 9 }
227 { { 70, 50}, { 10, 50}, { 50, 50} }, // { 1, 9, 10 }
228 { { 70, 50}, { 50, 50}, { 70, 10} }, // { 1, 10, 0 }
229 { { 70, 70}, { 50, 110}, { 50, 70} }, // { 4, 6, 7 }
230 { {110, 70}, { 70, 70}, { 50, 70} }, // { 3, 4, 7 }
231 { {110, 70}, { 50, 70}, { 10, 70} }, // { 3, 7, 8 }
232 { {110, 70}, { 10, 70}, {110, 50} }, // { 3, 8, 2 }
233 { { 70, 110}, { 50, 110}, { 70, 70} }, // { 5, 6, 4 }
234 };
235 const size_t numRefTriangles = sizeof(refTriangles)
236 / (6 * sizeof(refTriangles[0][0][0]));
237 SkTDArray<SkPoint> triangles;
238 const size_t numVertices = sizeof(plus) / sizeof(SkPoint);
239 bool success = SkConcaveToTriangles(numVertices, plus, &triangles);
240 PrintTriangles(triangles, numVertices, plus, reporter);
241 success = CompareTriangleList(numRefTriangles, refTriangles, triangles)
242 && success;
243 reporter->report("Triangulate Plus", success ? reporter->kPassed
244 : reporter->kFailed);
245 }
246
247
248 // Zipper test
TestZipperTriangulation(skiatest::Reporter * reporter)249 static void TestZipperTriangulation(skiatest::Reporter* reporter) {
250 static const float refTriangles[][3][2] = {
251 { { 10, 10}, { 20, 10}, { 20, 50} }, // { 1, 2, 3 }
252 { { 20, 50}, { 30, 50}, { 10, 60} }, // { 3, 4, 0 }
253 { { 10, 10}, { 20, 50}, { 10, 60} }, // { 1, 3, 0 }
254 { { 30, 10}, { 60, 10}, { 40, 20} }, // { 5, 6, 26 }
255 { { 30, 10}, { 40, 20}, { 30, 50} }, // { 5, 26, 4 }
256 { { 40, 60}, { 10, 60}, { 30, 50} }, // { 27, 0, 4 }
257 { { 40, 60}, { 30, 50}, { 40, 20} }, // { 27, 4, 26 }
258 { { 60, 50}, { 70, 50}, { 50, 60} }, // { 7, 8, 24 }
259 { { 50, 20}, { 60, 50}, { 50, 60} }, // { 25, 7, 24 }
260 { { 50, 20}, { 40, 20}, { 60, 10} }, // { 25, 26, 6 }
261 { { 60, 50}, { 50, 20}, { 60, 10} }, // { 7, 25, 6 }
262 { { 70, 10}, {100, 10}, { 80, 20} }, // { 9, 10, 22 }
263 { { 70, 10}, { 80, 20}, { 70, 50} }, // { 9, 22, 8 }
264 { { 80, 60}, { 50, 60}, { 70, 50} }, // { 23, 24, 8 }
265 { { 80, 60}, { 70, 50}, { 80, 20} }, // { 23, 8, 22 }
266 { {100, 50}, {110, 50}, { 90, 60} }, // { 11, 12, 20 }
267 { { 90, 20}, {100, 50}, { 90, 60} }, // { 21, 11, 20 }
268 { { 90, 20}, { 80, 20}, {100, 10} }, // { 21, 22, 10 }
269 { {100, 50}, { 90, 20}, {100, 10} }, // { 11, 21, 10 }
270 { {110, 10}, {140, 10}, {120, 20} }, // { 13, 14, 18 }
271 { {110, 10}, {120, 20}, {110, 50} }, // { 13, 18, 12 }
272 { {120, 60}, { 90, 60}, {110, 50} }, // { 19, 20, 12 }
273 { {120, 60}, {110, 50}, {120, 20} }, // { 19, 12, 18 }
274 { {140, 60}, {130, 60}, {130, 20} }, // { 15, 16, 17 }
275 { {130, 20}, {120, 20}, {140, 10} }, // { 17, 18, 14 }
276 { {140, 60}, {130, 20}, {140, 10} }, // { 15, 17, 14 }
277 };
278 const size_t numRefTriangles = sizeof(refTriangles)
279 / (6 * sizeof(refTriangles[0][0][0]));
280 SkTDArray<SkPoint> triangles;
281 const size_t numVertices = sizeof(zipper) / sizeof(SkPoint);
282 bool success = SkConcaveToTriangles(numVertices, zipper, &triangles);
283 PrintTriangles(triangles, numVertices, zipper, reporter);
284 success = CompareTriangleList(numRefTriangles, refTriangles, triangles)
285 && success;
286 reporter->report("Triangulate Zipper", success ? reporter->kPassed
287 : reporter->kFailed);
288 }
289
290
TestTriangulation(skiatest::Reporter * reporter)291 static void TestTriangulation(skiatest::Reporter* reporter) {
292 TestStarTriangulation(reporter);
293 TestStarHoleTriangulation(reporter);
294 TestPlusTriangulation(reporter);
295 TestZipperTriangulation(reporter);
296 }
297
298 #include "TestClassDef.h"
299 DEFINE_TESTCLASS("Triangulation", TriangulationTestClass, TestTriangulation)
300