BOXTREE: A Hierarchical Representation for Surfaces in 3D
Gill Barequet, Bernard Chazelle, Leonidas Guibas, Joseph S. B. Mitchell, Ayellet Tal · Computer Graphics Forum · 1996
Abstract We introduce the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D. A boxtree is a hierarchical structure of nested boxes that supports efficient ray tracing and collision detection. It is simple and robust, and requires minimal space. In situations where storage is at a premium, boxtrees are effective alternatives to octrees and BSP trees. They are also more flexible and efficient than R‐trees, and nearly as simple to implement.