I have a cube that can be split into 8 smaller cubes which can in turn be split infinitely. How do I get all adjacent leaf nodes regardless of how deep their branches go? One way I can think to do this would be to find the common parent and retrieve the adjacent nodes from there. However, this sound extremely process intensive. What is the fastest way to do this?
How to get adjacent nodes within an Octree?
It can be a bit intensive to do it on the fly, with some gymnastics... But you can pre-compue this.
I would do it like this: have an octree with the same deep everywhere (this might ease the process). Then calculate them the way you said, and stores all the neighbors to your leaves, so that each node will have 4 pointers to the front, back, left and right neighbors. You can then easily reuse them.
You will at some point need to go to a node's parent to find it's children to work out which node is next to the node your currently in. Whether you want each child node to have pointers to its neighbours and pre-compute the results like Silence said, or just call the parent at runtime to compute the result I think is a question you would want to think about.
If you're storing pointers to other neighbouring nodes then you will be using more memory (if you are having a large/infinite number of levels, could be a lot of extra memory used), but it might be quicker as you can pre-compute the result.
Do you have a 'complete' oct-tree, where every single possible node exists down to some depth?
If so, there's two main ways you could be storing them in an array --
Breadth first: [font='courier new']Root A B C D AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD AAA AAB AAC AAD ABA ...[/font]
or
Depth first: [font='courier new']Root A AA AAA AAB AAC AAD AB ABA ABC ABD AC ACA ACB ACC ACD AD ADA ADB ADC ADD B BA BAA ...[/font]
Where [font='courier new']Root[/font] is the root node, it's children are [font='courier new']A/B/C/D[/font], and [font='courier new']A[/font]'s children are [font='courier new']AA/AB/AC/AD[/font], etc...
And yes, if this is a complete oct-tree where every node exists, you should be storing them in a single, contiguous array with no pointers. Indices are enough to identify them.
To address a particular node, you can use a series of indices. Zero indices = the root node. One index (i) = one of the root's children. Two indices (i,j) = one of the root's children's children, etc...
If you're using breadth first storage, then the lookups are something like:
Edit: just realized I used a quadtree example... But it's the same for octree
If so, there's two main ways you could be storing them in an array --
Breadth first: [font='courier new']Root A B C D AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD AAA AAB AAC AAD ABA ...[/font]
or
Depth first: [font='courier new']Root A AA AAA AAB AAC AAD AB ABA ABC ABD AC ACA ACB ACC ACD AD ADA ADB ADC ADD B BA BAA ...[/font]
Where [font='courier new']Root[/font] is the root node, it's children are [font='courier new']A/B/C/D[/font], and [font='courier new']A[/font]'s children are [font='courier new']AA/AB/AC/AD[/font], etc...
And yes, if this is a complete oct-tree where every node exists, you should be storing them in a single, contiguous array with no pointers. Indices are enough to identify them.
To address a particular node, you can use a series of indices. Zero indices = the root node. One index (i) = one of the root's children. Two indices (i,j) = one of the root's children's children, etc...
If you're using breadth first storage, then the lookups are something like:
GetLayer1(i) { return 1+i }
GetLayer2(i,j) { return 1+4+i*4+j }
GetLayer3(i,j,k) { return 1+4+16+i*16+j*4+k }Edit: just realized I used a quadtree example... But it's the same for octree
I have used a dynamic non-complete loose octree for collision detection. Each node had pointers to 26 neighbours, where the neighbour was either equal or larger in size (if it has no children).
That was pretty complex to implement, but fast because not everything changes in the octree even whan all objects move.
To find all collisions of course i had to traverse neighbours with children downwards to find all adjacent cells, but that's rarely and you never have to go up to the root.
Updating the neighbour pointers took most of the time - this time was linear related to object count.
Unfortunately i have not compared performance with a 'find neighbours on the fly' approach without neighbour pointers, so i'm not sure it's really worth the big effort.
I've found this a lot simpler since I converted to an implicit linear octree, using morton codes as the node keys. At which point finding neighbours is just arithmetic.
There are a few articles on the topic, if you are interested.
At which point finding neighbours is just arithmetic.
Upvote, but this one sounds a bit misleading to me, making me think: 'Hurray! I just need to do some bit math to index any neighbour'.
Thats not true - we still need to do a search, we just replace a tree traversal with searching a hash table.
But we need efficient searching anyways, no matter if we use neighbour pointers or not.
Thinking about my collision example again, neighbour pointers have this disadvantages:
26 pointers is a lot of memory.
It might be better to temporarily find those neighbours for one node at a time and build all collision pairs for contained bodies.
We would end up finding any neighbourhood twice per frame.
Advantage:
Per frame we need to update neighbourhood only for nodes that have been added or removed.
Probably there is no simple answer, i guess for collisions in a world where most bodies don't move most nodes need no work and we get the advantage for free anyways,
so i would only mess around with this if i'm sure i have a real performance problem.
EDIT:
Nice paper on related bitmath: http://www.merl.com/publications/docs/TR2002-41.pdf
Upvote, but this one sounds a bit misleading to me, making me think: 'Hurray! I just need to do some bit math to index any neighbour'.
Yeah, sorry. I should have said "addressing neighbours". Testing for existence still requires a lookup in the hashmap.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
