Subversion Repositories gelsvn

Rev

Rev 89 | Rev 133 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 89 Rev 113
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
namespace HMesh
12
namespace HMesh
13
{
13
{
14
	class VertexCirculator;
14
	class VertexCirculator;
15
	class FaceCirculator;
15
	class FaceCirculator;
16
 
16
 
17
	/** \brief A Data structure representing an open or closed manifold.
17
	/** \brief A Data structure representing an open or closed manifold.
18
 
18
 
19
			Manifold keeps lists of the entities making up a halfedge mesh
19
			Manifold keeps lists of the entities making up a halfedge mesh
20
			and provides basic functions for creating new faces, halfedges
20
			and provides basic functions for creating new faces, halfedges
21
			and vertices. There are also primitive operations for editing 
21
			and vertices. There are also primitive operations for editing 
22
			such as edge collapse. */
22
			such as edge collapse. */
23
	struct Manifold
23
	struct Manifold
24
	{
24
	{
25
		std::list<Vertex> vertex_db;
25
		std::list<Vertex> vertex_db;
26
		std::list<Face> face_db;
26
		std::list<Face> face_db;
27
		std::list<HalfEdge> halfedge_db;
27
		std::list<HalfEdge> halfedge_db;
28
 
28
 
29
		/** Remove a face if it contains only two edges.
29
		/** Remove a face if it contains only two edges.
30
 
30
 
31
		This is an auxiliary function called from collapse_halfedge. */
31
		This is an auxiliary function called from collapse_halfedge. */
32
		void remove_face_if_degenerate(HalfEdgeIter fi);
32
		void remove_face_if_degenerate(HalfEdgeIter fi);
33
 
33
 
34
		/** Empty copy constructor.
34
		/** Empty copy constructor.
35
				
35
				
36
		Copying a manifold will not work, since faces, vertices, and
36
		Copying a manifold will not work, since faces, vertices, and
37
				halfedges contain iterators pointing to other faces, vertices,
37
				halfedges contain iterators pointing to other faces, vertices,
38
				and halfedges. These pointers would need to be changed if the 
38
				and halfedges. These pointers would need to be changed if the 
39
				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
40
				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 
41
				operation that is easily invoked by calling the copy constructor.
41
				operation that is easily invoked by calling the copy constructor.
42
				Hence, this operator is made private.		*/
42
				Hence, this operator is made private.		*/
43
		Manifold(const Manifold& m2) {}
43
		Manifold(const Manifold& m2) {}
44
 
44
 
45
		/** Empty assignment operator.
45
		/** Empty assignment operator.
46
				
46
				
47
		The assignment operator is private for the same reason that the
47
		The assignment operator is private for the same reason that the
48
				copy constructor is private. */
48
				copy constructor is private. */
49
		const Manifold& operator=(const Manifold& m2) {}
49
		const Manifold& operator=(const Manifold& m2) {}
50
 
50
 
51
		public:
51
		public:
52
	
52
	
53
		/// Construct an empty manifold.
53
		/// Construct an empty manifold.
54
		Manifold() {}
54
		Manifold() {}
55
 
55
 
56
		/// Return the bounding box of the manifold.
56
		/// Return the bounding box of the manifold.
57
		void get_bbox(CGLA::Vec3f&, CGLA::Vec3f&);
57
		void get_bbox(CGLA::Vec3f&, CGLA::Vec3f&);
58
 
58
 
59
		/// Get a bounding sphere
59
		/// Get a bounding sphere
60
    void get_bsphere(CGLA::Vec3f& c, float& r);
60
    void get_bsphere(CGLA::Vec3f& c, float& r);
61
 
61
 
62
		/// Clear the manifold - removing all data.
62
		/// Clear the manifold - removing all data.
63
		void clear()
63
		void clear()
64
		{
64
		{
65
			vertex_db.clear();
65
			vertex_db.clear();
66
			face_db.clear();
66
			face_db.clear();
67
			halfedge_db.clear();
67
			halfedge_db.clear();
68
		}
68
		}
69
 
69
 
70
		/// Return the number of faces.
70
		/// Return the number of faces.
71
		int no_faces() const {return face_db.size();}
71
		int no_faces() const {return face_db.size();}
72
 
72
 
73
		/// Return the number of halfedges.
73
		/// Return the number of halfedges.
74
		int no_halfedges() const {return halfedge_db.size();}
74
		int no_halfedges() const {return halfedge_db.size();}
75
 
75
 
76
		/// Return the number of vertices
76
		/// Return the number of vertices
77
		int no_vertices() const {return vertex_db.size();}
77
		int no_vertices() const {return vertex_db.size();}
78
 
78
 
79
		/// Create a new vertex at a given position.
79
		/// Create a new vertex at a given position.
80
		VertexIter create_vertex(const CGLA::Vec3f& pos)
80
		VertexIter create_vertex(const CGLA::Vec3f& pos)
81
		{
81
		{
82
			vertex_db.push_back(Vertex(pos));
82
			vertex_db.push_back(Vertex(pos));
83
			return --vertex_db.end();
83
			return --vertex_db.end();
84
		}
84
		}
85
 
85
 
86
		/// Create a new face 
86
		/// Create a new face 
87
		FaceIter create_face()
87
		FaceIter create_face()
88
		{
88
		{
89
			face_db.push_back(Face());
89
			face_db.push_back(Face());
90
			return --face_db.end();
90
			return --face_db.end();
91
		}
91
		}
92
 
92
 
93
		/// Create a new halfedge.
93
		/// Create a new halfedge.
94
		HalfEdgeIter create_halfedge()
94
		HalfEdgeIter create_halfedge()
95
		{
95
		{
96
			halfedge_db.push_back(HalfEdge());
96
			halfedge_db.push_back(HalfEdge());
97
			return --halfedge_db.end();
97
			return --halfedge_db.end();
98
		}
98
		}
99
 
99
 
100
		/// 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.
101
		void erase_halfedge(HalfEdgeIter he)
101
		void erase_halfedge(HalfEdgeIter he)
102
		{
102
		{
103
			halfedge_db.erase(he);
103
			halfedge_db.erase(he);
104
		}
104
		}
105
 
105
 
106
		/// 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.
107
		void erase_vertex(VertexIter v)
107
		void erase_vertex(VertexIter v)
108
		{
108
		{
109
			vertex_db.erase(v);
109
			vertex_db.erase(v);
110
		}
110
		}
111
	
111
	
112
		/// 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.
113
		void erase_face(FaceIter f)
113
		void erase_face(FaceIter f)
114
		{
114
		{
115
			face_db.erase(f);
115
			face_db.erase(f);
116
		}
116
		}
117
 
117
 
118
		/// Return iterator pointing to the first halfedge.
118
		/// Return iterator pointing to the first halfedge.
119
		HalfEdgeIter halfedges_begin() { return halfedge_db.begin();}
119
		HalfEdgeIter halfedges_begin() { return halfedge_db.begin();}
120
 
120
 
121
		/// Return iterator pointing to beyond the last halfedge.
121
		/// Return iterator pointing to beyond the last halfedge.
122
		HalfEdgeIter halfedges_end() { return halfedge_db.end(); }
122
		HalfEdgeIter halfedges_end() { return halfedge_db.end(); }
123
	
123
	
124
		/// Return iterator pointing to the first vertex.
124
		/// Return iterator pointing to the first vertex.
125
		VertexIter vertices_begin() { return vertex_db.begin();}
125
		VertexIter vertices_begin() { return vertex_db.begin();}
126
 
126
 
127
		/// Return iterator pointing to beyond the last vertex.
127
		/// Return iterator pointing to beyond the last vertex.
128
		VertexIter vertices_end() { return vertex_db.end(); }
128
		VertexIter vertices_end() { return vertex_db.end(); }
129
 
129
 
130
		/// Return iterator pointing to the first face.
130
		/// Return iterator pointing to the first face.
131
		FaceIter faces_begin() { return face_db.begin();	}
131
		FaceIter faces_begin() { return face_db.begin();	}
132
 
132
 
133
		/// Return iterator pointing to beyond the last face.
133
		/// Return iterator pointing to beyond the last face.
134
		FaceIter faces_end() { return face_db.end(); }
134
		FaceIter faces_end() { return face_db.end(); }
135
 
135
 
136
		/** HalfEdge collapse precondition. 
136
		/** \brief HalfEdge collapse precondition. 
-
 
137
 
137
				If this function does not return true, it is illegal to collapse
138
				If this function does not return true, it is illegal to collapse
138
				the halfedge given as second arg. The reason is that the collapse
139
				the halfedge given as second arg. The reason is that the collapse
139
				would violate the manifold property of the mesh. */
140
				would violate the manifold property of the mesh.
-
 
141
 
-
 
142
				The test is as follows.
-
 
143
 
-
 
144
				1. For the two vertices adjacent to the edge, we generate
-
 
145
				a list of all their neighbouring vertices. We then generate a 
-
 
146
				list of the vertices that occur in both these lists. That is, 
-
 
147
				we find all vertices connected by edges to both endpoints
-
 
148
				of the edge and store these in a list.
-
 
149
 
-
 
150
				2. For both faces incident on the edge, check whether they
-
 
151
				are triangular. If this is the case, the face will be removed,
-
 
152
				and it is ok that the the third vertex is connected to both 
-
 
153
				endpoints. Thus the third vertex in such a face is removed
-
 
154
				from the list generated in 1.
-
 
155
 
-
 
156
				3. If the list is now empty, all is well. Otherwise, there
-
 
157
				would be a vertex in the new mesh with two edges connecting
-
 
158
				it to the same vertex. Return false.
-
 
159
 
-
 
160
				4. TETRAHEDRON TEST:
-
 
161
				If the valency of both vertices is 
-
 
162
				three, and the incident faces are triangles, we also disallow
-
 
163
				the operation. Reason: It introduces a vertex of valency two
-
 
164
				and if the final two polygons incident on the vertices 
-
 
165
				that are adjacent to the edge being collapsed are triangles, then
-
 
166
				the construction will collapse
-
 
167
 
-
 
168
				5. VALENCY 4 TEST:
-
 
169
				If a face adjacent to the edge being collapsed is a triangle,
-
 
170
				it will disappear, and the valency of the final vertex beloning to
-
 
171
				this edge will be reduced by one. Hence this valency should be at
-
 
172
				least 4. A valency three vertex will be reduced to a valency two
-
 
173
				vertex which is considered illegal.
-
 
174
 
-
 
175
				6. PREVENT MERGING HOLES:
-
 
176
				We do not want to collapse an edge if its end points are boundary
-
 
177
				vertices, but its two adjacent faces are not NULL faces, because
-
 
178
				in that case we create a vertex where two holes meet. A non manifold
-
 
179
				situation.	*/
140
		bool collapse_precond(VertexIter, HalfEdgeIter);
180
		bool collapse_precond(VertexIter, HalfEdgeIter);
141
		
181
		
142
		/** Collapse the halfedge given as second argument. The first argument
182
		/** Collapse the halfedge given as second argument. 
-
 
183
 
-
 
184
		The first argument
143
				is the vertex that is being removed. This function is not guaranteed
185
				is the vertex that is being removed. The second is a halfedge pointing
-
 
186
				away from that vertex. This function is not guaranteed
144
				to keep the mesh sane unless, collapse_precond has returned true. */
187
				to keep the mesh sane unless, collapse_precond has returned true. */
145
		void collapse_halfedge(VertexIter, HalfEdgeIter, bool=false);
188
		void collapse_halfedge(VertexIter, HalfEdgeIter, bool=false);
146
 
189
 
147
		/** Split a face (first argument) by connecting two vertices (the
190
		/** Split a face (first argument) by connecting two vertices (the
148
				next two arguments). */
191
				next two arguments). */
149
		FaceIter split_face(FaceIter, VertexIter, VertexIter);
192
		FaceIter split_face(FaceIter, VertexIter, VertexIter);
150
 
193
 
151
		/** Insert a new vertex on the halfedge given as argument. */
194
		/** Insert a new vertex on the halfedge given as argument. */
152
		VertexIter Manifold::split_edge(HalfEdgeIter h);
195
		VertexIter Manifold::split_edge(HalfEdgeIter h);
153
 
196
 
154
		/** Triangulate a polygonal face by repeatedly calling splitface. */
197
		/** Triangulate a polygonal face by repeatedly calling splitface. */
155
		void triangulate(FaceIter);
198
		void triangulate(FaceIter);
156
 
199
 
157
		/** Triangulate a polygon by inserting a vertex at the barycenter and 
200
		/** Triangulate a polygon by inserting a vertex at the barycenter and 
158
				connecting all vertices to this vertex. */
201
				connecting all vertices to this vertex. */
159
		VertexIter safe_triangulate(FaceIter f);
202
		VertexIter safe_triangulate(FaceIter f);
160
 
203
 
161
		/** Insert a new vertex (second arg.) in a face (first arg.).
204
		/** Insert a new vertex (second arg.) in a face (first arg.).
162
				This operation splits an N-gon into N triangles. */
205
				This operation splits an N-gon into N triangles. */
163
		void face_insert_point(FaceIter f, VertexIter);
206
		void face_insert_point(FaceIter f, VertexIter);
164
 
207
 
165
		/** Merges two faces into a single polygon. The first face is the first
208
		/** Merges two faces into a single polygon. The first face is the first
166
				argument. The second face is adjacent to the first along the
209
				argument. The second face is adjacent to the first along the
167
				halfedge given as second argument. */
210
				halfedge given as second argument. */
168
		bool merge_faces(FaceIter f, HalfEdgeIter h);
211
		bool merge_faces(FaceIter f, HalfEdgeIter h);
169
 
212
 
170
		/** flips an edge. Returns false if flipping cannot be performed.
213
		/** flips an edge. Returns false if flipping cannot be performed.
171
				This is either because one of the two adjacent faces is not
214
				This is either because one of the two adjacent faces is not
172
				a triangle, or because either end point has valency three or
215
				a triangle, or because either end point has valency three or
173
				because the vertices that will be connected already are. */
216
				because the vertices that will be connected already are. */
174
		bool flip(HalfEdgeIter);
217
		bool flip(HalfEdgeIter);
175
 
218
 
176
		/** Performs a series of tests to check that this is a valid manifold.
219
		/** Performs a series of tests to check that this is a valid manifold.
177
				This function is not rigorously constructed but seems to catch
220
				This function is not rigorously constructed but seems to catch
178
				all problems so far. */
221
				all problems so far. */
179
		bool is_valid();
222
		bool is_valid();
180
 
223
 
181
		/** Give each vertex a unique id corresponding to its iterator 
224
		/** Give each vertex a unique id corresponding to its iterator 
182
				position */
225
				position */
183
		void enumerate_vertices();
226
		void enumerate_vertices();
184
 
227
 
185
		/** Give each halfedge a unique id corresponding to its iterator 
228
		/** Give each halfedge a unique id corresponding to its iterator 
186
				position */
229
				position */
187
		void enumerate_halfedges();
230
		void enumerate_halfedges();
188
 
231
 
189
		/** Give each face a unique id corresponding to its iterator 
232
		/** Give each face a unique id corresponding to its iterator 
190
				position */
233
				position */
191
		void enumerate_faces();
234
		void enumerate_faces();
192
		
235
		
193
	};
236
	};
194
 
237
 
195
 
238
 
196
}
239
}
197
#endif
240
#endif
198
 
241