Collision Detection

[Cynbe ru Taren]

Re the recent collision detection discussion:  There was a pretty
good article on this in Computer Graphics and Applications about
3-5 years ago.  The solution and conclusion there was that to do
realtime collision detection on complex worlds, you just have to
be really aggressive at eliminating needless work, using a whole
hierarchy of techniques, basically cheapest-first.

E.g.:

Typically much/most of the scenery is fixed wrt the ground:  You
don't have to test motionless trees to see if they are hitting
each other.  So don't.  Similarly with parts of moving vehicles
&tc.  They suggest that parts in contact are a nightmare for
collision detection algorithms anyhow, since they keep going in
and out of exact contact based on floating-point roundoff, and
fail all the cheap tests:  Big win to set up your system to just
not do those checks.

Beyond that, just use a cascade of techniques cheapest-first as
aggressively and intelligently as you can:  Sphere-intersection
checks and quadtrees &tc can rule out lots of potentential collisions
very quickly.  Bounding-boxes aligned with the coordinate system
ditto.  Potential collisions that pass those tests can be checked
on a simple convex hull, and potential collisions that pass -that-
can start checking against real device geometry.