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

Subversion Repositories gelsvn

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