OLD | NEW |
1 // Another approach is to start with the implicit form of one curve and solve | 1 // Another approach is to start with the implicit form of one curve and solve |
2 // (seek implicit coefficients in QuadraticParameter.cpp | 2 // (seek implicit coefficients in QuadraticParameter.cpp |
3 // by substituting in the parametric form of the other. | 3 // by substituting in the parametric form of the other. |
4 // The downside of this approach is that early rejects are difficult to come by. | 4 // The downside of this approach is that early rejects are difficult to come by. |
5 // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormu
la.html#step | 5 // http://planetmath.org/encyclopedia/GaloisTheoreticDerivationOfTheQuarticFormu
la.html#step |
6 | 6 |
7 | 7 |
8 #include "SkDQuadImplicit.h" | 8 #include "SkDQuadImplicit.h" |
9 #include "SkIntersections.h" | 9 #include "SkIntersections.h" |
10 #include "SkPathOpsLine.h" | 10 #include "SkPathOpsLine.h" |
(...skipping 283 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
294 double tStep = ROUGH_EPSILON; | 294 double tStep = ROUGH_EPSILON; |
295 SkDPoint t1[3], t2[3]; | 295 SkDPoint t1[3], t2[3]; |
296 int calcMask = ~0; | 296 int calcMask = ~0; |
297 do { | 297 do { |
298 if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed); | 298 if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed); |
299 if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed); | 299 if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed); |
300 if (t1[1].approximatelyEqual(t2[1])) { | 300 if (t1[1].approximatelyEqual(t2[1])) { |
301 *pt = t1[1]; | 301 *pt = t1[1]; |
302 #if ONE_OFF_DEBUG | 302 #if ONE_OFF_DEBUG |
303 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __
FUNCTION__, | 303 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __
FUNCTION__, |
304 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t1[2].fX, t1[2].fY); | 304 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t2[1].fX, t2[1].fY); |
305 #endif | 305 #endif |
306 return true; | 306 return true; |
307 } | 307 } |
308 if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(*t1Seed - tStep); | 308 if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(*t1Seed - tStep); |
309 if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(*t1Seed + tStep); | 309 if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(*t1Seed + tStep); |
310 if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(*t2Seed - tStep); | 310 if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(*t2Seed - tStep); |
311 if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(*t2Seed + tStep); | 311 if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(*t2Seed + tStep); |
312 double dist[3][3]; | 312 double dist[3][3]; |
313 // OPTIMIZE: using calcMask value permits skipping some distance calcuat
ions | 313 // OPTIMIZE: using calcMask value permits skipping some distance calcuat
ions |
314 // if prior loop's results are moved to correct slot for reuse | 314 // if prior loop's results are moved to correct slot for reuse |
(...skipping 168 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
483 } | 483 } |
484 double roots2[4]; | 484 double roots2[4]; |
485 int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); | 485 int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); |
486 double roots2Copy[4]; | 486 double roots2Copy[4]; |
487 int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); | 487 int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); |
488 SkDPoint pts2[4]; | 488 SkDPoint pts2[4]; |
489 for (index = 0; index < r2Count; ++index) { | 489 for (index = 0; index < r2Count; ++index) { |
490 pts2[index] = q2.ptAtT(roots2Copy[index]); | 490 pts2[index] = q2.ptAtT(roots2Copy[index]); |
491 } | 491 } |
492 if (r1Count == r2Count && r1Count <= 1) { | 492 if (r1Count == r2Count && r1Count <= 1) { |
493 if (r1Count == 1) { | 493 if (r1Count == 1 && used() == 0) { |
494 if (pts1[0].approximatelyEqual(pts2[0])) { | 494 if (pts1[0].approximatelyEqual(pts2[0])) { |
495 insert(roots1Copy[0], roots2Copy[0], pts1[0]); | 495 insert(roots1Copy[0], roots2Copy[0], pts1[0]); |
496 } else if (pts1[0].moreRoughlyEqual(pts2[0])) { | 496 } else if (pts1[0].moreRoughlyEqual(pts2[0])) { |
497 // experiment: try to find intersection by chasing t | 497 // experiment: try to find intersection by chasing t |
498 rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); | |
499 (void) addValidRoots(roots1, rootCount, roots1Copy); | |
500 rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); | |
501 (void) addValidRoots(roots2, rootCount2, roots2Copy); | |
502 if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) { | 498 if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) { |
503 insert(roots1Copy[0], roots2Copy[0], pts1[0]); | 499 insert(roots1Copy[0], roots2Copy[0], pts1[0]); |
504 } | 500 } |
505 } | 501 } |
506 } | 502 } |
507 return fUsed; | 503 return fUsed; |
508 } | 504 } |
509 int closest[4]; | 505 int closest[4]; |
510 double dist[4]; | 506 double dist[4]; |
511 bool foundSomething = false; | 507 bool foundSomething = false; |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
557 } | 553 } |
558 if (lowestIndex < 0) { | 554 if (lowestIndex < 0) { |
559 break; | 555 break; |
560 } | 556 } |
561 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], | 557 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], |
562 pts1[lowestIndex]); | 558 pts1[lowestIndex]); |
563 closest[lowestIndex] = -1; | 559 closest[lowestIndex] = -1; |
564 } while (++used < r1Count); | 560 } while (++used < r1Count); |
565 return fUsed; | 561 return fUsed; |
566 } | 562 } |
OLD | NEW |