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