Graphics Reference
In-Depth Information
(a)
(b)
Figure 12.28
(a) A simple polyhedron. (b) A nonsimple polyhedron (of genus one).
sphere with zero or more handles, with the number of handles determined by the
genus. An extended version of Euler's formula, which holds for polyhedra of any
genus (
G
), is the
Euler-Poincaré formula
:
V
+
F
−
E
=
2
(
1
−
G
)
.
=
1. It therefore satisfies the Euler-Poincaré formula. For the Euler-Poincaré formula to
apply, all polyhedral faces must be bounded by a single loop of connected vertices;
that is, be homeomorphic to disks. The faces cannot be rings or otherwise have holes
in them. In addition, both formulas only apply to manifold geometry, and thus it is
assumed that each edge is shared by exactly two faces, that each edge is connected
to exactly two vertices, and that at least three edges join at each vertex.
Because the flattening of a polyhedron into the plane does not change the number
of vertices, faces, or edges, Euler's formula also applies to planar graphs in general,
and polygon meshes in particular. Note, however, that when flattening, for example,
a cube into the plane one face of the cube corresponds to the unbounded surface
outside the flattened figure. Therefore, when working with planar graphs either the
unbounded face must be included in the face count or the formula has to be adjusted
to account for one less face.
Several useful expressions can be derived from Euler's formula. Consider first a
closed all-triangle mesh. For such a mesh, the relationship
E
For the nonsimple polyhedron in Figure 12.28b,
V
=
16,
F
=
16,
E
=
32, and
G
3
F
/2 holds because
there are three edges per face, but an edge is also part of two faces. For an arbitrary
closed mesh, each face is bounded by at least three edges that all are part of two
faces and the expression thus becomes
E
=
3
F
/2. Solving Euler's formula for
E
and
F
,
respectively, and substituting in this expression gives that
F
≥
≤
−
≤
−
6
for arbitrary closed meshes. If the closed mesh consists solely of triangles, the number
2
V
4 and
E
3
V
