Broad Phase with spheres

[projectileman]

Hi,

Is there a very efficient and fast spatial partition for getting intersections between thousands of spheres?

thanks.

[Nathanael]

I guess SAP could do just fine, else you can try to google papers about "smooth particle hydrodynamic" which is a Lagrangian method to simulate fluid that require just that, very fast enumeration of interacting particles (usually fixed radius).
You can try Takashi Amada SPH demo http://www.ss.iij4u.or.jp/~amada/fluid/, he handle ~2k particles with a simple spatial hashing i believe.

Hope it help.
Nathanael.

[BGB]

Hi,

Is there a very efficient and fast spatial partition for getting intersections between thousands of spheres?

thanks.

don't know if there is better, but I typically use a variation of BSPs.

basically, my approach is like this:
for a list of items, if there are too few items (for example, 0 or 1), create a leaf;
for the list, calculate the centroid;
for the list, using the centroid, calculate the division axis (usually a single-pass);
use these to make a plane (stored in node);
split the list into 3 lists (left, middle, and right) depending on how the items relate to the plane (middle items cross the plane);
bind middle items to the current node;
recurse for the left list, forming the left sub-node;
recurse for the right list, forming the right sub-node.

now, these trees can typically be formed fairly quickly, even for a fairly large number of objects. likewise, these can also offer a notable speedup in terms of spatial queries.

typically, the centroid is just the average of the origins.
often, for the axis I use:
normalize( sum(0, i=n) abs(org-centroid) )

this is simple and fairly effective, but, this does for some distributions produce sub-ideal division planes. I have a slightly more complicated (but more effective at finding planes) algo, which works by dividing the vector-space into hemispheres and accumulating these, finally picking the hemisphere with the biggest axis.

these are similar to KD-trees (also commonly used), except that KD-trees typically force an axially-aligned division plane (personally, I would think this would tend to reduce the tree's query efficiency, but oh well).


I have used this basic approach in things ranging from speeding up rendering of geometry, to particle simulation, and also intersection culling...