Rev 519 | Rev 546 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed
/* ----------------------------------------------------------------------- *
* This file is part of GEL, www.imm.dtu.dk/GEL
* Copyright (C) the authors (see AUTHORS.txt) and DTU Informatics
*
* Principal authors:
* Christian Thode Larsen (thode2d@gmail.com)
* J. Andreas Baerentzen (jab@imm.dtu.dk)
*
* See LICENSE.txt for licensing information
* ----------------------------------------------------------------------- */
#ifndef __HMESH_MANIFOLD_H__
#define __HMESH_MANIFOLD_H__
#include <CGLA/Vec3f.h>
#include "ConnectivityKernel.h"
#include "Iterators.h"
#include "HalfEdgeWalker.h"
#include "AttributeVector.h"
namespace Geometry
{
// forward declaration
class TriMesh;
class IndexedFaceSet;
}
namespace HMesh
{
class Manifold
{
public:
/// Default constructor
Manifold();
/** \brief Build a manifold.
The arguments are the number of vertices, no_vertices, the vector of vertices, vertvec, the number of faces, no_faces.
facevecis an array where each entry indicates the number of vertices in that face.
The array indices contains all the corresponding vertex indices in one concatenated list. */
void build( size_t no_vertices,
const float* vertvec,
size_t no_faces,
const int* facevec,
const int* indices);
/// Build a manifold from a TriMesh
void build(const Geometry::TriMesh& mesh);
/** \brief Collapse the halfedge h.
The argument h is the halfedge being removed. The vertex v=h->opp->vert is the one being removed while h->vert survives.
The final argument indicates whether the surviving vertex should have the average position of the former vertices.
By default false meaning that the surviving vertex retains it position.
This function is not guaranteed to keep the mesh sane unless, precond_collapse_edge has returned true !! */
void collapse_edge(HalfEdgeID h, bool avg_vertices = false);
/** \brief Split a face.
The face, f, is split by creating an edge with endpoints v0 and v1 (the next two arguments).
The vertices of the old face between v0 and v1 (in counter clockwise order) continue to belong to f.
The vertices between v1 and v0 belong to the new face. A handle to the new face is returned. */
FaceID split_face_by_edge(FaceID f, VertexID v0, VertexID v1);
/** \brief Split a polygon, f, by inserting a vertex at the barycenter.
This function is less likely to create flipped triangles than the split_face_triangulate function.
On the other hand, it introduces more vertices and probably makes the triangles more acute.
A handle to the inserted vertex is returned. */
VertexID split_face_by_vertex(FaceID f);
// VertexID split_face_by_vertex(HalfEdgeID h);
/** \brief Insert a new vertex on halfedge h.
The new halfedge is insterted as the previous edge to h.
A handle to the inserted vertex is returned. */
VertexID split_edge(HalfEdgeID h);
/** \brief Merges two faces into a single polygon.
The first face is f. The second face is adjacent to f along the halfedge h.
This function returns true if the merging was possible and false otherwise.
Currently merge only fails if the mesh is already illegal. Thus it should, in fact, never fail. */
bool merge_faces(FaceID f, HalfEdgeID h);
/// \brief Close hole given by the invalid face of halfedgehandle h.
void close_hole(HalfEdgeID h);
/// \brief Flip an edge h.
void flip_edge(HalfEdgeID h);
/// Get number of vertices
size_t active_vertices() const;
/// Get number of halfedges
size_t active_halfedges() const;
/// Get number of faces
size_t active_faces() const;
/// Get number of vertices
size_t total_vertices() const;
/// Get number of halfedges
size_t total_halfedges() const;
/// Get number of faces
size_t total_faces() const;
bool in_use(VertexID id) const;
bool in_use(FaceID id) const;
bool in_use(HalfEdgeID id) const;
/// Iterator to first VertexID, optional argument defines if unused items should be skipped
VertexIDIterator vertices_begin(bool skip = true) const;
/// Iterator to first FaceID, optional argument defines if unused items should be skipped
FaceIDIterator faces_begin(bool skip = true) const;
/// Iterator to first HalfEdgeID, optional argument defines if unused items should be skipped
HalfEdgeIDIterator halfedges_begin(bool skip = true) const;
/// Iterator to past the end VertexID
VertexIDIterator vertices_end() const;
/// Iterator topast the end FaceID
FaceIDIterator faces_end() const;
/// Iterator to past the end HalfEdgeID
HalfEdgeIDIterator halfedges_end() const;
/// Returns a HalfEdgeWalker to the out halfedge of vertex given by VertexID
HalfEdgeWalker halfedgewalker(VertexID id) const;
/// Returns a HalfEdgeWalker to the last halfedge of face given by FaceID
HalfEdgeWalker halfedgewalker(FaceID id) const;
/// Returns a HalfEdgeWalker to the halfedge given by HalfEdgeID
HalfEdgeWalker halfedgewalker(HalfEdgeID id) const;
/// Return reference to position given by VertexID
CGLA::Vec3f& pos(VertexID id);
/// Return const reference to position given by VertexID
const CGLA::Vec3f& pos(VertexID id) const;
/// Clear the mesh
void clear();
/// Remove unused items from Mesh, map argument is to be used for attribute vector cleanups in order to maintain sync.
void cleanup(IDRemap& map);
/// Remove unused items from Mesh
void cleanup();
private:
ConnectivityKernel ck;
VertexAttributeVector<CGLA::Vec3f> positions;
// private template for building the manifold from various types
template<typename size_type, typename float_type, typename int_type>
void build_template(size_type no_vertices,
const float_type* vertvec,
size_type no_faces,
const int_type* facevec,
const int_type* indices);
/// Set the next and prev indices of the first and second argument respectively.
void link(HalfEdgeID h0, HalfEdgeID h1);
/// Glue halfedges by letting the opp indices point to each other.
void glue(HalfEdgeID h0, HalfEdgeID h1);
/// Auxiliary function called from collapse
void remove_face_if_degenerate(HalfEdgeID h);
/// Ensure boundary consistency.
void ensure_boundary_consistency(VertexID v);
};
/** \brief 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. */
bool valid(const Manifold& m);
/// Calculate the bounding box of the manifold
void bbox(const Manifold& m, CGLA::Vec3f& pmin, CGLA::Vec3f& pmax);
/// Calculate the bounding sphere of the manifold
void bsphere(const Manifold& m, CGLA::Vec3f& c, float& r);
/** \brief 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 three vertex reduced to a valency two 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. */
bool precond_collapse_edge(const Manifold& m, HalfEdgeID h);
/** \brief 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 precond_flip_edge(const Manifold& m, HalfEdgeID h);
/// Returns true if the halfedge is a boundary halfedge.
bool boundary(const Manifold& m, HalfEdgeID h);
/// Return the geometric length of a halfedge.
float length(const Manifold& m, HalfEdgeID h);
/// Returns true if the vertex is a boundary vertex.
bool boundary(const Manifold& m, VertexID v);
/// Compute valency, i.e. number of incident edges.
int valency(const Manifold& m, VertexID v);
/// Compute the vertex normal. This function computes the angle weighted sum of incident face normals.
CGLA::Vec3f normal(const Manifold& m, VertexID v);
/// Returns true if the two argument vertices are in each other's one-rings.
bool connected(const Manifold& m, VertexID v0, VertexID v1);
/// Compute the number of edges of a face
int no_edges(const Manifold& m, FaceID f);
/** 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. */
CGLA::Vec3f normal(const Manifold& m, FaceID f);
/// Compute the area of a face.
float area(const Manifold& m, FaceID f);
/// Compute the centre of a face
CGLA::Vec3f centre(const Manifold& m, FaceID f);
/*******************************************************************
* Manifold code
*******************************************************************/
inline Manifold::Manifold(){}
inline size_t Manifold::active_vertices() const
{ return ck.active_vertices(); }
inline size_t Manifold::active_halfedges() const
{ return ck.active_halfedges(); }
inline size_t Manifold::active_faces() const
{ return ck.active_faces(); }
inline size_t Manifold::total_vertices() const
{ return ck.total_vertices(); }
inline size_t Manifold::total_halfedges() const
{ return ck.total_halfedges(); }
inline size_t Manifold::total_faces() const
{ return ck.total_faces(); }
inline bool Manifold::in_use(VertexID id) const
{ return ck.in_use(id); }
inline bool Manifold::in_use(FaceID id) const
{ return ck.in_use(id); }
inline bool Manifold::in_use(HalfEdgeID id) const
{ return ck.in_use(id); }
inline VertexIDIterator Manifold::vertices_begin(bool skip) const
{ return VertexIDIterator(ck, ck.vertices_begin(skip), skip); }
inline FaceIDIterator Manifold::faces_begin(bool skip) const
{ return FaceIDIterator(ck, ck.faces_begin(skip), skip); }
inline HalfEdgeIDIterator Manifold:: halfedges_begin(bool skip) const
{ return HalfEdgeIDIterator(ck, ck.halfedges_begin(skip), skip); }
inline VertexIDIterator Manifold::vertices_end() const
{ return VertexIDIterator(ck, ck.vertices_end()); }
inline FaceIDIterator Manifold::faces_end() const
{ return FaceIDIterator(ck, ck.faces_end()); }
inline HalfEdgeIDIterator Manifold::halfedges_end() const
{ return HalfEdgeIDIterator(ck, ck.halfedges_end()); }
inline HalfEdgeWalker Manifold::halfedgewalker(VertexID id) const
{ return HalfEdgeWalker(ck, ck.out(id)); }
inline HalfEdgeWalker Manifold::halfedgewalker(FaceID id) const
{ return HalfEdgeWalker(ck, ck.last(id)); }
inline HalfEdgeWalker Manifold::halfedgewalker(HalfEdgeID id) const
{ return HalfEdgeWalker(ck, id); }
inline CGLA::Vec3f& Manifold::pos(VertexID id)
{ return positions[id]; }
inline const CGLA::Vec3f& Manifold::pos(VertexID id) const
{ return positions[id]; }
inline void Manifold::clear()
{
ck.clear();
positions.clear();
}
inline void Manifold::cleanup(IDRemap& map)
{
ck.cleanup(map);
positions.cleanup(map.vmap);
}
inline void Manifold::cleanup()
{
IDRemap map;
cleanup(map);
}
}
#endif __HMESH_MANIFOLD_H__