Editing Polygon mesh (section)

== Representations ==

Polygon meshes may be represented in a variety of ways, using different methods to store the vertex, edge and face data. These include:

{{term|Face-vertex meshes}} {{defn|A simple list of [[vertex (graph theory)|vertices]], and a set of polygons that point to the vertices it uses.}}
{{term|Winged-edge meshes|content=[[Winged edge|Winged-edge]]}} {{defn|in which each edge points to two vertices, two faces, and the four (clockwise and counterclockwise) edges that touch them. Winged-edge meshes allow constant time traversal of the surface, but with higher storage requirements.}}
{{term|half-edge meshes|content=[[Half-edge data structure|Half-edge meshes]]}} {{defn|Similar to winged-edge meshes except that only half the edge traversal information is used.  (see [http://www.openmesh.org/ OpenMesh])}}
{{term|quad-edge meshes|content=[[Quad-edge|Quad-edge meshes]]}} {{defn|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.}}
{{term|Corner-tables}} {{defn|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 (triangle fans) are needed to represent most meshes.}}
{{term|Vertex-vertex meshes}}{{defn|A VV mesh represents only vertices, which point to other vertices. Both the edge and the 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 (2006).<ref name="Smith(2006)">Colin Smith, [http://algorithmicbotany.org/papers/smithco.dis2006.pdf On Vertex-Vertex Meshes and Their Use in Geometric and Biological Modeling], ([[PDF]])</ref>

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 (triangle fan) is commonly incorporated into low-level rendering APIs such as [[DirectX]] and [[OpenGL]].

=== Vertex-vertex meshes ===
[[File:Vertex-Vertex Meshes (VV).png|center|400px|Figure 2. 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).<ref name="Smith(2006)" />

=== Face-vertex meshes ===
[[File:mesh fv.jpg|center|500px|Figure 3. 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. 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.

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 ===
[[File:mesh we2.jpg|center|Figure 4. Winged-edge meshes]]

Introduced by Baumgart in 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. The above figure shows the "box-cylinder" as a winged-edge mesh. The total data for an edge consists of 2 vertices (endpoints), 2 faces (on each side), and 4 edges (winged-edge).

Rendering of winged-edge meshes for graphics hardware requires generating a Face index list, which 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 (1975) for more details.<ref>Bruce Baumgart, Winged-Edge Polyhedron Representation for Computer Vision. National Computer Conference, May 1975. {{cite web|url=http://www.baumgart.org/winged-edge/winged-edge.html|title=Use of Polyhedra in computer vision|date=May 1975|website=baumgart.org|url-status=dead|archive-url=https://web.archive.org/web/20050829135758/http://www.baumgart.org/winged-edge/winged-edge.html|archive-date=2005-08-29|access-date=2005-08-29}}</ref>

=== 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 (like FV meshes), and the faces and vertices of an edge (like winged-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 (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 winged-edge meshes by allowing for geometry to be dynamically updated.

See Tobler & Maierhofer ([[Winter School of Computer Graphics|WSCG]] 2006) for more details.<ref>Tobler & Maierhofer, [http://wscg.zcu.cz/wscg2006/Papers_2006/Short/E17-full.pdf A Mesh Data Structure for Rendering and Subdivision. 2006]. ([[PDF]])</ref>