Multi SAP

[John McCutchan]

What I was getting at is, how do you handle adding/removing/transitioning objects between the independent SAPs efficiently.

I'm not sure what you want to hear exactly? Since each SAP doesn't contain a lot of objects, adding or removing a shape from them is not very costly. Overlapping shapes are kept in a shared hash-based pair manager with O(1) add/remove/find (and no holes )
- Pierre

This still isn't what I'm asking, let me try again by describing a scenario

You have a block which is in SAP1 and it moves so that it is now in SAP2 (which is adjacent to SAP1.) How do you handle moving the object from SAP1 to SAP2?

Do you just do an AABB check between the blocks AABB and each SAPs AABB and insert / remove objects from the various SAPs as they enter / leave the region managed by the SAP. Or do you use a more elaborate scheme to determine when an object should be moved from one sap to another.

[Julio Jerez]

Mr Pierre you can make all the sacasmic juke you want, but that does changes from been a multigrid populated by fat SAP, There is nothing wrong with that.


Well Mr. Coummand you win you are too much of a dishonest person to really understand the huge conflict of interests you are by being the Collida official representative and the physic solution provider and the same time.
Not only that by you use your position foro self serving while blocking other developers, I guess we will have not other choice but to make our own standard.

Let my tell you if you ever get a public position do not ever do a simular activity, bacause that’s is called corruption.

[Christer Ericson]

All I'm saying is that "multiresolution grid" is a well-known data-structure, e.g. described in Christer Ericson's book (he calls them "hierarchical grids").

The reasons I called them hierarchical grids and not multiresolution grids were: (1) hierarchical grid was (and is) the more commonly used term, and (2) I find "multiresolution grid" much too close to "multigrid" for comfort, and multigrid is something different entirely.

And to corroborate Pierre's statement - yes, hierarchical grids are very well known, and that's also not the structure Pierre started the thread about (but instead about a combination of two other, also well known structures: a uniform grid and sort-and-sweep / sweep-and-prune structures).

[Erwin Coumans]

Well Mr. Coummand you win you are too much of a dishonest person to really understand the huge conflict of interests you are by being the Collida official representative and the physic solution provider and the same time.
Not only that by you use your position foro self serving while blocking other developers, I guess we will have not other choice but to make our own standard.

COLLADA is an open standard. Representatives of Ageia PhysX and others contributed to this standard, not just me.

Bullet is an open source physics engine. Developers can use it, and contribute if they like. There is no conflict of interest.

Julio, I asked you several times to post in your own topic, and not to clutter Pierre's broadphase posting. You disrespect the forum rules, therefore you are banned from this forum.

[Pierre]

Pierre, do you forsee any tricky cases in above scenario?

No, implementation was quite easy, ~1 day of work, no big challenges.

You have a block which is in SAP1 and it moves so that it is now in SAP2 (which is adjacent to SAP1.) How do you handle moving the object from SAP1 to SAP2?

Do you just do an AABB check between the blocks AABB and each SAPs AABB and insert / remove objects from the various SAPs as they enter / leave the region managed by the SAP. Or do you use a more elaborate scheme to determine when an object should be moved from one sap to another.

The AABB checks are not needed. For an update I simply rasterize the AABB in the grid, and compare touched grid cells to previously touched grid cells. Object is added to newly touched cells, updated in cells already there before, and in a second pass object is removed from cells that haven't been touched during this update.

Mr Pierre you can make all the sacasmic juke you want, but that does changes from been a multigrid populated by fat SAP, There is nothing wrong with that.

Sorry Julio, I have no idea what you're talking about. There was no "sarcastic junk" in my post. I can still add Newton to the test when the API is updated. And if you have a clever data structure that beats everything else, by all means, please share the details.

- Pierre

[thebolt]

Interesting results.

Me and a college have discussed two different ways of achieving a hierarchical broadphase utilizing SAP, mainly to solve the problem of having dense clusters of objects moving semi-coherently within a sparse world and that of additions/removals due to loading/unloading of parts of the world (streaming).

One idea we toyed with was to use a sparse 3d grid of SAPs so that cells are (lazily) added/removed on need. Another idea was to use "hierarchical SAP" whereby you would have an outer "master" SAP for most objects, but when you get a dense cluster of objects such as a pile of ragdolls or explosion object you create a separate SAP for them and insert the bounds of the inner SAP as a single AABB in the outer one.

Pierre, did you consider/try any other multi-SAP layouts except the flat dense 2D grid? While 2D grid is good fo rmost games, with my personal interest which is (space) flight it isn't always, or even ever, possible to define "up".

On a related matter, while I don't know what have changed since, in PhysX version 2.5 (and, I might even misremember some parts of this ) the SAP actually use linked lists however they were allocated from pools that were resorted so you had almost linear traversal (cache friendly) but didn't have to swap the objects, only pointers (or was it indices?).

-Marten

[Erwin Coumans]

- it would be interesting to apply the "multiple SAPs" strategy to both Bullet &
PhysX implementations...

Hi Pierre,

I just refactored Bullet and added the multi SAP broadphase. The overlapping pair cache is decoupled from the broadphases, and some bookkeeping is re-organized. Note that Bullet's broadphase also does early collision filtering. I wanted to keep the broadphase proxy 8 bytes which took a bit of effort (custom collision filtering, broadphase proxy points back to the 'parent' proxy, which stores the actual aabb and collision filter).

The implementation is almost done, so if you like you can finish it Seriously, I hope to have the first working implementation done tomorrow (before SIGGRAPH starts).

You can check all the changes here:
http://www.bulletphysics.com/ftp/pub/te ... elease.zip
or browse the SVN repository online

It should be fairly flexible, so the user can mix and match, and distribute the SAP broadphases in any arbitrary way (including overlapping SAPs).

Thanks,
Erwin

[Pierre]

Pierre, did you consider/try any other multi-SAP layouts except the flat dense 2D grid?

No, not yet. Maybe later.

On a related matter, while I don't know what have changed since, in PhysX version 2.5 (and, I might even misremember some parts of this ) the SAP actually use linked lists however they were allocated from pools that were resorted so you had almost linear traversal (cache friendly) but didn't have to swap the objects, only pointers (or was it indices?).

The SAP got rewritten using arrays for the Xbox. And then we used this new version everywhere because it was faster even on PC.

The implementation is almost done, so if you like you can finish it

I still have plenty to try for mine so I think I'll pass

- Pierre