Original Post
Today I thought up an algorithm that I haven''t seen before for doing basic collision testing. Basically it solves the problem of a sphere moving so fast that it isn''t properly tested on another sphere and it requires almost no slow operations (it requires 1 square root; everything else in part 3 (the new part of the algorithm) is done in 7 operations which are vector additions, subtractions, scalar multiplications, or dot products). That seems pretty good to me, but I don''t know all the algorithms out there. I''m almost 100% sure it works in every possible collision case. I will use the following terms in describing the two hypothetical objects:
Potential Collider - The object that is having its movement processed and is checking other objects to see if they would hit it if it were to move to its destination.
Target - The current object being tested for collision with the potential collider.
Position vector - Position vector of the center of a sphere.
Offset vector - The vector added to the current position vector to obtain the new position.
Anyway, the first two steps of the algorithm are the same thing that everyone does already. Part 3 is the new part.
For each possible colliding object:
1.) See if the potential collider is even traveling in the direction of the target in the first place (simple dot product abort test). If it is, then proceed.
2.) Calculate the length of the offset vector for the potential collider, and the length of the "distance" vector. The distance vector is the vector that points from sphere center to center. If the offset vector''s length is shorter than the length of the distance vector minus the radius of the target, then there isn''t any way they could hit and the collision test aborts. If this is not the case, this new action is taken:
3.) Calculate the orthogonal projection of the distance vector onto the offset vector. This is 2 dot products, a division, and a scalar multiplication of a vector. It''s actually only 1 dot product and a squaring operation, since you need to find (offset dot offset) but that is equal to ||offset||^2. Then take the difference of the projection vector and the distance vector, which is the vector v. Find the length of v, which is the distance d. This requires one vector subtration, a dot product, and a square root.
If you''re not familiar with orthogonal projections (or the description was too convoluted to follow), v is the the vector that points from the target''s center and intersects the offset vector at a right angle. Therefore, it is the shortest distance from the center point of the target sphere to the offset vector. It seems logical that if you take the distance d and subtract the target radius, you have the smallest possible "window" that an object would have to fit in to avoid colliding. If the potential collider radius was smaller than this window, it would always fit through. If it was the same size or larger, it would always collide. Therefore r1 > d - r2 is the only way there is no collision. I would state this as r1 + r2 > d is always a collision avoidance, else the two objects must have collided. I believe this test always works, and it seems relatively fast. The slowest operations are the two dot products and the square root. However, since no one uses this already (AFAIK), I think there must be a better way.
