1 /* 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 10 namespace SimplifyAngleTest { 11 12 #include "Simplify.cpp" 13 14 } // end of SimplifyAngleTest namespace 15 16 #include "Intersection_Tests.h" 17 18 static 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 29 static const size_t lineCount = sizeof(lines) / sizeof(lines[0]); 30 31 static 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 41 static const size_t quadCount = sizeof(quads) / sizeof(quads[0]); 42 43 static 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 53 static const size_t cubicCount = sizeof(cubics) / sizeof(cubics[0]); 54 55 struct segment { 56 SkPath::Verb verb; 57 SkPoint pts[4]; 58 }; 59 60 static 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 68 static 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 75 static 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 81 static const segment* segmentTests[] = { 82 segmentTest3, 83 segmentTest2, 84 segmentTest1, 85 }; 86 87 static const size_t segmentTestCount = sizeof(segmentTests) / sizeof(segmentTests[0]); 88 89 static 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; 96 SkTDArray<SimplifyAngleTest::Span> dummy; 97 lesser.set(segPtr[index].pts, segPtr[index].verb, NULL, index, next, dummy); 98 if (segPtr[next].verb == SkPath::kMove_Verb) { 99 break; 100 } 101 greater.set(segPtr[next].pts, segPtr[next].verb, NULL, index, next, dummy); 102 bool result = lesser < greater; 103 SkASSERT(result); 104 index = next; 105 } while (true); 106 } 107 } 108 109 static 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(); 117 SkTDArray<SimplifyAngleTest::Span> dummy; 118 angle->set(lines[x], SkPath::kLine_Verb, 0, x, x + 1, dummy); 119 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 159 static 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(); 165 SkTDArray<SimplifyAngleTest::Span> dummy; 166 angle->set(quads[x], SkPath::kQuad_Verb, 0, x, x + 1, dummy); 167 } 168 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]; 176 if ((int) x != angle->start()) { 177 SkDebugf("%s [%d] [%d]\n", __FUNCTION__, x, angle->start()); 178 SkASSERT(0); 179 } 180 } 181 } 182 183 static 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(); 188 SkTDArray<SimplifyAngleTest::Span> dummy; 189 angle->set(cubics[x], SkPath::kCubic_Verb, 0, x, x + 1, dummy); 190 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]; 195 if ((int) x != angle->start()) { 196 SkDebugf("%s [%d] [%d]\n", __FUNCTION__, x, angle->start()); 197 SkASSERT(0); 198 } 199 } 200 } 201 202 struct segmentWithT { 203 SkPath::Verb verb; 204 SkPoint pts[4]; 205 double ts[2]; 206 }; 207 208 209 static 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 217 static 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 225 static 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 233 static 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 241 static const segmentWithT* oneOffTests[] = { 242 oneOffTest1, 243 oneOffTest2, 244 oneOffTest3, 245 oneOffTest4, 246 }; 247 248 static const size_t oneOffTestCount = sizeof(oneOffTests) / sizeof(oneOffTests[0]); 249 250 static 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 271 #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 273 static 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 314 static void (*tests[])(bool) = { 315 oneOffTest, 316 testSegments, 317 testLines, 318 testQuads, 319 testCubics 320 }; 321 322 static const size_t testCount = sizeof(tests) / sizeof(tests[0]); 323 324 static void (*firstTest)(bool) = 0; 325 static bool skipAll = false; 326 327 void 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) { 339 (*tests[index])(false); // set to true to exercise setFlat 340 firstTestComplete = true; 341 } 342 } 343
