Subversion Repositories gelsvn

Rev

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

Rev 561 Rev 595
Line -... Line 1...
- 
 
 1 
/* ----------------------------------------------------------------------- *
- 
 
 2 
 * This file is part of GEL, http://www.imm.dtu.dk/GEL
1 
#include <iostream>
 3 
 * Copyright (C) the authors and DTU Informatics
- 
 
 4 
 * For license and list of authors, see ../../doc/intro.pdf
- 
 
 5 
 * ----------------------------------------------------------------------- */
2 
#include <iterator>
 6 
#include <iterator>
3 
#include "Manifold.h"
 7 
#include "Manifold.h"
4 
#include "VertexCirculator.h"
 - 
 
5 
#include "FaceCirculator.h"
 - 
 
6 
 
 8 
 
- 
 
 9 
#include <iostream>
- 
 
 10 
#include <vector>
- 
 
 11 
#include <map>
- 
 
 12 
#include <iterator>
- 
 
 13 
 
- 
 
 14 
#include <Geometry/TriMesh.h>
7 
 
 15 
 
8 
namespace HMesh
 16 
namespace HMesh
9 
{
 17 
{
- 
 
 18
10 
	using namespace std;
 19 
    using namespace std;
- 
 
 20 
    using namespace Geometry;
11 
	using namespace CGLA;
 21 
    using namespace CGLA;
12
22
- 
 
 23 
    namespace
- 
 
 24 
    {
- 
 
 25 
        /************************************************************
- 
 
 26 
		 * Edgekeys and Edges for halfedge identification during build
- 
 
 27 
		 ************************************************************/
13 
	void Manifold::remove_unused()
 28 
        class EdgeKey
14 
	{
 29 
        {
- 
 
 30 
        public:
15 
		for(size_t i=0;i<unused_vertices.size(); ++i)
 31 
            EdgeKey(VertexID va, VertexID vb)
- 
 
 32 
            {
16 
			vertex_db.erase(unused_vertices[i]);
 33 
                if(va < vb){
- 
 
 34 
                    v0 = va;
- 
 
 35 
                    v1 = vb;
- 
 
 36 
                }
- 
 
 37 
                else{
- 
 
 38 
                    v0 = vb;
- 
 
 39 
                    v1 = va;
- 
 
 40 
                }
- 
 
 41 
            }
17
42
- 
 
 43 
            bool operator<(const EdgeKey& k2) const
- 
 
 44 
            {
- 
 
 45 
                if(v0 < k2.v0){
- 
 
 46 
                    return true;
- 
 
 47 
                }
- 
 
 48 
                else if( k2.v0 < v0){
- 
 
 49 
                    return false;
- 
 
 50 
                }
- 
 
 51 
                else{
- 
 
 52 
                    return v1 < k2.v1;
- 
 
 53 
                }
- 
 
 54 
            }
- 
 
 55 
        private:
18 
		std::vector<VertexIter> vdummy(0);
 56 
            VertexID v0;
19 
		unused_vertices = vdummy;
 57 
            VertexID v1;
- 
 
 58 
        };
20
59
- 
 
 60 
        struct Edge
- 
 
 61 
        {
- 
 
 62 
            HalfEdgeID h0;
21 
		for(size_t i=0;i<unused_faces.size(); ++i)
 63 
            HalfEdgeID h1;
- 
 
 64 
            int count;
22 
			face_db.erase(unused_faces[i]);
 65 
            Edge() : count(0){}
- 
 
 66 
        };
- 
 
 67 
    }
23
68
24 
		std::vector<FaceIter> fdummy(0);
 69 
    /*********************************************
25 
		unused_faces = fdummy;
 70 
	 * Public functions
- 
 
 71 
	 *********************************************/
- 
 
 72 
    void Manifold::build(const TriMesh& mesh)
- 
 
 73 
    {
- 
 
 74 
        // A vector of 3's - used to tell build how many indices each face consists of
- 
 
 75 
        vector<int> faces(mesh.geometry.no_faces(), 3);
26
76
- 
 
 77 
        build_template( static_cast<size_t>(mesh.geometry.no_vertices()),
- 
 
 78 
					   reinterpret_cast<const float*>(&mesh.geometry.vertex(0)),
27 
		for(size_t i=0;i<unused_halfedges.size(); ++i)
 79 
					   static_cast<size_t>(faces.size()),
28 
			halfedge_db.erase(unused_halfedges[i]);
 80 
					   static_cast<const int*>(&faces[0]),
- 
 
 81 
					   reinterpret_cast<const int*>(&mesh.geometry.face(0)));
- 
 
 82 
    }
29
83
- 
 
 84 
    void Manifold::build(   size_t no_vertices,
30 
		std::vector<HalfEdgeIter> hdummy(0);
 85 
						 const float* vertvec,
- 
 
 86 
						 size_t no_faces,
- 
 
 87 
						 const int* facevec,
31 
		unused_halfedges = hdummy;
 88 
						 const int* indices)
- 
 
 89 
    {
- 
 
 90 
        build_template(no_vertices, vertvec, no_faces, facevec, indices);
32 
	}
 91 
    }
33
92
34 
	void Manifold::clear()
 93 
    void Manifold::build(   size_t no_vertices,
- 
 
 94 
						 const double* vertvec,
- 
 
 95 
						 size_t no_faces,
- 
 
 96 
						 const int* facevec,
- 
 
 97 
						 const int* indices)
35 
	{
 98 
    {
36 
		vertex_db.clear();
 99 
        build_template(no_vertices, vertvec, no_faces, facevec, indices);
37 
		face_db.clear();
 100 
    }
38 
		halfedge_db.clear();
 - 
 
39
101
- 
 
 102 
    FaceID Manifold::add_face(std::vector<Manifold::Vec> points)
- 
 
 103 
    {
- 
 
 104 
        int F = points.size();
40 
		std::vector<VertexIter> vdummy(0);
 105 
        vector<int> indices;
- 
 
 106 
        for(int i=0;i<points.size(); ++i)
41 
		unused_vertices = vdummy;
 107 
            indices.push_back(i);
- 
 
 108 
        FaceID fid = *faces_end();
- 
 
 109 
        build(points.size(), reinterpret_cast<double*>(&points[0]), 1, &F, &indices[0]);
- 
 
 110 
        return fid;
- 
 
 111 
    }
42
112
43 
		std::vector<FaceIter> fdummy(0);
 113 
//    bool remove_face(FaceID fid);
- 
 
 114 
//
44 
		unused_faces = fdummy;
 115 
//    bool remove_edge(HalfEdgeID hid);
- 
 
 116 
//
- 
 
 117 
//    bool remove_vertex(VertexID vid);
45
118 
 
46 
		std::vector<HalfEdgeIter> hdummy(0);
 - 
 
47 
		unused_halfedges = hdummy;
 - 
 
48 
	}
 - 
 
49
119
50
120
51 
	void Manifold::erase_halfedge(HalfEdgeIter h)
 121 
    void Manifold::collapse_edge(HalfEdgeID h, bool avg_vertices)
52 
	{
 - 
 
53 
		if(erase_immediately)
 - 
 
54 
			halfedge_db.erase(h);
 - 
 
55 
		else
 - 
 
56 
		{
 122 
    {
- 
 
 123 
        HalfEdgeID ho = kernel.opp(h);
- 
 
 124 
        VertexID hv = kernel.vert(h);
- 
 
 125 
        VertexID hov = kernel.vert(ho);
- 
 
 126 
        HalfEdgeID hn = kernel.next(h);
- 
 
 127 
        HalfEdgeID hp = kernel.prev(h);
- 
 
 128 
        HalfEdgeID hon = kernel.next(ho);
- 
 
 129 
        HalfEdgeID hop = kernel.prev(ho);
57 
			unused_halfedges.push_back(h);
 130 
		FaceID f = kernel.face(h);
- 
 
 131 
		FaceID fo = kernel.face(ho);
- 
 
 132
- 
 
 133 
        // average the vertex positions
- 
 
 134 
        pos(hv) = avg_vertices ? (0.5f * (pos(hov) + pos(hv))) : pos(hv);
- 
 
 135
- 
 
 136 
        // update all halfedges pointing to hov to point to hv, effectively removing hov from all loops
- 
 
 137 
        HalfEdgeID he = kernel.out(hov);
58 
			HalfEdge h_dummy;
 138 
        HalfEdgeID last = he;
59 
			(*h) = h_dummy;
 139 
		do {
- 
 
 140 
			assert(kernel.vert(kernel.opp(he)) == hov);
- 
 
 141 
            kernel.set_vert(kernel.opp(he), hv);
- 
 
 142 
            he = kernel.next(kernel.opp(he));
60 
		}
 143 
        }
- 
 
 144 
		while(he != last);
- 
 
 145 
        kernel.set_out(hv, hn);
- 
 
 146
- 
 
 147 
        // link hp and hn, effectively removing h from opposite loop
- 
 
 148 
        link(hp, hn);
- 
 
 149 
        // make face owning h own hn instead
- 
 
 150 
        if(kernel.face(h) != InvalidFaceID)
- 
 
 151 
            kernel.set_last(f, hn);
- 
 
 152
- 
 
 153 
        // link hop and hon, effectively removing h from opposite face loop
- 
 
 154 
        link(hop, hon);
- 
 
 155 
        // make opposite face owning h own hon instead
- 
 
 156 
        if(kernel.face(ho) != InvalidFaceID)
- 
 
 157 
            kernel.set_last(fo, hon);
- 
 
 158
- 
 
 159 
        // remove the obsolete entities
- 
 
 160 
        kernel.remove_vertex(hov);
- 
 
 161 
        kernel.remove_halfedge(h);
- 
 
 162 
        kernel.remove_halfedge(ho);
- 
 
 163
- 
 
 164 
        // verify that remaining faces haven't become degenerate because of collapse
- 
 
 165 
        remove_face_if_degenerate(hn);
- 
 
 166 
        remove_face_if_degenerate(hon);
- 
 
 167
- 
 
 168 
        // verify that v is sane after collapse
- 
 
 169 
        ensure_boundary_consistency(hv);
61 
	}
 170 
    }
62
171
63 
	void Manifold::erase_vertex(VertexIter v)
 172 
    FaceID Manifold::split_face_by_edge(FaceID f, VertexID v0, VertexID v1)
64 
	{
 173 
    {
65 
		if(erase_immediately)
 174 
		assert(!connected(*this, v0, v1));
66 
			vertex_db.erase(v);
 175 
        HalfEdgeID he = kernel.last(f);
67 
		else
 176 
        HalfEdgeID last = he;
68 
		{
 - 
 
69 
			unused_vertices.push_back(v);
 177 
        int steps = 0;
70 
			Vertex v_dummy(v->pos);
 178 
        while(he != last || steps == 0){
71 
			(*v) = v_dummy;
 179 
            ++steps;
72 
		}
 - 
 
- 
 
 180 
            he = kernel.next(he);
73 
	}
 181 
        }
74
182
75 
	void Manifold::erase_face(FaceIter f)
 183 
        // make sure this is not a triangle
76 
	{
 - 
 
77 
		if(erase_immediately)
 184 
        assert(steps > 3);
- 
 
 185 
        // make sure we are not trying to connect a vertex to itself
78 
			face_db.erase(f);
 186 
        assert(v0 != v1);
79 
		else
 - 
 
80 
		{
 187
81 
			unused_faces.push_back(f);
 188 
		HalfEdgeID h0 = kernel.out(v0);
- 
 
 189 
		for(Walker w = walker(v0); !w.full_circle(); w = w.circulate_vertex_cw()){
82 
			Face f_dummy;
 190 
			if(w.face() == f){
83 
			(*f) = f_dummy;
 191 
				h0 = w.halfedge();
- 
 
 192 
				break;
84 
		}
 193 
			}
85 
	}
 194 
		}
- 
 
 195 
		assert(kernel.face(h0) != InvalidFaceID);
- 
 
 196 
        assert(kernel.face(h0) == f);
- 
 
 197
- 
 
 198 
        // the halfedge belonging to f, going out from v0, is denoted h. Move along h until we hit v1.
- 
 
 199 
        // now we have the halfedge which belongs to f and points to v1.
- 
 
 200 
        HalfEdgeID h = h0;
- 
 
 201 
        while(kernel.vert(h) != v1){
- 
 
 202 
            h = kernel.next(h);
- 
 
 203 
        }
- 
 
 204 
        assert(h != h0);
- 
 
 205
- 
 
 206 
        // create a new halfedge ha which connects v1 and v0 closing the first loop.
- 
 
 207 
        HalfEdgeID h1 = kernel.next(h);
- 
 
 208 
        HalfEdgeID ha = kernel.add_halfedge();
- 
 
 209 
        link(h, ha);
- 
 
 210 
        link(ha, h0);
- 
 
 211 
        kernel.set_face(ha, f);
- 
 
 212 
        kernel.set_vert(ha, v0);
- 
 
 213 
        kernel.set_last(f, ha);
- 
 
 214
- 
 
 215 
        // create a new face, f2, and set all halfedges in the remaining part of the polygon to point to this face.
- 
 
 216 
        h = h1;
- 
 
 217 
        FaceID f2 = kernel.add_face();
- 
 
 218 
        while(kernel.vert(h) != v0){
- 
 
 219 
            kernel.set_face(h, f2);
- 
 
 220 
            h = kernel.next(h);
- 
 
 221 
        }
- 
 
 222 
        kernel.set_face(h, f2);
- 
 
 223 
        assert(h != h1);
86
224
- 
 
 225 
        // create a new halfedge hb to connect v0 and v1.
- 
 
 226 
        HalfEdgeID hb = kernel.add_halfedge();
- 
 
 227 
        link(h, hb);
- 
 
 228 
        link(hb, h1);
- 
 
 229 
        kernel.set_face(hb, f2);
- 
 
 230 
        kernel.set_vert(hb, v1);
- 
 
 231 
        kernel.set_last(f2, hb);
87
232
- 
 
 233 
        // complete the operation by gluing the two new halfedges
- 
 
 234 
        glue(ha, hb);
88
235
- 
 
 236 
        // assert sanity of operation
- 
 
 237 
        assert(kernel.next(kernel.opp(kernel.prev(h1))) == h0);
- 
 
 238 
        assert(kernel.next(kernel.opp(kernel.prev(h0))) == h1);
- 
 
 239 
        assert(kernel.face(kernel.next(hb)) == f2);
- 
 
 240 
        assert(kernel.face(kernel.next(kernel.next(hb))) == f2);
- 
 
 241 
        assert(kernel.face(hb) == f2);
89
242
90 
	void Manifold::get_bbox(Vec3f& pmin, Vec3f& pmax)
 243 
        // return handle to newly created face
91 
	{
 - 
 
92 
		VertexIter vi = vertices_begin();
 - 
 
93 
		pmin = pmax = vi->pos;
 244 
        return f2;
94 
		for(++vi;vi != vertices_end(); ++vi)
 - 
 
95 
		{
 - 
 
96 
			pmin = v_min(vi->pos, pmin);
 - 
 
97 
			pmax = v_max(vi->pos, pmax);
 - 
 
98 
		}
 - 
 
99 
	}
 245 
    }
100
246
101 
	void Manifold::get_bsphere(CGLA::Vec3f& c, float& r)
 247 
    VertexID Manifold::split_face_by_vertex(FaceID f)
102 
	{
 248 
    {
- 
 
 249 
        //create the new vertex, with the barycenter of the face as position
103 
		Vec3f p0,p7;
 250 
        Manifold::Vec p(0.0f);
- 
 
 251 
        HalfEdgeID last_he = kernel.last(f);
- 
 
 252 
        HalfEdgeID he = last_he;
104 
		get_bbox(p0, p7);
 253 
        int steps = 0;
- 
 
 254
105 
		Vec3f rad = (p7 - p0)/2.0;
 255 
        while(he != last_he || steps == 0){
- 
 
 256 
            p += positions[kernel.vert(he)];
106 
		c = p0 + rad;
 257 
            ++steps;
107 
		r = rad.length();
 258 
            he = kernel.next(he);
108 
	}
 259 
        }
109
260
- 
 
 261 
        p /= steps;
110
262
111 
	VertexIter Manifold::split_edge(HalfEdgeIter h)
 263 
        VertexID v = kernel.add_vertex();
- 
 
 264 
        positions[v]  = p;
112 
	{
 265
- 
 
 266 
        //circulate the face, create halfedges and connect to vertex
113 
		HalfEdgeIter ho = h->opp;
 267 
        vector<HalfEdgeID> eout;
114 
		VertexIter v  = h->vert;
 268 
        vector<HalfEdgeID> ein;
- 
 
 269 
        last_he = kernel.last(f);
115 
		VertexIter vo = ho->vert;
 270 
        he = last_he;
- 
 
 271
- 
 
 272 
        do{
116 
		Vec3f np = (v->pos+vo->pos)/2.0f;
 273 
            HalfEdgeID hn = kernel.next(he);
117
274
118 
		VertexIter vn = create_vertex(np);
 275 
            HalfEdgeID ho = kernel.add_halfedge();
119 
		vn->he = h;
 276 
            HalfEdgeID hi = kernel.add_halfedge();
120
277
121 
		HalfEdgeIter hn = create_halfedge();
 278 
            FaceID fn = kernel.add_face();
- 
 
 279 
            kernel.set_face(hi, fn);
- 
 
 280 
            kernel.set_vert(hi, v);
- 
 
 281 
            kernel.set_face(ho, fn);
- 
 
 282 
            kernel.set_vert(ho, kernel.vert(kernel.opp(he)));
- 
 
 283 
            kernel.set_face(he, fn);
122 
		HalfEdgeIter hno = create_halfedge();
 284 
            kernel.set_last(fn, ho);
123
285
- 
 
 286 
            link(hi, ho);
- 
 
 287 
            link(ho, he);
- 
 
 288 
            link(he, hi);
- 
 
 289
- 
 
 290 
            eout.push_back(ho);
- 
 
 291 
            ein.push_back(hi);
- 
 
 292
124 
		vo->he = hn;
 293 
            he = hn;
- 
 
 294 
        }
- 
 
 295 
        while(he != last_he);
- 
 
 296
- 
 
 297 
        // glue new halfedges together
- 
 
 298 
        size_t N = eout.size();
- 
 
 299 
        for(size_t i = 0; i < N; ++i){
- 
 
 300 
            glue(ein[i], eout[(i+1)%N]);
125 
		v->he = ho;
 301 
        }
- 
 
 302 
        kernel.set_out(v, eout[0]);
- 
 
 303
- 
 
 304 
        //remove the now replaced face
- 
 
 305 
        kernel.remove_face(f);
- 
 
 306
- 
 
 307 
        return v;
- 
 
 308 
    }
- 
 
 309 
    VertexID Manifold::split_edge(HalfEdgeID h)
- 
 
 310 
    {
- 
 
 311 
        HalfEdgeID ho = kernel.opp(h);
- 
 
 312 
        VertexID v = kernel.vert(h);
- 
 
 313 
        VertexID vo = kernel.vert(ho);
- 
 
 314
- 
 
 315 
        //create the new vertex with middle of edge as position and update connectivity
- 
 
 316 
        VertexID vn = kernel.add_vertex();
- 
 
 317 
        positions[vn] = .5f * (positions[v] + positions[vo]);
- 
 
 318 
        kernel.set_out(vn, h);
- 
 
 319
- 
 
 320 
        //create two necessary halfedges, and update connectivity
- 
 
 321 
        HalfEdgeID hn = kernel.add_halfedge();
- 
 
 322 
        HalfEdgeID hno = kernel.add_halfedge();
- 
 
 323
- 
 
 324 
        kernel.set_out(vo, hn);
- 
 
 325 
        kernel.set_out(v, ho);
126
326
127 
		glue(hn,hno);
 327 
        glue(hn, hno);
- 
 
 328
128 
		link(h->prev, hn);
 329 
        link(kernel.prev(h), hn);
129 
		link(hn,h);
 330 
        link(hn, h);
130 
		hn->vert = vn;
 - 
 
131
331
- 
 
 332 
        kernel.set_vert(hn, vn);
- 
 
 333
132 
		link(hno,ho->next);
 334 
        link(hno, kernel.next(ho));
133 
		link(ho, hno);
 335 
        link(ho, hno);
134 
		hno->vert = vo;
 - 
 
135 
		ho->vert = vn;
 - 
 
136
336
137 
		if(h->face != NULL_FACE_ITER)
 337 
        kernel.set_vert(hno, vo);
138 
			h->face->last = hn;
 338 
        kernel.set_vert(ho, vn);
- 
 
 339
- 
 
 340 
        // update faces in case of non boundary edge
139 
		if(ho->face != NULL_FACE_ITER)
 341 
        if(kernel.face(h) != InvalidFaceID)
140 
			ho->face->last = ho;
 342 
            kernel.set_last(kernel.face(h), hn);
141
343
142 
		hn->face = h->face;
 344 
        if(kernel.face(ho) != InvalidFaceID)
- 
 
 345 
            kernel.set_last(kernel.face(ho), ho);
- 
 
 346
- 
 
 347 
        // update new edge with faces from existing edge
143 
		hno->face = ho->face;
 348 
        kernel.set_face(hn, kernel.face(h));
- 
 
 349 
        kernel.set_face(hno, kernel.face(ho));
144
350
- 
 
 351 
        //if split occurs on a boundary, consistency must be ensured.
145 
		check_boundary_consistency(vn);
 352 
        ensure_boundary_consistency(vn);
146 
		check_boundary_consistency(v);
 353 
        ensure_boundary_consistency(v);
147 
		check_boundary_consistency(vo);
 354 
        ensure_boundary_consistency(vo);
- 
 
 355
148 
		return vn;
 356 
        return vn;
149 
	}
 357 
    }
150
358
151
- 
 
152 
	void Manifold::remove_face_if_degenerate(HalfEdgeIter h0)
 359 
    size_t link_intersection(const Manifold& m, VertexID v0, VertexID v1, vector<VertexID>& lisect)
153 
	{
 360 
    {
- 
 
 361 
        // get the one-ring of v0
- 
 
 362 
        vector<VertexID> link0;
- 
 
 363 
        for(Walker vj = m.walker(v0);
- 
 
 364 
			!vj.full_circle(); vj = vj.circulate_vertex_ccw())
- 
 
 365 
            link0.push_back(vj.vertex());
- 
 
 366
- 
 
 367 
        // get the one-ring of v1
- 
 
 368 
        vector<VertexID> link1;
- 
 
 369 
        for(Walker vj = m.walker(v1);
- 
 
 370 
			!vj.full_circle(); vj = vj.circulate_vertex_ccw())
- 
 
 371 
            link1.push_back(vj.vertex());
- 
 
 372
- 
 
 373 
        // sort the vertices of the two rings
- 
 
 374 
        sort(link0.begin(), link0.end());
- 
 
 375 
        sort(link1.begin(), link1.end());
- 
 
 376
- 
 
 377 
        // get the intersection of the shared vertices from both rings
- 
 
 378 
        std::back_insert_iterator<vector<VertexID> > lii(lisect);
- 
 
 379 
        set_intersection(link0.begin(), link0.end(),
- 
 
 380 
						 link1.begin(), link1.end(),
- 
 
 381 
						 lii);
- 
 
 382
154 
		if(h0->next->next == h0)
 383 
        return lisect.size();
- 
 
 384 
    }
- 
 
 385
- 
 
 386 
    bool Manifold::stitch_boundary_edges(HalfEdgeID h0, HalfEdgeID h1)
155 
		{
 387 
    {
- 
 
 388 
        // Cannot stitch an edge with itself
- 
 
 389 
        if(h0 == h1)
156 
			HalfEdgeIter h1 = h0->next;
 390 
            return false;
157
391
- 
 
 392 
        // Only stitch a pair of boundary edges.
- 
 
 393 
        if(kernel.face(h0) == InvalidFaceID && kernel.face(h1) == InvalidFaceID)
- 
 
 394 
        {
158 
			HalfEdgeIter h0o = h0->opp;
 395 
            HalfEdgeID h0o = kernel.opp(h0);
159 
			HalfEdgeIter h1o = h1->opp;
 396 
            HalfEdgeID h1o = kernel.opp(h1);
- 
 
 397 
            VertexID v0a = kernel.vert(h0);
- 
 
 398 
            VertexID v0b = kernel.vert(kernel.opp(h1));
- 
 
 399 
            VertexID v1b = kernel.vert(h1);
- 
 
 400 
            VertexID v1a = kernel.vert(kernel.opp(h0));
- 
 
 401
- 
 
 402 
            // Case below implies that h0 and h1 are the same edge with different ID
- 
 
 403 
            // That should not happen.
- 
 
 404 
            assert(!(v0a == v0b && v1a == v1b));
160
405
- 
 
 406 
            if(connected(*this, v0a, v0b))
- 
 
 407 
                return false;
- 
 
 408 
            if(connected(*this, v1a, v1b))
161 
			glue(h0o, h1o);
 409 
                return false;
162
410
163 
			VertexIter v0 = h1->vert;
 - 
 
164 
			VertexIter v1 = h0->vert;
 - 
 
165 
			v0->he = h1o;
 - 
 
166 
			v1->he = h0o;
 - 
 
167
411
168 
			if(h0->face != NULL_FACE_ITER)
 - 
 
169 
				erase_face(h0->face);
 412 
            if(v0b != v0a)
170 
			erase_halfedge(h0);
 413 
            {
171 
			erase_halfedge(h1);
 - 
 
172
414
- 
 
 415 
                // Check the link intersection v0a and v0b are welded together
- 
 
 416 
                // if they share a neighbouring vertex, it will appear twice in the combined
173 
			check_boundary_consistency(v0);
 417 
                // one ring unless it v1a and v1a==v1b
174 
			check_boundary_consistency(v1);
 418 
                vector<VertexID> lisect;
- 
 
 419 
                if(link_intersection(*this, v0a, v0b, lisect))
- 
 
 420 
                {
- 
 
 421 
                    vector<VertexID>::iterator iter;
175
422
- 
 
 423 
                    if(v1a == v1b)
- 
 
 424 
                    {
- 
 
 425 
                        iter = find(lisect.begin(), lisect.end(), v1a);
- 
 
 426 
                        if(iter != lisect.end())
- 
 
 427 
                            lisect.erase(iter);
- 
 
 428 
                    }
- 
 
 429 
                    iter = find(lisect.begin(), lisect.end(), kernel.vert(kernel.next(h0)));
- 
 
 430 
                    if(iter != lisect.end())
- 
 
 431 
                        lisect.erase(iter);
- 
 
 432 
                    if(lisect.size() > 0)
- 
 
 433 
                        return false;
176 
		}
 434 
                }
177 
	}
 435 
            }
178
436
- 
 
 437 
            if(v1a != v1b)
- 
 
 438 
            {
- 
 
 439 
                // Check the same for the other endpoints.
- 
 
 440 
                vector<VertexID> lisect;
179 
	bool Manifold::collapse_precond(HalfEdgeIter h)
 441 
                if(link_intersection(*this, v1a, v1b, lisect))
180 
	{
 442 
                {
181 
		VertexIter v1 = h->opp->vert;
 443 
                    vector<VertexID>::iterator iter;
182 
		VertexIter v2 = h->vert;
 - 
 
183
444
184 
		std::vector<Vertex*> link1;
 445 
                    if(v0a == v0b)
185 
		VertexCirculator vc1(v1);
 446 
                    {
- 
 
 447 
                        iter = find(lisect.begin(), lisect.end(), v1a);
- 
 
 448 
                        if(iter != lisect.end())
- 
 
 449 
                            lisect.erase(iter);
186 
		for(;!vc1.end();++vc1)
 450 
                    }
- 
 
 451 
                    iter = find(lisect.begin(), lisect.end(), kernel.vert(kernel.next(h1)));
- 
 
 452 
                    if(iter != lisect.end())
187 
			link1.push_back(&(*vc1.get_vertex()));
 453 
                        lisect.erase(iter);
188 
		assert(link1.size()>=2);
 454 
                    if(lisect.size() > 0)
- 
 
 455 
                        return false;
- 
 
 456 
                }
- 
 
 457 
            }
189
458
190 
		std::vector<Vertex*> link2;
 - 
 
191 
		VertexCirculator vc2(v2);
 - 
 
192 
		for(;!vc2.end();++vc2)
 - 
 
193 
			link2.push_back(&(*vc2.get_vertex()));
 - 
 
194 
		assert(link2.size()>=2);
 - 
 
195
459
196 
		sort(link1.begin(),link1.end());
 460 
            if(v0b != v0a)
- 
 
 461 
            {
197 
		sort(link2.begin(),link2.end());
 462 
                Walker hew = walker(v0b);
- 
 
 463 
                for(;!hew.full_circle(); hew = hew.circulate_vertex_ccw())
- 
 
 464 
                    kernel.set_vert(hew.opp().halfedge(), v0a);
- 
 
 465 
            }
198
466
199 
		vector<Vertex*> lisect;
 467 
            if(v1b != v1a)
- 
 
 468 
            {
- 
 
 469 
                Walker hew = walker(v1b);
- 
 
 470 
                for(;!hew.full_circle(); hew = hew.circulate_vertex_ccw())
200 
		back_insert_iterator<vector<Vertex*> > lii(lisect);
 471 
                    kernel.set_vert(hew.opp().halfedge(), v1a);
- 
 
 472 
            }
201
473
202 
		set_intersection(link1.begin(), link1.end(),
 - 
 
203 
						 link2.begin(), link2.end(),
 474 
            if(v0a != v0b)
204 
						 lii);
 475 
            {
- 
 
 476 
                HalfEdgeID h1p = kernel.prev(h1);
- 
 
 477 
                HalfEdgeID h0n = kernel.next(h0);
205
478
- 
 
 479 
                if(kernel.next(h0n) == h1p)
- 
 
 480 
                {
- 
 
 481 
                    glue(kernel.opp(h0n), kernel.opp(h1p));
- 
 
 482 
                    kernel.set_out(kernel.vert(h0n),kernel.opp(h0n));
- 
 
 483 
                    kernel.remove_halfedge(h0n);
- 
 
 484 
                    kernel.remove_halfedge(h1p);
- 
 
 485 
                }
- 
 
 486 
                else
- 
 
 487 
                    link(h1p, h0n);
- 
 
 488 
                kernel.remove_vertex(v0b);
- 
 
 489 
            }
206
490
207 
		// If the adjacent face is a triangle (see 2)
 - 
 
208 
		int k=0;
 - 
 
209 
		if(h->next->next->next == h)
 491 
            if(v1a != v1b)
210 
		{
 492 
            {
- 
 
 493 
                HalfEdgeID h0p = kernel.prev(h0);
- 
 
 494 
                HalfEdgeID h1n = kernel.next(h1);
- 
 
 495 
                if(kernel.next(h1n) == h0p)
- 
 
 496 
                {
- 
 
 497 
                    glue(kernel.opp(h0p), kernel.opp(h1n));
- 
 
 498 
                    kernel.set_out(kernel.vert(h1n), kernel.opp(h1n));
- 
 
 499 
                    kernel.remove_halfedge(h0p);
- 
 
 500 
                    kernel.remove_halfedge(h1n);
- 
 
 501 
                }
211 
			// VALENCY 4 TEST
 502 
                else
- 
 
 503 
                    link(h0p, h1n);
212 
			if(valency(h->next->vert)<4)
 504 
                kernel.remove_vertex(v1b);
213 
				return false;
 505 
            }
- 
 
 506 
            glue(h0o, h1o);
214
507
215 
			vector<Vertex*>::iterator iter;
 508 
            kernel.remove_halfedge(h0);
216 
			iter = find(lisect.begin(),	lisect.end(),&(*h->next->vert));
 509 
            kernel.remove_halfedge(h1);
- 
 
 510
217 
			assert(iter != lisect.end());
 511 
            kernel.set_out(v1a, h1o);
218 
			lisect.erase(iter);
 512 
            kernel.set_out(v0a, h0o);
219 
			++k;
 513
- 
 
 514 
            ensure_boundary_consistency(v1a);
- 
 
 515 
            ensure_boundary_consistency(v0a);
220
516
- 
 
 517 
            return true;
221 
		}
 518 
        }
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;
 519 
        return false;
- 
 
 520 
    }
- 
 
 521
228
522
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
523
- 
 
 524 
    FaceID Manifold::merge_one_ring(VertexID v, float max_loop_length)
- 
 
 525 
    {
- 
 
 526 
        // If the vertex is either not in use or has just
- 
 
 527 
        // one incident edge (or less), bail out.
- 
 
 528 
        int val = valency(*this,v);
- 
 
 529 
        if(!in_use(v) || val<2)
- 
 
 530 
            return InvalidFaceID;
- 
 
 531
- 
 
 532 
        // If the vertex is  a boundary vertex, we preparte the walker so that the
- 
 
 533 
        // first face visited is not the invalid face outside the boundary. If the boundary
- 
 
 534 
        // vertex is adjacent to only one vertex, there is little to do and we bail out.
- 
 
 535 
        bool vertex_is_boundary = false;
- 
 
 536 
        Walker hew = walker(v);
- 
 
 537 
        if(boundary(*this, v))
- 
 
 538 
        {
- 
 
 539 
            if(val==2) return InvalidFaceID;
- 
 
 540 
            vertex_is_boundary = true;
- 
 
 541 
            hew = hew.circulate_vertex_ccw();
- 
 
 542 
        }
- 
 
 543
- 
 
 544 
        // Prepare some vectors for taking out the trash: We remove all old faces and all orphaned edges
- 
 
 545 
        // and vertices
- 
 
 546 
        vector<HalfEdgeID> garbage_halfedges;
- 
 
 547 
        vector<FaceID> garbage_faces;
- 
 
 548 
        vector<VertexID> garbage_vertices;
- 
 
 549
- 
 
 550 
        vector<HalfEdgeID> loop; // The halfedges which form the outer loop of the merged one ring.
- 
 
 551
- 
 
 552 
        // Below we loop over all faces adjacent to the vertex and add their halfedges to a big loop
- 
 
 553 
        // which will form the loop of the new merged face. Below we remove from the loop edges
- 
 
 554 
        // that appear twice (as each other's opposite).
- 
 
 555 
        for(;!hew.full_circle(); hew = hew.circulate_vertex_ccw())
- 
 
 556 
        {
- 
 
 557 
            garbage_faces.push_back(hew.face());
- 
 
 558 
            for(Walker hew2 = walker(hew.halfedge());
- 
 
 559 
                !hew2.full_circle(); hew2 = hew2.circulate_face_ccw())
- 
 
 560 
                loop.push_back(hew2.halfedge());
235 
		}
 561 
        }
- 
 
 562
- 
 
 563
- 
 
 564 
        // Now merge the loops. We iteratively remove pairs of adjacent halfedges from the loop
- 
 
 565 
        // if we find that the second is the opposite of the first since this is a degenerate
- 
 
 566 
        // situation. However, we stop at four remaining halfedges since otherwise the loop degenerates
- 
 
 567 
        // to zero after the next step if these four are also pairwise each other's opposites.
- 
 
 568 
        int did_work;
- 
 
 569 
        do
- 
 
 570 
        {
- 
 
 571 
            did_work = 0;
- 
 
 572 
            vector<HalfEdgeID> loop_tmp(0);
- 
 
 573 
            for(int i=0;i<loop.size();++i)
- 
 
 574 
                if(walker(loop[i]).opp().halfedge() == loop[(i+1)%loop.size()])
- 
 
 575 
                {
- 
 
 576 
                    VertexID vid = walker(loop[i]).vertex();
- 
 
 577 
                    if(vid != v)
- 
 
 578 
                        garbage_vertices.push_back(walker(loop[i]).vertex());
- 
 
 579 
                    garbage_halfedges.push_back(loop[i]);
- 
 
 580 
                    garbage_halfedges.push_back(loop[(i+1)%loop.size()]);
- 
 
 581 
                    loop[i] = InvalidHalfEdgeID;
- 
 
 582 
                    loop[(i+1)%loop.size()] = InvalidHalfEdgeID;
- 
 
 583 
                    ++did_work;
- 
 
 584 
                    ++i;
- 
 
 585 
                }
- 
 
 586 
            for(int i=0;i<loop.size();++i)
- 
 
 587 
                if(loop[i] != InvalidHalfEdgeID)
- 
 
 588 
                    loop_tmp.push_back(loop[i]);
- 
 
 589 
            loop = loop_tmp;
- 
 
 590 
        } while(did_work > 0 && loop.size() > 4);
- 
 
 591
- 
 
 592 
        // Check whether the loop is too long
- 
 
 593 
        float loop_len=0.0;
- 
 
 594 
        for(int i=0;i<loop.size();++i)
- 
 
 595 
            loop_len += length(*this, loop[i]);
- 
 
 596 
        if(loop_len > max_loop_length)
- 
 
 597 
            return InvalidFaceID;
- 
 
 598
- 
 
 599 
        // The following block checks wheteher the same halfedge appears twice. In this
- 
 
 600 
        // case we fail since it means that the one ring contains the same face twice.
- 
 
 601 
        vector<HalfEdgeID> loop_tmp = loop;
- 
 
 602 
        sort(loop_tmp.begin(), loop_tmp.end());
- 
 
 603 
        vector<HalfEdgeID>::iterator end_iter = unique(loop_tmp.begin(), loop_tmp.end());
236 
		if(lisect.size() !=0) // See 3.
 604 
        if(end_iter != loop_tmp.end())
- 
 
 605 
            return InvalidFaceID;
- 
 
 606
- 
 
 607 
        // Remove all faces and connected halfedges and the original vertex v.
- 
 
 608 
        for(int i=0;i<garbage_vertices.size(); ++i)
- 
 
 609 
            kernel.remove_vertex(garbage_vertices[i]);
- 
 
 610 
        for(int i=0;i<garbage_faces.size(); ++i)
- 
 
 611 
            kernel.remove_face(garbage_faces[i]);
- 
 
 612 
        for(int i=0;i<garbage_halfedges.size(); ++i)
- 
 
 613 
            kernel.remove_halfedge(garbage_halfedges[i]);
- 
 
 614 
        if(!vertex_is_boundary)
- 
 
 615 
            kernel.remove_vertex(v);
- 
 
 616
- 
 
 617 
        // Create a new face for the merged one ring and link up all the halfedges
- 
 
 618 
        // in the loop
- 
 
 619 
        FaceID f = kernel.add_face();
- 
 
 620 
        kernel.set_last(f,loop[0]);
- 
 
 621 
        for(int i=0;i<loop.size(); ++i)
- 
 
 622 
        {
- 
 
 623 
            kernel.set_face(loop[i], f);
- 
 
 624 
            Walker hw = walker(loop[i]);
- 
 
 625 
            kernel.set_out(hw.vertex(),hw.opp().halfedge());
- 
 
 626 
            link(loop[i],loop[(i+1)%loop.size()]);
- 
 
 627 
            assert(hw.vertex() == walker(loop[(i+1)%loop.size()]).opp().vertex());
- 
 
 628 
        }
- 
 
 629
- 
 
 630 
        // Finally, we ensure boundary consitency for all vertices in the loop.
- 
 
 631 
        for(int i=0;i<loop.size(); ++i)
- 
 
 632 
        {
- 
 
 633 
            Walker hw = walker(loop[i]);
- 
 
 634 
            ensure_boundary_consistency(hw.vertex());
- 
 
 635 
        }
- 
 
 636
- 
 
 637 
        // Return the brand new merged face.
- 
 
 638 
        return f;
- 
 
 639 
    }
- 
 
 640
- 
 
 641
- 
 
 642
- 
 
 643 
    bool Manifold::merge_faces(FaceID f, HalfEdgeID h)
- 
 
 644 
    {
- 
 
 645 
        //assert that we're merging a valid face with the corresponding halfedge
- 
 
 646 
        assert(kernel.face(h) == f);
- 
 
 647
- 
 
 648 
        HalfEdgeID ho = kernel.opp(h);
- 
 
 649 
        FaceID fo = kernel.face(ho);
- 
 
 650 
        HalfEdgeID hn = kernel.next(h);
- 
 
 651 
        HalfEdgeID hon = kernel.next(ho);
- 
 
 652
- 
 
 653 
        if(fo == f)
237 
			return false;
 654 
            return false;
238
655
239 
		// TETRAHEDRON TEST
 656 
        //boundary case
240 
		if(k==2 && (link1.size()+link2.size()==6))
 657 
        if(kernel.vert(hn) == kernel.vert(hon))
241 
			return false;
 658 
            return false;
242
659
243 
		// Test that we are not merging holes (see 6)
 660 
        HalfEdgeID hp = kernel.prev(h);
244 
		if(is_boundary(v1) && is_boundary(v2) &&
 661 
        HalfEdgeID hop = kernel.prev(ho);
245 
		   (h->face != NULL_FACE_ITER) &&
 662 
        VertexID v = kernel.vert(h);
246 
		   (h->opp->face != NULL_FACE_ITER))
 663 
        VertexID vo = kernel.vert(ho);
- 
 
 664
- 
 
 665 
        if(valency(*this, v) < 3 || valency(*this, vo) < 3)
247 
			return false;
 666 
            return false;
248
667
- 
 
 668 
        link(hop, hn);
- 
 
 669 
        link(hp, hon);
- 
 
 670 
        kernel.set_out(vo, hon);
- 
 
 671 
        kernel.set_out(v, hn);
- 
 
 672 
        kernel.set_last(f, hn);
- 
 
 673
- 
 
 674 
        HalfEdgeID hx = hon;
- 
 
 675
- 
 
 676 
        assert(kernel.face(hx) == fo);
- 
 
 677 
        while(kernel.face(hx) != f){
- 
 
 678 
            kernel.set_face(hx, f);
- 
 
 679 
            hx = kernel.next(hx);
- 
 
 680 
        }
- 
 
 681
- 
 
 682 
        ensure_boundary_consistency(v);
- 
 
 683 
        ensure_boundary_consistency(vo);
- 
 
 684
- 
 
 685 
        kernel.remove_halfedge(h);
- 
 
 686 
        kernel.remove_halfedge(ho);
- 
 
 687 
        kernel.remove_face(fo);
249
688
250 
		return true;
 689 
        return true;
251 
	}
 690 
    }
252
691
- 
 
 692 
    FaceID Manifold::close_hole(HalfEdgeID h)
- 
 
 693 
    {
- 
 
 694 
        // invalid face is a hole
- 
 
 695 
        if(kernel.face(h) == InvalidFaceID){
- 
 
 696 
            FaceID f = kernel.add_face();
- 
 
 697 
            kernel.set_last(f, h);
- 
 
 698 
            do{
- 
 
 699 
                kernel.set_face(h, f);
- 
 
 700 
                h = kernel.next(h);
- 
 
 701 
            }
- 
 
 702 
            while(kernel.face(h) != f);
- 
 
 703 
            return f;
- 
 
 704 
        }
- 
 
 705 
        return kernel.face(h);
- 
 
 706 
    }
- 
 
 707 
    void Manifold::flip_edge(HalfEdgeID h)
- 
 
 708 
    {
- 
 
 709 
        HalfEdgeID hn = kernel.next(h);
- 
 
 710 
        HalfEdgeID hp = kernel.prev(h);
- 
 
 711 
        HalfEdgeID ho = kernel.opp(h);
- 
 
 712 
        HalfEdgeID hon = kernel.next(ho);
- 
 
 713 
        HalfEdgeID hop = kernel.prev(ho);
- 
 
 714
- 
 
 715 
        FaceID hf = kernel.face(h);
- 
 
 716 
        FaceID hof = kernel.face(ho);
- 
 
 717
- 
 
 718 
        VertexID hv = kernel.vert(h);
- 
 
 719 
        VertexID hnv = kernel.vert(hn);
- 
 
 720 
        VertexID hov = kernel.vert(ho);
- 
 
 721 
        VertexID honv = kernel.vert(hon);
- 
 
 722
- 
 
 723 
        // update face connectivity of halfedges changing face
- 
 
 724 
        kernel.set_face(hop, hf);
- 
 
 725 
        kernel.set_face(hp, hof);
- 
 
 726
- 
 
 727 
        // connectivity of faces with halfedges of flipped edge
- 
 
 728 
        kernel.set_last(hf, h);
- 
 
 729 
        kernel.set_last(hof, ho);
- 
 
 730
- 
 
 731 
        // connectivity of halfedges of first face after flip
- 
 
 732 
        link(hn, h);
- 
 
 733 
        link(h, hop);
- 
 
 734 
        link(hop, hn);
- 
 
 735
- 
 
 736 
        // connectivity of halfedges of second face after flip
- 
 
 737 
        link(hon, ho);
- 
 
 738 
        link(ho, hp);
- 
 
 739 
        link(hp, hon);
253
740
- 
 
 741 
        // connectivity of flipped edge and corresponding vertices
- 
 
 742 
        kernel.set_vert(h, honv);
- 
 
 743 
        kernel.set_vert(ho, hnv);
- 
 
 744
- 
 
 745 
        if(kernel.out(hv) == ho)
- 
 
 746 
            kernel.set_out(hv, hn);
- 
 
 747 
        if(kernel.out(hov) == h)
- 
 
 748 
            kernel.set_out(hov, hon);
- 
 
 749
- 
 
 750 
        //
- 
 
 751 
        //        // if the flip occurs next to a boundary, ensure the boundary consistency
- 
 
 752 
        //        ensure_boundary_consistency(hv);
- 
 
 753 
        //        ensure_boundary_consistency(hov);
- 
 
 754 
    }
- 
 
 755
- 
 
 756
- 
 
 757 
    /**********************************************
- 
 
 758 
     * Private functions
- 
 
 759 
     **********************************************/
- 
 
 760
- 
 
 761 
    template<typename size_type, typename float_type, typename int_type>
254 
	void Manifold::collapse_halfedge(HalfEdgeIter h, bool avg_vertices)
 762 
    void Manifold::build_template(  size_type no_vertices,
- 
 
 763 
                                  const float_type* vertvec,
- 
 
 764 
                                  size_type no_faces,
- 
 
 765 
                                  const int_type* facevec,
- 
 
 766 
                                  const int_type* indices)
255 
	{
 767 
    {
256 
		VertexIter v = h->opp->vert;
 768 
        vector<VertexID> vids(no_vertices);
257 
		HalfEdgeIter ho = h->opp;
 - 
 
258 
		VertexIter n = h->vert;
 - 
 
259
769
- 
 
 770 
        // create vertices corresponding to positions stored in vertvec
260 
		if(avg_vertices)
 771 
        for(int i=0;i<no_vertices;++i)
- 
 
 772 
        {
261 
			n->pos = ((v->pos + n->pos) / 2.0f);
 773 
            const float_type* v0 = &vertvec[i*3];
- 
 
 774 
            pos(vids[i] = kernel.add_vertex()) = Manifold::Vec(v0[0], v0[1], v0[2]);
- 
 
 775 
        }
262
776
263 
		HalfEdgeIter hn = h->next;
 - 
 
264 
		HalfEdgeIter hp = h->prev;
 777 
        //map over the created edges - needed to preserve edge uniqueness
265 
		HalfEdgeIter hon = ho->next;
 778 
        typedef map<EdgeKey, Edge> EdgeMap;
266 
		HalfEdgeIter hop = ho->prev;
 779 
        EdgeMap edge_map;
267
780
268 
		VertexCirculator vc(v);
 781 
        // counter that jumps between faces in indices vector
269 
		for(;!vc.end();++vc)
 - 
 
270 
			vc.get_opp_halfedge()->vert = n;
 782 
        int_type n  = 0;
271
783
- 
 
 784 
        // create faces correspponding to faces stored in facevec
- 
 
 785 
        for(size_type i = 0; i < no_faces; ++i){
- 
 
 786 
            //amount of vertices in current face
272 
		n->he = h->next;
 787 
            size_type N = facevec[i];
- 
 
 788 
            vector<HalfEdgeID> fh;
273
789
274 
		link(hp, hn);
 790 
            //each face indice results corresponds to 1 edge, 2 halfedges
275 
		if(h->face != NULL_FACE_ITER)
 791 
            for(size_type j = 0; j < N; ++j){
276 
			h->face->last = hn;
 792 
                // ensure indice integrity
277
793
278 
		link(hop, hon);
 - 
 
279 
		if(ho->face != NULL_FACE_ITER)
 794 
                assert(static_cast<size_type>(indices[j + n]) < no_vertices);
280 
			ho->face->last = hon;
 795 
                assert(static_cast<size_type>(indices[(j + 1) % N + n]) < no_vertices);
281
796
282
797
- 
 
 798 
                // each iteration uses two indices from the face
- 
 
 799 
                VertexID v0 = vids[static_cast<size_type>(indices[j + n])];
- 
 
 800 
                VertexID v1 = vids[static_cast<size_type>(indices[(j + 1) % N + n])];
283
801
284 
		erase_vertex(v);
 802 
                // create key and search map for edge
285 
		erase_halfedge(h);
 803 
                EdgeKey ek(v0, v1);
286 
		erase_halfedge(ho);
 804 
                EdgeMap::iterator em_iter = edge_map.find(ek);
287
805
- 
 
 806 
                // current edge has not been created
- 
 
 807 
                if(em_iter == edge_map.end()){
- 
 
 808 
                    // create edge for map
- 
 
 809 
                    Edge e;
- 
 
 810 
                    e.h0 = kernel.add_halfedge();
- 
 
 811 
                    e.h1 = kernel.add_halfedge();
- 
 
 812 
                    e.count = 1;
- 
 
 813
- 
 
 814 
                    // glue operation: 1 edge = 2 glued halfedges
288 
		remove_face_if_degenerate(hn);
 815 
                    glue(e.h0, e.h1);
- 
 
 816
- 
 
 817 
                    // update vertices with their outgoing halfedges
- 
 
 818 
                    kernel.set_out(v0, e.h0);
- 
 
 819 
                    kernel.set_out(v1, e.h1);
- 
 
 820
- 
 
 821 
                    // update halfedges with the vertices they point to
- 
 
 822 
                    kernel.set_vert(e.h0, v1);
- 
 
 823 
                    kernel.set_vert(e.h1, v0);
- 
 
 824
- 
 
 825 
                    // update map
289 
		remove_face_if_degenerate(hon);
 826 
                    edge_map[ek] = e;
290
827
- 
 
 828 
                    // update vector of halfedges belonging to current face
291 
		check_boundary_consistency(n);
 829 
                    fh.push_back(e.h0);
292 
	}
 830 
                }
- 
 
 831 
                else{
- 
 
 832 
                    // update current face with halfedge from edge
- 
 
 833 
                    fh.push_back(em_iter->second.h1);
293
834
- 
 
 835 
                    // asserting that a halfedge is visited exactly twice;
- 
 
 836 
                    // once for each face on either side of the edge.
- 
 
 837 
                    em_iter->second.count++;
- 
 
 838 
                    assert(em_iter->second.count == 2);
- 
 
 839 
                }
- 
 
 840 
            }
- 
 
 841
- 
 
 842 
            FaceID fid = kernel.add_face();
- 
 
 843 
            for(size_type j = 0; j < N; ++j){
- 
 
 844 
                // update halfedge with face
- 
 
 845 
                kernel.set_face(fh[j], fid);
- 
 
 846
- 
 
 847 
                // link operation: link two halfedges in the same face
- 
 
 848 
                link(fh[j], fh[(j + 1) % N]);
- 
 
 849 
            }
- 
 
 850 
            //update face with the first halfedge created
294 
	bool Manifold::is_valid()
 851 
            kernel.set_last(fid, fh[0]);
- 
 
 852
- 
 
 853 
            // step to first index of next face
- 
 
 854 
            n += N;
- 
 
 855 
        }
295 
	{
 856
- 
 
 857 
        // test for unused vertices
- 
 
 858 
        for(VertexIDIterator v = vertices_begin(); v != vertices_end(); ++v){
296 
		HalfEdgeIter he0 = halfedges_begin();
 859 
            assert( (*v) != InvalidVertexID);
- 
 
 860 
            if(kernel.out(*v) == InvalidHalfEdgeID)
- 
 
 861 
                kernel.remove_vertex(*v);
- 
 
 862 
        }
- 
 
 863
- 
 
 864 
        // boundary check while avoiding unused vertices
- 
 
 865 
        for(VertexIDIterator v = vertices_begin(); v != vertices_end(); ++v){
297 
		while(he0 != halfedges_end())
 866 
            if((*v) != InvalidVertexID)
- 
 
 867 
                ensure_boundary_consistency(*v);
- 
 
 868 
        }
- 
 
 869 
    }
- 
 
 870 
    void Manifold::link(HalfEdgeID h0, HalfEdgeID h1)
298 
		{
 871 
    {
- 
 
 872 
        kernel.set_next(h0, h1);
299 
			if(he0->prev == NULL_HALFEDGE_ITER)
 873 
        kernel.set_prev(h1, h0);
- 
 
 874 
    }
- 
 
 875 
    void Manifold::glue(HalfEdgeID h0, HalfEdgeID h1)
300 
			{
 876 
    {
301 
				cout << "Halfedge lacks previous" << endl;
 877 
        kernel.set_opp(h0, h1);
302 
				return false;
 878 
        kernel.set_opp(h1, h0);
303 
			}
 879 
    }
304 
			if(he0->next == NULL_HALFEDGE_ITER)
 880 
    void Manifold::ensure_boundary_consistency(VertexID v)
305 
			{
 881 
    {
- 
 
 882 
        // boundary consistency check by performing two vertex circulations
306 
				cout << "Halfedge lacks next" << endl;
 883 
        HalfEdgeID h = kernel.out(v);
- 
 
 884 
        HalfEdgeID last = h;
- 
 
 885
- 
 
 886 
        // step 1: circle through edges pointing away from vertex until reaching a null face
- 
 
 887 
        while(kernel.face(h) != InvalidFaceID){
- 
 
 888 
            h = kernel.opp(kernel.prev(h));
- 
 
 889 
            if(h == last) // We came full circle - vertex not boundary - return.
- 
 
 890 
                return;
- 
 
 891 
        }
- 
 
 892 
        // null face encountered, we update our vertex with half edge index and prepare for step 2
- 
 
 893 
        kernel.set_out(v, h);
- 
 
 894 
        HalfEdgeID ho = kernel.opp(h);
- 
 
 895
- 
 
 896 
        // step 2: circle through edges pointing towards vertex until reaching a null face
- 
 
 897 
        while(kernel.face(ho) != InvalidFaceID){
- 
 
 898 
            ho = kernel.opp(kernel.next(ho));
- 
 
 899 
        }
- 
 
 900 
        // null face encountered again, we update our edge with vertex index
- 
 
 901 
        kernel.set_vert(ho, v);
- 
 
 902
- 
 
 903 
        // remaining step is to make the in and out going edges link to each other
307 
				return false;
 904 
        link(ho, h);
308 
			}
 905 
    }
309 
			if(he0->opp == NULL_HALFEDGE_ITER)
 906 
    void Manifold::remove_face_if_degenerate(HalfEdgeID h)
310 
			{
 907 
    {
- 
 
 908 
        // face is degenerate if there is only two halfedges in face loop
- 
 
 909 
        if(kernel.next(kernel.next(h)) == h)
- 
 
 910 
        {
- 
 
 911 
            HalfEdgeID hn = kernel.next(h);
- 
 
 912 
            HalfEdgeID ho = kernel.opp(h);
311 
				cout << "Halfedge lacks opposite" << endl;
 913 
            HalfEdgeID hno = kernel.opp(hn);
- 
 
 914 
            VertexID hv = kernel.vert(h);
- 
 
 915 
            VertexID hnv = kernel.vert(hn);
- 
 
 916 
            FaceID f = kernel.face(h);
- 
 
 917
- 
 
 918 
            assert(ho != hn);
- 
 
 919 
            assert(h != hno);
- 
 
 920 
            assert(hv != hnv);
- 
 
 921
- 
 
 922 
            // glue opposite halfedge to halfedge opposite next halfedge, obsoleting h and hn from loop
312 
				return false;
 923 
            glue(ho, hno);
- 
 
 924
- 
 
 925 
            // make v and vn point to opposite and next opposite halfedge, obsoleting h and hn from loop
- 
 
 926 
            kernel.set_out(hnv, hno);
- 
 
 927 
            kernel.set_out(hv, ho);
- 
 
 928
- 
 
 929 
            // if face owning h is valid, remove face
- 
 
 930 
            if(f != InvalidFaceID)
- 
 
 931 
                kernel.remove_face(f);
- 
 
 932 
            // remove the two invalid halfedges and the invalid face loop
- 
 
 933 
            kernel.remove_halfedge(h);
- 
 
 934 
            kernel.remove_halfedge(hn);
- 
 
 935
- 
 
 936 
            // verify that v and vn is sane after removing the degenerate face
- 
 
 937 
            ensure_boundary_consistency(hv);
- 
 
 938 
            ensure_boundary_consistency(hnv);
- 
 
 939 
        }
313 
			}
 940 
    }
- 
 
 941
314 
			if(he0->vert == NULL_VERTEX_ITER)
 942 
    vector<HalfEdgeID> Manifold::bridge_faces(FaceID f0, FaceID f1, const vector<pair<VertexID, VertexID> >& pairs)
315 
			{
 943 
    {
316 
				cout << "Halfedge lacks vertex" << endl;
 944 
        // Let N be the number of vertex pairs to connect by edges
- 
 
 945 
        size_t N = pairs.size();
- 
 
 946
- 
 
 947 
        // We now create N pairs of edges, glue each pair and let them point to the appropriate
317 
				return false;
 948 
        // vertices.
- 
 
 949 
        vector<HalfEdgeID> new_halfedges(N);
- 
 
 950 
        vector<HalfEdgeID> new_halfedges_opp(N);
- 
 
 951 
        for(int i=0;i<N; ++i)
- 
 
 952 
        {
- 
 
 953 
            new_halfedges[i] = kernel.add_halfedge();
- 
 
 954 
            new_halfedges_opp[i] = kernel.add_halfedge();
- 
 
 955 
            glue(new_halfedges[i], new_halfedges_opp[i]);
- 
 
 956 
            kernel.set_vert(new_halfedges[i], pairs[i].second);
- 
 
 957 
            kernel.set_vert(new_halfedges_opp[i], pairs[i].first);
318 
			}
 958 
        }
- 
 
 959
- 
 
 960 
        // We now maintain some halfedge indices to right before
- 
 
 961 
        // and right after the point we are trying to connect on
- 
 
 962 
        // each of the two loops.
- 
 
 963 
        HalfEdgeID h0p = kernel.last(f0);
- 
 
 964 
        HalfEdgeID h1n = kernel.last(f1);
- 
 
 965
- 
 
 966 
        // loop over all connections and link the new halfedges with the old
- 
 
 967 
        // ones.
- 
 
 968 
        for(int i=0;i<N; ++i)
319 
			++he0;
 969 
        {
- 
 
 970 
            while(kernel.vert(h0p) != pairs[i].first)
- 
 
 971 
                h0p = kernel.next(h0p);
- 
 
 972 
            while(kernel.vert(kernel.prev(h1n)) != pairs[i].second)
- 
 
 973 
                h1n = kernel.prev(h1n);
- 
 
 974
- 
 
 975 
            HalfEdgeID h0n = kernel.next(h0p);
- 
 
 976 
            HalfEdgeID h1p = kernel.prev(h1n);
- 
 
 977
- 
 
 978 
            link(h0p, new_halfedges[i]);
- 
 
 979 
            link(new_halfedges[i],h1n);
- 
 
 980 
            link(h1p, new_halfedges_opp[i]);
- 
 
 981 
            link(new_halfedges_opp[i],h0n);
- 
 
 982
- 
 
 983 
            h0p = new_halfedges_opp[i];
- 
 
 984 
            h1n = new_halfedges_opp[i];
320 
		}
 985 
        }
321
986
322 
		VertexIter vi = vertices_begin();
 987 
        // Create the faces and their connections
323 
		while(vi != vertices_end())
 988 
        for(int i=0;i<N; ++i)
324 
		{
 989 
        {
- 
 
 990 
            HalfEdgeID last = new_halfedges[i];
325 
			std::vector<Vertex*> link;
 991 
            FaceID f = kernel.add_face();
326 
			VertexCirculator vc(vi);
 992 
            kernel.set_last(f, last);
327 
			int k=0;
 993 
            HalfEdgeID h = last;
328 
			for(;!vc.end();++vc,++k)
 994 
            do
329 
			{
 995 
            {
- 
 
 996 
                kernel.set_face(h, f);
- 
 
 997 
                h = kernel.next(h);
- 
 
 998 
            } while(h != last);
- 
 
 999 
        }
- 
 
 1000
330 
				if(vc.get_halfedge() == NULL_HALFEDGE_ITER)
 1001 
        // Delete the old faces that were bridged.
- 
 
 1002 
        kernel.remove_face(f0);
- 
 
 1003 
        kernel.remove_face(f1);
- 
 
 1004
- 
 
 1005 
        new_halfedges.insert(new_halfedges.end(), new_halfedges_opp.begin(), new_halfedges_opp.end());
- 
 
 1006 
        return new_halfedges;
- 
 
 1007 
    }
- 
 
 1008
- 
 
 1009 
    /***************************************************
- 
 
 1010 
     * Namespace functions
- 
 
 1011 
     ***************************************************/
- 
 
 1012 
    bool valid(const Manifold& m)
331 
				{
 1013 
    {
- 
 
 1014 
        // Verify components of halfedges
- 
 
 1015 
        for(HalfEdgeIDIterator h = m.halfedges_begin(); h != m.halfedges_end(); ++h){
- 
 
 1016 
            Walker j = m.walker(*h);
- 
 
 1017
- 
 
 1018 
            if(j.vertex() == InvalidVertexID){
332 
					cout << "Vertex has null outgoing he" << endl;
 1019 
                cout << "Halfedge lacks vert" << endl;
333 
					return false;
 1020 
                return false;
334 
				}
 1021 
            }
335 
				Vertex* x = &(*vc.get_vertex());
 - 
 
336 
				if(find(link.begin(), link.end(), x) != link.end())
 1022 
            if(j.next().halfedge() == InvalidHalfEdgeID){
337 
				{
 - 
 
338 
					cout << "Vertex appears two times in one-ring of other vertex" << endl;
 1023 
                cout << "Halfedge lacks next" << endl;
339 
					return false;
 1024 
                return false;
340 
				}
 1025 
            }
341 
				link.push_back(x);
 1026 
            if(j.prev().halfedge() == InvalidHalfEdgeID){
342 
				if(k==1e6)
 - 
 
343 
				{
 - 
 
344 
					cout << "infin. loop around vertex" << endl;
 1027 
                cout << "Halfedge lacks prev" << endl;
345 
					return false;
 1028 
                return false;
346 
				}
 1029 
            }
- 
 
 1030 
            if(j.opp().halfedge() == InvalidHalfEdgeID){
- 
 
 1031 
                cout << "Halfedge lacks opp" << endl;
- 
 
 1032 
                return false;
347 
			}
 1033 
            }
348 
			if(link.size()==2)
 - 
 
349 
			{
 - 
 
350 
				if(!is_boundary(vi))
 - 
 
351 
					cout << "Warning: A vertex with only two incident edges" << endl;
 - 
 
352 
				else
 1034
353 
					cout << "Comment: A boundary vertex with only two incident edges" << endl;
 - 
 
354 
			}
 1035 
        }
- 
 
 1036 
        // Verify components of vertices
- 
 
 1037 
        for(VertexIDIterator v = m.vertices_begin(); v != m.vertices_end(); ++v){
355 
			assert(link.size()>=2);
 1038 
            vector<VertexID> link;
356 
			++vi;
 1039
- 
 
 1040 
            // circulate the halfedges of vertex
- 
 
 1041 
            for(Walker j = m.walker(*v); !j.full_circle(); j = j.circulate_vertex_cw()){
- 
 
 1042 
                // test halfedges around v
- 
 
 1043 
                if(j.halfedge() == InvalidHalfEdgeID){
- 
 
 1044 
                    cout << "Vertex circulation produced invalid halfedge" << endl;
- 
 
 1045 
                    return false;
357 
		}
 1046 
                }
- 
 
 1047 
                VertexID ring_v = j.vertex();
358
1048
359 
		HMesh::FaceIter f = faces_begin();
 1049 
                // test one-ring for multiple occurences of vertex
360 
		for(;f != faces_end(); ++f)
 1050 
                if(find(link.begin(), link.end(), ring_v) != link.end()){
361 
		{
 - 
 
362 
			if(no_edges(f)<3)
 1051 
                    cout << "Vertex appears two times in one-ring of vertex" << endl;
363 
			{
 - 
 
364 
				cout << "Degenerate face" << endl;
 1052 
                    return false;
365 
			}
 1053 
                }
366 
			FaceCirculator fc(f);
 1054 
                link.push_back(ring_v);
367 
			int k=0;
 1055
368 
			while(!fc.end())
 1056 
                // test for infinite loop around vertex
369 
			{
 - 
 
370 
				if(fc.get_halfedge()->face != f)
 1057 
                if(static_cast<size_t>(j.no_steps()) > m.no_vertices()){
371 
				{
 - 
 
372 
					cout << "Inconsistent face" << endl;
 1058 
                    cout << "Vertex loop contains more vertices than manifold" << endl;
373 
					return false;
 1059 
                    return false;
374 
				}
 1060 
                }
- 
 
 1061 
            }
- 
 
 1062
- 
 
 1063 
            // test one_ring size for boundary consistency
- 
 
 1064 
            if(link.size() <= 2){
- 
 
 1065 
                Walker j = m.walker(*v);
- 
 
 1066
- 
 
 1067 
                if(j.face() != InvalidFaceID && j.opp().face() != InvalidFaceID)
- 
 
 1068 
                {
- 
 
 1069 
                    if(link.size()==1)
375 
				if(++k==1e6) cout << "infin. loop around face" << endl;
 1070 
                        cout << "Vertex contains only a single incident edge" << endl;
- 
 
 1071 
                    //
- 
 
 1072 
                    //                    cout << "Vertex contains only " << link.size() <<" incident edges" << endl;
- 
 
 1073 
                }
- 
 
 1074 
                else
- 
 
 1075 
                    cout << "Boundary vertex contains only " << link.size() <<" incident edges" << endl;
- 
 
 1076 
            }
376 
				++fc;
 1077 
        }
- 
 
 1078 
        // verify components of faces
- 
 
 1079 
        for(FaceIDIterator f = m.faces_begin(); f != m.faces_end(); ++f){
- 
 
 1080 
            // count edges on face
- 
 
 1081 
            Walker j = m.walker(*f);
- 
 
 1082
- 
 
 1083 
            for(; !j.full_circle(); j = j.circulate_face_cw()){
- 
 
 1084 
                // test that all halfedges in faces bind properly to their face
- 
 
 1085 
                if(j.face() != *f){
- 
 
 1086 
                    cout << "Face is inconsistent, halfedge is not bound to face" << endl;
- 
 
 1087 
                    return false;
- 
 
 1088 
                }
- 
 
 1089 
            }
- 
 
 1090 
            // test faces for valid geometrical properties
- 
 
 1091 
            if(j.no_steps() < 3){
- 
 
 1092 
                cout << "Face contains less than 3 edges" << endl;
- 
 
 1093 
                return false;
- 
 
 1094 
            }
- 
 
 1095 
            // test for infinite loop around face
- 
 
 1096 
            if(j.no_steps() > m.no_halfedges() * 0.5f){
- 
 
 1097 
                cout << "Face loop contains more halfedges than manifold" << endl;
- 
 
 1098 
                return false;
377 
			}
 1099 
            }
378 
		}
 1100 
        }
379 
		return true;
 1101 
        return true;
380 
	}
 1102 
    }
381
1103
382 
	FaceIter Manifold::split_face(FaceIter f, VertexIter v0, VertexIter v1)
 1104 
    void bbox(const Manifold& m, Manifold::Vec& pmin, Manifold::Vec& pmax)
383 
	{
 1105 
    {
384 
		// Make sure this is not a triangle
 - 
 
385 
		assert(no_edges(f)>3);
 - 
 
386
1106
387 
		// Make sure we are not trying to connect a vertex to itself.
 1107 
        VertexIDIterator v = m.vertices_begin();
- 
 
 1108 
        pmin = pmax = m.pos(*v);
388 
		assert(v0 != v1);
 1109 
        ++v;
- 
 
 1110 
        for(; v != m.vertices_end(); ++v){
- 
 
 1111 
            pmin = v_min(m.pos(*v), pmin);
- 
 
 1112 
            pmax = v_max(m.pos(*v), pmax);
- 
 
 1113 
        }
- 
 
 1114 
    }
389
1115
390 
		// Find the halfedge emanating from v0 which belongs to the
 1116 
    void bsphere(const Manifold& m, Manifold::Vec& c, float& r)
391 
		// face, we need to split.
 1117 
    {
392 
		VertexCirculator vc0(v0);
 1118 
        Manifold::Vec p0, p7;
393 
		while(vc0.get_halfedge()->face != f && !vc0.end()) vc0++;
 - 
 
394 
		assert(!vc0.end());
 1119 
        bbox(m, p0, p7);
395 
		HalfEdgeIter h0 = vc0.get_halfedge();
 - 
 
396 
		assert(h0->face == f); // Sanity check.
 - 
 
397
- 
 
398 
		// The halfedge belonging to f, going out from v0, is denoted h.
 - 
 
399 
		// Move along h until we hit v1. Now we have the halfedge which
 - 
 
400 
		// belongs to f and points to v1.
 1120 
        Manifold::Vec rad = (p7 - p0) * 0.5f;
401 
		HalfEdgeIter h = h0;
 1121 
        c = p0 + rad;
402 
		while(h->vert != v1)
 1122 
        r = rad.length();
403 
			h = h->next;
 1123 
    }
404
1124
405 
		// Create a new halfedge ha which connects v1 and v0 closing the first
 - 
 
406 
		// loop. This new halfedge becomes f->last
 - 
 
407 
		assert(h != h0);
 - 
 
408 
		HalfEdgeIter h1 = h->next;
 - 
 
409 
		HalfEdgeIter ha = create_halfedge();
 - 
 
410 
		link(h,ha);
 - 
 
411 
		link(ha, h0);
 - 
 
412 
		ha->face = f;
 - 
 
413 
		ha->vert = v0;
 - 
 
414 
		f->last = ha;
 - 
 
415
1125
416 
		// Create a new face, f2, and set all halfedges in the remaining part of
 - 
 
417 
		// the polygon to point to this face.
 - 
 
418 
		h = h1;
 1126
419 
		FaceIter f2 = create_face();
 1127 
    bool precond_collapse_edge(const Manifold& m, HalfEdgeID h)
420 
		while(h->vert != v0)
 - 
 
421 
		{
 1128 
    {
- 
 
 1129 
        Walker hew = m.walker(h);
- 
 
 1130 
        HalfEdgeID ho = hew.opp().halfedge();
- 
 
 1131 
        VertexID v0 = hew.opp().vertex();
- 
 
 1132 
        VertexID v1 = hew.vertex();
- 
 
 1133
- 
 
 1134 
        // get the one-ring of v0
- 
 
 1135 
        vector<VertexID> link0;
422 
			h->face = f2;
 1136 
        vector<FaceID> faces0;
- 
 
 1137 
        for(Walker vj = m.walker(h);
- 
 
 1138 
            !vj.full_circle(); vj = vj.circulate_vertex_ccw()){
- 
 
 1139 
            link0.push_back(vj.vertex());
- 
 
 1140 
            if(vj.halfedge() != h)
- 
 
 1141 
                faces0.push_back(vj.face());
423 
			h = h->next;
 1142 
        }
- 
 
 1143 
        assert(link0.size() > 1);
- 
 
 1144
- 
 
 1145 
        // get the one-ring of v1
- 
 
 1146 
        vector<VertexID> link1;
- 
 
 1147 
        vector<FaceID> faces1;
- 
 
 1148 
        for(Walker vj = m.walker(ho);
- 
 
 1149 
            !vj.full_circle(); vj = vj.circulate_vertex_ccw()){
- 
 
 1150 
            link1.push_back(vj.vertex());
- 
 
 1151 
            if(vj.halfedge() != ho)
- 
 
 1152 
                faces1.push_back(vj.face());
424 
		}
 1153 
        }
425 
		h->face = f2;
 - 
 
426 
		assert(h != h1);
 1154 
        assert(link1.size() > 1);
427
1155
428 
		// Create a new halfedge hb to connect v0 and v1. this new halfedge
 1156 
        // sort the vertices of the two rings
429 
		// becomes f2->last
 - 
 
430 
		HalfEdgeIter hb = create_halfedge();
 1157 
        sort(link0.begin(), link0.end());
431 
		link(h,hb);
 - 
 
432 
		link(hb, h1);
 1158 
        sort(link1.begin(), link1.end());
433 
		hb->face = f2;
 - 
 
434 
		hb->vert = v1;
 - 
 
435 
		f2->last = hb;
 - 
 
436
1159
437 
		// Complete the operation by gluing the two new halfedges.
 1160 
        // get the intersection of the shared vertices from both rings
- 
 
 1161 
        vector<VertexID> lisect;
- 
 
 1162 
        std::back_insert_iterator<vector<VertexID> > lii(lisect);
- 
 
 1163 
        set_intersection(link0.begin(), link0.end(),
- 
 
 1164 
                         link1.begin(), link1.end(),
438 
		glue(ha, hb);
 1165 
                         lii);
439
1166
440 
		// Assert that the pointers are sane :-)
 1167 
        // sort the faces of the two rings
441 
		assert(h1->prev->opp->next == h0);
 1168 
        sort(faces0.begin(), faces0.end());
442 
		assert(h0->prev->opp->next == h1);
 1169 
        sort(faces1.begin(), faces1.end());
- 
 
 1170
- 
 
 1171 
        // get the intersection of the shared faces from both rings
443 
		assert(hb->next->face == f2);
 1172 
        vector<FaceID> fisect;
- 
 
 1173 
        std::back_insert_iterator<vector<FaceID> > fii(fisect);
444 
		assert(hb->next->next->face == f2);
 1174 
        set_intersection(faces0.begin(), faces0.end(),
- 
 
 1175 
                         faces1.begin(), faces1.end(),
445 
		assert(hb->face == f2);
 1176 
                         fii);
- 
 
 1177 
        if(fisect.size() > 0)
- 
 
 1178 
            return false;
446
1179
- 
 
 1180 
        int k = 0;
447 
		// Return the newly created face
 1181 
        // if the adjacent face is a triangle (see 2)
- 
 
 1182 
        if(hew.next().next().next().halfedge() == h){
448 
		return f2;
 1183 
            VertexID v = hew.next().vertex();
449 
	}
 - 
 
450
1184
451 
	void Manifold::triangulate(FaceIter f)
 1185 
            // valency test (see 5)
452 
	{
 - 
 
453 
		// Assert sanity of pointers
 1186 
            if(valency(m, v) < 3)
454 
		assert(f->last->next->next != f->last);
 - 
 
455 
		assert(f->last->next != f->last);
 1187 
                return false;
456 
		assert(--(++f) == f);
 - 
 
457 
		// As long as f is not a triangle.
 1188
458 
		while(f->last->next->next->next != f->last)
 - 
 
459 
		{
 - 
 
460 
			assert(no_edges(f) != 3);
 - 
 
461 
			// Call split face to split f into a triangle
 - 
 
462 
			// from the first three vertices and a polygon
 1189 
            // remove the vertex shared by the two rings from the intersection
463 
			// containing the rest of the vertices. In the
 1190 
            vector<VertexID>::iterator iter;
464 
			// next iteration, f becomes this polygon.
 1191 
            iter = find(lisect.begin(), lisect.end(), v);
465
- 
 
466 
			assert(f->last->next->next != f->last);
 1192 
            assert(iter != lisect.end());
467 
			VertexIter v0 = f->last->vert;
 1193 
            lisect.erase(iter);
468 
			VertexIter v1 = f->last->next->next->vert;
 - 
 
469 
			assert(v0 != v1);
 1194 
            ++k;
470 
			f = split_face(f, v0, v1);
 - 
 
471 
		}
 1195 
        }
- 
 
 1196 
        // if the adjacent face is a triangle (see 2)
- 
 
 1197 
        if(hew.opp().next().next().next().halfedge() == hew.opp().halfedge()){
- 
 
 1198 
            VertexID v = hew.opp().next().vertex();
- 
 
 1199
- 
 
 1200 
            // valency test (see 5)
- 
 
 1201 
            if(valency(m, v) < 3)
- 
 
 1202 
                return false;
- 
 
 1203
- 
 
 1204 
            // remove the vertex shared by the two rings from the intersection
- 
 
 1205 
            vector<VertexID>::iterator iter;
- 
 
 1206 
            iter = find(lisect.begin(), lisect.end(), v);
- 
 
 1207 
            assert(iter != lisect.end());
- 
 
 1208 
            lisect.erase(iter);
- 
 
 1209 
            ++k;
472 
	}
 1210 
        }
- 
 
 1211 
        // double edge test (see 3)
- 
 
 1212 
        if(lisect.size() != 0)
- 
 
 1213 
            return false;
473
1214
- 
 
 1215 
        // tetrahedon test (see 4)
474 
	bool Manifold::merge_faces(FaceIter f1, HalfEdgeIter h)
 1216 
        if(k == 2 && (link0.size() + link1.size() == 6))
475 
	{
 - 
 
476 
		assert(h->face == f1);
 1217 
            return false;
477
1218
478 
		HalfEdgeIter ho = h->opp;
 1219 
        // test that we do not merge holes (see 6)
479 
		FaceIter f2 = ho->face;
 1220 
        if(boundary(m, v0) && boundary(m, v1) && hew.face() != InvalidFaceID && hew.opp().face() != InvalidFaceID)
480 
		HalfEdgeIter hn = h->next;
 1221 
            return false;
481 
		HalfEdgeIter hon = ho->next;
 - 
 
482
1222
483 
		if(hn->vert == hon->vert) return false;
 1223 
        return true;
- 
 
 1224 
    }
484
1225
485 
		HalfEdgeIter hp = h->prev;
 - 
 
486 
		HalfEdgeIter hop = ho->prev;
 1226 
    bool precond_flip_edge(const Manifold& m, HalfEdgeID h)
487 
		VertexIter v  = h->vert;
 1227 
    {
488 
		VertexIter vo = ho->vert;
 1228 
        Walker j = m.walker(h);
489
1229
490 
		link(hop, hn);
 1230 
        FaceID hf = j.face();
- 
 
 1231 
        //        HalfEdgeID ho = j.opp().halfedge();
491 
		v->he = hn;
 1232 
        FaceID hof = j.opp().face();
492
1233
493 
		link(hp, hon);
 1234 
        // boundary case
- 
 
 1235 
        if(hf == InvalidFaceID || hof == InvalidFaceID)
494 
		vo->he = hon;
 1236 
            return false;
495
1237
496 
		f1->last = hn;
 - 
 
497 
		HalfEdgeIter hx = hon;
 1238 
        // We can only flip an edge if both incident polygons are triangles.
498 
		assert(hx->face == f2);
 - 
 
499 
		while(hx->face != f1)
 1239 
        if(no_edges(m, hf) != 3 || no_edges(m, hof) !=3)
500 
		{
 - 
 
501 
			hx->face = f1;
 - 
 
502 
			hx = hx->next;
 1240 
            return false;
503 
		}
 - 
 
504
1241
- 
 
 1242 
        // non boundary vertices with a valency of less than 4(less than 3 after operation) degenerates mesh.
505 
		check_boundary_consistency(v);
 1243 
        VertexID hv = j.vertex();
506 
		check_boundary_consistency(vo);
 1244 
        VertexID hov = j.opp().vertex();
- 
 
 1245 
        if((valency(m, hv) < 4 && !boundary(m, hv)) || (valency(m, hov) < 4 && !boundary(m, hov)))
- 
 
 1246 
            return false;
507
1247
- 
 
 1248 
        // Disallow flip if vertices being connected already are.
508 
		erase_halfedge(h);
 1249 
        VertexID hnv = j.next().vertex();
- 
 
 1250 
        VertexID honv = j.opp().next().vertex();
509 
		erase_halfedge(ho);
 1251 
        if(connected(m, hnv, honv))
510 
		erase_face(f2);
 1252 
            return false;
511
1253
512 
		return true;
 1254 
        return true;
513 
	}
 1255 
    }
514
1256
515
- 
 
516 
	VertexIter Manifold::safe_triangulate(FaceIter f)
 1257 
    bool boundary(const Manifold& m, VertexID v)
517 
	{
 1258 
    {
518 
		Vec3f p(0.0f);
 - 
 
519 
		FaceCirculator fc(f);
 - 
 
520 
		for(;!fc.end(); ++fc)
 - 
 
521 
			p += fc.get_vertex()->pos;
 - 
 
522 
		int n = fc.no_steps();
 - 
 
523 
		p /= n;
 - 
 
524 
		VertexIter v = create_vertex(p);
 1259 
        Walker j  = m.walker(v);
525 
		face_insert_point(f,v);
 1260 
        return boundary(m, j.halfedge());
526 
		return v;
 - 
 
527 
	}
 1261 
    }
528
- 
 
529
- 
 
530 
	void Manifold::face_insert_point(FaceIter f, VertexIter v)
 1262 
    int valency(const Manifold& m, VertexID v)
531 
	{
 1263 
    {
- 
 
 1264 
        // perform full circulation to get valency
532 
		vector<HalfEdgeIter> eout;
 1265 
        Walker vj = m.walker(v);
533 
		vector<HalfEdgeIter> ein;
 1266 
        while(!vj.full_circle())
534
- 
 
535 
		HalfEdgeIter hlast = f->last;
 1267 
            vj = vj.circulate_vertex_cw();
536 
		HalfEdgeIter h = hlast;
 1268 
        return vj.no_steps();
- 
 
 1269 
    }
537
1270
538 
		do
 - 
 
- 
 
 1271 
    Manifold::Vec normal(const Manifold& m, VertexID v)
539 
		{
 1272 
    {
540 
			HalfEdgeIter hn = h->next;
 1273 
        Manifold::Vec p0 = m.pos(v);
- 
 
 1274 
        vector<Manifold::Vec> one_ring;
541
1275
- 
 
 1276 
        // run through outgoing edges, and store them normalized
- 
 
 1277 
        for(Walker vj = m.walker(v); !vj.full_circle(); vj = vj.circulate_vertex_ccw()){
- 
 
 1278 
            Manifold::Vec edge = m.pos(vj.vertex())-p0;
542 
			HalfEdgeIter o = create_halfedge();
 1279 
            float l = length(edge);
543 
			HalfEdgeIter i = create_halfedge();
 1280 
            if(l > 0.0f) one_ring.push_back(edge/l);
- 
 
 1281 
        }
544
1282
545 
			FaceIter fn = create_face();
 1283 
        Manifold::Vec n(0);
546 
			i->face = fn;
 1284 
        size_t N = one_ring.size();
547 
			i->vert = v;
 1285 
        if(N<2)
548 
			o->face = fn;
 - 
 
549 
			o->vert = h->opp->vert;
 1286 
            return Manifold::Vec(0);
550 
			h->face = fn;
 - 
 
551 
			fn->last = o;
 - 
 
552
1287
553 
			link(i,o);
 1288 
        size_t N_count = N;
554 
			link(o,h);
 1289 
        if(boundary(m, v))
555 
			link(h,i);
 1290 
            N_count -= 1;
556
1291
- 
 
 1292 
        // sum up the normals of each face surrounding the vertex
557 
			eout.push_back(o);
 1293 
        for(size_t i = 0; i < N_count; ++i){
558 
			ein.push_back(i);
 1294 
            Manifold::Vec e0 = one_ring[i];
- 
 
 1295 
            Manifold::Vec e1 = one_ring[(i+1) % N];
559
1296
560 
			h = hn;
 1297 
            Manifold::Vec n_part = normalize(cross(e0, e1));
- 
 
 1298 
            n += n_part * acos(max(-1.0, min(1.0, dot(e0, e1))));
561 
		}
 1299 
        }
562 
		while(h != hlast);
 - 
 
563
1300
564 
		int N = eout.size();
 1301 
        // normalize and return the normal
565 
		for(int i=0;i<N;++i)
 1302 
        float sqr_l = sqr_length(n);
566 
			glue(ein[i],eout[(i+1)%N]);
 1303 
        if(sqr_l > 0.0f) return n / sqrt(sqr_l);
567
1304
568 
		v->he = eout[0];
 1305 
        return n;
569 
		erase_face(f);
 - 
 
570 
	}
 1306 
    }
571
1307
572
- 
 
573 
	bool Manifold::flip(HalfEdgeIter h1)
 1308 
    bool connected(const Manifold& m, VertexID v0, VertexID v1)
574 
	{
 1309 
    {
575 
		FaceIter f1 = h1->face;
 - 
 
576 
		HalfEdgeIter h2 = h1->opp;
 - 
 
577 
		FaceIter f2 = h2->face;
 - 
 
578
- 
 
579 
		if(f1 == NULL_FACE_ITER || f2 == NULL_FACE_ITER)
 - 
 
580 
			return false;
 - 
 
581
- 
 
582 
		// We can only flip an edge if both incident polygons
 1310 
        for(Walker vj = m.walker(v0); !vj.full_circle(); vj = vj.circulate_vertex_cw()){
583 
		// are triangles. Otherwise, this operation makes no sense.
 - 
 
584 
		if(no_edges(f1) != 3)
 1311 
            if(vj.vertex() == v1)
585 
			return false;
 1312 
                return true;
586 
		if(no_edges(f2) !=3)
 - 
 
587 
			return false;
 1313 
        }
588
- 
 
589 
		// If the valency of either vertex incident on the edge
 - 
 
590 
		// being flipped is three, we cannot perform this operation.
 - 
 
591 
		// That is because the vertex would then have valency two
 - 
 
592 
		// after the operation which means it would be degenerate.
 - 
 
593 
		VertexIter va = h1->vert;
 - 
 
594 
		VertexIter vb = h2->vert;
 - 
 
595 
		int vala = valency(va);
 - 
 
596 
		int valb = valency(vb);
 - 
 
597 
		if((vala <= 3 && !is_boundary(va)) ||
 - 
 
598 
		   (valb <= 3 && !is_boundary(vb)))
 - 
 
599 
			return false;
 1314 
        return false;
- 
 
 1315 
    }
600
1316
601 
		// If the two vertices being connected by the flip are already
 1317 
    int no_edges(const Manifold& m, FaceID f)
- 
 
 1318 
    {
602 
		// connected, the mesh would become degenerate, so we disallow
 1319 
        // perform full circulation to get valency
603 
		// the operation.
 1320 
        Walker w = m.walker(f);
604 
		VertexIter vc = h1->next->vert;
 1321 
        for(; !w.full_circle(); w = w.circulate_face_cw());
605 
		VertexIter vd = h2->next->vert;
 1322 
        return w.no_steps();
- 
 
 1323 
    }
606 
		if(is_connected(vc,vd))
 1324 
    Manifold::Vec normal(const Manifold& m, FaceID f)
- 
 
 1325 
    {
607 
			return false;
 1326 
        vector<Manifold::Vec> v;
608
1327
609 
		HalfEdgeIter ha = h1->next;
 1328 
        int k=0;
610 
		HalfEdgeIter hb = h1->prev;
 1329 
        for(Walker  w = m.walker(f); !w.full_circle(); w = w.circulate_face_ccw(),++k)
611 
		HalfEdgeIter hc = h2->next;
 1330 
            v.push_back(m.pos(w.vertex()));
612 
		HalfEdgeIter hd = h2->prev;
 - 
 
613
1331
- 
 
 1332 
        Manifold::Vec norm(0);
- 
 
 1333 
        for(int i=0;i<k;++i)
- 
 
 1334 
        {
- 
 
 1335 
            norm[0] += (v[i][1]-v[(i+1)%k][1])*(v[i][2]+v[(i+1)%k][2]);
- 
 
 1336 
            norm[1] += (v[i][2]-v[(i+1)%k][2])*(v[i][0]+v[(i+1)%k][0]);
- 
 
 1337 
            norm[2] += (v[i][0]-v[(i+1)%k][0])*(v[i][1]+v[(i+1)%k][1]);
614 
		hd->face = f1;
 1338 
        }
- 
 
 1339 
        float l = sqr_length(norm);
615 
		hb->face = f2;
 1340 
        if(l>0.0f)
616 
		f1->last = h1;
 1341 
            norm /= sqrt(l);
617 
		f2->last = h2;
 1342 
        return norm;
- 
 
 1343 
    }
618
1344
619 
		link(ha,h1);
 - 
 
620 
		link(h1,hd);
 - 
 
621 
		link(hd,ha);
 - 
 
622
1345
- 
 
 1346 
    float area(const Manifold& m, FaceID f)
- 
 
 1347 
    {
- 
 
 1348 
        // Get all projected vertices
- 
 
 1349 
        vector<Manifold::Vec> vertices;
- 
 
 1350 
        Walker w = m.walker(f);
- 
 
 1351 
        for(; !w.full_circle(); w = w.circulate_face_ccw())
- 
 
 1352 
            vertices.push_back(m.pos(w.vertex()));
623 
		link(hc,h2);
 1353 
        float area = 0;
624 
		link(h2,hb);
 1354 
        int k = w.no_steps();
- 
 
 1355 
        Manifold::Vec n = normal(m,f);
- 
 
 1356 
        for(int i = 0; i < k; ++i)
- 
 
 1357 
        {
- 
 
 1358 
            Manifold::Vec A = cross(vertices[i], vertices[(i+1 )%k]);
- 
 
 1359 
            float s = sign(dot(n, A));
- 
 
 1360 
            area += 0.5 * s * length(A);
- 
 
 1361 
        }
625 
		link(hb,hc);
 1362 
        return abs(area);
- 
 
 1363 
    }
626
1364
- 
 
 1365 
    Manifold::Vec centre(const Manifold& m, FaceID f)
- 
 
 1366 
    {
627 
		h1->vert = vd;
 1367 
        Manifold::Vec c(0);
628 
		h2->vert = vc;
 1368 
        Walker w = m.walker(f);
629
1369
630 
		va->he = ha;
 - 
 
631 
		vb->he = hc;
 1370 
        for(; !w.full_circle(); w = w.circulate_face_ccw()) c += m.pos(w.vertex());
632
1371
633 
		check_boundary_consistency(va);
 - 
 
634 
		check_boundary_consistency(vb);
 1372 
        c /= w.no_steps();
635 
		return true;
 1373 
        return c;
636 
	}
 1374 
    }
637
1375
638 
	/** Give each vertex a unique id corresponding to its iterator
 1376 
    float perimeter(const Manifold& m, FaceID f)
639 
		position */
 - 
 
640 
	void Manifold::enumerate_vertices()
 - 
 
641 
	{
 1377 
    {
- 
 
 1378 
        float p=0.0;
- 
 
 1379 
        Walker w = m.walker(f);
642 
		int i=0;
 1380
643 
		for(VertexIter vi=vertices_begin(); vi != vertices_end(); ++vi)
 1381 
        for(; !w.full_circle(); w = w.circulate_face_cw()) p += length(m, w.halfedge());
644 
			vi->touched = i++;
 1382 
        return p;
645 
	}
 1383 
    }
646
1384
647 
	/** Give each halfedge a unique id corresponding to its iterator
 - 
 
648 
		position */
 - 
 
649 
	void Manifold::enumerate_halfedges()
 1385 
    bool boundary(const Manifold& m, HalfEdgeID h)
650 
	{
 1386 
    {
651 
		int i=0;
 1387 
        Walker w = m.walker(h);
652 
		for(HalfEdgeIter h=halfedges_begin(); h != halfedges_end(); ++h)
 1388 
        return w.face() == InvalidFaceID || w.opp().face() == InvalidFaceID;
653 
			h->touched = i++;
 - 
 
654 
	}
 1389 
    }
655
1390
656 
	/** Give each face a unique id corresponding to its iterator
 - 
 
657 
		position */
 - 
 
658 
	void Manifold::enumerate_faces()
 1391 
    float length(const Manifold& m, HalfEdgeID h)
659 
	{
 1392 
    {
660 
		int i=0;
 1393 
        Walker w = m.walker(h);
661 
		for(FaceIter f=faces_begin(); f != faces_end(); ++f)
 1394 
        return (m.pos(w.vertex()) - m.pos(w.opp().vertex())).length();
662 
			f->touched = i++;
 - 
 
663 
	}
 1395 
    }
664
- 
 
665
- 
 
666 
}
 1396 
}
667 
 
 -