Octree is the best implementation out. It works fine for moving objects as long as the objects' containing node is updated correctly when the object moves. There is also the problem with which node to contain your object in:
a) Keep multiple instances of each object (one in each node that it "touches"). I.E. keep all objects in leaf nodes.
b) Keep each game object in the smallest node that completely contains it.

I'm not sure which of those is the best. I would presume (a), but it does seem a bit more complicated, and you can't use the octree to traverse data because it has multiple copies of each object.

If you don't want to use a space partition, the next best collision detection is bounding sphere and/or bounding boxes (axis aligned or not). The most important part is using a lot of trivial rejection. I always use the following 2: velocity - if the objects are not getting closer, there is not need to detect collision; and bounding sphere - simple distance test to determine if 2 objects are close enough to collide.

I'm using only bounding spheres right now, a hierarchy of spheres. Most objects just have a bounding sphere to check and we can get thousands of objects on the screen.

Laterz

Quote:Original post by ivquatch
I suspect there is a lot of space overhead in keeping a copy in each leaf that it touches, especially if the object is very large and the max leaf volume is very small.

Well, by "store a copy", I meant keep a pointer in each node. Its not really a memory problem, just a more complex algorithm for moving game objects around.

When storing objects in just the leafes that it touches, the hard part is if the object moves, you have to know all the nodes its stored in to move all of the pointers :( I'm not sure what the best way for that is... maybe keep a list of nodes inside each game object. And the easiest part is the collision detection, you need to only test collision with all objects in each leaf node.

When storing objects in the smallest node that contains them, the downside is that its a little tricky determining which node to store the object in. Its also a little weird if your octree is symmetrical about the origin, any object at the origin will be contained by the ROOT node and checked against all other nodes... because it touches the biggest 8 nodes (all children of the root). And the collision detection is a little trickier, you just have to test against all objects in nodes above and below the object, not just the leaves.

I think the "storing in leaves only" is the best option, but I can't say that I've done it before. I did, however, make an octree that dynamically subdivided sections that had clusters of objects... and quickly realized that it had virtually NO application in the real world :(
Anyways, I suggest not taking my word too much, do some research. I've seen a few papers online. Make sure you search for octree and octtree. I wish someone would tell me the correct spelling.
Haha.

Cheers.