Graphics Reference
In-Depth Information
Table 12.1
Relationships between the number of edges, vertices, and faces of a closed mesh
derived from Euler's formula.
For a
closed
(manifold) mesh
the number of edges (
E
)
consisting of a number of…
and vertices (
V
) and faces relate as…
triangles (
T
)
2
E
=
3
T
,
T
=
2
V
−
4,
E
=
3
V
−
6
quads (
Q
)
2
E
=
4
Q
,
Q
=
V
−
2,
E
=
2
V
−
4
=
+
=
−
−
triangles (
T
) and quads (
Q
)
2
E
3
T
4
Q
,
T
2
V
2
Q
4
≥
≤
−
≤
−
arbitrary convex faces (
F
)
2
E
3
F
,
F
2
V
4,
E
3
V
6
of edges relate to the number of triangles (
T
)as2
E
=
3
T
and the corresponding
formulas become
T
6. If the mesh instead consists of a
number of quads only, edges relate to the number of quads (
Q
)as2
E
=
2
V
−
4 and
E
=
3
V
−
=
4
Q
and the
formulas become
Q
=
V
−
2 and
E
=
2
V
−
4. For a closed mesh that may consist
of both triangles and quads, 2
E
4. These
relationships between the number of edges, vertices, and faces are summarized in
Table 12.1.
Euler's formula, and the formulas derived from it, can all be used to help check if
a mesh is well formed. It is important to note that these formulas can only serve as
necessary but not sufficient validity conditions in that a malformed mesh could by
chance meet the restrictions of the formulas. The formulas should therefore be used
in conjunction with other constraint checks for full validity checking.
As an example of how the formulas can be used in validity checking, consider
the two cubes in Figure 12.29. Both cubes have been somewhat inefficiently modeled
using nine vertices. The cube in Figure 12.29a is correctly modeled, with six quads and
two triangles. The cube in Figure 12.29b, however, has been incorrectly modeled, with
a t-junction on the top face (the resulting crack shown in gray). This cube consists of
five quads and three triangles.
If the edge counts are known, 15 for the left cube and 16 for the right, Euler's
formula gives 9
=
3
T
+
4
Q
, and therefore
T
=
2
V
−
2
Q
−
1 for
the right cube. Thus, the left cube satisfies the formula, whereas the right one does
not. However, in many cases the representation used does not directly give the edge
counts, only the face and vertex counts. In this case, because the cubes consist of
triangles and quads only the number of edges can be computed using the formula
E
+
(6
+
2)
−
15
=
2 for the left cube and 9
+
(5
+
3)
−
16
=
4
Q
)/2 derived earlier. For the left cube, this gives 15 edges, and for the right
cube 14.5 edges. Because the number of edges must be integral, again something is
wrong with the right cube. Consequently, whether edge counts are available or not,
in both cases the conclusion must be that the right cube cannot have been correctly
modeled.
Another way of detecting the problem is to note that for a closed manifold triangle
mesh the number of triangles must be even, as
T
=
(3
T
+
=
−
2
V
4 is always an even number.
