[ODE] Sweep-and-Prune space for ODE
Graham Fyffe
gfyffe at gmail.com
Thu Nov 25 10:51:10 MST 2004
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
>
>
>
>
More information about the ODE
mailing list