[ODE] [ opende-Patches-1335198 ] Sweep and Prune Space

Jason Perkins starkos at gmail.com
Thu Nov 8 12:07:34 MST 2007

If this the SAP space is really working (see tracker item below) any chance
we could get it into the trunk? It is still very useful even without
dCollide2(), and is much more likely to get worked on in the trunk.



On Nov 8, 2007 12:56 PM, SourceForge.net <noreply at sourceforge.net> wrote:
Patches item #1335198, was opened at 2005-10-22 17:53
Message generated for change (Comment added) made by markdjwilliams
You can respond by visiting:

Category: New Feature
Group: Needs Feedback
Status: Open
Summary: Sweep and Prune Space

Initial Comment:
From: Aras Pranckevicius
Date: Mon Apr 25 01:56:06 2005
Subject: [ODE] SAP space (was: Large physics worlds...)

> > Should I package the patch again, and maybe
submit/upload it somewhere?
> >
> I know I for one would love to try it out...  Are
there any major
> issues with it?

Ok, here goes the sweep-and-prune space for ODE:

It's not a patch, as I don't have diff/patch right now
and am too lazy
to get them. Some readme is included; basically it's
one new cpp file
and a couple of lines added to ODE include files.
Should be pretty
basic to integrate.

Now, about it:

* Does complete re-sort on each collide call. That is,
no temporal
coherence of any kind. The good side of this is that it
handles very
fast moving things well.

* Has no collide2 implemented :(

* Depends on Opcode sources being present
includes Opcode.h and uses radix sorter from there).

* Uses radix sort for the sweep phase. Uses single
precision floats
internally (ODE can still use doubles), which I think
must be standard
IEEE floats (Opcode's radix sorter assumes IEEE
floats). I think
that's not a problem on most platforms.

In my own usage scenarios, I've seen SAP either beating
other spaces
by large amount, or beating them by small amount :) YMMV.

> ----------------------------------------
> Comment By: Mark Williams (markdjwilliams)
> Date: 2007-11-08 09:56
> Message:
> Logged In: YES
> user_id=1768899
> Originator: NO
> I just applied this patch to my local checkout, and hacked the Makefile.am<http://makefile.am/>
> files so that Opcode was linked even when --with-trimesh=gimpact
> A simple test simulation with a few thousand cubes falling on a ground
> plane took 3070 seconds with the SAP space, and 3050 seconds with QuadTree
> space. So this space appears to be incredibly useful because , in this
> example, it gives results close to what I consider to be the optimal case
> but without any parameter tweaking (quadtree needs center, extents, and
> depth settings)
> If the dependence on Opcode radix sort were removed I think this would be
> a very valuable patch, even without collide2()
> (comments snipped for brevity)
> You can respond by visiting:
> https://sourceforge.net/tracker/?func=detail&atid=382801&aid=1335198&group_id=24884
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://ode.org/pipermail/ode/attachments/20071108/d2a4b46e/attachment.htm

More information about the ODE mailing list