Sign in to follow this  

How to get adjacent nodes within an Octree?

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

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?

Share this post


Link to post
Share on other sites

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.

Edited by _Silence_

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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:
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  }
If you know the index of the current node, you can decompose that index into i/j/k/etc, modify those coordinates, then compute a new index from the modified coordinates in order to find a neighbouring node. There's no need to use pointers at all (having 6 neighbour pointers per node for a depth-8 octree is 3MB of useless overhead!!)

Edit: just realized I used a quadtree example... But it's the same for octree

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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

Edited by JoeJ

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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