Detailed Description

A halfedge data structure for polygonal meshes.

Collaboration diagram for gsSurfMesh:

Classes
class	Base_handle

struct	Edge

class	Edge_container

class	Edge_iterator

class	Edge_property

struct	Face

class	Face_around_vertex_circulator

struct	Face_connectivity

class	Face_container

class	Face_iterator

class	Face_property

struct	Halfedge

class	Halfedge_around_face_circulator

class	Halfedge_around_vertex_circulator

struct	Halfedge_connectivity

class	Halfedge_container

class	Halfedge_iterator

class	Halfedge_property

class	Mesh_property

struct	Vertex

class	Vertex_around_face_circulator

class	Vertex_around_vertex_circulator

struct	Vertex_connectivity

class	Vertex_container

class	Vertex_iterator

class	Vertex_property

Public Types
typedef real_t	Scalar
	Scalar type.

Public Member Functions
gsMultiPatch< real_t >	cc_acc3 (bool comp_topology=false) const
	Generate ACC3 biqubic Bezier patches.

Vertex_property< Point >	cc_limit_normals (std::string label="v:normal", bool normalize=true)
	Compute CC vertex limit normals.

Vertex_property< Point >	cc_limit_points (std::string label="v:limit")
	Compute CC vertex limit positions.

Vertex_property< Point >	cc_limit_tangent_vec (std::string label="v:tanvec", bool normalize=true)
	Compute CC vertex limit tangent.

void	cc_subdivide ()
	Catmull-Clark subdivision.

gsMultiPatch< real_t >	linear_patches () const
	Generate linear tensor-product patches (possibly merging faces)

Construct, destruct, assignment
	gsSurfMesh ()
	default constructor

	gsSurfMesh (const gsMatrix< Scalar > &pts)
	Constructor from a set of points.

virtual	~gsSurfMesh ()

	gsSurfMesh (const gsSurfMesh &rhs)
	copy constructor: copies `rhs` to `*this`. performs a deep copy of all properties.

gsSurfMesh &	operator= (const gsSurfMesh &rhs)
	assign `rhs` to `*this`. performs a deep copy of all properties.

gsSurfMesh &	assign (const gsSurfMesh &rhs)
	assign `rhs` to `*this`. does not copy custom properties.

File IO
bool	read (const std::string &filename)

bool	write (const std::string &filename) const

Add new elements by hand
Vertex	add_vertex (const Point &p)
	add a new vertex with position `p`

Face	add_face (const std::vector< Vertex > &vertices)

Face	add_triangle (Vertex v1, Vertex v2, Vertex v3)

Face	add_quad (Vertex v1, Vertex v2, Vertex v3, Vertex v4)

Memory Management
unsigned int	vertices_size () const
	returns number of (deleted and valid) vertices in the mesh

unsigned int	halfedges_size () const
	returns number of (deleted and valid)halfedge in the mesh

unsigned int	edges_size () const
	returns number of (deleted and valid)edges in the mesh

unsigned int	faces_size () const
	returns number of (deleted and valid)faces in the mesh

unsigned int	n_vertices () const
	returns number of vertices in the mesh

unsigned int	n_halfedges () const
	returns number of halfedge in the mesh

unsigned int	n_edges () const
	returns number of edges in the mesh

unsigned int	n_faces () const
	returns number of faces in the mesh

unsigned int	empty () const
	returns true iff the mesh is empty, i.e., has no vertices

void	clear ()
	clear mesh: remove all vertices, edges, faces

void	free_memory ()
	remove unused memory from vectors

void	reserve (unsigned int nvertices, unsigned int nedges, unsigned int nfaces)
	reserve memory (mainly used in file readers)

void	garbage_collection ()
	remove deleted vertices/edges/faces

bool	is_deleted (Vertex v) const

bool	is_deleted (Halfedge h) const

bool	is_deleted (Edge e) const

bool	is_deleted (Face f) const

bool	is_valid (Vertex v) const
	return whether vertex `v` is valid, i.e. the index it stores is within the array bounds.

bool	is_valid (Halfedge h) const
	return whether halfedge `h` is valid, i.e. the index it stores is within the array bounds.

bool	is_valid (Edge e) const
	return whether edge `e` is valid, i.e. the index it stores is within the array bounds.

bool	is_valid (Face f) const
	return whether face `f` is valid, i.e. the index it stores is within the array bounds.

Low-level connectivity
Halfedge	halfedge (Vertex v) const

void	set_halfedge (Vertex v, Halfedge h)
	set the outgoing halfedge of vertex `v` to `h`

bool	is_boundary (Vertex v) const
	returns whether `v` is a boundary vertex

bool	is_isolated (Vertex v) const
	returns whether `v` is isolated, i.e., not incident to any face

bool	is_manifold (Vertex v) const
	returns whether `v` is a manifold vertex (not incident to several patches)

Vertex	to_vertex (Halfedge h) const
	returns the vertex the halfedge `h` points to

Vertex	from_vertex (Halfedge h) const
	returns the vertex the halfedge `h` emanates from

void	set_vertex (Halfedge h, Vertex v)
	sets the vertex the halfedge `h` points to to `v`

Face	face (Halfedge h) const
	returns the face incident to halfedge `h`

void	set_face (Halfedge h, Face f)
	sets the incident face to halfedge `h` to `f`

Halfedge	next_halfedge (Halfedge h) const
	returns the next halfedge within the incident face

void	set_next_halfedge (Halfedge h, Halfedge nh)
	sets the next halfedge of `h` within the face to `nh`

Halfedge	prev_halfedge (Halfedge h) const
	returns the previous halfedge within the incident face

Halfedge	opposite_halfedge (Halfedge h) const
	returns the opposite halfedge of `h`

Halfedge	ccw_rotated_halfedge (Halfedge h) const

Halfedge	cw_rotated_halfedge (Halfedge h) const

Edge	edge (Halfedge h) const
	return the edge that contains halfedge `h` as one of its two halfedges.

bool	is_boundary (Halfedge h) const
	returns whether h is a boundary halfege, i.e., if its face does not exist.

bool	touches_boundary (Halfedge h) const
	returns whether h touches the boundary, i.e., its opposite is a boundary halfedge.

Halfedge	halfedge (Edge e, unsigned int i) const
	returns the `i'th` halfedge of edge `e`. `i` has to be 0 or 1.

Vertex	vertex (Edge e, unsigned int i) const
	returns the `i'th` vertex of edge `e`. `i` has to be 0 or 1.

Face	face (Edge e, unsigned int i) const
	returns the face incident to the `i'th` halfedge of edge `e`. `i` has to be 0 or 1.

bool	is_boundary (Edge e) const

Halfedge	halfedge (Face f) const
	returns a halfedge of face `f`

void	set_halfedge (Face f, Halfedge h)
	sets the halfedge of face `f` to `h`

bool	is_boundary (Face f) const
	returns whether `f` is a boundary face, i.e., it one of its edges is a boundary edge.

gsProperty handling
template<class T >
Vertex_property< T >	add_vertex_property (const std::string &name, T t=T())

template<class T >
Halfedge_property< T >	add_halfedge_property (const std::string &name, T t=T())

template<class T >
Edge_property< T >	add_edge_property (const std::string &name, T t=T())

template<class T >
Face_property< T >	add_face_property (const std::string &name, const T t=T())

template<class T >
Mesh_property< T >	add_mesh_property (const std::string &name, const T t=T())

template<class T >
Vertex_property< T >	get_vertex_property (const std::string &name) const

template<class T >
Halfedge_property< T >	get_halfedge_property (const std::string &name) const

template<class T >
Edge_property< T >	get_edge_property (const std::string &name) const

template<class T >
Face_property< T >	get_face_property (const std::string &name) const

template<class T >
Mesh_property< T >	get_mesh_property (const std::string &name) const

template<class T >
Vertex_property< T >	vertex_property (const std::string &name, const T t=T())

template<class T >
Halfedge_property< T >	halfedge_property (const std::string &name, T t=T())

template<class T >
Edge_property< T >	edge_property (const std::string &name, const T t=T())

template<class T >
Face_property< T >	face_property (const std::string &name, const T t=T())

template<class T >
Mesh_property< T >	mesh_property (const std::string &name, const T t=T())

template<class T >
void	rename_vertex_property (Vertex_property< T > &p, std::string newname)
	rename the vertex property `p`

void	swap_vertex_property (const std::string &name1, const std::string &name2)
	swaps (the values of) two vertex properties of the same type

template<class T >
void	remove_vertex_property (Vertex_property< T > &p)
	remove the vertex property `p`

template<class T >
void	remove_halfedge_property (Halfedge_property< T > &p)
	remove the halfedge property `p`

template<class T >
void	remove_edge_property (Edge_property< T > &p)
	remove the edge property `p`

template<class T >
void	remove_face_property (Face_property< T > &p)
	remove the face property `p`

template<class T >
void	remove_mesh_property (Mesh_property< T > &p)
	remove the mesh property `p`

const std::type_info &	get_vertex_property_type (const std::string &name)

const std::type_info &	get_halfedge_property_type (const std::string &name)

const std::type_info &	get_edge_property_type (const std::string &name)

const std::type_info &	get_face_property_type (const std::string &name)

const std::type_info &	get_mesh_property_type (const std::string &name)

std::vector< std::string >	vertex_properties () const
	returns the names of all vertex properties

std::vector< std::string >	halfedge_properties () const
	returns the names of all halfedge properties

std::vector< std::string >	edge_properties () const
	returns the names of all edge properties

std::vector< std::string >	face_properties () const
	returns the names of all face properties

std::vector< std::string >	mesh_properties () const
	returns the names of all mesh properties

void	property_stats () const
	prints the names of all properties

Iterators & Circulators
Vertex_iterator	vertices_begin () const
	returns start iterator for vertices

Vertex_iterator	vertices_end () const
	returns end iterator for vertices

Vertex_container	vertices () const
	returns vertex container for C++11 range-based for-loops

Halfedge_iterator	halfedges_begin () const
	returns start iterator for halfedges

Halfedge_iterator	halfedges_end () const
	returns end iterator for halfedges

Halfedge_container	halfedges () const
	returns halfedge container for C++11 range-based for-loops

Edge_iterator	edges_begin () const
	returns start iterator for edges

Edge_iterator	edges_end () const
	returns end iterator for edges

Edge_container	edges () const
	returns edge container for C++11 range-based for-loops

Face_iterator	faces_begin () const
	returns start iterator for faces

Face_iterator	faces_end () const
	returns end iterator for faces

Face_container	faces () const
	returns face container for C++11 range-based for-loops

Vertex_around_vertex_circulator	vertices (Vertex v) const
	returns circulator for vertices around vertex `v`

Halfedge_around_vertex_circulator	halfedges (Vertex v) const
	returns circulator for outgoing halfedges around vertex `v`

Face_around_vertex_circulator	faces (Vertex v) const
	returns circulator for faces around vertex `v`

Vertex_around_face_circulator	vertices (Face f) const
	returns circulator for vertices of face `f`

Halfedge_around_face_circulator	halfedges (Face f) const
	returns circulator for halfedges of face `f`

Higher-level Topological Operations
bool	is_triangle_mesh () const

bool	is_quad_mesh () const

void	triangulate ()

void	triangulate (Face f)

bool	is_collapse_ok (Halfedge h)

void	collapse (Halfedge h)

Vertex	split (Face f, const Point &p)

void	split (Face f, Vertex v)

void	quad_split (Face f, Vertex v, Halfedge s)

void	quad_split ()

Halfedge	split (Edge e, const Point &p)

Halfedge	split (Edge e, Vertex v)

Halfedge	insert_vertex (Edge e, const Point &p)

Halfedge	insert_vertex (Edge e, Vertex v)

Halfedge	insert_vertex (Halfedge h, Vertex v)

Halfedge	insert_edge (Halfedge h0, Halfedge h1)

bool	is_flip_ok (Edge e) const

void	flip (Edge e)

unsigned int	valence (Vertex v) const

unsigned int	valence (Face f) const
	returns the valence of face `f` (its number of vertices)

unsigned int	face_valence_sum () const
	returns the sum of all valences of faces in the mesh

Halfedge	find_halfedge (Vertex start, Vertex end) const
	find the halfedge from start to end

Edge	find_edge (Vertex a, Vertex b) const
	find the edge (a,b)

void	delete_vertex (Vertex v)
	deletes the vertex `v` from the mesh

void	delete_edge (Edge e)
	deletes the edge `e` from the mesh

void	delete_face (Face f)
	deletes the face `f` from the mesh

Geometry-related Functions
const Point &	position (Vertex v) const
	position of a vertex (read only)

Point &	position (Vertex v)
	position of a vertex

std::vector< Point > &	points ()
	vector of vertex positions

void	update_face_normals ()
	compute face normals by calling compute_face_normal(Face) for each face.

Normal	compute_face_normal (Face f) const
	compute normal vector of face `f`.

void	update_vertex_normals ()
	compute vertex normals by calling compute_vertex_normal(Vertex) for each vertex.

Normal	compute_vertex_normal (Vertex v) const
	compute normal vector of vertex `v`.

Scalar	edge_length (Edge e) const
	compute the length of edge `e`.

Private Types
typedef gsEigen::Vector < Scalar, 3 >	Vec3
	3D vector type

Private Member Functions
void	adjust_outgoing_halfedge (Vertex v)

bool	garbage () const
	are there deleted vertices, edges or faces?

Halfedge	new_edge (Vertex start, Vertex end)
	allocate a new edge, resize edge and halfedge properties accordingly.

Face	new_face ()
	allocate a new face, resize face properties accordingly.

Vertex	new_vertex ()
	allocate a new vertex, resize vertex properties accordingly.

void	remove_edge (Halfedge h)
	Helper for halfedge collapse.

void	remove_loop (Halfedge h)
	Helper for halfedge collapse.

Member Function Documentation

Edge_property<T> add_edge_property	(	const std::string &	name,
		T	t = `T()`
	)

inline

add a edge property of type T with name name and default value t. fails if a property named name exists already, since the name has to be unique. in this case it returns an invalid property

gsSurfMesh::Face add_face ( const std::vector< Vertex > & vertices )

add a new face with vertex list vertices

See Also: add_triangle, add_quad

Face_property<T> add_face_property	(	const std::string &	name,
		const T	t = `T()`
	)

inline

add a face property of type T with name name and default value t. fails if a property named name exists already, since the name has to be unique. in this case it returns an invalid property

Halfedge_property<T> add_halfedge_property	(	const std::string &	name,
		T	t = `T()`
	)

inline

add a halfedge property of type T with name name and default value t. fails if a property named name exists already, since the name has to be unique. in this case it returns an invalid property

Mesh_property<T> add_mesh_property	(	const std::string &	name,
		const T	t = `T()`
	)

inline

add a mesh property of type T with name name and default value t. fails if a property named name exists already, since the name has to be unique. in this case it returns an invalid property

gsSurfMesh::Face add_quad	(	Vertex	v1,
		Vertex	v2,
		Vertex	v3,
		Vertex	v4
	)

add a new quad connecting vertices v1, v2, v3, v4

See Also: add_triangle, add_face

gsSurfMesh::Face add_triangle	(	Vertex	v1,
		Vertex	v2,
		Vertex	v3
	)

add a new triangle connecting vertices v1, v2, v3

See Also: add_face, add_quad

Vertex_property<T> add_vertex_property	(	const std::string &	name,
		T	t = `T()`
	)

inline

add a vertex property of type T with name name and default value t. fails if a property named name exists already, since the name has to be unique. in this case it returns an invalid property

void adjust_outgoing_halfedge ( Vertex v )

private

make sure that the outgoing halfedge of vertex v is a boundary halfedge if v is a boundary vertex.

Halfedge ccw_rotated_halfedge ( Halfedge h ) const

inline

returns the halfedge that is rotated counter-clockwise around the start vertex of h. it is the opposite halfedge of the previous halfedge of h.

void collapse ( Halfedge h )

Collapse the halfedge h by moving its start vertex into its target vertex. For non-boundary halfedges this function removes one vertex, three edges, and two faces. For boundary halfedges it removes one vertex, two edges and one face.

Attention: This function is only valid for triangle meshes.; Halfedge collapses might lead to invalid faces. Call is_collapse_ok(Halfedge) to be sure the collapse is legal.; The removed items are only marked as deleted. You have to call garbage_collection() to finally remove them.

Halfedge cw_rotated_halfedge ( Halfedge h ) const

inline

returns the halfedge that is rotated clockwise around the start vertex of h. it is the next halfedge of the opposite halfedge of h.

Edge_property<T> edge_property	(	const std::string &	name,
		const T	t = `T()`
	)

inline

if an edge property of type T with name name exists, it is returned. otherwise this property is added (with default value t)

Face_property<T> face_property	(	const std::string &	name,
		const T	t = `T()`
	)

inline

if a face property of type T with name name exists, it is returned. otherwise this property is added (with default value t)

void flip ( Edge e )

Flip edge e: Remove edge e and add an edge between the two vertices opposite to edge e of the two incident triangles.

Attention: This function is only valid for triangle meshes.

See Also: is_flip_ok(Edge)

Edge_property<T> get_edge_property ( const std::string & name ) const

inline

get the edge property named name of type T. returns an invalid Vertex_property if the property does not exist or if the type does not match.

const std::type_info& get_edge_property_type ( const std::string & name )

inline

get the type_info T of edge property named . returns an typeid(void) if the property does not exist or if the type does not match.

Face_property<T> get_face_property ( const std::string & name ) const

inline

get the face property named name of type T. returns an invalid Vertex_property if the property does not exist or if the type does not match.

const std::type_info& get_face_property_type ( const std::string & name )

inline

get the type_info T of face property named . returns an typeid(void) if the property does not exist or if the type does not match.

Halfedge_property<T> get_halfedge_property ( const std::string & name ) const

inline

get the halfedge property named name of type T. returns an invalid Vertex_property if the property does not exist or if the type does not match.

const std::type_info& get_halfedge_property_type ( const std::string & name )

inline

get the type_info T of halfedge property named . returns an typeid(void) if the property does not exist or if the type does not match.

Mesh_property<T> get_mesh_property ( const std::string & name ) const

inline

get the mesh property named name of type T. returns an invalid Mesh_property if the property does not exist or if the type does not match.

const std::type_info& get_mesh_property_type ( const std::string & name )

inline

get the type_info T of face property named . returns an typeid(void) if the property does not exist or if the type does not match.

Vertex_property<T> get_vertex_property ( const std::string & name ) const

inline

get the vertex property named name of type T. returns an invalid Vertex_property if the property does not exist or if the type does not match.

const std::type_info& get_vertex_property_type ( const std::string & name )

inline

get the type_info T of vertex property named . returns an typeid(void) if the property does not exist or if the type does not match.

Halfedge halfedge ( Vertex v ) const

inline

returns an outgoing halfedge of vertex v. if v is a boundary vertex this will be a boundary halfedge.

Halfedge_property<T> halfedge_property	(	const std::string &	name,
		T	t = `T()`
	)

inline

if a halfedge property of type T with name name exists, it is returned. otherwise this property is added (with default value t)

gsSurfMesh::Halfedge insert_edge	(	Halfedge	h0,
		Halfedge	h1
	)

insert edge between the to-vertices v0 of h0 and v1 of h1. returns the new halfedge from v0 to v1.

Attention: h0 and h1 have to belong to the same face

Halfedge insert_vertex	(	Edge	e,
		const Point &	p
	)

inline

Subdivide the edge e = (v0,v1) by splitting it into the two edge (v0,p) and (p,v1). Note that this function does not introduce any other edge or faces. It simply splits the edge. Returns halfedge that points to p.

See Also: insert_vertex(Edge, Vertex); insert_vertex(Halfedge, Vertex)

Halfedge insert_vertex	(	Edge	e,
		Vertex	v
	)

inline

Subdivide the edge e = (v0,v1) by splitting it into the two edge (v0,v) and (v,v1). Note that this function does not introduce any other edge or faces. It simply splits the edge. Returns halfedge that points to p.

See Also: insert_vertex(Edge, Point); insert_vertex(Halfedge, Vertex)

gsSurfMesh::Halfedge insert_vertex	(	Halfedge	h,
		Vertex	v
	)

Subdivide the edge e = (v0,v1) by splitting it into the two edge (v0,v) and (v,v1). Note that this function does not introduce any other edge or faces. It simply splits the edge. Returns halfedge that points to p.

See Also: insert_vertex(Edge, Point); insert_vertex(Edge, Vertex)

bool is_boundary ( Edge e ) const

inline

returns whether e is a boundary edge, i.e., if one of its halfedges is a boundary halfedge.

bool is_collapse_ok ( Halfedge h )

returns whether collapsing the halfedge h is topologically legal.

Attention: This function is only valid for triangle meshes.

bool is_deleted ( Vertex v ) const

inline

returns whether vertex v is deleted

See Also: garbage_collection()

bool is_deleted ( Halfedge h ) const

inline

returns whether halfedge h is deleted

See Also: garbage_collection()

bool is_deleted ( Edge e ) const

inline

returns whether edge e is deleted

See Also: garbage_collection()

bool is_deleted ( Face f ) const

inline

returns whether face f is deleted

See Also: garbage_collection()

bool is_flip_ok ( Edge e ) const

Check whether flipping edge e is topologically

Attention: This function is only valid for triangle meshes.

See Also: flip(Edge)

bool is_quad_mesh ( ) const

returns whether the mesh a quad mesh. this function simply tests each face, and therefore is not very efficient.

bool is_triangle_mesh ( ) const

returns whether the mesh a triangle mesh. this function simply tests each face, and therefore is not very efficient.

See Also: trianglate(), triangulate(Face)

Mesh_property<T> mesh_property	(	const std::string &	name,
		const T	t = `T()`
	)

inline

if a mesh property of type \c T with name \c name exists, it is returned.

otherwise this property is added (with default value t)

void quad_split	(	Face	f,
		Vertex	v,
		Halfedge	s
	)

Quad-split face connecting vertex v, starting from corner s of the face f is assumed to have 8 vertices, and contains halfedge s

bool read ( const std::string & filename )

read mesh from file filename. file extension determines file type.

See Also: write(const std::string& filename)

Vertex split	(	Face	f,
		const Point &	p
	)

inline

Split the face f by first adding point p to the mesh and then inserting edges between p and the vertices of f. For a triangle this is a standard one-to-three split.

See Also: split(Face, Vertex)

void split	(	Face	f,
		Vertex	v
	)

Split the face f by inserting edges between p and the vertices of f. For a triangle this is a standard one-to-three split.

See Also: split(Face, const Point&)

Halfedge split	(	Edge	e,
		const Point &	p
	)

inline

Split the edge e by first adding point p to the mesh and then connecting it to the two vertices of the adjacent triangles that are opposite to edge e. Returns the halfedge pointing to p that is created by splitting the existing edge e.

Attention: This function is only valid for triangle meshes.

See Also: split(Edge, Vertex)

gsSurfMesh::Halfedge split	(	Edge	e,
		Vertex	v
	)

Split the edge e by connecting vertex v it to the two vertices of the adjacent triangles that are opposite to edge e. Returns the halfedge pointing to p that is created by splitting the existing edge e.

Attention: This function is only valid for triangle meshes.

See Also: split(Edge, Point)

void triangulate ( )

triangulate the entire mesh, by calling triangulate(Face) for each face.

See Also: trianglate(Face)

void triangulate ( Face f )

triangulate the face f

See Also: trianglate()

unsigned int valence ( Vertex v ) const

returns the valence (number of incident edges or neighboring vertices) of vertex v.

Vertex_property<T> vertex_property	(	const std::string &	name,
		const T	t = `T()`
	)

inline

if a vertex property of type T with name name exists, it is returned. otherwise this property is added (with default value t)

bool write ( const std::string & filename ) const

write mesh to file filename. file extensions determines file type.

See Also: read(const std::string& filename)

Detailed Description

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Member Function Documentation