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