Half-edge data structure implementing the BaseMesh interface. More...

#include <HalfEdgeMesh.hpp>

Inheritance diagram for lvr2::HalfEdgeMesh< BaseVecT >:

Public Types
using	Edge = HalfEdge

using	Face = HalfEdgeFace

using	Vertex = HalfEdgeVertex< BaseVecT >

Public Member Functions
FaceHandle	addFace (VertexHandle v1H, VertexHandle v2H, VertexHandle v3H) final
	Creates a face connecting the three given vertices. More...

VertexHandle	addVertex (BaseVecT pos) final
	Adds a vertex with the given position to the mesh. More...

EdgeCollapseResult	collapseEdge (EdgeHandle edgeH) final
	Merges the two vertices connected by the given edge. More...

bool	containsEdge (EdgeHandle eH) const
	Checks if the given edge is part of this mesh. More...

bool	containsFace (FaceHandle fH) const
	Checks if the given face is part of this mesh. More...

bool	containsVertex (VertexHandle vH) const
	Checks if the given vertex is part of this mesh. More...

bool	debugCheckMeshIntegrity () const

MeshHandleIteratorPtr< EdgeHandle >	edgesBegin () const final
	Returns an iterator to the first edge of this mesh. More...

MeshHandleIteratorPtr< EdgeHandle >	edgesEnd () const final
	Returns an iterator to the element following the last edge of this mesh. More...

MeshHandleIteratorPtr< FaceHandle >	facesBegin () const final
	Returns an iterator to the first face of this mesh. More...

MeshHandleIteratorPtr< FaceHandle >	facesEnd () const final
	Returns an iterator to the element following the last face of this mesh. More...

vector< VertexHandle >	findCommonNeigbours (VertexHandle vH1, VertexHandle vH2)

void	flipEdge (EdgeHandle edgeH) final
	Performs the edge flip operation. More...

array< EdgeHandle, 3 >	getEdgesOfFace (FaceHandle handle) const final
	Get the three edges surrounding the given face. More...

void	getEdgesOfVertex (VertexHandle handle, vector< EdgeHandle > &edgesOut) const final

array< OptionalFaceHandle, 2 >	getFacesOfEdge (EdgeHandle edgeH) const final
	Get the two faces of an edge. More...

void	getFacesOfVertex (VertexHandle handle, vector< FaceHandle > &facesOut) const final

void	getNeighboursOfFace (FaceHandle handle, vector< FaceHandle > &facesOut) const final

void	getNeighboursOfVertex (VertexHandle handle, vector< VertexHandle > &verticesOut) const final

OptionalEdgeHandle	getOppositeEdge (FaceHandle faceH, VertexHandle vertexH) const
	Get the optional edge handle of the edge lying on the vertex's opposite site. More...

OptionalFaceHandle	getOppositeFace (FaceHandle faceH, VertexHandle vertexH) const
	Get the optional face handle of the neighboring face lying on the vertex's opposite site. More...

OptionalVertexHandle	getOppositeVertex (FaceHandle faceH, EdgeHandle edgeH) const
	Get the optional vertex handle of the vertex lying on the edge's opposite site. More...

BaseVecT	getVertexPosition (VertexHandle handle) const final
	Get the position of the given vertex. More...

BaseVecT &	getVertexPosition (VertexHandle handle) final
	Get a ref to the position of the given vertex. More...

array< VertexHandle, 2 >	getVerticesOfEdge (EdgeHandle edgeH) const final
	Get the two vertices of an edge. More...

array< VertexHandle, 3 >	getVerticesOfFace (FaceHandle handle) const final
	Get the three vertices surrounding the given face. More...

	HalfEdgeMesh ()

	HalfEdgeMesh (MeshBufferPtr ptr)

bool	isBorderEdge (EdgeHandle handle) const
	Determines wheter the given edge is an border edge, i.e., if it is connected to two faces or not. More...

bool	isFlippable (EdgeHandle handle) const
	Determines whether or not the given edge can be flipped without destroying the mesh. More...

Index	nextEdgeIndex () const
	Returns the handle index which would be assigned to the next edge that is created. This method is mainly useful for manually iterating over all possible handles. As handles are strictly increasing, all edges currently in this mesh have a handle index smaller than what this method returns. More...

Index	nextFaceIndex () const
	Returns the handle index which would be assigned to the next face that is created. This method is mainly useful for manually iterating over all possible handles. As handles are strictly increasing, all faces currently in this mesh have a handle index smaller than what this method returns. More...

Index	nextVertexIndex () const
	Returns the handle index which would be assigned to the next vertex that is created. This method is mainly useful for manually iterating over all possible handles. As handles are strictly increasing, all vertices currently in this mesh have a handle index smaller than what this method returns. More...

size_t	numEdges () const final
	Returns the number of edges in the mesh. More...

size_t	numFaces () const final
	Returns the number of faces in the mesh. More...

size_t	numVertices () const final
	Returns the number of vertices in the mesh. More...

void	removeFace (FaceHandle handle) final
	Removes the given face and all (if not connected to any other face/edge/vertex) connected edges and vertices. More...

EdgeSplitResult	splitEdge (EdgeHandle edgeH)

void	splitVertex (EdgeHandle eH, VertexHandle vH, BaseVecT pos1, BaseVecT pos2)

VertexSplitResult	splitVertex (VertexHandle vertexToBeSplitH)

std::pair< BaseVecT, float >	triCircumCenter (FaceHandle faceH)

MeshHandleIteratorPtr< VertexHandle >	verticesBegin () const final
	Returns an iterator to the first vertex of this mesh. More...

MeshHandleIteratorPtr< VertexHandle >	verticesEnd () const final
	Returns an iterator to the element following the last vertex of this mesh. More...

Public Member Functions inherited from lvr2::BaseMesh< BaseVecT >
BaseVecT::CoordType	calcFaceArea (FaceHandle handle) const
	Calc and return the area of the requested face. More...

BaseVecT	calcFaceCentroid (FaceHandle handle) const
	Calc and return the centroid of the requested face. More...

virtual EdgeIteratorProxy< BaseVecT >	edges () const
	Method for usage in range-based for-loops. More...

virtual FaceIteratorProxy< BaseVecT >	faces () const
	Method for usage in range-based for-loops. More...

virtual OptionalEdgeHandle	getEdgeBetween (VertexHandle aH, VertexHandle bH) const
	If the two given vertices are connected by an edge, it is returned. None otherwise. More...

virtual std::vector< EdgeHandle >	getEdgesOfVertex (VertexHandle handle) const
	Get a list of edges around the given vertex. More...

virtual void	getEdgesOfVertex (VertexHandle handle, std::vector< EdgeHandle > &edgesOut) const =0
	Get a list of edges around the given vertex. More...

virtual OptionalFaceHandle	getFaceBetween (VertexHandle aH, VertexHandle bH, VertexHandle cH) const
	If all vertices are part of one face, this face is returned. None otherwise. More...

virtual std::vector< FaceHandle >	getFacesOfVertex (VertexHandle handle) const
	Get a list of faces the given vertex belongs to. More...

virtual void	getFacesOfVertex (VertexHandle handle, std::vector< FaceHandle > &facesOut) const =0
	Get a list of faces the given vertex belongs to. More...

virtual std::vector< FaceHandle >	getNeighboursOfFace (FaceHandle handle) const
	Get face handles of the neighbours of the requested face. More...

virtual void	getNeighboursOfFace (FaceHandle handle, std::vector< FaceHandle > &facesOut) const =0
	Get face handles of the neighbours of the requested face. More...

virtual std::vector< VertexHandle >	getNeighboursOfVertex (VertexHandle handle) const
	Get a list of vertices around the given vertex. More...

virtual void	getNeighboursOfVertex (VertexHandle handle, std::vector< VertexHandle > &verticesOut) const =0
	Get vertex handles of the neighbours of the requested vertex. More...

virtual OptionalVertexHandle	getVertexBetween (EdgeHandle aH, EdgeHandle bH) const
	If the given edges share a vertex, it is returned. None otherwise. More...

virtual std::array< BaseVecT, 3 >	getVertexPositionsOfFace (FaceHandle handle) const
	Get the points of the requested face. More...

virtual bool	isCollapsable (EdgeHandle handle) const
	Determines whether or not an edge collapse of the given edge is possible without creating invalid meshes. More...

virtual bool	isFaceInsertionValid (VertexHandle v1, VertexHandle v2, VertexHandle v3) const
	Check whether or not inserting a face between the given vertices would be valid. More...

virtual uint8_t	numAdjacentFaces (EdgeHandle handle) const
	Returns the number of adjacent faces to the given edge. More...

virtual VertexIteratorProxy< BaseVecT >	vertices () const
	Method for usage in range-based for-loops. More...

virtual	~BaseMesh ()

Private Member Functions
pair< HalfEdgeHandle, HalfEdgeHandle >	addEdgePair (VertexHandle v1H, VertexHandle v2H)
	Adds a new, incomplete edge-pair. More...

template<typename Visitor >
void	circulateAroundVertex (HalfEdgeHandle startEdgeH, Visitor visitor) const
	Circulates around the vertex `startEdgeH.target`, calling the `visitor` for each ingoing edge of the vertex. More...

template<typename Visitor >
void	circulateAroundVertex (VertexHandle vH, Visitor visitor) const
	Circulates around the vertex `vH`, calling the `visitor` for each ingoing edge of the vertex. More...

OptionalHalfEdgeHandle	edgeBetween (VertexHandle fromH, VertexHandle toH)
	Given two vertices, find the edge pointing from one to the other. More...

template<typename Pred >
OptionalHalfEdgeHandle	findEdgeAroundVertex (HalfEdgeHandle startEdgeH, Pred pred) const
	Iterates over all ingoing edges of the vertex `startEdge.target`, starting at the edge `startEdgeH`, returning the first edge that satisfies the given predicate. More...

template<typename Pred >
OptionalHalfEdgeHandle	findEdgeAroundVertex (VertexHandle vH, Pred pred) const
	Iterates over all ingoing edges of one vertex, returning the first edge that satisfies the given predicate. More...

HalfEdgeHandle	findOrCreateEdgeBetween (VertexHandle fromH, VertexHandle toH)
	Attempts to find an edge between the given vertices and, if none is found, creates a new edge with `addEdgePair()` More...

HalfEdgeHandle	findOrCreateEdgeBetween (VertexHandle fromH, VertexHandle toH, bool &added)
	Attempts to find an edge between the given vertices and, if none is found, creates a new edge with `addEdgePair()` and sets the add boolean to true. More...

Edge &	getE (HalfEdgeHandle handle)

const Edge &	getE (HalfEdgeHandle handle) const

Face &	getF (FaceHandle handle)

const Face &	getF (FaceHandle handle) const

array< HalfEdgeHandle, 3 >	getInnerEdges (FaceHandle handle) const
	Get inner edges in counter clockwise order. More...

Vertex &	getV (VertexHandle handle)

const Vertex &	getV (VertexHandle handle) const

EdgeHandle	halfToFullEdgeHandle (HalfEdgeHandle handle) const
	Converts a half edge handle to a full edge handle. More...

Private Attributes
StableVector< HalfEdgeHandle, Edge >	m_edges

StableVector< FaceHandle, Face >	m_faces

StableVector< VertexHandle, Vertex >	m_vertices

Friends
template<typename >
class	HemEdgeIterator

Detailed Description

template<typename BaseVecT>
class lvr2::HalfEdgeMesh< BaseVecT >

Half-edge data structure implementing the BaseMesh interface.

This implementation uses a half-edge structure. This encodes many connectivity details explicitly, enabling fast lookup. However, HEMs are primarily intended for non-triangle meshes (variable number of edges per face). Using it for triangle meshes might be overkill and results in a memory overhead.

Definition at line 70 of file HalfEdgeMesh.hpp.

Member Typedef Documentation

◆ Edge

template<typename BaseVecT >

using lvr2::HalfEdgeMesh< BaseVecT >::Edge = HalfEdge

Definition at line 73 of file HalfEdgeMesh.hpp.

◆ Face

template<typename BaseVecT >

using lvr2::HalfEdgeMesh< BaseVecT >::Face = HalfEdgeFace

Definition at line 74 of file HalfEdgeMesh.hpp.

◆ Vertex

template<typename BaseVecT >

using lvr2::HalfEdgeMesh< BaseVecT >::Vertex = HalfEdgeVertex<BaseVecT>

Definition at line 75 of file HalfEdgeMesh.hpp.

Constructor & Destructor Documentation

◆ HalfEdgeMesh() [1/2]

template<typename BaseVecT >

lvr2::HalfEdgeMesh< BaseVecT >::HalfEdgeMesh ( )

◆ HalfEdgeMesh() [2/2]

template<typename BaseVecT >

lvr2::HalfEdgeMesh< BaseVecT >::HalfEdgeMesh ( MeshBufferPtr ptr )

Member Function Documentation

◆ addEdgePair()

template<typename BaseVecT >

pair<HalfEdgeHandle, HalfEdgeHandle> lvr2::HalfEdgeMesh< BaseVecT >::addEdgePair	(	VertexHandle	v1H,
		VertexHandle	v2H
	)

private

Adds a new, incomplete edge-pair.

This method is private and unsafe, because it leaves some fields uninitialized. The invariants of this mesh are broken after calling this method and the caller has to fix those broken invariants.

In particular, no next handle is set or changed. The outgoing handle of the vertices is not changed (or set) either.

Returns: Both edge handles. The first edge points from v1H to v2H, the second one points from v2H to v1H.

◆ addFace()

template<typename BaseVecT >

FaceHandle lvr2::HalfEdgeMesh< BaseVecT >::addFace	(	VertexHandle	v1,
		VertexHandle	v2,
		VertexHandle	v3
	)

finalvirtual

Creates a face connecting the three given vertices.

Important: The face's vertices have to be given in front-face counter- clockwise order. This means that, when looking at the face's front, the vertices would appear in counter-clockwise order. Or in more mathy terms: the face's normal is equal to (v1 - v2) x (v1 - v3) in the right-handed coordinate system (where x is cross-product).

This method panics if an insertion is not possible. You can check whether or not an insertion is valid by using isFaceInsertionValid().

Returns: A handle to access the inserted face later.

vector<VertexHandle> lvr2::HalfEdgeMesh< BaseVecT >::findCommonNeigbours	(	VertexHandle	vH1,
		VertexHandle	vH2
	)

faceH	The corresponding face handle
vertexH	The corresponding vertex handle

faceH	The corresponding face handle
edgeH	The corresponding edge handle

void lvr2::HalfEdgeMesh< BaseVecT >::splitVertex	(	EdgeHandle	eH,
		VertexHandle	vH,
		BaseVecT	pos1,
		BaseVecT	pos2
	)

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

template<typename BaseVecT> class lvr2::HalfEdgeMesh< BaseVecT >

Member Typedef Documentation

◆ Edge

◆ Face

◆ Vertex

Constructor & Destructor Documentation

◆ HalfEdgeMesh() [1/2]

◆ HalfEdgeMesh() [2/2]

Member Function Documentation

◆ addEdgePair()

◆ addFace()

◆ addVertex()

◆ circulateAroundVertex() [1/2]

◆ circulateAroundVertex() [2/2]

◆ collapseEdge()

◆ containsEdge()

◆ containsFace()

◆ containsVertex()

◆ debugCheckMeshIntegrity()

◆ edgeBetween()

◆ edgesBegin()

◆ edgesEnd()

◆ facesBegin()

◆ facesEnd()

◆ findCommonNeigbours()

◆ findEdgeAroundVertex() [1/2]

◆ findEdgeAroundVertex() [2/2]

◆ findOrCreateEdgeBetween() [1/2]

◆ findOrCreateEdgeBetween() [2/2]

◆ flipEdge()

◆ getE() [1/2]

◆ getE() [2/2]

◆ getEdgesOfFace()

◆ getEdgesOfVertex()

◆ getF() [1/2]

◆ getF() [2/2]

◆ getFacesOfEdge()

◆ getFacesOfVertex()

◆ getInnerEdges()

◆ getNeighboursOfFace()

◆ getNeighboursOfVertex()

◆ getOppositeEdge()

◆ getOppositeFace()

◆ getOppositeVertex()

◆ getV() [1/2]

◆ getV() [2/2]

◆ getVertexPosition() [1/2]

◆ getVertexPosition() [2/2]

◆ getVerticesOfEdge()

◆ getVerticesOfFace()

◆ halfToFullEdgeHandle()

◆ isBorderEdge()

◆ isFlippable()

◆ nextEdgeIndex()

◆ nextFaceIndex()

◆ nextVertexIndex()

◆ numEdges()

◆ numFaces()

◆ numVertices()

◆ removeFace()

◆ splitEdge()

◆ splitVertex() [1/2]

◆ splitVertex() [2/2]

◆ triCircumCenter()

◆ verticesBegin()

◆ verticesEnd()

Friends And Related Function Documentation

◆ HemEdgeIterator

Member Data Documentation

◆ m_edges

◆ m_faces

◆ m_vertices

template<typename BaseVecT>
class lvr2::HalfEdgeMesh< BaseVecT >