| 483 | } |
| 484 | |
| 485 | static void |
| 486 | findIntersection(const BezierCPs& cps, |
| 487 | double time, |
| 488 | const Point& p, |
| 489 | const Point& q, |
| 490 | BezierCPPtr* newPoint, |
| 491 | int* before) |
| 492 | { |
| 493 | double fuzz = 1000. * std::numeric_limits<double>::epsilon(); |
| 494 | double fuzz2 = fuzz * fuzz; |
| 495 | double dx = q.x - p.x; |
| 496 | double dy = q.y - p.y; |
| 497 | double det = p.y * q.x - p.x * q.y; |
| 498 | std::vector<std::pair<BezierCPPtr, std::pair<BezierCPs::const_iterator, BezierCPs::const_iterator> > > intersections; |
| 499 | BezierCPs::const_iterator s1 = cps.begin(); |
| 500 | BezierCPs::const_iterator s2 = cps.begin(); |
| 501 | |
| 502 | ++s2; |
| 503 | int index = 0; |
| 504 | for (; s1 != cps.end(); ++s1, ++s2, ++index) { |
| 505 | if ( s2 == cps.end() ) { |
| 506 | s2 = cps.begin(); |
| 507 | } |
| 508 | |
| 509 | Point z0, z1, c0, c1; |
| 510 | (*s1)->getPositionAtTime(false, time, ViewIdx(0), &z0.x, &z0.y); |
| 511 | (*s1)->getRightBezierPointAtTime(false, time, ViewIdx(0), &c0.x, &c0.y); |
| 512 | (*s2)->getPositionAtTime(false, time, ViewIdx(0), &z1.x, &z1.y); |
| 513 | (*s2)->getLeftBezierPointAtTime(false, time, ViewIdx(0), &c1.x, &c1.y); |
| 514 | |
| 515 | |
| 516 | Point t3, t2, t1; |
| 517 | t3.x = z1.x - z0.x + 3. * (c0.x - c1.x); |
| 518 | t3.y = z1.y - z0.y + 3. * (c0.y - c1.y); |
| 519 | |
| 520 | t2.x = 3. * (z0.x + c1.x) - 6. * c0.x; |
| 521 | t2.y = 3. * (z0.y + c1.y) - 6. * c0.y; |
| 522 | |
| 523 | t1.x = 3. * (c0.x - z0.x); |
| 524 | t1.y = 3. * (c0.y - z0.y); |
| 525 | |
| 526 | double a = dy * t3.x - dx * t3.y; |
| 527 | double b = dy * t2.x - dx * t2.y; |
| 528 | double c = dy * t1.x - dx * t1.y; |
| 529 | double d = dy * z0.x - dx * z0.y + det; |
| 530 | std::vector<double> roots; |
| 531 | if ( std::max(std::max(std::max(a * a, b * b), c * c), d * d) > |
| 532 | fuzz2 * std::max(std::max(std::max(z0.x * z0.x + z0.y * z0.y, z1.x * z1.x + z1.y * z1.y), |
| 533 | c0.x * c0.x + c0.y * c0.y), |
| 534 | c1.x * c1.x + c1.y * c1.y) ) { |
| 535 | double r[3]; |
| 536 | int order[3]; |
| 537 | int nsols = Interpolation::solveCubic(d, c, b, a, r, order); |
| 538 | for (int i = 0; i < nsols; ++i) { |
| 539 | roots.push_back(r[i]); |
| 540 | } |
| 541 | } else { |
| 542 | roots.push_back(0); |
no test coverage detected