Subversion Repositories gelsvn

Rev

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

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