Subversion Repositories gelsvn

Rev

Rev 136 | Rev 561 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 136 Rev 178
Line 8... Line 8...
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::remove_unused()
14 
	{
 14 
	{
- 
 
 15 
    for(size_t i=0;i<unused_vertices.size(); ++i)
15 
		VertexIter vi = vertices_begin();
 16 
			vertex_db.erase(unused_vertices[i]);
- 
 
 17 
 
- 
 
 18 
    std::vector<VertexIter> vdummy(0);
- 
 
 19 
    unused_vertices = vdummy;
- 
 
 20 
 
- 
 
 21 
    for(size_t i=0;i<unused_faces.size(); ++i)
- 
 
 22 
			face_db.erase(unused_faces[i]);
- 
 
 23 
 
- 
 
 24 
    std::vector<FaceIter> fdummy(0);
- 
 
 25 
    unused_faces = fdummy;
- 
 
 26 
 
- 
 
 27 
    for(size_t i=0;i<unused_halfedges.size(); ++i)
- 
 
 28 
			halfedge_db.erase(unused_halfedges[i]);
- 
 
 29 
 
- 
 
 30 
    std::vector<HalfEdgeIter> hdummy(0);
- 
 
 31 
    unused_halfedges = hdummy;
- 
 
 32 
	}
- 
 
 33
- 
 
 34 
	void Manifold::clear()
- 
 
 35 
	{
- 
 
 36 
		vertex_db.clear();
- 
 
 37 
		face_db.clear();
- 
 
 38 
		halfedge_db.clear();
- 
 
 39 
 
- 
 
 40 
		std::vector<VertexIter> vdummy(0);
- 
 
 41 
		unused_vertices = vdummy;
- 
 
 42
- 
 
 43 
		std::vector<FaceIter> fdummy(0);
16 
		pmin = pmax = vi->pos;
 44 
		unused_faces = fdummy;
- 
 
 45 
 
- 
 
 46 
		std::vector<HalfEdgeIter> hdummy(0);
- 
 
 47 
		unused_halfedges = hdummy;
- 
 
 48 
	}
- 
 
 49 
 
- 
 
 50 
 
- 
 
 51 
	void Manifold::erase_halfedge(HalfEdgeIter h)
- 
 
 52 
	{
- 
 
 53 
		if(erase_immediately)
- 
 
 54 
			halfedge_db.erase(h);
- 
 
 55 
		else
- 
 
 56 
			{
- 
 
 57 
				unused_halfedges.push_back(h);
- 
 
 58 
				HalfEdge h_dummy;
- 
 
 59 
				(*h) = h_dummy;
- 
 
 60 
			}
- 
 
 61 
	}
- 
 
 62 
 
- 
 
 63 
	void Manifold::erase_vertex(VertexIter v)
- 
 
 64 
	{
- 
 
 65 
		if(erase_immediately)
- 
 
 66 
			vertex_db.erase(v);
- 
 
 67 
		else
- 
 
 68 
			{
17 
		for(++vi;vi != vertices_end(); ++vi)
 69 
				unused_vertices.push_back(v);
- 
 
 70 
				Vertex v_dummy(v->pos);
- 
 
 71 
				(*v) = v_dummy;
- 
 
 72 
			}
- 
 
 73 
	}
- 
 
 74 
 
- 
 
 75 
	void Manifold::erase_face(FaceIter f)
- 
 
 76 
	{
- 
 
 77 
		if(erase_immediately)
- 
 
 78 
			face_db.erase(f);
- 
 
 79 
		else
18 
			{
 80 
			{
19 
				pmin = v_min(vi->pos, pmin);
 81 
				unused_faces.push_back(f);
- 
 
 82 
				Face f_dummy;
20 
				pmax = v_max(vi->pos, pmax);
 83 
				(*f) = f_dummy;
21 
			}
 84 
			}
22 
	}
 85 
	}
23 
 
 86 
 
- 
 
 87 
 
- 
 
 88 
 
- 
 
 89 
 
- 
 
 90 
	void Manifold::get_bbox(Vec3f& pmin, Vec3f& pmax)
- 
 
 91 
	{
- 
 
 92 
    VertexIter vi = vertices_begin();
- 
 
 93 
    pmin = pmax = vi->pos;
- 
 
 94 
    for(++vi;vi != vertices_end(); ++vi)
- 
 
 95 
			{
- 
 
 96 
        pmin = v_min(vi->pos, pmin);
- 
 
 97 
        pmax = v_max(vi->pos, pmax);
- 
 
 98 
			}
- 
 
 99 
	}
- 
 
 100 
 
24 
  void Manifold::get_bsphere(CGLA::Vec3f& c, float& r)
101 
	void Manifold::get_bsphere(CGLA::Vec3f& c, float& r)
25 
  {
 102 
	{
26 
    Vec3f p0,p7;
 103 
    Vec3f p0,p7;
27 
    get_bbox(p0, p7);
 104 
    get_bbox(p0, p7);
28 
    Vec3f rad = (p7 - p0)/2.0;
 105 
    Vec3f rad = (p7 - p0)/2.0;
29 
    c = p0 + rad;
 106 
    c = p0 + rad;
30 
    r = rad.length();
 107 
    r = rad.length();
31 
  }
 108 
	}
32 
 
 109 
 
33 
 
 110 
 
34 
	VertexIter Manifold::split_edge(HalfEdgeIter h)
 111 
	VertexIter Manifold::split_edge(HalfEdgeIter h)
35 
	{
 112 
	{
36 
		HalfEdgeIter ho = h->opp;
 113 
    HalfEdgeIter ho = h->opp;
37 
		VertexIter v  = h->vert;
 114 
    VertexIter v  = h->vert;
38 
		VertexIter vo = ho->vert;
 115 
    VertexIter vo = ho->vert;
39 
		Vec3f np = (v->pos+vo->pos)/2.0f;
 116 
    Vec3f np = (v->pos+vo->pos)/2.0f;
40 
 
 117 
 
41 
		VertexIter vn = create_vertex(np);
 118 
    VertexIter vn = create_vertex(np);
42 
		vn->he = h;
 119 
    vn->he = h;
43 
 
 120 
 
44 
		HalfEdgeIter hn = create_halfedge();
 121 
    HalfEdgeIter hn = create_halfedge();
45 
		HalfEdgeIter hno = create_halfedge();
 122 
    HalfEdgeIter hno = create_halfedge();
46 
 
 123 
 
47 
		vo->he = hn;
 124 
    vo->he = hn;
48 
		v->he = ho;
 125 
    v->he = ho;
49
126 
 
50 
		glue(hn,hno);
 127 
    glue(hn,hno);
51 
		link(h->prev, hn);
 128 
    link(h->prev, hn);
52 
		link(hn,h);
 129 
    link(hn,h);
53 
		hn->vert = vn;
 130 
    hn->vert = vn;
54 
 
 131 
 
55 
		link(hno,ho->next);
 132 
    link(hno,ho->next);
56 
		link(ho, hno);
 133 
    link(ho, hno);
57 
		hno->vert = vo;
 134 
    hno->vert = vo;
58 
		ho->vert = vn;
 135 
    ho->vert = vn;
59 
 
 136 
 
60 
		if(h->face != NULL_FACE_ITER)
 137 
    if(h->face != NULL_FACE_ITER)
61 
				h->face->last = hn;
 138 
			h->face->last = hn;
62 
		if(ho->face != NULL_FACE_ITER)
 139 
    if(ho->face != NULL_FACE_ITER)
63 
				ho->face->last = ho;
 140 
			ho->face->last = ho;
64 
 
 141 
 
65 
		hn->face = h->face;
 142 
    hn->face = h->face;
66 
		hno->face = ho->face;
 143 
    hno->face = ho->face;
67 
 
 144 
 
68 
		check_boundary_consistency(vn);
 145 
    check_boundary_consistency(vn);
69 
		check_boundary_consistency(v);
 146 
    check_boundary_consistency(v);
70 
		check_boundary_consistency(vo);
 147 
    check_boundary_consistency(vo);
71 
		return vn;
 148 
    return vn;
72 
	}
 149 
	}
73 
 
 150 
 
74 
 
 151 
 
75 
	void Manifold::remove_face_if_degenerate(HalfEdgeIter h0)
 152 
	void Manifold::remove_face_if_degenerate(HalfEdgeIter h0)
76 
	{
 153 
	{
77 
		if(h0->next->next == h0)
 154 
    if(h0->next->next == h0)
78 
			{
 155 
			{
79 
				HalfEdgeIter h1 = h0->next;
 156 
        HalfEdgeIter h1 = h0->next;
80 
 
 157 
 
81 
				HalfEdgeIter h0o = h0->opp;
 158 
        HalfEdgeIter h0o = h0->opp;
82 
				HalfEdgeIter h1o = h1->opp;
 159 
        HalfEdgeIter h1o = h1->opp;
83 
 
 160 
 
84 
				glue(h0o, h1o);
 161 
        glue(h0o, h1o);
85 
 
 162 
 
86 
				VertexIter v0 = h1->vert;
 163 
        VertexIter v0 = h1->vert;
87 
				VertexIter v1 = h0->vert;
 164 
        VertexIter v1 = h0->vert;
88 
				v0->he = h1o;
 165 
        v0->he = h1o;
89 
				v1->he = h0o;
 166 
        v1->he = h0o;
90
167 
 
91 
				if(h0->face != NULL_FACE_ITER)
 168 
        if(h0->face != NULL_FACE_ITER)
92 
					erase_face(h0->face);
 169 
					erase_face(h0->face);
93 
				erase_halfedge(h0);
 170 
        erase_halfedge(h0);
94 
				erase_halfedge(h1);
 171 
        erase_halfedge(h1);
95
172 
 
96 
				check_boundary_consistency(v0);
 173 
        check_boundary_consistency(v0);
97 
				check_boundary_consistency(v1);
 174 
        check_boundary_consistency(v1);
98 
 
 175 
 
99 
			}
 176 
			}
100 
	}
 177 
	}
101 
 
 178 
 
102 
	bool Manifold::collapse_precond(VertexIter v1, HalfEdgeIter h)
 179 
	bool Manifold::collapse_precond(HalfEdgeIter h)
103 
	{
180 
	{
- 
 
 181 
    VertexIter v1 = h->opp->vert;
104 
		VertexIter v2 = h->vert;
 182 
    VertexIter v2 = h->vert;
105 
 
 183 
 
106 
		std::vector<Vertex*> link1;
 184 
    std::vector<Vertex*> link1;
107 
		VertexCirculator vc1(v1);
 185 
    VertexCirculator vc1(v1);
108 
		for(;!vc1.end();++vc1)
 186 
    for(;!vc1.end();++vc1)
109 
			link1.push_back(&(*vc1.get_vertex()));
 187 
			link1.push_back(&(*vc1.get_vertex()));
110 
		assert(link1.size()>=2);
 188 
    assert(link1.size()>=2);
111 
 
 189 
 
112 
		std::vector<Vertex*> link2;
 190 
    std::vector<Vertex*> link2;
113 
		VertexCirculator vc2(v2);
 191 
    VertexCirculator vc2(v2);
114 
		for(;!vc2.end();++vc2)
 192 
    for(;!vc2.end();++vc2)
115 
			link2.push_back(&(*vc2.get_vertex()));
 193 
			link2.push_back(&(*vc2.get_vertex()));
116 
		assert(link2.size()>=2);
 194 
    assert(link2.size()>=2);
- 
 
 195 
 
- 
 
 196 
    sort(link1.begin(),link1.end());
- 
 
 197 
    sort(link2.begin(),link2.end());
117 
 
 198 
 
118 
		sort(link1.begin(),link1.end());
 199 
    vector<Vertex*> lisect;
119 
		sort(link2.begin(),link2.end());
 200 
    back_insert_iterator<vector<Vertex*> > lii(lisect);
120 
 
 201 
 
121 
		vector<Vertex*> lisect;
 202 
    set_intersection(link1.begin(), link1.end(),
122 
		back_insert_iterator<vector<Vertex*> > lii(lisect);
 203 
                     link2.begin(), link2.end(),
- 
 
 204 
                     lii);
123 
 
 205 
 
124 
		set_intersection(link1.begin(), link1.end(),
 - 
 
125 
										 link2.begin(), link2.end(),
 - 
 
126 
										 lii);
 - 
 
127 
 
 - 
 
128
- 
 
129 
		// If the adjacent face is a triangle (see 2)
 - 
 
130 
		int k=0;
 - 
 
131 
		if(h->next->next->next == h)
 - 
 
132 
		{
 - 
 
133 
			// VALENCY 4 TEST
 - 
 
134 
			if(valency(h->next->vert)<4)
 - 
 
135 
				return false;
 - 
 
136 
 
 - 
 
137 
			vector<Vertex*>::iterator iter;
 - 
 
138 
			iter = find(lisect.begin(),	lisect.end(),&(*h->next->vert));
 - 
 
139 
			assert(iter != lisect.end());
 - 
 
140 
			lisect.erase(iter);
 - 
 
141 
			++k;
 - 
 
142 
 
 - 
 
143 
		}
 - 
 
144 
		// If the adjacent face is a triangle (see 2)
 - 
 
145 
		if(h->opp->next->next->next == h->opp)
 - 
 
146 
		{
 - 
 
147 
			// VALENCY 4 TEST
 - 
 
148 
			if(valency(h->opp->next->vert)<4)
 - 
 
149 
				return false;
 - 
 
150 
 
 - 
 
151 
			vector<Vertex*>::iterator iter;
 - 
 
152 
			iter = find(lisect.begin(),	lisect.end(),&(*h->opp->next->vert));
 - 
 
153 
			assert(iter != lisect.end());
 - 
 
154 
			lisect.erase(iter);
 - 
 
155 
			++k;
 - 
 
156 
 
 206 
 
- 
 
 207 
    // If the adjacent face is a triangle (see 2)
- 
 
 208 
    int k=0;
- 
 
 209 
    if(h->next->next->next == h)
- 
 
 210 
			{
- 
 
 211 
        // VALENCY 4 TEST
- 
 
 212 
        if(valency(h->next->vert)<4)
- 
 
 213 
					return false;
- 
 
 214 
 
- 
 
 215 
        vector<Vertex*>::iterator iter;
- 
 
 216 
        iter = find(lisect.begin(),	lisect.end(),&(*h->next->vert));
- 
 
 217 
        assert(iter != lisect.end());
- 
 
 218 
        lisect.erase(iter);
- 
 
 219 
        ++k;
- 
 
 220 
 
157 
		}
 221 
			}
- 
 
 222 
    // If the adjacent face is a triangle (see 2)
- 
 
 223 
    if(h->opp->next->next->next == h->opp)
- 
 
 224 
			{
- 
 
 225 
        // VALENCY 4 TEST
- 
 
 226 
        if(valency(h->opp->next->vert)<4)
- 
 
 227 
					return false;
- 
 
 228 
 
- 
 
 229 
        vector<Vertex*>::iterator iter;
- 
 
 230 
        iter = find(lisect.begin(),	lisect.end(),&(*h->opp->next->vert));
- 
 
 231 
        assert(iter != lisect.end());
- 
 
 232 
        lisect.erase(iter);
- 
 
 233 
        ++k;
- 
 
 234 
 
- 
 
 235 
			}
158 
		if(lisect.size() !=0) // See 3.
 236 
    if(lisect.size() !=0) // See 3.
159 
			return false;
 237 
			return false;
160 
 
 238 
 
161 
		// TETRAHEDRON TEST
 239 
    // TETRAHEDRON TEST
162 
		if(k==2 && (link1.size()+link2.size()==6))
240 
    if(k==2 && (link1.size()+link2.size()==6))
163 
			return false;
 241 
			return false;
164 
 
 242 
 
165 
		// Test that we are not merging holes (see 6)
 243 
    // Test that we are not merging holes (see 6)
166 
		if(is_boundary(v1) && is_boundary(v2) &&
 244 
    if(is_boundary(v1) && is_boundary(v2) &&
167 
			 (h->face != NULL_FACE_ITER) &&
 245 
			 (h->face != NULL_FACE_ITER) &&
168 
			 (h->opp->face != NULL_FACE_ITER))
 246 
			 (h->opp->face != NULL_FACE_ITER))
169 
			return false;
 247 
			return false;
170
248 
 
171
249 
 
172 
		return true;
 250 
    return true;
173 
	}
 251 
	}
174 
 
 252 
 
175 
 
 253 
 
176 
 	void Manifold::collapse_halfedge(VertexIter v, HalfEdgeIter h,
254 
	void Manifold::collapse_halfedge(HalfEdgeIter h, bool avg_vertices)
177 
																	 bool avg_vertices)
 - 
 
178 
	{
 255 
	{
- 
 
 256 
    VertexIter v = h->opp->vert;
179 
		HalfEdgeIter ho = h->opp;
 257 
    HalfEdgeIter ho = h->opp;
180 
		VertexIter n = h->vert;
 258 
    VertexIter n = h->vert;
181 
 
 259 
 
182 
		if(avg_vertices)
 260 
    if(avg_vertices)
183 
			n->pos = ((v->pos + n->pos) / 2.0f);
 261 
			n->pos = ((v->pos + n->pos) / 2.0f);
184
- 
 
185 
		HalfEdgeIter hn = h->next;
 - 
 
186 
		HalfEdgeIter hp = h->prev;
 - 
 
187 
		HalfEdgeIter hon = ho->next;
 - 
 
188 
		HalfEdgeIter hop = ho->prev;
 - 
 
189 
 
 262 
 
- 
 
 263 
    HalfEdgeIter hn = h->next;
- 
 
 264 
    HalfEdgeIter hp = h->prev;
- 
 
 265 
    HalfEdgeIter hon = ho->next;
- 
 
 266 
    HalfEdgeIter hop = ho->prev;
- 
 
 267 
 
190 
		VertexCirculator vc(v);
 268 
    VertexCirculator vc(v);
191 
		for(;!vc.end();++vc)
 269 
    for(;!vc.end();++vc)
192 
			vc.get_opp_halfedge()->vert = n;
 270 
			vc.get_opp_halfedge()->vert = n;
193 
 
 271 
 
194 
		n->he = h->next;
 272 
    n->he = h->next;
195 
 
 273 
 
196 
		link(hp, hn);
 274 
    link(hp, hn);
197 
		if(h->face != NULL_FACE_ITER)
 275 
    if(h->face != NULL_FACE_ITER)
198 
			h->face->last = hn;
 276 
			h->face->last = hn;
199 
 
 277 
 
200 
		link(hop, hon);
 278 
    link(hop, hon);
201 
		if(ho->face != NULL_FACE_ITER)
 279 
    if(ho->face != NULL_FACE_ITER)
202 
			ho->face->last = hon;
 280 
			ho->face->last = hon;
203 
 
 281 
 
204 
 
 282 
 
205 
 
 283 
 
206 
		erase_vertex(v);
 284 
    erase_vertex(v);
207 
 		erase_halfedge(h);
 285 
    erase_halfedge(h);
208 
 		erase_halfedge(ho);
 286 
    erase_halfedge(ho);
209 
 
 287 
 
210 
		remove_face_if_degenerate(hn);
 288 
    remove_face_if_degenerate(hn);
211 
		remove_face_if_degenerate(hon);
 289 
    remove_face_if_degenerate(hon);
212 
 
 290 
 
213 
		check_boundary_consistency(n);
 291 
    check_boundary_consistency(n);
214 
	}
 292 
	}
215 
 
 293 
 
216 
	bool Manifold::is_valid()
 294 
	bool Manifold::is_valid()
217 
	{
 295 
	{
218 
		HalfEdgeIter he0 = halfedges_begin();
 296 
    HalfEdgeIter he0 = halfedges_begin();
219 
		while(he0 != halfedges_end())
 297 
    while(he0 != halfedges_end())
220 
			{
 298 
			{
221 
				if(he0->prev == NULL_HALFEDGE_ITER)
 299 
        if(he0->prev == NULL_HALFEDGE_ITER)
222 
					{
 300 
					{
223 
						cout << "Halfedge lacks previous" << endl;
 301 
            cout << "Halfedge lacks previous" << endl;
224 
						return false;
 302 
            return false;
225 
					}
 303 
					}
226 
				if(he0->next == NULL_HALFEDGE_ITER)
 304 
        if(he0->next == NULL_HALFEDGE_ITER)
227 
					{
 305 
					{
228 
						cout << "Halfedge lacks next" << endl;
 306 
            cout << "Halfedge lacks next" << endl;
229 
						return false;
 307 
            return false;
230 
					}
 308 
					}
231 
				if(he0->opp == NULL_HALFEDGE_ITER)
 309 
        if(he0->opp == NULL_HALFEDGE_ITER)
232 
					{
 310 
					{
233 
						cout << "Halfedge lacks opposite" << endl;
 311 
            cout << "Halfedge lacks opposite" << endl;
234 
						return false;
 312 
            return false;
235 
					}
 313 
					}
236 
				if(he0->vert == NULL_VERTEX_ITER)
 314 
        if(he0->vert == NULL_VERTEX_ITER)
237 
					{
 315 
					{
238 
						cout << "Halfedge lacks vertex" << endl;
 316 
            cout << "Halfedge lacks vertex" << endl;
239 
						return false;
 317 
            return false;
240 
					}
318 
					}
241 
				++he0;
 319 
        ++he0;
242 
			}
 320 
			}
243
321 
 
244 
		VertexIter vi = vertices_begin();
 322 
    VertexIter vi = vertices_begin();
245 
		while(vi != vertices_end())
 323 
    while(vi != vertices_end())
246 
			{
 324 
			{
247 
				std::vector<Vertex*> link;
 325 
        std::vector<Vertex*> link;
248 
				VertexCirculator vc(vi);
 326 
        VertexCirculator vc(vi);
249 
				int k=0;
 327 
        int k=0;
250 
				for(;!vc.end();++vc,++k)
 328 
        for(;!vc.end();++vc,++k)
251 
					{
 329 
					{
252 
						if(vc.get_halfedge() == NULL_HALFEDGE_ITER)
 330 
            if(vc.get_halfedge() == NULL_HALFEDGE_ITER)
253 
							{
 331 
							{
254 
								cout << "Vertex has null outgoing he" << endl;
 332 
                cout << "Vertex has null outgoing he" << endl;
255 
								return false;
 333 
                return false;
256 
							}
 334 
							}
257 
						Vertex* x = &(*vc.get_vertex());
 335 
            Vertex* x = &(*vc.get_vertex());
258 
						if(find(link.begin(), link.end(), x) != link.end())
 336 
            if(find(link.begin(), link.end(), x) != link.end())
259 
							{
 337 
							{
260 
								cout << "Vertex appears two times in one-ring of other vertex" << endl;
 338 
                cout << "Vertex appears two times in one-ring of other vertex" << endl;
261 
 								return false;
 339 
                return false;
262 
							}
 340 
							}
263 
						link.push_back(x);
 341 
            link.push_back(x);
264 
						if(k==1e6)
342 
            if(k==1e6)
265 
							{
 343 
							{
266 
								cout << "infin. loop around vertex" << endl;
 344 
                cout << "infin. loop around vertex" << endl;
267 
								return false;
 345 
                return false;
268 
							}
 346 
							}
269 
					}
 347 
					}
270 
				if(link.size()==2)
 348 
        if(link.size()==2)
271 
					{
 349 
					{
- 
 
 350 
						if(!is_boundary(vi))
272 
						cout << "Warning: A vertex with only two incident edges" << endl;
 351 
							cout << "Warning: A vertex with only two incident edges" << endl;
- 
 
 352 
						else
- 
 
 353 
							cout << "Comment: A boundary vertex with only two incident edges" << endl;
273 
					}
 354 
					}
274 
				assert(link.size()>=2);
 355 
        assert(link.size()>=2);
275 
				++vi;
 356 
        ++vi;
276 
			}
 357 
			}
277 
 
 358 
 
278 
		HMesh::FaceIter f = faces_begin();
 359 
    HMesh::FaceIter f = faces_begin();
279 
			for(;f != faces_end(); ++f)
 360 
    for(;f != faces_end(); ++f)
280 
				{
 361 
			{
281 
					if(no_edges(f)<3)
 362 
        if(no_edges(f)<3)
282 
						{
 363 
					{
283 
							cout << "Degenerate face" << endl;
 364 
            cout << "Degenerate face" << endl;
284 
						}
 365 
					}
285 
					FaceCirculator fc(f);
 366 
        FaceCirculator fc(f);
286 
					int k=0;
 367 
        int k=0;
287 
					while(!fc.end())
 368 
        while(!fc.end())
288 
						{
 369 
					{
289 
							if(fc.get_halfedge()->face != f)
 370 
            if(fc.get_halfedge()->face != f)
290 
								{
 371 
							{
291 
									cout << "Inconsistent face" << endl;
 372 
                cout << "Inconsistent face" << endl;
292 
									return false;
 373 
                return false;
293 
								}
 374 
							}
294 
							if(++k==1e6) cout << "infin. loop around face" << endl;
 375 
            if(++k==1e6) cout << "infin. loop around face" << endl;
295 
							++fc;
 376 
            ++fc;
296 
						}
 377 
					}
297 
				}
 378 
			}
298 
		return true;
 379 
    return true;
299 
	}
 380 
	}
300 
 
 381 
 
301 
	FaceIter Manifold::split_face(FaceIter f, VertexIter v0, VertexIter v1)
 382 
	FaceIter Manifold::split_face(FaceIter f, VertexIter v0, VertexIter v1)
302 
	{
 383 
	{
303 
		// Make sure this is not a triangle
384 
    // Make sure this is not a triangle
304 
		assert(no_edges(f)>3);
 385 
    assert(no_edges(f)>3);
305 
 
 386 
 
306 
		// Make sure we are not trying to connect a vertex to itself.
 387 
    // Make sure we are not trying to connect a vertex to itself.
307 
		assert(v0 != v1);
 388 
    assert(v0 != v1);
308 
 
 389 
 
309 
		// Find the halfedge emanating from v0 which belongs to the
 390 
    // Find the halfedge emanating from v0 which belongs to the
310 
		// face, we need to split.
391 
    // face, we need to split.
311 
		VertexCirculator vc0(v0);
 392 
    VertexCirculator vc0(v0);
312 
		while(vc0.get_halfedge()->face != f && !vc0.end()) vc0++;
 393 
    while(vc0.get_halfedge()->face != f && !vc0.end()) vc0++;
313 
		assert(!vc0.end());
 394 
    assert(!vc0.end());
314 
		HalfEdgeIter h0 = vc0.get_halfedge();
 395 
    HalfEdgeIter h0 = vc0.get_halfedge();
315 
		assert(h0->face == f); // Sanity check.
 396 
    assert(h0->face == f); // Sanity check.
316 
 
 397 
 
317 
		// The halfedge belonging to f, going out from v0, is denoted h.
 398 
    // The halfedge belonging to f, going out from v0, is denoted h.
318 
		// Move along h until we hit v1. Now we have the halfedge which
 399 
    // Move along h until we hit v1. Now we have the halfedge which
319 
		// belongs to f and points to v1.
 400 
    // belongs to f and points to v1.
320 
		HalfEdgeIter h = h0;
 401 
    HalfEdgeIter h = h0;
321 
		while(h->vert != v1)
402 
    while(h->vert != v1)
322 
			h = h->next;
 403 
			h = h->next;
323 
 
 404 
 
324 
		// Create a new halfedge ha which connects v1 and v0 closing the first
 405 
    // Create a new halfedge ha which connects v1 and v0 closing the first
325 
		// loop. This new halfedge becomes f->last
 406 
    // loop. This new halfedge becomes f->last
326 
		assert(h != h0);
 407 
    assert(h != h0);
327 
		HalfEdgeIter h1 = h->next;
 408 
    HalfEdgeIter h1 = h->next;
328 
		HalfEdgeIter ha = create_halfedge();
 409 
    HalfEdgeIter ha = create_halfedge();
329 
		link(h,ha);
 410 
    link(h,ha);
330 
		link(ha, h0);
 411 
    link(ha, h0);
331 
		ha->face = f;
 412 
    ha->face = f;
332 
		ha->vert = v0;
 413 
    ha->vert = v0;
333 
		f->last = ha;
 414 
    f->last = ha;
334 
 
 415 
 
335 
		// Create a new face, f2, and set all halfedges in the remaining part of
416 
    // Create a new face, f2, and set all halfedges in the remaining part of
336 
		// the polygon to point to this face.
417 
    // the polygon to point to this face.
337 
		h = h1;
 418 
    h = h1;
338 
		FaceIter f2 = create_face();
 419 
    FaceIter f2 = create_face();
339 
		while(h->vert != v0)
420 
    while(h->vert != v0)
340 
			{
 421 
			{
341 
				h->face = f2;
 422 
        h->face = f2;
342 
				h = h->next;
 423 
        h = h->next;
343 
			}
 424 
			}
344 
		h->face = f2;
 425 
    h->face = f2;
345 
		assert(h != h1);
 426 
    assert(h != h1);
346
427 
 
347 
		// Create a new halfedge hb to connect v0 and v1. this new halfedge
428 
    // Create a new halfedge hb to connect v0 and v1. this new halfedge
348 
		// becomes f2->last
 429 
    // becomes f2->last
349 
		HalfEdgeIter hb = create_halfedge();
 430 
    HalfEdgeIter hb = create_halfedge();
350 
		link(h,hb);
 431 
    link(h,hb);
351 
		link(hb, h1);
 432 
    link(hb, h1);
352 
		hb->face = f2;
 433 
    hb->face = f2;
353 
		hb->vert = v1;
 434 
    hb->vert = v1;
354 
		f2->last = hb;
 435 
    f2->last = hb;
355 
 
 436 
 
356 
		// Complete the operation by gluing the two new halfedges.
 437 
    // Complete the operation by gluing the two new halfedges.
357 
		glue(ha, hb);
 438 
    glue(ha, hb);
358 
 
 439 
 
359 
		// Assert that the pointers are sane :-)
 440 
    // Assert that the pointers are sane :-)
360 
		assert(h1->prev->opp->next == h0);
 441 
    assert(h1->prev->opp->next == h0);
361 
		assert(h0->prev->opp->next == h1);
 442 
    assert(h0->prev->opp->next == h1);
362 
		assert(hb->next->face == f2);
 443 
    assert(hb->next->face == f2);
363 
		assert(hb->next->next->face == f2);
 444 
    assert(hb->next->next->face == f2);
364 
		assert(hb->face == f2);
 445 
    assert(hb->face == f2);
365 
 
 446 
 
366 
		// Return the newly created face
 447 
    // Return the newly created face
367 
		return f2;
 448 
    return f2;
368 
	}
 449 
	}
369 
 
 450 
 
370 
	void Manifold::triangulate(FaceIter f)
 451 
	void Manifold::triangulate(FaceIter f)
371 
	{
 452 
	{
372 
		// Assert sanity of pointers
 453 
    // Assert sanity of pointers
373 
		assert(f->last->next->next != f->last);
 454 
    assert(f->last->next->next != f->last);
374 
		assert(f->last->next != f->last);
 455 
    assert(f->last->next != f->last);
375 
		assert(--(++f) == f);
 456 
    assert(--(++f) == f);
376 
		// As long as f is not a triangle.
 457 
    // As long as f is not a triangle.
377 
		while(f->last->next->next->next != f->last)
 458 
    while(f->last->next->next->next != f->last)
378 
			{
 459 
			{
379 
				assert(no_edges(f) != 3);
 460 
        assert(no_edges(f) != 3);
380 
				// Call split face to split f into a triangle
 461 
        // Call split face to split f into a triangle
381 
				// from the first three vertices and a polygon
 462 
        // from the first three vertices and a polygon
382 
				// containing the rest of the vertices. In the
 463 
        // containing the rest of the vertices. In the
383 
				// next iteration, f becomes this polygon.
 464 
        // next iteration, f becomes this polygon.
384
465 
 
385 
				assert(f->last->next->next != f->last);
 466 
        assert(f->last->next->next != f->last);
386 
				VertexIter v0 = f->last->vert;
 467 
        VertexIter v0 = f->last->vert;
387 
				VertexIter v1 = f->last->next->next->vert;
 468 
        VertexIter v1 = f->last->next->next->vert;
388 
				assert(v0 != v1);
 469 
        assert(v0 != v1);
389 
				f = split_face(f, v0, v1);
 470 
        f = split_face(f, v0, v1);
390 
			}
 471 
			}
391 
	}
 472 
	}
392 
 
 473 
 
393 
	bool Manifold::merge_faces(FaceIter f1, HalfEdgeIter h)
 474 
	bool Manifold::merge_faces(FaceIter f1, HalfEdgeIter h)
394 
	{
 475 
	{
395 
		assert(h->face == f1);
 476 
    assert(h->face == f1);
396
477 
 
397 
		HalfEdgeIter ho = h->opp;
 478 
    HalfEdgeIter ho = h->opp;
398 
		FaceIter f2 = ho->face;
 479 
    FaceIter f2 = ho->face;
399 
		HalfEdgeIter hn = h->next;
 480 
    HalfEdgeIter hn = h->next;
400 
		HalfEdgeIter hon = ho->next;
 481 
    HalfEdgeIter hon = ho->next;
401
482 
 
402 
		if(hn->vert == hon->vert) return false;
 483 
    if(hn->vert == hon->vert) return false;
403 
 
 484 
 
404 
		HalfEdgeIter hp = h->prev;
 485 
    HalfEdgeIter hp = h->prev;
405 
		HalfEdgeIter hop = ho->prev;
 486 
    HalfEdgeIter hop = ho->prev;
406 
		VertexIter v  = h->vert;
 487 
    VertexIter v  = h->vert;
407 
		VertexIter vo = ho->vert;
 488 
    VertexIter vo = ho->vert;
408
489 
 
409 
		link(hop, hn);
 490 
    link(hop, hn);
410 
		v->he = hn;
 491 
    v->he = hn;
411 
 
 492 
 
412 
		link(hp, hon);
 493 
    link(hp, hon);
413 
		vo->he = hon;
 494 
    vo->he = hon;
414 
 
 495 
 
415 
		f1->last = hn;
 496 
    f1->last = hn;
416 
		HalfEdgeIter hx = hon;
 497 
    HalfEdgeIter hx = hon;
417 
		assert(hx->face == f2);
 498 
    assert(hx->face == f2);
418 
		while(hx->face != f1)
 499 
    while(hx->face != f1)
419 
			{
 500 
			{
420 
				hx->face = f1;
 501 
        hx->face = f1;
421 
				hx = hx->next;
 502 
        hx = hx->next;
422 
			}
 503 
			}
423 
 
 504 
 
424 
		check_boundary_consistency(v);
 505 
    check_boundary_consistency(v);
425 
		check_boundary_consistency(vo);
 506 
    check_boundary_consistency(vo);
426 
 
 507 
 
427 
 		erase_halfedge(h);
 508 
    erase_halfedge(h);
428 
 		erase_halfedge(ho);
 509 
    erase_halfedge(ho);
429 
		erase_face(f2);
 510 
    erase_face(f2);
430
511 
 
431 
		return true;
 512 
    return true;
432 
	}
 513 
	}
433 
 
 514 
 
434 
 
 515 
 
435 
	VertexIter Manifold::safe_triangulate(FaceIter f)
 516 
	VertexIter Manifold::safe_triangulate(FaceIter f)
436 
	{
 517 
	{
437 
		Vec3f p;
 518 
    Vec3f p(0.0f);
438 
		FaceCirculator fc(f);
 519 
    FaceCirculator fc(f);
439 
		for(;!fc.end(); ++fc)
 520 
    for(;!fc.end(); ++fc)
440 
			p += fc.get_vertex()->pos;
 521 
			p += fc.get_vertex()->pos;
441 
		int n = fc.no_steps();
 522 
    int n = fc.no_steps();
442 
		p /= n;
 523 
    p /= n;
443 
		VertexIter v = create_vertex(p);
 524 
    VertexIter v = create_vertex(p);
444 
		face_insert_point(f,v);
 525 
    face_insert_point(f,v);
445 
		return v;
 526 
    return v;
446 
	}
 527 
	}
447 
 
 528 
 
448 
 
 529 
 
449 
	void Manifold::face_insert_point(FaceIter f, VertexIter v)
 530 
	void Manifold::face_insert_point(FaceIter f, VertexIter v)
450 
	{
 531 
	{
451 
		vector<HalfEdgeIter> eout;
 532 
    vector<HalfEdgeIter> eout;
452 
		vector<HalfEdgeIter> ein;
 533 
    vector<HalfEdgeIter> ein;
453 
 
 534 
 
454 
		HalfEdgeIter hlast = f->last;
 535 
    HalfEdgeIter hlast = f->last;
455 
		HalfEdgeIter h = hlast;
 536 
    HalfEdgeIter h = hlast;
456 
 
 537 
 
457 
		do
 538 
    do
458 
			{
 539 
			{
459 
				HalfEdgeIter hn = h->next;
 540 
        HalfEdgeIter hn = h->next;
460 
 
 541 
 
461 
				HalfEdgeIter o = create_halfedge();
 542 
        HalfEdgeIter o = create_halfedge();
462 
				HalfEdgeIter i = create_halfedge();
 543 
        HalfEdgeIter i = create_halfedge();
463
544 
 
464 
				FaceIter fn = create_face();
 545 
        FaceIter fn = create_face();
465 
				i->face = fn;
 546 
        i->face = fn;
466 
				i->vert = v;
 547 
        i->vert = v;
467 
				o->face = fn;
 548 
        o->face = fn;
468 
				o->vert = h->opp->vert;
 549 
        o->vert = h->opp->vert;
469 
				h->face = fn;
 550 
        h->face = fn;
470 
				fn->last = o;
 551 
        fn->last = o;
471 
 
 552 
 
472 
				link(i,o);
 553 
        link(i,o);
473 
				link(o,h);
 554 
        link(o,h);
474 
				link(h,i);
 555 
        link(h,i);
475 
 
 556 
 
476 
				eout.push_back(o);
 557 
        eout.push_back(o);
477 
				ein.push_back(i);
 558 
        ein.push_back(i);
478
559 
 
479 
				h = hn;
 560 
        h = hn;
480 
			}
 561 
			}
481 
		while(h != hlast);
 562 
    while(h != hlast);
482 
 
 563 
 
483 
		int N = eout.size();
 564 
    int N = eout.size();
484 
		for(int i=0;i<N;++i)
 565 
    for(int i=0;i<N;++i)
485 
			glue(ein[i],eout[(i+1)%N]);
 566 
			glue(ein[i],eout[(i+1)%N]);
486
567 
 
487 
		v->he = eout[0];
 568 
    v->he = eout[0];
488 
		erase_face(f);
 569 
    erase_face(f);
489 
	}
 570 
	}
490 
 
 571 
 
491 
 
 572 
 
492 
	bool Manifold::flip(HalfEdgeIter h1)
 573 
	bool Manifold::flip(HalfEdgeIter h1)
493 
	{
 574 
	{
494 
		FaceIter f1 = h1->face;
 575 
    FaceIter f1 = h1->face;
495 
		HalfEdgeIter h2 = h1->opp;
 576 
    HalfEdgeIter h2 = h1->opp;
496 
		FaceIter f2 = h2->face;
 577 
    FaceIter f2 = h2->face;
497 
 
 578 
 
498 
		if(f1 == NULL_FACE_ITER || f2 == NULL_FACE_ITER)
 579 
    if(f1 == NULL_FACE_ITER || f2 == NULL_FACE_ITER)
499 
			return false;
 580 
			return false;
500 
 
 581 
 
501 
		// We can only flip an edge if both incident polygons
 582 
    // We can only flip an edge if both incident polygons
502 
		// are triangles. Otherwise, this operation makes no sense.
 583 
    // are triangles. Otherwise, this operation makes no sense.
503 
		if(no_edges(f1) != 3)
 584 
    if(no_edges(f1) != 3)
504 
			return false;
 585 
			return false;
505 
		if(no_edges(f2) !=3)
 586 
    if(no_edges(f2) !=3)
506 
			return false;
 587 
			return false;
507
588 
 
508 
		// If the valency of either vertex incident on the edge
 589 
    // If the valency of either vertex incident on the edge
509 
		// being flipped is three, we cannot perform this operation.
 590 
    // being flipped is three, we cannot perform this operation.
510 
		// That is because the vertex would then have valency two
 591 
    // That is because the vertex would then have valency two
511 
		// after the operation which means it would be degenerate.
 592 
    // after the operation which means it would be degenerate.
512 
		VertexIter va = h1->vert;
 593 
    VertexIter va = h1->vert;
513 
		VertexIter vb = h2->vert;
 594 
    VertexIter vb = h2->vert;
514 
		int vala = valency(va);
 595 
    int vala = valency(va);
515 
		int valb = valency(vb);
 596 
    int valb = valency(vb);
516 
		if((vala <= 3 && !is_boundary(va)) ||
597 
    if((vala <= 3 && !is_boundary(va)) ||
517 
			 (valb <= 3 && !is_boundary(vb)))
 598 
			 (valb <= 3 && !is_boundary(vb)))
518 
			return false;
 599 
			return false;
519
600 
 
520 
		// If the two vertices being connected by the flip are already
 601 
    // If the two vertices being connected by the flip are already
521 
		// connected, the mesh would become degenerate, so we disallow
 602 
    // connected, the mesh would become degenerate, so we disallow
522 
		// the operation.
 603 
    // the operation.
523 
		VertexIter vc = h1->next->vert;
 604 
    VertexIter vc = h1->next->vert;
524 
		VertexIter vd = h2->next->vert;
 605 
    VertexIter vd = h2->next->vert;
525 
		if(is_connected(vc,vd))
 606 
    if(is_connected(vc,vd))
526 
			return false;
 607 
			return false;
527 
 
 608 
 
528 
		HalfEdgeIter ha = h1->next;
 609 
    HalfEdgeIter ha = h1->next;
529 
		HalfEdgeIter hb = h1->prev;
 610 
    HalfEdgeIter hb = h1->prev;
530 
		HalfEdgeIter hc = h2->next;
 611 
    HalfEdgeIter hc = h2->next;
531 
		HalfEdgeIter hd = h2->prev;
 612 
    HalfEdgeIter hd = h2->prev;
532 
 
 613 
 
533 
		hd->face = f1;
 614 
    hd->face = f1;
534 
		hb->face = f2;
 615 
    hb->face = f2;
535 
		f1->last = h1;
 616 
    f1->last = h1;
536 
		f2->last = h2;
 617 
    f2->last = h2;
537 
 
 618 
 
538 
		link(ha,h1);
 619 
    link(ha,h1);
539 
		link(h1,hd);
 620 
    link(h1,hd);
540 
		link(hd,ha);
 621 
    link(hd,ha);
541 
 
 622 
 
542 
		link(hc,h2);
 623 
    link(hc,h2);
543 
		link(h2,hb);
 624 
    link(h2,hb);
544 
		link(hb,hc);
 625 
    link(hb,hc);
545
626 
 
546 
		h1->vert = vd;
 627 
    h1->vert = vd;
547 
		h2->vert = vc;
 628 
    h2->vert = vc;
548 
 
 629 
 
549 
		va->he = ha;
 630 
    va->he = ha;
550 
		vb->he = hc;
 631 
    vb->he = hc;
551 
 
 632 
 
552 
		check_boundary_consistency(va);
 633 
    check_boundary_consistency(va);
553 
		check_boundary_consistency(vb);
 634 
    check_boundary_consistency(vb);
554 
		return true;
 635 
    return true;
555 
	}
 636 
	}
556 
 
 637 
 
557 
		/** Give each vertex a unique id corresponding to its iterator
638 
	/** Give each vertex a unique id corresponding to its iterator
558 
				position */
 639 
			position */
559 
		void Manifold::enumerate_vertices()
 640 
	void Manifold::enumerate_vertices()
560 
		{
 641 
	{
561 
			int i=0;
 642 
    int i=0;
562 
			for(VertexIter vi=vertices_begin(); vi != vertices_end(); ++vi)
 643 
    for(VertexIter vi=vertices_begin(); vi != vertices_end(); ++vi)
563 
				vi->touched = i++;
 644 
			vi->touched = i++;
564 
		}
 645 
	}
565
646 
 
566 
		/** Give each halfedge a unique id corresponding to its iterator
647 
	/** Give each halfedge a unique id corresponding to its iterator
567 
				position */
 648 
			position */
568 
		void Manifold::enumerate_halfedges()
 649 
	void Manifold::enumerate_halfedges()
569 
		{
 650 
	{
570 
			int i=0;
 651 
    int i=0;
571 
			for(HalfEdgeIter h=halfedges_begin(); h != halfedges_end(); ++h)
 652 
    for(HalfEdgeIter h=halfedges_begin(); h != halfedges_end(); ++h)
572 
				h->touched = i++;
 653 
			h->touched = i++;
573 
		}
 654 
	}
574 
 
 655 
 
575 
		/** Give each face a unique id corresponding to its iterator
656 
	/** Give each face a unique id corresponding to its iterator
576 
				position */
 657 
			position */
577 
		void Manifold::enumerate_faces()
 658 
	void Manifold::enumerate_faces()
578 
		{
 659 
	{
579 
			int i=0;
 660 
    int i=0;
580 
			for(FaceIter f=faces_begin(); f != faces_end(); ++f)
 661 
    for(FaceIter f=faces_begin(); f != faces_end(); ++f)
581 
				f->touched = i++;
 662 
			f->touched = i++;
582 
		}
 663 
	}
583 
 
 664 
 
584 
 
 665 
 
585 
}
 666 
}
586 
 
 667