Octrees
Author
I'm thinking about using octrees for collision detection. my question is:
what do i do to bodies that are moving? do i take them out of the tree and put them back in every frame? or do i give the body a pointer to the cell it's in so that it can check if it's still inside and only remove itself when it has to? what's the best way?
Thanks.
You can do it either way. Checking to see if you can move the object without changing the tree around is an optimization - but usually it's a simple one, so get it working first by removing the object from the tree and adding it back in, then optimize it.
If body will not move, it will stay in the cell of the tree. If you meant something like a creation of an octree in every frame, then it's waste of resources.
In fact object doesn't need a reference at the octree cell, it might be actually dangerous if you'd implement merging of octree cells, it knows in what cell it's because it knows its own position, so the only requirement is a test if the object crossed cell boundary.
Actually octree have few bad properties.
They are wasting memory.
Quad tree is often sufficient.
Spanish moss is often better.
Clutter in the middle.
In fact object doesn't need a reference at the octree cell, it might be actually dangerous if you'd implement merging of octree cells, it knows in what cell it's because it knows its own position, so the only requirement is a test if the object crossed cell boundary.
Actually octree have few bad properties.
Quote:Original post by RagharThey are wasting memory.
Tree's don't necessarily require any parent or child pointers if you do not plan on using tree rotation/reordering techniques. If memory is a concern consider how much can be saved with an implicit tree structure - 16 or more bytes per node can be eliminated from a quad-tree and 32 or more bytes per node from an oct-tree. Granted that an implicit tree reserves space for empty nodes, this is still often a reasonable tradeoff.
Implicit tree structures additionally offer operations that are not computationally feasable with explicit structures. You basically get all the linear O(1) and O(n) benefits of uniform grids while additionally getting many of the O(log n) and O(n log n) walking benefits of a tree.
I do agree that for most 3D games quad-tree's are a lot more efficient memory-wise than oct-tree's since the gaming field is often a pancake.
Quote:Original post by Rockoon1Implicit trees do not require dense storage. You can have sparse implicit trees by hashing on the location key of a node. Not surprisingly, we called this the hashed storage method for (implicit) trees.
Tree's don't necessarily require any parent or child pointers if you do not plan on using tree rotation/reordering techniques. If memory is a concern consider how much can be saved with an implicit tree structure - 16 or more bytes per node can be eliminated from a quad-tree and 32 or more bytes per node from an oct-tree. Granted that an implicit tree reserves space for empty nodes, this is still often a reasonable tradeoff.
Quote:Implicit tree structures additionally offer operations that are not computationally feasable with explicit structures. You basically get all the linear O(1) and O(n) benefits of uniform grids while additionally getting many of the O(log n) and O(n log n) walking benefits of a tree.Correct. But it's worth noting that hierarchical grids practically have additional benefits on top of implicit trees, most notably that you're not wasting search effort on an often-empty top of a tree.
Quote:Original post by Christer Ericson
Implicit trees do not require dense storage. You can have sparse implicit trees by hashing on the location key of a node. Not surprisingly, we called this the hashed storage method for (implicit) trees.
Ah. Good idea. Had not considered this strategy.
My first instinct when implimenting an implicit tree with a large node structure is for the tree to hold pointers to the node structure (overhead of 4 bytes per node) which is no better than anti-collision overhead with your hashing strategy.
Obviously the hashing method only has overhead for populated nodes so its a big footprint win vs my instincts. I am wondering about cache performance however. Do you use a hash function which maintains locality?
[Edited by - Rockoon1 on January 8, 2007 1:13:31 PM]
Quote:Original post by Christer EricsonQuote:Original post by Rockoon1Implicit trees do not require dense storage. You can have sparse implicit trees by hashing on the location key of a node. Not surprisingly, we called this the hashed storage method for (implicit) trees.
Tree's don't necessarily require any parent or child pointers if you do not plan on using tree rotation/reordering techniques. If memory is a concern consider how much can be saved with an implicit tree structure - 16 or more bytes per node can be eliminated from a quad-tree and 32 or more bytes per node from an oct-tree. Granted that an implicit tree reserves space for empty nodes, this is still often a reasonable tradeoff.Quote:Implicit tree structures additionally offer operations that are not computationally feasable with explicit structures. You basically get all the linear O(1) and O(n) benefits of uniform grids while additionally getting many of the O(log n) and O(n log n) walking benefits of a tree.Correct. But it's worth noting that hierarchical grids practically have additional benefits on top of implicit trees, most notably that you're not wasting search effort on an often-empty top of a tree.
Can you describe the hashed-storage implicit tree structure in more detail? I'm very interested in using this in some code I have already that relies on an octree...
Quote:Original post by playmesumch00nsYou should just search for "location code" but, in short, a location code is a "street address" of a node in an octree/quadtree. You can form the location code in several different ways, but a simple one (for this particular purpose) is to concatenate, each time you move to an octree cublet, three bits representing which cubelet you moved to (000, 001, through 111). These are concatenated into a bitstring that's initially 1, so as not to lose leading zero bits if your first move is to e.g. 010. (This is not the most sophisticated location code but it's easy to explain, so do search for info on other variants.)
Can you describe the hashed-storage implicit tree structure in more detail? I'm very interested in using this in some code I have already that relies on an octree...
Once you have the location code of the leaf cell, you treat it as a normal hash key into a hash table, wherein you store the leaf node contents. Nothing more complicated than that.
To rockoon1: it's hard to find a hash mapping that's both cache-coherent and has a good distribution to avoid worst-case behavior, thus I just use a "normal" hash mapping. So, yes, there's an extra indirection for each leaf-node lookup for the hashed-storage vs. the complete-storage linear octree, likely causing one extra cacheline miss. That's pretty much the usual time/space tradeoff though. It's still vastly superior to a traditional pointer-based tree, which can have a cache miss every time you go down a level of the tree (in the most naive implementation).
OK gotcha. So you just use the location code to lookup the hash table to get the actual memory address of the node contents in the sparse tree?
Quote:Original post by playmesumch00nsYes, if I follow you correctly. Restated: you have a linear octree. You traverse it to a leaf, forming a location code. At this point you hash the location code into a hash key, said hash key you use to look up an array entry in your hash table where you'll find the leaf node contents stored.
OK gotcha. So you just use the location code to lookup the hash table to get the actual memory address of the node contents in the sparse tree?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
