#include <CGAL/Surface_mesh/Surface_mesh.h>

Definition

template<typename P>
class CGAL::Surface_mesh

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` `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, Surface_mesh/sm_points.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)
	Inserts `other` into `sm`.

template<typename P >
std::ostream &	operator<< (std::ostream &os, const Surface_mesh< P > &sm)
	This operator calls `write_OFF(std::ostream& os, const CGAL::Surface_mesh& sm)`.

template<typename P >
std::istream &	operator>> (std::istream &is, Surface_mesh< P > &sm)
	Extracts the surface mesh from an input stream in OFF and appends it to the surface mesh `sm`.

Basic Types
typedef P	Point
	The point type.

typedef std::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.

typedef unspecified_type	Halfedge_range
	The range over all halfedge indices.

typedef unspecified_type	Edge_range
	The range over all edge indices.

typedef unspecified_type	Face_range
	The range over all face indices.

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.

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

template<class I , class T >
std::optional< Property_map< I, T > >	property_map (const std::string &name) const
	returns an optional property map named `name` with key type `I` and value type `T`.

template<class I , class T >
void	remove_property_map (Property_map< I, T > &p)
	removes property map `p`.

template<class I >
void	remove_property_maps ()
	removes all property maps for index type `I` added by a call to `add_property_map<I>()`.

void	remove_all_property_maps ()
	removes all property maps for all index types added by a call to `add_property_map()`.

template<class I >
std::vector< std::string >	properties () const
	returns a vector with all strings that describe properties with the key type `I`.

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

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 (Surface_mesh &&sm)
	Move constructor.

Surface_mesh &	operator= (const Surface_mesh &rhs)
	assigns `rhs` to `*this`. Performs a deep copy of all properties.

Surface_mesh &	operator= (Surface_mesh &&sm)
	move assignment

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

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.

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

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

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

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_without_removing_property_maps ()
	removes all vertices, halfedge, edges and faces. Collects garbage but keeps all property maps.

void	clear ()
	removes all vertices, halfedge, edges and faces.

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)
	copies the simplices from `other`, and copies values of properties that already exist under the same name in `*this`.

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 referring to the right elements. When adding elements, by default elements that are marked as removed are recycled.
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.

bool	is_removed (Halfedge_index h) const
	returns whether halfedge `h` is marked removed.

bool	is_removed (Edge_index e) const
	returns whether edge `e` is marked removed.

bool	is_removed (Face_index f) const
	returns whether face `f` is marked removed.

bool	has_garbage () const
	checks if any vertices, halfedges, edges, or faces are marked as removed.

void	collect_garbage ()
	really removes vertices, halfedges, edges, and faces which are marked removed.

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

void	set_recycle_garbage (bool b)
	controls the recycling or not of simplices previously marked as removed upon addition of new elements.

bool	does_recycle_garbage () const
	Getter.

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=false) 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, bool verbose=false) const
	performs a validity check on a single vertex.

bool	is_valid (Halfedge_index h, bool verbose=false) const
	performs a validity check on a single halfedge.

bool	is_valid (Edge_index e, bool verbose=false) const
	performs a validity check on a single edge.

bool	is_valid (Face_index f, bool verbose=false) 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`.

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.

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.

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

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_property_map()

template<typename P >

template<class I , class T >

std::pair< Property_map< I, T >, bool > CGAL::Surface_mesh< P >::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.

Examples: Surface_mesh/draw_surface_mesh.cpp.

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

◆ clear()

template<typename P >

void CGAL::Surface_mesh::clear

removes all vertices, halfedge, edges and faces.

Collects garbage and removes all property maps added by a call to add_property_map() for all simplex types.

After calling this method, the object is the same as a newly constructed object. The additional property maps are also removed and must thus be re-added if needed.

◆ 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 referring to the right elements.

◆ halfedge() [1/2]

template<typename P >

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

◆ halfedge() [2/2]

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 ( Edge_index e ) const

returns whether edge e is marked removed.

See also: collect_garbage()

◆ is_removed() [2/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()

◆ is_removed() [3/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() [4/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()

◆ join()

template<typename P >

bool CGAL::Surface_mesh::join ( const Surface_mesh & other )

copies the simplices from other, and copies values of properties that already exist under the same name in *this.

In case *this has a property that does not exist in other the copied simplices get the default value of the property.

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

◆ remove_all_property_maps()

template<typename P >

void CGAL::Surface_mesh::remove_all_property_maps ( )

removes all property maps for all index types added by a call to add_property_map().

The memory allocated for those property maps is freed.

◆ remove_property_map()

template<typename P >

template<class I , class T >

void CGAL::Surface_mesh::remove_property_map ( Property_map< I, T > & p )

removes property map p.

The memory allocated for that property map is freed.

◆ remove_property_maps()

template<typename P >

template<class I >

void CGAL::Surface_mesh::remove_property_maps ( )

removes all property maps for index type I added by a call to add_property_map().

The memory allocated for those property maps is freed.

◆ set_recycle_garbage()

template<typename P >

void CGAL::Surface_mesh::set_recycle_garbage ( bool b )

controls the recycling or not of simplices previously marked as removed upon addition of new elements.

When set to true (default value), new elements are first picked in the garbage (if any) while if set to false only new elements are created.

Definition

Classes

Related Functions

Basic Types

Range Types

Property Handling

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

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_property_map()

◆ add_vertex()

◆ clear()

◆ collect_garbage()

◆ halfedge() [1/2]

◆ halfedge() [2/2]

◆ has_garbage()

◆ is_border()

◆ is_removed() [1/4]

◆ is_removed() [2/4]

◆ is_removed() [3/4]

◆ is_removed() [4/4]

◆ join()

◆ properties()

◆ remove_all_property_maps()

◆ remove_property_map()

◆ remove_property_maps()

◆ set_recycle_garbage()