Simple and Efficient Traversal Methods for Quadtrees and Octrees

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.