Re: [Algorithms] Octree leaf neighbours

[Sam K. <sa...@ip...>]

John,

I'm sure I mean six. Above,Below,Left,Right,Forward and Back. (Don't care
about diagonals).

Yes I am recursing through the tree, and yes each node is "in play" during
the traversal. But I'm doing a "marching cubes" type of thing, I need to
share vertices between nodes. To do that I need to look at my neighbours,
see if they have been processed, and if so use their vertex instead of
generating a new one.

Yeah, If I store a pointer to parent I can traverse "up and round" to find
my neighbour. But whether this will save me any time over just generating
new vertices and not sharing. Time to suck it and see.

Thanks,

Sam.





-----Original Message-----
From: SHA...@ao... <SHA...@ao...>
To: gda...@li...
<gda...@li...>
Date: 16 July 2000 9:47 AM
Subject: Re: [Algorithms] Octree leaf neighbours


>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.
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list