CGAL 5.6.3 - Surface Mesh

Loading...
Searching...
No Matches
User Manual

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:

- `Surface_mesh::Vertex_index`
- `Surface_mesh::Halfedge_index`
- `Surface_mesh::Face_index`
- `Surface_mesh::Edge_index`

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;
}
CGAL::Surface_mesh
This class is a data structure that can be used as halfedge data structure or polyhedral surface.
Definition: Surface_mesh.h:336
CGAL::Surface_mesh::add_vertex
Vertex_index add_vertex()
adds a new vertex, and resizes vertex properties if necessary.
Definition: Surface_mesh.h:988
CGAL::Simple_cartesian

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;
}
CGAL::vertices_around_face
Iterator_range< Vertex_around_face_iterator< Graph > > vertices_around_face(typename boost::graph_traits< Graph >::halfedge_descriptor h, const Graph &g)
CGAL::convex_hull_3
void convex_hull_3(InputIterator first, InputIterator last, PolygonMesh &pm, const Traits &ch_traits=Default_traits)

# 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 27.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 27.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 = boost::begin(r);
ve = boost::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;
}
CGAL::Vertex_around_face_iterator
CGAL::Vertex_around_target_circulator

# 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
Mesh::Property_map<face_descriptor,std::string> gnus;
bool found;
boost::tie(gnus, found) = m.property_map<face_descriptor,std::string>("v:gnus");
assert(! found);
// 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;
}
CGAL::make_triangle
boost::graph_traits< Graph >::halfedge_descriptor make_triangle(const P &p0, const P &p1, const P &p2, Graph &g)

# 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;
}
Kernel::Point_3
CGAL::IO::read_polygon_mesh
bool read_polygon_mesh(const std::string &fname, Graph &g, const NamedParameters &np=parameters::default_values())
Kernel

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").first;
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." << 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());
CGAL_USE(fcm);
// Draw!
CGAL::draw(sm);
return EXIT_SUCCESS;
}
CGAL::IO::Color
CGAL::Surface_mesh::add_property_map
std::pair< Property_map< I, T >, bool > add_property_map(std::string name=std::string(), const T t=T())
adds a property map named name with value type T and default t for index type I.
Definition: Surface_mesh.h:2077
CGAL::draw
void draw(const POLY &apoly)

This function requires `CGAL_Qt5`, 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_Qt5` and add the definition `CGAL_USE_BASIC_VIEWER`.

Figure 27.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 `boost::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.