[Algorithms] Collision fun in cube hell

[Pierre T. <p.t...@wa...>]

(This is a repost since the first one apparently never made it to the
list... While I was at it I completed it :)


Hi,

The thread "Checking for duplicate vertices quickly" where I proposed to use
the collision detection code to weld some 10K vertices gave birth to one or
two interesting tests......................

Ever wondered what fun it was to detect exact collisions among 10.000
individual cubes? I tell you, it's a lot of pain. So let's push the
enveloppe quite a bit:

www.codercorner.com/CubeHell.jpg
www.codercorner.com/CubeHell2.jpg

AABBs are drawn on the second screenshot.
Green = no collision
Yellow = AABBs overlap but cubes do not collide
Red = cubes are colliding

Not all cubes are visible on the same screen, "only" ~3300, else you just
can't see anything :) And yes it's "slow" (see the framerate in the corner
but eh ...!! That's 10000 individual cubes colliding down to the triangle
level !

This is absolutely useless and I know that, but it was so much fun to code I
must share that one with the list!

Note that for "only" 1024 cubes, it runs at ~70 fps on on Celeron 500, which
is kind of cool regarding Chris Hecker and Jeff Lander's "stress" tests of
physics engines, where 40 objects are said to be "a lot".

The algorithms used are the standard ones:
- sweep & prune
- OBB tree
- GJK
- Separating vector

...so nothing special, except the implementation looks robust.

I can change the collision detection method on the fly.

Currently the fastest method is a mix of GJK+Separating vector, in a
Q-Collide fashion. OBB "tree" is especially useless when the object is a
single box, and hence it runs way slower than the two other algorithms.
(about 6 times slower than the mixed GJK/SV, but this is a quite
experimental OBB tree implementation where I decompress the tree on the
f:ly, so the comparison may not be very fair!)

Guess what? I love collision detection :)

Cheers,

Pierre