Surface_mesh
1.0
A simple and efficient halfedge-based mesh data structure
|
In general, a polygonal surface mesh is composed of vertices, edges and faces as well as the incidence relationships between them. Surface_mesh stores the connectivity information based on halfedges, i.e. pairs of directed edges with opposing direction. To be more precise:
The halfedge connectivity is illustrated in the figure below:
In the following sections we describe the basic usage of Surface_mesh by means of simple example programs and code excerpts.
The very basic usage of Surface_mesh is demonstrated in the example below. The program first instantiates a Surface_mesh object as well as four vertex handles. These handles, as well as the handles for the other mesh entities Halfedge
, Edge
, and Face
are basically indices. Four vertices are added to the mesh, as well as four triangular faces composing a tetrahedron. Finally, the number of vertices, edges, and faces is printed to standard output.
Surface_mesh currently supports reading OFF, OBJ, and STL files. Write support is currently limited to OFF files. All I/O operations are handled by the Surface_mesh::read() and Surface_mesh::write() member functions, with the target file name being their only argument. An example is given below.
In order to sequentially access mesh entities Surface_mesh provides iterators for each entity type, namely Vertex_iterator
, Halfedge_iterator
, Edge_iterator
, and Face_iterator
. Similar to iterators, Surface_mesh also provides circulators for the ordered enumeration of all incident vertices, halfedges, or faces around a given face or vertex. Since there is no clear begin- and end-circulator, do-while
loops are used for circulators. The example below demonstrates the use of iterators and circulators for computing the mean valence of a mesh.
Attaching additional attributes to mesh entities is important for many applications. Surface_mesh supports properties by means of synchronized arrays that can be (de-)allocated dynamically at run-time. Property arrays are also used internally, e.g., to store vertex coordinates. The example program below shows how to access vertex coordinates through the (pre-defined) point property.
The dynamic (de-)allocation of properties at run-time is managed by a set of four different functions:
add_EntityType_property<PropertyType>("PropertyName")
get_EntityType_property<PropertyType>("PropertyName")
EntityType_property<PropertyType>("PropertyName")
remove_EntityType_property(PropertyHandle)
Functions that allocate a new property take a default value for the property as an optional second argument.
The code excerpt below demonstrates how to allocate, use and remove a custom edge property.
Commonly used connectivity queries such as retrieving the next halfedge or the target vertex of an halfedge are illustrated below.
Surface_mesh::Halfedge h;
Surface_mesh::Halfedge h0 = mesh.next_halfedge_handle(h);
Surface_mesh::Halfedge h1 = mesh.prev_halfedge_handle(h);
Surface_mesh::Halfedge h2 = mesh.opposite_halfedge_handle(h);
Surface_mesh::Face f = mesh.face_handle(h);
Surface_mesh::Vertex v0 = mesh.from_vertex_handle(h);
Surface_mesh::Vertex v1 = mesh.to_vertex_handle(h);
| ![]() |
Surface mesh also offers higher-level topological operations, such as performing edge flips, edge splits, face splits, or halfedge collapses. The figure below illustrates some of these operations.
The corresponding member functions and their syntax is demonstrated in the pseudo-code below.
When entities are removed from the mesh due to topological changes, the member function garbage_collection()
has to be called in order to ensure the consistency of the data structure.