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

Subversion Repositories gelsvn

(root)/trunk/src/HMesh/Manifold.cpp – Rev 113 → 115