Thread: Re: [Algorithms] Quadtree / Octtree neighbors
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Sam K. <sa...@ip...> - 2000-08-04 12:36:11
|
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 |
|
From: Kelvin M. <ke...@re...> - 2000-08-04 19:00:23
|
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 |
|
From: Leigh M. <lei...@ro...> - 2000-08-04 19:42:06
|
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 > |
|
From: Sam K. <sa...@ip...> - 2000-08-04 22:17:46
|
How do you mean "big gain in footprint"? memory footprint? Say you subdivide and octree down about 7 levels thats (64*64*64*SizeOfNode) or (16384*SizeOfNode) of memory. Which I guess is not too bad, if the node size is fairly small. However if you subdivide an octree down 10 levels thats (512*512*512*SizeOfNode) or (134217728*SizeOfNode), which is horrendous. Ither way, this method is surely taking more memory. Also I don't know if it will be any more cache friendly, because you are still jumping about considerably in memory (Expecially reading "up and down"). Sam Kuhn I!Play Ltd. sa...@ip... -----Original Message----- From: Leigh McRae <lei...@ro...> To: gda...@li... <gda...@li...> Date: 04 August 2000 8:47 PM Subject: Re: [Algorithms] Quadtree / Octtree neighbors > 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 >> > > >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X