Small, High-Speed Object Collisions: Avoiding Tunneling

Question

EDIT/UPDATE: My biggest question right now is whether step 3's "t=..." equation is a good idea or there a better way to do it. Most other issues have been partially or fully addressed, but no comments or answers have really touched on this issue. Again, an analytic solution is probably required, the velocities and distances are too large, and the objects are too small, for any iterative/recursive solution (a few are suggested below in the comments) that I can think of (although if there is a special iterative/recursive solution that will handle these kinds of situations fine then I'm definitely open to it). Thank you very much for your help so far, you all are awesome and I really appreciate your thoughts and help!

I'm trying to detect collisions between small, high-speed objects. This is a situation where tunneling may occur very easily, even at relatively low speeds.

Ray casting will not work, since this is detecting a collision between two high-speed objects, not between one object and a stationary wall. (Unless if I'm misunderstanding ray casting?) Performance is VERY MUCH a consideration; if at all possible, I want to avoid a large performance hit. I already have a functional and very effective quadtree (http://en.wikipedia.org/wiki/Quadtree) implemented, so I shall modify and use it as described below.

Edit: Reducing the time interval will not work. The speeds are too high for this solution, which means that the performance hits would be too great, while still missing the vast majority of the tunneling collisions. (For example, I might have an object with a size of about 1 unit going at a speed measured in millions of units per time interval...)

PROPOSED SOLUTION:

Step 1:

Create a box around each object's movement, then feed those boxes into the quadtree to generate an initial list of possible collisions. See the following image (this image shows a circle object moving from one position to another, and the movement generating a rectangle, which will be fed into the quadtree):

Step 2: (might want to skip this step?)

Go through the list of possible collisions generated by the quadtree. See if the rectangles intersect in each possible collision. If so, proceed to step 3.

EDIT: Below, Sean Middleditch suggested using swept volumes/the intersection of capsules (if the objects are circles). That leaves three options: 1) skip step 2 entirely. 2) Do step 2 my way. 3) Do it Sean's way. Sean's way will be more computationally expensive than my box idea, however it will weed out more false positives than my way, preventing them from getting to the final step.

Can anyone speak from experience as to which of these 3 choices is best? (I intend to use this physics engine for a few different thing, so I am looking for the "generally best" solution that works the fastest in the widest variety of situations, not just one specific test case in which I can easily measure which solution is fastest).

Step 3:

Use the t = equation below, if the discriminant (i.e. the part under the square root) is negative or 0, no collision, if positive then use the t value as the time of collision (after which it is easy to adjust positions accordingly...if both objects continue to exist after the collision). Equation:

t = (-1/2 sqrt((2 a w-2 a x+2 b y-2 b z-2 c w+2 c x-2 d y+2 d z)^2-4 (w^2-2 w x+x^2+y^2-2 y z+z^2) (a^2-2 a c+b^2-2 b d+c^2+d^2-r^2-2 r s-s^2))-a w+a x-b y+b z+c w-c x+d y-d z)/(w^2-2 w x+x^2+y^2-2 y z+z^2).

Where (1 and 2 are used to denote objects 1 and 2):

t is a negative time value between 0 and -1, where 0 is the current frame, and -1 is the previous frame;

a = x position 1;

b = y position 1;

c = x position 2;

d = y position 2;

w = x velocity 1;

x = x velocity 2;

y = y velocity 1;

z = y velocity 2;

r = radius 1;

s = radius 2;

Derivation: (^2 means squared)

Take parametric equations (for example, newxpos1 = a + tw) for the objects' motions and plug them into the distance formula (squaring both sides): distance formula squared = (a + tw - (c + tx))^2 + (b + ty - (d + t*z))^2. Remember, t is going to be negative. To find the time of collision for two circular objects we set the left side equal to (r+s)^2. Solving for t using the quadratic equation (and a great deal of very tedious algebra), we get the above "t=..." equation.

My Questions:

1) Is this a good way to do it? Will it work at all? Am I going to run into any unforeseen issues? (I know I'm going to have trouble when more than 2 objects at a time collide, but I don't care since the only case that I really object to that is when they have low relative velocities (if the relative velocities are high then the "goofy" solution the algorithm gives will be "good enough", and it will be impossible for a human to see the error), and if more than 2 collide with low relative velocities in the same time-step, most solutions will be close enough anyway, since I don't plan on having a bunch of inelastic collisions)

2) Will my performance suffer a lot? I don't think it will, but if it will, is there a better way to do it?

3) Should I skip step 2 and go straight from step 1 to 3? Obviously step 2 is not vital, but it might help performance (OR it might cost more CPU time than it saves).

All other comments, suggestions, or criticism is very welcome. Thank you for your help!

Answer 1

You have essentially create a somewhat over-enthusiastic version of swept volumes.

Take the object's two positions. "Sweep" the object from its start to the end. For a sphere, this would create a capsule. For a box, this would create a hexagon (or a longer box is the movement is along a single axis). For general convex polygons, this would create a different convex polygon.

You can now do intersection tests (including quadtree queries) using this swept volume. You can calculate when the collision had occurred, roll forward the simulation from the starting time to the collision time, and repeat.

Another option, somewhat simpler, is to do what @ashes999 stated and to simply use a smaller time interval or smaller speeds. There is an ideal maximum speed derived from the interval in which no object can move farther than its narrowest side in a single physics interation. For particularly small or particularly fast objects you may not be able to find a reasonably small interval that performs well.

See Real-Time Collision Detection for one of the better introductory/intermediary books on the topic of detecting collisions.

Answer 2

The algorithm proposed in the question works great: it is fast and is completely accurate, even when the objects are going at extreme speeds. I have a quadtree implemented, so after feeding the boxes from step 1 into the quadtree, I found step 2 to be unnecessary: my program was running almost as fast as before.

I've been using this algorithm for a couple of months now, and it seems to be perfectly accurate in determining t, the time of collision. Since there seems to be nothing on the web that is better, I highly recommend using this one. (Some of the answers in the other answers and comments above are great, but they either don't quite meet the needs as stated by the question or else the author was very ambiguous about something and never came back to answer when questioned about the ambiguity).

Answer 3

I do not have enough reputation yet to comment, but I'd just like to add that using what Sean Middleditch mentioned above makes it possible to calculate your "t". At least if I understood his answer and you question correctly.

Here is a link to an awesome answer by sam hocevar that provides the best explanation about it I have ever found (he drew pictures too, hurray!)

https://gamedev.stackexchange.com/a/55991/112940

If that is faster than your own method I cannot say, but he sure gives you everything you need in order to implement it and compare with yours.

Just to avoid leaving a "link only answer", I will provide a quick summup of his idea:

1. calculate the Minkowski Difference between the two bounding boxes
2. using the relative velocity between then, cast a ray/line segment from the origin to the box created by the Minkowski Difference in order to get the intersection point
3. If the ray hits, divide the distance your ray travaled by the length of the vector representing the relative velocity and you will have your "t"
4. click on the link I provided above and see sam beautiful explanation of all this, with lots of pictures. It is awesome.