Re: [Algorithms] Collision fun in cube hell
Brought to you by:
vexxed72
From: David B. <db...@bt...> - 2000-09-29 10:55:06
|
> 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 |