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 #include "SkDQuadImplicit.h" | 7 #include "SkDQuadImplicit.h" |
8 #include "SkIntersections.h" | 8 #include "SkIntersections.h" |
9 #include "SkPathOpsLine.h" | 9 #include "SkPathOpsLine.h" |
10 #include "SkQuarticRoot.h" | 10 #include "SkQuarticRoot.h" |
(...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
66 for (index = 0; index < count; ++index) { | 66 for (index = 0; index < count; ++index) { |
67 if (!approximately_zero_or_more(roots[index]) || !approximately_one_or_l
ess(roots[index])) { | 67 if (!approximately_zero_or_more(roots[index]) || !approximately_one_or_l
ess(roots[index])) { |
68 continue; | 68 continue; |
69 } | 69 } |
70 double t = 1 - roots[index]; | 70 double t = 1 - roots[index]; |
71 if (approximately_less_than_zero(t)) { | 71 if (approximately_less_than_zero(t)) { |
72 t = 0; | 72 t = 0; |
73 } else if (approximately_greater_than_one(t)) { | 73 } else if (approximately_greater_than_one(t)) { |
74 t = 1; | 74 t = 1; |
75 } | 75 } |
76 SkASSERT(t >= 0 && t <= 1); | |
77 valid[result++] = t; | 76 valid[result++] = t; |
78 } | 77 } |
79 return result; | 78 return result; |
80 } | 79 } |
81 | 80 |
82 static bool only_end_pts_in_common(const SkDQuad& q1, const SkDQuad& q2) { | 81 static bool only_end_pts_in_common(const SkDQuad& q1, const SkDQuad& q2) { |
83 // the idea here is to see at minimum do a quick reject by rotating all points | 82 // the idea here is to see at minimum do a quick reject by rotating all points |
84 // to either side of the line formed by connecting the endpoints | 83 // to either side of the line formed by connecting the endpoints |
85 // if the opposite curves points are on the line or on the other side, the | 84 // if the opposite curves points are on the line or on the other side, the |
86 // curves at most intersect at the endpoints | 85 // curves at most intersect at the endpoints |
(...skipping 149 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
236 | 235 |
237 static double flat_measure(const SkDQuad& q) { | 236 static double flat_measure(const SkDQuad& q) { |
238 SkDVector mid = q[1] - q[0]; | 237 SkDVector mid = q[1] - q[0]; |
239 SkDVector dxy = q[2] - q[0]; | 238 SkDVector dxy = q[2] - q[0]; |
240 double length = dxy.length(); // OPTIMIZE: get rid of sqrt | 239 double length = dxy.length(); // OPTIMIZE: get rid of sqrt |
241 return fabs(mid.cross(dxy) / length); | 240 return fabs(mid.cross(dxy) / length); |
242 } | 241 } |
243 | 242 |
244 // FIXME ? should this measure both and then use the quad that is the flattest a
s the line? | 243 // FIXME ? should this measure both and then use the quad that is the flattest a
s the line? |
245 static bool is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i)
{ | 244 static bool is_linear(const SkDQuad& q1, const SkDQuad& q2, SkIntersections* i)
{ |
246 if (i->flatMeasure()) { | 245 double measure = flat_measure(q1); |
247 // for backward compatibility, use the old method when called from cubic
s | 246 // OPTIMIZE: (get rid of sqrt) use approximately_zero |
248 // FIXME: figure out how to fix cubics when it calls the new path | 247 if (!approximately_zero_sqrt(measure)) { |
249 double measure = flat_measure(q1); | 248 return false; |
250 // OPTIMIZE: (get rid of sqrt) use approximately_zero | |
251 if (!approximately_zero_sqrt(measure)) { // approximately_zero_sqrt | |
252 return false; | |
253 } | |
254 } else { | |
255 if (!q1.isLinear(0, 2)) { | |
256 return false; | |
257 } | |
258 } | 249 } |
259 return is_linear_inner(q1, 0, 1, q2, 0, 1, i, NULL); | 250 return is_linear_inner(q1, 0, 1, q2, 0, 1, i, NULL); |
260 } | 251 } |
261 | 252 |
262 // FIXME: if flat measure is sufficiently large, then probably the quartic solut
ion failed | 253 // FIXME: if flat measure is sufficiently large, then probably the quartic solut
ion failed |
263 // avoid imprecision incurred with chopAt | 254 // avoid imprecision incurred with chopAt |
264 static void relaxed_is_linear(const SkDQuad* q1, double s1, double e1, const SkD
Quad* q2, | 255 static void relaxed_is_linear(const SkDQuad* q1, double s1, double e1, const SkD
Quad* q2, |
265 double s2, double e2, SkIntersections* i) { | 256 double s2, double e2, SkIntersections* i) { |
266 double m1 = flat_measure(*q1); | 257 double m1 = flat_measure(*q1); |
267 double m2 = flat_measure(*q2); | 258 double m2 = flat_measure(*q2); |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
307 int calcMask = ~0; | 298 int calcMask = ~0; |
308 do { | 299 do { |
309 if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed); | 300 if (calcMask & (1 << 1)) t1[1] = quad1.ptAtT(*t1Seed); |
310 if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed); | 301 if (calcMask & (1 << 4)) t2[1] = quad2.ptAtT(*t2Seed); |
311 if (t1[1].approximatelyEqual(t2[1])) { | 302 if (t1[1].approximatelyEqual(t2[1])) { |
312 *pt = t1[1]; | 303 *pt = t1[1]; |
313 #if ONE_OFF_DEBUG | 304 #if ONE_OFF_DEBUG |
314 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __
FUNCTION__, | 305 SkDebugf("%s t1=%1.9g t2=%1.9g (%1.9g,%1.9g) == (%1.9g,%1.9g)\n", __
FUNCTION__, |
315 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t2[1].fX, t2[1].fY); | 306 t1Seed, t2Seed, t1[1].fX, t1[1].fY, t2[1].fX, t2[1].fY); |
316 #endif | 307 #endif |
317 if (*t1Seed < 0) { | |
318 *t1Seed = 0; | |
319 } else if (*t1Seed > 1) { | |
320 *t1Seed = 1; | |
321 } | |
322 if (*t2Seed < 0) { | |
323 *t2Seed = 0; | |
324 } else if (*t2Seed > 1) { | |
325 *t2Seed = 1; | |
326 } | |
327 return true; | 308 return true; |
328 } | 309 } |
329 if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(SkTMax(0., *t1Seed - tStep)
); | 310 if (calcMask & (1 << 0)) t1[0] = quad1.ptAtT(SkTMax(0., *t1Seed - tStep)
); |
330 if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(SkTMin(1., *t1Seed + tStep)
); | 311 if (calcMask & (1 << 2)) t1[2] = quad1.ptAtT(SkTMin(1., *t1Seed + tStep)
); |
331 if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(SkTMax(0., *t2Seed - tStep)
); | 312 if (calcMask & (1 << 3)) t2[0] = quad2.ptAtT(SkTMax(0., *t2Seed - tStep)
); |
332 if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(SkTMin(1., *t2Seed + tStep)
); | 313 if (calcMask & (1 << 5)) t2[2] = quad2.ptAtT(SkTMin(1., *t2Seed + tStep)
); |
333 double dist[3][3]; | 314 double dist[3][3]; |
334 // OPTIMIZE: using calcMask value permits skipping some distance calcuat
ions | 315 // OPTIMIZE: using calcMask value permits skipping some distance calcuat
ions |
335 // if prior loop's results are moved to correct slot for reuse | 316 // if prior loop's results are moved to correct slot for reuse |
336 dist[1][1] = t1[1].distanceSquared(t2[1]); | 317 dist[1][1] = t1[1].distanceSquared(t2[1]); |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
410 if (swap) { | 391 if (swap) { |
411 i->insert(testT, impTs[0][index], tmpLine[0]); | 392 i->insert(testT, impTs[0][index], tmpLine[0]); |
412 } else { | 393 } else { |
413 i->insert(impTs[0][index], testT, tmpLine[0]); | 394 i->insert(impTs[0][index], testT, tmpLine[0]); |
414 } | 395 } |
415 } | 396 } |
416 } | 397 } |
417 | 398 |
418 int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { | 399 int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) { |
419 fMax = 4; | 400 fMax = 4; |
420 bool exactMatch = false; | |
421 // if the quads share an end point, check to see if they overlap | 401 // if the quads share an end point, check to see if they overlap |
422 for (int i1 = 0; i1 < 3; i1 += 2) { | 402 for (int i1 = 0; i1 < 3; i1 += 2) { |
423 for (int i2 = 0; i2 < 3; i2 += 2) { | 403 for (int i2 = 0; i2 < 3; i2 += 2) { |
424 if (q1[i1].asSkPoint() == q2[i2].asSkPoint()) { | 404 if (q1[i1].asSkPoint() == q2[i2].asSkPoint()) { |
425 insert(i1 >> 1, i2 >> 1, q1[i1]); | 405 insert(i1 >> 1, i2 >> 1, q1[i1]); |
426 exactMatch = true; | |
427 } | 406 } |
428 } | 407 } |
429 } | 408 } |
430 SkASSERT(fUsed < 3); | 409 SkASSERT(fUsed < 3); |
431 if (only_end_pts_in_common(q1, q2)) { | 410 if (only_end_pts_in_common(q1, q2)) { |
432 return fUsed; | 411 return fUsed; |
433 } | 412 } |
434 if (only_end_pts_in_common(q2, q1)) { | 413 if (only_end_pts_in_common(q2, q1)) { |
435 return fUsed; | 414 return fUsed; |
436 } | 415 } |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
483 SkDQuadImplicit i1(q1); | 462 SkDQuadImplicit i1(q1); |
484 SkDQuadImplicit i2(q2); | 463 SkDQuadImplicit i2(q2); |
485 int index; | 464 int index; |
486 bool flip1 = q1[2] == q2[0]; | 465 bool flip1 = q1[2] == q2[0]; |
487 bool flip2 = q1[0] == q2[2]; | 466 bool flip2 = q1[0] == q2[2]; |
488 bool useCubic = q1[0] == q2[0]; | 467 bool useCubic = q1[0] == q2[0]; |
489 double roots1[4]; | 468 double roots1[4]; |
490 int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); | 469 int rootCount = findRoots(i2, q1, roots1, useCubic, flip1, 0); |
491 // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 | 470 // OPTIMIZATION: could short circuit here if all roots are < 0 or > 1 |
492 double roots1Copy[4]; | 471 double roots1Copy[4]; |
493 SkDEBUGCODE(sk_bzero(roots1Copy, sizeof(roots1Copy))); | |
494 int r1Count = addValidRoots(roots1, rootCount, roots1Copy); | 472 int r1Count = addValidRoots(roots1, rootCount, roots1Copy); |
495 SkDPoint pts1[4]; | 473 SkDPoint pts1[4]; |
496 for (index = 0; index < r1Count; ++index) { | 474 for (index = 0; index < r1Count; ++index) { |
497 pts1[index] = q1.ptAtT(roots1Copy[index]); | 475 pts1[index] = q1.ptAtT(roots1Copy[index]); |
498 } | 476 } |
499 double roots2[4]; | 477 double roots2[4]; |
500 int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); | 478 int rootCount2 = findRoots(i1, q2, roots2, useCubic, flip2, 0); |
501 double roots2Copy[4]; | 479 double roots2Copy[4]; |
502 int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); | 480 int r2Count = addValidRoots(roots2, rootCount2, roots2Copy); |
503 SkDPoint pts2[4]; | 481 SkDPoint pts2[4]; |
504 for (index = 0; index < r2Count; ++index) { | 482 for (index = 0; index < r2Count; ++index) { |
505 pts2[index] = q2.ptAtT(roots2Copy[index]); | 483 pts2[index] = q2.ptAtT(roots2Copy[index]); |
506 } | 484 } |
507 bool triedBinary = false; | |
508 if (r1Count == r2Count && r1Count <= 1) { | 485 if (r1Count == r2Count && r1Count <= 1) { |
509 if (r1Count == 1 && used() == 0) { | 486 if (r1Count == 1 && used() == 0) { |
510 if (pts1[0].approximatelyEqual(pts2[0])) { | 487 if (pts1[0].approximatelyEqual(pts2[0])) { |
511 insert(roots1Copy[0], roots2Copy[0], pts1[0]); | 488 insert(roots1Copy[0], roots2Copy[0], pts1[0]); |
512 } else { | 489 } else { |
513 // find intersection by chasing t | 490 // find intersection by chasing t |
514 triedBinary = true; | |
515 if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) { | 491 if (binary_search(q1, q2, roots1Copy, roots2Copy, pts1)) { |
516 insert(roots1Copy[0], roots2Copy[0], pts1[0]); | 492 insert(roots1Copy[0], roots2Copy[0], pts1[0]); |
517 } | 493 } |
518 } | 494 } |
519 } | 495 } |
520 return fUsed; | 496 return fUsed; |
521 } | 497 } |
522 int closest[4]; | 498 int closest[4]; |
523 double dist[4]; | 499 double dist[4]; |
524 bool foundSomething = false; | 500 bool foundSomething = false; |
(...skipping 20 matching lines...) Expand all Loading... |
545 closest[outer] = -1; | 521 closest[outer] = -1; |
546 } | 522 } |
547 dist[index] = distance; | 523 dist[index] = distance; |
548 closest[index] = ndex2; | 524 closest[index] = ndex2; |
549 foundSomething = true; | 525 foundSomething = true; |
550 next: | 526 next: |
551 ; | 527 ; |
552 } | 528 } |
553 } | 529 } |
554 if (r1Count && r2Count && !foundSomething) { | 530 if (r1Count && r2Count && !foundSomething) { |
555 if (exactMatch) { | |
556 SkASSERT(fUsed > 0); | |
557 return fUsed; | |
558 } | |
559 relaxed_is_linear(&q1, 0, 1, &q2, 0, 1, this); | 531 relaxed_is_linear(&q1, 0, 1, &q2, 0, 1, this); |
560 if (fUsed) { | |
561 return fUsed; | |
562 } | |
563 // maybe the curves are nearly coincident | |
564 if (!triedBinary && binary_search(q1, q2, roots1Copy, roots2Copy, pts1))
{ | |
565 insert(roots1Copy[0], roots2Copy[0], pts1[0]); | |
566 } | |
567 return fUsed; | 532 return fUsed; |
568 } | 533 } |
569 int used = 0; | 534 int used = 0; |
570 do { | 535 do { |
571 double lowest = DBL_MAX; | 536 double lowest = DBL_MAX; |
572 int lowestIndex = -1; | 537 int lowestIndex = -1; |
573 for (index = 0; index < r1Count; ++index) { | 538 for (index = 0; index < r1Count; ++index) { |
574 if (closest[index] < 0) { | 539 if (closest[index] < 0) { |
575 continue; | 540 continue; |
576 } | 541 } |
577 if (roots1Copy[index] < lowest) { | 542 if (roots1Copy[index] < lowest) { |
578 lowestIndex = index; | 543 lowestIndex = index; |
579 lowest = roots1Copy[index]; | 544 lowest = roots1Copy[index]; |
580 } | 545 } |
581 } | 546 } |
582 if (lowestIndex < 0) { | 547 if (lowestIndex < 0) { |
583 break; | 548 break; |
584 } | 549 } |
585 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], | 550 insert(roots1Copy[lowestIndex], roots2Copy[closest[lowestIndex]], |
586 pts1[lowestIndex]); | 551 pts1[lowestIndex]); |
587 closest[lowestIndex] = -1; | 552 closest[lowestIndex] = -1; |
588 } while (++used < r1Count); | 553 } while (++used < r1Count); |
589 return fUsed; | 554 return fUsed; |
590 } | 555 } |
591 | |
592 void SkIntersections::alignQuadPts(const SkPoint q1[3], const SkPoint q2[3]) { | |
593 for (int index = 0; index < used(); ++index) { | |
594 const SkPoint result = pt(index).asSkPoint(); | |
595 if (q1[0] == result || q1[2] == result || q2[0] == result || q2[2] == re
sult) { | |
596 continue; | |
597 } | |
598 if (SkDPoint::ApproximatelyEqual(q1[0], result)) { | |
599 fPt[index].set(q1[0]); | |
600 // SkASSERT(way_roughly_zero(fT[0][index])); // this value can be bi
gger than way rough | |
601 fT[0][index] = 0; | |
602 } else if (SkDPoint::ApproximatelyEqual(q1[2], result)) { | |
603 fPt[index].set(q1[2]); | |
604 // SkASSERT(way_roughly_equal(fT[0][index], 1)); | |
605 fT[0][index] = 1; | |
606 } | |
607 if (SkDPoint::ApproximatelyEqual(q2[0], result)) { | |
608 fPt[index].set(q2[0]); | |
609 // SkASSERT(way_roughly_zero(fT[1][index])); | |
610 fT[1][index] = 0; | |
611 } else if (SkDPoint::ApproximatelyEqual(q2[2], result)) { | |
612 fPt[index].set(q2[2]); | |
613 // SkASSERT(way_roughly_equal(fT[1][index], 1)); | |
614 fT[1][index] = 1; | |
615 } | |
616 } | |
617 } | |
OLD | NEW |