Graphics Reference
In-Depth Information
For more general planar meshes, in which the faces may not be triangles, one
can use the
winged-edge
data structure [Bau72], which associates to each edge of
the mesh the next edge of the face to its right, the next edge of the face to its left,
and the previous edges of each of these as well (see Figure 8.13). This suffices
to recover all the faces and edges, provided that all faces are simply connected
(i.e., no face has a ringlike shape, like the surface of a moat). The winged-edge
structure also stores, for each vertex, its
xyz
-coordinates, and a reference to one of
the edges that it lies on (from which one can find all other edges). For each face,
the structure stores a reference to one edge of the face (from which one can find
all the others).
Vertices
x
a
y
a
z
a
e
r
x
b
y
b
z
b
e
q
…
v
b
e
p
e
q
f
i
e
t
f
j
e
r
e
s
v
a
Faces
e
r
e
s
…
Winged edges
v
a
v
b
f
i
f
j
e
r
e
p
e
s
e
q
…
Each of the structures we've described for representing meshes has certain mem-
ory requirements. Assuming 4-byte floating-point representations and 4-byte
integers, we can compare their memory requirements as done by Campagna
et al. [CKS98].
The vertex-table-and-triangle-table approach takes 12
V
bytes for the
V
ver-
tices and 12
T
bytes for the
T
triangles. How are the number of vertices and tri-
angles related? For a mesh representing a closed surface, Euler's formula tells us
that
V
Figure 8.13: The winged-edge
data structure records a “previ-
ous” and “next” pointer for the
facesoneachsideofeachedge.
2
g
, where
g
is the
genus
of the surface.
2
Assuming further
that every vertex is actually part of some triangle (so that the vertex table does not
contain lots of unused vertices), and that the mesh is closed, we can simplify this:
Each triangle has three edges, and each edge is shared by two triangles. So the
number of edges,
E
,is
2
T
. Thus,
−
E
+
F
=
2
−
3
2
T
+
T
=
2
V
−
−
2
g
,
(8.4)
which simplifies to
1
2
T
=
2
V
−
−
2
g
.
(8.5)
For low-genus surfaces with fine tessellations, the right-hand side is negligible
compared to the left, so we find that the number of triangles is approximately twice
the number of vertices; this gets us a total of 12
(
T
+
V
)
18
T
bytes of storage. For the remaining mesh representations, we'll assume that we're
representing closed manifolds of low genus so that we can replace
V
with
2
≈
12
(
3
V
)=
36
V
≈
and
vice versa.
For the winged-edge structure, each vertex uses 16 bytes (three floats and an
edge reference); each face uses four bytes (one edge reference), and each edge has
four edge references, two face references, and two vertex references, for a total of
eight references or 32 bytes. The total, again assuming we use
triangular faces
only,
is 16
V
+
32
E
+
4
T
8
T
+
32
2
T
+
4
T
=
60
T
.
For the directed-edge data structure (in the store-all-references form), each
vertex uses 12 bytes for coordinates and four for an edge reference. Each directed
≈
2. The genus of a closed surface is, informally, the number of holes in it. A sphere has
genus zero, a torus has genus one, a two-holed torus has genus two, etc. A slice of
Swiss cheese tends to have quite high genus.
