On Tue, Jul 18, 2006 at 09:09:12AM -0400, Mathieu Bouchard wrote:
On Tue, 18 Jul 2006, Thomas Grill wrote:
Maybe it's a good idea to check whether collision detection can be turned off for situations that don't need it.
You can ask ODE to detect and do this for you automatically.
Also, make sure its collision detection algorithms are O(n log n). I can't imagine them being O(n*n), but you never know: if the lib is really new and/or always used with low object counts, it's possible that they didn't bother with O(n log n). (I didn't look at their code.)
ODE has two high level collision/culling algorithms to choose from. One is the most obvious one and is O(n^2). The other uses a nifty method of storing which objects are near eachother (and culling out those that couldn't possibly collide) and runs at O(n) which is better than O(n log n) for larger numbers of bodies.
There is another excellent clustering collision detection algorithm which speeds up collision detection drastically in a similar way, described in the book Game Programming Gems II, called recursive dimensional clustering. It can be used on spaces of arbitrary dimension and allows you to use fast sorting algorithms on cached lists to do the grunt work. I am hoping one day someone (maybe me) will make a new ODE space which uses the RDC method and do some profiling against the existing methods. My intuition says it will be quicker in many cases.
There are also many other ways to increase the speed of ODE at the expense of integrator stability and accuracy. Check the documentation for more info.
Best,
Chris.
chris@mccormick.cx http://mccormick.cx