i
i
i
i
i
i
i
i
266 12. Data Structures for Graphics
• Triangle. Three vectors per triangle, for 9n
t
units of storage;
• IndexedMesh. One vector per vertex and three ints per triangle, for 3n
v
+
3n
t
units of storage.
The relative storage requirements depend on the ratio of n
t
to n
v
.
Is this factor of two worth
the complication? I think
the answer is yes, and it be-
comes an even bigger win
as soon as you start adding
“properties” to the vertices.
As a rule of thumb, a large mesh has each vertex connected to about six tri-
angles (although there can be any number for extreme cases). Since each triangle
connects to three vertices, this means that there are generally twice as many tri-
angles as vertices in a large mesh: n
t
≈ 2n
v
. Making this substitution, we can
conclude that the storage requirementsare 18n
v
for the Triangle structure and 9n
v
for IndexedMesh. Using shared vertices reduces storage requirements by about a
factor of two; and this seems to hold in practice for most implementations.
12.1.3 Triangle Strips and Fans
Indexed meshes are the most common in-memory representation of triangle
meshes, because they achieve a good balance of simplicity, convenience, and
compactness. They are also commonly used to transfer meshes over networks
and between the application and graphics pipeline. In applications where even
more compactness is desirable, the triangle vertex indices (which take up two-
thirds of the space in an indexed mesh with only positions at the vertices) can be
expressed more efficiently using triangle strips and triangle fans.
Figure 12.9. A triangle
fan.
A triangle fan is shown in Figure 12.9. In an indexed mesh, the triangles
array would contain [(0, 1, 2), (0, 2, 3), (0, 3, 4), (0, 4, 5)]. We are storing
12 vertex indices, although there are only six distinct vertices. In a triangle fan,
all the triangles share one common vertex, and the other vertices generate a set
of triangles like the vanes of a collapsible fan. The fan in the figure could be
specified with the sequence [0, 1, 2, 3, 4, 5]: the first vertex establishes the center,
and subsequently each pair of adjacent vertices (1-2, 2-3, etc.) creates a triangle.
The triangle strip is a similar concept, but it is useful for a wider range of
meshes. Here, vertices are added alternating top and bottom in a linear strip as
shown in Figure 12.10. The triangle strip in the figure could be specified by the
sequence[01234567],andeverysubsequenceofthreeadjacent vertices (0-
1-2, 1-2-3, etc.) creates a triangle. For consistent orientation, every other triangle
needs to have its order reversed. In the example, this results in the triangles (0, 1,
Figure 12.10. A triangle
strip.
2), (2, 1, 3), (2, 3, 4), (4, 3, 5), etc. For each new vertex that comes in, the oldest
vertex is forgotten and the order of the two remaining vertices is swapped. See
Figure 12.11 for a larger example.
i
i
i
i
i
i
i
i
12.1. Triangle Meshes 267
p
0
p
1
p
2
p
3
p
9
p
10
p
4
p
6
p
5
p
7
p
8
p
4
p
1
p
*
verts[0] x
0
, y
0
, z
0
x
1
, y
1
, z
1
x
2
, y
2
, z
2
x
3
, y
3
, z
3
verts[1]
…
[0]
tStrips
4, 0, 1, 2, 5, 8
[1]
6, 9, 0, 3, 2, 10, 7
…
Figure 12.11. Two triangle strips in the context of a larger mesh. Note that neither strip can
be extended to include the triangle marked with an asterisk.
In both strips and fans, n +2vertices suffice to describe n triangles—a sub-
stantial savings over the 3n vertices required by a standard indexed mesh. Long
triangle strips will save approximately a factor of three if the program is vertex-
bound.
It might seem that triangle strips are only useful if the strips are very long,
but even relatively short strips already gain most of the benefits. The savings in
storage space (for only the vertex indices) are as follows:
strip length 1 2 3 4 5 6 7 8 16 100 ∞
relative size 1.00 0.67 0.56 0.50 0.47 0.44 0.43 0.42 0.38 0.34 0.33
So, in fact, there is a rather rapid diminishing return as the strips grow longer.
Thus, even for an unstructured mesh, it is worthwhile to use some greedy algo-
rithm to gather them into short strips.
12.1.4 Data Structures for Mesh Connectivity
Indexed meshes, strips, and fans are all good, compact representations for static
meshes. However, they do not readily allow for meshes to be modified. In order to
efficiently edit meshes, more complicated data structures are needed to efficiently
answer queries such as:
• Given a triangle, what are the three adjacent triangles?
• Given an edge, which two triangles share it?
i
i
i
i
i
i
i
i
268 12. Data Structures for Graphics
• Given a vertex, which faces share it?
• Given a vertex, which edges share it?
There are many data structures for triangle meshes, polygonal meshes, and polyg-
onal meshes with holes (see the notes at the end of the chapter for references). In
many applications the meshes are very large, so an efficient representation can be
crucial.
The most straightforward, though bloated, implementation would be to have
three types, Ve rtex , Edge,andTriangle, and to just store all the relationships di-
rectly:
Triangle {
Vertex v[3]
Edge e[3]
}
Edge {
Vertex v[2]
Triangle t[2]
}
Vertex {
Triangle t[]
Edge e[]
}
This lets us directly look up answers to the connectivity questions above, but
because this information is all inter-related, it stores more than is really needed.
Also, storing connectivity in vertices makes for variable-length data structures
(since vertices can have arbitrary numbers of neighbors), which are generally less
efficient to implement. Rather than committing to store all these relationships
explicitly, it is best to define a class interface to answer these questions, behind
which a more efficient data structure can hide. It turns out we can store only some
of the connectivity and efficiently recover the other information when needed.
The fixed-size arrays in the Edge and Triangle classes suggest that it will be
more efficient to store the connectivity information there. In fact, for polygon
meshes, in which polygons have arbitrary numbers of edges and vertices, only
edges have fixed-size connectivity information, which leads to many traditional
mesh data structures being based on edges. But for triangle-only meshes, storing
connectivity in the (less numerous) faces is appealing.
A good mesh data structure should be reasonably compact and allow efficient
answers to all adjacency queries. Efficient means constant-time: the time to find
i
i
i
i
i
i
i
i
12.1. Triangle Meshes 269
neighbors should not depend on the size of the mesh. We’ll look at three data
structures for meshes, one based on triangles and two based on edges.
The Triangle-Neighbor Structure
We can create a compact mesh data structure based on triangles by augmentingthe
basic shared-vertexmesh with pointers from the triangles to the three neighboring
triangles, and a pointer from each vertex to one of the adjacent triangles (it doesn’t
matter which one); see Figure 12.12:
Triangle {
Triangle nbr[3];
Vertex v[3];
}
Vertex {
// ... per-vertex data ...
Triangle t; // any adjacent tri
}
v[2]
v[0]
v[1]
nbr[1]
nbr[2]
nbr[0]
t
t
t
Figure 12.12. The ref-
erences between triangles
and vertices in the triangle
neighbor structure.
In the array Triangle.nbr, the kth entry points to the neighboring triangle that
shares vertices k and k +1. We call this structure the triangle-neighbor struc-
ture. Starting from standard indexed mesh arrays, it can be implemented with two
additional arrays: one that stores the three neighbors of each triangle, and one
that stores a single neighboring triangle for each vertex. (See Figure 12.13 for an
example):
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
T
0
[0]
[1]
[2]
[3]
…
[0]
0, 2, 1
1, 6, 7
10, 2, 0
3, 1, 12
2, 13, 4
[1]
[2]
[3]
0, 3, 2
10, 2, 3
2, 10, 7
…
…
[0]
0
[1]
[2]
[3]
6
3
1
vTri
tInd
tNbr
Figure 12.13. The triangle neighbor structure as encoded in arrays, and the sequence that
is followed in traversing the neighboring triangles of vertex 2.
i
i
i
i
i
i
i
i
270 12. Data Structures for Graphics
Mesh {
// ... per-vertex data ...
int tInd[nt][3]; // vertex indices
int tNbr[nt][3]; // indices of neighbor triangles
int vTri[nv]; // index of any adjacent triangle
}
Clearly the neighboring triangles and vertices of a triangle can be found di-
rectly in the data structure, but by using this triangle adjacency information care-
fully it is also possible to answer connectivity queries about vertices in constant
time. The idea is to move from triangle to triangle, visiting only the triangles
adjacent to the relevant vertex. If triangle t has vertex v as its kth vertex, then
the triangle t.nbr[k] is the next triangle around v in the clockwise direction. This
observation leads to the following algorithm to traverse all the triangles adjacent
to a given vertex:
Of course, a real program
would
do
something with
the triangles as it found
them.
TrianglesOfVertex(v) {
t = v.t
do {
find i such that (t.v[i] == v)
t = t.nbr[i]
} while (t != v.t)
}
This operation finds each subsequent triangle in constant time—even though a
search is required to find the position of the central vertex in each triangle’s vertex
list, the vertex lists have constant size so the search takes constant time. However,
that search is awkward and requires extra branching.
Asmallrefinement can avoid these searches. The problem is that once we
follow a pointer from one triangle to the next, we don’t know from which way
we came: we have to search the triangle’s vertices to find the vertex that con-
nects back to the previous triangle. To solve this, instead of storing pointers to
neighboring triangles, we can store pointers to specific edges of those triangles by
storing an index with the pointer:
Triangle {
Edge nbr[3];
Vertex v[3];
}
Edge { // the i-th edge of triangle t
Triangle t;
int i; // in {0,1,2}
}
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.