Polygon mesh
From Wikipedia, the free encyclopedia
A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics. 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 (the volume is implicit). As polygonal meshes are extensively used in computer graphics, algorithms also exist for raytracing, collision detection, and rigid-body dynamics of polygon meshes.
[edit] Representation
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 (clockwise and counterclockwise) 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 - A quad-edge mesh stores 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-Table - A corner-table stores 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 (triangle fans) 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 allows for many efficient operations to be performed on meshes.
The representations above each have particular advantages and drawbacks, further discussed in [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's 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 (triangle fan) is commonly incorporated into low-level rendering APIs such as DirectX and OpenGL.
In the first, and most common, Face-Vertex Mesh representation above, a unit pyramid (depicted right) may be represented by these two lists in 3D space (the lists correspond to the image on the right):
Vertices list:
| Vertex index | X Coordinate | Y Coordinate | Z Coordinate |
|---|---|---|---|
| 1 | -1 | 0 | 1 |
| 2 | -1 | 0 | -1 |
| 3 | 1 | 0 | -1 |
| 4 | 1 | 0 | 1 |
| 5 | 0 | 1 | 0 |
Faces list:
| Face index | Type | Vertex 1 | Vertex 2 | Vertex 3 | Vertex 4 |
|---|---|---|---|---|---|
| 1 | Triangle | 1 | 2 | 5 | |
| 2 | Triangle | 2 | 3 | 5 | |
| 3 | Triangle | 3 | 4 | 5 | |
| 4 | Triangle | 4 | 1 | 5 | |
| 5 | Quadrilateral | 1 | 2 | 3 | 4 |
[edit] 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.
