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

Subversion Repositories gelsvn

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