Polygon mesh
It has been suggested that this article be merged into Wireframe model. (Discuss) Proposed since September 2018.

This article needs additional citations for verification. (June 2009) (Learn how and when to remove this template message)

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 (triangle mesh), 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 subfield 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. 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 (the volume is implicit). As polygonal meshes are extensively used in computer graphics, algorithms also exist for ray tracing, collision detection, and rigidbody dynamics of polygon meshes.
Contents
Elements
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 3sided faces, so polygons must be constructed of many of these, as shown above. However, many renderers either support quads and highersided polygons, or are able to convert polygons to triangles on the fly, making it unnecessary to store a mesh in a triangulated form.
Representations
Polygon meshes may be represented in a variety of ways, using different methods to store the vertex, edge and face data. These include:
Each of the representations above have particular advantages and drawbacks, further discussed in Smith (2006).^{[1]} 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 wingededge representation. For hardware rendering, compact, simple structures are needed; thus the cornertable (triangle fan) is commonly incorporated into lowlevel rendering APIs such as DirectX and OpenGL.
Vertexvertex meshes
Vertexvertex 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. The above figure shows a foursided box as represented by a VV mesh. Each vertex indexes its neighboring vertices. Notice that the last two vertices, 8 and 9 at the top and bottom center of the "boxcylinder", 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 (2006).^{[1]}
Facevertex meshes
Facevertex 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.
Facevertex meshes improve on VVmesh for modeling in that they allow explicit lookup of the vertices of a face, and the faces surrounding a vertex. The above figure shows the "boxcylinder" 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 position/color/normal structures (in the figure, only position is given). 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 facevertex 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 facevertex meshes.
Wingededge meshes
Introduced by Baumgart 1975, wingededge 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 Wingededge meshes may be found in the book Graphics Gems II.
Wingededge 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, wingededge meshes provide only four, the nearest clockwise and counterclockwise edges at each end. The other edges may be traversed incrementally. The information for each edge therefore resembles a butterfly, hence "wingededge" meshes. The above figure shows the "boxcylinder" as a wingededge mesh. The total data for an edge consists of 2 vertices (endpoints), 2 faces (on each side), and 4 edges (wingededge).
Rendering of wingededge meshes for graphics hardware requires generating a Face index list. This is usually done only when the geometry changes. Wingededge 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 (1975) for more details.^{[2]}
Render dynamic meshes
Wingededge meshes are not the only representation which allows for dynamic changes to geometry. A new representation which combines wingededge meshes and facevertex meshes is the render dynamic mesh, which explicitly stores both, the vertices of a face and faces of a vertex (like FV meshes), and the faces and vertices of an edge (like wingededge).
Render dynamic meshes require slightly less storage space than standard wingededge 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 (constant time), 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 wingededge meshes by allowing for geometry to be dynamically updated.
See Tobler & Maierhofer (WSCG 2006) for more details.^{[3]}
Summary of mesh representation
Operation  Vertexvertex  Facevertex  Wingededge  Render dynamic  

VV  All vertices around vertex  Explicit  V → f1, f2, f3, ... → v1, v2, v3, ...  V → e1, e2, e3, ... → v1, v2, v3, ...  V → e1, e2, e3, ... → v1, v2, v3, ... 
EF  All edges of a face  F(a,b,c) → {a,b}, {b,c}, {a,c}  F → {a,b}, {b,c}, {a,c}  Explicit  Explicit 
VF  All vertices of a face  F(a,b,c) → {a,b,c}  Explicit  F → e1, e2, e3 → a, b, c  Explicit 
FV  All faces around a vertex  Pair search  Explicit  V → e1, e2, e3 → f1, f2, f3, ...  Explicit 
EV  All edges around a vertex  V → {v,v1}, {v,v2}, {v,v3}, ...  V → f1, f2, f3, ... → v1, v2, v3, ...  Explicit  Explicit 
FE  Both faces of an edge  List compare  List compare  Explicit  Explicit 
VE  Both vertices of an edge  E(a,b) → {a,b}  E(a,b) → {a,b}  Explicit  Explicit 
Flook  Find face with given vertices  F(a,b,c) → {a,b,c}  Set intersection of v1,v2,v3  Set intersection of v1,v2,v3  Set intersection of v1,v2,v3 
Storage size  V*avg(V,V)  3F + V*avg(F,V)  3F + 8E + V*avg(E,V)  6F + 4E + V*avg(E,V)  
Example with 10 vertices, 16 faces, 24 edges:  
10 * 5 = 50  3*16 + 10*5 = 98  3*16 + 8*24 + 10*5 = 290  6*16 + 4*24 + 10*5 = 242  
Figure 6: summary of mesh representation operations 
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 facevertex 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 wingededge meshes explicitly store nearly all information, and other operations always traverse to the edge first to get additional info. Vertexvertex meshes are the only representation that explicitly stores the neighboring vertices of a given vertex.
As the mesh representations become more complex (from left to right in the summary), 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 halfedge and corner tables. These are all variants of how vertices, faces and edges index one another.
As a general rule, facevertex meshes are used whenever an object must be rendered on graphics hardware that does not change geometry (connectivity), but may deform or morph shape (vertex positions) such as realtime rendering of static or morphing objects. Wingededge or render dynamic meshes are used when the geometry changes, such as in interactive modeling packages or for computing subdivision surfaces. Vertexvertex meshes are ideal for efficient, complex changes in geometry or topology so long as hardware rendering is not of concern.
Other representations
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:
File suffix  Format name  Organization(s)  Program(s)  Description 

.raw  Raw mesh  Unknown  Various  Open, ASCIIonly format. Each line contains 3 vertices, separated by spaces, to form a triangle, like so: X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 
.blend  Blender File Format  Blender Foundation  Blender 3D  Open source, binaryonly format 
.fbx  Autodesk FBX Format  Autodesk  Various  Proprietary. Binary and ASCII specifications exist. 
.3ds  3ds Max File  Autodesk  3ds Max  A common but outdated format with hard 16bit limits on the number of vertices and faces. Neither standardised nor well documented, but used to be a "de facto standard" for data exchange. 
.dae  Digital Asset Exchange (COLLADA)  Sony Computer Entertainment, Khronos Group  N/A  Stands for "COLLAborative Design Activity". A universal format designed to prevent incompatibility. 
.dgn  MicroStation File  Bentley Systems  MicroStation  There are two dgn file formats: preversion 8 and version 8 (V8) 
.3dm  Rhino File  Robert McNeel & Associates  Rhinoceros 3D  
.dxf, .dwg  Drawing Exchange Format  Autodesk  AutoCAD  
.obj  Wavefront OBJ  Wavefront Technologies  Various  ASCII format describing 3D geometry. All faces' vertices are ordered counterclockwise, making facet normals implicit. Smooth normals are specified per vertex. 
.ply  Polygon File Format  Stanford University  Various  Binary and ASCII 
.pmd  Polygon Movie Maker data  Yu Higuchi  MikuMikuDance  Proprietary binary file format for storing humanoid model geometry with rigging, material, and physics information. 
.stl  Stereolithography Format  3D Systems  Many  Binary and ASCII format originally designed to aid in CNC. 
.amf  Additive Manufacturing File Format  ASTM International  N/A  Like the STL format, but with added native color, material, and constellation support. 
.wrl  Virtual Reality Modeling Language  Web3D Consortium  Web Browsers  ISO Standard 147721:1997 
.wrz  VRML Compressed  Web3D Consortium  Web Browsers  
.x3d, .x3db, .x3dv  Extensible 3D  Web3D Consortium  Web Browsers  XMLbased, open source, royaltyfree, extensible, and interoperable; also supports color, texture, and scene information. ISO Standard 19775/19776/19777 
.x3dz, .x3dbz, .x3dvz  X3D Compressed Binary  Web3D Consortium  Web Browsers  
.c4d  Cinema 4D File  MAXON  CINEMA 4D  
.lwo  LightWave 3D object File  NewTek  LightWave 3D  
.smb  SCOREC apf  RPI SCOREC  PUMI  Open source parallel adaptive unstructured 3D meshes for PDE based simulation workflows. 
.msh  Gmsh Mesh  GMsh Developers  GMsh Project  Open source, providing an ASCII mesh description for linear and polynomially interpolated elements in 1 to 3 dimensions. 
.mesh  OGRE XML  OGRE Development Team  OGRE, purebasic  Open Source. Binary (.mesh) and ASCII (.mesh.xml) format available. Includes data for vertex animation and Morph target animation (blendshape). Skeletal animation data in separate file (.skeleton). 
.veg  Vega FEM tetrahedral mesh  Jernej Barbič  Vega FEM  Open Source. Stores a tetrahedral mesh and its material properties for FEM simulation. ASCII (.veg) and binary (.vegb) formats available. 
.z3d  Z3d  Oleg Melashenko  Zanoza Modeler   
.vtk  VTK mesh  VTK, Kitware  VTK, Paraview  Open, ASCII or binary format that contains many different data fields, including point data, cell data, and field data. 
.l4d  LAI4D drawing  Laboratory of Artificial Intelligence for Design  LAI4D  ASCII data format that describes a hierarchical tree of entities. 
See also
 Brep
 Euler operator
 Hypergraph
 Manifold (a mesh can be manifold or nonmanifold)
 Mesh subdivision (a technique for adding detail to a polygon mesh)
 Polygon modeling
 Polygonizer
 Simplex
 Tspline
 Triangulation (geometry)
 Wireframe model
References
 ^ ^{a} ^{b} Colin Smith, On VertexVertex Meshes and Their Use in Geometric and Biological Modeling, http://algorithmicbotany.org/papers/smithco.dis2006.pdf
 ^ Bruce Baumgart, WingedEdge Polyhedron Representation for Computer Vision. National Computer Conference, May 1975. "Archived copy". Archived from the original on 20050829. Retrieved 20050829.
 ^ Tobler & Maierhofer, A Mesh Data Structure for Rendering and Subdivision. 2006. [1]
External links
 Weisstein, Eric W. "Simplicial complex". MathWorld.
 Weisstein, Eric W. "Triangulation". MathWorld.
 OpenMesh open source halfedge mesh representation.