Re: [Algorithms] Quadtree / Octtree neighbors
Brought to you by:
vexxed72
Menu
▾
▴
Re: [Algorithms] Quadtree / Octtree neighbors
|
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 |
