Surface_mesh  1.0
A simple and efficient halfedge-based mesh data structure
Usage

Introduction

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:

  • Each vertex stores an outgoing halfedge.
  • Each face stores an incident halfedge.
  • Each halfedge stores its incident face, its target vertex, and its previous and next halfedges within the face.

The halfedge connectivity is illustrated in the figure below:

halfedge-connectivity.png
Halfedge connectivity.

Usage

In the following sections we describe the basic usage of Surface_mesh by means of simple example programs and code excerpts.

Basics

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.

//=============================================================================
// Copyright (C) 2013 by Graphics & Geometry Group, Bielefeld University
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public License
// as published by the Free Software Foundation, version 2.
//
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//=============================================================================
#include <surface_mesh/Surface_mesh.h>
//=============================================================================
using namespace surface_mesh;
//=============================================================================
int main(void)
{
// instantiate a Surface_mesh object
// instantiate 4 vertex handles
Surface_mesh::Vertex v0,v1,v2,v3;
// add 4 vertices
v0 = mesh.add_vertex(Point(0,0,0));
v1 = mesh.add_vertex(Point(1,0,0));
v2 = mesh.add_vertex(Point(0,1,0));
v3 = mesh.add_vertex(Point(0,0,1));
// add 4 triangular faces
mesh.add_triangle(v0,v1,v3);
mesh.add_triangle(v1,v2,v3);
mesh.add_triangle(v2,v0,v3);
mesh.add_triangle(v0,v2,v1);
std::cout << "vertices: " << mesh.n_vertices() << std::endl;
std::cout << "edges: " << mesh.n_edges() << std::endl;
std::cout << "faces: " << mesh.n_faces() << std::endl;
return 0;
}
//=============================================================================

File I/O

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.

//=============================================================================
// Copyright (C) 2013 by Graphics & Geometry Group, Bielefeld University
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public License
// as published by the Free Software Foundation, version 2.
//
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//=============================================================================
#include <surface_mesh/Surface_mesh.h>
//=============================================================================
using namespace surface_mesh;
//=============================================================================
int main(int /*argc*/, char** argv)
{
// instantiate a Surface_mesh object
// read a mesh specified as the first command line argument
mesh.read(argv[1]);
// ...
// do fancy stuff with the mesh
// ...
// write the mesh to the file specified as second argument
mesh.write(argv[2]);
return 0;
}
//=============================================================================

Iterators and Circulators

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.

//=============================================================================
// Copyright (C) 2013 by Graphics & Geometry Group, Bielefeld University
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public License
// as published by the Free Software Foundation, version 2.
//
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//=============================================================================
#include <surface_mesh/Surface_mesh.h>
//=============================================================================
using namespace surface_mesh;
//=============================================================================
int main(int /*argc*/, char** argv)
{
mesh.read(argv[1]);
float mean_valence = 0.0f;
unsigned int vertex_valence;
// instantiate iterator and circulators
// loop over all vertices
for (vit = mesh.vertices_begin(); vit != mesh.vertices_end(); ++vit)
{
// initialize circulators
vc = mesh.vertices(*vit);
vc_end = vc;
// reset counter
vertex_valence = 0;
// loop over all incident vertices
do
{
++vertex_valence;
} while (++vc != vc_end);
// sum up vertex valences
mean_valence += vertex_valence;
}
mean_valence /= mesh.n_vertices();
std::cout << "mean valence: " << mean_valence << std::endl;
}
//=============================================================================

Properties

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.

//=============================================================================
// Copyright (C) 2013 by Graphics & Geometry Group, Bielefeld University
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Library General Public License
// as published by the Free Software Foundation, version 2.
//
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//=============================================================================
#include <surface_mesh/Surface_mesh.h>
//=============================================================================
using namespace surface_mesh;
//=============================================================================
int main(int /*argc*/, char** argv)
{
mesh.read(argv[1]);
// get (pre-defined) property storing vertex positions
Point p(0,0,0);
for (vit = mesh.vertices_begin(); vit != vend; ++vit)
{
// access point property like an array
p += points[*vit];
}
p /= mesh.n_vertices();
std::cout << "barycenter: " << p << std::endl;
}
//=============================================================================

The dynamic (de-)allocation of properties at run-time is managed by a set of four different functions:

add_EntityType_property<PropertyType>("PropertyName")
Allocates a new property for the given EntityType of the type PropertyType labeled by the PropertyName string.

get_EntityType_property<PropertyType>("PropertyName")
Returns a handle to an existing property.

EntityType_property<PropertyType>("PropertyName")
Returns a handle to an existing property if the specified property already exists. If not, a new property is allocated and its handle is returned.

remove_EntityType_property(PropertyHandle)
Removes and the vertex property referenced by 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.

Surface_mesh mesh;
// allocate property storing a point per edge
Surface_mesh::Edge_property<Point> edge_points = mesh.add_edge_property<Point>("property-name");
// access the edge property like an array
Surface_mesh::Edge e;
edge_points[e] = Point(x,y,z);
// remove property and free memory
mesh.remove_edge_property(edge_points);

Connectivity Queries

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);
connectivity-queries.png

Topological Operations

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.

topology-changes.png
High-level operations changing the topology.

The corresponding member functions and their syntax is demonstrated in the pseudo-code below.

Surface_mesh::Vertex v;
Surface_mesh::Edge e;
Surface_mesh::Halfedge h;
Surface_mesh::Face f;
mesh.split(f, v);
mesh.split(e, v);
mesh.flip(e);
mesh.collapse(h);

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.