[ODE] Sweep-and-Prune space for ODE

[Aras Pranckevicius]

Hi,

I've just made a quick implementation of Sweep-and-Prune (SAP) space for
ODE's collision system. It uses Opcode 1.3's BoxPruning code, that's the
simplicity itself (just resorts interval lists on every collision). So, it's
just under 300 lines of code to get it into ODE.

I've made some "does it work" tests using my LTGameJam2003 games - it seems
to work :)

I've made some timing tests using ODE's test_space_stress under various
conditions (no physics, even no contact generation) with various object
counts (100,1000,10000) and world sizes (5,10,20,100). The results are
basically like this:
. SAP is the fastest, which is kind of surprise :)
. Quadtree is next (1.5x-4x slower, depending on conditions)
. Hash is next (2x-20x slower than SAP, up to several times slower than
Quadtree)
. Finally, Simple space is last, which is no surprise (but it beats
Hashspace at low [100] geom counts!)

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

My SAP doesn't like objects with infinite AABBs yet (that's Planes, and
TriMeshes if you don't apply my patch for AABBs :)).


Aras Pranckevicius aka NeARAZ
http://www.gim.ktu.lt/nesnausk/nearaz/