Overview
In computer graphics applications, three-dimensional models are almost always represented using polygonal meshes. A mesh in its simplest form consists of a set of vertices, polygons, and optionally a number of additional vertex and polygonal attributes. The complexity of a mesh can vary from low to very high depending on requirements such as rendering quality, speed and resolution. A wide spectrum of mesh processing algorithms is used by graphics and game developers for a variety of applications such as generating, simplifying, smoothing, remapping and transforming meshes. Several types of data structures and file formats are also used to store mesh data.
This topic discusses the geometrical and topological aspects related to threedimensional meshes and their processing. It also presents important data structures and algorithms used for operations such as mesh simplification, mesh subdivision, planar embedding, and polygon triangulation.
Mesh Representation
A polygonal mesh is a set of vertices and polygonal elements that collectively define a three-dimensional geometrical shape. The simplest mesh representation thus consists of a vertex list and a polygon list as shown in Fig. 8.1. Polygons are often defined in terms of triangular elements. Since triangles are always both planar and convex, they can be conveniently used in several geometrical computations such as point inclusion tests, area and normal calculations and interpolation of vertex attributes.
The vertex list contains the three-dimensional coordinates of the mesh vertices defined in a suitable coordinate frame, and the polygon list contains integer values that index into the vertex list. An anticlockwise ordering of vertices with respect to the outward face normal direction is commonly used to indicate the front facing side of each polygon. The distinction between the front and the back faces of a polygon becomes important in lighting computations and culling operations. If the polygon list represents a set of connected triangles as in Fig. 8.1, a more efficient and compact data structure called a triangle strip may be used. The first three indices in a triangle strip specify the first triangle. The fourth index along with the previous two indices represents the second triangle. In this fashion, each remaining index represents a triangle that is defined by that index and the previous two indices.
Fig. 8.1 A cube and its mesh definition using vertex and polygon lists
Fig. 8.2 The cut-open view of the cube in Fig. 8.1 showing its representation as a triangle strip
The representation of a cube as a triangle strip is given in Fig. 8.2. The triangle strip is decoded as the set of 12 triangles {012, 123, 237, 371, 715, 154, 547, 476, 762, 624, 240, 401 g. Note that the orientation of triangles alternates between clockwise and anticlockwise in this representation. The change of orientation is corrected by reversing the direction of every alternate triangle in the list, starting from the second triangle. Thus the above list would be correctly interpreted as {012, 213,237,731,715,514, 547,746,762,264, 240, 041}. If the first triangle is defined in the anticlockwise sense, then all triangles in the corrected list will have the same orientation.
Several file formats are used in graphics applications for storing and sharing mesh data. A number of such file formats represent values in binary and compressed forms for minimizing storage space. In this section, we review some of the popular ASCII file formats that allows easy viewing and editing of mesh data. The Object (.OBJ) format was developed by Wavefront technologies. This format allows the definition of vertices in terms of either three-dimensional Cartesian coordinates or fourdimensional homogeneous coordinates. Polynomials can have more than three vertices. In addition to the basic set of commands supporting simple polygonal mesh data (Box 8.1), the .OBJ format also supports a number of advanced features such as grouping of polygons, material definitions and the specification of free-form surface geometries including curves and surfaces.
Box 8.1 OBJ File Format
Comments start with the symbol # e.g., # 3D Model definition A vertex definition starts with the symbol v and is followed by 3 or 4 floating point values. Each vertex is implicitly assigned an index. The first vertex has an index 1.
Texture coordinates are specified by the symbol vt followed by two or three floating point values in the range [0, 1]. Texture coordinates are mapped to vertex coordinates through the face (T) command. The first set of texture coordinates have an index 1.
Vertex normals are specified using the vn command. The normal components are assigned to a vertex through the face (‘f’) command. The first set of normal components is assigned an index 1.
A polygon definition uses a face command that starts with the symbol f and followed by a list of positive integers that are valid vertex indices.
The above face command has a more general form f v/vt/vn v/vt/vn v/vt/vn … that can be used to combine texture and normal attributes with vertices. Both/vt and/vn fields are optional.
The first example above defines a triangle including references to the texture and normal coordinates at the vertices. The second example attaches only texture coordinate references to each vertex, while the third example uses only the normal vectors.
Box 8.2 OFF File Format
The first line should contain the header keyword OFF
This line can be followed by optional comment lines starting with the character #
The first non-comment line should have three integer values nv, nf, ne denoting the total number of vertices, faces and edges. The number of edges (ne) is always set to 0
The above line is followed by the vertex list. The number of vertices in the list must match the number nv. The first vertex is assigned the index 0, and the last vertex the index nv—1.
Vertices can also be specified using four coordinates in homogeneous form. In this case, the header keyword should be changed to 4OFF.
The vertex list is followed by the face list. Each line contains a set of integers n, i1, i2, …in, where the first integer n gives the number of vertices of that face and the remaining integers give the face indices.
Color values in either RGB or RGBA representation can be optionally added to each face as 3 or 4 integer values in the range [0, 255] or floating point values in the range [0, 1].
The Object File Format (.OFF) is another convenient ASCII format for storing 3D model definitions. It uses simple vertex-list and face-list structures for specifying a polygonal model. Unlike the .OBJ format, this format does not intersperse commands with values on every line, and therefore can be easily parsed to extract vertex coordinates and face indices. This format also allows users to specify vertices in homogeneous coordinates, faces with more than three vertex indices, and optional colour values for every vertex or face (Box 8.2).
The Polygon File Format (.PLY) also organises mesh data as a vertex list and a face list with the addition of several optional elements. The format is also called the Stanford Triangle Format. Elements can be assigned a type (int, float, double, uint etc.), and a number of values that are stored against each element.
Box 8.3 PLY File Format
The first line in the header should contain the keyword ply. The second line specifies the file format using the format keyword.
Comments begin with the keyword comment
The total number of vertices, polygons etc. in the model definition is specified using the element keyword.
The type of each element is specified using the property keyword. The following commands specify the types of vertex coordinates.
The polygon data is usually defined using a set of vertex indices. The type specification is included in the header as
The keyword end-header is used to delimit the header information. The vertex and face lists follow this keyword. The first vertex has the index 0.
Such information is specified using a list of properties as part of the header (Box 8.3). This file format supports several types of elements and data, and the complete specification is included in the header. Parsing a PLY file is therefore considerably complex than parsing an OBJ or OFF file.
Polygonal Manifolds
The model definition files introduced in the previous section contain information about vertices, polygons, colour values, texture coordinates and possibly many other vertex and face related attributes that collectively specify the mesh geometry. As seen from the examples, list based mesh definitions often do not store any neighbourhood or connectivity information. The adjacency and incidence relationships between mesh elements define the topology of the mesh and are heavily used by several mesh processing algorithms. This section introduces some of the general and desirable topological characteristics of meshes.
Fig. 8.3 Examples of manifold meshes
Fig. 8.4 Examples of non-manifold meshes
A common assumption in the construction of mesh data structures and related algorithms is that the given mesh is a polygonal manifold. A polygonal manifold is defined as a mesh that satisfies two conditions: (i) no edge is shared by more than two faces, and (ii) the faces sharing a vertex can be ordered in such a way that their vertices excluding the shared vertex form a simple chain (Fig. 8.3).
A non-manifold mesh may contain edges shared by more than two polygons, or vertices with more than one chain of neighbouring vertices (Fig. 8.4). In a nonmanifold mesh, the neighbourhood of a point may not be topologically equivalent to a disc, which makes local adjustments surrounding that vertex difficult in many mesh processing algorithms. The methods discussed in this topic assume that the given mesh satisfies the conditions of a polygonal manifold.
The chain of vertices surrounding a vertex in a polygonal manifold is closed if the vertex is an interior vertex, otherwise the vertex is a boundary vertex. In a triangular mesh, the triangles sharing a common vertex form a closed triangle fan for interior vertices, and an open triangle fan for boundary vertices (Fig. 8.5). An interior vertex is also commonly called a simple vertex. A closed manifold that does not contain any boundary vertices is called a polyhedron.
Fig. 8.5 An interior and a boundary vertex on a polygonal manifold
Fig. 8.6 One-ring and two-ring neighbours of a vertex on a manifold mesh
Two vertices are adjacent if they are connected by an edge of a polygon. As seen in Fig. 8.5, the set of vertices that are adjacent to a vertex v in a closed manifold forms a ring. This set is called the one-ring neighbourhood of the vertex v. The union of one-ring neighbourhoods of every vertex in this set is called the two-ring neighbourhood of v (Fig. 8.6).
The orientation of the faces of a polygonal manifold is determined by the way in which its vertices are ordered. An anticlockwise ordering of vertices generally corresponds to the front face of a polygon. If two adjacent faces have the same orientation, they are said to be compatible. In this case, a common edge will have opposite directions in the two faces that share the edge (Fig. 8.7a). If every pair of adjacent faces is compatible, the mesh is said to be orientable.
The number of edges incident on a vertex is called its valence. A mesh in which every face has the same number of edges, and every vertex has the same valence is called a regular mesh.
Fig. 8.7 (a) Compatible faces in an orientable mesh. (b) The Möbius strip is an example of a non-orientable mesh
The number of vertices (V), edges (E), and faces (F) in a closed polygonal mesh are related by the Euler-Poincare formula
where g, the genus, denotes the number of holes/handles in the mesh. The right-hand side of the above equation is called the Euler Characteristic. For the torus in Fig. 8.3 and the Mobius strip in Fig. 8.7b, g = 1, and hence V C F = E. For polyhedral objects without any holes, V C F = E C 2. This equation is generally referred to as the Euler’s formula. In a triangular mesh without holes, the average valence of a vertex is six, and we can get an estimate of the number of faces and edges in terms of the vertices as
Also in a triangular mesh, every face has three edges, and every edge is counted twice while counting the number of faces. Therefore the number of faces and edges are connected by the equation E = 3 F/2.
