[ODE] ODE-GIMPACT performance and advices

Pierre Terdiman pierre.terdiman at novodex.com
Fri Oct 27 08:01:35 MST 2006

> > Well, if you find "real" bugs in Opcode, please
> > report them :)
> A\:Just try to compile it on MingW!! and then we talk.

Well, that's not what I call a "real" bug. I simply don't have time to
support N platforms / machines / etc.

> Updating a plain array of AABBs is faster a lot than
> updating an entire AABB tree with such 'refit'
> (refried) function.

Errrr....? That's exactly what the "refit" function does: it updates an
array of AABBs..... With Opcode's "no leaf" trees, the number of AABBs is
equal to the number of triangles in the mesh. So I don't see the difference.

> A\: At first I've tried Opcode's "box pruning", and
> let me say ... it is not correctly at all, specially
> the bipartite box prunning (necessary for trimeshes).
> It has redundant and innecessary code  that causes hit
> performance on your app.

As I wrote, maybe your implementation is faster. I was just pointing out
that I tried the same -idea- a while back, and that Opcode also supported
deformable meshes (and I only did that because you claimed the opposite).

> Another issue is that the
> Opcode's "Radix sort" is not the optimal
> implementation.  On many experiments I've noted that
> quicksort is often faster when we have less of 1000
> boxes; on the other hand radixsort would better when
> we have large sets.

This is correct, a radix sort is not optimal when the number of entities to
sort is "small". However it is generally a good idea to optimize your -worst
case-, and that's what a radix sort is good at. If you only have a small
amount of things to sort, you could even use a bubblesort and you wouldn't
see a difference in the framerate anyway.

There is no unique "optimal implementation" for all cases. If you want to be
optimal all the time, you need to use different algorithms for different
situations. Radix is good because it's fast when it matters.

> However, GIMPACT boxprunning code can be optimized
> even more. Use your imagination.


Would be nice to have a short description of your approaches/algorithms,
actually. Not just for the box pruning.

> I have to admit that GIMPACT doen't save memory as
> good as OPCODE. Also I've noted that it consumes more
> memory than OPCODE because GIMPACT needs to keep a
> cache of transformed vertices and planes.

Hmmm, I thought GIMPACT would use -less- memory... Do you have extra data
structures like a BV-tree or something? If you only have a cache of
transformed vertices, it sounds pretty reasonable.

> But about speed, GIMPACT remains as the King of the
> Hill. No matter what do you say, It is faster. I don't
> know why?  Sometimes Brute force astonish me!!
> (??????)


No matter what you say, I only believe in benchmarks :)

I suspect we will find that library X is better in some cases, library Y is
better in other cases. As often...

- Pierre

More information about the ODE mailing list