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


#ifndef __MANIFOLD_H
#define __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. */
 
	struct Manifold
	{
		std::list<Vertex> vertex_db;
		std::list<Face> face_db;
		std::list<HalfEdge> halfedge_db;
 
		/** Remove a face if it contains only two edges.
 
		This is an auxiliary function called from collapse_halfedge. */
		void remove_face_if_degenerate(HalfEdgeIter fi);
 
		/** 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.		*/
		Manifold(const Manifold& m2) {}
 
		/** Empty assignment operator.
				
		The assignment operator is private for the same reason that the
				copy constructor is private. */
		const Manifold& operator=(const Manifold& m2) {}
 
		public:
	
		/// Construct an empty manifold.
		Manifold() {}
 
		/// Return the bounding box of the manifold.
		void get_bbox(CGLA::Vec3f&, CGLA::Vec3f&);
 
		/// Get a bounding sphere
    void get_bsphere(CGLA::Vec3f& c, float& r);
 
		/// Clear the manifold - removing all data.
		void clear()
		{
			vertex_db.clear();
			face_db.clear();
			halfedge_db.clear();
		}
 
		/// Return the number of faces.
		int no_faces() const {return face_db.size();}
 
		/// Return the number of halfedges.
		int no_halfedges() const {return halfedge_db.size();}
 
		/// Return the number of vertices
		int no_vertices() const {return vertex_db.size();}
 
		/// Create a new vertex at a given position.
		VertexIter create_vertex(const CGLA::Vec3f& pos)
		{
			vertex_db.push_back(Vertex(pos));
			return --vertex_db.end();
		}
 
		/// Create a new face 
		FaceIter create_face()
		{
			face_db.push_back(Face());
			return --face_db.end();
		}
 
		/// Create a new halfedge.
		HalfEdgeIter create_halfedge()
		{
			halfedge_db.push_back(HalfEdge());
			return --halfedge_db.end();
		}
 
		/// Erase halfedge. Assumes it is safe to do so. Use with care.
		void erase_halfedge(HalfEdgeIter he)
		{
			halfedge_db.erase(he);
		}
 
		/// Erase vertex. Assumes it is safe to do so. Use with care.
		void erase_vertex(VertexIter v)
		{
			vertex_db.erase(v);
		}
	
		/// Erase face. Assumes it is safe to do so. Use with care.
		void erase_face(FaceIter f)
		{
			face_db.erase(f);
		}
 
		/// Return iterator pointing to the first halfedge.
		HalfEdgeIter halfedges_begin() { return halfedge_db.begin();}
 
		/// Return iterator pointing to beyond the last halfedge.
		HalfEdgeIter halfedges_end() { return halfedge_db.end(); }
	
		/// Return iterator pointing to the first vertex.
		VertexIter vertices_begin() { return vertex_db.begin();}
 
		/// Return iterator pointing to beyond the last vertex.
		VertexIter vertices_end() { return vertex_db.end(); }
 
		/// Return iterator pointing to the first face.
		FaceIter faces_begin() { return face_db.begin();	}
 
		/// Return iterator pointing to beyond the last face.
		FaceIter faces_end() { return face_db.end(); }
 
		/** HalfEdge collapse precondition. 
				If this function does not return true, it is illegal to collapse
				the halfedge given as second arg. The reason is that the collapse
				would violate the manifold property of the mesh. */
		bool collapse_precond(VertexIter, HalfEdgeIter);
		
		/** Collapse the halfedge given as second argument. The first argument
				is the vertex that is being removed. This function is not guaranteed
				to keep the mesh sane unless, collapse_precond has returned true. */
		void collapse_halfedge(VertexIter, HalfEdgeIter, bool=false);
 
		/** Split a face (first argument) by connecting two vertices (the
				next two arguments). */
		FaceIter split_face(FaceIter, VertexIter, VertexIter);
 
		/** Insert a new vertex on the halfedge given as argument. */
		VertexIter Manifold::split_edge(HalfEdgeIter h);
 
		/** Triangulate a polygonal face by repeatedly calling splitface. */
		void triangulate(FaceIter);
 
		/** Triangulate a polygon by inserting a vertex at the barycenter and 
				connecting all vertices to this vertex. */
		VertexIter safe_triangulate(FaceIter f);
 
		/** Insert a new vertex (second arg.) in a face (first arg.).
				This operation splits an N-gon into N triangles. */
		void face_insert_point(FaceIter f, VertexIter);
 
		/** Merges two faces into a single polygon. The first face is the first
				argument. The second face is adjacent to the first along the
				halfedge given as second argument. */
		bool merge_faces(FaceIter f, HalfEdgeIter h);
 
		/** flips an edge. 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. */
		bool flip(HalfEdgeIter);
 
		/** 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. */
		bool is_valid();
 
		/** Give each vertex a unique id corresponding to its iterator 
				position */
		void enumerate_vertices();
 
		/** Give each halfedge a unique id corresponding to its iterator 
				position */
		void enumerate_halfedges();
 
		/** Give each face a unique id corresponding to its iterator 
				position */
		void enumerate_faces();
		
	};
 
 
}
#endif
 

Subversion Repositories gelsvn

(root)/trunk/src/HMesh/Manifold.h – Rev 39 → 89

Rev 39		Rev 89
1	`#ifndef __MANIFOLD_H`	1	`#ifndef __MANIFOLD_H`
2	`#define __MANIFOLD_H`	2	`#define __MANIFOLD_H`
3		3
4	`#include <vector>`	4	`#include <vector>`
5	`#include <list>`	5	`#include <list>`
6	`#include <map>`	6	`#include <map>`
7		7
8	`#include "Vertex.h"`	8	`#include "Vertex.h"`
9	`#include "HalfEdge.h"`	9	`#include "HalfEdge.h"`
10	`#include "Face.h"`	10	`#include "Face.h"`
11		11
12		-
13		-
14	`namespace HMesh`	12	`namespace HMesh`
15	`{`	13	`{`
16	`class VertexCirculator;`	14	`class VertexCirculator;`
17	`class FaceCirculator;`	15	`class FaceCirculator;`
18		16
19	`/** A Data structure representing an open or closed manifold.`	17	`/** \brief A Data structure representing an open or closed manifold.`
-		18
20	`Manifold keeps lists of the entities making up a halfedge mesh`	19	`Manifold keeps lists of the entities making up a halfedge mesh`
21	`and provides basic functions for creating new faces, halfedges`	20	`and provides basic functions for creating new faces, halfedges`
22	`and vertices. There are also primitive operations for editing`	21	`and vertices. There are also primitive operations for editing`
23	`such as edge collapse. */`	22	`such as edge collapse. */`
24		-
25	`struct Manifold`	23	`struct Manifold`
26	`{`	24	`{`
27	`std::list<Vertex> vertex_db;`	25	`std::list<Vertex> vertex_db;`
28	`std::list<Face> face_db;`	26	`std::list<Face> face_db;`
29	`std::list<HalfEdge> halfedge_db;`	27	`std::list<HalfEdge> halfedge_db;`
30		28
31	`/** Remove a face if it contains only two edges. This is an auxiliary`	29	`/** Remove a face if it contains only two edges.`
-		30
32	`function called from collapse_halfedge. */`	31	`This is an auxiliary function called from collapse_halfedge. */`
33	`void remove_face_if_degenerate(HalfEdgeIter fi);`	32	`void remove_face_if_degenerate(HalfEdgeIter fi);`
34		33
-		34	`/** Empty copy constructor.`
-		35
35	`/** Copying a manifold will not work, since faces, vertices, and`	36	`Copying a manifold will not work, since faces, vertices, and`
36	`halfedges contain iterators pointing to other faces, vertices,`	37	`halfedges contain iterators pointing to other faces, vertices,`
37	`and halfedges. These pointers would need to be changed if the`	38	`and halfedges. These pointers would need to be changed if the`
38	`mesh were copied. In other words, we would need to walk the`	39	`mesh were copied. In other words, we would need to walk the`
39	`entire mesh. This may be required but it should not be an`	40	`entire mesh. This may be required but it should not be an`
40	`operation that is easily invoked by calling the copy constructor.`	41	`operation that is easily invoked by calling the copy constructor.`
41	`Hence, this operator is made private. */`	42	`Hence, this operator is made private. */`
42	`Manifold(const Manifold& m2) {}`	43	`Manifold(const Manifold& m2) {}`
43		44
-		45	`/** Empty assignment operator.`
-		46
44	`/** The assignment operator is private for the same reason that the`	47	`The assignment operator is private for the same reason that the`
45	`copy constructor is private. */`	48	`copy constructor is private. */`
46	`const Manifold& operator=(const Manifold& m2) {}`	49	`const Manifold& operator=(const Manifold& m2) {}`
47		50
48	`public:`	51	`public:`
49		52
50	`/// Construct an empty manifold.`	53	`/// Construct an empty manifold.`
51	`Manifold() {}`	54	`Manifold() {}`
52		55
53	`/// Return the bounding box of the manifold.`	56	`/// Return the bounding box of the manifold.`
54	`void get_bbox(CGLA::Vec3f&, CGLA::Vec3f&);`	57	`void get_bbox(CGLA::Vec3f&, CGLA::Vec3f&);`
55		58
56	`/// Get a bounding sphere`	59	`/// Get a bounding sphere`
57	`void get_bsphere(CGLA::Vec3f& c, float& r);`	60	`void get_bsphere(CGLA::Vec3f& c, float& r);`
58		61
59	`/// Clear the manifold - removing all data.`	62	`/// Clear the manifold - removing all data.`
60	`void clear()`	63	`void clear()`
61	`{`	64	`{`
62	`vertex_db.clear();`	65	`vertex_db.clear();`
63	`face_db.clear();`	66	`face_db.clear();`
64	`halfedge_db.clear();`	67	`halfedge_db.clear();`
65	`}`	68	`}`
66		69
67	`/// Return the number of faces.`	70	`/// Return the number of faces.`
68	`int no_faces() const {return face_db.size();}`	71	`int no_faces() const {return face_db.size();}`
69		72
70	`/// Return the number of halfedges.`	73	`/// Return the number of halfedges.`
71	`int no_halfedges() const {return halfedge_db.size();}`	74	`int no_halfedges() const {return halfedge_db.size();}`
72		75
73	`/// Return the number of vertices`	76	`/// Return the number of vertices`
74	`int no_vertices() const {return vertex_db.size();}`	77	`int no_vertices() const {return vertex_db.size();}`
75		78
76	`/// Create a new vertex at a given position.`	79	`/// Create a new vertex at a given position.`
77	`VertexIter create_vertex(const CGLA::Vec3f& pos)`	80	`VertexIter create_vertex(const CGLA::Vec3f& pos)`
78	`{`	81	`{`
79	`vertex_db.push_back(Vertex(pos));`	82	`vertex_db.push_back(Vertex(pos));`
80	`return --vertex_db.end();`	83	`return --vertex_db.end();`
81	`}`	84	`}`
82		85
83	`/// Create a new face`	86	`/// Create a new face`
84	`FaceIter create_face()`	87	`FaceIter create_face()`
85	`{`	88	`{`
86	`face_db.push_back(Face());`	89	`face_db.push_back(Face());`
87	`return --face_db.end();`	90	`return --face_db.end();`
88	`}`	91	`}`
89		92
90	`/// Create a new halfedge.`	93	`/// Create a new halfedge.`
91	`HalfEdgeIter create_halfedge()`	94	`HalfEdgeIter create_halfedge()`
92	`{`	95	`{`
93	`halfedge_db.push_back(HalfEdge());`	96	`halfedge_db.push_back(HalfEdge());`
94	`return --halfedge_db.end();`	97	`return --halfedge_db.end();`
95	`}`	98	`}`
96		99
97	`/// Erase halfedge. Assumes it is safe to do so. Use with care.`	100	`/// Erase halfedge. Assumes it is safe to do so. Use with care.`
98	`void erase_halfedge(HalfEdgeIter he)`	101	`void erase_halfedge(HalfEdgeIter he)`
99	`{`	102	`{`
100	`halfedge_db.erase(he);`	103	`halfedge_db.erase(he);`
101	`}`	104	`}`
102		105
103	`/// Erase vertex. Assumes it is safe to do so. Use with care.`	106	`/// Erase vertex. Assumes it is safe to do so. Use with care.`
104	`void erase_vertex(VertexIter v)`	107	`void erase_vertex(VertexIter v)`
105	`{`	108	`{`
106	`vertex_db.erase(v);`	109	`vertex_db.erase(v);`
107	`}`	110	`}`
108		111
109	`/// Erase face. Assumes it is safe to do so. Use with care.`	112	`/// Erase face. Assumes it is safe to do so. Use with care.`
110	`void erase_face(FaceIter f)`	113	`void erase_face(FaceIter f)`
111	`{`	114	`{`
112	`face_db.erase(f);`	115	`face_db.erase(f);`
113	`}`	116	`}`
114		117
115	`/// Return iterator pointing to the first halfedge.`	118	`/// Return iterator pointing to the first halfedge.`
116	`HalfEdgeIter halfedges_begin() { return halfedge_db.begin();}`	119	`HalfEdgeIter halfedges_begin() { return halfedge_db.begin();}`
117		120
118	`/// Return iterator pointing to beyond the last halfedge.`	121	`/// Return iterator pointing to beyond the last halfedge.`
119	`HalfEdgeIter halfedges_end() { return halfedge_db.end(); }`	122	`HalfEdgeIter halfedges_end() { return halfedge_db.end(); }`
120		123
121	`/// Return iterator pointing to the first vertex.`	124	`/// Return iterator pointing to the first vertex.`
122	`VertexIter vertices_begin() { return vertex_db.begin();}`	125	`VertexIter vertices_begin() { return vertex_db.begin();}`
123		126
124	`/// Return iterator pointing to beyond the last vertex.`	127	`/// Return iterator pointing to beyond the last vertex.`
125	`VertexIter vertices_end() { return vertex_db.end(); }`	128	`VertexIter vertices_end() { return vertex_db.end(); }`
126		129
127	`/// Return iterator pointing to the first face.`	130	`/// Return iterator pointing to the first face.`
128	`FaceIter faces_begin() { return face_db.begin(); }`	131	`FaceIter faces_begin() { return face_db.begin(); }`
129		132
130	`/// Return iterator pointing to beyond the last face.`	133	`/// Return iterator pointing to beyond the last face.`
131	`FaceIter faces_end() { return face_db.end(); }`	134	`FaceIter faces_end() { return face_db.end(); }`
132		135
133	`/** HalfEdge collapse precondition.`	136	`/** HalfEdge collapse precondition.`
134	`If this function does not return true, it is illegal to collapse`	137	`If this function does not return true, it is illegal to collapse`
135	`the halfedge given as second arg. The reason is that the collapse`	138	`the halfedge given as second arg. The reason is that the collapse`
136	`would violate the manifold property of the mesh. */`	139	`would violate the manifold property of the mesh. */`
137	`bool collapse_precond(VertexIter, HalfEdgeIter);`	140	`bool collapse_precond(VertexIter, HalfEdgeIter);`
138		141
139	`/** Collapse the halfedge given as second argument. The first argument`	142	`/** Collapse the halfedge given as second argument. The first argument`
140	`is the vertex that is being removed. This function is not guaranteed`	143	`is the vertex that is being removed. This function is not guaranteed`
141	`to keep the mesh sane unless, collapse_precond has returned true. */`	144	`to keep the mesh sane unless, collapse_precond has returned true. */`
142	`void collapse_halfedge(VertexIter, HalfEdgeIter, bool=false);`	145	`void collapse_halfedge(VertexIter, HalfEdgeIter, bool=false);`
143		146
144	`/** Split a face (first argument) by connecting two vertices (the`	147	`/** Split a face (first argument) by connecting two vertices (the`
145	`next two arguments). */`	148	`next two arguments). */`
146	`FaceIter split_face(FaceIter, VertexIter, VertexIter);`	149	`FaceIter split_face(FaceIter, VertexIter, VertexIter);`
147		150
148	`/** Insert a new vertex on the halfedge given as argument. */`	151	`/** Insert a new vertex on the halfedge given as argument. */`
149	`VertexIter Manifold::split_edge(HalfEdgeIter h);`	152	`VertexIter Manifold::split_edge(HalfEdgeIter h);`
150		153
151	`/** Triangulate a polygonal face by repeatedly calling splitface. */`	154	`/** Triangulate a polygonal face by repeatedly calling splitface. */`
152	`void triangulate(FaceIter);`	155	`void triangulate(FaceIter);`
153		156
154	`/** Triangulate a polygon by inserting a vertex at the barycenter and`	157	`/** Triangulate a polygon by inserting a vertex at the barycenter and`
155	`connecting all vertices to this vertex. */`	158	`connecting all vertices to this vertex. */`
156	`VertexIter safe_triangulate(FaceIter f);`	159	`VertexIter safe_triangulate(FaceIter f);`
157		160
158	`/** Insert a new vertex (second arg.) in a face (first arg.).`	161	`/** Insert a new vertex (second arg.) in a face (first arg.).`
159	`This operation splits an N-gon into N triangles. */`	162	`This operation splits an N-gon into N triangles. */`
160	`void face_insert_point(FaceIter f, VertexIter);`	163	`void face_insert_point(FaceIter f, VertexIter);`
161		164
162	`/** Merges two faces into a single polygon. The first face is the first`	165	`/** Merges two faces into a single polygon. The first face is the first`
163	`argument. The second face is adjacent to the first along the`	166	`argument. The second face is adjacent to the first along the`
164	`halfedge given as second argument. */`	167	`halfedge given as second argument. */`
165	`bool merge_faces(FaceIter f, HalfEdgeIter h);`	168	`bool merge_faces(FaceIter f, HalfEdgeIter h);`
166		169
167	`/** flips an edge. Returns false if flipping cannot be performed.`	170	`/** flips an edge. Returns false if flipping cannot be performed.`
168	`This is either because one of the two adjacent faces is not`	171	`This is either because one of the two adjacent faces is not`
169	`a triangle, or because either end point has valency three or`	172	`a triangle, or because either end point has valency three or`
170	`because the vertices that will be connected already are. */`	173	`because the vertices that will be connected already are. */`
171	`bool flip(HalfEdgeIter);`	174	`bool flip(HalfEdgeIter);`
172		175
173	`/** Performs a series of tests to check that this is a valid manifold.`	176	`/** Performs a series of tests to check that this is a valid manifold.`
174	`This function is not rigorously constructed but seems to catch`	177	`This function is not rigorously constructed but seems to catch`
175	`all problems so far. */`	178	`all problems so far. */`
176	`bool is_valid();`	179	`bool is_valid();`
177		180
178	`/** Give each vertex a unique id corresponding to its iterator`	181	`/** Give each vertex a unique id corresponding to its iterator`
179	`position */`	182	`position */`
180	`void enumerate_vertices();`	183	`void enumerate_vertices();`
181		184
182	`/** Give each halfedge a unique id corresponding to its iterator`	185	`/** Give each halfedge a unique id corresponding to its iterator`
183	`position */`	186	`position */`
184	`void enumerate_halfedges();`	187	`void enumerate_halfedges();`
185		188
186	`/** Give each face a unique id corresponding to its iterator`	189	`/** Give each face a unique id corresponding to its iterator`
187	`position */`	190	`position */`
188	`void enumerate_faces();`	191	`void enumerate_faces();`
189		192
190	`};`	193	`};`
191		194
192		195
193	`}`	196	`}`
194	`#endif`	197	`#endif`
195		198