Sign in to follow this  

Proper implementation of Octrees for collision detection?

This topic is 3378 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

(big, over-descriptive post :D) Some time ago I was looking around for ways to manage objects and somebody recommended octrees. I couldn't find anything that practically implemented it anywhere (at least not in a way I was likely to readily understand) so I went ahead and wrote a very basic octree class. This is the way I currently use it: Every solid object performs a test every step to locate itself in space, i.e. it basically associates itself to the nearest node in the tree. It's just an integer ID so while checking for collisions, this value is the first one that is checked. I figured this would be simpler than to have to make an array of pointers for every node. But here's the problem: When some object's bounding sphere is spread across several partitions, the collisions don't happen as wanted. Obviously, the little projectiles associated with a certain node don't collide with a big object that's associated with a neighboring node even though it shoots through parts of it. The only straightforward "solution" I can think of is to split the bounding sphere up into smaller spheres and have every one of them check for their spatial IDs. Then in the checking bit, I'd have to cycle through all the spheres to check with ones intersect with the projectiles path, if the IDs match. This is probably a very stupid thing to do because having everything check their positions every step is inefficient as it is. And the problem is still likely to persist (but to a lesser extent). So I guess the main problem is that large objects have parts of it protruding into a projectile's octant without actually being in the same logical spatial partition, and no collision happens. Anyone got any suggestions/methods I might try? The way I'm currently using the tree is quite literal. I just went ahead and made a static tree and if I render it, it looks like a gigantic.. well, tree. Also, having every object find it's node every step doesn't seem like too much of an efficient way to me. Am I doing it right at all? Thanks in advance.

Share this post


Link to post
Share on other sites
you need to reference the object in each node that overlap your object. If it is for dynamic geometry, then I would not use octree.

Or even for static geometry. I'd use a loose AABB tree instead (or a loose KD tree, same thing). This ensures your object is only referenced once in your tree, the drawback is that the nodes have varying bounding box size. The good news is, you dont have to mess about with object reference, and that your tree size is bound by the number of objects you have (iirc, 2 * number of objects -1).

Share this post


Link to post
Share on other sites
Hmm.. Multiple object references, you say.. I was hoping to avoid actually referencing an object so I implemented an identification system that's only relevant to the tree. But if I were to find out which nodes the object overlaps, how do I go about it? The node selection is based on a single point (the sphere's center). It seems pretty expensive to have to find out which partitions the sphere actually intersects. How is this generally done?

I am looking into AABB trees now. Thanks.

Share this post


Link to post
Share on other sites
It's probably best to use the bounding box around your sphere and use that. Then it becomes trivial. The thing is, your sphere is a volume. Something that intersects with your sphere volume will most likely not contain the sphere center, so basing your space partitioning around the sphere centre alone wont work in many cases.

Since a volume can overlap many branches of an octree, your sphere could be referenced in many leaves. It also implies that your tree will need a depth limit, as you cannot guarantee that you'll have one object referenced per leaf (if two object's bounding boxes already overlap).

Another solution if you want to reference the object only once, is to store the objects at any level in the tree.

All in all, a 'loose' configuration is probably best.

Share this post


Link to post
Share on other sites
For dynamically moving objects I can heartily recommend the Dynamic Bounding Volume Tree found in Bullet 2.70, or at least use the implementation as reference.

We've tried numerous data structures, and even though we have a totally different collision engine, the DBVT performs the best under pretty much all game related situations, at least for us.

Share this post


Link to post
Share on other sites

This topic is 3378 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this