0
\$\begingroup\$

I have been using the method here to find the intersection between a line and a curve but, I am not too sure how I would go about solving the time for when two objects moving along their respective tracks would collide. Both objects have a constant speed and radius.

enter image description here

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Three useful facts we can use here:

  • We can use De Casteljau's algorithm to split a Bézier curve into two smaller Bézier curves of the same degree. This tends to gradually straighten the child curves, as they cover less and less of the bends in the original curve.

  • A Bézier is that the path is always fully contained in the convex hull of its control points. For the cubic case, that's a quadrilateral, or just two triangles.

  • A disc somewhere inside that quadrilateral can only collide with the disc moving on a straight line only if the quadrilateral itself overlaps a capsule shape.

    The capsule's radius is equal to the sum of the two discs' radii, and its start/end points are the disc's position on the straight line path at the start and end of the time interval it takes to traverse the curve segment that quad contains.

    (You could check this by doing two point-in-quad checks and a circle cast if both come up negative - two circle casts if you want both entry and exit times to narrow your search window)

We can use this to quickly narrow down the range of possible collisions.

First, we check this capsule against the quad containing the entire curve. If there's no overlap, we know for sure that we miss.

Then we sub-divide the curve. There are probably principled ways to do this, but they run into edge cases, so for a simple first pass I'd suggest dividing into 3-10 even time segments between the earliest and latest overlap times.

Repeat the overlap test with each segment, using a smaller capsule - accounting for the fact that the disc on the straight line trajectory crosses only a part of its path during each of these time segments.

You can eliminate any segment that does not overlap, then further subdivide those that do. You can binary search for the intersection, pruning any quads that have no overlap, and recursively subdividing those that do. Your recursion bottoms-out when the time interval is small enough or the quad is flat enough to approximate as a straight line segment: then you can switch to a conventional swept disc collision test to get a closed-form solution for the time and location of the collision.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .