8 replies to this topic

[p0pes]

I've been working through learning collision detection and implementing some stuff. Specifically I'm using "Real Time Collision Detection" by Ericson. I'm just curious what type of spatial partitioning is typically used. I know the type probably depends on the what its going to be used for but is there any general thought of whats best/most common (Octree, Grid, etc.) If helps I'm going to first test it out on something similar to here (need WebGL enabled browser to run), http://dl.dropbox.co...ollingBall.html Basically, I just want to make a pretty big room with a bunch of objects and be able to simulate a ball bouncing and rolling around.

[Plex]

I would use an Oct-Tree (More general term is an R-Tree) when there is no tile map. And some sort of grid when I have a tilemap. I dont have a webgl browser & the iink you provided doesn't work. From your description if the room is always a manageable size I might go with having a grid. If the level is pretty big, than an oct-tree.

I just want to make a pretty big room with a bunch of objects and be able to simulate a ball bouncing and rolling around.

Sounds like a 2D room with 3D rendering, perhaps an Oct-Tree with ignoring the Y-Axis (Making it a quad-tree).

I only worked with Grid, and BSP-tree. BSP seems the most useless for games. I only learned about Oct-tree's never actually used them. The levels I made were all tile maps so partitioning all objects to a grid felt natural to the design.

[Bow_vernon]

For object-object partitioning, sweep and prune might be the way to go. For level-object collision, octree should do. My level is composed of triangles, and they're stored in a octree. I've never actually implemented sweep and prune, but I heard good things about them...

[kdmiller3]

There's no one "best" spatial partitioning technique for collision broadphase since each one has strengths and weaknesses. It depends on what you're trying to do.

To answer the original question, though, sweep-and-prune and bounding-volume hierarchies seem to be the most common techniques.

Here's some I've seen in actual use along with a few off-the-cuff descriptions:

• none (ODE dSimpleSpace)
  • fine for a small number of objects
  • slows down drastically as the number of objects goes up (O(N²))
• uniform grid (used by some tile-based games like N+)
  • good match for worlds naturally divided into tiles
  • allows efficient raycasts with with digital differential analyzer (DDA) algorithms
  • requires a pre-defined world size
  • can use a lot of memory (especially for a 3D grid--not advisable!)
  • doesn't handle objects larger than the grid very well (must add them to multiple cells)
• multi-resolution grid
  • different uniform grids for different-sized objects
• spatial hashing (what Chipmunk uses; ODE dHashSpace)
  • variant of uniform grid that stores grid cells in a hash table instead of a fixed 2D or 3D array
  • no longer requires a fixed world size
  • memory usage proportional to number of objects, not world size
• sweep and prune / sort and sweep (what Box2D used to use; Bullet btAxisSweep3; ODE dSAPSpace)
  • takes advantage of spatial and temporal coherence for efficiency
  • great for detecting colliding pairs of objects
  • not as good at handling raycasts
  • straightforward implementations break down for very-fast-moving objects
• bounding volume hierarchy / AABB tree (what Box2D currently uses; Bullet btDbvtBroadphase; Newton Game Dynamics)
  • no pre-defined limit on world size
  • efficient spatial queries (i.e. finding all objects in a specified area/volume)
  • may require periodic re-balancing unless the scene is static
• quadtree / octree (ODE dQuadTreeSpace)

Erwin Coumans, author of Bullet, posted some useful information in this thread.
StackOverflow has a good thread on this too.

[NEXUSKill]

I would use an Oct-Tree (More general term is an R-Tree) when there is no tile map. And some sort of grid when I have a tilemap. I dont have a webgl browser & the iink you provided doesn't work. From your description if the room is always a manageable size I might go with having a grid. If the level is pretty big, than an oct-tree.

I just want to make a pretty big room with a bunch of objects and be able to simulate a ball bouncing and rolling around.

Sounds like a 2D room with 3D rendering, perhaps an Oct-Tree with ignoring the Y-Axis (Making it a quad-tree).

I only worked with Grid, and BSP-tree. BSP seems the most useless for games. I only learned about Oct-tree's never actually used them. The levels I made were all tile maps so partitioning all objects to a grid felt natural to the design.

BSP seems most useless for games?? You're probably thinking of a limited spectrum of game types, BSP has fueled decades of in-doors FPS game engines right up until portals became popular, and many still use BSP trees

[p0pes]

First off thanks for the tips. I'm actually working with a large 3D room so I don't think a uniform grid would work. I started to code that up, but since my testing is in WebGL/Javascript its kinda slow and I can't do much more than a 100x100x100 grid. Since I'm really just trying to learn I guess I'll try a few others. Possibly the Octree first then try sweep & prune. I'll let you know what I liked/worked best. Thanks again.

[kdmiller3]

A 100x100x100 3D uniform grid is way larger than you would want to use unless you've implemented spatial hashing. Most of those cells would be empty, wasting memory unnecessarily. Unless you have a lot of vertically-positioned obstacles, you could easily get away with a 100x100 2D uniform grid. Even then I would recommend a lower-resolution grid or spatial hashing since I doubt your room has 10,000 objects in it.

It's fine to have a relatively loose collision broad-phase that returns false positives if it saves more processing cost than the extra narrow-phase collision tests it causes.

[Sneftel]

I would use an Oct-Tree (More general term is an R-Tree) when there is no tile map.

As a side note, octrees and R-trees are completely different data structures. R-trees are designed for range-searching very large databases of spatial information, and are the multidimensional analogue of B-trees. They're not widely useful for games.

[Antheus]

I started to code that up, but since my testing is in WebGL/Javascript its kinda slow

You will notice that none of the demos have collision detection. There is a reason for that. Despite being called "fast", JavaScript is abysmally slow for this type of tasks.

Unless you implement it fully as a shader, the geometry collision detection isn't viable. So instead implement pseudo collision, such as testing against 2D plane that describes the floor.

JavaScript/WebGL is a pipedream that doesn't come close to what could be done on a 386. It's a nice concept, but it's wrong on so many levels that no amount of tweaking can fix that. Approximations and faking is the only viable way.