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
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).
No comments:
Post a Comment