\( \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 - Surface Mesh
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Surface_mesh< P > Class Template 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
PThe 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
See Also
Graph Concepts
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 >
bool write_off (std::ostream &os, const Surface_mesh< P > &sm)
 
template<typename P >
std::ostream & operator<< (std::ostream &os, const Surface_mesh< P > &sm)
 
template<typename P >
bool read_off (std::istream &is, 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_meshoperator= (const Surface_mesh &rhs)
 assigns rhs to *this. Performs a deep copy of all properties.
 
Surface_meshassign (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 isolated or 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, or if the vertex is isolated.

 
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 Properties::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, Pointpoints () const
 returns the property for the string "v:point".
 
Property_map< Vertex_index,
Point > & 
points ()
 
const Pointpoint (Vertex_index v) const
 returns the point associated to vertex v.
 
Pointpoint (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
IThe key type of the properties.