HMesh Namespace Reference

The HMesh namespace contains the Manifold class which is a halfedge based mesh. More...

Classes
class	AttributeVector
class	VertexAttributeVector
class	FaceAttributeVector
class	HalfEdgeAttributeVector
struct	IDRemap
struct	Vertex
struct	Face
struct	HalfEdge
class	ConnectivityKernel
class	HalfEdgeWalker
struct	VertexTag
struct	FaceTag
struct	HalfEdgeTag
class	ItemID
class	ItemVector
class	IDIterator
class	Manifold
class	ValencyEnergy
class	RandomEnergy
class	GaussCurvatureEnergy
struct	PQElem
class	EnergyFun
	This class represents the energy of an edge. It is used in optimization schemes where edges are swapped (aka flipped). */. More...
class	MinAngleEnergy
class	DihedralEnergy
class	CurvatureEnergy
struct	PotentialEdge
Typedefs
typedef std::map< VertexID, VertexID >	VertexIDRemap
typedef std::map< FaceID, FaceID >	FaceIDRemap
typedef std::map< HalfEdgeID, HalfEdgeID >	HalfEdgeIDRemap
typedef ItemID< VertexTag >	VertexID
typedef ItemID< FaceTag >	FaceID
typedef ItemID< HalfEdgeTag >	HalfEdgeID
typedef IDIterator< VertexID >	VertexIDIterator
typedef IDIterator< FaceID >	FaceIDIterator
typedef IDIterator< HalfEdgeID >	HalfEdgeIDIterator
typedef std::priority_queue < PotentialEdge, std::vector < PotentialEdge > , std::greater< PotentialEdge > >	PotentialEdgeQueue
Enumerations
enum	WeightScheme { FLOATER_W, HARMONIC_W, LSCM_W, BARYCENTRIC_W }
Functions
void	remove_caps (Manifold &m, float thresh)
	Remove caps from a manifold consisting of only triangles. A cap is a triangle with two very small angles and an angle close to pi, however a cap does not necessarily have a very short edge. Set the ang_thresh to a value close to pi. The closer to pi the _less_ sensitive the cap removal. A cap is removed by flipping the (long) edge E opposite to the vertex V with the angle close to pi. However, the function is more complex. Read code and document more carefully !!!
void	remove_needles (Manifold &m, float thresh)
	Remove needles from a manifold consisting of only triangles. A needle is a triangle with a single very short edge. It is moved by collapsing the short edge. The thresh parameter sets the length threshold. The position of the vertex which survives the collapse is set to one of the two end points. Selection is based on what changes the geometry least.
void	close_holes (Manifold &m)
	This function replaces holes by faces. It is really a simple function that just finds all loops of edges next to missing faces.
void	flatten (Manifold &m, WeightScheme ws)
	This function flattens a mesh with a simple boundary, based on a weight scheme.It is mostly for showing mesh parametrization methods. The current mesh MUST have a SINGLE boundary loop. This loop is mapped to the unit circle in a regular fashion (equal angle intervals). All non boundary vertices are placed at the origin. Then the system is relaxed iteratively using the weight scheme given as argument.
bool	inp_load (const std::string &, Manifold &m)
	Load an INP file.
template<typename T >
std::ostream &	operator<< (std::ostream &os, const ItemID< T > &iid)
bool	load (const string &file_name, Manifold &mani)
bool	load (const std::string &, Manifold &m)
	Load a geometry file. This could be a PLY, OBJ, X3D, or OFF file.
bool	valid (const Manifold &m)
	Verify Manifold Integrity Performs a series of tests to check that this is a valid manifold. This function is not rigorously constructed but seems to catch all problems so far. The function returns true if the mesh is valid and false otherwise.
void	bbox (const Manifold &m, CGLA::Vec3f &pmin, CGLA::Vec3f &pmax)
	Calculate the bounding box of the manifold.
void	bsphere (const Manifold &m, CGLA::Vec3f &c, float &r)
	Calculate the bounding sphere of the manifold.
bool	precond_collapse_edge (const Manifold &m, HalfEdgeID h)
	Test for legal edge collapse. The argument h is the halfedge we want to collapse. If this function does not return true, it is illegal to collapse h. The reason is that the collapse would violate the manifold property of the mesh. The test is as follows: 1. For the two vertices adjacent to the edge, we generate a list of all their neighbouring vertices. We then generate a list of the vertices that occur in both these lists. That is, we find all vertices connected by edges to both endpoints of the edge and store these in a list. 2. For both faces incident on the edge, check whether they are triangular. If this is the case, the face will be removed, and it is ok that the the third vertex is connected to both endpoints. Thus the third vertex in such a face is removed from the list generated in 1. 3. If the list is now empty, all is well. Otherwise, there would be a vertex in the new mesh with two edges connecting it to the same vertex. Return false. 4. TETRAHEDRON TEST: If the valency of both vertices is three, and the incident faces are triangles, we also disallow the operation. Reason: A vertex valency of two and two triangles incident on the adjacent vertices makes the construction collapse. 5. VALENCY 4 TEST: If a triangle is adjacent to the edge being collapsed, it disappears. This means the valency of the remaining edge vertex is decreased by one. A valency two vertex reduced to a valency one vertex is considered illegal. 6. PREVENT MERGING HOLES: Collapsing an edge with boundary endpoints and valid faces results in the creation where two holes meet. A non manifold situation. We could relax this... 7. New test: if the same face is in the one-ring of both vertices but not adjacent to the common edge, then the result of a collapse would be a one ring where the same face occurs twice. This is disallowed as the resulting face would be non-simple.
bool	precond_flip_edge (const Manifold &m, HalfEdgeID h)
	Test fpr legal edge flip. Returns false if flipping cannot be performed. This is due to one of following: 1. one of the two adjacent faces is not a triangle. 2. Either end point has valency three. 3. The vertices that will be connected already are.
bool	boundary (const Manifold &m, HalfEdgeID h)
	Returns true if the halfedge is a boundary halfedge.
int	valency (const Manifold &m, VertexID v)
	Compute valency, i.e. number of incident edges.
CGLA::Vec3f	normal (const Manifold &m, VertexID v)
	Compute the vertex normal. This function computes the angle weighted sum of incident face normals.
bool	connected (const Manifold &m, VertexID v0, VertexID v1)
	Returns true if the two argument vertices are in each other's one-rings.
int	no_edges (const Manifold &m, FaceID f)
	Compute the number of edges of a face.
float	area (const Manifold &m, FaceID f)
	Compute the area of a face.
CGLA::Vec3f	centre (const Manifold &m, FaceID f)
	Compute the centre of a face.
float	perimeter (const Manifold &m, FaceID f)
	Compute the perimeter of a face.
float	length (const Manifold &m, HalfEdgeID h)
	Return the geometric length of a halfedge.
bool	operator< (const PQElem &e0, const PQElem &e1)
void	add_to_queue (const Manifold &m, HalfEdgeAttributeVector< int > &touched, priority_queue< PQElem > &Q, HalfEdgeID h, const EnergyFun &efun)
void	add_one_ring_to_queue (const Manifold &m, HalfEdgeAttributeVector< int > &touched, priority_queue< PQElem > &Q, VertexID v, const EnergyFun &efun)
void	priority_queue_optimization (Manifold &m, const EnergyFun &efun)
	Optimize in a greedy fashion.
void	simulated_annealing_optimization (Manifold &m, const EnergyFun &efun, int max_iter=10000)
	Optimize with simulated annealing. Avoids getting trapped in local minima.
void	minimize_dihedral_angle (Manifold &m, int max_iter=10000, bool anneal=false, bool alpha=false, double gamma=4.0)
	Minimize the angle between adjacent triangles. Almost the same as mean curvature minimization.
void	randomize_mesh (Manifold &m, int max_iter)
	Make radom flips. Useful for generating synthetic test cases.
void	minimize_curvature (Manifold &m, bool anneal=false)
	Minimizes mean curvature. This is really the same as dihedral angle optimization except that we weight by edge length.
void	minimize_gauss_curvature (Manifold &m, bool anneal=false)
	Minimizes gaussian curvature. Probably less useful than mean curvature.
void	maximize_min_angle (Manifold &m, float thresh, bool anneal=false)
	Maximizes the minimum angle of triangles. Makes the mesh more Delaunay.
void	optimize_valency (Manifold &m, bool anneal=false)
	Tries to achieve valence 6 internally and 4 along edges.
bool	obj_load (const string &filename, Manifold &m)
bool	obj_load (const std::string &, Manifold &m)
bool	obj_save (const string &filename, Manifold &m)
bool	obj_save (const std::string &, Manifold &m)
	Save in Wavefront OBJ format.
bool	off_load (const std::string &, Manifold &m)
	Load an OFF file (Object File Format). So far, this loader is mostly ensured to load files from the Princeton Shape Benchmark.
bool	off_save (const string &filename, Manifold &m)
bool	off_save (const std::string &, HMesh::Manifold &m)
bool	ply_load (const string &filename, Manifold &m)
bool	ply_load (const std::string &, Manifold &m)
void	quadric_simplify (Manifold &m, double keep_fraction, double singular_thresh=0.0001, bool choose_optimal_positions=true)
	Garland Heckbert simplification in our own implementation. keep_fraction is the fraction of vertices to retain. The singular_thresh defines how small singular values from the SVD we accept. It is relative to the greatest singular value. If choose_optimal_positions is true, we reposition vertices. Otherwise the vertices are a subset of the old vertices.
float	average_edge_length (const Manifold &m)
	Return the average edge length.
int	refine_edges (Manifold &m, float t)
Vec3f	laplacian (const Manifold &m, VertexID v)
void	laplacian_smooth (HMesh::Manifold &m, float t=1.0f)
	Simple laplacian smoothing with an optional weight.
void	taubin_smooth (HMesh::Manifold &m, int iter)
	Taubin smoothing is similar to laplacian smoothing but reduces shrinkage.
void	face_neighbourhood (Manifold &m, FaceAttributeVector< int > &touched, FaceID f, vector< Vec3f > &nbrs)
Vec3f	filtered_normal (Manifold &m, FaceAttributeVector< int > &touched, FaceID f)
void	fvm_smooth (HMesh::Manifold &m, int iter)
	Fuzzy vector median smoothing is effective when it comes to preserving sharp edges.
void	cc_split (Manifold &m_in, Manifold &m_out)
void	cc_smooth (Manifold &m)
void	get_candidates (const Manifold &m, VertexID v, vector< HalfEdgeID > &candidates)
float	curv (const Vec3f &p, vector< Vec3f > &vec)
float	get_badness (const Manifold &m, VertexID v, VertexID n)
const CGLA::Vec3f	get_normal (const Manifold &m, VertexID v)
void	triangulate_by_vertex_face_split (Manifold &m)
	Naive triangulation by connecting to center point.
void	triangulate_by_edge_face_split (Manifold &m)
	Naive division of polygons into triangles.
bool	operator> (const PotentialEdge &e0, const PotentialEdge &e1)
void	insert_potential_edges (const Manifold &m, VertexAttributeVector< int > &vtouched, VertexID v, PotentialEdgeQueue &pot_edges)
void	curvature_triangulate (Manifold &m)
	Try to respect curvature to create a better triangulation.
void	shortest_edge_triangulate (Manifold &m)
	Triangulate by connecting the points forming the shortest edge.
void	triangulate_face_by_edge_split (Manifold &m, FaceID f)
	Triangulate a polygonal face by repeatedly calling split_face. split_face_triangulate iteratively splits triangles off a polygon. The first triangle split off is the one connecting f.last().vert() and f.last().next().next().vert().
void	handle_Shape (XmlElement &elem)
void	handle_IndexedFaceSet (XmlElement &elem)
void	handle_Coordinate (XmlElement &elem)
int	find_last_of (const string &F, const string &C)
bool	x3d_load (const string &filename, Manifold &m)
bool	x3d_load (const std::string &filename, Manifold &m)
	Load a mesh from an X3D file. It handles arbitrary polygons.
bool	x3d_save (const std::string &, Manifold &m)
	Save mesh to x3d file.

---

Detailed Description

The HMesh namespace contains the Manifold class which is a halfedge based mesh.

Apart from manifold there are also face and vertex circulators in this namespace. More advanced things are relegated to the HMeshUtil namespace.

Some applications are also found here. For instance an isosurface polygonizer and Garland Heckbert simplification has been implemented on top of HMesh.

---

Function Documentation

bool HMesh::boundary	(	const Manifold &	m,
		VertexID	v
	)

Returns true if the halfedge is a boundary halfedge.

Returns true if the vertex is a boundary vertex.

void HMesh::cc_split	(	Manifold &	,
		Manifold &
	)

Perform a Catmull-Clark split, i.e. a split where each face is divided into new quadrilateral faces formed by connecting a corner with a point on each incident edge and a point at the centre of the face.

CGLA::Vec3f HMesh::normal	(	const Manifold &	m,
		FaceID	f
	)

Compute the vertex normal. This function computes the angle weighted sum of incident face normals.

Compute the normal of a face. If the face is not a triangle, the normal is not defined, but computed using the first three vertices of the face.

bool HMesh::obj_load	(	const std::string &	,
		Manifold &	m
	)

Load an Wavefront OBJ file. This is just a simple frontend for the Geometry::obj_load function which loads OBJ files into triangle meshes. Consequently, quads are unfortunately converted to triangles when this loader is used.

bool HMesh::off_save	(	const std::string &	,
		HMesh::Manifold &	m
	)

Save in OFF format.

bool HMesh::ply_load	(	const std::string &	,
		Manifold &	m
	)

Load an Wavefront OBJ file. This is just a simple frontend for the Geometry::obj_load function which loads OBJ files into triangle meshes. Consequently, quads are unfortunately converted to triangles when this loader is used.

int HMesh::refine_edges	(	Manifold &	m,
		float	t
	)

Split all edges in mesh passed as first argument which are longer than the threshold (second arg) length. A split edge results in a new vertex of valence two. We triangulate the faces on either side to ensure that there are no valence two vertices.