I'm currently doing collision detection using the second method described in this GamaSutra article. In short, I test each point defining the area of one object to see if it is inside another object by dividing areas around the point into quadrants. I follow the second object's points around the source point, adding or subtracting one as I jump from one quadrant to another. If the sum is 4 or -4, then the point is inside the object. My problem is this: If I have two objects moving towards each other too fast, they can pass each other in 2 consecutive frames, resulting in no collision detection (since no points from one object are inside the other object). See my crappy drawing for what I mean. Frame 1

  ___                       ___
 /   \                     /   \.
|     | ---->       <---- |     |
 \___/                     \___/
Object A                  Object B

Frame 2

        ___           ___
       /   \         /   \.
<---- |     |       |     | ---->
       \___/         \___/
      Object B      Object A

This problem exists regardless of what collision detection algorithm you are using. If you only check for collisions for the current positions of the objects and the objects aren't colliding then they simply aren't colliding.
(also for colliding polygons a separating axis test, which is breifly described later in the article you linked, is faster, but it wouldn't solve your problem)

One possible solution is to not only check the objects at their current positions but to also check them at times between the current time and the last timestep. The number of times to check for collision could be based on the size and speed of the objects being tested, and this could catch a reasonable number of collisions (although it would still potentially miss some).

Another way, and one that would be sure to find all the collisions, is to treat time as a third dimension (or for colliding 3d objects, as a 4th dimension). Assuming that between timesteps objects move at a constant velocity and don't rotate, a polygonal object in 2d would become a prism shaped object in 3d. And then you need to deal with collision detection between 3d polyhedrons. If the objects don't move at a constant velocity or if they rotate between timesteps then the resulting 3d shape is not necesarily a polyhedron, and treating it as a polyhedron would once again be an approximation that would not always work. And collision detection between non-polyhedral, non-convex shapes, let's not even go there.

You could try my method, *IF* your game is not going to be networked: set a max velocity for all objects, and set a max time elapsed between frames, say about 25 ms. That way, if the person's computer hangs, the next frame will act like only 25 ms have passed. Again, you can't do that in a networked game(unless you make the server make everyone else hang, but that code wouldl likely be as tricky to implement as the predictive collision detection).

There was some way to take the dot product of the two locations (or maybe it was direction/velocity vectors). Anyway, it comes out as positive on one frame, and if it goes to negative on the next frame, you had a collision. Look up "tunneling collision" it may be in there somewhere.

Well, what you are doing is partial check for intersection of objects with eachother, done at every frame. If objects do not intersect in specific frames, but collide somewhere half-way through, you need accurate collision detection algorithm that takes previons and current position and check if there was collision in middle. It is generally speaking more complicated than just check for intersection. Or you can try to avoid this happening, and force objects not to move too much. Though it will be problematic for small objects.

As anonymous poster have said, to find accurate collision in n dimensions you need to find intersection in n+1 dimensions. With rotating objects it becomes rather hard to do.

In 2D, it is relatively simple to avoid at least some problems:

instead of checking if vertices of one object are in the other object (and vice-versa), check for intersection of line segments between previous position of vertice and new position, with second object (and vice-versa). Use line segment-line segment intersection for it.
You need to choose frame of reference so second object doesn't move , i.e. use positions relatively to second object.
Most importantly, objects will not get stuck this way:

       _____      |     | _____|_____|_____|     |     |     ||_____|_____|_____|      |     |      |_____|       where wide rectangle is one object and tall is other object. 

Also, it will work for bullets and rockets aswell, you will not need to handle them specially.

Though, that will not work very well for fast spinning objects. If for example one object rotates 180 degrees during timeframe, lines corresponding to vertices will intersect in the centre, i.e. it will be able to get through small holes.

In 3D this is harder because of edge-edge checks, but not very much.

Gamasutra article addressing this issue.

[Edited by - Dmytry on September 16, 2005 2:52:29 AM]

Checking for intersections between segments connecting the old and new positions of each point should detect the collisions between objects as long as they aren't rotating. If they are rotating, it might miss some. In any case, it could also detect collisions that wouldn't have actually happened between fast moving bodies. But since the user never sees them that closely, how are they to tell that they wouldn't have collided?

Also an optimized way of doing this check would be to sweep the polygons by their displacement vector over the last time step and then check the swept polygons for collision.

Quote:Original post by Anonymous Poster
Checking for intersections between segments connecting the old and new positions of each point should detect the collisions between objects as long as they aren't rotating. If they are rotating, it might miss some.

Indeed. I mentioned that. Instead of segment of circle, there will be chord, instead of piece of cycloid there will be straight line.
Though, it is not that bad - it will screw up when it rotates alot during single frame. Such rotations look like blinking mess on display, so if you clamp rotational velocities it will not be very noticeable.
Distance between chord and circle is 1-cos(0.5*w*dt) ~= 0.125*w2*dt2 for small dt , so more steps per second will help significantly.

Quote:
In any case, it could also detect collisions that wouldn't have actually happened between fast moving bodies.

When both bodies is moving, it is necessary to use system of reference where one body is standing at rest, and check moving vertices against non-moving edges.

Though, if one body is quickly rotating, we can't use rotating system of reference of this body or in some cases directly aimed rockets will not hit spinning player (and missing one will).

Quote:
But since the user never sees them that closely, how are they to tell that they wouldn't have collided?

Also an optimized way of doing this check would be to sweep the polygons by their displacement vector over the last time step and then check the swept polygons for collision.

yes, and works in 3D too.

**************************************************
"Ideal" solution is hard, for rotational + linear motion in 2D, you get cycloids and it is hard to find intersection. I remember discussion on this forum of use of quadratic pathes instead of linear ones, works better for rotations, but can't find relevant thread. it's probably too hard to implement.

Indeed straight line segments thing is imprecise, but atleast objects will not go through walls. Another hard part of collision physics is what to do when there's more than one collision in timestep.

[Edited by - Dmytry on September 16, 2005 10:38:47 AM]