Re: [Algorithms] Octree leaf neighbours

[Michael K. <neg...@ea...>]

Sam,

 Array traversal is actually just simple math using indexes.

 let me illustrate with a 3x3x3 array that is squashed down into a one
dimensional array.

bottom     middle            top
0 1 2   |    9 10 11    |   18 19 20
3 4 5   |   12 13 14   |   21 22 23
6 7 8   |   15 16 17   |   24 25 26


to get from the bottom layer to the middle layer you just have to add 9 to
the index, to go the right neighbor add 1, bottom neighbor add 3, left
neighbor subtract 1, etc.. I've used this in a quadtree terrain algorithm to
traverse from the top node all the way down to the lowest layer all within a
single array that was logically 256x256 and only using simple math. I'm sure
you can extend it into 3 dimensions, but it may not work for an octree very
well since it would require the octree to be fully divided, depending on
your reason for using an octree of course. You can also test if an index is
negative to traverse into neighboring arrays, usefull for patching terrain
together.


----- Original Message -----
From: Sam Kuhn <sa...@ip...>
To: <gda...@li...>
Sent: Sunday, July 16, 2000 12:29 PM
Subject: Re: [Algorithms] Octree leaf neighbours


> >Martin Gladnishki wrote:
> >And in addition you can save much time if you hold the tree in an array.
> This
> >saves the parent links, too :)
>
> Erm, I mentioned this in my origional post... dont you have to store a 3d
> (i.e. *big*) hash table so you can hash to the neighbours in the array
using
> the coordinates of the node you are in?
> How does it save the parent links then?
>
> sam
>
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>