Re: [Algorithms] Quadtree / Octtree neighbors

[Leigh M. <lei...@ro...>]

  If your Octree or Quad tree has static nodes then you can use an array of
nodes.  I use a Static Octree and Quadtrees that have all the nodes
subdivided equally.   This makes finding neighbours easy.  This could also
be a big gain in footprint.  Might even be better for locality of memory
(cache) but I am not sure.

Leigh McRae

----- Original Message -----
From: Kelvin McDowell <ke...@re...>
To: <gda...@li...>
Sent: Friday, August 04, 2000 2:58 PM
Subject: RE: [Algorithms] Quadtree / Octtree neighbors


> Thanks, i'd forgotten about that thread even though I'd read it.
>
> I was thinking of implementing a method where you figured out the tree
> transversal of of your six neighbors *as if* your octree was subdivided
> equally.  Then transversing down the actual tree for each 'potential'
> neighbor.  If you can't reach it then you've found a neighbor and add it
to
> your neighbor list.  If you reach it but it's not a leaf node then
countinue
> transvering down the relavanet directions only (ie: if you're searching
for
> the north bordering node then transverse down all the south (southeast,
> southwest, etc.) nodes until you reach leave nodes.  Add the leaves.
>
> The method you describe below seems to be simular except I start
transversal
> at the root and go down where as you go up and then down.
>
> I noticed in the 'octree leaf neighbors' thread is was mentioned that you
> have 6 neighbors.   Isn't this number is variable?
>
>
> -----Original Message-----
> From: Sam Kuhn [mailto:sa...@ip...]
> Sent: Friday, August 04, 2000 5:40 AM
> To: gda...@li...
> Subject: Re: [Algorithms] Quadtree / Octtree neighbors
>
>
> Kelvin,
>
> We had a bit of a discussion on exactly this a couple of weeks ago, check
> the archive and see if you can find anything of use.
>
> I *think* we established that other than using a cubic hash table (for the
> octree case) indexed by position of a node in 3d, and using up tons of
> memory, that the only way to achieve this is to jump back up the tree and
> down neighbouring branches to find connectivity. But as Thatcher mentions,
> this probably isn't as bad as it would seem, like half the time you are
> jumping up one level, a quater of the time 2 levels, a 8th of the time 3
> etc.. Check his post for more on this.
>
> If you find anything else, I'd be interested in hearing it.
>
> Regards,
>
> Sam Kuhn
> I!Play Ltd.
> sa...@ip...
>
>
>
> -----Original Message-----
> From: Kelvin McDowell <ke...@re...>
> To: 'gda...@li...'
> <gda...@li...>
> Date: 03 August 2000 8:52 PM
> Subject: [Algorithms] Quadtree / Octtree neighbors
>
>
> >I need to construct a graph which connects all the neighboring nodes of a
> >quadtree and octree.  For each leaf node I need to determine all the
other
> >leaves that border on it.  Does anyone know of an elegant way of doing
> this?
> >
> >Kelvin McDowell
> >
> >_______________________________________________
> >GDAlgorithms-list mailing list
> >GDA...@li...
> >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>