[PD] ODE & Pd; was Re: patch parameterisation

[Chris McCormick]

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 at mccormick.cx
http://mccormick.cx