WebSVN – gelsvn – Diff – /branches/restructuring/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);
 
		/** 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&) {}
 
		/** Empty assignment operator.
				The assignment operator is private for the same reason that the
				copy constructor is private. */
		const Manifold& operator=(const Manifold&) {return *this;}
 
		public:
	
		/// Construct an empty manifold.
		Manifold() {}
 
  	/** 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_bbox(CGLA::Vec3f& pmin, CGLA::Vec3f& pmax);
 
		/** Get a bounding sphere. When the function returns c contains the 
				centre and r the radius. */ 
    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.
		size_t no_faces() const {return face_db.size();}
 
		/// Return the number of halfedges.
		size_t no_halfedges() const {return halfedge_db.size();}
 
		/// Return the number of vertices
		size_t no_vertices() const {return vertex_db.size();}
 
		/** Create a new vertex. 
				The argument is the position of the vertex, and the 
				function returns an iterator pointing to the vertex. */
		VertexIter create_vertex(const CGLA::Vec3f& pos)
		{
			vertex_db.push_back(Vertex(pos));
			return --vertex_db.end();
		}
 
		/** Create a new face. 
				An iterator to the face is returned. */
		FaceIter create_face()
		{
			face_db.push_back(Face());
			return --face_db.end();
		}
 
  	/** Create a new halfedge. An iterator to the halfedge is returned. */
		HalfEdgeIter create_halfedge()
		{
			halfedge_db.push_back(HalfEdge());
			return --halfedge_db.end();
		}
 
		/// Erase halfedge h. Assumes it is safe to do so. Use with care.
		void erase_halfedge(HalfEdgeIter h)
		{
			halfedge_db.erase(h);
		}
 
		/// Erase vertex v. Assumes it is safe to do so. Use with care.
		void erase_vertex(VertexIter v)
		{
			vertex_db.erase(v);
		}
	
		/// Erase face f. 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(); }
 
		/** \brief HalfEdge collapse precondition. 
 
				The first argument, v, is the vertex we want to remove. The
				second, h, is a halfedge pointing away from that vertex.
 
				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.	*/
		bool collapse_precond(VertexIter v, HalfEdgeIter h);
		
		/** Collapse the halfedge h.
 
				The first argument, v, is the vertex that is being removed. The
				second, h, is a halfedge pointing away from that vertex.
 
				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.
 
				This function is not guaranteed to keep the mesh sane unless,
				collapse_precond has returned true.
		*/
		void collapse_halfedge(VertexIter v, HalfEdgeIter h, bool=false);
 
		/** 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. */
		FaceIter split_face(FaceIter f, VertexIter v0, VertexIter v1);
 
		/** 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. */
		VertexIter Manifold::split_edge(HalfEdgeIter h);
 
		/** 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.
		*/
		void 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.
		*/
		VertexIter safe_triangulate(FaceIter f);
 
		/** 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. 
		*/
		void face_insert_point(FaceIter f, VertexIter v);
 
		/** 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(FaceIter f, 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. */
		bool flip(HalfEdgeIter h);
 
		/** 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 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)/branches/restructuring/src/HMesh/Manifold.h – Rev 136 → 145

Rev 136		Rev 145
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	`Manifold keeps lists of the entities making up a halfedge mesh`	18	`Manifold keeps lists of the entities making up a halfedge mesh`
19	`and provides basic functions for creating new faces, halfedges`	19	`and provides basic functions for creating new faces, halfedges`
20	`and vertices. There are also primitive operations for editing`	20	`and vertices. There are also primitive operations for editing`
21	`such as edge collapse. */`	21	`such as edge collapse. */`
22	`struct Manifold`	22	`struct Manifold`
23	`{`	23	`{`
24	`std::list<Vertex> vertex_db;`	24	`std::list<Vertex> vertex_db;`
25	`std::list<Face> face_db;`	25	`std::list<Face> face_db;`
26	`std::list<HalfEdge> halfedge_db;`	26	`std::list<HalfEdge> halfedge_db;`
27		27
28	`/** Remove a face if it contains only two edges.`	28	`/** Remove a face if it contains only two edges.`
29	`This is an auxiliary function called from collapse_halfedge. */`	29	`This is an auxiliary function called from collapse_halfedge. */`
30	`void remove_face_if_degenerate(HalfEdgeIter);`	30	`void remove_face_if_degenerate(HalfEdgeIter);`
31		31
32	`/** Empty copy constructor.`	32	`/** Empty copy constructor.`
33	`Copying a manifold will not work, since faces, vertices, and`	33	`Copying a manifold will not work, since faces, vertices, and`
34	`halfedges contain iterators pointing to other faces, vertices,`	34	`halfedges contain iterators pointing to other faces, vertices,`
35	`and halfedges. These pointers would need to be changed if the`	35	`and halfedges. These pointers would need to be changed if the`
36	`mesh were copied. In other words, we would need to walk the`	36	`mesh were copied. In other words, we would need to walk the`
37	`entire mesh. This may be required but it should not be an`	37	`entire mesh. This may be required but it should not be an`
38	`operation that is easily invoked by calling the copy constructor.`	38	`operation that is easily invoked by calling the copy constructor.`
39	`Hence, this operator is made private. */`	39	`Hence, this operator is made private. */`
40	`Manifold(const Manifold&) {}`	40	`Manifold(const Manifold&) {}`
41		41
42	`/** Empty assignment operator.`	42	`/** Empty assignment operator.`
43	`The assignment operator is private for the same reason that the`	43	`The assignment operator is private for the same reason that the`
44	`copy constructor is private. */`	44	`copy constructor is private. */`
45	`const Manifold& operator=(const Manifold&) {return *this;}`	45	`const Manifold& operator=(const Manifold&) {return *this;}`
46		46
47	`public:`	47	`public:`
48		48
49	`/// Construct an empty manifold.`	49	`/// Construct an empty manifold.`
50	`Manifold() {}`	50	`Manifold() {}`
51		51
52	`/** Return the bounding box of the manifold. The arguments pmin and pmax`	52	`/** Return the bounding box of the manifold. The arguments pmin and pmax`
53	`will contain the extreme corners of the box when the function returns.`	53	`will contain the extreme corners of the box when the function returns.`
54	`*/`	54	`*/`
55	`void get_bbox(CGLA::Vec3f& pmin, CGLA::Vec3f& pmax);`	55	`void get_bbox(CGLA::Vec3f& pmin, CGLA::Vec3f& pmax);`
56		56
57	`/** Get a bounding sphere. When the function returns c contains the`	57	`/** Get a bounding sphere. When the function returns c contains the`
58	`centre and r the radius. */`	58	`centre and r the radius. */`
59	`void get_bsphere(CGLA::Vec3f& c, float& r);`	59	`void get_bsphere(CGLA::Vec3f& c, float& r);`
60		60
61	`/// Clear the manifold - removing all data.`	61	`/// Clear the manifold - removing all data.`
62	`void clear()`	62	`void clear()`
63	`{`	63	`{`
64	`vertex_db.clear();`	64	`vertex_db.clear();`
65	`face_db.clear();`	65	`face_db.clear();`
66	`halfedge_db.clear();`	66	`halfedge_db.clear();`
67	`}`	67	`}`
68		68
69	`/// Return the number of faces.`	69	`/// Return the number of faces.`
70	`size_t no_faces() const {return face_db.size();}`	70	`size_t no_faces() const {return face_db.size();}`
71		71
72	`/// Return the number of halfedges.`	72	`/// Return the number of halfedges.`
73	`size_t no_halfedges() const {return halfedge_db.size();}`	73	`size_t no_halfedges() const {return halfedge_db.size();}`
74		74
75	`/// Return the number of vertices`	75	`/// Return the number of vertices`
76	`size_t no_vertices() const {return vertex_db.size();}`	76	`size_t no_vertices() const {return vertex_db.size();}`
77		77
78	`/** Create a new vertex.`	78	`/** Create a new vertex.`
79	`The argument is the position of the vertex, and the`	79	`The argument is the position of the vertex, and the`
80	`function returns an iterator pointing to the vertex. */`	80	`function returns an iterator pointing to the vertex. */`
81	`VertexIter create_vertex(const CGLA::Vec3f& pos)`	81	`VertexIter create_vertex(const CGLA::Vec3f& pos)`
82	`{`	82	`{`
83	`vertex_db.push_back(Vertex(pos));`	83	`vertex_db.push_back(Vertex(pos));`
84	`return --vertex_db.end();`	84	`return --vertex_db.end();`
85	`}`	85	`}`
86		86
87	`/** Create a new face.`	87	`/** Create a new face.`
88	`An iterator to the face is returned. */`	88	`An iterator to the face is returned. */`
89	`FaceIter create_face()`	89	`FaceIter create_face()`
90	`{`	90	`{`
91	`face_db.push_back(Face());`	91	`face_db.push_back(Face());`
92	`return --face_db.end();`	92	`return --face_db.end();`
93	`}`	93	`}`
94		94
95	`/** Create a new halfedge. An iterator to the halfedge is returned. */`	95	`/** Create a new halfedge. An iterator to the halfedge is returned. */`
96	`HalfEdgeIter create_halfedge()`	96	`HalfEdgeIter create_halfedge()`
97	`{`	97	`{`
98	`halfedge_db.push_back(HalfEdge());`	98	`halfedge_db.push_back(HalfEdge());`
99	`return --halfedge_db.end();`	99	`return --halfedge_db.end();`
100	`}`	100	`}`
101		101
102	`/// Erase halfedge h. Assumes it is safe to do so. Use with care.`	102	`/// Erase halfedge h. Assumes it is safe to do so. Use with care.`
103	`void erase_halfedge(HalfEdgeIter h)`	103	`void erase_halfedge(HalfEdgeIter h)`
104	`{`	104	`{`
105	`halfedge_db.erase(h);`	105	`halfedge_db.erase(h);`
106	`}`	106	`}`
107		107
108	`/// Erase vertex v. Assumes it is safe to do so. Use with care.`	108	`/// Erase vertex v. Assumes it is safe to do so. Use with care.`
109	`void erase_vertex(VertexIter v)`	109	`void erase_vertex(VertexIter v)`
110	`{`	110	`{`
111	`vertex_db.erase(v);`	111	`vertex_db.erase(v);`
112	`}`	112	`}`
113		113
114	`/// Erase face f. Assumes it is safe to do so. Use with care.`	114	`/// Erase face f. Assumes it is safe to do so. Use with care.`
115	`void erase_face(FaceIter f)`	115	`void erase_face(FaceIter f)`
116	`{`	116	`{`
117	`face_db.erase(f);`	117	`face_db.erase(f);`
118	`}`	118	`}`
119		119
120	`/// Return iterator pointing to the first halfedge.`	120	`/// Return iterator pointing to the first halfedge.`
121	`HalfEdgeIter halfedges_begin() { return halfedge_db.begin();}`	121	`HalfEdgeIter halfedges_begin() { return halfedge_db.begin();}`
122		122
123	`/// Return iterator pointing to beyond the last halfedge.`	123	`/// Return iterator pointing to beyond the last halfedge.`
124	`HalfEdgeIter halfedges_end() { return halfedge_db.end(); }`	124	`HalfEdgeIter halfedges_end() { return halfedge_db.end(); }`
125		125
126	`/// Return iterator pointing to the first vertex.`	126	`/// Return iterator pointing to the first vertex.`
127	`VertexIter vertices_begin() { return vertex_db.begin();}`	127	`VertexIter vertices_begin() { return vertex_db.begin();}`
128		128
129	`/// Return iterator pointing to beyond the last vertex.`	129	`/// Return iterator pointing to beyond the last vertex.`
130	`VertexIter vertices_end() { return vertex_db.end(); }`	130	`VertexIter vertices_end() { return vertex_db.end(); }`
131		131
132	`/// Return iterator pointing to the first face.`	132	`/// Return iterator pointing to the first face.`
133	`FaceIter faces_begin() { return face_db.begin(); }`	133	`FaceIter faces_begin() { return face_db.begin(); }`
134		134
135	`/// Return iterator pointing to beyond the last face.`	135	`/// Return iterator pointing to beyond the last face.`
136	`FaceIter faces_end() { return face_db.end(); }`	136	`FaceIter faces_end() { return face_db.end(); }`
137		137
138	`/** \brief HalfEdge collapse precondition.`	138	`/** \brief HalfEdge collapse precondition.`
139		139
140	`The first argument, v, is the vertex we want to remove. The`	140	`The first argument, v, is the vertex we want to remove. The`
141	`second, h, is a halfedge pointing away from that vertex.`	141	`second, h, is a halfedge pointing away from that vertex.`
142		142
143	`If this function does not return true, it is illegal to collapse`	143	`If this function does not return true, it is illegal to collapse`
144	`h. The reason is that the collapse would violate the manifold property`	144	`h. The reason is that the collapse would violate the manifold property`
145	`of the mesh.`	145	`of the mesh.`
146		146
147	`The test is as follows.`	147	`The test is as follows.`
148		148
149	`1. For the two vertices adjacent to the edge, we generate`	149	`1. For the two vertices adjacent to the edge, we generate`
150	`a list of all their neighbouring vertices. We then generate a`	150	`a list of all their neighbouring vertices. We then generate a`
151	`list of the vertices that occur in both these lists. That is,`	151	`list of the vertices that occur in both these lists. That is,`
152	`we find all vertices connected by edges to both endpoints`	152	`we find all vertices connected by edges to both endpoints`
153	`of the edge and store these in a list.`	153	`of the edge and store these in a list.`
154		154
155	`2. For both faces incident on the edge, check whether they`	155	`2. For both faces incident on the edge, check whether they`
156	`are triangular. If this is the case, the face will be removed,`	156	`are triangular. If this is the case, the face will be removed,`
157	`and it is ok that the the third vertex is connected to both`	157	`and it is ok that the the third vertex is connected to both`
158	`endpoints. Thus the third vertex in such a face is removed`	158	`endpoints. Thus the third vertex in such a face is removed`
159	`from the list generated in 1.`	159	`from the list generated in 1.`
160		160
161	`3. If the list is now empty, all is well. Otherwise, there`	161	`3. If the list is now empty, all is well. Otherwise, there`
162	`would be a vertex in the new mesh with two edges connecting`	162	`would be a vertex in the new mesh with two edges connecting`
163	`it to the same vertex. Return false.`	163	`it to the same vertex. Return false.`
164		164
165	`4. TETRAHEDRON TEST:`	165	`4. TETRAHEDRON TEST:`
166	`If the valency of both vertices is`	166	`If the valency of both vertices is`
167	`three, and the incident faces are triangles, we also disallow`	167	`three, and the incident faces are triangles, we also disallow`
168	`the operation. Reason: It introduces a vertex of valency two`	168	`the operation. Reason: It introduces a vertex of valency two`
169	`and if the final two polygons incident on the vertices`	169	`and if the final two polygons incident on the vertices`
170	`that are adjacent to the edge being collapsed are triangles, then`	170	`that are adjacent to the edge being collapsed are triangles, then`
171	`the construction will collapse`	171	`the construction will collapse`
172		172
173	`5. VALENCY 4 TEST:`	173	`5. VALENCY 4 TEST:`
174	`If a face adjacent to the edge being collapsed is a triangle,`	174	`If a face adjacent to the edge being collapsed is a triangle,`
175	`it will disappear, and the valency of the final vertex beloning to`	175	`it will disappear, and the valency of the final vertex beloning to`
176	`this edge will be reduced by one. Hence this valency should be at`	176	`this edge will be reduced by one. Hence this valency should be at`
177	`least 4. A valency three vertex will be reduced to a valency two`	177	`least 4. A valency three vertex will be reduced to a valency two`
178	`vertex which is considered illegal.`	178	`vertex which is considered illegal.`
179		179
180	`6. PREVENT MERGING HOLES:`	180	`6. PREVENT MERGING HOLES:`
181	`We do not want to collapse an edge if its end points are boundary`	181	`We do not want to collapse an edge if its end points are boundary`
182	`vertices, but its two adjacent faces are not NULL faces, because`	182	`vertices, but its two adjacent faces are not NULL faces, because`
183	`in that case we create a vertex where two holes meet. A non manifold`	183	`in that case we create a vertex where two holes meet. A non manifold`
184	`situation. */`	184	`situation. */`
185	`bool collapse_precond(VertexIter v, HalfEdgeIter h);`	185	`bool collapse_precond(VertexIter v, HalfEdgeIter h);`
186		186
187	`/** Collapse the halfedge h.`	187	`/** Collapse the halfedge h.`
188		188
189	`The first argument, v, is the vertex that is being removed. The`	189	`The first argument, v, is the vertex that is being removed. The`
190	`second, h, is a halfedge pointing away from that vertex.`	190	`second, h, is a halfedge pointing away from that vertex.`
191		191
192	`The final argument is a boolean indicating whether the vertex`	192	`The final argument is a boolean indicating whether the vertex`
193	`that survives the collapse should have a position which is the`	193	`that survives the collapse should have a position which is the`
194	`average of its own position and the vertex that is removed.`	194	`average of its own position and the vertex that is removed.`
195	`By default false.`	195	`By default false.`
196		196
197	`This function is not guaranteed to keep the mesh sane unless,`	197	`This function is not guaranteed to keep the mesh sane unless,`
198	`collapse_precond has returned true.`	198	`collapse_precond has returned true.`
199	`*/`	199	`*/`
200	`void collapse_halfedge(VertexIter v, HalfEdgeIter h, bool=false);`	200	`void collapse_halfedge(VertexIter v, HalfEdgeIter h, bool=false);`
201		201
202	`/** Split a face.`	202	`/** Split a face.`
203	`The face, f, is split by connecting two`	203	`The face, f, is split by connecting two`
204	`vertices v0 and v1 (the next two arguments). The vertices of`	204	`vertices v0 and v1 (the next two arguments). The vertices of`
205	`the old face between v0 and v1 (in counter clockwise order)`	205	`the old face between v0 and v1 (in counter clockwise order)`
206	`continue to belong to f. The vertices between v1 and`	206	`continue to belong to f. The vertices between v1 and`
207	`v0 belong to the new face. An iterator to the new face is`	207	`v0 belong to the new face. An iterator to the new face is`
208	`returned. */`	208	`returned. */`
209	`FaceIter split_face(FaceIter f, VertexIter v0, VertexIter v1);`	209	`FaceIter split_face(FaceIter f, VertexIter v0, VertexIter v1);`
210		210
211	`/** Insert a new vertex on halfedge h.`	211	`/** Insert a new vertex on halfedge h.`
212	`The new halfedge is insterted as the previous edge to h.`	212	`The new halfedge is insterted as the previous edge to h.`
213	`An iterator to the inserted vertex is returned. */`	213	`An iterator to the inserted vertex is returned. */`
214	`VertexIter Manifold::split_edge(HalfEdgeIter h);`	214	`VertexIter Manifold::split_edge(HalfEdgeIter h);`
215		215
216	`/** Triangulate a polygonal face by repeatedly calling split_face.`	216	`/** Triangulate a polygonal face by repeatedly calling split_face.`
217	`Triangulate iteratively splits triangles off a polygon. The first`	217	`Triangulate iteratively splits triangles off a polygon. The first`
218	`triangle split off is the one connecting f->last->vert and`	218	`triangle split off is the one connecting f->last->vert and`
219	`f->last->next->next->vert.`	219	`f->last->next->next->vert.`
220	`*/`	220	`*/`
221	`void triangulate(FaceIter f);`	221	`void triangulate(FaceIter f);`
222		222
223	`/** Triangulate a polygon, f, by inserting a vertex at the barycenter.`	223	`/** Triangulate a polygon, f, by inserting a vertex at the barycenter.`
224	`All vertices in f are connected to the new vertex.`	224	`All vertices in f are connected to the new vertex.`
225	`The word "safe" means that it is less likely to create flipped`	225	`The word "safe" means that it is less likely to create flipped`
226	`triangles than the normal triangulate. On the other hand, it`	226	`triangles than the normal triangulate. On the other hand, it`
227	`introduces more vertices and probably makes the triangles more`	227	`introduces more vertices and probably makes the triangles more`
228	`acute. This function simply calls face_insert_point.`	228	`acute. This function simply calls face_insert_point.`
229		229
230	`The inserted vertex is returned.`	230	`The inserted vertex is returned.`
231	`*/`	231	`*/`
232	`VertexIter safe_triangulate(FaceIter f);`	232	`VertexIter safe_triangulate(FaceIter f);`
233		233
234	`/** Insert a new vertex, v, in a face, f.`	234	`/** Insert a new vertex, v, in a face, f.`
235	`This operation splits an N-gon into N triangles.`	235	`This operation splits an N-gon into N triangles.`
236	`In the current implementation the original face is erased.`	236	`In the current implementation the original face is erased.`
237	`This means that the iterator is not valid after the function`	237	`This means that the iterator is not valid after the function`
238	`returns.`	238	`returns.`
239	`*/`	239	`*/`
240	`void face_insert_point(FaceIter f, VertexIter v);`	240	`void face_insert_point(FaceIter f, VertexIter v);`
241		241
242	`/** Merges two faces into a single polygon. The first face is f. The`	242	`/** Merges two faces into a single polygon. The first face is f. The`
243	`second face is adjacent to f along the halfedge h. This function`	243	`second face is adjacent to f along the halfedge h. This function`
244	`returns true if the merging was possible and false`	244	`returns true if the merging was possible and false`
245	`otherwise. Currently merge only fails if the mesh is already`	245	`otherwise. Currently merge only fails if the mesh is already`
246	`illegal. Thus it should, in fact, never fail. */`	246	`illegal. Thus it should, in fact, never fail. */`
247	`bool merge_faces(FaceIter f, HalfEdgeIter h);`	247	`bool merge_faces(FaceIter f, HalfEdgeIter h);`
248		248
249	`/** Flip an edge h. Returns false if flipping cannot be performed.`	249	`/** Flip an edge h. Returns false if flipping cannot be performed.`
250	`This is either because one of the two adjacent faces is not`	250	`This is either because one of the two adjacent faces is not`
251	`a triangle, or because either end point has valency three or`	251	`a triangle, or because either end point has valency three or`
252	`because the vertices that will be connected already are. */`	252	`because the vertices that will be connected already are. */`
253	`bool flip(HalfEdgeIter h);`	253	`bool flip(HalfEdgeIter h);`
254		254
255	`/** Performs a series of tests to check that this is a valid manifold.`	255	`/** Performs a series of tests to check that this is a valid manifold.`
256	`This function is not rigorously constructed but seems to catch`	256	`This function is not rigorously constructed but seems to catch`
257	`all problems so far. The function returns true if the mesh is`	257	`all problems so far. The function returns true if the mesh is`
258	`valid and false otherwise.`	258	`valid and false otherwise.`
259	`*/`	259	`*/`
260	`bool is_valid();`	260	`bool is_valid();`
261		261
262	`/** Give each vertex a unique id corresponding to its iterator`	262	`/** Give each vertex a unique id corresponding to its iterator`
263	`position */`	263	`position */`
264	`void enumerate_vertices();`	264	`void enumerate_vertices();`
265		265
266	`/** Give each halfedge a unique id corresponding to its iterator`	266	`/** Give each halfedge a unique id corresponding to its iterator`
267	`position */`	267	`position */`
268	`void enumerate_halfedges();`	268	`void enumerate_halfedges();`
269		269
270	`/** Give each face a unique id corresponding to its iterator`	270	`/** Give each face a unique id corresponding to its iterator`
271	`position */`	271	`position */`
272	`void enumerate_faces();`	272	`void enumerate_faces();`
273		273
274	`};`	274	`};`
275		275
276		276
277	`}`	277	`}`
278	`#endif`	278	`#endif`
279		279