Continuous Physics Engine's Collision Detection Techniques

Question

I'm working on a purely continuous physics engine, and I need to choose algorithms for broad and narrow phase collision detection. "Purely continuous" means I never do intersection tests, but instead want to find ways to catch every collision before it happens, and put each into "planned collisions" stack that is ordered by TOI.

Broad Phase The only continuous broad-phase method I can think of is encasing each body in a circle and testing if each circle will ever overlap another. This seems horribly inefficient however, and lacks any culling.

I have no idea what continuous analogs might exist for today's discrete collision culling methods such as quad-trees either. How might I go about preventing inappropriate and pointless broad test's such as a discrete engine does?

Narrow Phase
I've managed to adapt the narrow SAT to a continuous check rather than discrete, but I'm sure there's other better algorithms out there in papers or sites you guys might have come across.
What various fast or accurate algorithm's do you suggest I use and what are the advantages / disatvantages of each?

Final Note:
I say techniques and not algorithms because I have not yet decided on how I will store different polygons which might be concave, convex, round, or even have holes. I plan to make a decision on this based on what the algorithm requires (for instance if I choose an algorithm that breaks down a polygon into triangles or convex shapes I will simply store the polygon data in this form).

Answer 1

You said circles, so I'm assuming you have 2D objects. You could extend your 2D object (or their bounding shapes) into 3D by adding a time dimension, and then you can use the normal techniques for checking for static collisions among a set of 3D objects.

For example, if you have a circle in (x, y) moving to the right (+x) with constant velocity, then, when you extend that with a time dimension, you have a diagonal cylinder in (x, y, t). By doing intersections between these 3D objects (just treat time as z), you can see if two objects will ever intersect. If point P is a point of intersection, then you know the time of that intersection simply by looking at P.t.

This generalizes into higher dimensions, too, though the math gets hard (for me anyway).

The collision detection might be tricky if objects have complex paths. For example, if your circle is influenced by gravity, then the extruded space-time object is a parabolic sphere sweep rather than a simple cylinder. You could pad the bounding objects a bit and use linear approximations over shorter periods of time and iterate, but I'm not sure if that violates what you mean by continuous.