WebSVN – gelsvn – Diff – /trunk/src/HMesh/Manifold.h


#ifndef __HMESH_MANIFOLD_H
#define __HMESH_MANIFOLD_H
 
#include <vector>
#include <list>
#include <map>
 
#include "Vertex.h"
#include "HalfEdge.h"
#include "Face.h"
 
namespace HMesh
{
	class VertexCirculator;
	class FaceCirculator;
 
	/** \brief A Data structure representing an open or closed manifold.
			Manifold keeps lists of the entities making up a halfedge mesh
			and provides basic functions for creating new faces, halfedges
			and vertices. There are also primitive operations for editing 
			such as edge collapse. */
	class Manifold
		{
			std::list<Vertex> vertex_db;
			std::list<Face> face_db;
			std::list<HalfEdge> halfedge_db;
 
			bool erase_immediately;
			std::vector<VertexIter> unused_vertices;
			std::vector<FaceIter> unused_faces;
			std::vector<HalfEdgeIter> unused_halfedges;
 
 
			/** Remove a face if it contains only two edges.
					This is an auxiliary function called from collapse_halfedge. */
			void remove_face_if_degenerate(HalfEdgeIter);
 
			Manifold(const Manifold&) {}
			/**< Empty copy constructor.
				 Copying a manifold will not work, since faces, vertices, and
				 halfedges contain iterators pointing to other faces, vertices,
				 and halfedges. These pointers would need to be changed if the 
				 mesh were copied. In other words, we would need to walk the
				 entire mesh. This may be required but it should not be an 
				 operation that is easily invoked by calling the copy constructor.
				 Hence, this operator is made private.		*/
 
			const Manifold& operator=(const Manifold&) {return *this;}
			/**< Empty assignment operator.
				 The assignment operator is private for the same reason that the
				 copy constructor is private. */
 
		public:
 
 
			Manifold(): erase_immediately(true) {}
			///< Construct an empty manifold.
 
			bool is_valid();
			/**< 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 enumerate_vertices();
			/**< Give each vertex a unique id corresponding to its iterator
				 position. Value is stored in the touched attribute. */
 
			void enumerate_halfedges();
			/**< Give each halfedge a unique id corresponding to its iterator
				 position. Value is stored in the touched attribute. */
 
			void enumerate_faces();
			/**< Give each face a unique id corresponding to its iterator
				 position. Value is stored in the touched attribute. */
				 
			size_t no_faces() const {return face_db.size();}
			///< Return the number of faces.
 
			size_t no_halfedges() const {return halfedge_db.size();}
			///< Return the number of halfedges.
 
			size_t no_vertices() const {return vertex_db.size();}
			///< Return the number of vertices
 
			VertexIter create_vertex(const CGLA::Vec3f& pos);
			///< Create a new vertex.
 
			FaceIter create_face();
			/**< Create a new face.
				 An iterator to the face is returned. When a face f is initially
				 created, is_used(f) will return false. */
 
			HalfEdgeIter create_halfedge();
			/**< Create a new halfedge. An iterator to the halfedge is returned.
				 When h is initially created, is_used(h) returns false. */
 
			void clear();
			///< Clear the manifold, removing all data.
 
			void remove_unused();
			/**< Remove unused vertices, edges and faces from the database.
				 If delayed_erase mode is enabled, then until this function 
				 has been called, erased vertices, edges, and faces are just marked
				 as unused but not removed from their respective lists. */
 
			void delayed_erase();
			/**< Delay the actual removal of vertices, faces, and edges that
				 are erased.  In many cases, it is a problem if one cannot
				 test whether a vertex, halfedge, or face indicated by an
				 iterator is in use or has been removed from the mesh. One
				 solution to this problem is to delay the actual removal of
				 the vertex, edge or face. Instead when calling, say,
				 erase_face(f), all the iterators of f are assigned the
				 appropriate NULL value to indicate that they are not
				 pointing at anything, and f is added to a vector of faces
				 that need to be physically removed from the face_db.
 
				 Since f is not erased, all iterators pointing at f remain
				 valid! And, importantly, it is possible to test whether f is
				 in use by calling is_used(f).
 
				 When remove_unused is called, the physical removal takes
				 place. Calling immediate_erase switches Manifold back to the
				 state where entities are removed as soon as the appropriate
				 erase function is called, and at the same time calls
				 remove_unused.
			*/
 
			void immediate_erase();
			/**< Immediately remove erased entities.
				 Calling immediate_erase switches Manifold back to the state
				 where entities are removed as soon as the appropriate erase
				 function is called.
 
				 See delayed_erase for more details, and note that
				 immediate_erase is the default mode.  */
 
			bool is_used(VertexIter v) const;
			/**< Test whether the vertex indicated by the argument v is used.
				 This function returns true if the vertex appears to have a 
				 valid outgoing halfedge iterator. */
 
			bool is_used(FaceIter f) const;
			/**< Test whether the face indicated by the argument f is used.
				 This function returns true if the face appears to have a 
				 valid halfedge iterator. */
 
			bool is_used(HalfEdgeIter h) const;
			/**< Test whether the halfedge indicated by the argument h is used.
				 This function returns true if the halfedge appears to have a 
				 valid vertex iterator. */
 
			void erase_halfedge(HalfEdgeIter h);			
			/**< Erase halfedge h. 
				 In general, you should never call this function but use the 
				 collapse_halfedge function instead since blindly erasing geometry
				 is most likely to invalidate the Mesh. Quite possibly this function
				 will be removed from the public interface. 
					
				 Note that if delayed_erase has been called, this function does
				 not immediately remove anything from the mesh. Instead the halfedge
				 is reset to its initial state. Thus, iterators are not invalidated,
				 and it is possible to test whether h is used calling:
				 is_used(h). when remove_unused is called, the actual removal
				 takes place.
			*/
 
			void erase_vertex(VertexIter v);
			/**< Erase vertex v.
				 In general, you should never call this function but use the 
				 collapse_halfedge function to collapse the vertex away.
				 Blindly erasing is extremely likely to invalidate the
				 Mesh. Quite possibly this function will be removed from the
				 public interface. 
 
				 Note that if delayed_erase has been called, this function does
				 not immediately remove anything from the mesh. Instead the halfedge
				 is reset to its initial state. Thus, iterators are not invalidated,
				 and it is possible to test whether v is used calling:
				 is_used(v). when remove_unused is called, the actual removal
				 takes place.
			*/
 
 
			void erase_face(FaceIter f);
			/**< Erase face f.
				 In general, you should never call this function but use 
				 collapse_halfedge in conjunction with other functions to
				 remove the face through (Euler) operations which preserve
				 the mesh in a valid state.
				 Blindly erasing is extremely likely to invalidate the
				 Mesh. Quite possibly this function will be removed from the
				 public interface. 
 
				 Note that if delayed_erase has been called, this function does
				 not immediately remove anything from the mesh. Instead the face
				 is reset to its initial state. Thus, iterators are not invalidated,
				 and it is possible to test whether f is used calling:
				 is_used(f). when remove_unused is called, the actual removal
				 takes place.
			*/
 
			HalfEdgeIter halfedges_begin();
			///< Return iterator pointing to the first halfedge.
 
			HalfEdgeIter halfedges_end();
			///< Return iterator pointing to beyond the last halfedge.
 
			VertexIter vertices_begin();
			///< Return iterator pointing to the first vertex.
 
			VertexIter vertices_end();
			///< Return iterator pointing to beyond the last vertex.
 
			FaceIter faces_begin();
			///< Return iterator pointing to the first face.
 
			FaceIter faces_end();
			///< Return iterator pointing to beyond the last face.
 
			bool collapse_precond(HalfEdgeIter h);
			/**< \brief HalfEdge collapse precondition.
 
			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: It introduces a vertex of valency two
			and if the final two polygons incident on the vertices 
			that are adjacent to the edge being collapsed are triangles, then
			the construction will collapse
 
			5. VALENCY 4 TEST:
			If a face adjacent to the edge being collapsed is a triangle,
			it will disappear, and the valency of the final vertex beloning to
			this edge will be reduced by one. Hence this valency should be at
			least 4. A valency three vertex will be reduced to a valency two
			vertex which is considered illegal.
 
			6. PREVENT MERGING HOLES:
			We do not want to collapse an edge if its end points are boundary
			vertices, but its two adjacent faces are not NULL faces, because
			in that case we create a vertex where two holes meet. A non manifold
			situation.	*/
 
 
			void collapse_halfedge(HalfEdgeIter h, bool=false);
			/**< 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 is a boolean indicating whether the vertex
			that survives the collapse should have a position which is the
			average of its own position and the vertex that is removed.
			By default false meaning that the surviving vertex retains it 
			position.
 
			This function is not guaranteed to keep the mesh sane unless,
			collapse_precond has returned true !!
			*/
 
			FaceIter split_face(FaceIter f, VertexIter v0, VertexIter v1);
			/**< Split a face.
				 The face, f, is split by connecting two
				 vertices 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. An iterator to the new face is 
				 returned. */
 
			VertexIter split_edge(HalfEdgeIter h);
			/**< Insert a new vertex on halfedge h.
				 The new halfedge is insterted as the previous edge to h.
				 An iterator to the inserted vertex is	returned. */
 
			void triangulate(FaceIter f);
			/**< Triangulate a polygonal face by repeatedly calling 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.
			*/
 
			VertexIter safe_triangulate(FaceIter f);
			/**< Triangulate a polygon, f, by inserting a vertex at the barycenter.
				 All vertices in f are connected to the new vertex.				
				 The word "safe" means that it is less likely to create flipped
				 triangles than the normal triangulate. On the other hand, it 
				 introduces more vertices and probably makes the triangles more
				 acute. This function simply calls face_insert_point.
 
				 The inserted vertex is returned.
			*/
 
			void face_insert_point(FaceIter f, VertexIter v);
			/**< Insert a new vertex, v, in a face, f.
				 This operation splits an N-gon into N triangles.
				 In the current implementation the original face is erased. 
				 This means that the iterator is not valid after the function
				 returns. 
			*/
 
			bool merge_faces(FaceIter f, HalfEdgeIter h);
			/**< 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 flip(HalfEdgeIter h);
			/**< Flip an edge h. Returns false if flipping cannot be performed.
				 This is either because one of the two adjacent faces is not
				 a triangle, or because either end point has valency three or
				 because the vertices that will be connected already are. */
 
			void get_bbox(CGLA::Vec3f& pmin, CGLA::Vec3f& pmax);
			/**< Return the bounding box of the manifold. The arguments pmin and pmax
				 will contain the extreme corners of the box when the function 
				 returns.	*/
 
			void get_bsphere(CGLA::Vec3f& c, float& r);
			/**< Get a bounding sphere. When the function returns, c contains the
				 centre and r the radius. */ 
		};
			
 
	inline HalfEdgeIter Manifold::halfedges_begin() 
		{
			return halfedge_db.begin();
		}
	
	inline HalfEdgeIter Manifold::halfedges_end() 
		{
			return halfedge_db.end(); 
		}
 
	inline VertexIter Manifold::vertices_begin() 
		{
			return vertex_db.begin();
		}
 
	inline VertexIter Manifold::vertices_end()
		{
			return vertex_db.end(); 
		}
 
	inline FaceIter Manifold::faces_begin()
		{
			return face_db.begin();	
		}
 
	inline FaceIter Manifold::faces_end() 
		{ 
			return face_db.end(); 
		}
 
	inline VertexIter Manifold::create_vertex(const CGLA::Vec3f& pos)
		{
			vertex_db.push_back(Vertex(pos));
			return --vertex_db.end();
		}
 
	inline FaceIter Manifold::create_face()
		{
			face_db.push_back(Face());
			return --face_db.end();
		}
 
	inline HalfEdgeIter Manifold::create_halfedge()
		{
			halfedge_db.push_back(HalfEdge());
			return --halfedge_db.end();
		}
 
	inline void Manifold::delayed_erase()
		{
			erase_immediately = false;
		}
 
	inline void Manifold::immediate_erase()
		{
			erase_immediately = true;
			remove_unused();
		}
 
	inline bool Manifold::is_used(VertexIter v) const
		{
			if(v->he == NULL_HALFEDGE_ITER)
				return false;
			return true;
		}
 
	inline bool Manifold::is_used(FaceIter f) const
		{
			if(f->last == NULL_HALFEDGE_ITER)
				return false;
			return true;
		}
 
	inline bool Manifold::is_used(HalfEdgeIter h) const
		{
			if(h->vert == NULL_VERTEX_ITER)
				return false;
			return true;
		}
 
 
}
#endif
 
Subversion Repositories gelsvn

(root)/trunk/src/HMesh/Manifold.h – Rev 336 → 448
