Inherited by Vitelotte::VGMesh< _Scalar, _Dims, _Coeffs >.

Detailed Description

A halfedge data structure for polygonal meshes.

Classes
class	BaseHandle

struct	Edge

class	EdgeContainer

class	EdgeIterator

class	EdgeProperty

struct	Face

class	FaceAroundVertexCirculator

struct	FaceConnectivity

class	FaceContainer

class	FaceIterator

class	FaceProperty

struct	Halfedge

class	HalfedgeAroundFaceCirculator

class	HalfedgeAroundVertexCirculator

struct	HalfedgeConnectivity

class	HalfedgeContainer

class	HalfedgeIterator

class	HalfedgeProperty

struct	Vertex

class	VertexAroundFaceCirculator

class	VertexAroundVertexCirculator

struct	VertexConnectivity

class	VertexContainer

class	VertexIterator

class	VertexProperty

Public Types
enum	{ GC_DONT_RELEASE_INDEX_MAPS = 0x01 }

Public Member Functions
Construct, destruct, assignment
	SurfaceMesh ()
	default constructor

	~SurfaceMesh ()

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

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

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

Add new elements by hand
Vertex	addVertex ()
	add a new vertex

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

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

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

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

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

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

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

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

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

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

unsigned int	nFaces () 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	freeMemory ()
	remove unused memory from vectors

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

void	garbageCollection (unsigned flags=0)
	remove deleted vertices/edges/faces

void	releaseGCIndexMaps ()

Vertex	gcMap (Vertex v)

Halfedge	gcMap (Halfedge h)

Face	gcMap (Face f)

bool	isDeleted (Vertex v) const

bool	isDeleted (Halfedge h) const

bool	isDeleted (Edge e) const

bool	isDeleted (Face f) const

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

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

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

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

Low-level connectivity
Halfedge	halfedge (Vertex v) const

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

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

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

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

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

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

void	setVertex (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	setFace (Halfedge h, Face f)
	sets the incident face to halfedge `h` to `f`

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

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

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

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

Halfedge	ccwRotatedHalfedge (Halfedge h) const

Halfedge	cwRotatedHalfedge (Halfedge h) const

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

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

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

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

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

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

Property handling
template<class T >
VertexProperty< T >	addVertexProperty (const std::string &name, const T t=T())

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

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

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

template<class T >
VertexProperty< T >	getVertexProperty (const std::string &name) const

template<class T >
HalfedgeProperty< T >	getHalfedgeProperty (const std::string &name) const

template<class T >
EdgeProperty< T >	getEdgeProperty (const std::string &name) const

template<class T >
FaceProperty< T >	getFaceProperty (const std::string &name) const

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

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

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

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

template<class T >
void	removeVertexProperty (VertexProperty< T > &p)
	remove the vertex property `p`

template<class T >
void	removeHalfedgeProperty (HalfedgeProperty< T > &p)
	remove the halfedge property `p`

template<class T >
void	removeEdgeProperty (EdgeProperty< T > &p)
	remove the edge property `p`

template<class T >
void	removeFaceProperty (FaceProperty< T > &p)
	remove the face property `p`

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

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

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

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

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

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

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

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

void	propertyStats () const
	prints the names of all properties

Iterators & Circulators
VertexIterator	verticesBegin () const
	returns start iterator for vertices

VertexIterator	verticesEnd () const
	returns end iterator for vertices

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

HalfedgeIterator	halfedgesBegin () const
	returns start iterator for halfedges

HalfedgeIterator	halfedgesEnd () const
	returns end iterator for halfedges

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

EdgeIterator	edgesBegin () const
	returns start iterator for edges

EdgeIterator	edgesEnd () const
	returns end iterator for edges

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

FaceIterator	facesBegin () const
	returns start iterator for faces

FaceIterator	facesEnd () const
	returns end iterator for faces

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

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

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

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

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

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

Higher-level Topological Operations
bool	isTriangleMesh () const

bool	isQuadMesh () const

void	triangulate ()

void	triangulate (Face f)

bool	isCollapseOk (Halfedge h)

void	collapse (Halfedge h)

void	split (Face f, Vertex v)

void	split (Edge e, Vertex v)

Halfedge	insertVertex (Edge e, Vertex v)

Halfedge	insertVertex (Halfedge h, Vertex v)

Halfedge	insertEdge (Halfedge h0, Halfedge h1)

bool	isFlipOk (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)

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

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

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

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

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

Protected Types
typedef std::pair< Halfedge, Halfedge >	NextCacheEntry

typedef std::vector < NextCacheEntry >	NextCache

Protected Member Functions
Vertex	newVertex ()
	allocate a new vertex, resize vertex properties accordingly.

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

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

void	adjustOutgoingHalfedge (Vertex v)

void	removeEdge (Halfedge h)
	Helper for halfedge collapse.

void	removeLoop (Halfedge h)
	Helper for halfedge collapse.

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

Protected Attributes
PropertyContainer	m_vprops

PropertyContainer	m_hprops

PropertyContainer	m_eprops

PropertyContainer	m_fprops

VertexProperty < VertexConnectivity >	m_vconn

HalfedgeProperty < HalfedgeConnectivity >	m_hconn

FaceProperty< FaceConnectivity >	m_fconn

VertexProperty< bool >	m_vdeleted

EdgeProperty< bool >	m_edeleted

FaceProperty< bool >	m_fdeleted

unsigned int	m_deletedVertices

unsigned int	m_deletedEdges

unsigned int	m_deleteFaces

bool	m_garbage

std::vector< Vertex >	m_gcVertexMap

std::vector< Halfedge >	m_gcHalfedgeMap

std::vector< Face >	m_gcFaceMap

std::vector< Vertex >	m_addFaceVertices

std::vector< Halfedge >	m_addFaceHalfedges

std::vector< bool >	m_addFaceIsNew

std::vector< bool >	m_addFaceNeedsAdjust

NextCache	m_addFaceNextCache

Member Function Documentation

template<class T >

EdgeProperty<T> PatateCommon::SurfaceMesh::addEdgeProperty	(	const std::string &	name,
		const 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

SurfaceMesh::Face PatateCommon::SurfaceMesh::addFace ( const std::vector< Vertex > & vertices )

inline

add a new face with vertex list vertices

See Also: addTriangle, addQuad

template<class T >

FaceProperty<T> PatateCommon::SurfaceMesh::addFaceProperty	(	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

template<class T >

HalfedgeProperty<T> PatateCommon::SurfaceMesh::addHalfedgeProperty	(	const std::string &	name,
		const 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

SurfaceMesh::Face PatateCommon::SurfaceMesh::addQuad	(	Vertex	v1,
		Vertex	v2,
		Vertex	v3,
		Vertex	v4
	)

inline

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

See Also: addTriangle, addFace

SurfaceMesh::Face PatateCommon::SurfaceMesh::addTriangle	(	Vertex	v1,
		Vertex	v2,
		Vertex	v3
	)

inline

add a new triangle connecting vertices v1, v2, v3

See Also: addFace, addQuad

template<class T >

VertexProperty<T> PatateCommon::SurfaceMesh::addVertexProperty	(	const std::string &	name,
		const 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 PatateCommon::SurfaceMesh::adjustOutgoingHalfedge ( Vertex v )

inlineprotected

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

Halfedge PatateCommon::SurfaceMesh::ccwRotatedHalfedge ( 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 PatateCommon::SurfaceMesh::collapse ( Halfedge h )

inline

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 isCollapseOk(Halfedge) to be sure the collapse is legal.; The removed items are only marked as deleted. You have to call garbageCollection() to finally remove them.

Halfedge PatateCommon::SurfaceMesh::cwRotatedHalfedge ( 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.

template<class T >

EdgeProperty<T> PatateCommon::SurfaceMesh::edgeProperty	(	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)

template<class T >

FaceProperty<T> PatateCommon::SurfaceMesh::faceProperty	(	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 PatateCommon::SurfaceMesh::flip ( Edge e )

inline

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: isFlipOk(Edge)

template<class T >

EdgeProperty<T> PatateCommon::SurfaceMesh::getEdgeProperty ( const std::string & name ) const

inline

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

const std::type_info& PatateCommon::SurfaceMesh::getEdgePropertyType ( const std::string & name )

inline

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

template<class T >

FaceProperty<T> PatateCommon::SurfaceMesh::getFaceProperty ( const std::string & name ) const

inline

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

const std::type_info& PatateCommon::SurfaceMesh::getFacePropertyType ( const std::string & name )

inline

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

template<class T >

HalfedgeProperty<T> PatateCommon::SurfaceMesh::getHalfedgeProperty ( const std::string & name ) const

inline

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

const std::type_info& PatateCommon::SurfaceMesh::getHalfedgePropertyType ( const std::string & name )

inline

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

template<class T >

VertexProperty<T> PatateCommon::SurfaceMesh::getVertexProperty ( const std::string & name ) const

inline

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

const std::type_info& PatateCommon::SurfaceMesh::getVertexPropertyType ( const std::string & name )

inline

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

Halfedge PatateCommon::SurfaceMesh::halfedge ( Vertex v ) const

inline

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

template<class T >

HalfedgeProperty<T> PatateCommon::SurfaceMesh::halfedgeProperty	(	const std::string &	name,
		const 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)

SurfaceMesh::Halfedge PatateCommon::SurfaceMesh::insertEdge	(	Halfedge	h0,
		Halfedge	h1
	)

inline

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 PatateCommon::SurfaceMesh::insertVertex	(	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: insertVertex(Halfedge, Vertex)

SurfaceMesh::Halfedge PatateCommon::SurfaceMesh::insertVertex	(	Halfedge	h,
		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: insertVertex(Edge, Vertex)

bool PatateCommon::SurfaceMesh::isBoundary ( Edge e ) const

inline

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

bool PatateCommon::SurfaceMesh::isCollapseOk ( Halfedge h )

inline

returns whether collapsing the halfedge h is topologically legal.

Attention: This function is only valid for triangle meshes.

bool PatateCommon::SurfaceMesh::isDeleted ( Vertex v ) const

inline

returns whether vertex v is deleted

See Also: garbageCollection()

bool PatateCommon::SurfaceMesh::isDeleted ( Halfedge h ) const

inline

returns whether halfedge h is deleted

See Also: garbageCollection()

bool PatateCommon::SurfaceMesh::isDeleted ( Edge e ) const

inline

returns whether edge e is deleted

See Also: garbageCollection()

bool PatateCommon::SurfaceMesh::isDeleted ( Face f ) const

inline

returns whether face f is deleted

See Also: garbageCollection()

bool PatateCommon::SurfaceMesh::isFlipOk ( Edge e ) const

inline

Check whether flipping edge e is topologically

Attention: This function is only valid for triangle meshes.

See Also: flip(Edge)

bool PatateCommon::SurfaceMesh::isQuadMesh ( ) const

inline

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

bool PatateCommon::SurfaceMesh::isTriangleMesh ( ) const

inline

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

See Also: trianglate(), triangulate(Face)

void PatateCommon::SurfaceMesh::split	(	Face	f,
		Vertex	v
	)

inline

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.

void PatateCommon::SurfaceMesh::split	(	Edge	e,
		Vertex	v
	)

inline

Split the edge e by connecting vertex v it to the two vertices of the adjacent triangles that are opposite to edge e.

Attention: This function is only valid for triangle meshes.

void PatateCommon::SurfaceMesh::triangulate ( )

inline

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

See Also: trianglate(Face)

void PatateCommon::SurfaceMesh::triangulate ( Face f )

inline

triangulate the face f

See Also: trianglate()

unsigned int PatateCommon::SurfaceMesh::valence ( Vertex v ) const

inline

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

template<class T >

VertexProperty<T> PatateCommon::SurfaceMesh::vertexProperty	(	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)

Detailed Description

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Member Function Documentation