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


#include <iostream>
 
#include "Manifold.h"
#include "VertexCirculator.h"
#include "FaceCirculator.h"
 
 
namespace HMesh
{
	using namespace std;
	using namespace CGLA;
 
	void Manifold::get_bbox(Vec3f& pmin, Vec3f& pmax) 
	{
		VertexIter vi = vertices_begin();
		pmin = pmax = vi->pos;
		for(++vi;vi != vertices_end(); ++vi)
			{
				pmin = v_min(vi->pos, pmin);
				pmax = v_max(vi->pos, pmax);
			}
	}
 
  void Manifold::get_bsphere(CGLA::Vec3f& c, float& r) 
  {
    Vec3f p0,p7;
    get_bbox(p0, p7);
    Vec3f rad = (p7 - p0)/2.0;
    c = p0 + rad;
    r = rad.length();
  }
 
 
	VertexIter Manifold::split_edge(HalfEdgeIter h)
	{
		HalfEdgeIter ho = h->opp;
		VertexIter v  = h->vert;
		VertexIter vo = ho->vert;
		Vec3f np = (v->pos+vo->pos)/2.0f;
 
		VertexIter vn = create_vertex(np);
		vn->he = h;
 
		HalfEdgeIter hn = create_halfedge();
		HalfEdgeIter hno = create_halfedge();
 
		vo->he = hn;
		v->he = ho;
		
		glue(hn,hno);
		link(h->prev, hn);
		link(hn,h);
		hn->vert = vn;
 
		link(hno,ho->next);
		link(ho, hno);
		hno->vert = vo;
		ho->vert = vn;
 
 		h->face->last = hn;
 		ho->face->last = ho;
		hn->face = h->face;
		hno->face = ho->face;
 
		check_boundary_consistency(vn);
		check_boundary_consistency(v);
		check_boundary_consistency(vo);
		return vn;
	}
 
 
	void Manifold::remove_face_if_degenerate(HalfEdgeIter h0)
	{
		if(h0->next->next == h0)
			{
				HalfEdgeIter h1 = h0->next;
 
				HalfEdgeIter h0o = h0->opp;
				HalfEdgeIter h1o = h1->opp;
 
				glue(h0o, h1o);
 
				VertexIter v0 = h1->vert;
				VertexIter v1 = h0->vert;
				v0->he = h1o;
				v1->he = h0o;
					
				if(h0->face != NULL_FACE_ITER)
					erase_face(h0->face);
				erase_halfedge(h0);
				erase_halfedge(h1);
				
				check_boundary_consistency(v0);
				check_boundary_consistency(v1);
 
			}
	}
 
	bool Manifold::collapse_precond(VertexIter v1, HalfEdgeIter h)
	{
		/* The goal of this (fiendishly complex) function is to test
			 whether an edge is collapsible. 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.
			 
		*/
			
		VertexIter v2 = h->vert;
 
		std::vector<int> link1;
		VertexCirculator vc1(v1);
		for(;!vc1.end();++vc1)
			link1.push_back(reinterpret_cast<int>(&(*vc1.get_vertex())));
		assert(link1.size()>=2);
 
		std::vector<int> link2;
		VertexCirculator vc2(v2);
		for(;!vc2.end();++vc2)
			link2.push_back(reinterpret_cast<int>(&(*vc2.get_vertex())));
		assert(link2.size()>=2);
 
		sort(link1.begin(),link1.end());
		sort(link2.begin(),link2.end());
 
		vector<int> lisect;
		back_insert_iterator<vector<int> > lii(lisect);
 
		set_intersection(link1.begin(), link1.end(),
										 link2.begin(), link2.end(),
										 lii);
 
		
		// If the adjacent face is a triangle (see 2)
		int k=0;
		if(h->next->next->next == h)
		{
			// VALENCY 4 TEST
			if(valency(h->next->vert)<4)
				return false;
 
			vector<int>::iterator iter;
			iter = find(lisect.begin(),	lisect.end(),
									reinterpret_cast<int>(&(*h->next->vert)));
			assert(iter != lisect.end());
			lisect.erase(iter);
			++k;
 
		}
		// If the adjacent face is a triangle (see 2)
		if(h->opp->next->next->next == h->opp)
		{
			// VALENCY 4 TEST
			if(valency(h->opp->next->vert)<4)
				return false;
 
			vector<int>::iterator iter;
			iter = find(lisect.begin(),	lisect.end(),
									reinterpret_cast<int>(&(*h->opp->next->vert)));
			assert(iter != lisect.end());
			lisect.erase(iter);
			++k;
 
		}
		if(lisect.size() !=0) // See 3.
			return false;
 
		// TETRAHEDRON TEST
		if(k==2 && (link1.size()+link2.size()==6)) 
			return false;
 
		// Test that we are not merging holes (see 6)
		if(is_boundary(v1) && is_boundary(v2) &&
			 (h->face != NULL_FACE_ITER) &&
			 (h->opp->face != NULL_FACE_ITER))
			return false;
		
		
		return true;
	}
 
 
 	void Manifold::collapse_halfedge(VertexIter v, HalfEdgeIter h, 
																	 bool avg_vertices)
	{
		HalfEdgeIter ho = h->opp;
		VertexIter n = h->vert;
 
		if(avg_vertices)
			n->pos = ((v->pos + n->pos) / 2.0f);
		
		HalfEdgeIter hn = h->next;
		HalfEdgeIter hp = h->prev;
		HalfEdgeIter hon = ho->next;
		HalfEdgeIter hop = ho->prev;
 
		bool neighbour_is_boundary = is_boundary(n);
 
		VertexCirculator vc(v);
		for(;!vc.end();++vc)
			vc.get_opp_halfedge()->vert = n;
 
		n->he = h->next;
 
		link(hp, hn);
		if(h->face != NULL_FACE_ITER)
			h->face->last = hn;
 
		link(hop, hon);
		if(ho->face != NULL_FACE_ITER)
			ho->face->last = hon;
 
 
 
		erase_vertex(v);
 		erase_halfedge(h);
 		erase_halfedge(ho);
 
		remove_face_if_degenerate(hn);
		remove_face_if_degenerate(hon);
 
		check_boundary_consistency(n);
	}
 
	bool Manifold::is_valid()
	{
		HalfEdgeIter he0 = halfedges_begin();
		while(he0 != halfedges_end())
			{
				if(he0->prev == NULL_HALFEDGE_ITER)
					{
						cout << "Halfedge lacks previous" << endl;
						return false;
					}
				if(he0->next == NULL_HALFEDGE_ITER)
					{
						cout << "Halfedge lacks next" << endl;
						return false;
					}
				if(he0->opp == NULL_HALFEDGE_ITER)
					{
						cout << "Halfedge lacks opposite" << endl;
						return false;
					}
				if(he0->vert == NULL_VERTEX_ITER)
					{
						cout << "Halfedge lacks vertex" << endl;
						return false;
					}				
				++he0;
			}
				
		VertexIter vi = vertices_begin();
		while(vi != vertices_end())
			{
				std::vector<int> link;
				VertexCirculator vc(vi);
				int k=0;
				for(;!vc.end();++vc,++k)
					{
						if(vc.get_halfedge() == NULL_HALFEDGE_ITER)
							{
								cout << "Vertex has null outgoing he" << endl;
								return false;
							}
						int x = reinterpret_cast<int>(&(*vc.get_vertex()));
						if(find(link.begin(), link.end(), x) != link.end())
							{
								cout << "Vertex appears two times in one-ring of other vertex" << endl;
 								return false;
							}
						link.push_back(x);
						if(k==1e6) 
							{
								cout << "infin. loop around vertex" << endl;
								return false;
							}
					}
				if(link.size()==2)
					{
						cout << "Warning: A vertex with only two incident edges" << endl;
					}
				assert(link.size()>=2);
				++vi;
			}
 
		HMesh::FaceIter f = faces_begin();
			for(;f != faces_end(); ++f)
				{
					if(no_edges(f)<3)
						{
							cout << "Degenerate face" << endl;
						}
					FaceCirculator fc(f);
					int k=0;
					while(!fc.end())
						{
							if(fc.get_halfedge()->face != f)
								{
									cout << "Inconsistent face" << endl;
									return false;
								}
							if(++k==1e6) cout << "infin. loop around face" << endl;
							++fc;
						}
				}
		return true;
	}
 
	FaceIter Manifold::split_face(FaceIter f, VertexIter v0, VertexIter v1)
	{
		// Make sure this is not a triangle 
		assert(no_edges(f)>3);
 
		// Make sure we are not trying to connect a vertex to itself.
		assert(v0 != v1);
 
		// Find the halfedge emanating from v0 which belongs to the
		// face, we need to split. 
		VertexCirculator vc0(v0);
		while(vc0.get_halfedge()->face != f && !vc0.end()) vc0++;
		assert(!vc0.end());
		HalfEdgeIter h0 = vc0.get_halfedge();
		assert(h0->face == f); // Sanity check.
 
		// The halfedge belonging to f, going out from v0, is denoted h.
		// Move along h until we hit v1. Now we have the halfedge which
		// belongs to f and points to v1.
		HalfEdgeIter h = h0;
		while(h->vert != v1) 
			h = h->next;
 
		// Create a new halfedge ha which connects v1 and v0 closing the first
		// loop. This new halfedge becomes f->last
		assert(h != h0);
		HalfEdgeIter h1 = h->next;
		HalfEdgeIter ha = create_halfedge();
		link(h,ha);
		link(ha, h0);
		ha->face = f;
		ha->vert = v0;
		f->last = ha;
 
		// Create a new face, f2, and set all halfedges in the remaining part of 
		// the polygon to point to this face. 
		h = h1;
		FaceIter f2 = create_face();
		while(h->vert != v0) 
			{
				h->face = f2;
				h = h->next;
			}
		h->face = f2;
		assert(h != h1);
 
		// Create a new halfedge hb to connect v0 and v1. this new halfedge 
		// becomes f2->last
		HalfEdgeIter hb = create_halfedge();
		link(h,hb);
		link(hb, h1);
		hb->face = f2;
		hb->vert = v1;
		f2->last = hb;
 
		// Complete the operation by gluing the two new halfedges.
		glue(ha, hb);
 
		// Assert that the pointers are sane :-)
		assert(h1->prev->opp->next == h0);
		assert(h0->prev->opp->next == h1);
		assert(hb->next->face == f2);
		assert(hb->next->next->face == f2);
		assert(hb->face == f2);
 
		// Return the newly created face
		return f2;
	}
 
	void Manifold::triangulate(FaceIter f)
	{
		// Assert sanity of pointers
		assert(f->last->next->next != f->last);
		assert(f->last->next != f->last);
		assert(--(++f) == f);
		// As long as f is not a triangle.
		while(f->last->next->next->next != f->last)
			{
				assert(no_edges(f) != 3);
				// Call split face to split f into a triangle
				// from the first three vertices and a polygon
				// containing the rest of the vertices. In the
				// next iteration, f becomes this polygon.
				
				assert(f->last->next->next != f->last);
				VertexIter v0 = f->last->vert;
				VertexIter v1 = f->last->next->next->vert;
				assert(v0 != v1);
				f = split_face(f, v0, v1);
			}
	}
 
	bool Manifold::merge_faces(FaceIter f1, HalfEdgeIter h)
	{
		assert(h->face == f1);
		
		HalfEdgeIter ho = h->opp;
		FaceIter f2 = ho->face;
		HalfEdgeIter hn = h->next;
		HalfEdgeIter hon = ho->next;
		
		if(hn->vert == hon->vert) return false;
 
		HalfEdgeIter hp = h->prev;
		HalfEdgeIter hop = ho->prev;
		VertexIter v  = h->vert;
		VertexIter vo = ho->vert;
		
		link(hop, hn);
		v->he = hn;
 
		link(hp, hon);
		vo->he = hon;
 
		f1->last = hn;
		HalfEdgeIter hx = hon;
		assert(hx->face == f2);
		while(hx->face != f1)
			{
				hx->face = f1;
				hx = hx->next;
			}
 
		check_boundary_consistency(v);
		check_boundary_consistency(vo);
 
 		erase_halfedge(h);
 		erase_halfedge(ho);
		erase_face(f2);
		
		return true;
	}
 
 
	VertexIter Manifold::safe_triangulate(FaceIter f)
	{
		Vec3f p;
		FaceCirculator fc(f);
		for(;!fc.end(); ++fc)
			p += fc.get_vertex()->pos;
		int n = fc.no_steps();
		p /= n;
		VertexIter v = create_vertex(p);
		face_insert_point(f,v);
		return v;
	}
 
 
	void Manifold::face_insert_point(FaceIter f, VertexIter v)
	{
		vector<HalfEdgeIter> eout;
		vector<HalfEdgeIter> ein;
 
		HalfEdgeIter hlast = f->last;
		HalfEdgeIter h = hlast;
 
		do
			{
				HalfEdgeIter hn = h->next;
 
				HalfEdgeIter o = create_halfedge();
				HalfEdgeIter i = create_halfedge();
				
				FaceIter fn = create_face();
				i->face = fn;
				i->vert = v;
				o->face = fn;
				o->vert = h->opp->vert;
				h->face = fn;
				fn->last = o;
 
				link(i,o);
				link(o,h);
				link(h,i);
 
				eout.push_back(o);
				ein.push_back(i);
				
				h = hn;
			}
		while(h != hlast);
 
		int N = eout.size();
		for(int i=0;i<N;++i)
			glue(ein[i],eout[(i+1)%N]);
		
		v->he = eout[0];
		erase_face(f);
	}
 
 
	bool Manifold::flip(HalfEdgeIter h1)
	{
		FaceIter f1 = h1->face;
		HalfEdgeIter h2 = h1->opp;
		FaceIter f2 = h2->face;
 
		if(f1 == NULL_FACE_ITER || f2 == NULL_FACE_ITER)
			return false;
 
		// We can only flip an edge if both incident polygons
		// are triangles. Otherwise, this operation makes no sense.
		if(no_edges(f1) != 3)
			return false;
		if(no_edges(f2) !=3)
			return false;
		
		// If the valency of either vertex incident on the edge
		// being flipped is three, we cannot perform this operation.
		// That is because the vertex would then have valency two
		// after the operation which means it would be degenerate.
		VertexIter va = h1->vert;
		VertexIter vb = h2->vert;
		int vala = valency(va);
		int valb = valency(vb);
		if((vala <= 3) || (valb <= 3))
			return false;
		
		// If the two vertices being connected by the flip are already
		// connected, the mesh would become degenerate, so we disallow
		// the operation.
		VertexIter vc = h1->next->vert;
		VertexIter vd = h2->next->vert;
		if(is_connected(vc,vd))
			return false;
 
		HalfEdgeIter ha = h1->next;
		HalfEdgeIter hb = h1->prev;
		HalfEdgeIter hc = h2->next;
		HalfEdgeIter hd = h2->prev;
 
		hd->face = f1;
		hb->face = f2;
		f1->last = h1;
		f2->last = h2;
 
		link(ha,h1);
		link(h1,hd);
		link(hd,ha);
 
		link(hc,h2);
		link(h2,hb);
		link(hb,hc);
	 
		h1->vert = vd;
		h2->vert = vc;
 
		va->he = ha;
		vb->he = hc;
 
		check_boundary_consistency(va);
		check_boundary_consistency(vb);
		return true;
	}
 
		/** Give each vertex a unique id corresponding to its iterator 
				position */
		void Manifold::enumerate_vertices()
		{
			int i=0;
			for(VertexIter vi=vertices_begin(); vi != vertices_end(); ++vi)
				vi->touched = i++;
		}
	
		/** Give each halfedge a unique id corresponding to its iterator 
				position */
		void Manifold::enumerate_halfedges()
		{
			int i=0;
			for(HalfEdgeIter h=halfedges_begin(); h != halfedges_end(); ++h)
				h->touched = i++;
		}
 
		/** Give each face a unique id corresponding to its iterator 
				position */
		void Manifold::enumerate_faces()
		{
			int i=0;
			for(FaceIter f=faces_begin(); f != faces_end(); ++f)
				f->touched = i++;
		}
 
 
}
 
 

Rev 59	Rev 62
1	`#include <iostream>`	1	`#include <iostream>`
2		2
3	`#include "Manifold.h"`	3	`#include "Manifold.h"`
4	`#include "VertexCirculator.h"`	4	`#include "VertexCirculator.h"`
5	`#include "FaceCirculator.h"`	5	`#include "FaceCirculator.h"`
6		6
7		7
8	`namespace HMesh`	8	`namespace HMesh`
9	`{`	9	`{`
10	`using namespace std;`	10	`using namespace std;`
11	`using namespace CGLA;`	11	`using namespace CGLA;`
12		12
13	`void Manifold::get_bbox(Vec3f& pmin, Vec3f& pmax)`	13	`void Manifold::get_bbox(Vec3f& pmin, Vec3f& pmax)`
14	`{`	14	`{`
15	`VertexIter vi = vertices_begin();`	15	`VertexIter vi = vertices_begin();`
16	`pmin = pmax = vi->get_pos();`	16	`pmin = pmax = vi->pos;`
17	`for(++vi;vi != vertices_end(); ++vi)`	17	`for(++vi;vi != vertices_end(); ++vi)`
18	`{`	18	`{`
19	`pmin = v_min(vi->get_pos(), pmin);`	19	`pmin = v_min(vi->pos, pmin);`
20	`pmax = v_max(vi->get_pos(), pmax);`	20	`pmax = v_max(vi->pos, pmax);`
21	`}`	21	`}`
22	`}`	22	`}`
23		23
24	`void Manifold::get_bsphere(CGLA::Vec3f& c, float& r)`	24	`void Manifold::get_bsphere(CGLA::Vec3f& c, float& r)`
25	`{`	25	`{`
26	`Vec3f p0,p7;`	26	`Vec3f p0,p7;`
27	`get_bbox(p0, p7);`	27	`get_bbox(p0, p7);`
28	`Vec3f rad = (p7 - p0)/2.0;`	28	`Vec3f rad = (p7 - p0)/2.0;`
29	`c = p0 + rad;`	29	`c = p0 + rad;`
30	`r = rad.length();`	30	`r = rad.length();`
31	`}`	31	`}`
32		32
33		33
34	`VertexIter Manifold::split_edge(HalfEdgeIter h)`	34	`VertexIter Manifold::split_edge(HalfEdgeIter h)`
35	`{`	35	`{`
36	`HalfEdgeIter ho = h->opp;`	36	`HalfEdgeIter ho = h->opp;`
37	`VertexIter v = h->vert;`	37	`VertexIter v = h->vert;`
38	`VertexIter vo = ho->vert;`	38	`VertexIter vo = ho->vert;`
39	`Vec3f np = (v->get_pos()+vo->get_pos())/2.0f;`	39	`Vec3f np = (v->pos+vo->pos)/2.0f;`
40		40
41	`VertexIter vn = create_vertex(np);`	41	`VertexIter vn = create_vertex(np);`
42	`vn->he = h;`	42	`vn->he = h;`
43		43
44	`HalfEdgeIter hn = create_halfedge();`	44	`HalfEdgeIter hn = create_halfedge();`
45	`HalfEdgeIter hno = create_halfedge();`	45	`HalfEdgeIter hno = create_halfedge();`
46		46
47	`vo->he = hn;`	47	`vo->he = hn;`
48	`v->he = ho;`	48	`v->he = ho;`
49		49
50	`glue(hn,hno);`	50	`glue(hn,hno);`
51	`link(h->prev, hn);`	51	`link(h->prev, hn);`
52	`link(hn,h);`	52	`link(hn,h);`
53	`hn->vert = vn;`	53	`hn->vert = vn;`
54		54
55	`link(hno,ho->next);`	55	`link(hno,ho->next);`
56	`link(ho, hno);`	56	`link(ho, hno);`
57	`hno->vert = vo;`	57	`hno->vert = vo;`
58	`ho->vert = vn;`	58	`ho->vert = vn;`
59		59
60	`h->face->last = hn;`	60	`h->face->last = hn;`
61	`ho->face->last = ho;`	61	`ho->face->last = ho;`
62	`hn->face = h->face;`	62	`hn->face = h->face;`
63	`hno->face = ho->face;`	63	`hno->face = ho->face;`
64		64
65	`vn->check_boundary_consistency();`	65	`check_boundary_consistency(vn);`
66	`v->check_boundary_consistency();`	66	`check_boundary_consistency(v);`
67	`vo->check_boundary_consistency();`	67	`check_boundary_consistency(vo);`
68	`return vn;`	68	`return vn;`
69	`}`	69	`}`
70		70
71		71
72	`void Manifold::remove_face_if_degenerate(HalfEdgeIter h0)`	72	`void Manifold::remove_face_if_degenerate(HalfEdgeIter h0)`
73	`{`	73	`{`
74	`if(h0->next->next == h0)`	74	`if(h0->next->next == h0)`
75	`{`	75	`{`
76	`HalfEdgeIter h1 = h0->next;`	76	`HalfEdgeIter h1 = h0->next;`
77		77
78	`HalfEdgeIter h0o = h0->opp;`	78	`HalfEdgeIter h0o = h0->opp;`
79	`HalfEdgeIter h1o = h1->opp;`	79	`HalfEdgeIter h1o = h1->opp;`
80		80
81	`glue(h0o, h1o);`	81	`glue(h0o, h1o);`
82		82
83	`VertexIter v0 = h1->vert;`	83	`VertexIter v0 = h1->vert;`
84	`VertexIter v1 = h0->vert;`	84	`VertexIter v1 = h0->vert;`
85	`v0->he = h1o;`	85	`v0->he = h1o;`
86	`v1->he = h0o;`	86	`v1->he = h0o;`
87		87
88	`if(h0->face != NULL_FACE_ITER)`	88	`if(h0->face != NULL_FACE_ITER)`
89	`erase_face(h0->face);`	89	`erase_face(h0->face);`
90	`erase_halfedge(h0);`	90	`erase_halfedge(h0);`
91	`erase_halfedge(h1);`	91	`erase_halfedge(h1);`
92		92
93	`v0->check_boundary_consistency();`	93	`check_boundary_consistency(v0);`
94	`v1->check_boundary_consistency();`	94	`check_boundary_consistency(v1);`
95		95
96	`}`	96	`}`
97	`}`	97	`}`
98		98
99	`bool Manifold::collapse_precond(VertexIter v1, HalfEdgeIter h)`	99	`bool Manifold::collapse_precond(VertexIter v1, HalfEdgeIter h)`
100	`{`	100	`{`
101	`/* The goal of this (fiendishly complex) function is to test`	101	`/* The goal of this (fiendishly complex) function is to test`
102	`whether an edge is collapsible. The test is as follows.`	102	`whether an edge is collapsible. The test is as follows.`
103		103
104	`1. For the two vertices adjacent to the edge, we generate`	104	`1. For the two vertices adjacent to the edge, we generate`
105	`a list of all their neighbouring vertices. We then generate a`	105	`a list of all their neighbouring vertices. We then generate a`
106	`list of the vertices that occur in both these lists. That is,`	106	`list of the vertices that occur in both these lists. That is,`
107	`we find all vertices connected by edges to both endpoints`	107	`we find all vertices connected by edges to both endpoints`
108	`of the edge and store these in a list.`	108	`of the edge and store these in a list.`
109		109
110	`2. For both faces incident on the edge, check whether they`	110	`2. For both faces incident on the edge, check whether they`
111	`are triangular. If this is the case, the face will be removed,`	111	`are triangular. If this is the case, the face will be removed,`
112	`and it is ok that the the third vertex is connected to both`	112	`and it is ok that the the third vertex is connected to both`
113	`endpoints. Thus the third vertex in such a face is removed`	113	`endpoints. Thus the third vertex in such a face is removed`
114	`from the list generated in 1.`	114	`from the list generated in 1.`
115		115
116	`3. If the list is now empty, all is well. Otherwise, there`	116	`3. If the list is now empty, all is well. Otherwise, there`
117	`would be a vertex in the new mesh with two edges connecting`	117	`would be a vertex in the new mesh with two edges connecting`
118	`it to the same vertex. Return false.`	118	`it to the same vertex. Return false.`
119		119
120	`4. TETRAHEDRON TEST:`	120	`4. TETRAHEDRON TEST:`
121	`If the valency of both vertices is`	121	`If the valency of both vertices is`
122	`three, and the incident faces are triangles, we also disallow`	122	`three, and the incident faces are triangles, we also disallow`
123	`the operation. Reason: It introduces a vertex of valency two`	123	`the operation. Reason: It introduces a vertex of valency two`
124	`and if the final two polygons incident on the vertices`	124	`and if the final two polygons incident on the vertices`
125	`that are adjacent to the edge being collapsed are triangles, then`	125	`that are adjacent to the edge being collapsed are triangles, then`
126	`the construction will collapse`	126	`the construction will collapse`
127		127
128	`5. VALENCY 4 TEST:`	128	`5. VALENCY 4 TEST:`
129	`If a face adjacent to the edge being collapsed is a triangle,`	129	`If a face adjacent to the edge being collapsed is a triangle,`
130	`it will disappear, and the valency of the final vertex beloning to`	130	`it will disappear, and the valency of the final vertex beloning to`
131	`this edge will be reduced by one. Hence this valency should be at`	131	`this edge will be reduced by one. Hence this valency should be at`
132	`least 4. A valency three vertex will be reduced to a valency two`	132	`least 4. A valency three vertex will be reduced to a valency two`
133	`vertex which is considered illegal.`	133	`vertex which is considered illegal.`
134		134
135	`6. PREVENT MERGING HOLES:`	135	`6. PREVENT MERGING HOLES:`
136	`We do not want to collapse an edge if its end points are boundary`	136	`We do not want to collapse an edge if its end points are boundary`
137	`vertices, but its two adjacent faces are not NULL faces, because`	137	`vertices, but its two adjacent faces are not NULL faces, because`
138	`in that case we create a vertex where two holes meet. A non manifold`	138	`in that case we create a vertex where two holes meet. A non manifold`
139	`situation.`	139	`situation.`
140		140
141	`*/`	141	`*/`
142		142
143	`VertexIter v2 = h->vert;`	143	`VertexIter v2 = h->vert;`
144		144
145	`std::vector<int> link1;`	145	`std::vector<int> link1;`
146	`VertexCirculator vc1(v1);`	146	`VertexCirculator vc1(v1);`
147	`for(;!vc1.end();++vc1)`	147	`for(;!vc1.end();++vc1)`
148	`link1.push_back(reinterpret_cast<int>(&(*vc1.get_vertex())));`	148	`link1.push_back(reinterpret_cast<int>(&(*vc1.get_vertex())));`
149	`assert(link1.size()>=2);`	149	`assert(link1.size()>=2);`
150		150
151	`std::vector<int> link2;`	151	`std::vector<int> link2;`
152	`VertexCirculator vc2(v2);`	152	`VertexCirculator vc2(v2);`
153	`for(;!vc2.end();++vc2)`	153	`for(;!vc2.end();++vc2)`
154	`link2.push_back(reinterpret_cast<int>(&(*vc2.get_vertex())));`	154	`link2.push_back(reinterpret_cast<int>(&(*vc2.get_vertex())));`
155	`assert(link2.size()>=2);`	155	`assert(link2.size()>=2);`
156		156
157	`sort(link1.begin(),link1.end());`	157	`sort(link1.begin(),link1.end());`
158	`sort(link2.begin(),link2.end());`	158	`sort(link2.begin(),link2.end());`
159		159
160	`vector<int> lisect;`	160	`vector<int> lisect;`
161	`back_insert_iterator<vector<int> > lii(lisect);`	161	`back_insert_iterator<vector<int> > lii(lisect);`
162		162
163	`set_intersection(link1.begin(), link1.end(),`	163	`set_intersection(link1.begin(), link1.end(),`
164	`link2.begin(), link2.end(),`	164	`link2.begin(), link2.end(),`
165	`lii);`	165	`lii);`
166		166
167		167
168	`// If the adjacent face is a triangle (see 2)`	168	`// If the adjacent face is a triangle (see 2)`
169	`int k=0;`	169	`int k=0;`
170	`if(h->next->next->next == h)`	170	`if(h->next->next->next == h)`
171	`{`	171	`{`
172	`// VALENCY 4 TEST`	172	`// VALENCY 4 TEST`
173	`if(valency(h->next->vert)<4)`	173	`if(valency(h->next->vert)<4)`
174	`return false;`	174	`return false;`
175		175
176	`vector<int>::iterator iter;`	176	`vector<int>::iterator iter;`
177	`iter = find(lisect.begin(), lisect.end(),`	177	`iter = find(lisect.begin(), lisect.end(),`
178	`reinterpret_cast<int>(&(*h->next->vert)));`	178	`reinterpret_cast<int>(&(*h->next->vert)));`
179	`assert(iter != lisect.end());`	179	`assert(iter != lisect.end());`
180	`lisect.erase(iter);`	180	`lisect.erase(iter);`
181	`++k;`	181	`++k;`
182		182
183	`}`	183	`}`
184	`// If the adjacent face is a triangle (see 2)`	184	`// If the adjacent face is a triangle (see 2)`
185	`if(h->opp->next->next->next == h->opp)`	185	`if(h->opp->next->next->next == h->opp)`
186	`{`	186	`{`
187	`// VALENCY 4 TEST`	187	`// VALENCY 4 TEST`
188	`if(valency(h->opp->next->vert)<4)`	188	`if(valency(h->opp->next->vert)<4)`
189	`return false;`	189	`return false;`
190		190
191	`vector<int>::iterator iter;`	191	`vector<int>::iterator iter;`
192	`iter = find(lisect.begin(), lisect.end(),`	192	`iter = find(lisect.begin(), lisect.end(),`
193	`reinterpret_cast<int>(&(*h->opp->next->vert)));`	193	`reinterpret_cast<int>(&(*h->opp->next->vert)));`
194	`assert(iter != lisect.end());`	194	`assert(iter != lisect.end());`
195	`lisect.erase(iter);`	195	`lisect.erase(iter);`
196	`++k;`	196	`++k;`
197		197
198	`}`	198	`}`
199	`if(lisect.size() !=0) // See 3.`	199	`if(lisect.size() !=0) // See 3.`
200	`return false;`	200	`return false;`
201		201
202	`// TETRAHEDRON TEST`	202	`// TETRAHEDRON TEST`
203	`if(k==2 && (link1.size()+link2.size()==6))`	203	`if(k==2 && (link1.size()+link2.size()==6))`
204	`return false;`	204	`return false;`
205		205
206	`// Test that we are not merging holes (see 6)`	206	`// Test that we are not merging holes (see 6)`
207	`if(v1->is_boundary() && v2->is_boundary() &&`	207	`if(is_boundary(v1) && is_boundary(v2) &&`
208	`(h->face != NULL_FACE_ITER) &&`	208	`(h->face != NULL_FACE_ITER) &&`
209	`(h->opp->face != NULL_FACE_ITER))`	209	`(h->opp->face != NULL_FACE_ITER))`
210	`return false;`	210	`return false;`
211		211
212		212
213	`return true;`	213	`return true;`
214	`}`	214	`}`
215		215
216		216
217	`void Manifold::collapse_halfedge(VertexIter v, HalfEdgeIter h,`	217	`void Manifold::collapse_halfedge(VertexIter v, HalfEdgeIter h,`
218	`bool avg_vertices)`	218	`bool avg_vertices)`
219	`{`	219	`{`
220	`HalfEdgeIter ho = h->opp;`	220	`HalfEdgeIter ho = h->opp;`
221	`VertexIter n = h->vert;`	221	`VertexIter n = h->vert;`
222		222
223	`if(avg_vertices)`	223	`if(avg_vertices)`
224	`n->set_pos((v->get_pos() + n->get_pos()) / 2.0f);`	224	`n->pos = ((v->pos + n->pos) / 2.0f);`
225		225
226	`HalfEdgeIter hn = h->next;`	226	`HalfEdgeIter hn = h->next;`
227	`HalfEdgeIter hp = h->prev;`	227	`HalfEdgeIter hp = h->prev;`
228	`HalfEdgeIter hon = ho->next;`	228	`HalfEdgeIter hon = ho->next;`
229	`HalfEdgeIter hop = ho->prev;`	229	`HalfEdgeIter hop = ho->prev;`
230		230
231	`bool neighbour_is_boundary = n->is_boundary();`	231	`bool neighbour_is_boundary = is_boundary(n);`
232		232
233	`VertexCirculator vc(v);`	233	`VertexCirculator vc(v);`
234	`for(;!vc.end();++vc)`	234	`for(;!vc.end();++vc)`
235	`vc.get_opp_halfedge()->vert = n;`	235	`vc.get_opp_halfedge()->vert = n;`
236		236
237	`n->he = h->next;`	237	`n->he = h->next;`
238		238
239	`link(hp, hn);`	239	`link(hp, hn);`
240	`if(h->face != NULL_FACE_ITER)`	240	`if(h->face != NULL_FACE_ITER)`
241	`h->face->last = hn;`	241	`h->face->last = hn;`
242		242
243	`link(hop, hon);`	243	`link(hop, hon);`
244	`if(ho->face != NULL_FACE_ITER)`	244	`if(ho->face != NULL_FACE_ITER)`
245	`ho->face->last = hon;`	245	`ho->face->last = hon;`
246		246
247		247
248		248
249	`erase_vertex(v);`	249	`erase_vertex(v);`
250	`erase_halfedge(h);`	250	`erase_halfedge(h);`
251	`erase_halfedge(ho);`	251	`erase_halfedge(ho);`
252		252
253	`remove_face_if_degenerate(hn);`	253	`remove_face_if_degenerate(hn);`
254	`remove_face_if_degenerate(hon);`	254	`remove_face_if_degenerate(hon);`
255		255
256	`n->check_boundary_consistency();`	256	`check_boundary_consistency(n);`
257	`}`	257	`}`
258		258
259	`bool Manifold::is_valid()`	259	`bool Manifold::is_valid()`
260	`{`	260	`{`
261	`HalfEdgeIter he0 = halfedges_begin();`	261	`HalfEdgeIter he0 = halfedges_begin();`
262	`while(he0 != halfedges_end())`	262	`while(he0 != halfedges_end())`
263	`{`	263	`{`
264	`if(he0->prev == NULL_HALFEDGE_ITER)`	264	`if(he0->prev == NULL_HALFEDGE_ITER)`
265	`{`	265	`{`
266	`cout << "Halfedge lacks previous" << endl;`	266	`cout << "Halfedge lacks previous" << endl;`
267	`return false;`	267	`return false;`
268	`}`	268	`}`
269	`if(he0->next == NULL_HALFEDGE_ITER)`	269	`if(he0->next == NULL_HALFEDGE_ITER)`
270	`{`	270	`{`
271	`cout << "Halfedge lacks next" << endl;`	271	`cout << "Halfedge lacks next" << endl;`
272	`return false;`	272	`return false;`
273	`}`	273	`}`
274	`if(he0->opp == NULL_HALFEDGE_ITER)`	274	`if(he0->opp == NULL_HALFEDGE_ITER)`
275	`{`	275	`{`
276	`cout << "Halfedge lacks opposite" << endl;`	276	`cout << "Halfedge lacks opposite" << endl;`
277	`return false;`	277	`return false;`
278	`}`	278	`}`
279	`if(he0->vert == NULL_VERTEX_ITER)`	279	`if(he0->vert == NULL_VERTEX_ITER)`
280	`{`	280	`{`
281	`cout << "Halfedge lacks vertex" << endl;`	281	`cout << "Halfedge lacks vertex" << endl;`
282	`return false;`	282	`return false;`
283	`}`	283	`}`
284	`++he0;`	284	`++he0;`
285	`}`	285	`}`
286		286
287	`VertexIter vi = vertices_begin();`	287	`VertexIter vi = vertices_begin();`
288	`while(vi != vertices_end())`	288	`while(vi != vertices_end())`
289	`{`	289	`{`
290	`std::vector<int> link;`	290	`std::vector<int> link;`
291	`VertexCirculator vc(vi);`	291	`VertexCirculator vc(vi);`
292	`int k=0;`	292	`int k=0;`
293	`for(;!vc.end();++vc,++k)`	293	`for(;!vc.end();++vc,++k)`
294	`{`	294	`{`
295	`if(vc.get_halfedge() == NULL_HALFEDGE_ITER)`	295	`if(vc.get_halfedge() == NULL_HALFEDGE_ITER)`
296	`{`	296	`{`
297	`cout << "Vertex has null outgoing he" << endl;`	297	`cout << "Vertex has null outgoing he" << endl;`
298	`return false;`	298	`return false;`
299	`}`	299	`}`
300	`int x = reinterpret_cast<int>(&(*vc.get_vertex()));`	300	`int x = reinterpret_cast<int>(&(*vc.get_vertex()));`
301	`if(find(link.begin(), link.end(), x) != link.end())`	301	`if(find(link.begin(), link.end(), x) != link.end())`
302	`{`	302	`{`
303	`cout << "Vertex appears two times in one-ring of other vertex" << endl;`	303	`cout << "Vertex appears two times in one-ring of other vertex" << endl;`
304	`return false;`	304	`return false;`
305	`}`	305	`}`
306	`link.push_back(x);`	306	`link.push_back(x);`
307	`if(k==1e6)`	307	`if(k==1e6)`
308	`{`	308	`{`
309	`cout << "infin. loop around vertex" << endl;`	309	`cout << "infin. loop around vertex" << endl;`
310	`return false;`	310	`return false;`
311	`}`	311	`}`
312	`}`	312	`}`
313	`if(link.size()==2)`	313	`if(link.size()==2)`
314	`{`	314	`{`
315	`cout << "Warning: A vertex with only two incident edges" << endl;`	315	`cout << "Warning: A vertex with only two incident edges" << endl;`
316	`}`	316	`}`
317	`assert(link.size()>=2);`	317	`assert(link.size()>=2);`
318	`++vi;`	318	`++vi;`
319	`}`	319	`}`
320		320
321	`HMesh::FaceIter f = faces_begin();`	321	`HMesh::FaceIter f = faces_begin();`
322	`for(;f != faces_end(); ++f)`	322	`for(;f != faces_end(); ++f)`
323	`{`	323	`{`
324	`if(no_edges(f)<3)`	324	`if(no_edges(f)<3)`
325	`{`	325	`{`
326	`cout << "Degenerate face" << endl;`	326	`cout << "Degenerate face" << endl;`
327	`}`	327	`}`
328	`FaceCirculator fc(f);`	328	`FaceCirculator fc(f);`
329	`int k=0;`	329	`int k=0;`
330	`while(!fc.end())`	330	`while(!fc.end())`
331	`{`	331	`{`
332	`if(fc.get_halfedge()->face != f)`	332	`if(fc.get_halfedge()->face != f)`
333	`{`	333	`{`
334	`cout << "Inconsistent face" << endl;`	334	`cout << "Inconsistent face" << endl;`
335	`return false;`	335	`return false;`
336	`}`	336	`}`
337	`if(++k==1e6) cout << "infin. loop around face" << endl;`	337	`if(++k==1e6) cout << "infin. loop around face" << endl;`
338	`++fc;`	338	`++fc;`
339	`}`	339	`}`
340	`}`	340	`}`
341	`return true;`	341	`return true;`
342	`}`	342	`}`
343		343
344	`FaceIter Manifold::split_face(FaceIter f, VertexIter v0, VertexIter v1)`	344	`FaceIter Manifold::split_face(FaceIter f, VertexIter v0, VertexIter v1)`
345	`{`	345	`{`
346	`// Make sure this is not a triangle`	346	`// Make sure this is not a triangle`
347	`assert(no_edges(f)>3);`	347	`assert(no_edges(f)>3);`
348		348
349	`// Make sure we are not trying to connect a vertex to itself.`	349	`// Make sure we are not trying to connect a vertex to itself.`
350	`assert(v0 != v1);`	350	`assert(v0 != v1);`
351		351
352	`// Find the halfedge emanating from v0 which belongs to the`	352	`// Find the halfedge emanating from v0 which belongs to the`
353	`// face, we need to split.`	353	`// face, we need to split.`
354	`VertexCirculator vc0(v0);`	354	`VertexCirculator vc0(v0);`
355	`while(vc0.get_halfedge()->face != f && !vc0.end()) vc0++;`	355	`while(vc0.get_halfedge()->face != f && !vc0.end()) vc0++;`
356	`assert(!vc0.end());`	356	`assert(!vc0.end());`
357	`HalfEdgeIter h0 = vc0.get_halfedge();`	357	`HalfEdgeIter h0 = vc0.get_halfedge();`
358	`assert(h0->face == f); // Sanity check.`	358	`assert(h0->face == f); // Sanity check.`
359		359
360	`// The halfedge belonging to f, going out from v0, is denoted h.`	360	`// The halfedge belonging to f, going out from v0, is denoted h.`
361	`// Move along h until we hit v1. Now we have the halfedge which`	361	`// Move along h until we hit v1. Now we have the halfedge which`
362	`// belongs to f and points to v1.`	362	`// belongs to f and points to v1.`
363	`HalfEdgeIter h = h0;`	363	`HalfEdgeIter h = h0;`
364	`while(h->vert != v1)`	364	`while(h->vert != v1)`
365	`h = h->next;`	365	`h = h->next;`
366		366
367	`// Create a new halfedge ha which connects v1 and v0 closing the first`	367	`// Create a new halfedge ha which connects v1 and v0 closing the first`
368	`// loop. This new halfedge becomes f->last`	368	`// loop. This new halfedge becomes f->last`
369	`assert(h != h0);`	369	`assert(h != h0);`
370	`HalfEdgeIter h1 = h->next;`	370	`HalfEdgeIter h1 = h->next;`
371	`HalfEdgeIter ha = create_halfedge();`	371	`HalfEdgeIter ha = create_halfedge();`
372	`link(h,ha);`	372	`link(h,ha);`
373	`link(ha, h0);`	373	`link(ha, h0);`
374	`ha->face = f;`	374	`ha->face = f;`
375	`ha->vert = v0;`	375	`ha->vert = v0;`
376	`f->last = ha;`	376	`f->last = ha;`
377		377
378	`// Create a new face, f2, and set all halfedges in the remaining part of`	378	`// Create a new face, f2, and set all halfedges in the remaining part of`
379	`// the polygon to point to this face.`	379	`// the polygon to point to this face.`
380	`h = h1;`	380	`h = h1;`
381	`FaceIter f2 = create_face();`	381	`FaceIter f2 = create_face();`
382	`while(h->vert != v0)`	382	`while(h->vert != v0)`
383	`{`	383	`{`
384	`h->face = f2;`	384	`h->face = f2;`
385	`h = h->next;`	385	`h = h->next;`
386	`}`	386	`}`
387	`h->face = f2;`	387	`h->face = f2;`
388	`assert(h != h1);`	388	`assert(h != h1);`
389		389
390	`// Create a new halfedge hb to connect v0 and v1. this new halfedge`	390	`// Create a new halfedge hb to connect v0 and v1. this new halfedge`
391	`// becomes f2->last`	391	`// becomes f2->last`
392	`HalfEdgeIter hb = create_halfedge();`	392	`HalfEdgeIter hb = create_halfedge();`
393	`link(h,hb);`	393	`link(h,hb);`
394	`link(hb, h1);`	394	`link(hb, h1);`
395	`hb->face = f2;`	395	`hb->face = f2;`
396	`hb->vert = v1;`	396	`hb->vert = v1;`
397	`f2->last = hb;`	397	`f2->last = hb;`
398		398
399	`// Complete the operation by gluing the two new halfedges.`	399	`// Complete the operation by gluing the two new halfedges.`
400	`glue(ha, hb);`	400	`glue(ha, hb);`
401		401
402	`// Assert that the pointers are sane :-)`	402	`// Assert that the pointers are sane :-)`
403	`assert(h1->prev->opp->next == h0);`	403	`assert(h1->prev->opp->next == h0);`
404	`assert(h0->prev->opp->next == h1);`	404	`assert(h0->prev->opp->next == h1);`
405	`assert(hb->next->face == f2);`	405	`assert(hb->next->face == f2);`
406	`assert(hb->next->next->face == f2);`	406	`assert(hb->next->next->face == f2);`
407	`assert(hb->face == f2);`	407	`assert(hb->face == f2);`
408		408
409	`// Return the newly created face`	409	`// Return the newly created face`
410	`return f2;`	410	`return f2;`
411	`}`	411	`}`
412		412
413	`void Manifold::triangulate(FaceIter f)`	413	`void Manifold::triangulate(FaceIter f)`
414	`{`	414	`{`
415	`// Assert sanity of pointers`	415	`// Assert sanity of pointers`
416	`assert(f->last->next->next != f->last);`	416	`assert(f->last->next->next != f->last);`
417	`assert(f->last->next != f->last);`	417	`assert(f->last->next != f->last);`
418	`assert(--(++f) == f);`	418	`assert(--(++f) == f);`
419	`// As long as f is not a triangle.`	419	`// As long as f is not a triangle.`
420	`while(f->last->next->next->next != f->last)`	420	`while(f->last->next->next->next != f->last)`
421	`{`	421	`{`
422	`assert(no_edges(f) != 3);`	422	`assert(no_edges(f) != 3);`
423	`// Call split face to split f into a triangle`	423	`// Call split face to split f into a triangle`
424	`// from the first three vertices and a polygon`	424	`// from the first three vertices and a polygon`
425	`// containing the rest of the vertices. In the`	425	`// containing the rest of the vertices. In the`
426	`// next iteration, f becomes this polygon.`	426	`// next iteration, f becomes this polygon.`
427		427
428	`assert(f->last->next->next != f->last);`	428	`assert(f->last->next->next != f->last);`
429	`VertexIter v0 = f->last->vert;`	429	`VertexIter v0 = f->last->vert;`
430	`VertexIter v1 = f->last->next->next->vert;`	430	`VertexIter v1 = f->last->next->next->vert;`
431	`assert(v0 != v1);`	431	`assert(v0 != v1);`
432	`f = split_face(f, v0, v1);`	432	`f = split_face(f, v0, v1);`
433	`}`	433	`}`
434	`}`	434	`}`
435		435
436	`bool Manifold::merge_faces(FaceIter f1, HalfEdgeIter h)`	436	`bool Manifold::merge_faces(FaceIter f1, HalfEdgeIter h)`
437	`{`	437	`{`
438	`assert(h->face == f1);`	438	`assert(h->face == f1);`
439		439
440	`HalfEdgeIter ho = h->opp;`	440	`HalfEdgeIter ho = h->opp;`
441	`FaceIter f2 = ho->face;`	441	`FaceIter f2 = ho->face;`
442	`HalfEdgeIter hn = h->next;`	442	`HalfEdgeIter hn = h->next;`
443	`HalfEdgeIter hon = ho->next;`	443	`HalfEdgeIter hon = ho->next;`
444		444
445	`if(hn->vert == hon->vert) return false;`	445	`if(hn->vert == hon->vert) return false;`
446		446
447	`HalfEdgeIter hp = h->prev;`	447	`HalfEdgeIter hp = h->prev;`
448	`HalfEdgeIter hop = ho->prev;`	448	`HalfEdgeIter hop = ho->prev;`
449	`VertexIter v = h->vert;`	449	`VertexIter v = h->vert;`
450	`VertexIter vo = ho->vert;`	450	`VertexIter vo = ho->vert;`
451		451
452	`link(hop, hn);`	452	`link(hop, hn);`
453	`v->he = hn;`	453	`v->he = hn;`
454		454
455	`link(hp, hon);`	455	`link(hp, hon);`
456	`vo->he = hon;`	456	`vo->he = hon;`
457		457
458	`f1->last = hn;`	458	`f1->last = hn;`
459	`HalfEdgeIter hx = hon;`	459	`HalfEdgeIter hx = hon;`
460	`assert(hx->face == f2);`	460	`assert(hx->face == f2);`
461	`while(hx->face != f1)`	461	`while(hx->face != f1)`
462	`{`	462	`{`
463	`hx->face = f1;`	463	`hx->face = f1;`
464	`hx = hx->next;`	464	`hx = hx->next;`
465	`}`	465	`}`
466		466
467	`v->check_boundary_consistency();`	467	`check_boundary_consistency(v);`
468	`vo->check_boundary_consistency();`	468	`check_boundary_consistency(vo);`
469		469
470	`erase_halfedge(h);`	470	`erase_halfedge(h);`
471	`erase_halfedge(ho);`	471	`erase_halfedge(ho);`
472	`erase_face(f2);`	472	`erase_face(f2);`
473		473
474	`return true;`	474	`return true;`
475	`}`	475	`}`
476		476
477		477
478	`VertexIter Manifold::safe_triangulate(FaceIter f)`	478	`VertexIter Manifold::safe_triangulate(FaceIter f)`
479	`{`	479	`{`
480	`Vec3f p;`	480	`Vec3f p;`
481	`FaceCirculator fc(f);`	481	`FaceCirculator fc(f);`
482	`for(;!fc.end(); ++fc)`	482	`for(;!fc.end(); ++fc)`
483	`p += fc.get_vertex()->get_pos();`	483	`p += fc.get_vertex()->pos;`
484	`int n = fc.no_steps();`	484	`int n = fc.no_steps();`
485	`p /= n;`	485	`p /= n;`
486	`VertexIter v = create_vertex(p);`	486	`VertexIter v = create_vertex(p);`
487	`face_insert_point(f,v);`	487	`face_insert_point(f,v);`
488	`return v;`	488	`return v;`
489	`}`	489	`}`
490		490
491		491
492	`void Manifold::face_insert_point(FaceIter f, VertexIter v)`	492	`void Manifold::face_insert_point(FaceIter f, VertexIter v)`
493	`{`	493	`{`
494	`vector<HalfEdgeIter> eout;`	494	`vector<HalfEdgeIter> eout;`
495	`vector<HalfEdgeIter> ein;`	495	`vector<HalfEdgeIter> ein;`
496		496
497	`HalfEdgeIter hlast = f->last;`	497	`HalfEdgeIter hlast = f->last;`
498	`HalfEdgeIter h = hlast;`	498	`HalfEdgeIter h = hlast;`
499		499
500	`do`	500	`do`

Subversion Repositories gelsvn

(root)/trunk/src/HMesh/Manifold.cpp – Rev 59 → 62