Octree Creation Bottom-Up

Research archive · original page Research.Octrees · last recorded update 2009-11-15

This is a better method for creating octrees by a bottom-up approach instead of using top-down subdivision. The idea is to intersect 1-D rays with the object, split the part of each ray that is inside the object into bintrees, group adjacent bintrees into quadtrees, then group adjacent quadtrees into octrees. This whole process has a systolic computation flavor. The advantage of this method is that it is easier to intersect the object with a line than with a cube. (1985)

1. Wm Randolph Franklin and Varol Akman. Building an octree from a set of parallelepipeds. IEEE Computer Graphics and Applications, 5(10):58–64, October 1985.

   Paper / file · Download BibTeX

   BibTeX

   @article{fa-bospj-85,
       author = "Franklin, Wm Randolph and Akman, Varol",
       title = "Building an Octree from a Set of Parallelepipeds",
       journal = "IEEE Computer Graphics and Applications",
       month = "October",
       year = "1985",
       volume = "5",
       number = "10",
       pages = "58-64",
       fulltext = "https://wrfranklin.org/p/40-cga85-octree.pdf",
       href = "\bibhref{40-cga85-octree}",
       mykey = "akman",
       succeeds = "fa-bospi-85",
       keywords = "computer graphics, oct trees"
   }
   

2. Wm Randolph Franklin and Varol Akman. Octree data structures and creation by stacking. In Nadia Magenat-Thalmann, editor, Computer Generated Images, State of the Art. Springer-Verlag, 1985.

   Paper / file · Download BibTeX

   BibTeX

   @incollection{fa-odscs-85,
       author = "Franklin, Wm Randolph and Akman, Varol",
       editor = "Magenat-Thalmann, Nadia",
       title = "Octree Data Structures and Creation by Stacking",
       booktitle = "Computer Generated Images, State of the Art",
       publisher = "Springer-Verlag",
       year = "1985",
       fulltext = "https://wrfranklin.org/p/39-cgi85-octree-stack.pdf",
       href = "\bibhref{39-cgi85-octree-stack}",
       mykey = "akman",
       keywords = "computer graphics, oct trees"
   }
   

3. Wm Randolph Franklin and Varol Akman. Building an octree from a set of parallelepipeds. In Graphics Interface. 1985.

   Paper / file · Download BibTeX

   BibTeX

   @inproceedings{fa-bospi-85,
       author = "Franklin, Wm Randolph and Akman, Varol",
       title = "Building an Octree from a Set of Parallelepipeds",
       booktitle = "Graphics Interface",
       year = "1985",
       precedes = "fa-bospj-85",
       keywords = "computer graphics, oct trees, CAD",
       fulltext = "https://wrfranklin.org/p/29-gi85-building.pdf",
       mykey = "akman",
       href = "\bibhref{29-gi85-building}"
   }
   

4. Varol Akman and Wm Randolph Franklin. Representing objects as rays, or how to pile up an octree? Computers and Graphics, 13(3):373–379, 1989.

   Paper / file · Download BibTeX

   BibTeX

   @article{af-rorhp-89,
       author = "Akman, Varol and Franklin, Wm Randolph",
       title = "Representing Objects as Rays, or How to Pile up an Octree?",
       journal = "Computers and Graphics",
       volume = "13",
       number = "3",
       year = "1989",
       pages = "373--379",
       fulltext = "https://wrfranklin.org/p/64-cg89-rays.pdf",
       href = "\bibhref{64-cg89-rays}",
       mykey = "akman",
       keywords = "oct trees, measure, polyhedra, rays"
   }
   

5. Varol Akman and Wm Randolph Franklin. Ray representation for k-d trees. Pattern Recognition Letters, pages 315–320, November 1989.

   Paper / file · Download BibTeX

   BibTeX

   @article{af-rrkt-89,
       author = "Akman, Varol and Franklin, Wm Randolph",
       title = "Ray Representation for K-d Trees",
       journal = "Pattern Recognition Letters",
       month = "November",
       year = "1989",
       pages = "315--320",
       fulltext = "https://wrfranklin.org/p/66-prl89-ray.pdf",
       href = "\bibhref{66-prl89-ray}",
       mykey = "akman",
       keywords = "oct trees, measure, rays"
   }