Author: Mario Botsch, Daniel Sieger, Philipp Moeller and Andreas Fabri

The class Surface_mesh is an implementation of a halfedge data structure and can be used to represent a polyhedral surface. It is an alternative to the CGAL packages Halfedge Data Structures and 3D Polyhedral Surface. The main difference is that it is indexed based and not pointer based. Additionally, the mechanism for adding information to vertices, halfedges, edges, and faces is much simpler and is done at runtime and not at compile time.

Because the data structure uses integer indices as descriptors for vertices, halfedges, edges and faces it has a lower memory footprint than a 64-bit pointer based version. As the indices are contiguous, they can be used as index into vectors which store properties.

When elements are removed, they are only marked as removed, and a garbage collection function must be called to really remove them.

The class Surface_mesh can be used through its class member functions as well as through the BGL API as described in the package CGAL and the Boost Graph Library, as it is a model of the concepts MutableFaceGraph and FaceListGraph. Therefore it is possible to apply the algorithms of the packages Triangulated Surface Mesh Simplification, Triangulated Surface Mesh Segmentation, and Triangulated Surface Mesh Deformation on a surface mesh.

Usage

The main class Surface_mesh provides four nested classes that represent the basic elements of the halfedge data structure:

These types are just wrappers for an integer and their main purpose is to guarantee type safety. They are default constructible, which yields an invalid element. New elements can be added and removed to the Surface_mesh through a set of low-level functions which do not maintain connectivity. One exception is Surface_mesh::add_face(), which tries to add a new face to the mesh (defined by a sequence of vertices), and fails if the operation is not topologically valid. In that case, the returned Face_index is Surface_mesh::null_face().

typedef Surface_mesh<Point> Mesh;
Mesh m;
Mesh::Vertex_index u = m.add_vertex(Point(0,1,0));
Mesh::Vertex_index v = m.add_vertex(Point(0,0,0));
Mesh::Vertex_index w = m.add_vertex(Point(1,0,0));
m.add_face(u, v, w);

As Surface_mesh is index-based Vertex_index, Halfedge_index, Edge_index, and Face_index do not have member functions to access connectivity or properties. The functions of the Surface_mesh instance from which they were created must be used to obtain this information.

Example

The first example shows how to create a very simple Surface_mesh by adding 2 faces, and how to check that a face is correctly added to the mesh.

File Surface_mesh/check_orientation.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
 
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
typedef Mesh::Face_index face_descriptor;
 
int main()
{
  Mesh m;
 
  // Add the points as vertices
  vertex_descriptor u = m.add_vertex(K::Point_3(0,1,0));
  vertex_descriptor v = m.add_vertex(K::Point_3(0,0,0));
  vertex_descriptor w = m.add_vertex(K::Point_3(1,1,0));
  vertex_descriptor x = m.add_vertex(K::Point_3(1,0,0));
 
  m.add_face(u,v,w);
  face_descriptor f = m.add_face(u,v,x);
  if(f == Mesh::null_face())
  {
    std::cerr<<"The face could not be added because of an orientation error."<<std::endl;
    f = m.add_face(u,x,v);
    assert(f != Mesh::null_face());
  }
  return 0;
}

The second example shows how to access the points associated to the vertices, either for an individual vertex, or as the range of points of the entire mesh. Such a range can be accessed in a for-loop or passed to functions that expect a range of points as input.

File Surface_mesh/sm_points.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/convex_hull_3.h>
 
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
typedef Mesh::Face_index face_descriptor;
 
int main()
{
  Mesh m;
  vertex_descriptor v0 = m.add_vertex(K::Point_3(0,0,0));
  vertex_descriptor v1 = m.add_vertex(K::Point_3(1,0,0));
  vertex_descriptor v2 = m.add_vertex(K::Point_3(0,1,0));
  vertex_descriptor v3 = m.add_vertex(K::Point_3(0,0,1));
 
  face_descriptor fd = m.add_face(v0, v1, v2);
  m.add_face(v1, v0, v3);
 
  // Access the point for a given vertex
  for(vertex_descriptor vd : vertices_around_face(m.halfedge(fd), m)){
    std ::cout << m.point(vd) << std::endl;
  }
 
  // Access the range of all points of the mesh
  for( const K::Point_3& p : m.points()){
    std::cout << p << std::endl;
  }
 
  Mesh ch;
  CGAL::convex_hull_3(m.points().begin(), m.points().end(), ch);
 
  return 0;
}

Connectivity

A surface mesh is an edge-centered data structure capable of maintaining incidence information of vertices, edges, and faces. Each edge is represented by two halfedges with opposite orientation. Each halfedge stores a reference to an incident face and to an incident vertex. Additionally, it stores a reference to the next and previous halfedge incident to its incident face. For each face and each vertex an incident halfedge is stored. Halfedges do not store the index of the opposite halfedge, as Surface_mesh stores opposite halfedges consecutively in memory.

The following figure illustrates the functions which allow to navigate in a surface mesh: Surface_mesh::opposite(), Surface_mesh::next(), Surface_mesh::prev(), Surface_mesh::target(), and Surface_mesh::face(). Additionally, the functions Surface_mesh::halfedge() allows to obtain the halfedge associated to a vertex and to a face. Alternatively, one may use the free functions with the same names defined in the package CGAL and the Boost Graph Library.

Figure 28.1 Connectivity of halfedges and vertices in a surface mesh seen from outside.

The halfedges incident to a face form a cycle. Depending on from which side we look at the surface, the sequence of halfedges appears to be oriented clockwise or counterclockwise. When in this manual we speak about the orientation of a traversal then we look at the surface such that the halfedges around a face are oriented counterclockwise, as illustrated in Figure 28.1

The connectivity does not allow to represent faces with holes.

Ranges and Iterators

Surface_mesh provides iterator ranges to enumerate all vertices, halfedges, edges, and faces. It provides member functions returning ranges of elements which are compatible with the Boost.Range library.

Example

The following example shows how to obtain the iterator type from a range, alternatives for obtaining the begin and end iterator, and alternatives for range-based loops.

File Surface_mesh/sm_iterators.cpp

#include <vector>
 
 
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
 
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
typedef Mesh::Face_index face_descriptor;
int main()
{
  Mesh m;
 
  // u            x
  // +------------+
  // |            |
  // |            |
  // |      f     |
  // |            |
  // |            |
  // +------------+
  // v            w
 
  // Add the points as vertices
  vertex_descriptor u = m.add_vertex(K::Point_3(0,1,0));
  vertex_descriptor v = m.add_vertex(K::Point_3(0,0,0));
  vertex_descriptor w = m.add_vertex(K::Point_3(1,0,0));
  vertex_descriptor x = m.add_vertex(K::Point_3(1,1,0));
 
  /* face_descriptor f = */ m.add_face(u,v,w,x);
 
  {
    std::cout << "all vertices " << std::endl;
 
    // The vertex iterator type is a nested type of the Vertex_range
    Mesh::Vertex_range::iterator  vb, ve;
 
    Mesh::Vertex_range r = m.vertices();
    // The iterators can be accessed through the C++ range API
    vb = r.begin();
    ve = r.end();
    // or the boost Range API
    vb = std::begin(r);
    ve = std::end(r);
 
    // or with boost::tie, as the CGAL range derives from std::pair
    for(boost::tie(vb, ve) = m.vertices(); vb != ve; ++vb){
            // Print vertex index and vertex coordinates
            std::cout << *vb << " " << m.point(*vb) << std::endl;
    }
 
    // Instead of the classical for loop one can use
    // the boost macro for a range
    for(vertex_descriptor vd : m.vertices()){
      std::cout << vd << std::endl;
    }
 
    // or the C++11 for loop. Note that there is a ':' and not a ',' as in BOOST_FOREACH
    for(vertex_descriptor vd : m.vertices()){
      std::cout << vd << std::endl;
    }
 
  }
 
  return 0;
}

Circulators

Circulators around faces and around vertices are provided as class templates in the package CGAL and the Boost Graph Library.

Circulators around faces basically call Surface_mesh::next() in order to go from halfedge to halfedge counterclockwise around the face, and when dereferenced return the halfedge or the incident vertex or the opposite face.

CGAL::Halfedge_around_face_circulator<Mesh>
CGAL::Vertex_around_face_circulator<Mesh>
CGAL::Face_around_face_circulator<Mesh>

Circulators around the target vertex of an edge basically call Surface_mesh::opposite(Surface_mesh::next()) in order to go from halfedge to halfedge clockwise around the same target vertex.

CGAL::Halfedge_around_target_circulator<Mesh>
CGAL::Vertex_around_target_circulator<Mesh>
CGAL::Face_around_target_circulator<Mesh>

All circulators model BidirectionalCirculator. In addition to that they also support a conversion to bool for more convenient checking of emptiness.

Example

The following example shows how to enumerate the vertices around the target of a given halfedge. The second loop shows that each of these circulator types comes with an equivalent iterator and a free function to create an iterator range.

File Surface_mesh/sm_circulators.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
 
#include <vector>
 
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
typedef Mesh::Face_index face_descriptor;
 
int main()
{
  Mesh m;
 
  // u            x
  // +------------+
  // |            |
  // |            |
  // |      f     |
  // |            |
  // |            |
  // +------------+
  // v            w
 
  // Add the points as vertices
  vertex_descriptor u = m.add_vertex(K::Point_3(0,1,0));
  vertex_descriptor v = m.add_vertex(K::Point_3(0,0,0));
  vertex_descriptor w = m.add_vertex(K::Point_3(1,0,0));
  vertex_descriptor x = m.add_vertex(K::Point_3(1,1,0));
 
  face_descriptor f = m.add_face(u,v,w,x);
 
  {
    std::cout << "vertices around vertex " << v << std::endl;
    CGAL::Vertex_around_target_circulator<Mesh> vbegin(m.halfedge(v),m), done(vbegin);
 
    do {
      std::cout << *vbegin++ << std::endl;
    } while(vbegin != done);
  }
 
  {
    std::cout << "vertices around face " << f << std::endl;
    CGAL::Vertex_around_face_iterator<Mesh> vbegin, vend;
    for(boost::tie(vbegin, vend) = vertices_around_face(m.halfedge(f), m);
        vbegin != vend;
        ++vbegin){
      std::cout << *vbegin << std::endl;
    }
  }
 
  // or the same again, but directly with a range based loop
  for(vertex_descriptor vd : vertices_around_face(m.halfedge(f), m)){
    std::cout << vd << std::endl;
  }
 
 
  return 0;
}

Properties

Surface_mesh provides a mechanism to specify new properties for vertices, halfedges, edges, and faces at run-time. Each property is identified by a string and its key type. All the values of a given property are stored as consecutive blocks of memory. References to properties are invalidated whenever new elements of the key type are added to the data-structure or when the function Surface_mesh::collect_garbage() is performed. Properties of an element will continue to exist after the element has been deleted. Trying to access a property through an invalidated element will result in undefined behavior.

One property is maintained by default, namely "v:point". The value of this property has to be supplied when adding a new point to the data structure via Surface_mesh::add_vertex(). The property can be directly accessed using Surface_mesh::points() or Surface_mesh::point(Surface_mesh::Vertex_index v).

When an element is removed, it is only marked as removed, and it gets really removed when Surface_mesh::collect_garbage() is called. Garbage collection will also really remove the properties of these elements.

The connectivity is also stored in properties, namely the properties named "v:connectivity", "h:connectivity", and "f:connectivity". It is quite similar for the marker of deleted element, where we have "v:removed", "e:removed", and "f:removed".

Convenience functions are provided to remove property maps added by a user, either by index type (Surface_mesh::remove_property_maps<I>()) or all of them (Surface_mesh::remove_all_property_maps()).

To clear a mesh, you have the possibility to get a mesh with all added property maps removed (Surface_mesh::clear()) or to keep them (Surface_mesh::clear_without_removing_property_maps()). Note that in both cases, the "v:point" property map will be preserved and keeping a reference to it is safe.

Example

This example shows how to use the most common features of the property system.

File Surface_mesh/sm_properties.cpp

#include <string>
 
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/boost/graph/generators.h>
 
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
typedef Mesh::Face_index face_descriptor;
 
int main()
{
  Mesh m;
  vertex_descriptor v0 = m.add_vertex(K::Point_3(0,2,0));
  vertex_descriptor v1 = m.add_vertex(K::Point_3(2,2,0));
  vertex_descriptor v2 = m.add_vertex(K::Point_3(0,0,0));
  vertex_descriptor v3 = m.add_vertex(K::Point_3(2,0,0));
  vertex_descriptor v4 = m.add_vertex(K::Point_3(1,1,0));
  m.add_face(v3, v1, v4);
  m.add_face(v0, v4, v1);
  m.add_face(v0, v2, v4);
  m.add_face(v2, v3, v4);
 
 
  // give each vertex a name, the default is empty
  Mesh::Property_map<vertex_descriptor,std::string> name;
  bool created;
  boost::tie(name, created) = m.add_property_map<vertex_descriptor,std::string>("v:name","m1");
  assert(created);
  // add some names to the vertices
  name[v0] = "hello";
  name[v2] = "world";
 
  {
    // You get an existing property, and created will be false
    Mesh::Property_map<vertex_descriptor,std::string> name;
    bool created;
    boost::tie(name, created) = m.add_property_map<vertex_descriptor,std::string>("v:name", "");
    assert(! created);
  }
 
  //  You can't get a property that does not exist
  std::optional<Mesh::Property_map<face_descriptor,std::string>> gnus = m.property_map<face_descriptor,std::string>("v:gnus");
  assert(!gnus.has_value());
 
  // retrieve the point property for which exists a convenience function
  Mesh::Property_map<vertex_descriptor, K::Point_3> location = m.points();
  for(vertex_descriptor vd : m.vertices()) {
    std::cout << name[vd] << " @ " << location[vd] << std::endl;
  }
 
  Mesh m2;
  CGAL::make_triangle(K::Point_3(0,0,1), K::Point_3(1,0,1),K::Point_3(0,1,1), m2);
 
  m2.add_property_map<vertex_descriptor,std::string>("v:name","m2");
  Mesh::Property_map<vertex_descriptor,int> index;
  index = m2.add_property_map<vertex_descriptor,int>("v:index",-1).first;
  int i = 0;
  for (auto v : vertices(m2)) {
      index[v] = i++;
  }
 
  std::cout << "properties of m1:" << std::endl;
  std::vector<std::string> props = m.properties<vertex_descriptor>();
  for(std::string p : props){
    std::cout << p << std::endl;
  }
 
  m.join(m2);
  std::cout << "properties of m1 after join:" << std::endl;
  for(std::string p : m.properties<vertex_descriptor>()){
    std::cout << p << std::endl;
  }
 
  for (auto v : vertices(m)) {
    std::cout << name[v] << std::endl;
  }
  // delete the string property again
  m.remove_property_map(name);
 
  return 0;
}

Borders

A halfedge stores a reference to a face, its incident face. A halfedge h is on the border, if it has no incident face, that is if sm.face(h) == Surface_mesh::null_face(). An edge is on the border, if any of its halfedges is on the border. A vertex is on the border, if any of its incident halfedges is on the border.

A vertex has only one associated halfedge. If the user takes care that the associated halfedge is a border halfedge, in case the vertex is on the border, there is no need to look at all incident halfedges in the is_border() function for vertices. In order to only check if the associated halfedge is on the border the function Surface_mesh::is_border(Vertex_index v, bool check_all_incident_halfedges = true) must be called with check_all_incident_halfedges = false.

The user is in charge to correctly set the halfedge associated to a vertex after having applied an operation that might invalidate this property. The functions Surface_mesh::set_vertex_halfedge_to_border_halfedge(Vertex_index v), Surface_mesh::set_vertex_halfedge_to_border_halfedge(Halfedge_index h), and Surface_mesh::set_vertex_halfedge_to_border_halfedge() enable to set the border halfedge for a single vertex v, for all vertices on the boundary of the face of h, and for all vertices of the surface mesh, respectively.

Surface Mesh and the BGL API

The class Surface_mesh is a model of the concept IncidenceGraph defined in the Boost Graph Library. This enables to apply algorithms such as Dijkstra shortest path, or Kruskal minimum spanning tree directly on a surface mesh.

The types and free functions of the BGL API have each a similar type or member function, for example

BGL	Surface_mesh	Remark
`boost::graph_traits<G>::vertex_descriptor`	`Surface_mesh::Vertex_index`
`boost::graph_traits<G>::edge_descriptor`	`Surface_mesh::Edge_index`
`vertices(const G& g)`	`sm.vertices()`
`edges(const G& g)`	`sm.edges()`
`vd = source(ed,g)`	`vd = sm.source(ed)`
na	`n = sm.number_of_vertices()`	counts non-deleted vertices and has no BGL equivalent
`n = num_vertices(g)`	`n = sm.number_of_vertices() + sm.number_of_removed_vertices()`	counts used and deleted vertices in order to have an upper bound on the largest vertex index used

It would be nicer to return the number of vertices without taking removed vertices into account, but this would interact badly with the underlying vertex/edge index mappings. The index mapping would no longer fall in the range [0,num_vertices(g)) which is assumed in many of the algorithms.

The class Surface_mesh is also a model of the concept MutableFaceGraph defined in the package CGAL and the Boost Graph Library. This and similar concepts like HalfedgeGraph refine the graph concepts of the BGL by introducing the notion of halfedges and faces, as well as cycles of halfedges around faces and around vertices. Again, there are similar types and functions, for example:

BGL	Surface_mesh
`boost::graph_traits<G>::halfedge_descriptor`	`Surface_mesh::Halfedge_index`
`boost::graph_traits<G>::face_descriptor`	`Surface_mesh::Face_index`
`halfedges(const G& g)`	`sm.halfedges()`
`faces(const G& g)`	`sm.faces()`
`hd = next(hd, g)`	`hd = sm.next(hd)`
`hd = prev(hd, g)`	`hd = sm.prev(hd)`
`hd = opposite(hd,g)`	`hd = sm.opposite(hd)`
`hd = halfedge(vd,g)`	`hd = sm.halfedge(vd)`
etc.

The BGL API described in the package CGAL and the Boost Graph Library enables us to write geometric algorithms operating on surface meshes, that work for any model of FaceGraph, or MutableFaceGraph. That is surface mesh simplification, deformation, or segmentation algorithms work for Surface_mesh and Polyhedron_3.

BGL algorithms use property maps in order to associate information to vertices and edges. One important property is the index, an integer between 0 and num_vertices(g) for the vertices of a graph g. This allows algorithms to create a vector of the appropriate size in order to store per vertex information. For example a Boolean for storing if a vertex has already been visited during a graph traversal.

The BGL way of retrieving the vertex index property map of a graph g is vipm = get(boost::vertex_index, g), and get(vipm, vd) in order then to retrieve the index for a vertex descriptor vd, and it is get(vertex_index, g, vd) to obtain the vertex index directly.

Example

The first example shows that we can apply Kruskal's minimum spanning tree algorithm directly on a surface mesh.

File Surface_mesh/sm_kruskal.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
 
#include <boost/graph/kruskal_min_spanning_tree.hpp>
 
#include <iostream>
#include <fstream>
#include <list>
 
typedef CGAL::Simple_cartesian<double>                       Kernel;
typedef Kernel::Point_3                                      Point;
typedef CGAL::Surface_mesh<Point>                            Mesh;
 
typedef boost::graph_traits<Mesh>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Mesh>::vertex_iterator   vertex_iterator;
typedef boost::graph_traits<Mesh>::edge_descriptor   edge_descriptor;
 
void kruskal(const Mesh& sm)
{
   // We use the default edge weight which is the squared length of the edge
 
  std::list<edge_descriptor> mst;
 
  boost::kruskal_minimum_spanning_tree(sm,
                                       std::back_inserter(mst));
 
  std::cout << "#VRML V2.0 utf8\n"
    "Shape {\n"
    "  appearance Appearance {\n"
    "    material Material { emissiveColor 1 0 0}}\n"
    "    geometry\n"
    "    IndexedLineSet {\n"
    "      coord Coordinate {\n"
    "        point [ \n";
 
  vertex_iterator vb,ve;
  for(boost::tie(vb, ve) = vertices(sm); vb!=ve; ++vb){
    std::cout <<  "        " << sm.point(*vb) << "\n";
  }
 
  std::cout << "        ]\n"
               "     }\n"
    "      coordIndex [\n";
 
  for(std::list<edge_descriptor>::iterator it = mst.begin(); it != mst.end(); ++it)
  {
    edge_descriptor e = *it ;
    vertex_descriptor s = source(e,sm);
    vertex_descriptor t = target(e,sm);
    std::cout << "      " << s << ", " << t <<  ", -1\n";
  }
 
  std::cout << "]\n"
    "  }#IndexedLineSet\n"
    "}# Shape\n";
}
 
int main(int argc, char** argv)
{
  Mesh sm;
  std::string fname = argc==1?CGAL::data_file_path("meshes/knot1.off"):argv[1];
  if(!CGAL::IO::read_polygon_mesh(fname, sm))
  {
    std::cerr << "Invalid input file." << std::endl;
    return EXIT_FAILURE;
  }
 
  kruskal(sm);
 
  return 0;
}

The second example shows how we can use property maps for algorithms such as Prim's minimum spanning tree. The algorithm internally also uses a vertex index property map calling get(boost::vertex_index_t,sm). For the class Surface_mesh this boils down to an identity function as vertices are indices.

File Surface_mesh/sm_bgl.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
 
#include <iostream>
#include <fstream>
 
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
 
typedef CGAL::Simple_cartesian<double>                       Kernel;
typedef Kernel::Point_3                                      Point;
typedef CGAL::Surface_mesh<Point>                            Mesh;
 
typedef boost::graph_traits<Mesh>::vertex_descriptor vertex_descriptor;
 
int main(int argc, char* argv[])
{
  Mesh sm;
  std::string fname = argc==1?CGAL::data_file_path("meshes/knot1.off"):argv[1];
  if(!CGAL::IO::read_polygon_mesh(fname, sm))
  {
    std::cerr << "Invalid input file." << std::endl;
    return EXIT_FAILURE;
  }
 
  Mesh::Property_map<vertex_descriptor,vertex_descriptor> predecessor;
  predecessor = sm.add_property_map<vertex_descriptor,vertex_descriptor>("v:predecessor").first;
 
  boost::prim_minimum_spanning_tree(sm, predecessor, boost::root_vertex(*vertices(sm).first));
 
  std::cout << "#VRML V2.0 utf8\n"
    "DirectionalLight {\n"
    "direction 0 -1 0\n"
    "}\n"
    "Shape {\n"
    "  appearance Appearance {\n"
    "    material Material { emissiveColor 1 0 0}}\n"
    "    geometry\n"
    "    IndexedLineSet {\n"
    "      coord Coordinate {\n"
    "        point [ \n";
 
  for(vertex_descriptor vd : vertices(sm)){
    std::cout <<  "        " << sm.point(vd) << "\n";
  }
 
  std::cout << "        ]\n"
    "     }\n"
    "      coordIndex [\n";
  for(vertex_descriptor vd : vertices(sm)){
    if(predecessor[vd]!=vd){
      std::cout << "      " << std::size_t(vd) << ", " << std::size_t(predecessor[vd]) <<  ", -1\n";
    }
  }
 
  std::cout << "]\n"
    "  }#IndexedLineSet\n"
    "}# Shape\n";
 
  sm.remove_property_map(predecessor);
  return 0;
}

Surface Mesh I/O

As a model of FaceGraph (see Section Surface Mesh and the BGL API), CGAL::Surface_mesh can be read from and written using a number of different file formats. Refer to the I/O Functions of the CGAL and the Boost Graph Library package, and the I/O Functions of the Polygon Mesh Processing package for more information.

In addition, this package provides Surface_mesh-specific overloads of the I/O functions from the CGAL and the Boost Graph Library package. This enables reading/writing directly from/to internal property maps, see I/O Functions for more information.

Memory Management

Memory management is semi-automatic. Memory grows as more elements are added to the structure but does not shrink when elements are removed.

When you add elements and the capacity of the underlying vector is exhausted, the vector reallocates memory. As descriptors are basically indices, they refer to the same element after a reallocation.

When you remove an element it is only marked as removed. Internally it is put in a free list, and when you add elements to the surface mesh, they are taken from the free list in case it is not empty.

For all elements we offer a function to obtain the number of used elements, as well as the number of used and removed elements. For vertices the functions are Surface_mesh::number_of_vertices() and Surface_mesh::number_of_removed_vertices(), respectively. The first function is slightly different from the free function num_vertices(const G&) of the BGL package. As BGL style algorithms use the indices of elements to access data in temporary vectors of size num_vertices() this function must return a number larger than the largest index of the elements.

Iterators such as Surface_mesh::Vertex_iterator only enumerate elements that are not marked as deleted.

To really shrink the used memory, Surface_mesh::collect_garbage() must be called. Garbage collection also compacts the properties associated with the surface mesh.

Note however that by garbage collecting elements get new indices. In case you keep vertex descriptors they are most probably no longer referring to the right vertices.

Example

File Surface_mesh/sm_memory.cpp

#include <iostream>
 
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
 
typedef CGAL::Simple_cartesian<double> K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef Mesh::Vertex_index vertex_descriptor;
 
int main()
{
  Mesh m;
  Mesh::Vertex_index u;
  for(unsigned int i=0; i < 5; ++i){
    Mesh::Vertex_index v = m.add_vertex(K::Point_3(0,0,i+1));
    if(i==2) u=v;
  }
 
  m.remove_vertex(u);
 
  std::cout << "After insertion of 5 vertices and removal of the 3. vertex\n"
            << "# vertices  / # vertices + # removed vertices = "
            << m.number_of_vertices()
            << " / " << m.number_of_vertices() + m.number_of_removed_vertices() << std::endl;
 
  std::cout << "Iterate over vertices\n";
  {
    for(vertex_descriptor vd : m.vertices()){
      std::cout << m.point(vd) << std::endl;
    }
  }
 
  // The status of being used or removed is stored in a property map
  Mesh::Property_map<Mesh::Vertex_index,bool> removed
    = m.property_map<Mesh::Vertex_index,bool>("v:removed").value();
 
 
  std::cout << "\nIterate over vertices and deleted vertices\n"
            << "# vertices / # vertices + # removed vertices = "
            << m.number_of_vertices()
            << " / " << m.number_of_vertices() + m.number_of_removed_vertices() << std::endl;
    {
    unsigned int i = 0, end = m.number_of_vertices() + m.number_of_removed_vertices();
    for( ; i < end; ++i) {
      vertex_descriptor vh(i);
      assert(m.is_removed(vh) == removed[vh]);
      std::cout << m.point(vh) << ((m.is_removed(vh)) ? "  R\n" : "\n");
    }
  }
 
  m.collect_garbage();
 
  std::cout << "\nAfter garbage collection\n"
            << "# vertices / # vertices + # removed vertices = "
            << m.number_of_vertices()
            << " / " << m.number_of_vertices() + m.number_of_removed_vertices() << std::endl;
 
 {
   unsigned int i = 0, end = m.number_of_vertices() + m.number_of_removed_vertices();
    for( ; i < end; ++i) {
      vertex_descriptor vh(i);
      std::cout << m.point(vh) << ((m.is_removed(vh)) ? "  R\n" : "\n");
    }
  }
 
  return 0;
}

Draw a Surface Mesh

A surface mesh can be visualized by calling the CGAL::draw<SM>() as shown in the following example. This function opens a new window showing the given surface mesh. A call to this function is blocking, that is the program continues as soon as the user closes the window.

File Surface_mesh/draw_surface_mesh.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/draw_surface_mesh.h>
#include <fstream>
 
typedef CGAL::Simple_cartesian<double>                       Kernel;
typedef Kernel::Point_3                                      Point;
typedef CGAL::Surface_mesh<Point>                            Mesh;
 
int main(int argc, char* argv[])
{
  const std::string filename = (argc>1) ? argv[1] : CGAL::data_file_path("meshes/elephant.off");
 
  Mesh sm;
  if(!CGAL::IO::read_polygon_mesh(filename, sm))
  {
    std::cerr << "Invalid input file: " << filename << std::endl;
    return EXIT_FAILURE;
  }
 
  // Internal color property maps are used if they exist and are called "v:color", "e:color" and "f:color".
  auto vcm = sm.add_property_map<Mesh::Vertex_index, CGAL::IO::Color>("v:color").first;
  auto ecm = sm.add_property_map<Mesh::Edge_index, CGAL::IO::Color>("e:color").first;
  auto fcm = sm.add_property_map<Mesh::Face_index>("f:color", CGAL::IO::white() /*default*/).first;
 
  for(auto v : vertices(sm))
  {
    if(v.idx()%2)
    { put(vcm, v, CGAL::IO::black()); }
    else
    { put(vcm, v, CGAL::IO::blue()); }
  }
 
  for(auto e : edges(sm))
  { put(ecm, e, CGAL::IO::gray()); }
 
  put(fcm, *(sm.faces().begin()), CGAL::IO::red());
 
  // Draw!
  CGAL::draw(sm);
 
  return EXIT_SUCCESS;
}

This function requires CGAL_Qt6, and is only available if the macro CGAL_USE_BASIC_VIEWER is defined. Linking with the cmake target CGAL::CGAL_Basic_viewer will link with CGAL_Qt6 and add the definition CGAL_USE_BASIC_VIEWER.

Figure 28.2 Result of the run of the draw_surface_mesh program. A window shows the surface mesh and allows to navigate through the 3D scene.

Implementation Details

As integer type for the indices we have chosen std::uint32_t. On 64 bit operating systems they take only half the size of a pointer. They still allow to have meshes with 2 billion elements.

We use std::vector for storing properties. So by accessing the address of the 0th element of a property map you can access the underlying raw array. This may be useful, for example for passing an array of points to OpenGL.

We use a freelist for removed elements. This mean when a vertex gets removed and later add_vertex is called, the memory of the removed element is reused. This especially means that the n'th inserted element has not necessarily the index n-1, and when iterating over elements they will not be enumerated in the insertion order.

Implementation History

This package is derived from an early version of Daniel Sieger and Mario Botsch package Surface_mesh [1], which is inspired from the design of OpenMesh and the CGAL package 3D Polyhedral Surface.

Philipp Moeller and Andreas Fabri worked on the code so that iterators fulfill the requirements of the STL iterator concepts, and changed the API so that it becomes a model of the concepts MutableFaceGraph and FaceListGraph of the package CGAL and the Boost Graph Library.