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
i
i
i
i
i
i
i
i
12.1. Triangle Meshes 263
a surface in which a small neighborhood around any point could be smoothed out
into a bit of flat surface. This idea is most clearly explained by counterexample:
if an edge on a mesh has three triangles connected to it, the neighborhood of a
point on the edge is different from the neighborhood of one of the points in the
interior of one of the triangles, because it has an extra “fin” sticking out of it
(Figure 12.1). If the edge has exactly two triangles attached to it, points on the
Figure 12.1. Non-manifold
(left) and manifold (right) in-
terior edges.
edge have neighborhoods just like points in the interior, only with a crease down
the middle. Similarly, if the triangles sharing a vertex are in a configuration like
the left one in Figure 12.2, the neighborhood is like two pieces of surface glued
Figure 12.2. Non-manifold
(left) and manifold (right) in-
terior vertices.
together at the center, which can’t be flattened without doubling it up. The vertex
with the simpler neighborhood shown at right is just fine.
Many algorithms assume that meshes are manifold, and it’s always a good
idea to verify this property to prevent crashes or infinite loops if you are handed a
malformed mesh as input. This verification boils down to checking that all edges
are manifold and checking that all vertices are manifold by verifying the following
conditions:
• Every edge is shared by exactly two triangles.
• Every vertex has a single, complete loop of triangles around it.
Figure 12.1 illustrates how an edge can fail the first test by having too many tri-
angles, and Figure 12.2 illustrates how a vertex can fail the second test by having
two separate loops of triangles attached to it.
Manifold meshes are convenient, but sometimes it’s necessary to allow meshes
to have edges, or boundaries. Such meshes are not manifolds—a point on the
boundary has a neighborhood that is cut off on one side. They are not necessarily
watertight. However, we can relax the requirements of a manifold mesh to those
for a manifold with boundary without causing problems for most mesh processing
algorithms. The relaxed conditions are:
OK OK bad
Figure 12.3. Conditions at
the edge of a manifold with
boundary.
• Every edge is used by either one or two triangles.
• Every vertex connects to a single edge-connected set of triangles.
Figure 12.3 illustrates these conditions: from left to right, there is an edge with
one triangle, a vertex whose neighboring triangles are in a single edge-connected
set, and a vertex with two disconnected sets of triangles attached to it.
Finally, in many applications it’s important to be able to distinguish the “front”
or “outside” of a surface from the “back” or “inside”—this is known as the ori-
entation of the surface. For a single triangle we define orientation based on the
order in which the vertices are listed: the front is the side from which the trian-
gle’s three vertices are arranged in counterclockwise order. A connected mesh is
A
B
C
D
A
B
C
D
OK bad
Figure 12.4. Triangles
(B,A,C) and (D,C,A) are
consistently oriented,
whereas (B,A,C) and
(A,C,D) are inconsistently
oriented.
i
i
i
i
i
i
i
i
264 12. Data Structures for Graphics
consistently oriented if its triangles all agree on which side is the front—and this
is true if and only if every pair of adjacent triangles is consistently oriented.
In a consistently oriented pair of triangles, the two shared vertices appear in
opposite orders in the two triangles’ vertex lists (Figure 12.4). What’s important is
consistency of orientation—some systems define the front using clockwise rather
than counterclockwise order.
Figure 12.5. A triangu-
lated Mobius band, which is
not orientable.
Any mesh that has non-manifold edges can’t be oriented consistently. But
it’s also possible for a mesh to be a valid manifold with boundary (or even a
manifold), and yet have no consistent way to orient the triangles—they are not
orientable surfaces. An example is the M¨obius band shown in Figure 12.5. This
is rarely an issue in practice, however.
12.1.2 Indexed Mesh Storage
A simple triangular mesh is shown in Figure 12.6. You could store these three
triangles as independent entities, each of this form:
Triangle {
vector3 vertexPosition[3]
}
This would result in storing vertex b three times and the other vertices twice
each for a total of nine stored points (three vertices for each of three triangles). Or
you could instead arrange to share the common vertices and store only four, re-
a
d
c
b
#
vertex 0 vertex 1 vertex 2
0(a
x
, a
y
, a
z
)(b
x
, b
y
, b
z
)(c
x
, c
y
, c
z
)
1(b
x
, b
y
, b
z
)(d
x
, d
y
, d
z
)(c
x
, c
y
, c
z
)
2(a
x
, a
y
, a
z
)
#
vertices
0
(0, 1, 2)
1
(1, 3, 2)
2 (0, 3, 1)
#
position
0(a
x
, a
y
, a
z
)
1(b
x
, b
y
, b
z
)
2(c
x
, c
y
, c
z
)
3 (d
x
, d
y
, d
z
)
(d
x
, d
y
, d
z
)(b
x
, b
y
, b
z
)
separate triangles:
shared vertices:
triangles vertices
Figure 12.6. A three-triangle mesh with four vertices, represented with separate triangles
(left) and with shared vertices (right).
i
i
i
i
i
i
i
i
12.1. Triangle Meshes 265
sulting in a shared-vertex mesh. Logically, this data structure has triangles which
point to vertices which contain the vertex data:
Triangle {
Vertex v[3]
}
Vertex {
vector3 position // or other vertex data
}
v[2]
v[0]
v[1]
Figure 12.7. The triangle-
to-vertex references in a
shared-vertex mesh.
Note that the entries in the v array are references, or pointers, to Vertex objects;
the vertices are not contained in the triangle.
In implementation, the vertices and triangles are normally stored in arrays,
with the triangle-to-vertex references handled by storing array indices:
IndexedMesh {
int tInd[nt][3]
vector3 verts[nv]
}
The index of the kth vertex of the ith triangle is found in tInd[i][k], and the
position of that vertex is stored in the corresponding row of the verts array; see
Figure 12.8 for an example. This way of storing a shared-vertex mesh is an in-
dexed triangle mesh.
Separate triangles or shared vertices will both work well. Is there a space
advantage for sharing vertices? If our mesh has n
v
vertices and n
t
triangles, and
if we assume that the data for floats, pointers, and ints all require the same storage
(a dubious assumption), the space requirements are:
p
0
p
1
p
2
p
3
p
9
p
10
p
4
p
6
p
5
p
7
p
8
T
0
0
2
1
T
1
2
2
2
1
1
1
0
0
0
T
7
T
8
T
9
T
10
T
T
12
T
13
T
15
16
T
17
T
18
T
19
T
2
T
3
T
4
T
5
T
6
verts[0]
verts[1]
verts[2]
verts[3]
tInd[0]
tInd[1]
tInd[2]
tInd[3]
0, 2, 1
0, 3, 2
10, 2, 3
2, 10, 7
…
x
0
, y
0
, z
0
x
1
, y
1
, z
1
x
2
, y
2
, z
2
x
3
, y
3
, z
3
…
Figure 12.8. A larger triangle mesh, with part of its representation as an indexed triangle
mesh.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.