Summary of Mesh Representation
| Operation | Vertex-vertex | Face-vertex | Winged-edge | Render dynamic | |
|---|---|---|---|---|---|
| V-V | 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, ... |
| E-F | All edges of a face | F(a,b,c) → {a,b}, {b,c}, {a,c} | F → {a,b}, {b,c}, {a,c} | Explicit | Explicit |
| V-F | All vertices of a face | F(a,b,c) → {a,b,c} | Explicit | F → e1, e2, e3 → a, b, c | Explicit |
| F-V | All faces around a vertex | Pair search | Explicit | V → e1, e2, e3 → f1, f2, f3, ... | Explicit |
| E-V | All edges around a vertex | V → {v,v1}, {v,v2}, {v,v3}, ... | V → f1, f2, f3, ... → v1, v2, v3, ... | Explicit | Explicit |
| F-E | Both faces of an edge | List compare | List compare | Explicit | Explicit |
| V-E | 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 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 (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 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 (connectivity), but may deform or morph shape (vertex positions) 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 subdivison surfaces. Vertex-vertex meshes are ideal for efficient, complex changes in geometry or topology so long as hardware rendering is not of concern.
Read more about this topic: Polygon Mesh
Famous quotes containing the word summary:
“I have simplified my politics into an utter detestation of all existing governments; and, as it is the shortest and most agreeable and summary feeling imaginable, the first moment of an universal republic would convert me into an advocate for single and uncontradicted despotism. The fact is, riches are power, and poverty is slavery all over the earth, and one sort of establishment is no better, nor worse, for a people than another.”
—George Gordon Noel Byron (1788–1824)