Computing union of overlapping pairs (simulation islands)

[sbroumley]

Does anyone know of a fast (incremental perhaps?) method that can compute the union of overlapping pairs using the "pair deleted", "pair added" information from the broad phase?

The only methods I've seen are a "start from scratch every frame" 2 pass approach: The 1st pass sets up N islands (where N = the number of bodies). The 2nd pass merges the islands.

Is there a method that can use the information from the fast broad phase ie. 1) You know when a new pair begin to overlap 2) You know when a current pair cease to overlap.

I noticed bullet uses a 2 pass approach (although unless I'm reading the code wrong, the inner loops in "SimulationIslandManager::BuildAndProcessIslands" will become worst case O(NxN) searches if there are N islands. )


thanks
Steve.

[Erin Catto]

I like to use a body, contact, and joint graph. You can find the islands using a depth first search from the awake bodies. This is always O(n) in the number of bodies, contacts, and joints.

If you think about it as a graph problem, it seems that no incremental algorithm can be faster than O(n). Consider when an edge is deleted. How do you determine if the island is split? Wouldn't you have to search the island?

[Erwin Coumans]

I noticed bullet uses a 2 pass approach (although unless I'm reading the code wrong, the inner loops in "SimulationIslandManager::BuildAndProcessIslands" will become worst case O(NxN) searches if there are N islands. )
thanks
Steve.

Did you check the most recent version of Bullet 2.0e?

Bullet uses Union Find to find the connected simulation islands, based on AABB overlap from the broadphase and constraints. Recently I added path compression to Union Find, and according to the following link "Complicated analysis shows: O(m A(m,n)) time where A(m,n) is inverse-Ackerman's function"

http://www.continuousphysics.com/ftp/pu ... n%20II.htm

After the islands are build, I sort this data, and then all islands can be processed in parallel for both collision detection and constraint solving.
There is no multi-core version in the public version yet, but that will be available in the future.

I like to use a body, contact, and joint graph. You can find the islands using a depth first search from the awake bodies. This is always O(n) in the number of bodies, contacts, and joints.

I am curious if this is really a faster way then Union Find to find the islands. Can you give more details how to determine connected islands, from a set of N bodies, with M connections?

[Erin Catto]

I use the first algorithm in the link you provided:

------------------------
Off-line version:

* Entire input is given at once.

* Solution:
o Scan input and place edges in undirected graph.
o Run depth-first search to identify components and label each vertex.
o Scan labels and print out classes (components).

* Analysis: O(V + E).
(Here, E = number of input pairs.)
----------------------------

To speed this up I maintain a connectivity graph at across time steps. This is exactly what ODE does (except it recreates the contact graph each step).

[Erwin Coumans]

I use the first algorithm in the link you provided:

------------------------
Off-line version:

* Entire input is given at once.

* Solution:
o Scan input and place edges in undirected graph.
o Run depth-first search to identify components and label each vertex.
o Scan labels and print out classes (components).

* Analysis: O(V + E).
(Here, E = number of input pairs.)
----------------------------

To speed this up I maintain a connectivity graph at across time steps. This is exactly what ODE does (except it recreates the contact graph each step).

Do what is the actual output of your algorithm? All objects have their island id? How do you process the separate islands at the end, do you have an array of them? In other words, can you easily do parallel processing of islands too?

I'm doing the on-line version instead. If there would be a cheap way to remove edges/constraints in this approach, then it would be good to keep it persistent. I've been looking into this for a while (and this is probably what the original question is about), but couldn't find such incremental removal of edges/constraints.

union find deunion only allows backtracking/removing most recent added edges, no random removal of edges

Is there any?

[Erin Catto]

During the DFS, I build up arrays of pointers to bodies, joints, and contact constraints. These arrays get placed into an island structure which is sent to the solver.

With this system it should straight forward to do parallel processing of islands. Once the island is built, you can send it to another thread while the next island is being built in the main thread.

I don't keep any island ids in the bodies or joints because it is not needed.

[efoss]

I use a union-find, an "on-line" version. By the time all my pairwise collisions are done, the islands are ready to iterate over without any more work. I found this page to be very good for understanding the concept:

http://en.wikipedia.org/wiki/Disjoint-s ... _structure

As the example in Bullet demonstrates, the basic algorithm is very simple. According to that web page, it was proven in 1989 by Fredman and Saks to be the cheapest possible disjoint-set algorithm.

I found it useful in my implementation to keep linked lists attached to each object indicating its current children. That allows me to

1. Iterate over the items in each island without having to sort anything
2. Remove an item at any time without destroying its island

Getting all the pointer maintenance correct is a pain though!

I store a pointer within each collision object to its union-find parent, which through path compression is normally the mega-parent or representative of that island. That allows me to quickly find and iterate over an island, starting just with a pointer to one of its members.