Hughes/Computer Graphics, 3/E

Chapter 37. Spatial Data Structures

37.1. Introduction

Spatial data structures, such as the oct tree (Figure 37.1), are the multidimensional generalization of classic ordered data structures, such as the binary search tree. Because spatial data structures generally trade increased storage space for decreased query time, these are also known as spatial acceleration data structures. Spatial data structures are useful for finding intersections between different pieces of geometry. For example, they are used to identify the first triangle in a mesh that is intersected by a ray of light.

Figure 37.1: A gargoyle model embedded in an oct tree. The cube ...