[ODE] Sweep-and-Prune space for ODE

[Graham Fyffe]

Sorry guys, but I just *have* to ask.  Has anybody done any conclusive
benchmarks on the radix sorting code?  I remember a while back I did
some pretty extensive tests and I found that radix sorting was 2x as
fast as std::sort for integers, but the floating point version (that
handled signs) was 2.5x slower!  This was pretty consistent for input
sizes from 10,000 to 100,000,000.  Was I just using a crappy radix
sort implementaiton?

- Graham


On Thu, 25 Nov 2004 16:04:14 +0200, Aras Pranckevicius
<nearaz at interamotion.com> wrote:
> So, the sweep-and-prune collision space for ODE...
> 
> The sourceforge CVS isn't working for me at the moment, and my ODE cvs
> is really out of date, so I can't make a nice "patch". So, I'm trying to
> write in oldskool "plain text" way.
> 
> First, the sweep-and-prune space caveats/features:
> * uses radix sort, so the performance is nearly independant of object
> velocities/configurations. Radix sorter shamelessly used from Opcode.
> * relies heavily on "standard" ieee 4 byte floats present on a system.
> ODE itself can use either double of float, but the radix sorter uses
> only floats.
> * needs <Opcode.h> and library. I could factor the radix sorter into
> some independent sourcefile, but...
> * special handling of infinite-aabb geoms is needed here, internally the
> code only does a check "if( aabb.someAxisMax == dInfinity )". So far
> only dPlane has infinite aabb, and it works here; but the code could
> break with "half-infinite" (i.e. not all directions) AABBs.
> * abuses some pointer members in geom structure to store indices into
> internal arrays. So, at least 32 bit pointers are required (16bit
> pointers should work if geom counts don't exceed 64k).
> * dSpaceCollide2 for SAP space isn't implemented yet.
> 
> Now, steps to bring SAP space into ODE:
> 
> 1. include/ode/collision.h, add space class enumeration
> (roughly line 90, insert between "dHashSpaceClass," and
> "dQuadTreeSpaceClass,"):
>     dSweepAndPruneSpaceClass,
> 
> 2. include/ode/collision_space.h, add somewhere
> (eg. after dQuadTreeSpaceCreate prototype):
>     // Order XZY or ZXY usually works best, if your Y is up.
>     // Don't know how to express axis orders... defines are ok?
>     // must match PointComponent/AxisOrder from Opcode/Ice/IceAxes.h!
>     #define dSAP_AXES_XYZ  ((0)|(1<<2)|(2<<4))
>     #define dSAP_AXES_XZY  ((0)|(2<<2)|(1<<4))
>     #define dSAP_AXES_YXZ  ((1)|(0<<2)|(2<<4))
>     #define dSAP_AXES_YZX  ((1)|(2<<2)|(0<<4))
>     #define dSAP_AXES_ZXY  ((2)|(0<<2)|(1<<4))
>     #define dSAP_AXES_ZYX  ((2)|(1<<2)|(0<<4))
>     dSpaceID dSweepAndPruneSpaceCreate (dSpaceID space, int axisorder);
> 
> 3. take the attached file (collision_sapspace.cpp, zipped because
> of 10kb attachment limit), put into ode/src, add to
> makefiles/projectfiles so that it compiles.
> 
> That should be it! Call the function you added in step 2 above to create
> SAP space, and enjoy. In my tests (boxstack with various geom counts)
> SAP either beats all others by large amount, or is on par with quadtree
> space. Can't remember the details right now, and can't find the files
> where I've written them :)
> 
> 
> 
> 
> Aras Pranckevicius aka NeARAZ
> http://nesnausk.org/nearaz/
> 
> 
> _______________________________________________
> ODE mailing list
> ODE at q12.org
> http://q12.org/mailman/listinfo/ode
> 
> 
> 
>