A object has a position and a speed vector. Usually only the position is used to check if two objects collide, this is problematic for very fast moving objects as it can happen that the object moves so fast that it is in front of the first object in the first collision check, and behind it in the second collision check.
Now there is also line based collision checks, in which you only check if the movement vector of each object intersects with the bounding-box of the other one. This can be seen as a expansion of a point. This only works though if the fast moving object is really small.
So my idea is, instead of expanding a point, why not expanding a rectangle? This results in a Hexagon.
Now, so far so good. But how do I actually check if two Hexagons of this kind intersect? Note that these are very specific Hexagon's.
Bonus Question: Is it possible to calculate where exactly (or rather after how much time) the collision happened? This could be very useful to detect what really happened, like where and with how much power and to simulate how they moved in the time between the collision and the end of the frame.
Answer
The solution is actually simpler than expected. The trick is to use Minkowski subtraction before your hexagon technique.
Here are your rectangles A and B, with their velocities vA and vB. Note that vA and vB aren't actually velocities, they are the distance traveled during one frame.
Now replace rectangle B with a point P, and rectangle A with rectangle C = A+(-B), which has dimensions the sum of the dimensions of A and B. The Minkowski addition properties state that collision between the point and the new rectangle occur if and only if collision between the original two rectangles occur:
But if rectangle C moves along vector vA, and point P moves along vector vB, a simple change of reference frame tells us it is the same as if rectangle C was still, and point P moved along vector vB-vA:
You can then use a simple box-segment intersection formula to tell where the collision occurs in the new reference frame.
The last step is to move back to the proper reference frame. Just divide the distance traveled by the point until the circled intersection by the length of vector vB-vA and you will get a value s such that 0 < s < 1. The collision happens at time s * T where T is the duration of your frame.
Comment by madshogo:
One HUGE advantage of this technique over the one in Mr Beast's own answer is that if there's no rotation, then the "Minkowski subtraction" A+(-B) can be computed once for all the subsequent timesteps!
So the only algorithm that takes time in all this (Minkowski sum, complexity O(mn) where m is the number of vertices in A and n the number of vertices in B) can be used only once, effectively making collision detection a constant-time problem!
Later, you can throw the sum away once you know for sure that A and B are in different parts of your scene (of your quadtree?) and won't collide anymore.
In contrast, Mr Beast's method requires quite a lot of computations at each time step.
Also, for axis-aligned rectangles, A+(-B) can be computed much more simply than by actually computing all the sums, vertex by vertex. Just expand A by adding the height of B to its height and the width of B to its width (one half on each side).
But all this only works if neither A nor B is rotating and if both are convex. If rotation there is or if you use concave shapes then you must use swept volumes/areas.
end of comment
No comments:
Post a Comment