Simple and Efficient Traversal Methods for Quadtrees and Octrees

Sarah F. Frisken and Ron Perry
Mitsubishi Electric Research Laboratories

This paper appears in issue Volume 7, Number 3.
Purchase this issue from the akpeters.com web site.

Abstract

Quadtrees and octrees are used extensively throughout computer graphics and in many other diverse fields such as computer vision, robotics, and pattern recognition. Managing information stored in quadtrees and octrees requires basic tree traversal operations such as point location, region location, and neighbor searches. This paper presents simple and efficient methods for performing these operations that are inherently nonrecursive and reduce the number of comparisons with poor predictive behavior. The methods are table-free, thereby reducing memory accesses, and generalize easily to higher dimensions. Source code is available online.

Author Information

Sarah F. Frisken, Mitsubishi Electric Research Laboratories, 201 Broadway, 8th Floor, Cambridge, MA 02139 frisken@merl.com

Ron Perry, Mitsubishi Electric Research Laboratories, 201 Broadway, 8th Floor, Cambridge, MA 02139 perry@merl.com

Source Code

C source code for the point location and region location methods and three example neighbor searches is available here: treeTraversal.c (17K HTML text)

BibTeX Entry

@article{FriskenPerry02,
  author = "Sarah F. Frisken and Ron Perry",
  title = "Simple and Efficient Traversal Methods for Quadtrees and Octrees",
  journal = "journal of graphics, gpu, and game tools",
  volume = "7",
  number = "3",
  pages = "1-11",
  year = "2002",
}