Polygon mesh data structure
My first tests with OpenGL use a triangle soup which is basically a collection of triangles with no relationship whatsoever. In order to implement a more complex shader I need to work on a more complex and powerful data structure: the polygon mesh
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, quadrilaterals or other simple convex polygons, since this simplifies rendering, but may also be composed of more general concave polygons, or polygons with holes.[Wiki Polygon Mesh]
There's a variety of ways to represent a polygon mesh and they basically differ in how the vertex and topology information are stored. One of the most used representation in the filed computer graphics and geometry processing is the halfedge data structure.
Polygonal meshes consist of geometry (vertices) and topology (edges, faces). Data structure for polygonal meshes mainly differ in the way they store the topology information. While face-based structures lack the explicit representation of edges, and edge-based structures loose efficiency because of their missing orientation of edges, halfedge-based structures overcome this disadvantages. The halfedges (that result in splitting the edges in two oriented parts) store the main connectivity information:Intuitively, this provides a natural and simple way to represent vertices, edges and faces, as well as arbitrary polygons.[OpenMesh]
Many operations and queries are very natural on the halfedge data structure, in particular the circulation on the neighbors of vertices and faces.
Traversal of one-ring neighbors of a center vertex. From left to right:
- Start from center vertex.
- Select outgoing halfedge (and access its target vertex).
- Move to previous halfedge.
- Move to opposite halfedge (access its target vertex)
- CGAL
- OpenMesh
- SurfaceMesh
- Mesquite
 |
| CGAL Logo |
I have never used Mesquite. This is mainly focused on the mesh optimization [BFKLM03]. Although the CGAL is a very powerful library for the compuational geometry, its polygonal mesh implementation has a major drawback: all the custom properties associated with a mesh entity must be declared at compile time.
 |
| Aachen University Computer GraphicsLogo |
OpenMesh and SurfaceMesh are more flexible and much easier to use than CGAL. OpenMesh was originally developed at the Aachen University [BSBK02] and the version 3.0 was recently released. On the other hand SurfaceMesh is more recent [SB11] and it was developed at the Bielefeld university.
They have very much in common, starting with one of their developers, Mario Botsch who is also the head of the Computer Graphics & Geometry Processing Group at Bielefeld.
Based on our experience in academic research and teaching as well as in industrial cooperations, our primary design goal [of the SurfaceMesh] is ease of use. An easy-to-use data structure is learned faster, allows to focus on the main problem (instead of on the details of the data structure), and fosters code exchange between academic or industrial research partners. The data structure should therefore be just as flexible and generic as needed, but should otherwise be free of unnecessary switches and parameters. At the same time, however, we have to make sure not to compromise computational performance and memory consumption. Otherwise the data structure would be easy to use, but not useful, and hence would probably not be used at all.
[SB11]
In the end I'll show you an example of the SurfaceMesh which computes the mean valence of the mesh vertices
References
[SB11] Design, Implementation, and Evaluation of the Surface_mesh Data Structure[BFKLM03] The Mesquite mesh quality improvement toolkit
[BSBK02] OpenMesh – a generic and efficient polygon mesh data structure
[OpenMesh]
[Wiki Polygon Mesh]
[CGAL]
[Mesquite]
[OpenMesh]
[Wiki Polygon Mesh]
[CGAL]
[Mesquite]