#include <CGAL/Surface_mesh/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

See also: Graph Concepts

Examples:: Surface_mesh/check_orientation.cpp, Surface_mesh/draw_surface_mesh.cpp, Surface_mesh/sm_bgl.cpp, Surface_mesh/sm_circulators.cpp, Surface_mesh/sm_derivation.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 , typename NamedParameters >
bool	write_off (std::ostream &os, const Surface_mesh< P > &sm, const NamedParameters &np)

template<typename P >
std::ostream &	operator<< (std::ostream &os, const Surface_mesh< P > &sm)

template<typename P >
bool	write_ply (std::ostream &os, const Surface_mesh< P > &sm, const std::string &comments=std::string())

template<typename P , typename NamedParameters >
bool	read_off (std::istream &is, Surface_mesh< P > &sm, NamedParameters np)

template<typename P >
bool	read_ply (std::istream &is, Surface_mesh< P > &sm, std::string &comments)
	Extracts the surface mesh from an input stream in Ascii or Binary PLY format and appends it to the surface mesh `sm`. More...

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...

template<typename Visitor >
void	collect_garbage (Visitor &visitor)

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. More...

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 (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`. 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".

Property_map< Vertex_index, Point > &	points ()

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(std::numeric_limits<size_type>::max())`.

static Edge_index	null_edge ()
	returns `Edge_index(std::numeric_limits<size_type>::max())`.

static Halfedge_index	null_halfedge ()
	returns `Halfedge_index(std::numeric_limits<size_type>::max())`.

static Face_index	null_face ()
	returns `Face_index(std::numeric_limits<size_type>::max())`.

Member Typedef Documentation

◆ Edge_range

template<typename P >

typedef unspecified_type CGAL::Surface_mesh::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

◆ Face_range

template<typename P >

typedef unspecified_type CGAL::Surface_mesh::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

◆ Halfedge_range

template<typename P >

typedef unspecified_type CGAL::Surface_mesh::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

◆ Vertex_range

template<typename P >

typedef unspecified_type CGAL::Surface_mesh::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

◆ add_edge()

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

◆ add_face() [1/3]

template<typename P >

template<typename Range >

Face_index CGAL::Surface_mesh::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.

◆ add_face() [2/3]

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.

◆ add_face() [3/3]

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.

◆ add_vertex()

template<typename P >

Vertex_index CGAL::Surface_mesh::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.

◆ collect_garbage()

template<typename P >

void CGAL::Surface_mesh::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.

◆ halfedge()

template<typename P >

Halfedge_index CGAL::Surface_mesh::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

◆ has_garbage()

template<typename P >

bool CGAL::Surface_mesh::has_garbage ( ) const

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

See also: collect_garbage

◆ is_border()

template<typename P >

bool CGAL::Surface_mesh< P >::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.

Attention: If the data contained in the Surface_mesh is not a 2-manifold, then this operation is not guaranteed to return the right result.

◆ is_removed() [1/4]

template<typename P >

bool CGAL::Surface_mesh::is_removed ( Vertex_index v ) const

returns whether vertex v is marked removed.

See also: collect_garbage()

◆ is_removed() [2/4]

template<typename P >

bool CGAL::Surface_mesh::is_removed ( Halfedge_index h ) const

returns whether halfedge h is marked removed.

See also: collect_garbage()

◆ is_removed() [3/4]

template<typename P >

bool CGAL::Surface_mesh::is_removed ( Edge_index e ) const

returns whether edge e is marked removed.

See also: collect_garbage()

◆ is_removed() [4/4]

template<typename P >

bool CGAL::Surface_mesh::is_removed ( Face_index f ) const

returns whether face f is marked removed.

See also: collect_garbage()

◆ properties()

template<typename P >

template<class I >

std::vector<std::string> CGAL::Surface_mesh::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.

Definition

Classes

Related Functions

Basic Types

Range Types

Construction, Destruction, Assignment

Adding Vertices, Edges, and Faces

Low-Level Removal Functions

Memory Management

Garbage Collection

Validity Checks

Low-Level Connectivity

Low-Level Connectivity Convenience Functions

Switching between Halfedges and Edges

Degree Functions

Borders

Property Handling

Null Elements

Member Typedef Documentation

◆ Edge_range

◆ Face_range

◆ Halfedge_range

◆ Vertex_range

Member Function Documentation

◆ add_edge()

◆ add_face() [1/3]

◆ add_face() [2/3]

◆ add_face() [3/3]

◆ add_vertex()

◆ collect_garbage()

◆ halfedge()

◆ has_garbage()

◆ is_border()

◆ is_removed() [1/4]

◆ is_removed() [2/4]

◆ is_removed() [3/4]

◆ is_removed() [4/4]

◆ properties()