CubicIntersection_Test.cpp revision 45a8fc6a8b00451f807783f2a6ec640e9bcc7256
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 "CurveIntersection.h" 8#include "CurveUtilities.h" 9#include "CubicIntersection_TestData.h" 10#include "Intersection_Tests.h" 11#include "Intersections.h" 12#include "TestUtilities.h" 13 14const int firstCubicIntersectionTest = 9; 15 16static void standardTestCases() { 17 for (size_t index = firstCubicIntersectionTest; index < tests_count; ++index) { 18 const Cubic& cubic1 = tests[index][0]; 19 const Cubic& cubic2 = tests[index][1]; 20 Cubic reduce1, reduce2; 21 int order1 = reduceOrder(cubic1, reduce1, kReduceOrder_NoQuadraticsAllowed); 22 int order2 = reduceOrder(cubic2, reduce2, kReduceOrder_NoQuadraticsAllowed); 23 if (order1 < 4) { 24 printf("%s [%d] cubic1 order=%d\n", __FUNCTION__, (int) index, order1); 25 continue; 26 } 27 if (order2 < 4) { 28 printf("%s [%d] cubic2 order=%d\n", __FUNCTION__, (int) index, order2); 29 continue; 30 } 31 if (implicit_matches(reduce1, reduce2)) { 32 printf("%s [%d] coincident\n", __FUNCTION__, (int) index); 33 continue; 34 } 35 Intersections tIntersections; 36 intersect(reduce1, reduce2, tIntersections); 37 if (!tIntersections.intersected()) { 38 printf("%s [%d] no intersection\n", __FUNCTION__, (int) index); 39 continue; 40 } 41 for (int pt = 0; pt < tIntersections.used(); ++pt) { 42 double tt1 = tIntersections.fT[0][pt]; 43 double tx1, ty1; 44 xy_at_t(cubic1, tt1, tx1, ty1); 45 double tt2 = tIntersections.fT[1][pt]; 46 double tx2, ty2; 47 xy_at_t(cubic2, tt2, tx2, ty2); 48 if (!AlmostEqualUlps(tx1, tx2)) { 49 printf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", 50 __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); 51 } 52 if (!AlmostEqualUlps(ty1, ty2)) { 53 printf("%s [%d,%d] y!= t1=%g (%g,%g) t2=%g (%g,%g)\n", 54 __FUNCTION__, (int)index, pt, tt1, tx1, ty1, tt2, tx2, ty2); 55 } 56 } 57 } 58} 59 60static const Cubic testSet[] = { 61{{0,1}, {4,5}, {1,0}, {5,3}}, 62{{0,1}, {3,5}, {1,0}, {5,4}}, 63 64{{0, 1}, {1, 6}, {1, 0}, {1, 0}}, 65{{0, 1}, {0, 1}, {1, 0}, {6, 1}}, 66 67{{0,1}, {3,4}, {1,0}, {5,1}}, 68{{0,1}, {1,5}, {1,0}, {4,3}}, 69 70{{0,1}, {1,2}, {1,0}, {6,1}}, 71{{0,1}, {1,6}, {1,0}, {2,1}}, 72 73{{0,1}, {0,5}, {1,0}, {4,0}}, 74{{0,1}, {0,4}, {1,0}, {5,0}}, 75 76{{0,1}, {3,4}, {1,0}, {3,0}}, 77{{0,1}, {0,3}, {1,0}, {4,3}}, 78 79{{0, 0}, {1, 2}, {3, 4}, {4, 4}}, 80{{0, 0}, {1, 2}, {3, 4}, {4, 4}}, 81{{4, 4}, {3, 4}, {1, 2}, {0, 0}}, 82 83{{0,1}, {2,3}, {1,0}, {1,0}}, 84{{0,1}, {0,1}, {1,0}, {3,2}}, 85 86{{0,2}, {0,1}, {1,0}, {1,0}}, 87{{0,1}, {0,1}, {2,0}, {1,0}}, 88 89{{0, 0}, {0, 1}, {1, 1}, {1, 0}}, 90{{1, 0}, {0, 0}, {0, 1}, {1, 1}}, 91 92{{0, 1}, {0, 2}, {1, 0}, {1, 0}}, 93{{0, 1}, {0, 1}, {1, 0}, {2, 0}}, 94 95{{0, 1}, {1, 6}, {1, 0}, {2, 0}}, 96{{0, 1}, {0, 2}, {1, 0}, {6, 1}}, 97 98{{0, 1}, {5, 6}, {1, 0}, {1, 0}}, 99{{0, 1}, {0, 1}, {1, 0}, {6, 5}}, 100 101{{95.837747722788592, 45.025976907939643}, {16.564570095652982, 0.72959763963222402}, {63.209855865319199, 68.047528419665767}, {57.640240647662544, 59.524565264361243}}, 102{{51.593891741518817, 38.53849970667553}, {62.34752929878772, 74.924924725166022}, {74.810149322641152, 34.17966562983564}, {29.368398119401373, 94.66719277886078}}, 103 104{{39.765160968417838, 33.060396198677083}, {5.1922921581157908, 66.854301452103215}, {31.619281802149157, 25.269248720849514}, {81.541621071073038, 70.025341524754353}}, 105{{46.078911165743556, 48.259962651999651}, {20.24450549867214, 49.403916182650214}, {0.26325131778756683, 24.46489805563581}, {15.915006546264051, 83.515023059917155}}, 106 107{{65.454505973241524, 93.881892270353575}, {45.867360264932437, 92.723972719499827}, {2.1464054482739447, 74.636369140183717}, {33.774068594804994, 40.770872887582925}}, 108{{72.963387832494163, 95.659300729473728}, {11.809496633619768, 82.209921247423594}, {13.456139067865974, 57.329313623406605}, {36.060621606214262, 70.867335643091849}}, 109 110{{32.484981432782945, 75.082940782924624}, {42.467313093350882, 48.131159948246157}, {3.5963115764764657, 43.208665839959245}, {79.442476890721579, 89.709102357602262}}, 111{{18.98573861410177, 93.308887208490106}, {40.405250173250792, 91.039661826118675}, {8.0467721950480584, 42.100282172719147}, {40.883324221187891, 26.030185504830527}}, 112 113{{7.5374809128872498, 82.441702896003477}, {22.444346930107265, 22.138854312775123}, {66.76091829629658, 50.753805856571446}, {78.193478508942519, 97.7932997968948}}, 114{{97.700573130371311, 53.53260215070685}, {87.72443481149358, 84.575876772671876}, {19.215031396232092, 47.032676472809484}, {11.989686410869325, 10.659507480757082}}, 115 116{{26.192053931854691, 9.8504326817814416}, {10.174241480498686, 98.476562741434464}, {21.177712558385782, 33.814968789841501}, {75.329030899018534, 55.02231980442177}}, 117{{56.222082700683771, 24.54395039218662}, {95.589995289030483, 81.050822735322086}, {28.180450866082897, 28.837706255185282}, {60.128952916771617, 87.311672180570511}}, 118 119{{42.449716172390481, 52.379709366885805}, {27.896043159019225, 48.797373636065686}, {92.770268299044233, 89.899302036454571}, {12.102066544863426, 99.43241951960718}}, 120{{45.77532924980639, 45.958701495993274}, {37.458701356062065, 68.393691335056758}, {37.569326692060258, 27.673713456687381}, {60.674866037757539, 62.47349659096146}}, 121 122{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306}, {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}, 123{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745592}, {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503699973002}}, 124 125{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, {75.3863417, 18.24489}}, 126{{61.3365082, 82.6931328}, {44.6393809, 54.0748258}, {16.8156155, 20.0497047}, {41.866885, 56.7355037}}, 127 128{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945}, {18.5656052, 32.1268808}}, 129{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981}, {56.4860195, 60.529264}}, 130}; 131 132const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]); 133 134static void oneOff(const Cubic& cubic1, const Cubic& cubic2) { 135 SkTDArray<Quadratic> quads1; 136 cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1); 137#if ONE_OFF_DEBUG 138 for (int index = 0; index < quads1.count(); ++index) { 139 const Quadratic& q = quads1[index]; 140 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, 141 q[1].x, q[1].y, q[2].x, q[2].y); 142 } 143 SkDebugf("\n"); 144#endif 145 SkTDArray<Quadratic> quads2; 146 cubic_to_quadratics(cubic2, calcPrecision(cubic2), quads2); 147#if ONE_OFF_DEBUG 148 for (int index = 0; index < quads2.count(); ++index) { 149 const Quadratic& q = quads2[index]; 150 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, 151 q[1].x, q[1].y, q[2].x, q[2].y); 152 } 153 SkDebugf("\n"); 154#endif 155 Intersections intersections2, intersections3; 156 intersect2(cubic1, cubic2, intersections2); 157 intersect3(cubic1, cubic2, intersections3); 158 int pt1, pt2, pt3; 159 bool found; 160 double tt1, tt2, last = -1; 161 _Point xy1, xy2; 162 for (pt1 = 0; pt1 < intersections2.used(); ++pt1) { 163 tt1 = intersections2.fT[0][pt1]; 164 SkASSERT(!approximately_equal(last, tt1)); 165 last = tt1; 166 xy_at_t(cubic1, tt1, xy1.x, xy1.y); 167 pt2 = intersections2.fFlip ? intersections2.used() - pt1 - 1 : pt1; 168 tt2 = intersections2.fT[1][pt2]; 169 xy_at_t(cubic2, tt2, xy2.x, xy2.y); 170#if ONE_OFF_DEBUG 171 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", 172 __FUNCTION__, tt1, xy1.x, xy1.y, intersections2.fPt[pt1].x, 173 intersections2.fPt[pt1].y, xy2.x, xy2.y, tt2); 174#endif 175 SkASSERT(xy1.approximatelyEqual(xy2)); 176#if SK_DEBUG 177 found = false; 178 for (pt3 = 0; pt3 < intersections3.used(); ++pt3) { 179 if (roughly_equal(tt1, intersections3.fT[0][pt3])) { 180 found = true; 181 break; 182 } 183 } 184 SkASSERT(found); 185#endif 186 } 187 last = -1; 188 for (pt3 = 0; pt3 < intersections3.used(); ++pt3) { 189 found = false; 190 double tt3 = intersections3.fT[0][pt3]; 191 SkASSERT(!approximately_equal(last, tt3)); 192 last = tt3; 193 for (pt1 = 0; pt1 < intersections2.used(); ++pt1) { 194 if (approximately_equal(tt3, intersections2.fT[0][pt1])) { 195 found = true; 196 break; 197 } 198 } 199 if (!found) { 200 tt1 = intersections3.fT[0][pt3]; 201 xy_at_t(cubic1, tt1, xy1.x, xy1.y); 202 pt2 = intersections3.fFlip ? intersections3.used() - pt3 - 1 : pt3; 203 tt2 = intersections3.fT[1][pt2]; 204 xy_at_t(cubic2, tt2, xy2.x, xy2.y); 205 #if ONE_OFF_DEBUG 206 SkDebugf("%s t3=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", 207 __FUNCTION__, tt1, xy1.x, xy1.y, intersections3.fPt[pt1].x, 208 intersections3.fPt[pt1].y, xy2.x, xy2.y, tt2); 209 #endif 210 SkASSERT(xy1.approximatelyEqual(xy2)); 211 SkDebugf("%s missing in intersect2\n", __FUNCTION__); 212 } 213 } 214} 215 216static void oneOff3(const Cubic& cubic1, const Cubic& cubic2) { 217 SkTDArray<Quadratic> quads1; 218 cubic_to_quadratics(cubic1, calcPrecision(cubic1), quads1); 219#if ONE_OFF_DEBUG 220 for (int index = 0; index < quads1.count(); ++index) { 221 const Quadratic& q = quads1[index]; 222 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, 223 q[1].x, q[1].y, q[2].x, q[2].y); 224 } 225 SkDebugf("\n"); 226#endif 227 SkTDArray<Quadratic> quads2; 228 cubic_to_quadratics(cubic2, calcPrecision(cubic2), quads2); 229#if ONE_OFF_DEBUG 230 for (int index = 0; index < quads2.count(); ++index) { 231 const Quadratic& q = quads2[index]; 232 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].x, q[0].y, 233 q[1].x, q[1].y, q[2].x, q[2].y); 234 } 235 SkDebugf("\n"); 236#endif 237 Intersections intersections3; 238 intersect3(cubic1, cubic2, intersections3); 239 int pt2, pt3; 240 double tt1, tt2, last = -1; 241 _Point xy1, xy2; 242 for (pt3 = 0; pt3 < intersections3.used(); ++pt3) { 243 double tt3 = intersections3.fT[0][pt3]; 244 SkASSERT(!approximately_equal(last, tt3)); 245 last = tt3; 246 tt1 = intersections3.fT[0][pt3]; 247 xy_at_t(cubic1, tt1, xy1.x, xy1.y); 248 pt2 = intersections3.fFlip ? intersections3.used() - pt3 - 1 : pt3; 249 tt2 = intersections3.fT[1][pt2]; 250 xy_at_t(cubic2, tt2, xy2.x, xy2.y); 251#if ONE_OFF_DEBUG 252 SkDebugf("%s t3=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", 253 __FUNCTION__, tt1, xy1.x, xy1.y, intersections3.fPt[pt3].x, 254 intersections3.fPt[pt3].y, xy2.x, xy2.y, tt2); 255#endif 256 SkASSERT(xy1.approximatelyEqual(xy2)); 257 } 258} 259 260static int fails[][2] = { {0, 23}, // fails in intersect2 recursing 261 {2, 7}, // answers differ, but neither is correct ('3' is closer) 262 {3, 26}, // fails in intersect2 recursing 263 {4, 9}, // fails in intersect2 recursing 264 {4, 10}, // fails in intersect2 recursing 265 {10, 17}, // fails in intersect2 recursing 266 {12, 14}, // loops indefinitely 267 {12, 21}, // fails in intersect2 recursing 268 {13, 21}, // fails in intersect2 recursing 269 {14, 21}, // fails in intersect2 recursing 270 {17, 25}, // fails in intersect2 recursing 271 {23, 25}, // fails in intersect2 recursing 272}; 273 274static int failCount = sizeof(fails) / sizeof(fails[0]); 275 276static void oneOff(int outer, int inner) { 277 const Cubic& cubic1 = testSet[outer]; 278 const Cubic& cubic2 = testSet[inner]; 279 bool failing = false; 280 for (int i = 0; i < failCount; ++i) { 281 if ((fails[i][0] == outer && fails[i][1] == inner) 282 || (fails[i][1] == outer && fails[i][0] == inner)) { 283 failing = true; 284 break; 285 } 286 } 287 if (!failing) { 288 oneOff(cubic1, cubic2); 289 } else { 290 oneOff3(cubic1, cubic2); 291 } 292} 293 294void CubicIntersection_OneOffTest() { 295 oneOff(12, 14); 296} 297 298static void oneOffTests() { 299 for (size_t outer = 0; outer < testSetCount - 1; ++outer) { 300 for (size_t inner = outer + 1; inner < testSetCount; ++inner) { 301 oneOff(outer, inner); 302 } 303 } 304} 305 306void CubicIntersection_OneOffTests() { 307 oneOffTests(); 308} 309 310#define DEBUG_CRASH 0 311 312class CubicChopper { 313public: 314 315// only finds one intersection 316CubicChopper(const Cubic& c1, const Cubic& c2) 317 : cubic1(c1) 318 , cubic2(c2) 319 , depth(0) { 320} 321 322bool intersect(double minT1, double maxT1, double minT2, double maxT2) { 323 Cubic sub1, sub2; 324 // FIXME: carry last subdivide and reduceOrder result with cubic 325 sub_divide(cubic1, minT1, maxT1, sub1); 326 sub_divide(cubic2, minT2, maxT2, sub2); 327 Intersections i; 328 intersect2(sub1, sub2, i); 329 if (i.used() == 0) { 330 return false; 331 } 332 double x1, y1, x2, y2; 333 t1 = minT1 + i.fT[0][0] * (maxT1 - minT1); 334 t2 = minT2 + i.fT[1][0] * (maxT2 - minT2); 335 xy_at_t(cubic1, t1, x1, y1); 336 xy_at_t(cubic2, t2, x2, y2); 337 if (AlmostEqualUlps(x1, x2) && AlmostEqualUlps(y1, y2)) { 338 return true; 339 } 340 double half1 = (minT1 + maxT1) / 2; 341 double half2 = (minT2 + maxT2) / 2; 342 ++depth; 343 bool result; 344 if (depth & 1) { 345 result = intersect(minT1, half1, minT2, maxT2) || intersect(half1, maxT1, minT2, maxT2) 346 || intersect(minT1, maxT1, minT2, half2) || intersect(minT1, maxT1, half2, maxT2); 347 } else { 348 result = intersect(minT1, maxT1, minT2, half2) || intersect(minT1, maxT1, half2, maxT2) 349 || intersect(minT1, half1, minT2, maxT2) || intersect(half1, maxT1, minT2, maxT2); 350 } 351 --depth; 352 return result; 353} 354 355const Cubic& cubic1; 356const Cubic& cubic2; 357double t1; 358double t2; 359int depth; 360}; 361 362#define TRY_OLD 0 // old way fails on test == 1 363 364void CubicIntersection_RandTestOld() { 365 srand(0); 366 const int tests = 1000000; // 10000000; 367 double largestFactor = DBL_MAX; 368 for (int test = 0; test < tests; ++test) { 369 Cubic cubic1, cubic2; 370 for (int i = 0; i < 4; ++i) { 371 cubic1[i].x = (double) rand() / RAND_MAX * 100; 372 cubic1[i].y = (double) rand() / RAND_MAX * 100; 373 cubic2[i].x = (double) rand() / RAND_MAX * 100; 374 cubic2[i].y = (double) rand() / RAND_MAX * 100; 375 } 376 if (test == 2513) { // the pair crosses three times, but the quadratic approximation 377 continue; // only sees one -- should be OK to ignore the other two? 378 } 379 if (test == 12932) { // this exposes a weakness when one cubic touches the other but 380 continue; // does not touch the quad approximation. Captured in qc.htm as cubic15 381 } 382 #if DEBUG_CRASH 383 char str[1024]; 384 sprintf(str, "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n" 385 "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", 386 cubic1[0].x, cubic1[0].y, cubic1[1].x, cubic1[1].y, cubic1[2].x, cubic1[2].y, 387 cubic1[3].x, cubic1[3].y, 388 cubic2[0].x, cubic2[0].y, cubic2[1].x, cubic2[1].y, cubic2[2].x, cubic2[2].y, 389 cubic2[3].x, cubic2[3].y); 390 #endif 391 _Rect rect1, rect2; 392 rect1.setBounds(cubic1); 393 rect2.setBounds(cubic2); 394 bool boundsIntersect = rect1.left <= rect2.right && rect2.left <= rect2.right 395 && rect1.top <= rect2.bottom && rect2.top <= rect1.bottom; 396 Intersections i1, i2; 397 #if TRY_OLD 398 bool oldIntersects = intersect(cubic1, cubic2, i1); 399 #else 400 bool oldIntersects = false; 401 #endif 402 if (test == -1) { 403 SkDebugf("ready...\n"); 404 } 405 bool newIntersects = intersect2(cubic1, cubic2, i2); 406 if (!boundsIntersect && (oldIntersects || newIntersects)) { 407 #if DEBUG_CRASH 408 SkDebugf("%s %d unexpected intersection boundsIntersect=%d oldIntersects=%d" 409 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect, 410 oldIntersects, newIntersects, __FUNCTION__, str); 411 #endif 412 SkASSERT(0); 413 } 414 if (oldIntersects && !newIntersects) { 415 #if DEBUG_CRASH 416 SkDebugf("%s %d missing intersection oldIntersects=%d newIntersects=%d\n%s %s\n", 417 __FUNCTION__, test, oldIntersects, newIntersects, __FUNCTION__, str); 418 #endif 419 SkASSERT(0); 420 } 421 if (!oldIntersects && !newIntersects) { 422 continue; 423 } 424 if (i2.used() > 1) { 425 continue; 426 // just look at single intercepts for simplicity 427 } 428 Intersections self1, self2; // self-intersect checks 429 if (intersect(cubic1, self1)) { 430 continue; 431 } 432 if (intersect(cubic2, self2)) { 433 continue; 434 } 435 // binary search for range necessary to enclose real intersection 436 CubicChopper c(cubic1, cubic2); 437 bool result = c.intersect(0, 1, 0, 1); 438 if (!result) { 439 // FIXME: a failure here probably means that a core routine used by CubicChopper is failing 440 continue; 441 } 442 double delta1 = fabs(c.t1 - i2.fT[0][0]); 443 double delta2 = fabs(c.t2 - i2.fT[1][0]); 444 double calc1 = calcPrecision(cubic1); 445 double calc2 = calcPrecision(cubic2); 446 double factor1 = calc1 / delta1; 447 double factor2 = calc2 / delta2; 448 SkDebugf("%s %d calc1=%1.9g delta1=%1.9g factor1=%1.9g calc2=%1.9g delta2=%1.9g" 449 " factor2=%1.9g\n", __FUNCTION__, test, 450 calc1, delta1, factor1, calc2, delta2, factor2); 451 if (factor1 < largestFactor) { 452 SkDebugf("WE HAVE A WINNER! %1.9g\n", factor1); 453 #if DEBUG_CRASH 454 SkDebugf("%s\n", str); 455 #endif 456 oneOff(cubic1, cubic2); 457 largestFactor = factor1; 458 } 459 if (factor2 < largestFactor) { 460 SkDebugf("WE HAVE A WINNER! %1.9g\n", factor2); 461 #if DEBUG_CRASH 462 SkDebugf("%s\n", str); 463 #endif 464 oneOff(cubic1, cubic2); 465 largestFactor = factor2; 466 } 467 } 468} 469 470void CubicIntersection_RandTest() { 471 srand(0); 472 const int tests = 10000000; 473 for (int test = 0; test < tests; ++test) { 474 Cubic cubic1, cubic2; 475 for (int i = 0; i < 4; ++i) { 476 cubic1[i].x = (double) rand() / RAND_MAX * 100; 477 cubic1[i].y = (double) rand() / RAND_MAX * 100; 478 cubic2[i].x = (double) rand() / RAND_MAX * 100; 479 cubic2[i].y = (double) rand() / RAND_MAX * 100; 480 } 481 #if DEBUG_CRASH 482 char str[1024]; 483 sprintf(str, "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n" 484 "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", 485 cubic1[0].x, cubic1[0].y, cubic1[1].x, cubic1[1].y, cubic1[2].x, cubic1[2].y, 486 cubic1[3].x, cubic1[3].y, 487 cubic2[0].x, cubic2[0].y, cubic2[1].x, cubic2[1].y, cubic2[2].x, cubic2[2].y, 488 cubic2[3].x, cubic2[3].y); 489 #endif 490 _Rect rect1, rect2; 491 rect1.setBounds(cubic1); 492 rect2.setBounds(cubic2); 493 bool boundsIntersect = rect1.left <= rect2.right && rect2.left <= rect2.right 494 && rect1.top <= rect2.bottom && rect2.top <= rect1.bottom; 495 if (test == -1) { 496 SkDebugf("ready...\n"); 497 } 498 Intersections intersections2; 499 bool newIntersects = intersect2(cubic1, cubic2, intersections2); 500 if (!boundsIntersect && newIntersects) { 501 #if DEBUG_CRASH 502 SkDebugf("%s %d unexpected intersection boundsIntersect=%d " 503 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect, 504 newIntersects, __FUNCTION__, str); 505 #endif 506 SkASSERT(0); 507 } 508 for (int pt = 0; pt < intersections2.used(); ++pt) { 509 double tt1 = intersections2.fT[0][pt]; 510 _Point xy1, xy2; 511 xy_at_t(cubic1, tt1, xy1.x, xy1.y); 512 int pt2 = intersections2.fFlip ? intersections2.used() - pt - 1 : pt; 513 double tt2 = intersections2.fT[1][pt2]; 514 xy_at_t(cubic2, tt2, xy2.x, xy2.y); 515 #if 0 516 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__, 517 tt1, xy1.x, xy1.y, xy2.x, xy2.y, tt2); 518 #endif 519 SkASSERT(xy1.approximatelyEqual(xy2)); 520 } 521 } 522} 523 524void CubicIntersection_IntersectionFinder() { 525 const Cubic& cubic1 = testSet[2]; 526 const Cubic& cubic2 = testSet[7]; 527 528 double t1Seed = 0.254; 529 double t2Seed = 0.245; 530 double t1Step = 0.01; 531 double t2Step = 0.01; 532 _Point t1[3], t2[3]; 533 bool toggle = true; 534 do { 535 xy_at_t(cubic1, t1Seed - t1Step, t1[0].x, t1[0].y); 536 xy_at_t(cubic1, t1Seed, t1[1].x, t1[1].y); 537 xy_at_t(cubic1, t1Seed + t1Step, t1[2].x, t1[2].y); 538 xy_at_t(cubic2, t2Seed - t2Step, t2[0].x, t2[0].y); 539 xy_at_t(cubic2, t2Seed, t2[1].x, t2[1].y); 540 xy_at_t(cubic2, t2Seed + t2Step, t2[2].x, t2[2].y); 541 double dist[3][3]; 542 dist[1][1] = t1[1].distance(t2[1]); 543 int best_i = 1, best_j = 1; 544 for (int i = 0; i < 3; ++i) { 545 for (int j = 0; j < 3; ++j) { 546 if (i == 1 && j == 1) { 547 continue; 548 } 549 dist[i][j] = t1[i].distance(t2[j]); 550 if (dist[best_i][best_j] > dist[i][j]) { 551 best_i = i; 552 best_j = j; 553 } 554 } 555 } 556 if (best_i == 0) { 557 t1Seed -= t1Step; 558 } else if (best_i == 2) { 559 t1Seed += t1Step; 560 } 561 if (best_j == 0) { 562 t2Seed -= t2Step; 563 } else if (best_j == 2) { 564 t2Seed += t2Step; 565 } 566 if (best_i == 1 && best_j == 1) { 567 if ((toggle ^= true)) { 568 t1Step /= 2; 569 } else { 570 t2Step /= 2; 571 } 572 } 573 } while (!t1[1].approximatelyEqual(t2[1])); 574 t1Step = t2Step = 0.1; 575 double t10 = t1Seed - t1Step * 2; 576 double t12 = t1Seed + t1Step * 2; 577 double t20 = t2Seed - t2Step * 2; 578 double t22 = t2Seed + t2Step * 2; 579 _Point test; 580 while (!approximately_zero(t1Step)) { 581 xy_at_t(cubic1, t10, test.x, test.y); 582 t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; 583 t1Step /= 2; 584 } 585 t1Step = 0.1; 586 while (!approximately_zero(t1Step)) { 587 xy_at_t(cubic1, t12, test.x, test.y); 588 t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; 589 t1Step /= 2; 590 } 591 while (!approximately_zero(t2Step)) { 592 xy_at_t(cubic2, t20, test.x, test.y); 593 t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; 594 t2Step /= 2; 595 } 596 t2Step = 0.1; 597 while (!approximately_zero(t2Step)) { 598 xy_at_t(cubic2, t22, test.x, test.y); 599 t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; 600 t2Step /= 2; 601 } 602 SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, 603 t10, t1Seed, t12, t20, t2Seed, t22); 604 _Point p10 = xy_at_t(cubic1, t10); 605 _Point p1Seed = xy_at_t(cubic1, t1Seed); 606 _Point p12 = xy_at_t(cubic1, t12); 607 SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, 608 p10.x, p10.y, p1Seed.x, p1Seed.y, p12.x, p12.y); 609 _Point p20 = xy_at_t(cubic2, t20); 610 _Point p2Seed = xy_at_t(cubic2, t2Seed); 611 _Point p22 = xy_at_t(cubic2, t22); 612 SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, 613 p20.x, p20.y, p2Seed.x, p2Seed.y, p22.x, p22.y); 614} 615 616static void coincidentTest() { 617#if 0 618 Cubic cubic1 = {{0, 1}, {0, 2}, {1, 0}, {1, 0}}; 619 Cubic cubic2 = {{0, 1}, {0, 2}, {1, 0}, {6, 1}}; 620#endif 621} 622 623void CubicIntersection_Test() { 624 oneOffTests(); 625 coincidentTest(); 626 standardTestCases(); 627} 628