Patate Lib  0.5
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
PatateCommon::SurfaceMesh Class Reference

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.
 
SurfaceMeshoperator= (const SurfaceMesh &rhs)
 assign rhs to *this. performs a deep copy of all properties.
 
SurfaceMeshassign (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< FaceConnectivitym_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< Vertexm_gcVertexMap
 
std::vector< Halfedgem_gcHalfedgeMap
 
std::vector< Facem_gcFaceMap
 
std::vector< Vertexm_addFaceVertices
 
std::vector< Halfedgem_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)