Re: [Algorithms] Octree leaf neighbours

[<SHA...@ao...>]

In a message dated 15/07/00 20:59:35 !!!First Boot!!!, sa...@ip... writes:

<< I'm creating an octree, and need to maintain pointers between neighbouring
<< *leaves*, and do it quick. The only way I can think of is to skip back up
<<the tree and down the neighbouring branches to locate each of the 6
<< neighbours. This doesn't seem very fast.

Surely you mean 7 neighbours?

 
<< There is a method called "linear octrees" which supposedly let you use the
<< so called "morton number" to directly hash a neighbour from is location in 
3
<< space. But I believe you *have to subdivide the whole octree evenly* so
<< every leaf is stored and can be hashed properly. (i.e. a 3d array!). Fat 
use
<< since the reason i'm using an octree is to avoid a memory hungry grid in 
the
<< first place, or am I missing the point?
 
 Any insights would be appriciated!
 
 Sam.
>>

Looks like you need to provide a 'pointer to parent node' member in your 
structure to allow you to go back up a step and access the current nodes 
neighbours.

In my original octree implimentation I had such a pointer but later found I 
didn't need it so I took it out.

Why do you need access a parent nodes neighbours at this point?

Your code should have dealt with that node when it was 'in play' during the 
recursive traversal procedure.

You must know of course that when you are looking at a particular node you 
have access to all of it's children or as you call them, neighbours.

Maybe I am missing something here, but isn't your octree traversal recursive?

Each node that you subdivide, are you subdividing it into 8 equal parts?


And yes you are right, if you use a linear octree you will be creating many 
more nodes than you need.

Regards,

John.