Fundamentals of Computer Graphics, 3rd Edition

i

i

i

i

i

i

i

i

12

Data Structures for Graphics

Certain data structures seem to pop up repeatedly in graphics applications, per-

haps because they address fundamental underlying ideas like surfaces, space, and

scene structure. 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.

For meshes, we discuss the basic storage schemes used for storing static

meshes and for transferring meshes to graphics APIs. We also discuss the winged-

edge data structure (Baumgart, 1974) and the related half-edge structure, which

are useful for managing models where the tessellation changes, such as in sub-

division or model simplification. Although these methods generalize to arbitrary

polygon meshes, we focus on the simpler case of triangle meshes here.

Next, the scene-graph data structure is presented. Various forms of this data

structure are ubiquitous in graphics applications because they are so useful in

managing objects and transformations. All new graphics APIs are designed to

support scene graphs well.

For spatial data structures, we discuss three approaches to organizing models

in 3D space—bounding volume hierarchies, hierarchical space subdivision, and

uniform space subdivision—and the use of hierarchical space subdivision (BSP

trees) for hidden surface removal. The same methods are also used for other

purposes including geometry culling and collision detection.

Finally, the tiled multidimensional array is presented. Originally developed

to help paging performance in applications where graphics data needed to be

swapped in from disk, such structures are now crucial for memory locality on

machines regardless of whether the array fits in main memory.

261

i

i

i

i

i

i

i

i

262 12. Data Structures for Graphics

12.1 Triangle Meshes

Most real-world models are composed of complexes of triangles with shared ver-

tices. These are usually known as triangular meshes, triangle meshes,ortrian-

gular irregular networks (TINs) and handling them efficiently is crucial to the

performance of many graphics programs. The kind of efficiency that is impor-

tant depends on the application. Meshes are stored on disk and in memory, and

we’d like to minimize the amount of storage consumed. When meshes are trans-

mitted across networks or from the CPU to the graphics system, they consume

bandwidth, which is often even more precious than storage. In applications that

perform operations on meshes, besides simply storing and drawing them—such

as subdivision, mesh editing, mesh compression, or other operations—efficient

access to adjacency information is crucial.

Triangle meshes are generally used to represent surfaces, so a mesh is not just

a collection of unrelated triangles, but rather a network of triangles that connect to

one another throughshared vertices and edges to form a single continuoussurface.

This is a key insight about meshes: a mesh can be handled more efficiently than a

collection of the same number of unrelated triangles.

The minimum information required for a triangle mesh is a set of triangles

(triples of vertices) and the positions (in 3D space) of their vertices. But many,

if not most, programs require the ability to store additional data at the vertices,

edges, or faces to support texture mapping, shading, animation, and other opera-

tions. Vertex data is the most common: each vertex can have material parameters,

texture coordinates, irradiances—any parameters whose values change across the

surface. These parameters are then linearly interpolated across each triangle to

define a continuous function over the whole surface of the mesh. However, it is

also occasionally important to be able to store data per edge or per face.

12.1.1 Mesh Topology

The idea that meshes are surface-like can be formalized as constraints on the mesh

topology—the way the triangles connect together, without regard for the vertex

positions. Many algorithms will only work, or are much easier to implement, on a

mesh with predictable connectivity. The simplest and most restrictive requirement

on the topology of a mesh is for the surface to be a manifold. A manifold mesh is

“watertight”—it has no gaps and separates the space on the inside of the surface

from the space outside. It also looks like a surface everywhere on the mesh.

We’ll leave the precise def-

initions to the mathemati-

cians; see the chapter

notes.

The term manifold comes from the mathematical field of topology: roughly

speaking, a manifold (specifically a two-dimensional manifold, or 2-manifold) is