In 3D computer graphics and solid modeling, a polygon mesh is a collection of vertices, edges and faces that define the shape of a polyhedral object's surface. It simplifies rendering, as in a wire-frame model. The faces usually consist of triangles (triangle mesh), quadrilaterals (quads), or other simple convex polygons (n-gons). A polygonal mesh may also be more generally composed of concave polygons, or even polygons with holes. The study of polygon meshes is a large sub-field of computer graphics (specifically 3D computer graphics) and geometric modeling. Different representations of polygon meshes are used for different applications and goals. The variety of operations performed on meshes includes Boolean logic (Constructive solid geometry), smoothing, and simplification. Algorithms also exist for ray tracing, collision detection, and rigid-body dynamics with polygon meshes. If the mesh's edges are rendered instead of the faces, then the model becomes a wireframe model. Several methods exist for mesh generation, including the marching cubes algorithm. Volumetric meshes are distinct from polygon meshes in that they explicitly represent both the surface and interior region of a structure, while polygon meshes only explicitly represent the surface (the volume is implicit).
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 3-sided faces, so polygons must be constructed of many of these, as shown above. 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.
Vertices
A vertex in computer graphics terms is a data structure that describes the position of a point in 2, 3 or 4D space on a surface along with optional attributes - other values used to render the object correctly. Most attributes of a vertex represent vectors in the space to be rendered. These vectors are typically 2 (x, y) or 3 (x, y, z) dimensional and can include a fourth homogeneous coordinate (w).. In real-time rendering these properties are used by a vertex shader or vertex pipeline. Attributes can include position, color, reflectance, specularity, texture mapping coordinates, normal vectors, and displacement mapping.
Representations Polygon meshes may be represented in a variety of ways, using different methods to store the vertex, edge and face data. These include:
vertex-vertex face-vertex winged-edge half-edge quad-edge Each representation has advantages and disadvantages, discussed in Smith (2006).
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. The above figure shows a four-sided box as represented by a VV mesh. Each vertex indexes its neighboring vertices. 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 (2006).
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 modelling in that they allow explicit lookup of the vertices of a face, and the faces surrounding a vertex. The above figure 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 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. Modelling 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
… excerpt ends here. Continue reading the full article.
