On collision detection

[Dylan Trotter]

The basic idea for the collision detection system is to project the 2D system into a 3D system composed of 2 spacial dimensions plus time. In the 3D system, any intersections between geometries correspond to collisions between the bodies they represent. The time of intersection will be the minimum value of time where any two bodies intersect. The system will then be evolved by this minimum time, the collision will be resolved and evolution will continue until the time-step is exhausted.

The most expensive part of this procedure is certainly finding the minimum value of t where the system is still consistent. Thus finding a polyhedron-polyhedron intersection algorithm that is efficient, is of the utmost importance.

However, there are a few factors which may help us make simplifications to the algorithm:

1) If the 2D objects are convex, the 3D polyhedrons are necessarily convex. The algorithm for convex polyhedron intersection is much simpler than for general polyhedron.

2) The faces of the polyhedron not perpendicular to the time dimension are parallelograms which are easily triangulated. The other faces (the 2D objects at t=0 and t=t1) will be identical except for possible rotation and translation and can thus be pretriangulated.

3) We only really need to find the minimum time at which a collision might occur, so we don't necessarily have to construct the whole intersection polygon. This may be the most important simplification of all.

Here are a couple of papers on citeseer relating to collision detection in general. They may help get the ball rolling:

http://citeseer.ist.psu.edu/zachmann94exact.html
http://citeseer.ist.psu.edu/zachmann98rapid.html

[Andrew MacDonald]

There seems to be some much easier solutions to 2D collision detection. One based on the seperating axis theorem (SAT) is described here (which also includes some nice graphical examples of SAT at work):
http://www.harveycartel.org/metanet/tutorials/tutorialA.html

However (and correct me if I'm wrong), it's my understanding that a Timmy "guiding philosophy" is to build an engine as physically accurate as possible. In this case, a system such as the one described above should not be considered. This is due to a single assumption: that all collisions will be properly detected at each time-step. If the time-step is not small enough for this assumption to be satisfied, collisions may not be detected, or possibly worse may not be detected properly (so that objects will go shooting off in the wrong directions).

As long as we are ruling out simpler systems, I am curious to know if there are any physically accurate 2D collision detection methods besides time-projection. If so, would they warrant consideration for use in Timmy?

[Dylan Trotter]

The SAT is quite useful for 2D collision detection, however, as you say, unless the timestep is exceedingly small, collision resolution becomes very difficult.

One improvement is the following algorithm:

1) Evolve system by time dt.
2) Check for 2D collisions.
3) If there aren't any overlapping collisions goto step 6. Otherwise go to 4.
4) Backtrack the timestep.
5) Go to step 1 with dt -> dt/2.
6) If there are any collisions where objects touch or are within some epsilon of eachother, resolve the impact and ensure they won't touch in the next timestep (i.e. make them deflect).

I believe this is commonly done in games. However, it has the potential to be extremely slow since you may have to check for collisions many times before finding none. As well, it is less exact.

However, there is no reason that we can't design such a detection scheme. One of the main goals is to explore different possibilities. And who knows, perhaps such a scheme would turn out to be very efficient.