A polygon mesh is a collection of vertices, edges and faces that defines the shape of
a polyhedral object in 3D computer graphics and solid modeling.
The faces usually consist of triangles, quadrilaterals, or other simple convex polygons, since this
simplifies rendering, but may also be composed of more general concave polygons, or polygons
with holes.
The study of polygon meshes is a large sub-field of computer graphics and geometric modeling.
Different representations of polygon meshes are used for different applications and goals.
The variety of operations performed on meshes may include Boolean logic, smoothing, simplification,
and many others.
Network representations, "streaming" and "progressive" meshes, are used to transmit polygon meshes
over a network.
Volumetric meshes are distinct from polygon meshes in that they explicitly represent both
the surface and volume of a structure, while polygon meshes only explicitly represent the
surface.
As polygonal meshes are extensively used in computer graphics, algorithms also exist for
ray tracing, collision detection, and rigid-body dynamics of polygon meshes.
Elements of mesh modeling
Objects created with polygon meshes must store different types of elements.
These include vertices, edges, faces, polygons and surfaces.
In many applications, only vertices, edges and either faces or polygons are stored.
A renderer may support only 3-sided faces, so polygons must be constructed of many of
these, as shown in Figure 1.
However, many renderers either support quads and higher-sided polygons, or are able to
convert polygons to triangles on the fly, making it unnecessary to store a mesh in a
triangulated form.
Also, in certain applications like head modeling, it is desirable to be able to create both
3- and 4-sided polygons.
A vertex is a position along with other information such as color, normal vector and texture coordinates.
An edge is a connection between two vertices.
A face is a closed set of edges, in which a triangle face has three edges, and a quad
face has four edges.
A polygon is a coplanar set of faces.
In systems that support multi-sided faces, polygons and faces are equivalent.
However, most rendering hardware supports only 3- or 4-sided faces, so polygons are
represented as multiple faces.
Mathematically a polygonal mesh may be considered an unstructured grid, or undirected graph,
with additional properties of geometry, shape and topology.
Surfaces, more often called smoothing groups, are useful, but not required to group smooth
regions.
Consider a cylinder with caps, such as a soda can.
For smooth shading of the sides, all surface normals must point horizontally away from
the center, while the normals of the caps must point straight up and down.
Rendered as a single, Phong-shaded surface, the crease vertices would have incorrect normals.
Thus, some way of determining where to cease smoothing is needed to group smooth parts
of a mesh, just as polygons group 3-sided faces.
As an alternative to providing surfaces/smoothing groups, a mesh may contain other data for
calculating the same data, such as a splitting angle.
Additionally, very high resolution meshes are less subject to issues that would require
smoothing groups, as their polygons are so small as to make the need irrelevant.
Further, another alternative exists in the possibility of simply detaching the surfaces
themselves from the rest of the mesh.
Renderers do not attempt to smooth edges across noncontiguous polygons.
Mesh format may or may not define other useful data.
Groups may be defined which define separate elements of the mesh and are useful for determining
separate sub-objects for skeletal animation or separate actors for non-skeletal animation.
Generally materials will be defined, allowing different portions of the mesh to use different
shaders when rendered.
Most mesh formats also suppose some form of UV coordinates which are a separate 2d representation
of the mesh "unfolded" to show what portion of a 2-dimensional texture map to apply to
different polygons of the mesh.
Representations Polygon meshes may be represented in a variety
of ways, using different methods to store the vertex, edge and face data.
These include: Face-vertex meshes: A simple list of vertices,
and a set of polygons that point to the vertices it uses.
Winged-edge meshes, in which each edge points to two vertices, two faces, and the four edges
that touch it.
Winged-edge meshes allow constant time traversal of the surface, but with higher storage requirements.
Half-edge meshes: Similar to winged-edge meshes except that only half the edge traversal information
is used.
Quad-edge meshes, which store edges, half-edges, and vertices without any reference to polygons.
The polygons are implicit in the representation, and may be found by traversing the structure.
Memory requirements are similar to half-edge meshes.
Corner-tables, which store vertices in a predefined table, such that traversing the table implicitly
defines polygons.
This is in essence the triangle fan used in hardware graphics rendering.
The representation is more compact, and more efficient to retrieve polygons, but operations
to change polygons are slow.
Furthermore, corner-tables do not represent meshes completely.
Multiple corner-tables are needed to represent most meshes.
Vertex-vertex meshes: A "VV" mesh represents only vertices, which point to other vertices.
Both the edge and face information is implicit in the representation.
However, the simplicity of the representation does not allow for many efficient operations
to be performed on meshes.
Each of the representations above have particular advantages and drawbacks, further discussed
in Smith.
The choice of the data structure is governed by the application, the performance required,
size of the data, and the operations to be performed.
For example, it is easier to deal with triangles than general polygons, especially in computational
geometry.
For certain operations it is necessary to have a fast access to topological information
such as edges or neighboring faces; this requires more complex structures such as the winged-edge
representation.
For hardware rendering, compact, simple structures are needed; thus the corner-table is commonly
incorporated into low-level rendering APIs such as DirectX and OpenGL.
Vertex-vertex meshes
Vertex-vertex meshes represent an object as a set of vertices connected to other vertices.
This is the simplest representation, but not widely used since the face and edge information
is implicit.
Thus, it is necessary to traverse the data in order to generate a list of faces for rendering.
In addition, operations on edges and faces are not easily accomplished.
However, VV meshes benefit from small storage space and efficient morphing of shape.
Figure 2 shows the four-sided cylinder example represented using VV meshes.
Each vertex indexes its neighboring vertices.
Notice that the last two vertices, 8 and 9 at the top and bottom center of the "box-cylinder",
have four connected vertices rather than five.
A general system must be able to handle an arbitrary number of vertices connected to
any given vertex.
For a complete description of VV meshes see Smith.
Face-vertex meshes
Face-vertex meshes represent an object as a set of faces and a set of vertices.
This is the most widely used mesh representation, being the input typically accepted by modern
graphics hardware.
Face-vertex meshes improve on VV-mesh for modeling in that they allow explicit lookup
of the vertices of a face, and the faces surrounding a vertex.
Figure 3 shows the "box-cylinder" example as an FV mesh.
Vertex v5 is highlighted to show the faces that surround it.
Notice that, in this example, every face is required to have exactly 3 vertices.
However, this does not mean every vertex has the same number of surrounding faces.
For rendering, the face list is usually transmitted to the GPU as a set of indices to vertices,
and the vertices are sent as positionnormal structures.
This has the benefit that changes in shape, but not geometry, can be dynamically updated
by simply resending the vertex data without updating the face connectivity.
Modeling requires easy traversal of all structures.
With face-vertex meshes it is easy to find the vertices of a face.
Also, the vertex list contains a list of faces connected to each vertex.
Unlike VV meshes, both faces and vertices are explicit, so locating neighboring faces
and vertices is constant time.
However, the edges are implicit, so a search is still needed to find all the faces surrounding
a given face.
Other dynamic operations, such as splitting or merging a face, are also difficult with
face-vertex meshes.
Winged-edge meshes
Introduced by Baumgart 1975, winged-edge meshes explicitly represent the vertices, faces,
and edges of a mesh.
This representation is widely used in modeling programs to provide the greatest flexibility
in dynamically changing the mesh geometry, because split and merge operations can be
done quickly.
Their primary drawback is large storage requirements and increased complexity due to maintaining
many indices.
A good discussion of implementation issues of Winged-edge meshes may be found in the
book Graphics Gems II.
Winged-edge meshes address the issue of traversing from edge to edge, and providing an ordered
set of faces around an edge.
For any given edge, the number of outgoing edges may be arbitrary.
To simplify this, winged-edge meshes provide only four, the nearest clockwise and counter-clockwise
edges at each end.
The other edges may be traversed incrementally.
The information for each edge therefore resembles a butterfly, hence "winged-edge" meshes.
Figure 4 shows the "box-cylinder" as a winged-edge mesh.
The total data for an edge consists of 2 vertices, 2 faces, and 4 edges.
Rendering of winged-edge meshes for graphics hardware requires generating a Face index
list.
This is usually done only when the geometry changes.
Winged-edge meshes are ideally suited for dynamic geometry, such as subdivision surfaces
and interactive modeling, since changes to the mesh can occur locally.
Traversal across the mesh, as might be needed for collision detection, can be accomplished
efficiently.
See Baumgart for more details.
Render dynamic meshes Winged-edge meshes are not the only representation
which allows for dynamic changes to geometry.
A new representation which combines winged-edge meshes and face-vertex meshes is the render
dynamic mesh, which explicitly stores both, the vertices of a face and faces of a vertex,
and the faces and vertices of an edge.
Render dynamic meshes require slightly less storage space than standard winged-edge meshes,
and can be directly rendered by graphics hardware since the face list contains an index of vertices.
In addition, traversal from vertex to face is explicit, as is from face to vertex.
RD meshes do not require the four outgoing edges since these can be found by traversing
from edge to face, then face to neighboring edge.
RD meshes benefit from the features of winged-edge meshes by allowing for geometry to be dynamically
updated.
See Tobler & Maierhofer for more details.
Summary of mesh representation In the above table, explicit indicates that
the operation can be performed in constant time, as the data is directly stored; list
compare indicates that a list comparison between two lists must be performed to accomplish
the operation; and pair search indicates a search must be done on two indices.
The notation avg(V,V) means the average number of vertices connected to a given vertex; avg(E,V)
means the average number of edges connected to a given vertex, and avg(F,V) is the average
number of faces connected to a given vertex.
The notation "V → f1, f2, f3, ... → v1, v2, v3, ..." describes that a traversal across
multiple elements is required to perform the operation.
For example, to get "all vertices around a given vertex V" using the face-vertex mesh,
it is necessary to first find the faces around the given vertex V using the vertex list.
Then, from those faces, use the face list to find the vertices around them.
Notice that winged-edge meshes explicitly store nearly all information, and other operations
always traverse to the edge first to get additional info.
Vertex-vertex meshes are the only representation that explicitly stores the neighboring vertices
of a given vertex.
As the mesh representations become more complex, the amount of information explicitly stored
increases.
This gives more direct, constant time, access to traversal and topology of various elements
but at the cost of increased overhead and space in maintaining indices properly.
Figure 7 shows the connectivity information for each of the four technique described in
this article.
Other representations also exist, such as half-edge and corner tables.
These are all variants of how vertices, faces and edges index one another.
As a general rule, face-vertex meshes are used whenever an object must be rendered on
graphics hardware that does not change geometry, but may deform or morph shape such as real-time
rendering of static or morphing objects.
Winged-edge or render dynamic meshes are used when the geometry changes, such as in interactive
modeling packages or for computing subdivision surfaces.
Vertex-vertex meshes are ideal for efficient, complex changes in geometry or topology so
long as hardware rendering is not of concern.
Other representations Streaming meshes store faces in an ordered,
yet independent, way so that the mesh can be transmitted in pieces.
The order of faces may be spatial, spectral, or based on other properties of the mesh.
Streaming meshes allow a very large mesh to be rendered even while it is still being loaded.
Progressive meshes transmit the vertex and face data with increasing levels of detail.
Unlike streaming meshes, progressive meshes give the overall shape of the entire object,
but at a low level of detail.
Additional data, new edges and faces, progressively increase the detail of the mesh.
Normal meshes transmit progressive changes to a mesh as a set of normal displacements
from a base mesh.
With this technique, a series of textures represent the desired incremental modifications.
Normal meshes are compact, since only a single scalar value is needed to express displacement.
However, the technique requires a complex series of transformations to create the displacement
textures.
File formats There exist many different file formats for
storing polygon mesh data.
Each format is most effective when used for the purpose intended by its creator.
Some of these formats are presented below: See also
Simulation Modeling Wire-frame model
Euler operator B-rep
Simplex Triangulation
Manifold Mesh subdivision
T-Spline References
External links Weisstein, Eric W., "Simplicial complex",
MathWorld.
Weisstein, Eric W., "Triangulation", MathWorld.
OpenMesh open source half-edge mesh representation.