Re: [Algorithms] Collision fun in cube hell

[David B. <db...@bt...>]

> 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
>

cool.

> 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".

I think the bottleneck for these test would be the contact force computation
or integration stepsize (if penalty methods are being used etc). Not the
collision detection and contact determination.

>
> 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 :)

I personally _HATE_ collision detection a lot. There are just too many
special cases and it is difficult to get really accurate contact
manifolds(not to mention debugging this)... But I love working on the other
physics simulation problems:-)

David

http://www.dblack.btinternet.co.uk
ICQ #: 24402391
Mobile: (UK) 0778 7836188