Sign in to follow this  

Octrees and dynamic objects

This topic is 4674 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

Hello! I have this collision management system able to contain any number of (relatively) static collision, "world"- objects such as heightmaps or trees of convex hull objects. Now, This system is used to manage dynamic entities, each entity is defined by either a Sphere or an AABB. Pretty straightforward to check and manage collisions between objects and the world, but with a large number of (potentially moving) entities, it can get expensive to check against *all* other entities, so I need some kind of spatial partitioning. I figured an Octree would be the way to go, since there isn't any natural hierarchy present, but the sollutions I came up with each presented some problems... ... I'll rant know. You may skip the next part. 1. Make it a loose octree. Problem is, each entity would need to have references to each node it "belonged" to, and these would need to constantly be updated. Also, an entity on an "edge" would need to check all nodes it belonged to, making traversing between nodes really, really expensive. 2. Make a standard octree, and place each object in the node with the closest fit. Problem is, this would force every check to recursively check all parent nodes and all child nodes (though not the parents' child nodes). An entity placed on the "edge" of the initial octree division would need to check against all other objects, and all other objects would need to check against it. 3. Make a standard octree and place each object in the leaf node that the center of the object fits in. Problem with this sollution is that if you don't specify a "max radius" of the entities, you must always check the neighbouring nodes- in most cases 27 nodes in total. It would be possible to double-index entities that existed on the edges, but then we're back at the problem of keeping track of indices. ... Now, I'm not sure if I'm on the right track here, I'm not even sure if Octrees are the way to go. If anyone has tried something similar and has some warnings, hints, code, links to information... I'd very much appreciate some pointers.

Share this post


Link to post
Share on other sites
Quote:

2. Make a standard octree, and place each object in the node with the closest fit. Problem is, this would force every check to recursively check all parent nodes and all child nodes (though not the parents' child nodes). An entity placed on the "edge" of the initial octree division would need to check against all other objects, and all other objects would need to check against it.

3. Make a standard octree and place each object in the leaf node that the center of the object fits in. Problem with this sollution is that if you don't specify a "max radius" of the entities, you must always check the neighbouring nodes- in most cases 27 nodes in total. It would be possible to double-index entities that existed on the edges, but then we're back at the problem of keeping track of indices.



Hmm maybe im not getting you right, but you talk about checking agains the child nodes and the parent nodes recursivly. I don't think you need to do that, in a standard octree, an object is always guaranteed to be completely contained by a node. If it is not, it is placed in higher level node, and eventually, the root node. (This is assuming the octree size contains the entire object). So atmost, each object would have to check agains its node's childern.

But the point is, if each if your objects have a bounding volume, they should always be completely contained by a node. And hence only need to check collision agains their children.
Ofcourse this dosn't work if you are forcing all objects to the lowest level of the tree nodes or something like that (it sounds like you are). But i dont think that is a "standard" approach. And iv also never culled collision detection, so i could be completely wrong here. :-)

Hope it helps.

Share this post


Link to post
Share on other sites
Quote:
Original post by peter_b
But the point is, if each if your objects have a bounding volume, they should always be completely contained by a node. And hence only need to check collision agains their children.


... Well, no. If object A is in the complete center of the octree, it would be assigned to the root node (since it can't be completely contained by any of it's child nodes). Now, say object B moves near the center, near enough to collide with the first object but still completely inside one of the child nodes... We would miss the collision B->A if we only checked the current node and children, since A is in the parent node of B. Of course, we could constantly check if object A has any collisions (thereby catching the collision A->B), but that would *really* be a waste of processing power compared to just checking for collisions when an object actually *moves*.

Share this post


Link to post
Share on other sites
Hmm i didn't think of that.

I knew i had read about this so i checked it up. In GPG1 page 442 Dan Ginsburg mentions in his article that he, in each node of the octree, saves pointers to each of that nodes (up to) 6 neighbors. Of equal or larger size. This he claims is all the information needed to do octree collision culling as opposed to visability culling.

Hope it helps.

Share this post


Link to post
Share on other sites
Sign in to follow this