Continuous Physics Engine's Collision Detection Techniques

6
votes

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).

2
algorithm2dcollision-detectionphysicssimulation
assert( Make_a_list == not_constructive_close) - dmckee --- ex-moderator kitten
If you don't already know it I would recommend Real-time Collision Detection as an excellent resource. - Bart
how are you implementing your dynamics, and do you do that in a continuous way? if your system is linear, then you should be able to simply solve for the next collision time using the state transition matrix, the collision conditions and a root-finder (like Newton's method). if your system is not linear then you're going to have to solve the dynamics using a time stepper anyway, unless you have extra structure, in which case you should probably mention that. - vlsd
@VladSeghete What do you mean by implementing my dynamics in a continuous way? My system is linear to, so I do solve for collision times between Bounding Circles with a root finder, but what my issue currently is is how to weed out the tests between Bounding Circles that might not even be heading towards each other. Is there some way to organize my collision space with a continous analog of the discrete quad-tree method? Or something like it? - Griffin
If objects can rotate, I would say your system is not linear. In other words, the trajectory of a vertex is generally not a straight line. - phkahler

2 Answers

6
votes

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.

1
votes

I am going to assume you want things like gravity or other conservative forces in your simulation. If that's the case the trajectories of your objects are most likely not going to be lines, in which case, just like Adrian pointed out, the math will be somewhat harder. I can't think of a way to avoid checking all possible combinations of curves for collisions, but you can calculate the minimum distance between two curves rather easily, as long as both are solutions to linear systems (or, in general, if you have a closed form solution for the curves). If you know that x1(t) = f(t) and x2(t) = g(t) then what you'll want to do is calculate the distance ||x1(t) - x2(t)|| and set its derivative to zero. This should be an expression that depends on f(t), g(t) and their derivatives and will give you a time tmin (or maybe a few possible ones) at which you then evaluate the distance and check to see if it is greater or smaller than r1+r2 --- the sum of the radii of the two bounding circles. If it is smaller, then you have a potential collision at that time so you run the narrow phase algorithm.