12
\$\begingroup\$

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): Rectangle Generated By Movement

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Christer Ericson has some info on swept sphere/sphere testing in his orange book. There are quite a few ways to solve the problem, but I imagine you'll like interval halving the most. It's good to try to derive this stuff on your own, but you really should just go look at the orange book and compare in order to get a really good detection routine and learn more. \$\endgroup\$ – RandyGaul Sep 18 '13 at 2:31
  • \$\begingroup\$ Sounds like you already have a plan.. give it a try and see how it works? \$\endgroup\$ – Trevor Powell Sep 18 '13 at 2:36
  • \$\begingroup\$ I think the "usual" way is to have a small maximum interval on your delta time. So if you have 1000ms elapse, just simulate 10x 100ms (or 100x 10ms, or 33x 30ms, or something similar). \$\endgroup\$ – ashes999 Sep 18 '13 at 3:05
  • \$\begingroup\$ @RandyGaul I looked over the algorithm described on page 215-218, especially page 218 (Google preview). It is quite elegant, although I have not yet thought through all of its implications, strengths, and weaknesses. Will it be much faster than mine? If so, what part of my algorithm is slow compared to Ericson's recursion? Is the equation in step 3 going to be too slow? The recursion makes me hesitate, since some objects may be moving VERY fast, and therefore a great deal of recursion might be necessary in some cases. (Also, OUCH, $70 for that book...) \$\endgroup\$ – MindSeeker Sep 18 '13 at 19:01
  • 1
    \$\begingroup\$ @MindSeeker I don't have time to look over your derivation, but I am positive that the algorithms in Ericson's book, any of them, will work really well and probably be faster and more robust than your stuff. You can find PDF versions online for free, if you want to demo the other pages. Also if you're going to be doing collision detection often, the orange book is a staple. \$\endgroup\$ – RandyGaul Sep 18 '13 at 22:27
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the awesome input! Breaking your answer down so I can ask questions about it: ""Sweep" the object from its start to the end." So far I'm tracking; definitely an improvement over my box method. I'll feed these shapes to by quadtree and then check for more exact collisions. "You can calculate when the collision had occurred." Haha easier said than done :) Are you recommending that I stick with my equation from step 3 for the step? Or is there a better way? This is the really critical part. \$\endgroup\$ – MindSeeker Sep 18 '13 at 19:08
  • \$\begingroup\$ [continued] "Another option..." I thought about that option, but unfortunately the speeds are too high. See my comment response to @ashes999 and edit above for more info. Thank you very much for your help! \$\endgroup\$ – MindSeeker Sep 18 '13 at 19:13
  • \$\begingroup\$ The only way to know about performance is to try it, measure it, and see. I've seen some "obviously" inefficient code massively out-perform the efficient versions before, usually for quite non-intuitive reasons. Don't ask what is fastest; test and find out. \$\endgroup\$ – Sean Middleditch Sep 18 '13 at 19:20
  • \$\begingroup\$ Fair enough, I'll go ahead and try my method, modified as you suggested. My question in the comment still stands though: "You can calculate when the collision had occurred." Are you recommending that I stick with my equation from step 3 for that step? Or is there a better way? This is the most difficult part of the problem I think. Swept volumes, if I'm understanding them correctly, can tell me that the objects' paths intersect, but cannot tell me if/when the objects themselves collide. \$\endgroup\$ – MindSeeker Sep 18 '13 at 19:29
  • 1
    \$\begingroup\$ @MindSeeker Swept geometry is raycasting except you are casting the shape instead of a ray. So the method should look similar to using ray casting with "rays" for all fast moving objects instead of just one ray versus a stationary object. After you determine potential collisions from the "rays" you need to solve for time on both "rays" to make sure they were at the same spot at the same time. \$\endgroup\$ – stonemetal Sep 19 '13 at 14:57
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.