Discussion:
[ opende-Patches-1335198 ] Sweep and Prune Space
Jason Perkins
18 years ago
Permalink
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.

Jason

---

On Nov 8, 2007 12:56 PM, SourceForge.net <***@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:
https://sourceforge.net/tracker/?func=detail&atid=382801&aid=1335198&group_id=24884

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:
http://nesnausk.org/nearaz/files/ode-sapspace-050425.zip
(30kb).

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
(collision_sapspace.cpp
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.

------------------------------
...
David Walters
18 years ago
Permalink
Okay, I've added this new Sweep and Prune space. I had to do some
additional work to get it though:

* The space doesn't store geoms as a usual linked list, so a custom
destructor was required to remove / destroy geoms under it's
ownership.

* Each call to collide caused a memory allocation, I've changed that
to use a scratch pad mechanism so allocations are only performed when
the geom count changes. Now I think of it there is probably room for
improvement here by replacing my code with a dArray.

* The code had a dependency on the radix sorter from OPCODE. To break
this I've copied the inner workings into the SAP source file - it
doesn't amount to very much when you boil off the fluff.

* The was the radix sorter was used before would leak, now it uses a
very simple reference counter to catch this.

Here a few other notes:

* The radix sorter uses IEEE floats, so AABBs are actually cast if
you're building in double precision mode. I'm hopeful that this isn't
a problem - if it is there are other spaces you could use for now.

* I changed demo_crash to use this new space.

Finally, I've not profiled this at all - I'm hoping Mark Williams,
etc. can tell me if it's even faster now I've incorporated it
properly.

Regards,
David Walters
David Walters
18 years ago
Permalink
Post by David Walters
Okay, I've added this new Sweep and Prune space. I had to do some
Darn, forgot:

* I added a naive collide2 implementation too. Now, at least, it's a
fully functional as a space.

Dave
Jason Perkins
18 years ago
Permalink
Post by David Walters
Okay, I've added this new Sweep and Prune space.
Awesome - thanks!

Jason
Mark Williams
18 years ago
Permalink
Post by David Walters
Okay, I've added this new Sweep and Prune space.
Wow, that was quick! Thanks so much!
Post by David Walters
Finally, I've not profiled this at all - I'm hoping Mark Williams,
etc. can tell me if it's even faster now I've incorporated it
properly.
It does seem slightly better - it now outperforms QuadTree space by a
small amount (2-3%) for the test case I was previously working with.

I'm using GIMPACT and everything builds fine out-of-the-box (linux gcc
4.0.2) - single precisions only here, because of existing issues with
double/GIMPACT, though. I've not seen any memory leaks.

I'd love to see some documentation on this added to the Wiki, if
possible, especially regarding how to establish what the best "axis"
might be for a given configuration. Also, I see that computeAABB is not
yet implemented, so perhaps an assert should be added there inline with
the other non-implemented functions elsewhere in ODE?

It's a great job as far as I can tell so far, and will be using it as my
"default" collision space in the future!

Thanks again,
Mark
David Walters
18 years ago
Permalink
Post by Mark Williams
It does seem slightly better - it now outperforms QuadTree space by a
small amount (2-3%) for the test case I was previously working with.
That's great to hear, glad I could help.
Post by Mark Williams
I'm using GIMPACT and everything builds fine out-of-the-box (linux gcc
4.0.2) - single precisions only here, because of existing issues with
double/GIMPACT, though. I've not seen any memory leaks.
The SVN mailing list seems to have skipped reporting a checkin I've
just made (despite logging SVN #1303 that I put in straight
afterwards) - so I'll just say here that I've ripped out my redundant
scratchpad buffer and replaced it with a dArray. This shrinks the code
a little and should operate at the same performance.

I also fixed the 64-bit warnings. They occurred from the hijacking of
the geom pointer values intended for a space to uses as a linked list,
but used here to store index values. There are no mixing of genuine
pointers and integers so it was safe to silence them.
Post by Mark Williams
I'd love to see some documentation on this added to the Wiki, if
possible, especially regarding how to establish what the best "axis"
might be for a given configuration.
Well, although it wasn't a straight job of importing a patch, the work
I have done on this is just to make it comply with ODE's requirements
for spaces and a few optimisations - the core work should be credited
to Aras Pranckevicius for the submission and Pierre Terdiman for the
radix sort function.

I roughly understand what it's doing but not to the extent that I
could write any meaningful documention. I know the gist is to pick an
axis order such that your 'up' is last, so XZY typically - but I have
no idea why!

Your best bet is if Aras is reading this list, and he could comment on
the specifics for tuning. Alternatively profile the options as it will
obviously have some degree of dependence on the world you're
simulating. I suppose also doing some research on SAP as a general
concept might help?
Post by Mark Williams
It's a great job as far as I can tell so far, and will be using it as my
"default" collision space in the future!
I've always stuck with hash space because it's zero configuration, but
never really experimented with the alternatives - this certainly wins
on the low effort front!

Glad to have contributed,
Dave
Pierre Terdiman
18 years ago
Permalink
Post by David Walters
the core work should be credited
to Aras Pranckevicius for the submission and Pierre Terdiman for the
radix sort function.
I think it also uses the box pruning code from Opcode 1.3, right? :)
Mark Williams
18 years ago
Permalink
...
After a bit of reading, my best guess would be that if the up axis were
first then simulations where objects come to rest on the ground would be
some kind of worst-case scenario?


Thanks once again,

Mark

Loading...