Subversion Repositories gelsvn

Rev

Rev 158 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 158 Rev 159
Line 33... Line 33...
33 
 
 33 
 
34 
			/** Remove a face if it contains only two edges.
 34 
			/** Remove a face if it contains only two edges.
35 
					This is an auxiliary function called from collapse_halfedge. */
 35 
					This is an auxiliary function called from collapse_halfedge. */
36 
			void remove_face_if_degenerate(HalfEdgeIter);
 36 
			void remove_face_if_degenerate(HalfEdgeIter);
37 
 
 37 
 
38 
			/** Empty copy constructor.
 - 
 
39 
					Copying a manifold will not work, since faces, vertices, and
 - 
 
40 
					halfedges contain iterators pointing to other faces, vertices,
 - 
 
41 
					and halfedges. These pointers would need to be changed if the
- 
 
42 
					mesh were copied. In other words, we would need to walk the
 - 
 
43 
					entire mesh. This may be required but it should not be an
- 
 
44 
					operation that is easily invoked by calling the copy constructor.
 - 
 
45 
					Hence, this operator is made private.		*/
 - 
 
46 
			Manifold(const Manifold&) {}
 38 
			Manifold(const Manifold&) {}
- 
 
 39 
			/**< Empty copy constructor.
- 
 
 40 
				 Copying a manifold will not work, since faces, vertices, and
- 
 
 41 
				 halfedges contain iterators pointing to other faces, vertices,
- 
 
 42 
				 and halfedges. These pointers would need to be changed if the
- 
 
 43 
				 mesh were copied. In other words, we would need to walk the
- 
 
 44 
				 entire mesh. This may be required but it should not be an
- 
 
 45 
				 operation that is easily invoked by calling the copy constructor.
- 
 
 46 
				 Hence, this operator is made private.		*/
47 
 
 47 
 
48 
			/** Empty assignment operator.
 - 
 
49 
					The assignment operator is private for the same reason that the
 - 
 
50 
					copy constructor is private. */
 - 
 
51 
			const Manifold& operator=(const Manifold&) {return *this;}
 48 
			const Manifold& operator=(const Manifold&) {return *this;}
- 
 
 49 
			/**< Empty assignment operator.
- 
 
 50 
				 The assignment operator is private for the same reason that the
- 
 
 51 
				 copy constructor is private. */
52 
 
 52 
 
53 
		public:
 53 
		public:
54 
 
 54 
 
55 
			/// Construct an empty manifold.
 - 
 
- 
 
 55 
 
56 
			Manifold(): erase_immediately(true) {}
 56 
			Manifold(): erase_immediately(true) {}
- 
 
 57 
			///< Construct an empty manifold.
57 
 
 58 
 
- 
 
 59 
			bool is_valid();
58 
			/** Return the bounding box of the manifold. The arguments pmin and pmax
 60 
			/**< Performs a series of tests to check that this is a valid manifold.
59 
					will contain the extreme corners of the box when the function
61 
				 This function is not rigorously constructed but seems to catch
60 
					returns.	*/
 62 
				 all problems so far. The function returns true if the mesh is
61 
			void get_bbox(CGLA::Vec3f& pmin, CGLA::Vec3f& pmax);
 63 
				 valid and false otherwise.	*/
62 
 
 64 
 
- 
 
 65 
			void enumerate_vertices();
63 
			/** Get a bounding sphere. When the function returns c contains the
 66 
			/**< Give each vertex a unique id corresponding to its iterator
- 
 
 67 
				 position */
- 
 
 68 
 
64 
					centre and r the radius. */
69 
			void enumerate_halfedges();
- 
 
 70 
			/**< Give each halfedge a unique id corresponding to its iterator
- 
 
 71 
				 position */
- 
 
 72 
 
65 
			void get_bsphere(CGLA::Vec3f& c, float& r);
 73 
			void enumerate_faces();
- 
 
 74 
			/**< Give each face a unique id corresponding to its iterator
- 
 
 75 
				 position */
66 
 
 76 
 
67 
			/// Return the number of faces.
 - 
 
68 
			size_t no_faces() const {return face_db.size();}
 77 
			size_t no_faces() const {return face_db.size();}
- 
 
 78 
			///< Return the number of faces.
69 
 
 79 
 
70 
			/// Return the number of halfedges.
 - 
 
71 
			size_t no_halfedges() const {return halfedge_db.size();}
 80 
			size_t no_halfedges() const {return halfedge_db.size();}
- 
 
 81 
			///< Return the number of halfedges.
72 
 
 82 
 
73 
			/// Return the number of vertices
 - 
 
74 
			size_t no_vertices() const {return vertex_db.size();}
 83 
			size_t no_vertices() const {return vertex_db.size();}
- 
 
 84 
			///< Return the number of vertices
75 
 
 85 
 
76 
			/** Create a new vertex.
 - 
 
77 
					The argument is the position of the vertex, and the
- 
 
78 
					function returns an iterator pointing to the vertex.
 - 
 
79 
					When a vertex v is initially created, is_used(v) will
 - 
 
80 
					return false.
 - 
 
81 
			*/
 - 
 
82 
			VertexIter create_vertex(const CGLA::Vec3f& pos)
 86 
			VertexIter create_vertex(const CGLA::Vec3f& pos);
83 
				{
 - 
 
84 
					vertex_db.push_back(Vertex(pos));
 - 
 
85 
					return --vertex_db.end();
 87 
			///< Create a new vertex.
86 
				}
 - 
 
87 
 
 88 
 
- 
 
 89 
			FaceIter create_face();
88 
			/** Create a new face.
 90 
			/**< Create a new face.
89 
					An iterator to the face is returned. When a face f is initially
 91 
				 An iterator to the face is returned. When a face f is initially
90 
					created, is_used(f) will return false. */
 92 
				 created, is_used(f) will return false. */
91 
			FaceIter create_face()
 - 
 
92 
				{
 - 
 
93 
					face_db.push_back(Face());
 - 
 
94 
					return --face_db.end();
 - 
 
95 
				}
 - 
 
96 
 
 93 
 
- 
 
 94 
			HalfEdgeIter create_halfedge();
97 
			/** Create a new halfedge. An iterator to the halfedge is returned.
 95 
			/**< Create a new halfedge. An iterator to the halfedge is returned.
98 
					When h is initially created, is_used(h) returns false. */
 96 
				 When h is initially created, is_used(h) returns false. */
99 
			HalfEdgeIter create_halfedge()
 - 
 
100 
				{
 - 
 
101 
					halfedge_db.push_back(HalfEdge());
 - 
 
102 
					return --halfedge_db.end();
 - 
 
103 
				}
 - 
 
104 
 
 97 
 
105 
			/// Clear the manifold - removing all data.
 - 
 
106 
			void clear();
 98 
			void clear();
- 
 
 99 
			///< Clear the manifold, removing all data.
107 
 
 100 
 
108 
			/** Remove unused vertices, edges and faces from the database.
 - 
 
109 
					If delayed_erase mode is enabled, then until this function
- 
 
110 
					has been called, erased vertices, edges, and faces are just marked
 - 
 
111 
					as unused but not removed from their respective lists. */
 - 
 
112 
			void remove_unused();
 101 
			void remove_unused();
113 
 
 - 
 
- 
 
 102 
			/**< Remove unused vertices, edges and faces from the database.
- 
 
 103 
				 If delayed_erase mode is enabled, then until this function
- 
 
 104 
				 has been called, erased vertices, edges, and faces are just marked
- 
 
 105 
				 as unused but not removed from their respective lists. */
114 
 
 106 
 
- 
 
 107 
			void delayed_erase();
115 
			/** Delay the actual removal of vertices, faces, and edges that
 108 
			/**< Delay the actual removal of vertices, faces, and edges that
116 
					are erased.  In many cases, it is a problem if one cannot
 109 
				 are erased.  In many cases, it is a problem if one cannot
117 
					test whether a vertex, halfedge, or face indicated by an
 110 
				 test whether a vertex, halfedge, or face indicated by an
118 
					iterator is in use or has been removed from the mesh. One
 111 
				 iterator is in use or has been removed from the mesh. One
119 
					solution to this problem is to delay the actual removal of
 112 
				 solution to this problem is to delay the actual removal of
120 
					the vertex, edge or face. Instead when calling, say,
 113 
				 the vertex, edge or face. Instead when calling, say,
121 
					erase_face(f), all the iterators of f are assigned the
 114 
				 erase_face(f), all the iterators of f are assigned the
122 
					appropriate NULL value to indicate that they are not
 115 
				 appropriate NULL value to indicate that they are not
123 
					pointing at anything, and f is added to a vector of faces
 116 
				 pointing at anything, and f is added to a vector of faces
124 
					that need to be physically removed from the face_db.
 117 
				 that need to be physically removed from the face_db.
125 
 
 118 
 
126 
					Since f is not erased, all iterators pointing at f remain
 119 
				 Since f is not erased, all iterators pointing at f remain
127 
					valid! And, importantly, it is possible to test whether f is
 120 
				 valid! And, importantly, it is possible to test whether f is
128 
					in use by calling is_used(f).
 121 
				 in use by calling is_used(f).
129 
 
 122 
 
130 
					When remove_unused is called, the physical removal takes
 123 
				 When remove_unused is called, the physical removal takes
131 
					place. Calling immediate_erase switches Manifold back to the
 124 
				 place. Calling immediate_erase switches Manifold back to the
132 
					state where entities are removed as soon as the appropriate
 125 
				 state where entities are removed as soon as the appropriate
133 
					erase function is called, and at the same time calls
 126 
				 erase function is called, and at the same time calls
134 
					remove_unused.
 127 
				 remove_unused.
135 
			*/
 128 
			*/
136 
			void delayed_erase()
 - 
 
137 
				{
 - 
 
138 
					erase_immediately = false;
 - 
 
139 
				}
 - 
 
140 
 
 129 
 
- 
 
 130 
			void immediate_erase();
141 
			/** Immediately remove erased entities.
 131 
			/**< Immediately remove erased entities.
142 
					Calling immediate_erase switches Manifold back to the state
 132 
				 Calling immediate_erase switches Manifold back to the state
143 
					where entities are removed as soon as the appropriate erase
 133 
				 where entities are removed as soon as the appropriate erase
144 
					function is called.
 134 
				 function is called.
145 
 
 135 
 
146 
					See delayed_erase for more details, and note that
 136 
				 See delayed_erase for more details, and note that
147 
					immediate_erase is the default mode.  */
 137 
				 immediate_erase is the default mode.  */
148 
			void immediate_erase()
 - 
 
149 
				{
 - 
 
150 
					erase_immediately = true;
 - 
 
151 
					remove_unused();
 - 
 
152 
				}
 - 
 
153 
 
 138 
 
- 
 
 139 
			bool is_used(VertexIter v) const;
154 
			/** Test whether the vertex indicated by the argument v is used.
 140 
			/**< Test whether the vertex indicated by the argument v is used.
155 
					This function returns true if the vertex appears to have a
141 
				 This function returns true if the vertex appears to have a
156 
					valid outgoing halfedge iterator. */
 142 
				 valid outgoing halfedge iterator. */
157 
			bool is_used(VertexIter v) const
 - 
 
158 
				{
 - 
 
159 
					if(v->he == NULL_HALFEDGE_ITER)
 - 
 
160 
						return false;
 - 
 
161 
					return true;
 - 
 
162 
				}
 - 
 
163 
 
 143 
 
- 
 
 144 
			bool is_used(FaceIter f) const;
164 
			/** Test whether the face indicated by the argument f is used.
 145 
			/**< Test whether the face indicated by the argument f is used.
165 
					This function returns true if the face appears to have a
146 
				 This function returns true if the face appears to have a
166 
					valid halfedge iterator. */
 147 
				 valid halfedge iterator. */
167 
			bool is_used(FaceIter f) const
 - 
 
168 
				{
 - 
 
169 
					if(f->last == NULL_HALFEDGE_ITER)
 - 
 
170 
						return false;
 - 
 
171 
					return true;
 - 
 
172 
				}
 - 
 
173 
 
 148 
 
- 
 
 149 
			bool is_used(HalfEdgeIter h) const;
174 
			/** Test whether the halfedge indicated by the argument h is used.
 150 
			/**< Test whether the halfedge indicated by the argument h is used.
175 
					This function returns true if the halfedge appears to have a
151 
				 This function returns true if the halfedge appears to have a
176 
					valid vertex iterator. */
 152 
				 valid vertex iterator. */
177 
			bool is_used(HalfEdgeIter h) const
 - 
 
178 
				{
 - 
 
179 
					if(h->vert == NULL_VERTEX_ITER)
 - 
 
180 
						return false;
 - 
 
181 
					return true;
 - 
 
182 
				}
 - 
 
183 
 
 153 
 
- 
 
 154 
			void erase_halfedge(HalfEdgeIter h);
184 
			/** Erase halfedge h.
155 
			/**< Erase halfedge h.
185 
					In general, you should never call this function but use the
156 
				 In general, you should never call this function but use the
186 
					collapse_halfedge function instead since blindly erasing geometry
 157 
				 collapse_halfedge function instead since blindly erasing geometry
187 
					is most likely to invalidate the Mesh. Quite possibly this function
 158 
				 is most likely to invalidate the Mesh. Quite possibly this function
188 
					will be removed from the public interface.
159 
				 will be removed from the public interface.
189
160
190 
					Note that if delayed_erase has been called, this function does
 161 
				 Note that if delayed_erase has been called, this function does
191 
					not immediately remove anything from the mesh. Instead the halfedge
 162 
				 not immediately remove anything from the mesh. Instead the halfedge
192 
					is reset to its initial state. Thus, iterators are not invalidated,
 163 
				 is reset to its initial state. Thus, iterators are not invalidated,
193 
					and it is possible to test whether h is used calling:
 164 
				 and it is possible to test whether h is used calling:
194 
					is_used(h). when remove_unused is called, the actual removal
 165 
				 is_used(h). when remove_unused is called, the actual removal
195 
					takes place.
 166 
				 takes place.
196 
			*/
 167 
			*/
197 
			void erase_halfedge(HalfEdgeIter h);
 - 
 
198 
 
 168 
 
199 
			/** Erase vertex v.
 - 
 
200 
					In general, you should never call this function but use the
- 
 
201 
					collapse_halfedge function to collapse the vertex away.
 - 
 
202 
					Blindly erasing is extremely likely to invalidate the
 - 
 
203 
					Mesh. Quite possibly this function will be removed from the
 - 
 
204 
					public interface.
- 
 
205 
 
 - 
 
206 
					Note that if delayed_erase has been called, this function does
 - 
 
207 
					not immediately remove anything from the mesh. Instead the halfedge
 - 
 
208 
					is reset to its initial state. Thus, iterators are not invalidated,
 - 
 
209 
					and it is possible to test whether v is used calling:
 - 
 
210 
					is_used(v). when remove_unused is called, the actual removal
 - 
 
211 
					takes place.
 - 
 
212 
			*/
 - 
 
213 
			void erase_vertex(VertexIter v);
 169 
			void erase_vertex(VertexIter v);
- 
 
 170 
			/**< Erase vertex v.
- 
 
 171 
				 In general, you should never call this function but use the
- 
 
 172 
				 collapse_halfedge function to collapse the vertex away.
- 
 
 173 
				 Blindly erasing is extremely likely to invalidate the
- 
 
 174 
				 Mesh. Quite possibly this function will be removed from the
- 
 
 175 
				 public interface.
- 
 
 176 
 
- 
 
 177 
				 Note that if delayed_erase has been called, this function does
- 
 
 178 
				 not immediately remove anything from the mesh. Instead the halfedge
- 
 
 179 
				 is reset to its initial state. Thus, iterators are not invalidated,
- 
 
 180 
				 and it is possible to test whether v is used calling:
- 
 
 181 
				 is_used(v). when remove_unused is called, the actual removal
- 
 
 182 
				 takes place.
- 
 
 183 
			*/
214 
 
 184 
 
215 
 
 185 
 
216 
			/** Erase face f.
 - 
 
217 
					In general, you should never call this function but use
- 
 
218 
					collapse_halfedge in conjunction with other functions to
 - 
 
219 
					remove the face through (Euler) operations which preserve
 - 
 
220 
					the mesh in a valid state.
 - 
 
221 
					Blindly erasing is extremely likely to invalidate the
 - 
 
222 
					Mesh. Quite possibly this function will be removed from the
 - 
 
223 
					public interface.
- 
 
224 
 
 - 
 
225 
					Note that if delayed_erase has been called, this function does
 - 
 
226 
					not immediately remove anything from the mesh. Instead the face
 - 
 
227 
					is reset to its initial state. Thus, iterators are not invalidated,
 - 
 
228 
					and it is possible to test whether f is used calling:
 - 
 
229 
					is_used(f). when remove_unused is called, the actual removal
 - 
 
230 
					takes place.
 - 
 
231 
			*/
 - 
 
232 
			void erase_face(FaceIter f);
 186 
			void erase_face(FaceIter f);
- 
 
 187 
			/**< Erase face f.
- 
 
 188 
				 In general, you should never call this function but use
- 
 
 189 
				 collapse_halfedge in conjunction with other functions to
- 
 
 190 
				 remove the face through (Euler) operations which preserve
- 
 
 191 
				 the mesh in a valid state.
- 
 
 192 
				 Blindly erasing is extremely likely to invalidate the
- 
 
 193 
				 Mesh. Quite possibly this function will be removed from the
- 
 
 194 
				 public interface.
- 
 
 195 
 
- 
 
 196 
				 Note that if delayed_erase has been called, this function does
- 
 
 197 
				 not immediately remove anything from the mesh. Instead the face
- 
 
 198 
				 is reset to its initial state. Thus, iterators are not invalidated,
- 
 
 199 
				 and it is possible to test whether f is used calling:
- 
 
 200 
				 is_used(f). when remove_unused is called, the actual removal
- 
 
 201 
				 takes place.
- 
 
 202 
			*/
233 
 
 203 
 
- 
 
 204 
			HalfEdgeIter halfedges_begin();
234 
			/// Return iterator pointing to the first halfedge.
 205 
			///< Return iterator pointing to the first halfedge.
235 
			HalfEdgeIter halfedges_begin() { return halfedge_db.begin();}
 - 
 
236 
 
 206 
 
- 
 
 207 
			HalfEdgeIter halfedges_end();
237 
			/// Return iterator pointing to beyond the last halfedge.
 208 
			///< Return iterator pointing to beyond the last halfedge.
238 
			HalfEdgeIter halfedges_end() { return halfedge_db.end(); }
 - 
 
239 
 
 209 
 
240 
			/// Return iterator pointing to the first vertex.
 210 
			VertexIter vertices_begin();
241 
			VertexIter vertices_begin() { return vertex_db.begin();}
 211 
			///< Return iterator pointing to the first vertex.
242 
 
 212 
 
- 
 
 213 
			VertexIter vertices_end();
243 
			/// Return iterator pointing to beyond the last vertex.
 214 
			///< Return iterator pointing to beyond the last vertex.
244 
			VertexIter vertices_end() { return vertex_db.end(); }
 - 
 
245 
 
 215 
 
- 
 
 216 
			FaceIter faces_begin();
246 
			/// Return iterator pointing to the first face.
 217 
			///< Return iterator pointing to the first face.
247 
			FaceIter faces_begin() { return face_db.begin();	}
 - 
 
248 
 
 218 
 
- 
 
 219 
			FaceIter faces_end();
249 
			/// Return iterator pointing to beyond the last face.
 220 
			///< Return iterator pointing to beyond the last face.
250 
			FaceIter faces_end() { return face_db.end(); }
 - 
 
251 
 
 221 
 
- 
 
 222 
			bool collapse_precond(HalfEdgeIter h);
252 
			/** \brief HalfEdge collapse precondition.
 223 
			/**< \brief HalfEdge collapse precondition.
253 
 
 224 
 
254 
			The argument h is the halfedge we want to collapse.
225 
			The argument h is the halfedge we want to collapse.
255 
 
 226 
 
256 
			If this function does not return true, it is illegal to collapse
 227 
			If this function does not return true, it is illegal to collapse
257 
			h. The reason is that the collapse would violate the manifold property
 228 
			h. The reason is that the collapse would violate the manifold property
Line 293... Line 264...
293 
			6. PREVENT MERGING HOLES:
 264 
			6. PREVENT MERGING HOLES:
294 
			We do not want to collapse an edge if its end points are boundary
 265 
			We do not want to collapse an edge if its end points are boundary
295 
			vertices, but its two adjacent faces are not NULL faces, because
 266 
			vertices, but its two adjacent faces are not NULL faces, because
296 
			in that case we create a vertex where two holes meet. A non manifold
 267 
			in that case we create a vertex where two holes meet. A non manifold
297 
			situation.	*/
 268 
			situation.	*/
298 
			bool collapse_precond(HalfEdgeIter h);
 - 
 
299 
 
 269 
 
- 
 
 270 
 
- 
 
 271 
			void collapse_halfedge(HalfEdgeIter h, bool=false);
300 
			/** Collapse the halfedge h.
 272 
			/**< Collapse the halfedge h.
301 
 
 273 
 
302 
			The argument h is the halfedge being removed. The vertex
274 
			The argument h is the halfedge being removed. The vertex
303 
			v=h->opp->vert is the one being removed while h->vert survives.
 275 
			v=h->opp->vert is the one being removed while h->vert survives.
304 
 
 276 
 
305 
			The final argument is a boolean indicating whether the vertex
 277 
			The final argument is a boolean indicating whether the vertex
Line 309... Line 281...
309 
			position.
 281 
			position.
310 
 
 282 
 
311 
			This function is not guaranteed to keep the mesh sane unless,
 283 
			This function is not guaranteed to keep the mesh sane unless,
312 
			collapse_precond has returned true !!
 284 
			collapse_precond has returned true !!
313 
			*/
 285 
			*/
314 
			void collapse_halfedge(HalfEdgeIter h, bool=false);
 - 
 
315 
 
 286 
 
316 
			/** Split a face.
 - 
 
317 
					The face, f, is split by connecting two
 - 
 
318 
					vertices v0 and v1 (the next two arguments). The vertices of
 - 
 
319 
					the old face between v0 and v1 (in counter clockwise order)
- 
 
320 
					continue to belong to f. The vertices between v1 and
- 
 
321 
					v0 belong to the new face. An iterator to the new face is
- 
 
322 
					returned. */
 - 
 
323 
			FaceIter split_face(FaceIter f, VertexIter v0, VertexIter v1);
 287 
			FaceIter split_face(FaceIter f, VertexIter v0, VertexIter v1);
- 
 
 288 
			/**< Split a face.
- 
 
 289 
				 The face, f, is split by connecting two
- 
 
 290 
				 vertices v0 and v1 (the next two arguments). The vertices of
- 
 
 291 
				 the old face between v0 and v1 (in counter clockwise order)
- 
 
 292 
				 continue to belong to f. The vertices between v1 and
- 
 
 293 
				 v0 belong to the new face. An iterator to the new face is
- 
 
 294 
				 returned. */
- 
 
 295 
 
- 
 
 296 
			VertexIter split_edge(HalfEdgeIter h);
- 
 
 297 
			/**< Insert a new vertex on halfedge h.
- 
 
 298 
				 The new halfedge is insterted as the previous edge to h.
- 
 
 299 
				 An iterator to the inserted vertex is	returned. */
324 
 
 300 
 
325 
			/** Insert a new vertex on halfedge h.
 - 
 
326 
					The new halfedge is insterted as the previous edge to h.
 - 
 
327 
					An iterator to the inserted vertex is	returned. */
 - 
 
328 
			VertexIter Manifold::split_edge(HalfEdgeIter h);
 - 
 
329 
 
 - 
 
330 
			/** Triangulate a polygonal face by repeatedly calling split_face.
 - 
 
331 
					Triangulate iteratively splits triangles off a polygon. The first
- 
 
332 
					triangle split off is the one connecting f->last->vert and
 - 
 
333 
					f->last->next->next->vert.
 - 
 
334 
			*/
 - 
 
335 
			void triangulate(FaceIter f);
 301 
			void triangulate(FaceIter f);
336 
 
 - 
 
337 
			/** Triangulate a polygon, f, by inserting a vertex at the barycenter.
 302 
			/**< Triangulate a polygonal face by repeatedly calling split_face.
338 
					All vertices in f are connected to the new vertex.
- 
 
339 
					The word "safe" means that it is less likely to create flipped
 - 
 
340 
					triangles than the normal triangulate. On the other hand, it
303 
				 Triangulate iteratively splits triangles off a polygon. The first
341 
					introduces more vertices and probably makes the triangles more
 - 
 
342 
					acute. This function simply calls face_insert_point.
 304 
				 triangle split off is the one connecting f->last->vert and
343 
 
 - 
 
344 
					The inserted vertex is returned.
 305 
				 f->last->next->next->vert.
345 
			*/
 306 
			*/
- 
 
 307 
 
346 
			VertexIter safe_triangulate(FaceIter f);
 308 
			VertexIter safe_triangulate(FaceIter f);
- 
 
 309 
			/**< Triangulate a polygon, f, by inserting a vertex at the barycenter.
- 
 
 310 
				 All vertices in f are connected to the new vertex.
- 
 
 311 
				 The word "safe" means that it is less likely to create flipped
- 
 
 312 
				 triangles than the normal triangulate. On the other hand, it
- 
 
 313 
				 introduces more vertices and probably makes the triangles more
- 
 
 314 
				 acute. This function simply calls face_insert_point.
347 
 
 315 
 
348 
			/** Insert a new vertex, v, in a face, f.
 316 
				 The inserted vertex is returned.
349 
					This operation splits an N-gon into N triangles.
 - 
 
350 
					In the current implementation the original face is erased.
- 
 
351 
					This means that the iterator is not valid after the function
 - 
 
352 
					returns.
- 
 
353 
			*/
 317 
			*/
- 
 
 318 
 
354 
			void face_insert_point(FaceIter f, VertexIter v);
 319 
			void face_insert_point(FaceIter f, VertexIter v);
- 
 
 320 
			/**< Insert a new vertex, v, in a face, f.
- 
 
 321 
				 This operation splits an N-gon into N triangles.
- 
 
 322 
				 In the current implementation the original face is erased.
- 
 
 323 
				 This means that the iterator is not valid after the function
- 
 
 324 
				 returns.
- 
 
 325 
			*/
355 
 
 326 
 
356 
			/** Merges two faces into a single polygon. The first face is f.  The
 - 
 
357 
					second face is adjacent to f along the halfedge h. This function
 - 
 
358 
					returns true if the merging was possible and false
 - 
 
359 
					otherwise. Currently merge only fails if the mesh is already
 - 
 
360 
					illegal. Thus it should, in fact, never fail. */
 - 
 
361 
			bool merge_faces(FaceIter f, HalfEdgeIter h);
 327 
			bool merge_faces(FaceIter f, HalfEdgeIter h);
- 
 
 328 
			/**< Merges two faces into a single polygon. The first face is f.  The
- 
 
 329 
				 second face is adjacent to f along the halfedge h. This function
- 
 
 330 
				 returns true if the merging was possible and false
- 
 
 331 
				 otherwise. Currently merge only fails if the mesh is already
- 
 
 332 
				 illegal. Thus it should, in fact, never fail. */
362 
 
 333 
 
363 
			/** Flip an edge h. Returns false if flipping cannot be performed.
 - 
 
364 
					This is either because one of the two adjacent faces is not
 - 
 
365 
					a triangle, or because either end point has valency three or
 - 
 
366 
					because the vertices that will be connected already are. */
 - 
 
367 
			bool flip(HalfEdgeIter h);
 334 
			bool flip(HalfEdgeIter h);
- 
 
 335 
			/**< Flip an edge h. Returns false if flipping cannot be performed.
- 
 
 336 
				 This is either because one of the two adjacent faces is not
- 
 
 337 
				 a triangle, or because either end point has valency three or
- 
 
 338 
				 because the vertices that will be connected already are. */
368 
 
 339 
 
369 
			/** Performs a series of tests to check that this is a valid manifold.
 - 
 
370 
					This function is not rigorously constructed but seems to catch
 - 
 
371 
					all problems so far. The function returns true if the mesh is
340 
			void get_bbox(CGLA::Vec3f& pmin, CGLA::Vec3f& pmax);
372 
					valid and false otherwise.
 - 
 
373 
			*/
 - 
 
374 
			bool is_valid();
 - 
 
375 
 
 - 
 
376 
			/** Give each vertex a unique id corresponding to its iterator
 - 
 
377 
					position */
 - 
 
378 
			void enumerate_vertices();
 - 
 
379 
 
 - 
 
380 
			/** Give each halfedge a unique id corresponding to its iterator
 341 
			/**< Return the bounding box of the manifold. The arguments pmin and pmax
381 
					position */
 - 
 
382 
			void enumerate_halfedges();
 - 
 
383 
 
 - 
 
384 
			/** Give each face a unique id corresponding to its iterator
 342 
				 will contain the extreme corners of the box when the function
385 
					position */
 343 
				 returns.	*/
386 
			void enumerate_faces();
 - 
 
387 
 
 344 
 
- 
 
 345 
			void get_bsphere(CGLA::Vec3f& c, float& r);
- 
 
 346 
			/**< Get a bounding sphere. When the function returns, c contains the
- 
 
 347 
				 centre and r the radius. */
388 
		};
 348 
		};
- 
 
 349
- 
 
 350 
 
- 
 
 351 
	inline HalfEdgeIter Manifold::halfedges_begin()
- 
 
 352 
		{
- 
 
 353 
			return halfedge_db.begin();
- 
 
 354 
		}
- 
 
 355
- 
 
 356 
	inline HalfEdgeIter Manifold::halfedges_end()
- 
 
 357 
		{
- 
 
 358 
			return halfedge_db.end();
- 
 
 359 
		}
- 
 
 360 
 
- 
 
 361 
	inline VertexIter Manifold::vertices_begin()
- 
 
 362 
		{
- 
 
 363 
			return vertex_db.begin();
- 
 
 364 
		}
- 
 
 365 
 
- 
 
 366 
	inline VertexIter Manifold::vertices_end()
- 
 
 367 
		{
- 
 
 368 
			return vertex_db.end();
- 
 
 369 
		}
- 
 
 370 
 
- 
 
 371 
	inline FaceIter Manifold::faces_begin()
- 
 
 372 
		{
- 
 
 373 
			return face_db.begin();
- 
 
 374 
		}
- 
 
 375 
 
- 
 
 376 
	inline FaceIter Manifold::faces_end()
- 
 
 377 
		{
- 
 
 378 
			return face_db.end();
- 
 
 379 
		}
- 
 
 380 
 
- 
 
 381 
	inline VertexIter Manifold::create_vertex(const CGLA::Vec3f& pos)
- 
 
 382 
		{
- 
 
 383 
			vertex_db.push_back(Vertex(pos));
- 
 
 384 
			return --vertex_db.end();
- 
 
 385 
		}
- 
 
 386 
 
- 
 
 387 
	inline FaceIter Manifold::create_face()
- 
 
 388 
		{
- 
 
 389 
			face_db.push_back(Face());
- 
 
 390 
			return --face_db.end();
- 
 
 391 
		}
- 
 
 392 
 
- 
 
 393 
	inline HalfEdgeIter Manifold::create_halfedge()
- 
 
 394 
		{
- 
 
 395 
			halfedge_db.push_back(HalfEdge());
- 
 
 396 
			return --halfedge_db.end();
- 
 
 397 
		}
- 
 
 398 
 
- 
 
 399 
	inline void Manifold::delayed_erase()
- 
 
 400 
		{
- 
 
 401 
			erase_immediately = false;
- 
 
 402 
		}
- 
 
 403 
 
- 
 
 404 
	inline void Manifold::immediate_erase()
- 
 
 405 
		{
- 
 
 406 
			erase_immediately = true;
- 
 
 407 
			remove_unused();
- 
 
 408 
		}
- 
 
 409 
 
- 
 
 410 
	inline bool Manifold::is_used(VertexIter v) const
- 
 
 411 
		{
- 
 
 412 
			if(v->he == NULL_HALFEDGE_ITER)
- 
 
 413 
				return false;
- 
 
 414 
			return true;
- 
 
 415 
		}
- 
 
 416 
 
- 
 
 417 
	inline bool Manifold::is_used(FaceIter f) const
- 
 
 418 
		{
- 
 
 419 
			if(f->last == NULL_HALFEDGE_ITER)
- 
 
 420 
				return false;
- 
 
 421 
			return true;
- 
 
 422 
		}
- 
 
 423 
 
- 
 
 424 
	inline bool Manifold::is_used(HalfEdgeIter h) const
- 
 
 425 
		{
- 
 
 426 
			if(h->vert == NULL_VERTEX_ITER)
- 
 
 427 
				return false;
- 
 
 428 
			return true;
- 
 
 429 
		}
389 
 
 430 
 
390 
 
 431 
 
391 
}
 432 
}
392 
#endif
 433 
#endif