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 #include "PathOpsCubicIntersectionTestData.h" 8 #include "PathOpsTestCommon.h" 9 #include "SkIntersections.h" 10 #include "SkPathOpsRect.h" 11 #include "SkReduceOrder.h" 12 #include "Test.h" 13 14 const int firstCubicIntersectionTest = 9; 15 16 static void standardTestCases(skiatest::Reporter* reporter) { 17 for (size_t index = firstCubicIntersectionTest; index < tests_count; ++index) { 18 int iIndex = static_cast<int>(index); 19 const SkDCubic& cubic1 = tests[index][0]; 20 const SkDCubic& cubic2 = tests[index][1]; 21 SkReduceOrder reduce1, reduce2; 22 int order1 = reduce1.reduce(cubic1, SkReduceOrder::kNo_Quadratics, 23 SkReduceOrder::kFill_Style); 24 int order2 = reduce2.reduce(cubic2, SkReduceOrder::kNo_Quadratics, 25 SkReduceOrder::kFill_Style); 26 const bool showSkipped = false; 27 if (order1 < 4) { 28 if (showSkipped) { 29 SkDebugf("%s [%d] cubic1 order=%d\n", __FUNCTION__, iIndex, order1); 30 } 31 continue; 32 } 33 if (order2 < 4) { 34 if (showSkipped) { 35 SkDebugf("%s [%d] cubic2 order=%d\n", __FUNCTION__, iIndex, order2); 36 } 37 continue; 38 } 39 SkIntersections tIntersections; 40 tIntersections.intersect(cubic1, cubic2); 41 if (!tIntersections.used()) { 42 if (showSkipped) { 43 SkDebugf("%s [%d] no intersection\n", __FUNCTION__, iIndex); 44 } 45 continue; 46 } 47 if (tIntersections.isCoincident(0)) { 48 if (showSkipped) { 49 SkDebugf("%s [%d] coincident\n", __FUNCTION__, iIndex); 50 } 51 continue; 52 } 53 for (int pt = 0; pt < tIntersections.used(); ++pt) { 54 double tt1 = tIntersections[0][pt]; 55 SkDPoint xy1 = cubic1.ptAtT(tt1); 56 double tt2 = tIntersections[1][pt]; 57 SkDPoint xy2 = cubic2.ptAtT(tt2); 58 if (!xy1.approximatelyEqual(xy2)) { 59 SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", 60 __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY); 61 } 62 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); 63 } 64 } 65 } 66 67 static const SkDCubic testSet[] = { 68 // FIXME: uncommenting these two will cause this to fail 69 // this results in two curves very nearly but not exactly coincident 70 #if 0 71 {{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306}, 72 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}}, 73 {{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, 74 {75.3863417, 18.24489}}}, 75 #endif 76 77 {{{0, 0}, {0, 1}, {1, 1}, {1, 0}}}, 78 {{{1, 0}, {0, 0}, {0, 1}, {1, 1}}}, 79 80 {{{0, 1}, {4, 5}, {1, 0}, {5, 3}}}, 81 {{{0, 1}, {3, 5}, {1, 0}, {5, 4}}}, 82 83 {{{0, 1}, {1, 6}, {1, 0}, {1, 0}}}, 84 {{{0, 1}, {0, 1}, {1, 0}, {6, 1}}}, 85 86 {{{0, 1}, {3, 4}, {1, 0}, {5, 1}}}, 87 {{{0, 1}, {1, 5}, {1, 0}, {4, 3}}}, 88 89 {{{0, 1}, {1, 2}, {1, 0}, {6, 1}}}, 90 {{{0, 1}, {1, 6}, {1, 0}, {2, 1}}}, 91 92 {{{0, 1}, {0, 5}, {1, 0}, {4, 0}}}, 93 {{{0, 1}, {0, 4}, {1, 0}, {5, 0}}}, 94 95 {{{0, 1}, {3, 4}, {1, 0}, {3, 0}}}, 96 {{{0, 1}, {0, 3}, {1, 0}, {4, 3}}}, 97 98 {{{0, 0}, {1, 2}, {3, 4}, {4, 4}}}, 99 {{{0, 0}, {1, 2}, {3, 4}, {4, 4}}}, 100 {{{4, 4}, {3, 4}, {1, 2}, {0, 0}}}, 101 102 {{{0, 1}, {2, 3}, {1, 0}, {1, 0}}}, 103 {{{0, 1}, {0, 1}, {1, 0}, {3, 2}}}, 104 105 {{{0, 2}, {0, 1}, {1, 0}, {1, 0}}}, 106 {{{0, 1}, {0, 1}, {2, 0}, {1, 0}}}, 107 108 {{{0, 1}, {0, 2}, {1, 0}, {1, 0}}}, 109 {{{0, 1}, {0, 1}, {1, 0}, {2, 0}}}, 110 111 {{{0, 1}, {1, 6}, {1, 0}, {2, 0}}}, 112 {{{0, 1}, {0, 2}, {1, 0}, {6, 1}}}, 113 114 {{{0, 1}, {5, 6}, {1, 0}, {1, 0}}}, 115 {{{0, 1}, {0, 1}, {1, 0}, {6, 5}}}, 116 117 {{{95.837747722788592, 45.025976907939643}, {16.564570095652982, 0.72959763963222402}, 118 {63.209855865319199, 68.047528419665767}, {57.640240647662544, 59.524565264361243}}}, 119 {{{51.593891741518817, 38.53849970667553}, {62.34752929878772, 74.924924725166022}, 120 {74.810149322641152, 34.17966562983564}, {29.368398119401373, 94.66719277886078}}}, 121 122 {{{39.765160968417838, 33.060396198677083}, {5.1922921581157908, 66.854301452103215}, 123 {31.619281802149157, 25.269248720849514}, {81.541621071073038, 70.025341524754353}}}, 124 {{{46.078911165743556, 48.259962651999651}, {20.24450549867214, 49.403916182650214}, 125 {0.26325131778756683, 24.46489805563581}, {15.915006546264051, 83.515023059917155}}}, 126 127 {{{65.454505973241524, 93.881892270353575}, {45.867360264932437, 92.723972719499827}, 128 {2.1464054482739447, 74.636369140183717}, {33.774068594804994, 40.770872887582925}}}, 129 {{{72.963387832494163, 95.659300729473728}, {11.809496633619768, 82.209921247423594}, 130 {13.456139067865974, 57.329313623406605}, {36.060621606214262, 70.867335643091849}}}, 131 132 {{{32.484981432782945, 75.082940782924624}, {42.467313093350882, 48.131159948246157}, 133 {3.5963115764764657, 43.208665839959245}, {79.442476890721579, 89.709102357602262}}}, 134 {{{18.98573861410177, 93.308887208490106}, {40.405250173250792, 91.039661826118675}, 135 {8.0467721950480584, 42.100282172719147}, {40.883324221187891, 26.030185504830527}}}, 136 137 {{{7.5374809128872498, 82.441702896003477}, {22.444346930107265, 22.138854312775123}, 138 {66.76091829629658, 50.753805856571446}, {78.193478508942519, 97.7932997968948}}}, 139 {{{97.700573130371311, 53.53260215070685}, {87.72443481149358, 84.575876772671876}, 140 {19.215031396232092, 47.032676472809484}, {11.989686410869325, 10.659507480757082}}}, 141 142 {{{26.192053931854691, 9.8504326817814416}, {10.174241480498686, 98.476562741434464}, 143 {21.177712558385782, 33.814968789841501}, {75.329030899018534, 55.02231980442177}}}, 144 {{{56.222082700683771, 24.54395039218662}, {95.589995289030483, 81.050822735322086}, 145 {28.180450866082897, 28.837706255185282}, {60.128952916771617, 87.311672180570511}}}, 146 147 {{{42.449716172390481, 52.379709366885805}, {27.896043159019225, 48.797373636065686}, 148 {92.770268299044233, 89.899302036454571}, {12.102066544863426, 99.43241951960718}}}, 149 {{{45.77532924980639, 45.958701495993274}, {37.458701356062065, 68.393691335056758}, 150 {37.569326692060258, 27.673713456687381}, {60.674866037757539, 62.47349659096146}}}, 151 152 {{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306}, 153 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}}, 154 {{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745592}, 155 {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503699973002}}}, 156 157 {{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945}, 158 {18.5656052, 32.1268808}}}, 159 {{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981}, 160 {56.4860195, 60.529264}}}, 161 }; 162 163 const size_t testSetCount = SK_ARRAY_COUNT(testSet); 164 165 static const SkDCubic newTestSet[] = { 166 {{{3, 4}, {1, 5}, {4, 3}, {6, 4}}}, 167 {{{3, 4}, {4, 6}, {4, 3}, {5, 1}}}, 168 169 {{{130.04275512695312, 11417.413085937500 }, 170 {130.23312377929687, 11418.319335937500 }, 171 {131.03707885742187, 11419.000000000000 }, 172 {132.00000000000000, 11419.000000000000 }}}, 173 174 {{{132.00000000000000, 11419.000000000000 }, 175 {130.89543151855469, 11419.000000000000 }, 176 {130.00000000000000, 11418.104492187500 }, 177 {130.00000000000000, 11417.000000000000 }}}, 178 179 {{{1.0516976506771041, 2.9684399028541346 }, 180 {1.0604363140895228, 2.9633503074444141 }, 181 {1.0692548215065762, 2.9580354426587459 }, 182 {1.0781560339512140, 2.9525043684031349 }}}, 183 184 {{{1.0523038101345104, 2.9523755204833737 }, 185 {1.0607035288264237, 2.9580853881628375 }, 186 {1.0690530472271964, 2.9633896794787749 }, 187 {1.0773566568712512, 2.9682969775000219 }}}, 188 189 {{{1.0386522625066592, 2.9759024812329078 }, 190 {1.0559713690392631, 2.9661782500838885 }, 191 {1.0736041309019990, 2.9555348259177858 }, 192 {1.0915734362784633, 2.9440446879826569 }}}, 193 194 {{{1.0396670794879301, 2.9435062123457261 }, 195 {1.0565690546812769, 2.9557413250983462 }, 196 {1.0732616463413533, 2.9663369676594282 }, 197 {1.0897791867435489, 2.9753618045797472 }}}, 198 199 {{{0.8685656183311091, 3.0409266475785208 }, 200 {0.99189542936395292, 3.0212163698184424 }, 201 {1.1302108367493320, 2.9265646471747306 }, 202 {1.2952305904872474, 2.7940808546473788 }}}, 203 204 {{{0.85437872843682727, 2.7536036928549055 }, 205 {1.0045584590592620, 2.9493041024831705 }, 206 {1.1336998329885613, 3.0248027987251747 }, 207 {1.2593809752247314, 3.0152560315809107 }}}, 208 209 {{{0, 1}, {1, 6}, {1, 0}, {6, 2}}}, 210 {{{0, 1}, {2, 6}, {1, 0}, {6, 1}}}, 211 212 {{{134,11414}, {131.990234375,11414}, {130.32666015625,11415.482421875}, {130.04275512695312,11417.4130859375}}}, 213 {{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}}, 214 215 {{{132,11419}, {130.89543151855469,11419}, {130,11418.1044921875}, {130,11417}}}, 216 {{{130.04275512695312,11417.4130859375}, {130.23312377929687,11418.3193359375}, {131.03707885742187,11419}, {132,11419}}}, 217 218 {{{0, 1}, {2, 3}, {5, 1}, {4, 3}}}, 219 {{{1, 5}, {3, 4}, {1, 0}, {3, 2}}}, 220 221 {{{3, 5}, {1, 6}, {5, 0}, {3, 1}}}, 222 {{{0, 5}, {1, 3}, {5, 3}, {6, 1}}}, 223 224 {{{0, 1}, {1, 5}, {1, 0}, {1, 0}}}, 225 {{{0, 1}, {0, 1}, {1, 0}, {5, 1}}}, 226 227 {{{1, 3}, {5, 6}, {5, 3}, {5, 4}}}, 228 {{{3, 5}, {4, 5}, {3, 1}, {6, 5}}}, 229 230 {{{0, 5}, {0, 5}, {5, 4}, {6, 4}}}, 231 {{{4, 5}, {4, 6}, {5, 0}, {5, 0}}}, 232 233 {{{0, 4}, {1, 3}, {5, 4}, {4, 2}}}, 234 {{{4, 5}, {2, 4}, {4, 0}, {3, 1}}}, 235 236 {{{0, 2}, {1, 5}, {3, 2}, {4, 1}}}, 237 {{{2, 3}, {1, 4}, {2, 0}, {5, 1}}}, 238 239 {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}}, 240 {{{1, 5}, {2, 3}, {2, 0}, {3, 2}}}, 241 242 {{{2, 6}, {4, 5}, {1, 0}, {6, 1}}}, 243 {{{0, 1}, {1, 6}, {6, 2}, {5, 4}}}, 244 245 {{{0, 1}, {1, 2}, {6, 5}, {5, 4}}}, 246 {{{5, 6}, {4, 5}, {1, 0}, {2, 1}}}, 247 248 {{{2.5119999999999996, 1.5710000000000002}, {2.6399999999999983, 1.6599999999999997}, 249 {2.8000000000000007, 1.8000000000000003}, {3, 2}}}, 250 {{{2.4181876227114887, 1.9849772580462195}, {2.8269904869227211, 2.009330650246834}, 251 {3.2004679292461624, 1.9942047174679169}, {3.4986199496818058, 2.0035994597094731}}}, 252 253 {{{2, 3}, {1, 4}, {1, 0}, {6, 0}}}, 254 {{{0, 1}, {0, 6}, {3, 2}, {4, 1}}}, 255 256 {{{0, 2}, {1, 5}, {1, 0}, {6, 1}}}, 257 {{{0, 1}, {1, 6}, {2, 0}, {5, 1}}}, 258 259 {{{0, 1}, {1, 5}, {2, 1}, {4, 0}}}, 260 {{{1, 2}, {0, 4}, {1, 0}, {5, 1}}}, 261 262 {{{0, 1}, {3, 5}, {2, 1}, {3, 1}}}, 263 {{{1, 2}, {1, 3}, {1, 0}, {5, 3}}}, 264 265 {{{0, 1}, {2, 5}, {6, 0}, {5, 3}}}, 266 {{{0, 6}, {3, 5}, {1, 0}, {5, 2}}}, 267 268 {{{0, 1}, {3, 6}, {1, 0}, {5, 2}}}, 269 {{{0, 1}, {2, 5}, {1, 0}, {6, 3}}}, 270 271 {{{1, 2}, {5, 6}, {1, 0}, {1, 0}}}, 272 {{{0, 1}, {0, 1}, {2, 1}, {6, 5}}}, 273 274 {{{0, 6}, {1, 2}, {1, 0}, {1, 0}}}, 275 {{{0, 1}, {0, 1}, {6, 0}, {2, 1}}}, 276 277 {{{0, 2}, {0, 1}, {3, 0}, {1, 0}}}, 278 {{{0, 3}, {0, 1}, {2, 0}, {1, 0}}}, 279 }; 280 281 const size_t newTestSetCount = SK_ARRAY_COUNT(newTestSet); 282 283 static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const SkDCubic& cubic2) { 284 SkASSERT(ValidCubic(cubic1)); 285 SkASSERT(ValidCubic(cubic2)); 286 #if ONE_OFF_DEBUG 287 SkDebugf("computed quadratics given\n"); 288 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", 289 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, 290 cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY); 291 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", 292 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, 293 cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY); 294 #endif 295 SkTArray<SkDQuad, true> quads1; 296 CubicToQuads(cubic1, cubic1.calcPrecision(), quads1); 297 #if ONE_OFF_DEBUG 298 SkDebugf("computed quadratics set 1\n"); 299 for (int index = 0; index < quads1.count(); ++index) { 300 const SkDQuad& q = quads1[index]; 301 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY, 302 q[1].fX, q[1].fY, q[2].fX, q[2].fY); 303 } 304 #endif 305 SkTArray<SkDQuad, true> quads2; 306 CubicToQuads(cubic2, cubic2.calcPrecision(), quads2); 307 #if ONE_OFF_DEBUG 308 SkDebugf("computed quadratics set 2\n"); 309 for (int index = 0; index < quads2.count(); ++index) { 310 const SkDQuad& q = quads2[index]; 311 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX, q[0].fY, 312 q[1].fX, q[1].fY, q[2].fX, q[2].fY); 313 } 314 #endif 315 SkIntersections intersections; 316 intersections.intersect(cubic1, cubic2); 317 double tt1, tt2; 318 SkDPoint xy1, xy2; 319 for (int pt3 = 0; pt3 < intersections.used(); ++pt3) { 320 tt1 = intersections[0][pt3]; 321 xy1 = cubic1.ptAtT(tt1); 322 tt2 = intersections[1][pt3]; 323 xy2 = cubic2.ptAtT(tt2); 324 const SkDPoint& iPt = intersections.pt(pt3); 325 #if ONE_OFF_DEBUG 326 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", 327 __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX, 328 iPt.fY, xy2.fX, xy2.fY, tt2); 329 #endif 330 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt)); 331 REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt)); 332 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); 333 } 334 } 335 336 static void oneOff(skiatest::Reporter* reporter, int outer, int inner) { 337 const SkDCubic& cubic1 = testSet[outer]; 338 const SkDCubic& cubic2 = testSet[inner]; 339 oneOff(reporter, cubic1, cubic2); 340 } 341 342 static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) { 343 const SkDCubic& cubic1 = newTestSet[outer]; 344 const SkDCubic& cubic2 = newTestSet[inner]; 345 oneOff(reporter, cubic1, cubic2); 346 } 347 348 static void oneOffTests(skiatest::Reporter* reporter) { 349 for (size_t outer = 0; outer < testSetCount - 1; ++outer) { 350 for (size_t inner = outer + 1; inner < testSetCount; ++inner) { 351 oneOff(reporter, outer, inner); 352 } 353 } 354 for (size_t outer = 0; outer < newTestSetCount - 1; ++outer) { 355 for (size_t inner = outer + 1; inner < newTestSetCount; ++inner) { 356 newOneOff(reporter, outer, inner); 357 } 358 } 359 } 360 361 #define DEBUG_CRASH 0 362 363 static void CubicIntersection_RandTest(skiatest::Reporter* reporter) { 364 srand(0); 365 const int tests = 10000000; 366 #if !defined(SK_BUILD_FOR_WIN) && !defined(SK_BUILD_FOR_ANDROID) 367 unsigned seed = 0; 368 #endif 369 for (int test = 0; test < tests; ++test) { 370 SkDCubic cubic1, cubic2; 371 for (int i = 0; i < 4; ++i) { 372 cubic1[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100; 373 cubic1[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100; 374 cubic2[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100; 375 cubic2[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100; 376 } 377 #if DEBUG_CRASH 378 char str[1024]; 379 snprintf(str, sizeof(str), 380 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n" 381 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n", 382 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, cubic1[2].fX, cubic1[2].fY, 383 cubic1[3].fX, cubic1[3].fY, 384 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, cubic2[2].fX, cubic2[2].fY, 385 cubic2[3].fX, cubic2[3].fY); 386 #endif 387 SkDRect rect1, rect2; 388 rect1.setBounds(cubic1); 389 rect2.setBounds(cubic2); 390 bool boundsIntersect = rect1.fLeft <= rect2.fRight && rect2.fLeft <= rect2.fRight 391 && rect1.fTop <= rect2.fBottom && rect2.fTop <= rect1.fBottom; 392 if (test == -1) { 393 SkDebugf("ready...\n"); 394 } 395 SkIntersections intersections2; 396 int newIntersects = intersections2.intersect(cubic1, cubic2); 397 if (!boundsIntersect && newIntersects) { 398 #if DEBUG_CRASH 399 SkDebugf("%s %d unexpected intersection boundsIntersect=%d " 400 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect, 401 newIntersects, __FUNCTION__, str); 402 #endif 403 REPORTER_ASSERT(reporter, 0); 404 } 405 for (int pt = 0; pt < intersections2.used(); ++pt) { 406 double tt1 = intersections2[0][pt]; 407 SkDPoint xy1 = cubic1.ptAtT(tt1); 408 double tt2 = intersections2[1][pt]; 409 SkDPoint xy2 = cubic2.ptAtT(tt2); 410 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); 411 } 412 } 413 } 414 415 static void intersectionFinder(int index0, int index1, double t1Seed, double t2Seed, 416 double t1Step, double t2Step) { 417 const SkDCubic& cubic1 = newTestSet[index0]; 418 const SkDCubic& cubic2 = newTestSet[index1]; 419 SkDPoint t1[3], t2[3]; 420 bool toggle = true; 421 do { 422 t1[0] = cubic1.ptAtT(t1Seed - t1Step); 423 t1[1] = cubic1.ptAtT(t1Seed); 424 t1[2] = cubic1.ptAtT(t1Seed + t1Step); 425 t2[0] = cubic2.ptAtT(t2Seed - t2Step); 426 t2[1] = cubic2.ptAtT(t2Seed); 427 t2[2] = cubic2.ptAtT(t2Seed + t2Step); 428 double dist[3][3]; 429 dist[1][1] = t1[1].distance(t2[1]); 430 int best_i = 1, best_j = 1; 431 for (int i = 0; i < 3; ++i) { 432 for (int j = 0; j < 3; ++j) { 433 if (i == 1 && j == 1) { 434 continue; 435 } 436 dist[i][j] = t1[i].distance(t2[j]); 437 if (dist[best_i][best_j] > dist[i][j]) { 438 best_i = i; 439 best_j = j; 440 } 441 } 442 } 443 if (best_i == 0) { 444 t1Seed -= t1Step; 445 } else if (best_i == 2) { 446 t1Seed += t1Step; 447 } 448 if (best_j == 0) { 449 t2Seed -= t2Step; 450 } else if (best_j == 2) { 451 t2Seed += t2Step; 452 } 453 if (best_i == 1 && best_j == 1) { 454 if ((toggle ^= true)) { 455 t1Step /= 2; 456 } else { 457 t2Step /= 2; 458 } 459 } 460 } while (!t1[1].approximatelyEqual(t2[1])); 461 t1Step = t2Step = 0.1; 462 double t10 = t1Seed - t1Step * 2; 463 double t12 = t1Seed + t1Step * 2; 464 double t20 = t2Seed - t2Step * 2; 465 double t22 = t2Seed + t2Step * 2; 466 SkDPoint test; 467 while (!approximately_zero(t1Step)) { 468 test = cubic1.ptAtT(t10); 469 t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; 470 t1Step /= 2; 471 } 472 t1Step = 0.1; 473 while (!approximately_zero(t1Step)) { 474 test = cubic1.ptAtT(t12); 475 t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; 476 t1Step /= 2; 477 } 478 while (!approximately_zero(t2Step)) { 479 test = cubic2.ptAtT(t20); 480 t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; 481 t2Step /= 2; 482 } 483 t2Step = 0.1; 484 while (!approximately_zero(t2Step)) { 485 test = cubic2.ptAtT(t22); 486 t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; 487 t2Step /= 2; 488 } 489 #if ONE_OFF_DEBUG 490 SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, 491 t10, t1Seed, t12, t20, t2Seed, t22); 492 SkDPoint p10 = cubic1.ptAtT(t10); 493 SkDPoint p1Seed = cubic1.ptAtT(t1Seed); 494 SkDPoint p12 = cubic1.ptAtT(t12); 495 SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, 496 p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY); 497 SkDPoint p20 = cubic2.ptAtT(t20); 498 SkDPoint p2Seed = cubic2.ptAtT(t2Seed); 499 SkDPoint p22 = cubic2.ptAtT(t22); 500 SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, 501 p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY); 502 #endif 503 } 504 505 static void CubicIntersection_IntersectionFinder() { 506 // double t1Seed = 0.87; 507 // double t2Seed = 0.87; 508 double t1Step = 0.000001; 509 double t2Step = 0.000001; 510 intersectionFinder(0, 1, 0.855895664, 0.864850875, t1Step, t2Step); 511 intersectionFinder(0, 1, 0.865207906, 0.865207887, t1Step, t2Step); 512 intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step); 513 } 514 515 static const SkDCubic selfSet[] = { 516 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}}, 517 {{{3, 6}, {2, 3}, {4, 0}, {3, 2}}}, 518 {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}}, 519 {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}}, 520 {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}}, 521 {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}}, 522 {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}}, 523 {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}}, 524 }; 525 size_t selfSetCount = SK_ARRAY_COUNT(selfSet); 526 527 static void selfOneOff(skiatest::Reporter* reporter, int index) { 528 const SkDCubic& cubic = selfSet[index]; 529 #if ONE_OFF_DEBUG 530 int idx2; 531 double max[3]; 532 int ts = cubic.findMaxCurvature(max); 533 for (idx2 = 0; idx2 < ts; ++idx2) { 534 SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2, 535 max[idx2], cubic.ptAtT(max[idx2]).fX, cubic.ptAtT(max[idx2]).fY); 536 } 537 SkTArray<double, true> ts1; 538 SkTArray<SkDQuad, true> quads1; 539 cubic.toQuadraticTs(cubic.calcPrecision(), &ts1); 540 for (idx2 = 0; idx2 < ts1.count(); ++idx2) { 541 SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]); 542 } 543 CubicToQuads(cubic, cubic.calcPrecision(), quads1); 544 for (idx2 = 0; idx2 < quads1.count(); ++idx2) { 545 const SkDQuad& q = quads1[idx2]; 546 SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", 547 q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY); 548 } 549 SkDebugf("\n"); 550 #endif 551 SkIntersections i; 552 int result = i.intersect(cubic); 553 REPORTER_ASSERT(reporter, result == 1); 554 REPORTER_ASSERT(reporter, i.used() == 1); 555 REPORTER_ASSERT(reporter, !approximately_equal(i[0][0], i[1][0])); 556 SkDPoint pt1 = cubic.ptAtT(i[0][0]); 557 SkDPoint pt2 = cubic.ptAtT(i[1][0]); 558 REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2)); 559 } 560 561 static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) { 562 size_t firstFail = 0; 563 for (size_t index = firstFail; index < selfSetCount; ++index) { 564 selfOneOff(reporter, index); 565 } 566 } 567 568 static void PathOpsCubicIntersectionOneOffTest(skiatest::Reporter* reporter) { 569 newOneOff(reporter, 0, 1); 570 } 571 572 static void PathOpsCubicSelfOneOffTest(skiatest::Reporter* reporter) { 573 selfOneOff(reporter, 0); 574 } 575 576 static void PathOpsCubicIntersectionTest(skiatest::Reporter* reporter) { 577 oneOffTests(reporter); 578 cubicIntersectionSelfTest(reporter); 579 standardTestCases(reporter); 580 if (false) CubicIntersection_IntersectionFinder(); 581 if (false) CubicIntersection_RandTest(reporter); 582 } 583 584 #include "TestClassDef.h" 585 DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionTest) 586 587 DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionOneOffTest) 588 589 DEFINE_TESTCLASS_SHORT(PathOpsCubicSelfOneOffTest) 590
