CGAL 4.7 - Surface Mesh: CGAL::Surface_mesh< P > Class Template Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - Surface Mesh

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members | Classes | Related Functions
CGAL::Surface_mesh< P > Class Template Reference
Surface Mesh Reference

`#include <CGAL/Surface_mesh.h>`

## Definition

This class is a data structure that can be used as halfedge data structure or polyhedral surface. It is an alternative to the classes `HalfedgeDS` and `Polyhedron_3` defined in the packages Halfedge Data Structures and 3D Polyhedral Surface. The main difference is that it is indexed based and not pointer based, and that the mechanism for adding information to vertices, halfedges, edges, and faces is much simpler and done at runtime and not at compile time. When elements are removed, they are only marked as removed, and a garbage collection function must be called to really remove them.

Template Parameters

  P | The type of the point property of a vertex. There is no requirement on `P`, besides being default constructible and assignable. In typical use cases it will be a 2D or 3D point type.

Is Model Of:
  `MutableFaceGraph` and `FaceListGraph`

Examples:
  Surface_mesh/sm_bgl.cpp, Surface_mesh/sm_circulators.cpp, Surface_mesh/sm_iterators.cpp, Surface_mesh/sm_kruskal.cpp, Surface_mesh/sm_memory.cpp, and Surface_mesh/sm_properties.cpp.

## Classes

class | Edge_index
| This class represents an edge. More...
class | Face_index
| This class represents a face. More...
class | Halfedge_index
| This class represents a halfedge. More...
class | Vertex_index
| This class represents a vertex. More...

## Related Functions

(Note that these are not member functions.)
template<typename P >
Surface_mesh< P > & | operator+= (Surface_mesh< P > &sm, const Surface_mesh< P > &other)
template<typename P >
std::ostream & | operator<< (std::ostream &os, const Surface_mesh< P > &sm)
template<typename P >
std::istream & | operator>> (std::istream &is, Surface_mesh< P > &sm)

## Basic Types

typedef P | Point
| The point type.
typedef boost::uint32_t | size_type
| The type used to represent an index.

## Range Types

Each range `R` in this section has a nested type `R::iterator`, is convertible to `std:pair<R::iterator,R::iterator>`, so that one can use `boost::tie()`, and can be used with `BOOST_FOREACH()`, as well as with the C++11 range based for-loop.
typedef unspecified_type | Vertex_range
| The range over all vertex indices. More...
typedef unspecified_type | Halfedge_range
| The range over all halfedge indices. More...
typedef unspecified_type | Edge_range
| The range over all edge indices. More...
typedef unspecified_type | Face_range
| The range over all face indices. More...
Vertex_range | vertices () const
| returns the iterator range of the vertices of the mesh.
Halfedge_range | halfedges () const
| returns the iterator range of the halfedges of the mesh.
Edge_range | edges () const
| returns the iterator range of the edges of the mesh.
Face_range | faces () const
| returns the iterator range of the faces of the mesh.

## Construction, Destruction, Assignment

Copy constructors as well as assignment do also copy simplices marked as removed.
| Surface_mesh ()
| Default constructor.
| Surface_mesh (const Surface_mesh &rhs)
| Copy constructor: copies `rhs` to `*this`. Performs a deep copy of all properties.
Surface_mesh & | operator= (const Surface_mesh &rhs)
| assigns `rhs` to `*this`. Performs a deep copy of all properties.
Surface_mesh & | assign (const Surface_mesh &rhs)
| assigns `rhs` to `*this`. Does not copy custom properties.

## Adding Vertices, Edges, and Faces

Vertex_index | add_vertex ()
| adds a new vertex, and resizes vertex properties if necessary.
Vertex_index | add_vertex (const Point &p)
| adds a new vertex, resizes vertex properties if necessary, and sets the point property to `p`. More...
Halfedge_index | add_edge ()
| adds a new edge, and resizes edge and halfedge properties if necessary.
Halfedge_index | add_edge (Vertex_index v0, Vertex_index v1)
| adds two opposite halfedges, and resizes edge and halfedge properties if necessary. Sets the targets of the halfedge to the given vertices, but does not modify the halfedge associated to the vertices. More...
Face_index | add_face ()
| adds a new face, and resizes face properties if necessary.
template<typename Range >
Face_index | add_face (const Range &vertices)

if possible, adds a new face with vertices from a range with value type `Vertex_index`. The function adds halfedges between successive vertices if they are not yet indicent to halfedges, or updates the connectivity of halfedges already in place. Resizes halfedge, edge, and face properties if necessary. More...

Face_index | add_face (Vertex_index v0, Vertex_index v1, Vertex_index v2)
| adds a new triangle connecting vertices `v0`, `v1`, `v2`. More...
Face_index | add_face (Vertex_index v0, Vertex_index v1, Vertex_index v2, Vertex_index v3)
| adds a new quad connecting vertices `v0`, `v1`, `v2`, `v3`. More...

## Low-Level Removal Functions

Although the elements are only marked as removed their connectivity and properties should not be used.

Warning
  Functions in this group do not adjust any of connected elements and usually leave the surface mesh in an invalid state.

void | remove_vertex (Vertex_index v)
| removes vertex `v` from the halfedge data structure without adjusting anything.
void | remove_edge (Edge_index e)
| removes the two halfedges corresponding to `e` from the halfedge data structure without adjusting anything.
void | remove_face (Face_index f)
| removes face `f` from the halfedge data structure without adjusting anything.

## Memory Management

Functions to check the number of elements, the amount of space allocated for elements, and to clear the structure.
size_type | number_of_vertices () const
| returns the number of vertices in the mesh.
size_type | number_of_halfedges () const
| returns the number of halfedges in the mesh.
size_type | number_of_edges () const
| returns the number of edges in the mesh.
size_type | number_of_faces () const
| returns the number of faces in the mesh.
bool | is_empty () const
| returns `true` iff the mesh is empty, i.e., has no vertices, halfedges and faces.
void | clear ()
| removes all vertices, halfedge, edges and faces. Collects garbage and clears all properties.
void | reserve (size_type nvertices, size_type nedges, size_type nfaces)
| reserves space for vertices, halfedges, edges, faces, and their currently associated properties.
void | resize (size_type nvertices, size_type nedges, size_type nfaces)
bool | join (const Surface_mesh &other)

## Garbage Collection

While removing elements only marks them as removed garbage collection really removes them. The API in this section allows to check whether an element is removed, to get the number of removed elements, and to collect garbage. The number of elements together with the number of removed elements is an upperbound on the index, and is needed by algorithms that temporarily store a property in a vector of the appropriate size. Note however that by garbage collecting elements get new indices. In case you store indices in an auxiliary data structure or in a property these indices are potentially no longer refering to the right elements.
size_type | number_of_removed_vertices () const
| returns the number of vertices in the mesh which are marked removed.
size_type | number_of_removed_halfedges () const
| returns the number of halfedges in the mesh which are marked removed.
size_type | number_of_removed_edges () const
| returns the number of edges in the mesh which are marked removed.
size_type | number_of_removed_faces () const
| returns the number offaces in the mesh which are marked removed.
bool | is_removed (Vertex_index v) const
| returns whether vertex `v` is marked removed. More...
bool | is_removed (Halfedge_index h) const
| returns whether halfedge `h` is marked removed. More...
bool | is_removed (Edge_index e) const
| returns whether edge `e` is marked removed. More...
bool | is_removed (Face_index f) const
| returns whether face `f` is marked removed. More...
bool | has_garbage () const
| checks if any vertices, halfedges, edges, or faces are marked as removed. More...
void | collect_garbage ()
| really removes vertices, halfedges, edges, and faces which are marked removed. More...

## Validity Checks

Functions in this group perform checks for structural consistency of a complete surface mesh, or an individual element. They are expensive and should only be used in debug configurations.
bool | is_valid (bool verbose=true) const
| perform an expensive validity check on the data structure and print found errors to `std::cerr` when `verbose == true`.
bool | is_valid (Vertex_index v) const
| performs a validity check on a single vertex.
bool | is_valid (Halfedge_index h) const
| performs a validity check on a single halfedge.
bool | is_valid (Edge_index e) const
| performs a validity check on a single ede.
bool | is_valid (Face_index f) const
| performs a validity check on a single face.

## Low-Level Connectivity

Vertex_index | target (Halfedge_index h) const
| returns the vertex the halfedge `h` points to.
void | set_target (Halfedge_index h, Vertex_index v)
| sets the vertex the halfedge `h` points to to `v`.
Face_index | face (Halfedge_index h) const
| returns the face incident to halfedge `h`.
void | set_face (Halfedge_index h, Face_index f)
| sets the incident face to halfedge `h` to `f`.
Halfedge_index | next (Halfedge_index h) const
| returns the next halfedge within the incident face.
Halfedge_index | prev (Halfedge_index h) const
| returns the previous halfedge within the incident face.
void | set_next (Halfedge_index h, Halfedge_index nh)
| sets the next halfedge of `h` within the face to `nh` and the previous halfedge of `nh` to `h`.
Halfedge_index | halfedge (Vertex_index v) const
| returns an incoming halfedge of vertex `v`. If `v` is a border vertex this will be a border halfedge. More...
void | set_halfedge (Vertex_index v, Halfedge_index h)
| sets the incoming halfedge of vertex `v` to `h`.
Halfedge_index | halfedge (Face_index f) const
| returns a halfedge of face `f`.
void | set_halfedge (Face_index f, Halfedge_index h)
| sets the halfedge of face `f` to `h`.
Halfedge_index | opposite (Halfedge_index h) const
| returns the opposite halfedge of `h`. Note that there is no function `set_opposite()`.

## Low-Level Connectivity Convenience Functions

Vertex_index | source (Halfedge_index h) const
| returns the vertex the halfedge `h` emanates from.
Halfedge_index | next_around_target (Halfedge_index h) const
| returns `opposite(next(h))`, that is the next halfedge clockwise around the target vertex of `h`.
Halfedge_index | prev_around_target (Halfedge_index h) const
| returns `prev(opposite(h))`, that is the previous halfedge clockwise around the target vertex of `h`.
Halfedge_index | next_around_source (Halfedge_index h) const
| returns `next(opposite(h))`, that is the next halfedge clockwise around the source vertex of `h`.
Halfedge_index | prev_around_source (Halfedge_index h) const
| returns `opposite(prev(h))`, that is the previous halfedge clockwise around the source vertex of `h`.
Vertex_index | vertex (Edge_index e, unsigned int i) const
| returns the i'th vertex of edge `e`, for `i=0` or `1`.
Halfedge_index | halfedge (Vertex_index source, Vertex_index target) const
| finds a halfedge between two vertices. Returns a default constructed `Halfedge_index`, if `source` and `target` are not connected.

## Switching between Halfedges and Edges

Edge_index | edge (Halfedge_index h) const
| returns the edge that contains halfedge `h` as one of its two halfedges.
Halfedge_index | halfedge (Edge_index e) const
| returns the halfedge corresponding to the edge `e`.
Halfedge_index | halfedge (Edge_index e, unsigned int i) const
| returns the i'th halfedge of edge `e`, for `i=0` or `1`.

## Degree Functions

size_type | degree (Vertex_index v) const
| returns the number of incident halfedges of vertex `v`.
size_type | degree (Face_index f) const
| returns the number of incident halfedges of face `f`.

## Borders

A halfedge, or edge is on the border of a surface mesh if it is incident to a `null_face()`. A vertex is on a border if it is incident to a border halfedge. While for a halfedge and edge this is a constant time operation, for a vertex it means to look at all incident halfedges. If algorithms operating on a surface mesh maintain that the halfedge associated to a border vertex is a border halfedge, this is a constant time operation too. This section provides functions to check if an element is on a border and to change the halfedge associated to a border vertex.
bool | is_border (Vertex_index v, bool check_all_incident_halfedges=true) const

returns whether `v` is a border vertex.
Advanced
With the default value for `check_all_incident_halfedges` the function iteratates over the incident halfedges. With `check_all_incident_halfedges == false` the function returns `true`, if the incident halfedge associated to vertex `v` is a border halfedge.

bool | is_border (Halfedge_index h) const
| returns whether `h` is a border halfege, that is if its incident face is `sm.null_face()`.
bool | is_border (Edge_index e) const
| returns whether `e` is a border edge, i.e., if any of its two halfedges is a border halfedge.
bool | set_vertex_halfedge_to_border_halfedge (Vertex_index v)
| iterates over the incident halfedges and sets the incident halfedge associated to vertex `v` to a border halfedge and returns `true` if it exists.
void | set_vertex_halfedge_to_border_halfedge (Halfedge_index h)
| applies `set_vertex_halfedge_to_border_halfedge(Vertex_index)` on all vertices around the face associated to `h`.
void | set_vertex_halfedge_to_border_halfedge ()
| applies `set_vertex_halfedge_to_border_halfedge(Vertex_index)` on all vertices of the surface mesh.
bool | is_isolated (Vertex_index v) const
| returns whether `v` is isolated, i.e., incident to `Surface_mesh::null_halfedge()`.

## Property Handling

A `Property_map<I,T>` allows to associate properties of type `T` to a vertex, halfdge, edge, or face index type I. Properties can be added, and looked up with a string, and they can be removed at runtime. The point property of type `P` is associated to the string "v:point".
template<class I , class T >
using | Property_map = unspecified_type
| Model of `LvaluePropertyMap` with `I` as key type and `T` as value type, where `I` is either a vertex, halfedge, edge, or face index type.
template<class I , class T >
std::pair< Property_map< I, T > , bool > | add_property_map (const std::string &name, const T t=T())

adds a property map named `name` with value type `T` and default `t` for index type `I`. Returns the property map together with a Boolean that is `true` if a new map was created. In case it already exists the existing map together with `false` is returned.

template<class I , class T >
std::pair< Property_map< I, T > , bool > | property_map (const std::string &name) const
| returns a property map named `name` with key type `I` and value type `T`, and a Boolean that is `true` if the property exists. In case it does not exist the Boolean is `false` and the behavior of the property map is undefined.
template<class I , class T >
void | remove_property_map (Property_map< I, T > &p)
| removes property map `p`. The memory allocated for that property map is freed.
template<class I >
std::vector< std::string > | properties () const
| returns a vector with all strings that describe properties with the key type `I`. More...
Property_map< Vertex_index, Point > | points () const
| returns the property for the string "v:point".
const Point & | point (Vertex_index v) const
| returns the point associated to vertex `v`.
Point & | point (Vertex_index v)
| returns the point associated to vertex `v`.

## Null Elements

static Vertex_index | null_vertex ()
| returns `Vertex_index(-1)`.
static Edge_index | null_edge ()
| returns `Edge_index(-1)`.
static Halfedge_index | null_halfedge ()
| returns `Halfedge_index(-1)`.
static Face_index | null_face ()
| returns `Face_index(-1)`.

## Member Typedef Documentation

template<typename P >

typedef unspecified_type CGAL::Surface_mesh< P >::Edge_range

The range over all edge indices.

A model of BidirectionalRange with value type `Edge_index`.

See Also
  `edges()`
  `Halfedge_range`, `Vertex_range`, `Face_range`

template<typename P >

typedef unspecified_type CGAL::Surface_mesh< P >::Face_range

The range over all face indices.

A model of BidirectionalRange with value type `Face_index`.

See Also
  `faces()`
  `Vertex_range`, `Halfedge_range`, `Edge_range`

template<typename P >

typedef unspecified_type CGAL::Surface_mesh< P >::Halfedge_range

The range over all halfedge indices.

A model of BidirectionalRange with value type `Halfedge_index`.

See Also
  `halfedges()`
  `Vertex_range`, `Edge_range`, `Face_range`

template<typename P >

typedef unspecified_type CGAL::Surface_mesh< P >::Vertex_range

The range over all vertex indices.

A model of BidirectionalRange with value type `Vertex_index`.

See Also
  `vertices()`
  `Halfedge_range`, `Edge_range`, `Face_range`

## Member Function Documentation

template<typename P >

Halfedge_index CGAL::Surface_mesh< P >::add_edge | ( | Vertex_index | v0,
|  | Vertex_index | v1
| ) |  |

adds two opposite halfedges, and resizes edge and halfedge properties if necessary. Sets the targets of the halfedge to the given vertices, but does not modify the halfedge associated to the vertices.

Note
  The function does not check whether there is already an edge between the vertices.

Returns
  the halfedge with `v1` as target

template<typename P >
template<typename Range >

Face_index CGAL::Surface_mesh< P >::add_face | ( | const Range & | vertices) |  |

if possible, adds a new face with vertices from a range with value type `Vertex_index`. The function adds halfedges between successive vertices if they are not yet indicent to halfedges, or updates the connectivity of halfedges already in place. Resizes halfedge, edge, and face properties if necessary.

Returns
  the face index of the added face, or `Surface_mesh::null_face()` if the face could not be added.

template<typename P >

Face_index CGAL::Surface_mesh< P >::add_face | ( | Vertex_index | v0,
|  | Vertex_index | v1,
|  | Vertex_index | v2
| ) |  |

adds a new triangle connecting vertices `v0`, `v1`, `v2`.

Returns
  the face index of the added face, or `Surface_mesh::null_face()` if the face could not be added.

template<typename P >

Face_index CGAL::Surface_mesh< P >::add_face | ( | Vertex_index | v0,
|  | Vertex_index | v1,
|  | Vertex_index | v2,
|  | Vertex_index | v3
| ) |  |

adds a new quad connecting vertices `v0`, `v1`, `v2`, `v3`.

Returns
  the face index of the added face, or `Surface_mesh::null_face()` if the face could not be added.

template<typename P >

Vertex_index CGAL::Surface_mesh< P >::add_vertex | ( | const Point & | p) |  |

adds a new vertex, resizes vertex properties if necessary, and sets the point property to `p`.

Note
  Several vertices may have the same point property.

template<typename P >

void CGAL::Surface_mesh< P >::collect_garbage | ( | ) |  |

really removes vertices, halfedges, edges, and faces which are marked removed.

See Also
  `has_garbage()`

Attention
  By garbage collecting elements get new indices. In case you store indices in an auxiliary data structure or in a property these indices are potentially no longer refering to the right elements.

template<typename P >

Halfedge_index CGAL::Surface_mesh< P >::halfedge | ( | Vertex_index | v) |  | const

returns an incoming halfedge of vertex `v`. If `v` is a border vertex this will be a border halfedge.

Invariant
  `target(halfedge(v)) == v`

template<typename P >

bool CGAL::Surface_mesh< P >::has_garbage | ( | ) |  | const

checks if any vertices, halfedges, edges, or faces are marked as removed.

See Also
  collect_garbage

template<typename P >

bool CGAL::Surface_mesh< P >::is_removed | ( | Vertex_index | v) |  | const

returns whether vertex `v` is marked removed.

See Also
  `collect_garbage()`

template<typename P >

bool CGAL::Surface_mesh< P >::is_removed | ( | Halfedge_index | h) |  | const

returns whether halfedge `h` is marked removed.

See Also
  `collect_garbage()`

template<typename P >

bool CGAL::Surface_mesh< P >::is_removed | ( | Edge_index | e) |  | const

returns whether edge `e` is marked removed.

See Also
  `collect_garbage()`

template<typename P >

bool CGAL::Surface_mesh< P >::is_removed | ( | Face_index | f) |  | const

returns whether face `f` is marked removed.

See Also
  `collect_garbage()`

template<typename P >
template<class I >

std::vector<std::string> CGAL::Surface_mesh< P >::properties | ( | ) |  | const

returns a vector with all strings that describe properties with the key type `I`.

Template Parameters

  I | The key type of the properties.