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
12static 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
21bool gPrintTriangles = false;   // Can we set this on the command line?
22
23static 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
46static 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
74static 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};
95static 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};
109static 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
140static 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
167static 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
191static 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
222static 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
249static 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
291static void TestTriangulation(skiatest::Reporter* reporter) {
292    TestStarTriangulation(reporter);
293    TestStarHoleTriangulation(reporter);
294    TestPlusTriangulation(reporter);
295    TestZipperTriangulation(reporter);
296}
297
298#include "TestClassDef.h"
299DEFINE_TESTCLASS("Triangulation", TriangulationTestClass, TestTriangulation)
300