[ODE] Sweep-and-Prune space for ODE

[Aras Pranckevicius]

> It would be useful in removing the float/double problem anyway.

It wasn't the problem for me (I used ODE in double precision, and SAP space 
uses single precision internally). Yes, there are quite many casts involved, 
but oh well :)

> It'd be interesting to see how the performance goes between the different
> sorts in a complex test.

Sure. Of course, this doesn't change the SAP space much - you just sort box 
intervals with another sorter, and that's it.

Another interesting thing would be implementing "classic" SAP that 
incrementally re-sorts moved AABBs instead of doing full sort each time. 
Shoulf be faster if geoms are moving slowly, but can be very slow if there's 
complete chaos happening with your geoms (Pierre has some measurements on his 
site).

Alas, I never got time to implement that, especially considering that now 
we're doing network management software and not interactive entertainment 
software :)

> Certainly 
> in contrived box stacks, lots of identical values aren't ideal for 
> some sorts, while radix doesn't care.

Yes, especially for things like quicksort. On the other hand, most "standard" 
sort implementations (eg. STL; don't know about qsort()) have special code 
paths for nearly-sorted data.


Aras Pranckevicius aka NeARAZ
http://nesnausk.org/nearaz/