I'm having a real hard time sifting through the literature to decide the best Spatial Partition method. Alot of literature is on dividing up meshes into spatial partitions, especially static meshes, which is confusing me to no end. I need a tree or other structure to help me lower the order of complexity on the collision detection between my bouncing, falling, and generally moving around and quite dynamically spheres. The number of objects is on the order of up to about, say, 5000. They're all spheres at the moment, and that doesn't look like it's going to change anytime soon, so I'm willing to make a decision based on them staying spheres. They range in size from a radius of 1 to about 25, relatively speaking. Quadtree/Octree sounds good, and is what I'm leaning towards at the moment, but there are so many different kinds of quadtrees/octrees that I don't know which one to choose. Since my objects take up physical space (ie: they're not just single points) I think a point quadtree might not be the best solution. Also, it seems to me that since my data is spherical instead of cubical, I'd want some data structure that's sphere based. Uniform Grids are easy to implement, and would definately provide a speed up, but I'm really trying to learn something in the process and I know that since my objects aren't uniformly sized this isn't the best solution. k-d trees work well for static objects, like landscapes, but really take too long to balance for dynamic objects. That's as far as I am at the moment. I've tried looking at various physics engines but alot (perhaps most) seem to just use brute force between the game world objects' AABB or bounding sphere, which is fine when you're running a couple hundred objects, but I'd like something a little more intelligent myself. If anyone's implemented a physics engine and sorted their objects into a tree or something similar, I'd like to know what they used.

"Sweep and Prune" is a popular method that works well for the broad phase collision detection of dynamic objects. It's used by many of the popular commercial physics engines and it's relatively easy to implement (there are plenty of resources on the net).

Throwing static objects into the mix, I just add them to the sweep and prune also (broad phase), but then for the narrow phase of primitive (in your case sphere) v static mesh (poly soup), I just use an axis-aligned-bounding-tree for the static mesh which has a query that can return the list of triangles within the collision aa-bbox of the moving primitive.

-Steve.

I tried many: uniform grid, quad tree, loose quadtree, sphere-tree, hier-grid, sweep & prune. I ended up using loose quadtree for rendering and hier-grid for CD. See Christer Ericson's Real-Time Collision Detection for more info (including example source). The version(s) that works best for you will depend on the size of your world, the types of objects, how they move, etc. The best way is to develop a SpatialPartition() virtual/interface class and swap out a variety of methods, testing each for various performance cases.

Quote:Original post by Numsgil
I'm having a real hard time sifting through the literature to decide the best Spatial Partition method.

The reason you're having a hard time is because there is no single best method. There are soo many parameters that affect whether one approach will perform better than another.

Like John said, the best thing is to implement a few different approaches in a generic framework that allows you to swap between them easily and then simply measure which does better on your particular problem.

That said, for dynamic objects options include: sort-and-sweep (not sweep-and-prune), regular structures like octrees and quadtrees (possibly loose), grids (both uniform, as well as hierarchical), and trees (often using lazy updating).

In that they're so trivial to implement I would start with a grid. In that you want to learn something new, try a hierarchical grid.

About two years ago, I tried out both the quadtree and sort-and-sweep algorithms for the broad phase of a 2D collision system. The "universe" was composed of 1000-2000 circles with radii ranging from nearly zero to about 10 units. The space was 1000 x 1000 units. About 80% of the circles were static and the rest were mobile, some quite fast. With my implementations, at least, the quadtree was a little bit harder to program, but ran significantly faster. I can't say exactly how much faster, since I did the tests a long time ago, but because your setup sounds relatively similar to mine (that is, we both have a lot of shapes), I thought you might find the results interesting.

John Edwards

Quote:Original post by PistachioPro
About two years ago, I tried out both the quadtree and sort-and-sweep algorithms for the broad phase of a 2D collision system. The "universe" was composed of 1000-2000 circles with radii ranging from nearly zero to about 10 units. The space was 1000 x 1000 units. About 80% of the circles were static and the rest were mobile, some quite fast. With my implementations, at least, the quadtree was a little bit harder to program, but ran significantly faster. I can't say exactly how much faster, since I did the tests a long time ago, but because your setup sounds relatively similar to mine (that is, we both have a lot of shapes), I thought you might find the results interesting.

John Edwards

That does sound quite similar, thanks.

I'll do as you guys suggest and develop a wrapper for any partition method I develop so I can swap them in and out and test different methods.

Quote:Original post by Numsgil

Quote:Original post by PistachioPro
About two years ago, I tried out both the quadtree and sort-and-sweep algorithms for the broad phase of a 2D collision system. The "universe" was composed of 1000-2000 circles with radii ranging from nearly zero to about 10 units. The space was 1000 x 1000 units. About 80% of the circles were static and the rest were mobile, some quite fast. With my implementations, at least, the quadtree was a little bit harder to program, but ran significantly faster. I can't say exactly how much faster, since I did the tests a long time ago, but because your setup sounds relatively similar to mine (that is, we both have a lot of shapes), I thought you might find the results interesting.

John Edwards

That does sound quite similar, thanks.

I'll do as you guys suggest and develop a wrapper for any partition method I develop so I can swap them in and out and test different methods.

Be sure to check out John Ratcliff's sphere tree chapter/demo/code (in GPG2). It shows thousands of spheres moving around in real time (2D).

See also Thatcher Ulrich's Loose Octrees/Quadtrees (GPG1).

After checking my source code, I tested Sweep and Sort using qsort(). I'll test it again in the future using Pierre Terdiman's Optimized Radix Sort (provided the code/radix-algorithm can be adapted (uses arrays of ints or floats, properties of the bits)).

Christer, why do you recommend Sort and Sweep vs. Sweep and Prune (or just a preferred naming convention)?

Quote:Original post by John SchultzChrister, why do you recommend Sort and Sweep vs. Sweep and Prune (or just a preferred naming convention)?

It's a preferred naming convention. To the best of my knowledge Baraff was first with that particular approach, which he called "sort and sweep" in his 1992 PhD thesis. The same approach was reinvented by Cohen et al in 1995, but they called it "sweep and prune." The latter term seems to have stuck more, possibly because Baraff's thesis is a pretty obscure reference but, arguably, sort and seep should be the term we're all using.

Quote:Original post by John Schultz

Quote:Original post by Numsgil

Quote:Original post by PistachioPro
About two years ago, I tried out both the quadtree and sort-and-sweep algorithms for the broad phase of a 2D collision system. The "universe" was composed of 1000-2000 circles with radii ranging from nearly zero to about 10 units. The space was 1000 x 1000 units. About 80% of the circles were static and the rest were mobile, some quite fast. With my implementations, at least, the quadtree was a little bit harder to program, but ran significantly faster. I can't say exactly how much faster, since I did the tests a long time ago, but because your setup sounds relatively similar to mine (that is, we both have a lot of shapes), I thought you might find the results interesting.

John Edwards

That does sound quite similar, thanks.

I'll do as you guys suggest and develop a wrapper for any partition method I develop so I can swap them in and out and test different methods.

Be sure to check out John Ratcliff's sphere tree chapter/demo/code (in GPG2). It shows thousands of spheres moving around in real time (2D).

See also Thatcher Ulrich's Loose Octrees/Quadtrees (GPG1).

After checking my source code, I tested Sweep and Sort using qsort(). I'll test it again in the future using Pierre Terdiman's Optimized Radix Sort (provided the code/radix-algorithm can be adapted (uses arrays of ints or floats, properties of the bits)).

I'm a poor college student, and I've already exceeded my yearly splurge cash. No more books :D

Thanks for the radix link, I wouldn't have thought of that.