[ODE] Sweep-and-Prune space for ODE

[Pierre Terdiman]

> . SAP is the fastest, which is kind of surprise :)

What surprise ? Finally someone sees the light ! :)

> The tests aren't very good, as object sizes are roughly the same, and
> distributed nearly uniformly (more investigations needed, as always).

It shouldn't make a lot of difference for the SAP algo, since it doesn't
really care about objects' sizes. However the other algorithms in your
benchmark might take a speed hit with big objects.

Your test might be flawed anyway : moving all objects all the time is *not*
a realistic behaviour. Most of the time only a small subset of all objects
is actually moving each frame. Which means my box-pruning code does a lot of
extra work in vain. In that case, the others algorithms might take the lead.

However, the "more advanced" form you mention takes care of this, and should
outperform the basic version in those cases. It should always run faster
than hashing and/or quadtree.

The nice thing about the box-pruning stuff is that it's very robust, taking
roughly the same time regardless of objects' velocities. The "more advanced"
version however collapses completely when all objects are moving very fast.
In that case it's often even slower than brute-force O(n^2) queries.
Speaking of which :

>Finally, Simple space is last, which is no surprise (but it beats
>Hashspace at low [100] geom counts!)

That's exactly why I've been advocating the brute-force box-pruning approach
for years. The Mirtich-like hashing scheme is fine and dandy... except it
doesn't take the real world into account. In the real world, i.e. in real
games, you often have less than 100 dynamic objects. You don't need the
extra complexity (i.e. the extra cache misses) here. Brute-force is the way.
Actually, improved brute-force (the box-pruning code you profiled) is the
way.... no extra ram needed, no extra data structure to maintain, fast,
reliable, predictable running speed, and it even scales well up to 10.000
objects, as you discovered. Nice or what ? :)


Pierre Terdiman

- Novodex AG (www.novodex.com)
- Personal : www.codercorner.com