Data Structures for Graphics
Steve Marschner, Peter Shirley, Michael Ashikhmin, Michael Lee Gleicher, Naty Hoffman, Garrett M. Johnson, Tamara Munzner, Erik Reinhard, William B. Thompson, Peter Willemsen, Brian Wyvill · 2018
This chapter talks about several basic and unrelated categories of data structures that are among the most common and useful: mesh structures, spatial data structures, scene graphs, and tiled multidimensional arrays. It discusses the basic storage schemes used for storing static meshes and for transferring meshes to graphics application program interfaces. The chapter also discusses the winged-edge data structure and the related half-edge structure, which are useful for managing models where the tessellation changes, such as in subdivision or model simplification. It focuses on the simpler case of triangle meshes here, though these methods generalize to arbitrary polygon meshes. The chapter provides information on various approaches to organizing models in 3D space—bounding volume hierarchies, hierarchical space subdivision, and uniform space subdivision—and the use of hierarchical space subdivision for hidden surface removal. The same methods are also used for other purposes, including geometry culling and collision detection.