1 /* 2 * Copyright 2013 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 #include "PathOpsTestCommon.h" 8 #include "SkOpSegment.h" 9 #include "SkTArray.h" 10 #include "Test.h" 11 12 static const SkPoint cubics[][4] = { 13 /* 0 */ {{0, 1}, {2, 6}, {4, 2}, {5, 3}}, 14 /* 1 */ {{10, 234}, {10, 229.581726f}, {13.5817204f, 226}, {18, 226}}, 15 /* 2 */ {{132, 11419}, {130.89543151855469f, 11419}, {130, 11418.1044921875f}, {130, 11417}}, 16 /* 3 */ {{130.04275512695312f, 11417.4130859375f}, {130.23307800292969f, 11418.3193359375f}, 17 {131.03709411621094f, 11419}, {132, 11419}}, 18 /* 4 */ {{0,1}, {0,5}, {4,1}, {6,4}}, 19 /* 5 */ {{1,5}, {4,6}, {1,0}, {4,0}}, 20 /* 6 */ {{0,1}, {0,4}, {5,1}, {6,4}}, 21 /* 7 */ {{0,1}, {1,2}, {1,0}, {6,1}}, 22 /* 8 */ {{0,3}, {0,1}, {2,0}, {1,0}}, 23 /* 9 */ {{189,7}, {189,5.3431458473205566f}, {190.3431396484375f,4}, {192,4}}, 24 /* 10 */ {{0,1}, {1,3}, {1,0}, {6,4}}, 25 /* 11 */ {{0,1}, {2,3}, {2,1}, {4,3}}, 26 /* 12 */ {{1,2}, {3,4}, {1,0}, {3,2}}, 27 /* 13 */ {{0,1}, {4,6}, {4,3}, {5,4}}, 28 /* 14 */ {{806,11419}, {806.962890625f,11419}, {807.76690673828125f,11418.3193359375f}, {807.957275390625f,11417.4130859375f}}, 29 /* 15 */ {{808,11417}, {808,11418.1044921875f}, {807.10455322265625f,11419}, {806,11419}}, 30 /* 16 */ {{132,11419}, {130.89543151855469f,11419}, {130,11418.1044921875f}, {130,11417}}, 31 /* 17 */ {{130.04275512695312f,11417.4130859375f}, {130.23312377929687f,11418.3193359375f}, {131.03707885742187f,11419}, {132,11419}}, 32 /* 18 */ {{1006.6951293945312f,291}, {1023.263671875f,291}, {1033.8402099609375f,304.43145751953125f}, {1030.318359375f,321}}, 33 }; 34 35 static const SkPoint quads[][3] = { 36 /* 0 */ {{12.3423996f, 228.342407f}, {10, 230.686295f}, {10, 234}}, 37 /* 1 */ {{304.24319458007812f,591.75677490234375f}, {306,593.51470947265625f}, {306,596}}, 38 /* 2 */ {{0,0}, {3,1}, {0,3}}, 39 /* 3 */ {{0,1}, {3,1}, {0,2}}, 40 }; 41 42 static const SkPoint lines[][2] = { 43 /* 0 */ {{6, 2}, {2, 4}}, 44 /* 1 */ {{306,617}, {306,590}}, 45 /* 2 */ {{306,596}, {306,617}}, 46 /* 3 */ {{6,4}, {0,1}}, 47 /* 4 */ {{6,1}, {0,1}}, 48 /* 5 */ {{1,0}, {0,3}}, 49 /* 6 */ {{246,4}, {189,4}}, 50 /* 7 */ {{192,4}, {243,4}}, 51 /* 8 */ {{4,3}, {0,1}}, 52 /* 9 */ {{3,2}, {1,2}}, 53 /* 10 */ {{6,4}, {3,4}}, 54 /* 11 */ {{979.30487060546875f,561}, {1036.695068359375f,291}}, 55 }; 56 57 struct SortSet { 58 const SkPoint* ptData; 59 int ptCount; 60 double tStart; 61 double tEnd; 62 SkPoint endPt; 63 }; 64 65 /*static const SortSet set1[] = { 66 {cubics[0], 4, 0.66666987081928919, 0.875, {0, 0}}, 67 {lines[0], 2, 0.574070336, 0.388888889, {0, 0}}, 68 {cubics[0], 4, 0.66666987081928919, 0.4050371120499307, {0, 0}}, 69 {lines[0], 2, 0.574070336, 0.9140625, {0, 0}}, 70 }; 71 72 static const SortSet set1a[] = { 73 {cubics[0], 4, 0.666666667, 0.405037112, {4.58007812f,2.83203125f}}, 74 {lines[0], 2, 0.574074074, 0.9140625, {4.44444466f,2.77777767f}}, 75 };*/ 76 77 static const SortSet set2[] = { 78 {cubics[0], 4, 0.666666667, 0.875, {0, 0}}, 79 {lines[0], 2, 0.574074074, 0.388888889, {0, 0}}, 80 {cubics[0], 4, 0.666666667, 0.405037112, {0, 0}}, 81 {lines[0], 2, 0.574074074, 0.9140625, {0, 0}}, 82 }; 83 84 static const SortSet set3[] = { 85 {cubics[1], 4, 0, 1, {0, 0}}, 86 {quads[0], 3, 1, 0, {0, 0}}, 87 }; 88 89 /*static const SortSet set4[] = { 90 {cubics[2], 4, 0.812114222, 1, {0, 0}}, 91 {cubics[3], 4, 0.0684734759, 0, {0, 0}}, 92 };*/ 93 94 static const SortSet set5[] = { 95 {lines[1], 2, 0.777777778, 1, {0, 0}}, 96 {quads[1], 3, 1, 4.34137342e-06, {0, 0}}, 97 {lines[2], 2, 0, 1, {0, 0}}, 98 }; 99 100 static const SortSet set5a[] = { 101 {lines[1], 2, 0.777777778, 1, {306,590}}, 102 {quads[1], 3, 1, 4.34137342e-06, {304.243195f,591.756775f}}, 103 {lines[2], 2, 0, 1, {306,617}}, 104 }; 105 106 static const SortSet set6[] = { 107 {lines[3], 2, 0.407407407, 0.554627832, {0, 0}}, 108 {cubics[4], 4, 0.666666667, 0.548022446, {0, 0}}, 109 {lines[3], 2, 0.407407407, 0, {0, 0}}, 110 {cubics[4], 4, 0.666666667, 1, {0, 0}}, 111 }; 112 113 static const SortSet set6a[] = { 114 {lines[3], 2, 0.407407407, 0.554627832, {2.6722331f,2.33611655f}}, 115 {cubics[4], 4, 0.666666667, 0.548022446, {2.61642241f,2.83718514f}}, 116 {lines[3], 2, 0.407407407, 0, {6,4}}, 117 {cubics[4], 4, 0.666666667, 1, {6,4}}, 118 }; 119 120 static const SortSet set7[] = { 121 {cubics[5], 4, 0.545233342, 0.545454545, {0, 0}}, 122 {cubics[6], 4, 0.484938134, 0.484805744, {0, 0}}, 123 {cubics[5], 4, 0.545233342, 0, {0, 0}}, 124 {cubics[6], 4, 0.484938134, 0.545454545, {0, 0}}, 125 }; 126 127 static const SortSet set8[] = { 128 {cubics[7], 4, 0.5, 0.522986744, {0, 0}}, 129 {lines[4], 2, 0.75, 1, {0, 0}}, 130 {cubics[7], 4, 0.5, 0, {0, 0}}, 131 {lines[4], 2, 0.75, 0.737654321, {0, 0}}, 132 }; 133 134 static const SortSet set8a[] = { 135 {cubics[7], 4, 0.5, 0.522986744, {1.60668361f,0.965592742f}}, 136 {lines[4], 2, 0.75, 1, {0,1}}, 137 {cubics[7], 4, 0.5, 0, {0,1}}, 138 {lines[4], 2, 0.75, 0.737654321, {1.57407403f,1}}, 139 }; 140 141 static const SortSet set9[] = { 142 {cubics[8], 4, 0.4, 1, {0, 0}}, 143 {lines[5], 2, 0.36, 0, {0, 0}}, 144 {cubics[8], 4, 0.4, 0.394675838, {0, 0}}, 145 {lines[5], 2, 0.36, 0.363999782, {0, 0}}, 146 }; 147 148 static const SortSet set10[] = { 149 {lines[6], 2, 0.947368421, 1, {0, 0}}, 150 {cubics[9], 4, 1, 0.500000357, {0, 0}}, 151 {lines[7], 2, 0, 1, {0, 0}}, 152 }; 153 154 static const SortSet set11[] = { 155 {lines[3], 2, 0.75, 1, {0, 0}}, 156 {cubics[10], 4, 0.5, 0.228744269, {0, 0}}, 157 {lines[3], 2, 0.75, 0.627112191, {0, 0}}, 158 {cubics[10], 4, 0.5, 0.6339746, {0, 0}}, 159 }; 160 161 static const SortSet set12[] = { 162 {cubics[12], 4, 0.5, 1, {0, 0}}, 163 {lines[8], 2, 0.5, 1, {0, 0}}, 164 {cubics[11], 4, 0.5, 0, {0, 0}}, 165 {lines[9], 2, 0.5, 1, {0, 0}}, 166 {cubics[12], 4, 0.5, 0, {0, 0}}, 167 {lines[8], 2, 0.5, 0, {0, 0}}, 168 {cubics[11], 4, 0.5, 1, {0, 0}}, 169 {lines[9], 2, 0.5, 0, {0, 0}}, 170 }; 171 172 /*static const SortSet set13[] = { 173 {cubics[13], 4, 0.5, 0.400631046, {0, 0}}, 174 {lines[10], 2, 0.791666667, 0.928, {0, 0}}, 175 {lines[10], 2, 0.791666667, 0.333333333, {0, 0}}, 176 {cubics[13], 4, 0.5, 0.866666667, {0, 0}}, 177 };*/ 178 179 static const SortSet set14[] = { 180 {quads[2], 3, 0.5, 0.310102051, {0, 0}}, 181 {quads[3], 3, 0.5, 0.2, {0, 0}}, 182 {quads[3], 3, 0.5, 0.770156212, {0, 0}}, 183 {quads[2], 3, 0.5, 0.7, {0, 0}}, 184 }; 185 186 /*static const SortSet set15[] = { 187 {cubics[14], 4, 0.93081374, 1, {0, 0}}, 188 {cubics[15], 4, 0.188518131, 0, {0, 0}}, 189 {cubics[14], 4, 0.93081374, 0, {0, 0}}, 190 };*/ 191 192 static const SortSet set16[] = { 193 {cubics[17], 4, 0.0682619216, 0, {130.042755f,11417.4131f}}, 194 {cubics[16], 4, 0.812302088, 1, {130,11417}}, 195 {cubics[17], 4, 0.0682619216, 1, {132,11419}}, 196 }; 197 198 static const SortSet set17[] = { 199 {lines[11], 2, 0.888889581, 1, {0, 0}}, 200 {cubics[18], 4, 0.999996241, 0, {0, 0}}, 201 {lines[11], 2, 0.888889581, 0, {0, 0}}, 202 {cubics[18], 4, 0.999996241, 1, {0, 0}}, 203 }; 204 205 struct SortSetTests { 206 const char* name; 207 const SortSet* set; 208 size_t count; 209 SkPoint startPt; 210 }; 211 212 #define TEST_ENTRY(name) #name, name, SK_ARRAY_COUNT(name) 213 214 static const SortSetTests tests[] = { 215 { TEST_ENTRY(set17), {0, 0}}, 216 { TEST_ENTRY(set16), {130.090179f,11417.5957f} }, 217 // { TEST_ENTRY(set15), {0, 0}}, 218 { TEST_ENTRY(set14), {0, 0}}, 219 // { TEST_ENTRY(set13), {0, 0}}, 220 { TEST_ENTRY(set12), {0, 0}}, 221 { TEST_ENTRY(set11), {0, 0}}, 222 { TEST_ENTRY(set10), {0, 0}}, 223 { TEST_ENTRY(set9), {0, 0}}, 224 { TEST_ENTRY(set6a), {3.55555558f,2.77777767f} }, 225 { TEST_ENTRY(set8a), {1.5f,1} }, 226 { TEST_ENTRY(set8), {0, 0}}, 227 { TEST_ENTRY(set7), {0, 0}}, 228 { TEST_ENTRY(set6a), {3.55555558f,2.77777767f} }, 229 { TEST_ENTRY(set6), {0, 0}}, 230 { TEST_ENTRY(set5a), {306,596} }, 231 { TEST_ENTRY(set5), {0, 0}}, 232 // { TEST_ENTRY(set4), {0, 0}}, 233 { TEST_ENTRY(set3), {0, 0}}, 234 { TEST_ENTRY(set2), {0, 0}}, 235 // { TEST_ENTRY(set1a), {3.70370364f,3.14814806f} }, 236 // { TEST_ENTRY(set1), {0, 0}}, 237 }; 238 239 #undef TEST_ENTRY 240 241 static void setup(const SortSet* set, const size_t idx, 242 SkOpSegment* seg, int* ts, const SkPoint& startPt) { 243 SkPoint start, end; 244 const SkPoint* data = set[idx].ptData; 245 bool useIntersectPt = startPt.fX != 0 || startPt.fY != 0; 246 if (useIntersectPt) { 247 start = startPt; 248 end = set[idx].endPt; 249 } 250 switch(set[idx].ptCount) { 251 case 2: { 252 SkASSERT(ValidPoints(data, 2)); 253 seg->addLine(data, false, false); 254 SkDLine dLine; 255 dLine.set(set[idx].ptData); 256 SkASSERT(ValidLine(dLine)); 257 if (useIntersectPt) { 258 break; 259 } 260 start = dLine.ptAtT(set[idx].tStart).asSkPoint(); 261 end = dLine.ptAtT(set[idx].tEnd).asSkPoint(); 262 } break; 263 case 3: { 264 SkASSERT(ValidPoints(data, 3)); 265 seg->addQuad(data, false, false); 266 SkDQuad dQuad; 267 dQuad.set(set[idx].ptData); 268 SkASSERT(ValidQuad(dQuad)); 269 if (useIntersectPt) { 270 break; 271 } 272 start = dQuad.ptAtT(set[idx].tStart).asSkPoint(); 273 end = dQuad.ptAtT(set[idx].tEnd).asSkPoint(); 274 } break; 275 case 4: { 276 SkASSERT(ValidPoints(data, 4)); 277 seg->addCubic(data, false, false); 278 SkDCubic dCubic; 279 dCubic.set(set[idx].ptData); 280 SkASSERT(ValidCubic(dCubic)); 281 if (useIntersectPt) { 282 break; 283 } 284 start = dCubic.ptAtT(set[idx].tStart).asSkPoint(); 285 end = dCubic.ptAtT(set[idx].tEnd).asSkPoint(); 286 } break; 287 } 288 double tStart = set[idx].tStart; 289 double tEnd = set[idx].tEnd; 290 seg->addT(NULL, start, tStart); 291 seg->addT(NULL, end, tEnd); 292 if (tStart != 0 && tEnd != 0) { 293 seg->addT(NULL, set[idx].ptData[0], 0); 294 } 295 if (tStart != 1 && tEnd != 1) { 296 seg->addT(NULL, set[idx].ptData[set[idx].ptCount - 1], 1); 297 } 298 int tIndex = 0; 299 ts[0] = 0; 300 ts[1] = 1; 301 do { 302 if (seg->t(tIndex) == set[idx].tStart) { 303 ts[0] = tIndex; 304 } 305 if (seg->t(tIndex) == set[idx].tEnd) { 306 ts[1] = tIndex; 307 } 308 if (seg->t(tIndex) >= 1) { 309 break; 310 } 311 } while (++tIndex); 312 } 313 314 static void testOne(skiatest::Reporter* reporter, const SortSetTests& test) { 315 SkTDArray<SkOpAngle> angles; 316 bool unsortable = false; 317 bool unorderable = false; 318 SkTArray<SkOpSegment> segs; 319 for (size_t idx = 0; idx < test.count; ++idx) { 320 int ts[2]; 321 const SortSet* set = test.set; 322 SkOpSegment& seg = segs.push_back(); 323 setup(set, idx, &seg, ts, test.startPt); 324 SkOpAngle* angle = angles.append(); 325 angle->set(&seg, ts[0], ts[1]); 326 #if DEBUG_ANGLE 327 angle->setID(idx); 328 #endif 329 if (angle->unsortable()) { 330 #if DEBUG_ANGLE 331 SkDebugf("%s test[%s]: angle[%d] unsortable\n", __FUNCTION__, test.name, idx); 332 #endif 333 unsortable = true; 334 } 335 if (angle->unorderable()) { 336 #if DEBUG_ANGLE 337 SkDebugf("%s test[%s]: angle[%d] unorderable\n", __FUNCTION__, test.name, idx); 338 #endif 339 unorderable = true; 340 } 341 reporter->bumpTestCount(); 342 } 343 if (unsortable || unorderable) { 344 return; 345 } 346 #if DEBUG_ANGLE 347 SkDebugf("%s test[%s]\n", __FUNCTION__, test.name); 348 #endif 349 for (size_t idxL = 0; idxL < test.count; ++idxL) { 350 const SkOpAngle& first = angles[idxL]; 351 for (size_t idxG = 0; idxG < test.count; ++idxG) { 352 if (idxL == idxG) { 353 continue; 354 } 355 const SkOpAngle& second = angles[idxG]; 356 bool compare = first < second; 357 if (idxL < idxG) { 358 if (!compare) { 359 SkDebugf("%s test[%s]: first[%d] > second[%d]\n", __FUNCTION__, 360 test.name, idxL, idxG); 361 compare = first < second; 362 } 363 REPORTER_ASSERT(reporter, compare); 364 } else { 365 SkASSERT(idxL > idxG); 366 if (compare) { 367 SkDebugf("%s test[%s]: first[%d] < second[%d]\n", __FUNCTION__, 368 test.name, idxL, idxG); 369 compare = first < second; 370 } 371 REPORTER_ASSERT(reporter, !compare); 372 } 373 compare = second < first; 374 if (idxL < idxG) { 375 if (compare) { 376 SkDebugf("%s test[%s]: second[%d] < first[%d]\n", __FUNCTION__, 377 test.name, idxL, idxG); 378 compare = second < first; 379 } 380 REPORTER_ASSERT(reporter, !compare); 381 } else { 382 SkASSERT(idxL > idxG); 383 if (!compare) { 384 SkDebugf("%s test[%s]: second[%d] > first[%d]\n", __FUNCTION__, 385 test.name, idxL, idxG); 386 compare = second < first; 387 } 388 REPORTER_ASSERT(reporter, compare); 389 } 390 } 391 } 392 } 393 394 static void PathOpsAngleTest(skiatest::Reporter* reporter) { 395 for (size_t index = 0; index < SK_ARRAY_COUNT(tests); ++index) { 396 const SortSetTests& test = tests[index]; 397 testOne(reporter, test); 398 reporter->bumpTestCount(); 399 } 400 } 401 402 static void PathOpsAngleTestOne(skiatest::Reporter* reporter) { 403 size_t index = 0; 404 const SortSetTests& test = tests[index]; 405 testOne(reporter, test); 406 } 407 408 #if 0 409 static int find_slop(double x, double y, double rx, double ry) { 410 int slopBits = 0; 411 bool less1, less2; 412 double absX = fabs(x); 413 double absY = fabs(y); 414 double length = absX < absY ? absX / 2 + absY : absX + absY / 2; 415 int exponent; 416 (void) frexp(length, &exponent); 417 double epsilon = ldexp(FLT_EPSILON, exponent); 418 do { 419 // get the length as the larger plus half the smaller (both same signs) 420 // find the ulps of the length 421 // compute the offsets from there 422 double xSlop = epsilon * slopBits; 423 double ySlop = x * y < 0 ? -xSlop : xSlop; // OPTIMIZATION: use copysign / _copysign ? 424 double x1 = x - xSlop; 425 double y1 = y + ySlop; 426 double x_ry1 = x1 * ry; 427 double rx_y1 = rx * y1; 428 less1 = x_ry1 < rx_y1; 429 double x2 = x + xSlop; 430 double y2 = y - ySlop; 431 double x_ry2 = x2 * ry; 432 double rx_y2 = rx * y2; 433 less2 = x_ry2 < rx_y2; 434 } while (less1 == less2 && ++slopBits); 435 return slopBits; 436 } 437 438 // from http://stackoverflow.com/questions/1427422/cheap-algorithm-to-find-measure-of-angle-between-vectors 439 static double diamond_angle(double y, double x) 440 { 441 if (y >= 0) 442 return (x >= 0 ? y/(x+y) : 1-x/(-x+y)); 443 else 444 return (x < 0 ? 2-y/(-x-y) : 3+x/(x-y)); 445 } 446 447 static const double slopTests[][4] = { 448 // x y rx ry 449 {-0.058554756452593892, -0.18804585843827226, -0.018568569646021160, -0.059615294434479438}, 450 {-0.0013717412948608398, 0.0041152238845825195, -0.00045837944195925573, 0.0013753175735478074}, 451 {-2.1033774145221198, -1.4046019261273715e-008, -0.70062688352066704, -1.2706324683777995e-008}, 452 }; 453 454 static void PathOpsAngleFindSlop(skiatest::Reporter* reporter) { 455 for (size_t index = 0; index < SK_ARRAY_COUNT(slopTests); ++index) { 456 const double* slopTest = slopTests[index]; 457 double x = slopTest[0]; 458 double y = slopTest[1]; 459 double rx = slopTest[2]; 460 double ry = slopTest[3]; 461 SkDebugf("%s xy %d=%d\n", __FUNCTION__, (int) index, find_slop(x, y, rx, ry)); 462 SkDebugf("%s rxy %d=%d\n", __FUNCTION__, (int) index, find_slop(rx, ry, x, y)); 463 double angle = diamond_angle(y, x); 464 double rAngle = diamond_angle(ry, rx); 465 double diff = fabs(angle - rAngle); 466 SkDebugf("%s diamond xy=%1.9g rxy=%1.9g diff=%1.9g factor=%d\n", __FUNCTION__, 467 angle, rAngle, diff, (int) (diff / FLT_EPSILON)); 468 469 } 470 } 471 #endif 472 473 #include "TestClassDef.h" 474 DEFINE_TESTCLASS_SHORT(PathOpsAngleTest) 475 476 DEFINE_TESTCLASS_SHORT(PathOpsAngleTestOne) 477 478 // DEFINE_TESTCLASS_SHORT(PathOpsAngleFindSlop) 479
