Half-edge mesh class. More...

Classes
struct	Edge
	Edge type More...

class	EdgesIterator
	Iterator that lazily flattens all face edges across all faces. More...

struct	ExtractedComponent
	One element of `extract_connected_components()`'s output. More...

struct	Face
	Face type More...

class	FaceIterator
	Iterator for the edges of a face. More...

struct	Vertex
	Vertex type More...

class	WheelIterator
	Iterator for the edges of a vertex's wheel. More...

Public Types
using	type = T

using	Pointer = std::shared_ptr< HalfEdgeMesh >

using	VertPtr = std::shared_ptr< Vertex >
	Vertex pointer type.

using	EdgePtr = std::shared_ptr< Edge >
	Edge pointer type.

using	FacePtr = std::shared_ptr< Face >
	Edge pointer type.

Public Member Functions
	HalfEdgeMesh ()=default
	Default constructor.

	~HalfEdgeMesh ()
	Destructor deallocating all element pointers.

auto	clone () const -> Pointer
	Clone this mesh.

template<typename... Args>
auto	insert_vertex (Args... args) -> std::size_t
	Insert a new vertex.

template<class VectorOfVectors >
auto	insert_vertices (const VectorOfVectors &v) -> std::vector< std::size_t >
	Insert new vertices from a list of Vertex-like objects.

template<typename ValType >
auto	insert_vertices (std::initializer_list< std::initializer_list< ValType > > v) -> std::vector< std::size_t >
	Insert new vertices from a brace-enclosed initializer list.

template<class Vector >
auto	insert_face (Vector &&vector) -> std::size_t
	Insert a face from an ordered list of Vertex indices.

template<typename... Args>
auto	insert_face (Args... args) -> std::size_t
	Insert a new face from an ordered list of Vertex indices.

template<class VectorOfVectors >
auto	insert_faces (const VectorOfVectors &v) -> std::vector< std::size_t >
	Insert new faces from a list of lists of Vertex indices.

template<typename IdxType >
auto	insert_faces (std::initializer_list< std::initializer_list< IdxType > > v)
	Insert new faces from a list of lists of Vertex indices.

void	update_boundary ()
	Update the mesh boundary connections.

auto	vertices () const -> const std::vector< VertPtr > &
	Get the list of vertices in insertion order.

auto	vertex (std::size_t idx) const -> VertPtr
	Get a vertex by index.

auto	edges () const
	Get a lazy range over all face edges in insertion order.

auto	edge (std::size_t start, std::size_t end) -> EdgePtr
	Find an existing edge with the provided end points.

auto	boundary_edge () const -> EdgePtr
	Get a boundary edge.

auto	boundaries () const -> std::vector< std::vector< EdgePtr > >
	Build a list of all boundary edges.

auto	faces () const -> const std::vector< FacePtr > &
	Get the list of faces in insertion order.

auto	face (std::size_t idx) const -> FacePtr
	Get a face by index.

auto	num_connected_components () const -> std::size_t
	Get the number of connected components.

auto	connected_components () const -> std::vector< std::vector< FacePtr > >
	Get a list of connected components.

auto	extract_connected_components () -> std::vector< ExtractedComponent >
	Extract each connected component of this mesh into its own independent mesh.

auto	vertices_interior () const
	Get the list of interior vertices in insertion order.

auto	vertices_boundary () const
	Get a lazy range over boundary vertices in insertion order.

auto	num_vertices () const -> std::size_t
	Get the number of vertices.

auto	num_vertices_interior () const -> std::size_t
	Get the number of interior vertices.

auto	num_edges () const -> std::size_t
	Get the number of edges.

auto	num_faces () const -> std::size_t
	Get the number of faces.

void	split_edge (const EdgePtr &edge)
	Split an edge in order to introduce a new boundary.

void	split_path (const std::vector< EdgePtr > &path)
	Split a list of edges (path) to form a new boundary.

void	split_path (const std::vector< std::size_t > &path)
	Split a list of edges (path) to form a new boundary.

auto	outgoing_edges (const std::size_t idx) -> std::vector< EdgePtr >
	Get a list of outgoing edges from a specific vertex (by index)

auto	incoming_edges (const std::size_t idx) -> std::vector< EdgePtr >
	Get a list of incoming edges to a specific vertex (by index)

Static Public Member Functions
template<typename... Args>
static Pointer	New (Args... args)
	Construct a new HalfEdgeMesh pointer.

Private Member Functions
void	rekey_edge_to_vertex_ (const EdgePtr &e, const VertPtr &newVert)

template<class Vector >
auto	insert_face_ (const Vector &vector, FacePtr face=nullptr) -> std::size_t

template<typename RemapFn >
auto	clone_face_ (const FacePtr &face, RemapFn remap)

auto	clone_face_ (const FacePtr &face)

Private Attributes
std::vector< VertPtr >	verts_

std::vector< FacePtr >	faces_

std::multimap< std::size_t, EdgePtr >	edges_

std::size_t	numFaceEdges_ {0}

Detailed Description

template<typename T, std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>
class OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >

Half-edge mesh class.

A half-edge mesh represents each edge as two oppositely oriented half-edges. There is one half-edge for each face containing the original edge. For example, if two faces share the edge AB, this will result in two half-edges, AB and BA. If an edge BC lies on the mesh border (i.e. it is only included in a single face), there will one be a single half-edge created. This data structure makes it possible to easily traverse the edges and faces adjacent to a vertex (the "wheel"), as well as to traverse the edges of each face.

For more information, see Chapter 12.1 in "Fundamentals of Computer Graphics, Fourth edition", Marschner and Shirley (2015) [2].

Template Parameters

T	Floating-point type for coordinates
Dim	Dimensionality of vertex coordinates
VertexTraits	Additional traits for vertices
EdgeTraits	Additional traits for edges
FaceTraits	Additional traits for face

Member Typedef Documentation

◆ Pointer

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

using OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::Pointer = std::shared_ptr<HalfEdgeMesh>

Pointer type

◆ type

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

using OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::type = T

Fundamental element type (e.g. float, double)

Member Function Documentation

◆ boundaries()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::boundaries ( ) const -> std::vector<std::vector<EdgePtr>>

inline

Build a list of all boundary edges.

Returns a list of lists of edges which lie on one of this mesh's boundaries. One edge list is returned for each unique boundary. Meshes with a single connected component may still have multiple boundaries (i.e. if the mesh has holes).

◆ boundary_edge()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::boundary_edge ( ) const -> EdgePtr

inline

Get a boundary edge.

Returns the first boundary edge in the list of edges

◆ clone()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::clone ( ) const -> Pointer

inline

Clone this mesh.

Returns a new mesh with the same structure as this mesh but not sharing vertex, face, or edge elements.

◆ clone_face_() [1/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::clone_face_ ( const FacePtr & face )

inlineprivate

Identity-remap overload (source and target share vertex indexing).

◆ clone_face_() [2/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

template<typename RemapFn >

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::clone_face_	(	const FacePtr &	face,
		RemapFn	remap
	)

inlineprivate

Extra steps which need to be run before insert_face_ when cloning a face from an existing mesh. Preserves FaceTraits (via Face::New(*face)) and EdgeTraits (via Edge::New(*e)) by exploiting the trait-only copy constructors.

Parameters

face	Existing face from the mesh being cloned (may belong to a different mesh than `this`).
remap	Callable mapping source-mesh vertex idx -> this-mesh vertex idx. The default identity remap is used by `clone()` where the two meshes share vertex indexing; `extract_connected_components` passes a real remap when sub-meshes have re-densified indices.

◆ extract_connected_components()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::extract_connected_components ( ) -> std::vector<ExtractedComponent>

inline

Extract each connected component of this mesh into its own independent mesh.

Returns one ExtractedComponent per connected component. The extracted meshes are deep copies that preserve VertexTraits, EdgeTraits, and FaceTraits via the relevant copy constructors. Vertex and face indices in the extracted meshes are re-densified to 0..N-1; the vertex_map and face_map let callers scatter/gather per-vertex and per-face data between the sub-mesh and the source.

A single-component mesh produces a vector of length 1 whose extracted mesh is equivalent to clone() and whose maps are both the identity.

◆ insert_face() [1/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

template<typename... Args>

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::insert_face ( Args... args ) -> std::size_t

inline

Insert a new face from an ordered list of Vertex indices.

Accepts vertex indices as individual variadic arguments.

Note: This function does not update the mesh boundary connections. Call update_boundary() after all faces have been inserted, or use insert_faces() to insert faces and update the boundary in one step.

Exceptions

std::out_of_range	If one of the vertex indices is out of bounds.
MeshException	If one of provided edges is already paired. This indicates that the mesh is not 2-manifold.

◆ insert_face() [2/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

template<class Vector >

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::insert_face ( Vector && vector ) -> std::size_t

inline

Insert a face from an ordered list of Vertex indices.

Accepts an iterable supporting range-based for loops.

Note: This function does not update the mesh boundary connections. Call update_boundary() after all faces have been inserted, or use insert_faces() to insert faces and update the boundary in one step.

Parameters

vector List of vertex indices

Exceptions

std::out_of_range	If one of the vertex indices is out of bounds.
MeshException	(1) If one of provided edges is already paired. This indicates that the mesh is not 2-manifold. (2) If an edge has zero length. This means the face has zero area. (3) If an edge's interior angle is NaN or Inf.

◆ insert_face_()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

template<class Vector >

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::insert_face_	(	const Vector &	vector,
		FacePtr	face = `nullptr`
	)		-> std::size_t

inlineprivate

Face insertion implementation

Parameters

vector	Iterable of vertex indices
face	Pre-existing Face (only used when cloning)

◆ insert_faces() [1/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

template<class VectorOfVectors >

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::insert_faces ( const VectorOfVectors & v ) -> std::vector<std::size_t>

inline

Insert new faces from a list of lists of Vertex indices.

A convenience function which adds multiple faces to the mesh (using insert_face()) and updates the mesh boundary (using update_boundary()) when complete.

◆ insert_faces() [2/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

template<typename IdxType >

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::insert_faces ( std::initializer_list< std::initializer_list< IdxType > > v )

inline

Insert new faces from a list of lists of Vertex indices.

A convenience function which adds multiple faces to the mesh (using insert_face()) and updates the mesh boundary (using update_boundary()) when complete.

◆ insert_vertex()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

template<typename... Args>

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::insert_vertex ( Args... args ) -> std::size_t

inline

Insert a new vertex.

Accepts all arguments supported by the Vertex constructor.

◆ insert_vertices() [1/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

template<class VectorOfVectors >

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::insert_vertices ( const VectorOfVectors & v ) -> std::vector<std::size_t>

inline

Insert new vertices from a list of Vertex-like objects.

A convenience function which adds multiple vertices to the mesh.

◆ insert_vertices() [2/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

template<typename ValType >

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::insert_vertices ( std::initializer_list< std::initializer_list< ValType > > v ) -> std::vector<std::size_t>

inline

Insert new vertices from a brace-enclosed initializer list.

Convenience overload of insert_vertices() accepting nested std::initializer_list syntax, e.g. {{0,0,0}, {1,0,0}, {0,1,0}}.

◆ num_connected_components()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

auto OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::num_connected_components ( ) const -> std::size_t

inline

Get the number of connected components.

A connected component is a set of continuous, adjacent faces. If you want to get the list of connected components, use connected_components().

See also: connected_components()

◆ rekey_edge_to_vertex_()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

void OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::rekey_edge_to_vertex_	(	const EdgePtr &	e,
		const VertPtr &	newVert
	)

inlineprivate

Move e from its current edges_ bucket to the bucket keyed by newVert, and update e->vertex.

edges_ is a multimap keyed by half-edge origin vertex index. Any code that reassigns a half-edge's origin (e.g. split_edge duplicating a vertex and moving a fan of half-edges to the new vertex) must call this to keep the multimap consistent, otherwise outgoing_edges() / incoming_edges() / Vertex::is_manifold() return stale results.

◆ split_edge()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

void OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::split_edge ( const EdgePtr & edge )

inline

Split an edge in order to introduce a new boundary.

Disconnects a single, paired half-edge (i.e. a single edge between two connected triangles) into two, unpaired half-edges, creating a "hole" in the mesh's connectivity graph. Useful when you want to introduce a boundary, or tear, into a mesh to improve parameterization.

Note: If the given edge intersects with an existing boundary, one or both of your endpoint vertices will be duplicated. Be sure to take this into account when converting the parameterized mesh to your (per-wedge) UV map.

See also: split_path()

◆ split_path() [1/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

void OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::split_path ( const std::vector< EdgePtr > & path )

inline

Split a list of edges (path) to form a new boundary.

Note: This function was designed to split a list of continuous edges forming a path on the surface of the mesh. Providing otherwise can lead to undefined behavior.

See also: split_edge()

◆ split_path() [2/2]

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

void OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::split_path ( const std::vector< std::size_t > & path )

inline

Split a list of edges (path) to form a new boundary.

This overload accepts a list of vertex indices forming a continuous path.

Note: This function was designed to split a list of continuous edges forming a path on the surface of the mesh. Providing otherwise can lead to undefined behavior.

See also: split_edge()

◆ update_boundary()

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

void OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::update_boundary ( )

inline

Update the mesh boundary connections.

Because the mesh boundary may become temporarily non-traversable while the mesh is being constructed, the mesh boundary connections should only be updated after all faces have been added to the mesh. Call this function after inserting faces with insert_face() or use insert_faces() to construct the mesh and update the boundary in one step.

Member Data Documentation

◆ edges_

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

std::multimap<std::size_t, EdgePtr> OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::edges_

private

List of all edges, indexed by the vertex's insertion index

◆ faces_

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

std::vector<FacePtr> OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::faces_

private

List of faces

◆ numFaceEdges_

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

std::size_t OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::numFaceEdges_ {0}

private

Number of all edges which border a face

◆ verts_

template<typename T , std::size_t Dim = 3, typename VertexTraits = traits::DefaultVertexTraits<T>, typename EdgeTraits = traits::DefaultEdgeTraits<T>, typename FaceTraits = traits::DefaultFaceTraits<T>>

std::vector<VertPtr> OpenABF::HalfEdgeMesh< T, Dim, VertexTraits, EdgeTraits, FaceTraits >::verts_

private

List of vertices

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Pointer

◆ type

Member Function Documentation

◆ boundaries()

◆ boundary_edge()

◆ clone()

◆ clone_face_() [1/2]

◆ clone_face_() [2/2]

◆ extract_connected_components()

◆ insert_face() [1/2]

◆ insert_face() [2/2]

◆ insert_face_()

◆ insert_faces() [1/2]

◆ insert_faces() [2/2]

◆ insert_vertex()

◆ insert_vertices() [1/2]

◆ insert_vertices() [2/2]

◆ num_connected_components()

◆ rekey_edge_to_vertex_()

◆ split_edge()

◆ split_path() [1/2]

◆ split_path() [2/2]

◆ update_boundary()

Member Data Documentation

◆ edges_

◆ faces_

◆ numFaceEdges_

◆ verts_