WebSVN – gelsvn – Diff – /trunk/src/HMesh/Manifold.cpp


/* ----------------------------------------------------------------------- *
 * This file is part of GEL, http://www.imm.dtu.dk/GEL
 * Copyright (C) the authors and DTU Informatics
 * For license and list of authors, see ../../doc/intro.pdf
 * ----------------------------------------------------------------------- */
#include <iterator>
#include "Manifold.h"
 
#include <iostream>
#include <vector>
#include <map>
#include <iterator>
 
#include "../Geometry/TriMesh.h"
 
namespace HMesh
{
	
    using namespace std;
    using namespace Geometry;
    using namespace CGLA;
	
    namespace
    {
        /************************************************************
		 * Edgekeys and Edges for halfedge identification during build
		 ************************************************************/
        class EdgeKey
        {
        public:
            EdgeKey(VertexID va, VertexID vb)
            {
                if(va < vb){
                    v0 = va;
                    v1 = vb;
                }
                else{
                    v0 = vb;
                    v1 = va;
                }
            }
			
            bool operator<(const EdgeKey& k2) const
            {
                if(v0 < k2.v0){
                    return true;
                }
                else if( k2.v0 < v0){
                    return false;
                }
                else{
                    return v1 < k2.v1;
                }
            }
        private:
            VertexID v0;
            VertexID v1;
        };
		
        struct Edge
        {
            HalfEdgeID h0;
            HalfEdgeID h1;
            int count;
            Edge() : count(0){}
        };
    }
	
    /*********************************************
	 * Public functions
	 *********************************************/
    void Manifold::build(const TriMesh& mesh)
    {
        // A vector of 3's - used to tell build how many indices each face consists of
        vector<int> faces(mesh.geometry.no_faces(), 3);
		
        build_template( static_cast<size_t>(mesh.geometry.no_vertices()),
					   reinterpret_cast<const float*>(&mesh.geometry.vertex(0)),
					   static_cast<size_t>(faces.size()),
					   static_cast<const int*>(&faces[0]),
					   reinterpret_cast<const int*>(&mesh.geometry.face(0)));
    }
    
    void Manifold::build(   size_t no_vertices,
						 const float* vertvec,
						 size_t no_faces,
						 const int* facevec,
						 const int* indices)
    {
        build_template(no_vertices, vertvec, no_faces, facevec, indices);
    }
    
    void Manifold::build(   size_t no_vertices,
						 const double* vertvec,
						 size_t no_faces,
						 const int* facevec,
						 const int* indices)
    {
        build_template(no_vertices, vertvec, no_faces, facevec, indices);
    }
    
    FaceID Manifold::add_face(std::vector<Manifold::Vec> points)
    {
        int F = points.size();
        vector<int> indices;
        for(size_t i=0;i<points.size(); ++i)
            indices.push_back(i);
        FaceID fid = *faces_end();
        build(points.size(), reinterpret_cast<double*>(&points[0]), 1, &F, &indices[0]);
        return fid;
    }
    
    bool Manifold::remove_face(FaceID fid)
    {
        if(!in_use(fid))
            return false;
        
        HalfEdgeID he = kernel.last(fid);
        HalfEdgeID last = he;
        
        vector<HalfEdgeID> halfedges;
        do
        {
            halfedges.push_back(he);
            kernel.set_face(he, InvalidFaceID);
            he = kernel.next(he);
        }
        while(he != last);
        
        vector<HalfEdgeID> halfedges_garbage;
        vector<VertexID> vertices_garbage;
        for(size_t i=0;i<halfedges.size(); ++i)
        {
            HalfEdgeID h = halfedges[i];
            HalfEdgeID hopp = kernel.opp(h);
            if(kernel.face(hopp) == InvalidFaceID)
            {
                halfedges_garbage.push_back(h);
                VertexID v0 = kernel.vert(hopp);
                if(valency(*this, v0) <= 2 )
                    vertices_garbage.push_back(v0);
                else {
                    link(kernel.prev(h), kernel.next(hopp));
                    kernel.set_out(v0, kernel.opp(kernel.prev(h)));
                }
                VertexID v1 = kernel.vert(h);
                if(valency(*this, v1)>2)
                {
                    link(kernel.prev(hopp),kernel.next(h));
                    kernel.set_out(v1, kernel.opp(kernel.prev(hopp)));
                }
                
            }
        }
        for(size_t i=0;i<halfedges_garbage.size();++i){
            kernel.remove_halfedge(kernel.opp(halfedges_garbage[i]));
            kernel.remove_halfedge(halfedges_garbage[i]);
        }
        for(size_t i=0;i<vertices_garbage.size(); ++i)
            kernel.remove_vertex(vertices_garbage[i]);
        
        kernel.remove_face(fid);
        return true;
    }
    
 
    bool Manifold::remove_edge(HalfEdgeID hid)
    {
        if(!in_use(hid))
            return false;
        
        FaceID f0 = kernel.face(hid);
        FaceID f1 = kernel.face(kernel.opp(hid));
        
        remove_face(f0);
        remove_face(f1);
 
        return true;
    }
 
    
    
    bool Manifold::remove_vertex(VertexID vid)
    {
        if(!in_use(vid))
            return false;
        
        Walker w = Manifold::walker(vid);
    
        vector<FaceID> faces;
        
        for(; !w.full_circle(); w = w.circulate_vertex_ccw())
            faces.push_back(w.face());
        
        for(size_t i=0;i<faces.size();++i)
            remove_face(faces[i]);
            
        return true;
    }
 
 
	
    void Manifold::collapse_edge(HalfEdgeID h, bool avg_vertices)
    {
        HalfEdgeID ho = kernel.opp(h);
        VertexID hv = kernel.vert(h);
        VertexID hov = kernel.vert(ho);
        HalfEdgeID hn = kernel.next(h);
        HalfEdgeID hp = kernel.prev(h);
        HalfEdgeID hon = kernel.next(ho);
        HalfEdgeID hop = kernel.prev(ho);
		FaceID f = kernel.face(h);
		FaceID fo = kernel.face(ho);
		
        // average the vertex positions
        pos(hv) = avg_vertices ? (0.5f * (pos(hov) + pos(hv))) : pos(hv);
		
        // update all halfedges pointing to hov to point to hv, effectively removing hov from all loops
        HalfEdgeID he = kernel.out(hov);
        HalfEdgeID last = he;
		do {
			assert(kernel.vert(kernel.opp(he)) == hov);
            kernel.set_vert(kernel.opp(he), hv);
            he = kernel.next(kernel.opp(he));
        }
		while(he != last);
        kernel.set_out(hv, hn);
		
        // link hp and hn, effectively removing h from opposite loop
        link(hp, hn);
        // make face owning h own hn instead
        if(kernel.face(h) != InvalidFaceID)
            kernel.set_last(f, hn);
		
        // link hop and hon, effectively removing h from opposite face loop
        link(hop, hon);
        // make opposite face owning h own hon instead
        if(kernel.face(ho) != InvalidFaceID)
            kernel.set_last(fo, hon);
		
        // remove the obsolete entities
        kernel.remove_vertex(hov);
        kernel.remove_halfedge(h);
        kernel.remove_halfedge(ho);
		
        // verify that remaining faces haven't become degenerate because of collapse
        remove_face_if_degenerate(hn);
        remove_face_if_degenerate(hon);
		
        // verify that v is sane after collapse
        ensure_boundary_consistency(hv);
    }
	
    FaceID Manifold::split_face_by_edge(FaceID f, VertexID v0, VertexID v1)
    {
		assert(!connected(*this, v0, v1));
        HalfEdgeID he = kernel.last(f);
        HalfEdgeID last = he;
        int steps = 0;
        while(he != last || steps == 0){
            ++steps;
            he = kernel.next(he);
        }
		
        // make sure this is not a triangle
        assert(steps > 3);
        // make sure we are not trying to connect a vertex to itself
        assert(v0 != v1);
		
		HalfEdgeID h0 = kernel.out(v0);
		for(Walker w = walker(v0); !w.full_circle(); w = w.circulate_vertex_cw()){
			if(w.face() == f){
				h0 = w.halfedge();
				break;
			}
		}
		assert(kernel.face(h0) != InvalidFaceID);
        assert(kernel.face(h0) == f);
		
        // the halfedge belonging to f, going out from v0, is denoted h. Move along h until we hit v1.
        // now we have the halfedge which belongs to f and points to v1.
        HalfEdgeID h = h0;
        while(kernel.vert(h) != v1){
            h = kernel.next(h);
        }
        assert(h != h0);
		
        // create a new halfedge ha which connects v1 and v0 closing the first loop.
        HalfEdgeID h1 = kernel.next(h);
        HalfEdgeID ha = kernel.add_halfedge();
        link(h, ha);
        link(ha, h0);
        kernel.set_face(ha, f);
        kernel.set_vert(ha, v0);
        kernel.set_last(f, ha);
		
        // create a new face, f2, and set all halfedges in the remaining part of the polygon to point to this face.
        h = h1;
        FaceID f2 = kernel.add_face();
        while(kernel.vert(h) != v0){
            kernel.set_face(h, f2);
            h = kernel.next(h);
        }
        kernel.set_face(h, f2);
        assert(h != h1);
		
        // create a new halfedge hb to connect v0 and v1.
        HalfEdgeID hb = kernel.add_halfedge();
        link(h, hb);
        link(hb, h1);
        kernel.set_face(hb, f2);
        kernel.set_vert(hb, v1);
        kernel.set_last(f2, hb);
		
        // complete the operation by gluing the two new halfedges
        glue(ha, hb);
		
        // assert sanity of operation
        assert(kernel.next(kernel.opp(kernel.prev(h1))) == h0);
        assert(kernel.next(kernel.opp(kernel.prev(h0))) == h1);
        assert(kernel.face(kernel.next(hb)) == f2);
        assert(kernel.face(kernel.next(kernel.next(hb))) == f2);
        assert(kernel.face(hb) == f2);
		
        // return handle to newly created face
        return f2;
    }
	
    VertexID Manifold::split_face_by_vertex(FaceID f)
    {
        //create the new vertex, with the barycenter of the face as position
        Manifold::Vec p(0.0f);
        HalfEdgeID last_he = kernel.last(f);
        HalfEdgeID he = last_he;
        int steps = 0;
		
        while(he != last_he || steps == 0){
            p += positions[kernel.vert(he)];
            ++steps;
            he = kernel.next(he);
        }
		
        p /= steps;
		
        VertexID v = kernel.add_vertex();
        positions[v]  = p;
		
        //circulate the face, create halfedges and connect to vertex
        vector<HalfEdgeID> eout;
        vector<HalfEdgeID> ein;
        last_he = kernel.last(f);
        he = last_he;
		
        do{
            HalfEdgeID hn = kernel.next(he);
			
            HalfEdgeID ho = kernel.add_halfedge();
            HalfEdgeID hi = kernel.add_halfedge();
			
            FaceID fn = kernel.add_face();
            kernel.set_face(hi, fn);
            kernel.set_vert(hi, v);
            kernel.set_face(ho, fn);
            kernel.set_vert(ho, kernel.vert(kernel.opp(he)));
            kernel.set_face(he, fn);
            kernel.set_last(fn, ho);
			
            link(hi, ho);
            link(ho, he);
            link(he, hi);
			
            eout.push_back(ho);
            ein.push_back(hi);
			
            he = hn;
        }
        while(he != last_he);
		
        // glue new halfedges together
        size_t N = eout.size();
        for(size_t i = 0; i < N; ++i){
            glue(ein[i], eout[(i+1)%N]);
        }
        kernel.set_out(v, eout[0]);
		
        //remove the now replaced face
        kernel.remove_face(f);
		
        return v;
    }
    VertexID Manifold::split_edge(HalfEdgeID h)
    {
        HalfEdgeID ho = kernel.opp(h);
        VertexID v = kernel.vert(h);
        VertexID vo = kernel.vert(ho);
		
        //create the new vertex with middle of edge as position and update connectivity
        VertexID vn = kernel.add_vertex();
        positions[vn] = .5f * (positions[v] + positions[vo]);
        kernel.set_out(vn, h);
		
        //create two necessary halfedges, and update connectivity
        HalfEdgeID hn = kernel.add_halfedge();
        HalfEdgeID hno = kernel.add_halfedge();
		
        kernel.set_out(vo, hn);
        kernel.set_out(v, ho);
		
        glue(hn, hno);
		
        link(kernel.prev(h), hn);
        link(hn, h);
		
        kernel.set_vert(hn, vn);
		
        link(hno, kernel.next(ho));
        link(ho, hno);
		
        kernel.set_vert(hno, vo);
        kernel.set_vert(ho, vn);
		
        // update faces in case of non boundary edge
        if(kernel.face(h) != InvalidFaceID)
            kernel.set_last(kernel.face(h), hn);
		
        if(kernel.face(ho) != InvalidFaceID)
            kernel.set_last(kernel.face(ho), ho);
		
        // update new edge with faces from existing edge
        kernel.set_face(hn, kernel.face(h));
        kernel.set_face(hno, kernel.face(ho));
		
        //if split occurs on a boundary, consistency must be ensured.
        ensure_boundary_consistency(vn);
        ensure_boundary_consistency(v);
        ensure_boundary_consistency(vo);
		
        return vn;
    }
    
    size_t link_intersection(const Manifold& m, VertexID v0, VertexID v1, vector<VertexID>& lisect)
    {
        // get the one-ring of v0
        vector<VertexID> link0;
        for(Walker vj = m.walker(v0);
			!vj.full_circle(); vj = vj.circulate_vertex_ccw())
            link0.push_back(vj.vertex());
		
        // get the one-ring of v1
        vector<VertexID> link1;
        for(Walker vj = m.walker(v1);
			!vj.full_circle(); vj = vj.circulate_vertex_ccw())
            link1.push_back(vj.vertex());
		
        // sort the vertices of the two rings
        sort(link0.begin(), link0.end());
        sort(link1.begin(), link1.end());
		
        // get the intersection of the shared vertices from both rings
        std::back_insert_iterator<vector<VertexID> > lii(lisect);
        set_intersection(link0.begin(), link0.end(),
						 link1.begin(), link1.end(),
						 lii);
        
        return lisect.size();
    }
    
    bool Manifold::stitch_boundary_edges(HalfEdgeID h0, HalfEdgeID h1)
    {
        // Cannot stitch an edge with itself
        if(h0 == h1)
            return false;
        
        // Only stitch a pair of boundary edges.
        if(kernel.face(h0) == InvalidFaceID && kernel.face(h1) == InvalidFaceID)
        {
            HalfEdgeID h0o = kernel.opp(h0);
            HalfEdgeID h1o = kernel.opp(h1);
            VertexID v0a = kernel.vert(h0);
            VertexID v0b = kernel.vert(kernel.opp(h1));
            VertexID v1b = kernel.vert(h1);
            VertexID v1a = kernel.vert(kernel.opp(h0));
            
            // Case below implies that h0 and h1 are the same edge with different ID
            // That should not happen.
            assert(!(v0a == v0b && v1a == v1b));
            
            if(connected(*this, v0a, v0b))
                return false;
            if(connected(*this, v1a, v1b))
                return false;
            
            
            if(v0b != v0a)
            {
                
                // Check the link intersection v0a and v0b are welded together
                // if they share a neighbouring vertex, it will appear twice in the combined
                // one ring unless it v1a and v1a==v1b
                vector<VertexID> lisect;
                if(link_intersection(*this, v0a, v0b, lisect))
                {
                    vector<VertexID>::iterator iter;
                    
                    if(v1a == v1b)
                    {
                        iter = find(lisect.begin(), lisect.end(), v1a);
                        if(iter != lisect.end())
                            lisect.erase(iter);
                    }
                    iter = find(lisect.begin(), lisect.end(), kernel.vert(kernel.next(h0)));
                    if(iter != lisect.end())
                        lisect.erase(iter);
                    if(lisect.size() > 0)
                        return false;
                }
            }
            
            if(v1a != v1b)
            {
                // Check the same for the other endpoints.
                vector<VertexID> lisect;
                if(link_intersection(*this, v1a, v1b, lisect))
                {
                    vector<VertexID>::iterator iter;
                    
                    if(v0a == v0b)
                    {
                        iter = find(lisect.begin(), lisect.end(), v1a);
                        if(iter != lisect.end())
                            lisect.erase(iter);
                    }
                    iter = find(lisect.begin(), lisect.end(), kernel.vert(kernel.next(h1)));
                    if(iter != lisect.end())
                        lisect.erase(iter);
                    if(lisect.size() > 0)
                        return false;
                }
            }
            
            
            if(v0b != v0a)
            {
                Walker hew = walker(v0b);
                for(;!hew.full_circle(); hew = hew.circulate_vertex_ccw())
                    kernel.set_vert(hew.opp().halfedge(), v0a);
            }
            
            if(v1b != v1a)
            {
                Walker hew = walker(v1b);
                for(;!hew.full_circle(); hew = hew.circulate_vertex_ccw())
                    kernel.set_vert(hew.opp().halfedge(), v1a);
            }
            
            if(v0a != v0b)
            {
                HalfEdgeID h1p = kernel.prev(h1);
                HalfEdgeID h0n = kernel.next(h0);
                
                if(kernel.next(h0n) == h1p)
                {
                    glue(kernel.opp(h0n), kernel.opp(h1p));
                    kernel.set_out(kernel.vert(h0n),kernel.opp(h0n));
                    kernel.remove_halfedge(h0n);
                    kernel.remove_halfedge(h1p);
                }
                else
                    link(h1p, h0n);
                kernel.remove_vertex(v0b);
            }
            
            if(v1a != v1b)
            {
                HalfEdgeID h0p = kernel.prev(h0);
                HalfEdgeID h1n = kernel.next(h1);
                if(kernel.next(h1n) == h0p)
                {
                    glue(kernel.opp(h0p), kernel.opp(h1n));
                    kernel.set_out(kernel.vert(h1n), kernel.opp(h1n));
                    kernel.remove_halfedge(h0p);
                    kernel.remove_halfedge(h1n);
                }
                else
                    link(h0p, h1n);
                kernel.remove_vertex(v1b);
            }
            glue(h0o, h1o);
            
            kernel.remove_halfedge(h0);
            kernel.remove_halfedge(h1);
            
            kernel.set_out(v1a, h1o);
            kernel.set_out(v0a, h0o);
            
            ensure_boundary_consistency(v1a);
            ensure_boundary_consistency(v0a);
            
            return true;
        }
        return false;
    }
    
    
    
    FaceID Manifold::merge_one_ring(VertexID v, float max_loop_length)
    {
        // If the vertex is either not in use or has just
        // one incident edge (or less), bail out.
        int val = valency(*this,v);
        if(!in_use(v) || val<2)
            return InvalidFaceID;
        
        // If the vertex is  a boundary vertex, we preparte the walker so that the
        // first face visited is not the invalid face outside the boundary. If the boundary
        // vertex is adjacent to only one vertex, there is little to do and we bail out.
        bool vertex_is_boundary = false;
        Walker hew = walker(v);
        if(boundary(*this, v))
        {
            if(val==2) return InvalidFaceID;
            vertex_is_boundary = true;
            hew = hew.circulate_vertex_ccw();
        }
        
        // Prepare some vectors for taking out the trash: We remove all old faces and all orphaned edges
        // and vertices
        vector<HalfEdgeID> garbage_halfedges;
        vector<FaceID> garbage_faces;
        vector<VertexID> garbage_vertices;
        
        vector<HalfEdgeID> loop; // The halfedges which form the outer loop of the merged one ring.
        
        // Below we loop over all faces adjacent to the vertex and add their halfedges to a big loop
        // which will form the loop of the new merged face. Below we remove from the loop edges
        // that appear twice (as each other's opposite).
        for(;!hew.full_circle(); hew = hew.circulate_vertex_ccw())
        {
            garbage_faces.push_back(hew.face());
            for(Walker hew2 = walker(hew.halfedge());
                !hew2.full_circle(); hew2 = hew2.circulate_face_ccw())
                loop.push_back(hew2.halfedge());
        }
        
        
        // Now merge the loops. We iteratively remove pairs of adjacent halfedges from the loop
        // if we find that the second is the opposite of the first since this is a degenerate
        // situation. However, we stop at four remaining halfedges since otherwise the loop degenerates
        // to zero after the next step if these four are also pairwise each other's opposites.
        int did_work;
        do
        {
            did_work = 0;
            vector<HalfEdgeID> loop_tmp(0);
            for(size_t i=0;i<loop.size();++i)
                if(walker(loop[i]).opp().halfedge() == loop[(i+1)%loop.size()])
                {
                    VertexID vid = walker(loop[i]).vertex();
                    if(vid != v)
                        garbage_vertices.push_back(walker(loop[i]).vertex());
                    garbage_halfedges.push_back(loop[i]);
                    garbage_halfedges.push_back(loop[(i+1)%loop.size()]);
                    loop[i] = InvalidHalfEdgeID;
                    loop[(i+1)%loop.size()] = InvalidHalfEdgeID;
                    ++did_work;
                    ++i;
                }
            for(size_t i=0;i<loop.size();++i)
                if(loop[i] != InvalidHalfEdgeID)
                    loop_tmp.push_back(loop[i]);
            loop = loop_tmp;
        } while(did_work > 0 && loop.size() > 4);
        
        // Check whether the loop is too long
        float loop_len=0.0;
        for(size_t i=0;i<loop.size();++i)
            loop_len += length(*this, loop[i]);
        if(loop_len > max_loop_length)
            return InvalidFaceID;
        
        // The following block checks wheteher the same halfedge appears twice. In this
        // case we fail since it means that the one ring contains the same face twice.
        vector<HalfEdgeID> loop_tmp = loop;
        sort(loop_tmp.begin(), loop_tmp.end());
        vector<HalfEdgeID>::iterator end_iter = unique(loop_tmp.begin(), loop_tmp.end());
        if(end_iter != loop_tmp.end())
            return InvalidFaceID;
        
        // Remove all faces and connected halfedges and the original vertex v.
        for(size_t i=0;i<garbage_vertices.size(); ++i)
            kernel.remove_vertex(garbage_vertices[i]);
        for(size_t i=0;i<garbage_faces.size(); ++i)
            kernel.remove_face(garbage_faces[i]);
        for(size_t i=0;i<garbage_halfedges.size(); ++i)
            kernel.remove_halfedge(garbage_halfedges[i]);
        if(!vertex_is_boundary)
            kernel.remove_vertex(v);
        
        // Create a new face for the merged one ring and link up all the halfedges
        // in the loop
        FaceID f = kernel.add_face();
        kernel.set_last(f,loop[0]);
        for(size_t i=0;i<loop.size(); ++i)
        {
            kernel.set_face(loop[i], f);
            Walker hw = walker(loop[i]);
            kernel.set_out(hw.vertex(),hw.opp().halfedge());
            link(loop[i],loop[(i+1)%loop.size()]);
            assert(hw.vertex() == walker(loop[(i+1)%loop.size()]).opp().vertex());
        }
        
        // Finally, we ensure boundary consitency for all vertices in the loop.
        for(size_t i=0;i<loop.size(); ++i)
        {
            Walker hw = walker(loop[i]);
            ensure_boundary_consistency(hw.vertex());
        }
        
        // Return the brand new merged face.
        return f;
    }
    
    
    
    bool Manifold::merge_faces(FaceID f, HalfEdgeID h)
    {
        //assert that we're merging a valid face with the corresponding halfedge
        assert(kernel.face(h) == f);
        
        HalfEdgeID ho = kernel.opp(h);
        FaceID fo = kernel.face(ho);
        HalfEdgeID hn = kernel.next(h);
        HalfEdgeID hon = kernel.next(ho);
        
        if(fo == f)
            return false;
        
        //boundary case
        if(kernel.vert(hn) == kernel.vert(hon))
            return false;
        
        HalfEdgeID hp = kernel.prev(h);
        HalfEdgeID hop = kernel.prev(ho);
        VertexID v = kernel.vert(h);
        VertexID vo = kernel.vert(ho);
        
        if(valency(*this, v) < 3 || valency(*this, vo) < 3)
            return false;
        
        link(hop, hn);
        link(hp, hon);
        kernel.set_out(vo, hon);
        kernel.set_out(v, hn);
        kernel.set_last(f, hn);
        
        HalfEdgeID hx = hon;
        
        assert(kernel.face(hx) == fo);
        while(kernel.face(hx) != f){
            kernel.set_face(hx, f);
            hx = kernel.next(hx);
        }
        
        ensure_boundary_consistency(v);
        ensure_boundary_consistency(vo);
        
        kernel.remove_halfedge(h);
        kernel.remove_halfedge(ho);
        kernel.remove_face(fo);
        
        return true;
    }
    
    FaceID Manifold::close_hole(HalfEdgeID h)
    {
        // invalid face is a hole
        if(kernel.face(h) == InvalidFaceID){
            FaceID f = kernel.add_face();
            kernel.set_last(f, h);
            do{
                kernel.set_face(h, f);
                h = kernel.next(h);
            }
            while(kernel.face(h) != f);
            return f;
        }
        return kernel.face(h);
    }
    void Manifold::flip_edge(HalfEdgeID h)
    {
        HalfEdgeID hn = kernel.next(h);
        HalfEdgeID hp = kernel.prev(h);
        HalfEdgeID ho = kernel.opp(h);
        HalfEdgeID hon = kernel.next(ho);
        HalfEdgeID hop = kernel.prev(ho);
        
        FaceID hf = kernel.face(h);
        FaceID hof = kernel.face(ho);
        
        VertexID hv = kernel.vert(h);
        VertexID hnv = kernel.vert(hn);
        VertexID hov = kernel.vert(ho);
        VertexID honv = kernel.vert(hon);
        
        // update face connectivity of halfedges changing face
        kernel.set_face(hop, hf);
        kernel.set_face(hp, hof);
        
        // connectivity of faces with halfedges of flipped edge
        kernel.set_last(hf, h);
        kernel.set_last(hof, ho);
        
        // connectivity of halfedges of first face after flip
        link(hn, h);
        link(h, hop);
        link(hop, hn);
        
        // connectivity of halfedges of second face after flip
        link(hon, ho);
        link(ho, hp);
        link(hp, hon);
        
        // connectivity of flipped edge and corresponding vertices
        kernel.set_vert(h, honv);
        kernel.set_vert(ho, hnv);
        
        if(kernel.out(hv) == ho)
            kernel.set_out(hv, hn);
        if(kernel.out(hov) == h)
            kernel.set_out(hov, hon);
        
        //
        //        // if the flip occurs next to a boundary, ensure the boundary consistency
        //        ensure_boundary_consistency(hv);
        //        ensure_boundary_consistency(hov);
    }
    
    
    /**********************************************
     * Private functions
     **********************************************/
    
    template<typename size_type, typename float_type, typename int_type>
    void Manifold::build_template(  size_type no_vertices,
                                  const float_type* vertvec,
                                  size_type no_faces,
                                  const int_type* facevec,
                                  const int_type* indices)
    {
        vector<VertexID> vids(no_vertices);
        
        // create vertices corresponding to positions stored in vertvec
        for(size_t i=0;i<no_vertices;++i)
        {
            const float_type* v0 = &vertvec[i*3];
            pos(vids[i] = kernel.add_vertex()) = Manifold::Vec(v0[0], v0[1], v0[2]);
        }
        
        //map over the created edges - needed to preserve edge uniqueness
        typedef map<EdgeKey, Edge> EdgeMap;
        EdgeMap edge_map;
        
        // counter that jumps between faces in indices vector
        int_type n  = 0;
        
        // create faces correspponding to faces stored in facevec
        for(size_type i = 0; i < no_faces; ++i){
            //amount of vertices in current face
            size_type N = facevec[i];
            vector<HalfEdgeID> fh;
            
            //each face indice results corresponds to 1 edge, 2 halfedges
            for(size_type j = 0; j < N; ++j){
                // ensure indice integrity
                
                assert(static_cast<size_type>(indices[j + n]) < no_vertices);
                assert(static_cast<size_type>(indices[(j + 1) % N + n]) < no_vertices);
                
                
                // each iteration uses two indices from the face
                VertexID v0 = vids[static_cast<size_type>(indices[j + n])];
                VertexID v1 = vids[static_cast<size_type>(indices[(j + 1) % N + n])];
                
                // create key and search map for edge
                EdgeKey ek(v0, v1);
                EdgeMap::iterator em_iter = edge_map.find(ek);
                
                // current edge has not been created
                if(em_iter == edge_map.end()){
                    // create edge for map
                    Edge e;
                    e.h0 = kernel.add_halfedge();
                    e.h1 = kernel.add_halfedge();
                    e.count = 1;
                    
                    // glue operation: 1 edge = 2 glued halfedges
                    glue(e.h0, e.h1);
                    
                    // update vertices with their outgoing halfedges
                    kernel.set_out(v0, e.h0);
                    kernel.set_out(v1, e.h1);
                    
                    // update halfedges with the vertices they point to
                    kernel.set_vert(e.h0, v1);
                    kernel.set_vert(e.h1, v0);
                    
                    // update map
                    edge_map[ek] = e;
                    
                    // update vector of halfedges belonging to current face
                    fh.push_back(e.h0);
                }
                else{
                    // update current face with halfedge from edge
                    fh.push_back(em_iter->second.h1);
                    
                    // asserting that a halfedge is visited exactly twice;
                    // once for each face on either side of the edge.
                    em_iter->second.count++;
                    assert(em_iter->second.count == 2);
                }
            }
            
            FaceID fid = kernel.add_face();
            for(size_type j = 0; j < N; ++j){
                // update halfedge with face
                kernel.set_face(fh[j], fid);
                
                // link operation: link two halfedges in the same face
                link(fh[j], fh[(j + 1) % N]);
            }
            //update face with the first halfedge created
            kernel.set_last(fid, fh[0]);
            
            // step to first index of next face
            n += N;
        }
        
        // test for unused vertices
        for(VertexIDIterator v = vertices_begin(); v != vertices_end(); ++v){
            assert( (*v) != InvalidVertexID);
            if(kernel.out(*v) == InvalidHalfEdgeID)
                kernel.remove_vertex(*v);
        }
        
        // boundary check while avoiding unused vertices
        for(VertexIDIterator v = vertices_begin(); v != vertices_end(); ++v){
            if((*v) != InvalidVertexID)
                ensure_boundary_consistency(*v);
        }
    }
    void Manifold::link(HalfEdgeID h0, HalfEdgeID h1)
    {
        kernel.set_next(h0, h1);
        kernel.set_prev(h1, h0);
    }
    void Manifold::glue(HalfEdgeID h0, HalfEdgeID h1)
    {
        kernel.set_opp(h0, h1);
        kernel.set_opp(h1, h0);
    }
    void Manifold::ensure_boundary_consistency(VertexID v)
    {
        // boundary consistency check by performing two vertex circulations
        HalfEdgeID h = kernel.out(v);
        HalfEdgeID last = h;
        
        // step 1: circle through edges pointing away from vertex until reaching a null face
        while(kernel.face(h) != InvalidFaceID){
            h = kernel.opp(kernel.prev(h));
            if(h == last) // We came full circle - vertex not boundary - return.
                return;
        }
        // null face encountered, we update our vertex with half edge index and prepare for step 2
        kernel.set_out(v, h);
        HalfEdgeID ho = kernel.opp(h);
        
        // step 2: circle through edges pointing towards vertex until reaching a null face
        while(kernel.face(ho) != InvalidFaceID){
            ho = kernel.opp(kernel.next(ho));
        }
        // null face encountered again, we update our edge with vertex index
        kernel.set_vert(ho, v);
        
        // remaining step is to make the in and out going edges link to each other
        link(ho, h);
    }
    void Manifold::remove_face_if_degenerate(HalfEdgeID h)
    {
        // face is degenerate if there is only two halfedges in face loop
        if(kernel.next(kernel.next(h)) == h)
        {
            HalfEdgeID hn = kernel.next(h);
            HalfEdgeID ho = kernel.opp(h);
            HalfEdgeID hno = kernel.opp(hn);
            VertexID hv = kernel.vert(h);
            VertexID hnv = kernel.vert(hn);
            FaceID f = kernel.face(h);
            
            assert(ho != hn);
            assert(h != hno);
            assert(hv != hnv);
            
            // glue opposite halfedge to halfedge opposite next halfedge, obsoleting h and hn from loop
            glue(ho, hno);
            
            // make v and vn point to opposite and next opposite halfedge, obsoleting h and hn from loop
            kernel.set_out(hnv, hno);
            kernel.set_out(hv, ho);
            
            // if face owning h is valid, remove face
            if(f != InvalidFaceID)
                kernel.remove_face(f);
            // remove the two invalid halfedges and the invalid face loop
            kernel.remove_halfedge(h);
            kernel.remove_halfedge(hn);
            
            // verify that v and vn is sane after removing the degenerate face
            ensure_boundary_consistency(hv);
            ensure_boundary_consistency(hnv);
        }
    }
    
    vector<HalfEdgeID> Manifold::bridge_faces(FaceID f0, FaceID f1, const vector<pair<VertexID, VertexID> >& pairs)
    {
        // Let N be the number of vertex pairs to connect by edges
        size_t N = pairs.size();
        
        // We now create N pairs of edges, glue each pair and let them point to the appropriate
        // vertices.
        vector<HalfEdgeID> new_halfedges(N);
        vector<HalfEdgeID> new_halfedges_opp(N);
        for(size_t i=0;i<N; ++i)
        {
            new_halfedges[i] = kernel.add_halfedge();
            new_halfedges_opp[i] = kernel.add_halfedge();
            glue(new_halfedges[i], new_halfedges_opp[i]);
            kernel.set_vert(new_halfedges[i], pairs[i].second);
            kernel.set_vert(new_halfedges_opp[i], pairs[i].first);
        }
        
        // We now maintain some halfedge indices to right before
        // and right after the point we are trying to connect on
        // each of the two loops.
        HalfEdgeID h0p = kernel.last(f0);
        HalfEdgeID h1n = kernel.last(f1);
        
        // loop over all connections and link the new halfedges with the old
        // ones.
        for(size_t i=0;i<N; ++i)
        {
            while(kernel.vert(h0p) != pairs[i].first)
                h0p = kernel.next(h0p);
            while(kernel.vert(kernel.prev(h1n)) != pairs[i].second)
                h1n = kernel.prev(h1n);
            
            HalfEdgeID h0n = kernel.next(h0p);
            HalfEdgeID h1p = kernel.prev(h1n);
            
            link(h0p, new_halfedges[i]);
            link(new_halfedges[i],h1n);
            link(h1p, new_halfedges_opp[i]);
            link(new_halfedges_opp[i],h0n);
            
            h0p = new_halfedges_opp[i];
            h1n = new_halfedges_opp[i];
        }
        
        // Create the faces and their connections
        for(size_t i=0;i<N; ++i)
        {
            HalfEdgeID last = new_halfedges[i];
            FaceID f = kernel.add_face();
            kernel.set_last(f, last);
            HalfEdgeID h = last;
            do
            {
                kernel.set_face(h, f);
                h = kernel.next(h);
            } while(h != last);
        }
        
        // Delete the old faces that were bridged.
        kernel.remove_face(f0);
        kernel.remove_face(f1);
        
        new_halfedges.insert(new_halfedges.end(), new_halfedges_opp.begin(), new_halfedges_opp.end());
        return new_halfedges;
    }
    
    /***************************************************
     * Namespace functions
     ***************************************************/
    bool valid(const Manifold& m)
    {
        // Verify components of halfedges
        for(HalfEdgeIDIterator h = m.halfedges_begin(); h != m.halfedges_end(); ++h){
            Walker j = m.walker(*h);
            
            if(j.vertex() == InvalidVertexID){
                cout << "Halfedge lacks vert" << endl;
                return false;
            }
            if(j.next().halfedge() == InvalidHalfEdgeID){
                cout << "Halfedge lacks next" << endl;
                return false;
            }
            if(j.prev().halfedge() == InvalidHalfEdgeID){
                cout << "Halfedge lacks prev" << endl;
                return false;
            }
            if(j.opp().halfedge() == InvalidHalfEdgeID){
                cout << "Halfedge lacks opp" << endl;
                return false;
            }
            
        }
        // Verify components of vertices
        for(VertexIDIterator v = m.vertices_begin(); v != m.vertices_end(); ++v){
            vector<VertexID> link;
            
            // circulate the halfedges of vertex
            for(Walker j = m.walker(*v); !j.full_circle(); j = j.circulate_vertex_cw()){
                // test halfedges around v
                if(j.halfedge() == InvalidHalfEdgeID){
                    cout << "Vertex circulation produced invalid halfedge" << endl;
                    return false;
                }
                VertexID ring_v = j.vertex();
                
                // test one-ring for multiple occurences of vertex
                if(find(link.begin(), link.end(), ring_v) != link.end()){
                    cout << "Vertex appears two times in one-ring of vertex" << endl;
                    return false;
                }
                link.push_back(ring_v);
                
                // test for infinite loop around vertex
                if(static_cast<size_t>(j.no_steps()) > m.no_vertices()){
                    cout << "Vertex loop contains more vertices than manifold" << endl;
                    return false;
                }
            }
            
            // test one_ring size for boundary consistency
            if(link.size() <= 2){
                Walker j = m.walker(*v);
                
                if(j.face() != InvalidFaceID && j.opp().face() != InvalidFaceID)
                {
                    if(link.size()==1)
                        cout << "Vertex contains only a single incident edge" << endl;
                    //
                    //                    cout << "Vertex contains only " << link.size() <<" incident edges" << endl;
                }
                else
                    cout << "Boundary vertex contains only " << link.size() <<" incident edges" << endl;
            }
        }
        // verify components of faces
        for(FaceIDIterator f = m.faces_begin(); f != m.faces_end(); ++f){
            // count edges on face
            Walker j = m.walker(*f);
            
            for(; !j.full_circle(); j = j.circulate_face_cw()){
                // test that all halfedges in faces bind properly to their face
                if(j.face() != *f){
                    cout << "Face is inconsistent, halfedge is not bound to face" << endl;
                    return false;
                }
            }
            // test faces for valid geometrical properties
            if(j.no_steps() < 3){
                cout << "Face contains less than 3 edges" << endl;
                return false;
            }
            // test for infinite loop around face
            if(j.no_steps() > m.no_halfedges() * 0.5f){
                cout << "Face loop contains more halfedges than manifold" << endl;
                return false;
            }
        }
        return true;
    }
    
    void bbox(const Manifold& m, Manifold::Vec& pmin, Manifold::Vec& pmax)
    {
        
        VertexIDIterator v = m.vertices_begin();
        pmin = pmax = m.pos(*v);
        ++v;
        for(; v != m.vertices_end(); ++v){
            pmin = v_min(m.pos(*v), pmin);
            pmax = v_max(m.pos(*v), pmax);
        }
    }
    
    void bsphere(const Manifold& m, Manifold::Vec& c, float& r)
    {
        Manifold::Vec p0, p7;
        bbox(m, p0, p7);
        Manifold::Vec rad = (p7 - p0) * 0.5f;
        c = p0 + rad;
        r = rad.length();
    }
    
    
    
    bool precond_collapse_edge(const Manifold& m, HalfEdgeID h)
    {
        Walker hew = m.walker(h);
        HalfEdgeID ho = hew.opp().halfedge();
        VertexID v0 = hew.opp().vertex();
        VertexID v1 = hew.vertex();
        
        // get the one-ring of v0
        vector<VertexID> link0;
        vector<FaceID> faces0;
        for(Walker vj = m.walker(h);
            !vj.full_circle(); vj = vj.circulate_vertex_ccw()){
            link0.push_back(vj.vertex());
            if(vj.halfedge() != h)
                faces0.push_back(vj.face());
        }
        assert(link0.size() > 1);
        
        // get the one-ring of v1
        vector<VertexID> link1;
        vector<FaceID> faces1;
        for(Walker vj = m.walker(ho);
            !vj.full_circle(); vj = vj.circulate_vertex_ccw()){
            link1.push_back(vj.vertex());
            if(vj.halfedge() != ho)
                faces1.push_back(vj.face());
        }
        assert(link1.size() > 1);
        
        // sort the vertices of the two rings
        sort(link0.begin(), link0.end());
        sort(link1.begin(), link1.end());
        
        // get the intersection of the shared vertices from both rings
        vector<VertexID> lisect;
        std::back_insert_iterator<vector<VertexID> > lii(lisect);
        set_intersection(link0.begin(), link0.end(),
                         link1.begin(), link1.end(),
                         lii);
        
        // sort the faces of the two rings
        sort(faces0.begin(), faces0.end());
        sort(faces1.begin(), faces1.end());
        
        // get the intersection of the shared faces from both rings
        vector<FaceID> fisect;
        std::back_insert_iterator<vector<FaceID> > fii(fisect);
        set_intersection(faces0.begin(), faces0.end(),
                         faces1.begin(), faces1.end(),
                         fii);
        if(fisect.size() > 0)
            return false;
        
        int k = 0;
        // if the adjacent face is a triangle (see 2)
        if(hew.next().next().next().halfedge() == h){
            VertexID v = hew.next().vertex();
            
            // valency test (see 5)
            if(valency(m, v) < 3)
                return false;
            
            // remove the vertex shared by the two rings from the intersection
            vector<VertexID>::iterator iter;
            iter = find(lisect.begin(), lisect.end(), v);
            assert(iter != lisect.end());
            lisect.erase(iter);
            ++k;
        }
        // if the adjacent face is a triangle (see 2)
        if(hew.opp().next().next().next().halfedge() == hew.opp().halfedge()){
            VertexID v = hew.opp().next().vertex();
            
            // valency test (see 5)
            if(valency(m, v) < 3)
                return false;
            
            // remove the vertex shared by the two rings from the intersection
            vector<VertexID>::iterator iter;
            iter = find(lisect.begin(), lisect.end(), v);
            assert(iter != lisect.end());
            lisect.erase(iter);
            ++k;
        }
        // double edge test (see 3)
        if(lisect.size() != 0)
            return false;
        
        // tetrahedon test (see 4)
        if(k == 2 && (link0.size() + link1.size() == 6))
            return false;
        
        // test that we do not merge holes (see 6)
        if(boundary(m, v0) && boundary(m, v1) && hew.face() != InvalidFaceID && hew.opp().face() != InvalidFaceID)
            return false;
        
        return true;
    }
    
    bool precond_flip_edge(const Manifold& m, HalfEdgeID h)
    {
        Walker j = m.walker(h);
        
        FaceID hf = j.face();
        //        HalfEdgeID ho = j.opp().halfedge();
        FaceID hof = j.opp().face();
        
        // boundary case
        if(hf == InvalidFaceID || hof == InvalidFaceID)
            return false;
        
        // We can only flip an edge if both incident polygons are triangles.
        if(no_edges(m, hf) != 3 || no_edges(m, hof) !=3)
            return false;
        
        // non boundary vertices with a valency of less than 4(less than 3 after operation) degenerates mesh.
        VertexID hv = j.vertex();
        VertexID hov = j.opp().vertex();
        if((valency(m, hv) < 4 && !boundary(m, hv)) || (valency(m, hov) < 4 && !boundary(m, hov)))
            return false;
        
        // Disallow flip if vertices being connected already are.
        VertexID hnv = j.next().vertex();
        VertexID honv = j.opp().next().vertex();
        if(connected(m, hnv, honv))
            return false;
        
        return true;
    }
    
    bool boundary(const Manifold& m, VertexID v)
    {
        Walker j  = m.walker(v);
        return boundary(m, j.halfedge());
    }
    int valency(const Manifold& m, VertexID v)
    {
        // perform full circulation to get valency
        Walker vj = m.walker(v);
        while(!vj.full_circle())
            vj = vj.circulate_vertex_cw();
        return vj.no_steps();
    }
    
    Manifold::Vec normal(const Manifold& m, VertexID v)
    {
        Manifold::Vec p0 = m.pos(v);
        vector<Manifold::Vec> one_ring;
        
        // run through outgoing edges, and store them normalized
        for(Walker vj = m.walker(v); !vj.full_circle(); vj = vj.circulate_vertex_ccw()){
            Manifold::Vec edge = m.pos(vj.vertex())-p0;
            float l = length(edge);
            if(l > 0.0f) one_ring.push_back(edge/l);
        }
        
        Manifold::Vec n(0);
        size_t N = one_ring.size();
        if(N<2)
            return Manifold::Vec(0);
        
        size_t N_count = N;
        if(boundary(m, v))
            N_count -= 1;
        
        // sum up the normals of each face surrounding the vertex
        for(size_t i = 0; i < N_count; ++i){
            Manifold::Vec e0 = one_ring[i];
            Manifold::Vec e1 = one_ring[(i+1) % N];
            
            Manifold::Vec n_part = normalize(cross(e0, e1));
            n += n_part * acos(max(-1.0, min(1.0, dot(e0, e1))));
        }
        
        // normalize and return the normal
        float sqr_l = sqr_length(n);
        if(sqr_l > 0.0f) return n / sqrt(sqr_l);
        
        return n;
    }
    
    bool connected(const Manifold& m, VertexID v0, VertexID v1)
    {
        for(Walker vj = m.walker(v0); !vj.full_circle(); vj = vj.circulate_vertex_cw()){
            if(vj.vertex() == v1)
                return true;
        }
        return false;
    }
    
    int no_edges(const Manifold& m, FaceID f)
    {
        // perform full circulation to get valency
        Walker w = m.walker(f);
        for(; !w.full_circle(); w = w.circulate_face_cw());
        return w.no_steps();
    }
    Manifold::Vec normal(const Manifold& m, FaceID f)
    {
        vector<Manifold::Vec> v;
        
        int k=0;
        for(Walker  w = m.walker(f); !w.full_circle(); w = w.circulate_face_ccw(),++k)
            v.push_back(m.pos(w.vertex()));
        
        Manifold::Vec norm(0);
        for(int i=0;i<k;++i)
        {
            norm[0] += (v[i][1]-v[(i+1)%k][1])*(v[i][2]+v[(i+1)%k][2]);
            norm[1] += (v[i][2]-v[(i+1)%k][2])*(v[i][0]+v[(i+1)%k][0]);
            norm[2] += (v[i][0]-v[(i+1)%k][0])*(v[i][1]+v[(i+1)%k][1]);
        }
        float l = sqr_length(norm);
        if(l>0.0f)
            norm /= sqrt(l);
        return norm;
    }
    
    
    float area(const Manifold& m, FaceID f)
    {
        // Get all projected vertices
        vector<Manifold::Vec> vertices;
        Walker w = m.walker(f);
        for(; !w.full_circle(); w = w.circulate_face_ccw())
            vertices.push_back(m.pos(w.vertex()));
        float area = 0;
        int k = w.no_steps();
        Manifold::Vec n = normal(m,f);
        for(int i = 0; i < k; ++i)
        {
            Manifold::Vec A = cross(vertices[i], vertices[(i+1 )%k]);
            float s = sign(dot(n, A));
            area += 0.5 * s * length(A);
        }
        return abs(area);
    }
    
    Manifold::Vec centre(const Manifold& m, FaceID f)
    {
        Manifold::Vec c(0);
        Walker w = m.walker(f);
        
        for(; !w.full_circle(); w = w.circulate_face_ccw()) c += m.pos(w.vertex());
        
        c /= w.no_steps();
        return c;
    }
    
    float perimeter(const Manifold& m, FaceID f)
    {
        float p=0.0;
        Walker w = m.walker(f);
        
        for(; !w.full_circle(); w = w.circulate_face_cw()) p += length(m, w.halfedge());
        return p;
    }
    
    bool boundary(const Manifold& m, HalfEdgeID h)
    {
        Walker w = m.walker(h);
        return w.face() == InvalidFaceID || w.opp().face() == InvalidFaceID;
    }
    
    float length(const Manifold& m, HalfEdgeID h)
    {
        Walker w = m.walker(h);
        return (m.pos(w.vertex()) - m.pos(w.opp().vertex())).length();
    }
}
 

Rev 601	Rev 605
1	`/* ----------------------------------------------------------------------- *`	1	`/* ----------------------------------------------------------------------- *`
2	`* This file is part of GEL, http://www.imm.dtu.dk/GEL`	2	`* This file is part of GEL, http://www.imm.dtu.dk/GEL`
3	`* Copyright (C) the authors and DTU Informatics`	3	`* Copyright (C) the authors and DTU Informatics`
4	`* For license and list of authors, see ../../doc/intro.pdf`	4	`* For license and list of authors, see ../../doc/intro.pdf`
5	`* ----------------------------------------------------------------------- */`	5	`* ----------------------------------------------------------------------- */`
6	`#include <iterator>`	6	`#include <iterator>`
7	`#include "Manifold.h"`	7	`#include "Manifold.h"`
8		8
9	`#include <iostream>`	9	`#include <iostream>`
10	`#include <vector>`	10	`#include <vector>`
11	`#include <map>`	11	`#include <map>`
12	`#include <iterator>`	12	`#include <iterator>`
13		13
14	`#include "../Geometry/TriMesh.h"`	14	`#include "../Geometry/TriMesh.h"`
15		15
16	`namespace HMesh`	16	`namespace HMesh`
17	`{`	17	`{`
18		18
19	`using namespace std;`	19	`using namespace std;`
20	`using namespace Geometry;`	20	`using namespace Geometry;`
21	`using namespace CGLA;`	21	`using namespace CGLA;`
22		22
23	`namespace`	23	`namespace`
24	`{`	24	`{`
25	`/************************************************************`	25	`/************************************************************`
26	`* Edgekeys and Edges for halfedge identification during build`	26	`* Edgekeys and Edges for halfedge identification during build`
27	`************************************************************/`	27	`************************************************************/`
28	`class EdgeKey`	28	`class EdgeKey`
29	`{`	29	`{`
30	`public:`	30	`public:`
31	`EdgeKey(VertexID va, VertexID vb)`	31	`EdgeKey(VertexID va, VertexID vb)`
32	`{`	32	`{`
33	`if(va < vb){`	33	`if(va < vb){`
34	`v0 = va;`	34	`v0 = va;`
35	`v1 = vb;`	35	`v1 = vb;`
36	`}`	36	`}`
37	`else{`	37	`else{`
38	`v0 = vb;`	38	`v0 = vb;`
39	`v1 = va;`	39	`v1 = va;`
40	`}`	40	`}`
41	`}`	41	`}`
42		42
43	`bool operator<(const EdgeKey& k2) const`	43	`bool operator<(const EdgeKey& k2) const`
44	`{`	44	`{`
45	`if(v0 < k2.v0){`	45	`if(v0 < k2.v0){`
46	`return true;`	46	`return true;`
47	`}`	47	`}`
48	`else if( k2.v0 < v0){`	48	`else if( k2.v0 < v0){`
49	`return false;`	49	`return false;`
50	`}`	50	`}`
51	`else{`	51	`else{`
52	`return v1 < k2.v1;`	52	`return v1 < k2.v1;`
53	`}`	53	`}`
54	`}`	54	`}`
55	`private:`	55	`private:`
56	`VertexID v0;`	56	`VertexID v0;`
57	`VertexID v1;`	57	`VertexID v1;`
58	`};`	58	`};`
59		59
60	`struct Edge`	60	`struct Edge`
61	`{`	61	`{`
62	`HalfEdgeID h0;`	62	`HalfEdgeID h0;`
63	`HalfEdgeID h1;`	63	`HalfEdgeID h1;`
64	`int count;`	64	`int count;`
65	`Edge() : count(0){}`	65	`Edge() : count(0){}`
66	`};`	66	`};`
67	`}`	67	`}`
68		68
69	`/*********************************************`	69	`/*********************************************`
70	`* Public functions`	70	`* Public functions`
71	`*********************************************/`	71	`*********************************************/`
72	`void Manifold::build(const TriMesh& mesh)`	72	`void Manifold::build(const TriMesh& mesh)`
73	`{`	73	`{`
74	`// A vector of 3's - used to tell build how many indices each face consists of`	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);`	75	`vector<int> faces(mesh.geometry.no_faces(), 3);`
76		76
77	`build_template( static_cast<size_t>(mesh.geometry.no_vertices()),`	77	`build_template( static_cast<size_t>(mesh.geometry.no_vertices()),`
78	`reinterpret_cast<const float*>(&mesh.geometry.vertex(0)),`	78	`reinterpret_cast<const float*>(&mesh.geometry.vertex(0)),`
79	`static_cast<size_t>(faces.size()),`	79	`static_cast<size_t>(faces.size()),`
80	`static_cast<const int*>(&faces[0]),`	80	`static_cast<const int*>(&faces[0]),`
81	`reinterpret_cast<const int*>(&mesh.geometry.face(0)));`	81	`reinterpret_cast<const int*>(&mesh.geometry.face(0)));`
82	`}`	82	`}`
83		83
84	`void Manifold::build( size_t no_vertices,`	84	`void Manifold::build( size_t no_vertices,`
85	`const float* vertvec,`	85	`const float* vertvec,`
86	`size_t no_faces,`	86	`size_t no_faces,`
87	`const int* facevec,`	87	`const int* facevec,`
88	`const int* indices)`	88	`const int* indices)`
89	`{`	89	`{`
90	`build_template(no_vertices, vertvec, no_faces, facevec, indices);`	90	`build_template(no_vertices, vertvec, no_faces, facevec, indices);`
91	`}`	91	`}`
92		92
93	`void Manifold::build( size_t no_vertices,`	93	`void Manifold::build( size_t no_vertices,`
94	`const double* vertvec,`	94	`const double* vertvec,`
95	`size_t no_faces,`	95	`size_t no_faces,`
96	`const int* facevec,`	96	`const int* facevec,`
97	`const int* indices)`	97	`const int* indices)`
98	`{`	98	`{`
99	`build_template(no_vertices, vertvec, no_faces, facevec, indices);`	99	`build_template(no_vertices, vertvec, no_faces, facevec, indices);`
100	`}`	100	`}`
101		101
102	`FaceID Manifold::add_face(std::vector<Manifold::Vec> points)`	102	`FaceID Manifold::add_face(std::vector<Manifold::Vec> points)`
103	`{`	103	`{`
104	`int F = points.size();`	104	`int F = points.size();`
105	`vector<int> indices;`	105	`vector<int> indices;`
106	`for(int i=0;i<points.size(); ++i)`	106	`for(size_t i=0;i<points.size(); ++i)`
107	`indices.push_back(i);`	107	`indices.push_back(i);`
108	`FaceID fid = *faces_end();`	108	`FaceID fid = *faces_end();`
109	`build(points.size(), reinterpret_cast<double*>(&points[0]), 1, &F, &indices[0]);`	109	`build(points.size(), reinterpret_cast<double*>(&points[0]), 1, &F, &indices[0]);`
110	`return fid;`	110	`return fid;`
111	`}`	111	`}`
112		112
113	`bool Manifold::remove_face(FaceID fid)`	113	`bool Manifold::remove_face(FaceID fid)`
114	`{`	114	`{`
115	`if(!in_use(fid))`	115	`if(!in_use(fid))`
116	`return false;`	116	`return false;`
117		117
118	`HalfEdgeID he = kernel.last(fid);`	118	`HalfEdgeID he = kernel.last(fid);`
119	`HalfEdgeID last = he;`	119	`HalfEdgeID last = he;`
120		120
121	`vector<HalfEdgeID> halfedges;`	121	`vector<HalfEdgeID> halfedges;`
122	`do`	122	`do`
123	`{`	123	`{`
124	`halfedges.push_back(he);`	124	`halfedges.push_back(he);`
125	`kernel.set_face(he, InvalidFaceID);`	125	`kernel.set_face(he, InvalidFaceID);`
126	`he = kernel.next(he);`	126	`he = kernel.next(he);`
127	`}`	127	`}`
128	`while(he != last);`	128	`while(he != last);`
129		129
130	`vector<HalfEdgeID> halfedges_garbage;`	130	`vector<HalfEdgeID> halfedges_garbage;`
131	`vector<VertexID> vertices_garbage;`	131	`vector<VertexID> vertices_garbage;`
132	`for(int i=0;i<halfedges.size(); ++i)`	132	`for(size_t i=0;i<halfedges.size(); ++i)`
133	`{`	133	`{`
134	`HalfEdgeID h = halfedges[i];`	134	`HalfEdgeID h = halfedges[i];`
135	`HalfEdgeID hopp = kernel.opp(h);`	135	`HalfEdgeID hopp = kernel.opp(h);`
136	`if(kernel.face(hopp) == InvalidFaceID)`	136	`if(kernel.face(hopp) == InvalidFaceID)`
137	`{`	137	`{`
138	`halfedges_garbage.push_back(h);`	138	`halfedges_garbage.push_back(h);`
139	`VertexID v0 = kernel.vert(hopp);`	139	`VertexID v0 = kernel.vert(hopp);`
140	`if(valency(*this, v0) <= 2 )`	140	`if(valency(*this, v0) <= 2 )`
141	`vertices_garbage.push_back(v0);`	141	`vertices_garbage.push_back(v0);`
142	`else {`	142	`else {`
143	`link(kernel.prev(h), kernel.next(hopp));`	143	`link(kernel.prev(h), kernel.next(hopp));`
144	`kernel.set_out(v0, kernel.opp(kernel.prev(h)));`	144	`kernel.set_out(v0, kernel.opp(kernel.prev(h)));`
145	`}`	145	`}`
146	`VertexID v1 = kernel.vert(h);`	146	`VertexID v1 = kernel.vert(h);`
147	`if(valency(*this, v1)>2)`	147	`if(valency(*this, v1)>2)`
148	`{`	148	`{`
149	`link(kernel.prev(hopp),kernel.next(h));`	149	`link(kernel.prev(hopp),kernel.next(h));`
150	`kernel.set_out(v1, kernel.opp(kernel.prev(hopp)));`	150	`kernel.set_out(v1, kernel.opp(kernel.prev(hopp)));`
151	`}`	151	`}`
152		152
153	`}`	153	`}`
154	`}`	154	`}`
155	`for(int i=0;i<halfedges_garbage.size();++i){`	155	`for(size_t i=0;i<halfedges_garbage.size();++i){`
156	`kernel.remove_halfedge(kernel.opp(halfedges_garbage[i]));`	156	`kernel.remove_halfedge(kernel.opp(halfedges_garbage[i]));`
157	`kernel.remove_halfedge(halfedges_garbage[i]);`	157	`kernel.remove_halfedge(halfedges_garbage[i]);`
158	`}`	158	`}`
159	`for(int i=0;i<vertices_garbage.size(); ++i)`	159	`for(size_t i=0;i<vertices_garbage.size(); ++i)`
160	`kernel.remove_vertex(vertices_garbage[i]);`	160	`kernel.remove_vertex(vertices_garbage[i]);`
161		161
162	`kernel.remove_face(fid);`	162	`kernel.remove_face(fid);`
163	`return true;`	163	`return true;`
164	`}`	164	`}`
165		165
166		166
167	`bool Manifold::remove_edge(HalfEdgeID hid)`	167	`bool Manifold::remove_edge(HalfEdgeID hid)`
168	`{`	168	`{`
169	`if(!in_use(hid))`	169	`if(!in_use(hid))`
170	`return false;`	170	`return false;`
171		171
172	`FaceID f0 = kernel.face(hid);`	172	`FaceID f0 = kernel.face(hid);`
173	`FaceID f1 = kernel.face(kernel.opp(hid));`	173	`FaceID f1 = kernel.face(kernel.opp(hid));`
174		174
175	`remove_face(f0);`	175	`remove_face(f0);`
176	`remove_face(f1);`	176	`remove_face(f1);`
177		177
178	`return true;`	178	`return true;`
179	`}`	179	`}`
180		180
181		181
182		182
183	`bool Manifold::remove_vertex(VertexID vid)`	183	`bool Manifold::remove_vertex(VertexID vid)`
184	`{`	184	`{`
185	`if(!in_use(vid))`	185	`if(!in_use(vid))`
186	`return false;`	186	`return false;`
187		187
188	`Walker w = Manifold::walker(vid);`	188	`Walker w = Manifold::walker(vid);`
189		189
190	`vector<FaceID> faces;`	190	`vector<FaceID> faces;`
191		191
192	`for(; !w.full_circle(); w = w.circulate_vertex_ccw())`	192	`for(; !w.full_circle(); w = w.circulate_vertex_ccw())`
193	`faces.push_back(w.face());`	193	`faces.push_back(w.face());`
194		194
195	`for(int i=0;i<faces.size();++i)`	195	`for(size_t i=0;i<faces.size();++i)`
196	`remove_face(faces[i]);`	196	`remove_face(faces[i]);`
197		197
198	`return true;`	198	`return true;`
199	`}`	199	`}`
200		200
201		201
202		202
203	`void Manifold::collapse_edge(HalfEdgeID h, bool avg_vertices)`	203	`void Manifold::collapse_edge(HalfEdgeID h, bool avg_vertices)`
204	`{`	204	`{`
205	`HalfEdgeID ho = kernel.opp(h);`	205	`HalfEdgeID ho = kernel.opp(h);`
206	`VertexID hv = kernel.vert(h);`	206	`VertexID hv = kernel.vert(h);`
207	`VertexID hov = kernel.vert(ho);`	207	`VertexID hov = kernel.vert(ho);`
208	`HalfEdgeID hn = kernel.next(h);`	208	`HalfEdgeID hn = kernel.next(h);`
209	`HalfEdgeID hp = kernel.prev(h);`	209	`HalfEdgeID hp = kernel.prev(h);`
210	`HalfEdgeID hon = kernel.next(ho);`	210	`HalfEdgeID hon = kernel.next(ho);`
211	`HalfEdgeID hop = kernel.prev(ho);`	211	`HalfEdgeID hop = kernel.prev(ho);`
212	`FaceID f = kernel.face(h);`	212	`FaceID f = kernel.face(h);`
213	`FaceID fo = kernel.face(ho);`	213	`FaceID fo = kernel.face(ho);`
214		214
215	`// average the vertex positions`	215	`// average the vertex positions`
216	`pos(hv) = avg_vertices ? (0.5f * (pos(hov) + pos(hv))) : pos(hv);`	216	`pos(hv) = avg_vertices ? (0.5f * (pos(hov) + pos(hv))) : pos(hv);`
217		217
218	`// update all halfedges pointing to hov to point to hv, effectively removing hov from all loops`	218	`// update all halfedges pointing to hov to point to hv, effectively removing hov from all loops`
219	`HalfEdgeID he = kernel.out(hov);`	219	`HalfEdgeID he = kernel.out(hov);`
220	`HalfEdgeID last = he;`	220	`HalfEdgeID last = he;`
221	`do {`	221	`do {`
222	`assert(kernel.vert(kernel.opp(he)) == hov);`	222	`assert(kernel.vert(kernel.opp(he)) == hov);`
223	`kernel.set_vert(kernel.opp(he), hv);`	223	`kernel.set_vert(kernel.opp(he), hv);`
224	`he = kernel.next(kernel.opp(he));`	224	`he = kernel.next(kernel.opp(he));`
225	`}`	225	`}`
226	`while(he != last);`	226	`while(he != last);`
227	`kernel.set_out(hv, hn);`	227	`kernel.set_out(hv, hn);`
228		228
229	`// link hp and hn, effectively removing h from opposite loop`	229	`// link hp and hn, effectively removing h from opposite loop`
230	`link(hp, hn);`	230	`link(hp, hn);`
231	`// make face owning h own hn instead`	231	`// make face owning h own hn instead`
232	`if(kernel.face(h) != InvalidFaceID)`	232	`if(kernel.face(h) != InvalidFaceID)`
233	`kernel.set_last(f, hn);`	233	`kernel.set_last(f, hn);`
234		234
235	`// link hop and hon, effectively removing h from opposite face loop`	235	`// link hop and hon, effectively removing h from opposite face loop`
236	`link(hop, hon);`	236	`link(hop, hon);`
237	`// make opposite face owning h own hon instead`	237	`// make opposite face owning h own hon instead`
238	`if(kernel.face(ho) != InvalidFaceID)`	238	`if(kernel.face(ho) != InvalidFaceID)`
239	`kernel.set_last(fo, hon);`	239	`kernel.set_last(fo, hon);`
240		240
241	`// remove the obsolete entities`	241	`// remove the obsolete entities`
242	`kernel.remove_vertex(hov);`	242	`kernel.remove_vertex(hov);`
243	`kernel.remove_halfedge(h);`	243	`kernel.remove_halfedge(h);`
244	`kernel.remove_halfedge(ho);`	244	`kernel.remove_halfedge(ho);`
245		245
246	`// verify that remaining faces haven't become degenerate because of collapse`	246	`// verify that remaining faces haven't become degenerate because of collapse`
247	`remove_face_if_degenerate(hn);`	247	`remove_face_if_degenerate(hn);`
248	`remove_face_if_degenerate(hon);`	248	`remove_face_if_degenerate(hon);`
249		249
250	`// verify that v is sane after collapse`	250	`// verify that v is sane after collapse`
251	`ensure_boundary_consistency(hv);`	251	`ensure_boundary_consistency(hv);`
252	`}`	252	`}`
253		253
254	`FaceID Manifold::split_face_by_edge(FaceID f, VertexID v0, VertexID v1)`	254	`FaceID Manifold::split_face_by_edge(FaceID f, VertexID v0, VertexID v1)`
255	`{`	255	`{`
256	`assert(!connected(*this, v0, v1));`	256	`assert(!connected(*this, v0, v1));`
257	`HalfEdgeID he = kernel.last(f);`	257	`HalfEdgeID he = kernel.last(f);`
258	`HalfEdgeID last = he;`	258	`HalfEdgeID last = he;`
259	`int steps = 0;`	259	`int steps = 0;`
260	`while(he != last \|\| steps == 0){`	260	`while(he != last \|\| steps == 0){`
261	`++steps;`	261	`++steps;`
262	`he = kernel.next(he);`	262	`he = kernel.next(he);`
263	`}`	263	`}`
264		264
265	`// make sure this is not a triangle`	265	`// make sure this is not a triangle`
266	`assert(steps > 3);`	266	`assert(steps > 3);`
267	`// make sure we are not trying to connect a vertex to itself`	267	`// make sure we are not trying to connect a vertex to itself`
268	`assert(v0 != v1);`	268	`assert(v0 != v1);`
269		269
270	`HalfEdgeID h0 = kernel.out(v0);`	270	`HalfEdgeID h0 = kernel.out(v0);`
271	`for(Walker w = walker(v0); !w.full_circle(); w = w.circulate_vertex_cw()){`	271	`for(Walker w = walker(v0); !w.full_circle(); w = w.circulate_vertex_cw()){`
272	`if(w.face() == f){`	272	`if(w.face() == f){`
273	`h0 = w.halfedge();`	273	`h0 = w.halfedge();`
274	`break;`	274	`break;`
275	`}`	275	`}`
276	`}`	276	`}`
277	`assert(kernel.face(h0) != InvalidFaceID);`	277	`assert(kernel.face(h0) != InvalidFaceID);`
278	`assert(kernel.face(h0) == f);`	278	`assert(kernel.face(h0) == f);`
279		279
280	`// the halfedge belonging to f, going out from v0, is denoted h. Move along h until we hit v1.`	280	`// the halfedge belonging to f, going out from v0, is denoted h. Move along h until we hit v1.`
281	`// now we have the halfedge which belongs to f and points to v1.`	281	`// now we have the halfedge which belongs to f and points to v1.`
282	`HalfEdgeID h = h0;`	282	`HalfEdgeID h = h0;`
283	`while(kernel.vert(h) != v1){`	283	`while(kernel.vert(h) != v1){`
284	`h = kernel.next(h);`	284	`h = kernel.next(h);`
285	`}`	285	`}`
286	`assert(h != h0);`	286	`assert(h != h0);`
287		287
288	`// create a new halfedge ha which connects v1 and v0 closing the first loop.`	288	`// create a new halfedge ha which connects v1 and v0 closing the first loop.`
289	`HalfEdgeID h1 = kernel.next(h);`	289	`HalfEdgeID h1 = kernel.next(h);`
290	`HalfEdgeID ha = kernel.add_halfedge();`	290	`HalfEdgeID ha = kernel.add_halfedge();`
291	`link(h, ha);`	291	`link(h, ha);`
292	`link(ha, h0);`	292	`link(ha, h0);`
293	`kernel.set_face(ha, f);`	293	`kernel.set_face(ha, f);`
294	`kernel.set_vert(ha, v0);`	294	`kernel.set_vert(ha, v0);`
295	`kernel.set_last(f, ha);`	295	`kernel.set_last(f, ha);`
296		296
297	`// create a new face, f2, and set all halfedges in the remaining part of the polygon to point to this face.`	297	`// create a new face, f2, and set all halfedges in the remaining part of the polygon to point to this face.`
298	`h = h1;`	298	`h = h1;`
299	`FaceID f2 = kernel.add_face();`	299	`FaceID f2 = kernel.add_face();`
300	`while(kernel.vert(h) != v0){`	300	`while(kernel.vert(h) != v0){`
301	`kernel.set_face(h, f2);`	301	`kernel.set_face(h, f2);`
302	`h = kernel.next(h);`	302	`h = kernel.next(h);`
303	`}`	303	`}`
304	`kernel.set_face(h, f2);`	304	`kernel.set_face(h, f2);`
305	`assert(h != h1);`	305	`assert(h != h1);`
306		306
307	`// create a new halfedge hb to connect v0 and v1.`	307	`// create a new halfedge hb to connect v0 and v1.`
308	`HalfEdgeID hb = kernel.add_halfedge();`	308	`HalfEdgeID hb = kernel.add_halfedge();`
309	`link(h, hb);`	309	`link(h, hb);`
310	`link(hb, h1);`	310	`link(hb, h1);`
311	`kernel.set_face(hb, f2);`	311	`kernel.set_face(hb, f2);`
312	`kernel.set_vert(hb, v1);`	312	`kernel.set_vert(hb, v1);`
313	`kernel.set_last(f2, hb);`	313	`kernel.set_last(f2, hb);`
314		314
315	`// complete the operation by gluing the two new halfedges`	315	`// complete the operation by gluing the two new halfedges`
316	`glue(ha, hb);`	316	`glue(ha, hb);`
317		317
318	`// assert sanity of operation`	318	`// assert sanity of operation`
319	`assert(kernel.next(kernel.opp(kernel.prev(h1))) == h0);`	319	`assert(kernel.next(kernel.opp(kernel.prev(h1))) == h0);`
320	`assert(kernel.next(kernel.opp(kernel.prev(h0))) == h1);`	320	`assert(kernel.next(kernel.opp(kernel.prev(h0))) == h1);`
321	`assert(kernel.face(kernel.next(hb)) == f2);`	321	`assert(kernel.face(kernel.next(hb)) == f2);`
322	`assert(kernel.face(kernel.next(kernel.next(hb))) == f2);`	322	`assert(kernel.face(kernel.next(kernel.next(hb))) == f2);`
323	`assert(kernel.face(hb) == f2);`	323	`assert(kernel.face(hb) == f2);`
324		324
325	`// return handle to newly created face`	325	`// return handle to newly created face`
326	`return f2;`	326	`return f2;`
327	`}`	327	`}`
328		328
329	`VertexID Manifold::split_face_by_vertex(FaceID f)`	329	`VertexID Manifold::split_face_by_vertex(FaceID f)`
330	`{`	330	`{`
331	`//create the new vertex, with the barycenter of the face as position`	331	`//create the new vertex, with the barycenter of the face as position`
332	`Manifold::Vec p(0.0f);`	332	`Manifold::Vec p(0.0f);`
333	`HalfEdgeID last_he = kernel.last(f);`	333	`HalfEdgeID last_he = kernel.last(f);`
334	`HalfEdgeID he = last_he;`	334	`HalfEdgeID he = last_he;`
335	`int steps = 0;`	335	`int steps = 0;`
336		336
337	`while(he != last_he \|\| steps == 0){`	337	`while(he != last_he \|\| steps == 0){`
338	`p += positions[kernel.vert(he)];`	338	`p += positions[kernel.vert(he)];`
339	`++steps;`	339	`++steps;`
340	`he = kernel.next(he);`	340	`he = kernel.next(he);`
341	`}`	341	`}`
342		342
343	`p /= steps;`	343	`p /= steps;`
344		344
345	`VertexID v = kernel.add_vertex();`	345	`VertexID v = kernel.add_vertex();`
346	`positions[v] = p;`	346	`positions[v] = p;`
347		347
348	`//circulate the face, create halfedges and connect to vertex`	348	`//circulate the face, create halfedges and connect to vertex`
349	`vector<HalfEdgeID> eout;`	349	`vector<HalfEdgeID> eout;`
350	`vector<HalfEdgeID> ein;`	350	`vector<HalfEdgeID> ein;`
351	`last_he = kernel.last(f);`	351	`last_he = kernel.last(f);`
352	`he = last_he;`	352	`he = last_he;`
353		353
354	`do{`	354	`do{`
355	`HalfEdgeID hn = kernel.next(he);`	355	`HalfEdgeID hn = kernel.next(he);`
356		356
357	`HalfEdgeID ho = kernel.add_halfedge();`	357	`HalfEdgeID ho = kernel.add_halfedge();`
358	`HalfEdgeID hi = kernel.add_halfedge();`	358	`HalfEdgeID hi = kernel.add_halfedge();`
359		359
360	`FaceID fn = kernel.add_face();`	360	`FaceID fn = kernel.add_face();`
361	`kernel.set_face(hi, fn);`	361	`kernel.set_face(hi, fn);`
362	`kernel.set_vert(hi, v);`	362	`kernel.set_vert(hi, v);`
363	`kernel.set_face(ho, fn);`	363	`kernel.set_face(ho, fn);`
364	`kernel.set_vert(ho, kernel.vert(kernel.opp(he)));`	364	`kernel.set_vert(ho, kernel.vert(kernel.opp(he)));`
365	`kernel.set_face(he, fn);`	365	`kernel.set_face(he, fn);`
366	`kernel.set_last(fn, ho);`	366	`kernel.set_last(fn, ho);`
367		367
368	`link(hi, ho);`	368	`link(hi, ho);`
369	`link(ho, he);`	369	`link(ho, he);`
370	`link(he, hi);`	370	`link(he, hi);`
371		371
372	`eout.push_back(ho);`	372	`eout.push_back(ho);`
373	`ein.push_back(hi);`	373	`ein.push_back(hi);`
374		374
375	`he = hn;`	375	`he = hn;`
376	`}`	376	`}`
377	`while(he != last_he);`	377	`while(he != last_he);`
378		378
379	`// glue new halfedges together`	379	`// glue new halfedges together`
380	`size_t N = eout.size();`	380	`size_t N = eout.size();`
381	`for(size_t i = 0; i < N; ++i){`	381	`for(size_t i = 0; i < N; ++i){`
382	`glue(ein[i], eout[(i+1)%N]);`	382	`glue(ein[i], eout[(i+1)%N]);`
383	`}`	383	`}`
384	`kernel.set_out(v, eout[0]);`	384	`kernel.set_out(v, eout[0]);`
385		385
386	`//remove the now replaced face`	386	`//remove the now replaced face`
387	`kernel.remove_face(f);`	387	`kernel.remove_face(f);`
388		388
389	`return v;`	389	`return v;`
390	`}`	390	`}`
391	`VertexID Manifold::split_edge(HalfEdgeID h)`	391	`VertexID Manifold::split_edge(HalfEdgeID h)`
392	`{`	392	`{`
393	`HalfEdgeID ho = kernel.opp(h);`	393	`HalfEdgeID ho = kernel.opp(h);`
394	`VertexID v = kernel.vert(h);`	394	`VertexID v = kernel.vert(h);`
395	`VertexID vo = kernel.vert(ho);`	395	`VertexID vo = kernel.vert(ho);`
396		396
397	`//create the new vertex with middle of edge as position and update connectivity`	397	`//create the new vertex with middle of edge as position and update connectivity`
398	`VertexID vn = kernel.add_vertex();`	398	`VertexID vn = kernel.add_vertex();`
399	`positions[vn] = .5f * (positions[v] + positions[vo]);`	399	`positions[vn] = .5f * (positions[v] + positions[vo]);`
400	`kernel.set_out(vn, h);`	400	`kernel.set_out(vn, h);`
401		401
402	`//create two necessary halfedges, and update connectivity`	402	`//create two necessary halfedges, and update connectivity`
403	`HalfEdgeID hn = kernel.add_halfedge();`	403	`HalfEdgeID hn = kernel.add_halfedge();`
404	`HalfEdgeID hno = kernel.add_halfedge();`	404	`HalfEdgeID hno = kernel.add_halfedge();`
405		405
406	`kernel.set_out(vo, hn);`	406	`kernel.set_out(vo, hn);`
407	`kernel.set_out(v, ho);`	407	`kernel.set_out(v, ho);`
408		408
409	`glue(hn, hno);`	409	`glue(hn, hno);`
410		410
411	`link(kernel.prev(h), hn);`	411	`link(kernel.prev(h), hn);`
412	`link(hn, h);`	412	`link(hn, h);`
413		413
414	`kernel.set_vert(hn, vn);`	414	`kernel.set_vert(hn, vn);`
415		415
416	`link(hno, kernel.next(ho));`	416	`link(hno, kernel.next(ho));`
417	`link(ho, hno);`	417	`link(ho, hno);`
418		418
419	`kernel.set_vert(hno, vo);`	419	`kernel.set_vert(hno, vo);`
420	`kernel.set_vert(ho, vn);`	420	`kernel.set_vert(ho, vn);`
421		421
422	`// update faces in case of non boundary edge`	422	`// update faces in case of non boundary edge`
423	`if(kernel.face(h) != InvalidFaceID)`	423	`if(kernel.face(h) != InvalidFaceID)`
424	`kernel.set_last(kernel.face(h), hn);`	424	`kernel.set_last(kernel.face(h), hn);`
425		425
426	`if(kernel.face(ho) != InvalidFaceID)`	426	`if(kernel.face(ho) != InvalidFaceID)`
427	`kernel.set_last(kernel.face(ho), ho);`	427	`kernel.set_last(kernel.face(ho), ho);`
428		428
429	`// update new edge with faces from existing edge`	429	`// update new edge with faces from existing edge`
430	`kernel.set_face(hn, kernel.face(h));`	430	`kernel.set_face(hn, kernel.face(h));`
431	`kernel.set_face(hno, kernel.face(ho));`	431	`kernel.set_face(hno, kernel.face(ho));`
432		432
433	`//if split occurs on a boundary, consistency must be ensured.`	433	`//if split occurs on a boundary, consistency must be ensured.`
434	`ensure_boundary_consistency(vn);`	434	`ensure_boundary_consistency(vn);`
435	`ensure_boundary_consistency(v);`	435	`ensure_boundary_consistency(v);`
436	`ensure_boundary_consistency(vo);`	436	`ensure_boundary_consistency(vo);`
437		437
438	`return vn;`	438	`return vn;`
439	`}`	439	`}`
440		440
441	`size_t link_intersection(const Manifold& m, VertexID v0, VertexID v1, vector<VertexID>& lisect)`	441	`size_t link_intersection(const Manifold& m, VertexID v0, VertexID v1, vector<VertexID>& lisect)`
442	`{`	442	`{`
443	`// get the one-ring of v0`	443	`// get the one-ring of v0`
444	`vector<VertexID> link0;`	444	`vector<VertexID> link0;`
445	`for(Walker vj = m.walker(v0);`	445	`for(Walker vj = m.walker(v0);`
446	`!vj.full_circle(); vj = vj.circulate_vertex_ccw())`	446	`!vj.full_circle(); vj = vj.circulate_vertex_ccw())`
447	`link0.push_back(vj.vertex());`	447	`link0.push_back(vj.vertex());`
448		448
449	`// get the one-ring of v1`	449	`// get the one-ring of v1`
450	`vector<VertexID> link1;`	450	`vector<VertexID> link1;`
451	`for(Walker vj = m.walker(v1);`	451	`for(Walker vj = m.walker(v1);`
452	`!vj.full_circle(); vj = vj.circulate_vertex_ccw())`	452	`!vj.full_circle(); vj = vj.circulate_vertex_ccw())`
453	`link1.push_back(vj.vertex());`	453	`link1.push_back(vj.vertex());`
454		454
455	`// sort the vertices of the two rings`	455	`// sort the vertices of the two rings`
456	`sort(link0.begin(), link0.end());`	456	`sort(link0.begin(), link0.end());`
457	`sort(link1.begin(), link1.end());`	457	`sort(link1.begin(), link1.end());`
458		458
459	`// get the intersection of the shared vertices from both rings`	459	`// get the intersection of the shared vertices from both rings`
460	`std::back_insert_iterator<vector<VertexID> > lii(lisect);`	460	`std::back_insert_iterator<vector<VertexID> > lii(lisect);`
461	`set_intersection(link0.begin(), link0.end(),`	461	`set_intersection(link0.begin(), link0.end(),`
462	`link1.begin(), link1.end(),`	462	`link1.begin(), link1.end(),`
463	`lii);`	463	`lii);`
464		464
465	`return lisect.size();`	465	`return lisect.size();`
466	`}`	466	`}`
467		467
468	`bool Manifold::stitch_boundary_edges(HalfEdgeID h0, HalfEdgeID h1)`	468	`bool Manifold::stitch_boundary_edges(HalfEdgeID h0, HalfEdgeID h1)`
469	`{`	469	`{`
470	`// Cannot stitch an edge with itself`	470	`// Cannot stitch an edge with itself`
471	`if(h0 == h1)`	471	`if(h0 == h1)`
472	`return false;`	472	`return false;`
473		473
474	`// Only stitch a pair of boundary edges.`	474	`// Only stitch a pair of boundary edges.`
475	`if(kernel.face(h0) == InvalidFaceID && kernel.face(h1) == InvalidFaceID)`	475	`if(kernel.face(h0) == InvalidFaceID && kernel.face(h1) == InvalidFaceID)`
476	`{`	476	`{`
477	`HalfEdgeID h0o = kernel.opp(h0);`	477	`HalfEdgeID h0o = kernel.opp(h0);`
478	`HalfEdgeID h1o = kernel.opp(h1);`	478	`HalfEdgeID h1o = kernel.opp(h1);`
479	`VertexID v0a = kernel.vert(h0);`	479	`VertexID v0a = kernel.vert(h0);`
480	`VertexID v0b = kernel.vert(kernel.opp(h1));`	480	`VertexID v0b = kernel.vert(kernel.opp(h1));`
481	`VertexID v1b = kernel.vert(h1);`	481	`VertexID v1b = kernel.vert(h1);`
482	`VertexID v1a = kernel.vert(kernel.opp(h0));`	482	`VertexID v1a = kernel.vert(kernel.opp(h0));`
483		483
484	`// Case below implies that h0 and h1 are the same edge with different ID`	484	`// Case below implies that h0 and h1 are the same edge with different ID`
485	`// That should not happen.`	485	`// That should not happen.`
486	`assert(!(v0a == v0b && v1a == v1b));`	486	`assert(!(v0a == v0b && v1a == v1b));`
487		487
488	`if(connected(*this, v0a, v0b))`	488	`if(connected(*this, v0a, v0b))`
489	`return false;`	489	`return false;`
490	`if(connected(*this, v1a, v1b))`	490	`if(connected(*this, v1a, v1b))`
491	`return false;`	491	`return false;`
492		492
493		493
494	`if(v0b != v0a)`	494	`if(v0b != v0a)`
495	`{`	495	`{`
496		496
497	`// Check the link intersection v0a and v0b are welded together`	497	`// Check the link intersection v0a and v0b are welded together`
498	`// if they share a neighbouring vertex, it will appear twice in the combined`	498	`// if they share a neighbouring vertex, it will appear twice in the combined`
499	`// one ring unless it v1a and v1a==v1b`	499	`// one ring unless it v1a and v1a==v1b`
500	`vector<VertexID> lisect;`	500	`vector<VertexID> lisect;`

Subversion Repositories gelsvn

(root)/trunk/src/HMesh/Manifold.cpp – Rev 601 → 605