WebSVN – gelsvn – Diff – /branches/ctl/hmesh_vector/src/HMesh/Manifold.cpp



                    return v1 < k2.v1;
                }
            }
        private:
            VertexID v0;
            VertexID v1;
        };
		
        struct Edge
        {
            HalfEdgeID h0;

						 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(int 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 remove_face(FaceID fid);
//    
//    bool remove_edge(HalfEdgeID hid);
//    
//    bool remove_vertex(VertexID vid);
 
    
	
    void Manifold::collapse_edge(HalfEdgeID h, bool avg_vertices)
    {
        HalfEdgeID ho = kernel.opp(h);
        VertexID hv = kernel.vert(h);

        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);

    }
    
    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;

            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;

                    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;
                }
            }

                    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;
                }
            }

        // 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());
        }
        
        

        for(int 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())

        // Finally, we ensure boundary consitency for all vertices in the loop.
        for(int i=0;i<loop.size(); ++i)
        {
            Walker hw = walker(loop[i]);
            ensure_boundary_consistency(hw.vertex());
        }
        
        // Return the brand new merged face.
        return 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;

        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);

        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

                // 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;

                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);
                }
            }
            

        
        // 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);

    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(int i=0;i<N; ++i)
        {

                
                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;
                }
            }

            }
        }
        return true;
    }
    
    void bbox(const Manifold& m, Manifold::Vec& pmin, Manifold::Vec& pmax)
    {
        
        VertexIDIterator v = m.vertices_begin();
        pmin = pmax = m.pos(*v);
        ++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;

        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());
        }

        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();

    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();

    }
    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)

        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)

        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 589	Rev 593
Line 52...	Line 52...
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;`
Line 87...	Line 87...
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
-		102	`FaceID Manifold::add_face(std::vector<Manifold::Vec> points)`
-		103	`{`
-		104	`int F = points.size();`
-		105	`vector<int> indices;`
-		106	`for(int i=0;i<points.size(); ++i)`
-		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	`}`
-		112
-		113	`// bool remove_face(FaceID fid);`
-		114	`//`
-		115	`// bool remove_edge(HalfEdgeID hid);`
-		116	`//`
-		117	`// bool remove_vertex(VertexID vid);`
101		118
-		119
102		120
103	`void Manifold::collapse_edge(HalfEdgeID h, bool avg_vertices)`	121	`void Manifold::collapse_edge(HalfEdgeID h, bool avg_vertices)`
104	`{`	122	`{`
105	`HalfEdgeID ho = kernel.opp(h);`	123	`HalfEdgeID ho = kernel.opp(h);`
106	`VertexID hv = kernel.vert(h);`	124	`VertexID hv = kernel.vert(h);`
Line 116...	Line 134...
116	`pos(hv) = avg_vertices ? (0.5f * (pos(hov) + pos(hv))) : pos(hv);`	134	`pos(hv) = avg_vertices ? (0.5f * (pos(hov) + pos(hv))) : pos(hv);`
117		135
118	`// update all halfedges pointing to hov to point to hv, effectively removing hov from all loops`	136	`// update all halfedges pointing to hov to point to hv, effectively removing hov from all loops`
119	`HalfEdgeID he = kernel.out(hov);`	137	`HalfEdgeID he = kernel.out(hov);`
120	`HalfEdgeID last = he;`	138	`HalfEdgeID last = he;`
121	`do {`	139	`do {`
122	`assert(kernel.vert(kernel.opp(he)) == hov);`	140	`assert(kernel.vert(kernel.opp(he)) == hov);`
123	`kernel.set_vert(kernel.opp(he), hv);`	141	`kernel.set_vert(kernel.opp(he), hv);`
124	`he = kernel.next(kernel.opp(he));`	142	`he = kernel.next(kernel.opp(he));`
125	`}`	143	`}`
126	`while(he != last);`	144	`while(he != last);`
127	`kernel.set_out(hv, hn);`	145	`kernel.set_out(hv, hn);`
128		146
129	`// link hp and hn, effectively removing h from opposite loop`	147	`// link hp and hn, effectively removing h from opposite loop`
130	`link(hp, hn);`	148	`link(hp, hn);`
Line 339...	Line 357...
339	`}`	357	`}`
340		358
341	`size_t link_intersection(const Manifold& m, VertexID v0, VertexID v1, vector<VertexID>& lisect)`	359	`size_t link_intersection(const Manifold& m, VertexID v0, VertexID v1, vector<VertexID>& lisect)`
342	`{`	360	`{`
343	`// get the one-ring of v0`	361	`// get the one-ring of v0`
344	`vector<VertexID> link0;`	362	`vector<VertexID> link0;`
345	`for(Walker vj = m.walker(v0);`	363	`for(Walker vj = m.walker(v0);`
346	`!vj.full_circle(); vj = vj.circulate_vertex_ccw())`	364	`!vj.full_circle(); vj = vj.circulate_vertex_ccw())`
347	`link0.push_back(vj.vertex());`	365	`link0.push_back(vj.vertex());`
348		366
349	`// get the one-ring of v1`	367	`// get the one-ring of v1`
350	`vector<VertexID> link1;`	368	`vector<VertexID> link1;`
Line 381...	Line 399...
381	`VertexID v1b = kernel.vert(h1);`	399	`VertexID v1b = kernel.vert(h1);`
382	`VertexID v1a = kernel.vert(kernel.opp(h0));`	400	`VertexID v1a = kernel.vert(kernel.opp(h0));`
383		401
384	`// Case below implies that h0 and h1 are the same edge with different ID`	402	`// Case below implies that h0 and h1 are the same edge with different ID`
385	`// That should not happen.`	403	`// That should not happen.`
386	`assert(!(v0a == v0b && v1a == v1b));`	404	`assert(!(v0a == v0b && v1a == v1b));`
387		405
388	`if(connected(*this, v0a, v0b))`	406	`if(connected(*this, v0a, v0b))`
389	`return false;`	407	`return false;`
390	`if(connected(*this, v1a, v1b))`	408	`if(connected(*this, v1a, v1b))`
391	`return false;`	409	`return false;`
Line 403...	Line 421...
403	`vector<VertexID>::iterator iter;`	421	`vector<VertexID>::iterator iter;`
404		422
405	`if(v1a == v1b)`	423	`if(v1a == v1b)`
406	`{`	424	`{`
407	`iter = find(lisect.begin(), lisect.end(), v1a);`	425	`iter = find(lisect.begin(), lisect.end(), v1a);`
408	`if(iter != lisect.end())`	426	`if(iter != lisect.end())`
409	`lisect.erase(iter);`	427	`lisect.erase(iter);`
410	`}`	428	`}`
411	`iter = find(lisect.begin(), lisect.end(), kernel.vert(kernel.next(h0)));`	429	`iter = find(lisect.begin(), lisect.end(), kernel.vert(kernel.next(h0)));`
412	`if(iter != lisect.end())`	430	`if(iter != lisect.end())`
413	`lisect.erase(iter);`	431	`lisect.erase(iter);`
414	`if(lisect.size() > 0)`	432	`if(lisect.size() > 0)`
415	`return false;`	433	`return false;`
416	`}`	434	`}`
417	`}`	435	`}`
Line 425...	Line 443...
425	`vector<VertexID>::iterator iter;`	443	`vector<VertexID>::iterator iter;`
426		444
427	`if(v0a == v0b)`	445	`if(v0a == v0b)`
428	`{`	446	`{`
429	`iter = find(lisect.begin(), lisect.end(), v1a);`	447	`iter = find(lisect.begin(), lisect.end(), v1a);`
430	`if(iter != lisect.end())`	448	`if(iter != lisect.end())`
431	`lisect.erase(iter);`	449	`lisect.erase(iter);`
432	`}`	450	`}`
433	`iter = find(lisect.begin(), lisect.end(), kernel.vert(kernel.next(h1)));`	451	`iter = find(lisect.begin(), lisect.end(), kernel.vert(kernel.next(h1)));`
434	`if(iter != lisect.end())`	452	`if(iter != lisect.end())`
435	`lisect.erase(iter);`	453	`lisect.erase(iter);`
436	`if(lisect.size() > 0)`	454	`if(lisect.size() > 0)`
437	`return false;`	455	`return false;`
438	`}`	456	`}`
439	`}`	457	`}`
Line 509...	Line 527...
509	`// one incident edge (or less), bail out.`	527	`// one incident edge (or less), bail out.`
510	`int val = valency(*this,v);`	528	`int val = valency(*this,v);`
511	`if(!in_use(v) \|\| val<2)`	529	`if(!in_use(v) \|\| val<2)`
512	`return InvalidFaceID;`	530	`return InvalidFaceID;`
513		531
514	`// If the vertex is a boundary vertex, we preparte the walker so that the`	532	`// If the vertex is a boundary vertex, we preparte the walker so that the`
515	`// first face visited is not the invalid face outside the boundary. If the boundary`	533	`// first face visited is not the invalid face outside the boundary. If the boundary`
516	`// vertex is adjacent to only one vertex, there is little to do and we bail out.`	534	`// vertex is adjacent to only one vertex, there is little to do and we bail out.`
517	`bool vertex_is_boundary = false;`	535	`bool vertex_is_boundary = false;`
518	`Walker hew = walker(v);`	536	`Walker hew = walker(v);`
519	`if(boundary(*this, v))`	537	`if(boundary(*this, v))`
520	`{`	538	`{`
521	`if(val==2) return InvalidFaceID;`	539	`if(val==2) return InvalidFaceID;`
522	`vertex_is_boundary = true;`	540	`vertex_is_boundary = true;`
523	`hew = hew.circulate_vertex_ccw();`	541	`hew = hew.circulate_vertex_ccw();`
524	`}`	542	`}`
525		543
526	`// Prepare some vectors for taking out the trash: We remove all old faces and all orphaned edges`	544	`// Prepare some vectors for taking out the trash: We remove all old faces and all orphaned edges`
527	`// and vertices`	545	`// and vertices`
528	`vector<HalfEdgeID> garbage_halfedges;`	546	`vector<HalfEdgeID> garbage_halfedges;`
529	`vector<FaceID> garbage_faces;`	547	`vector<FaceID> garbage_faces;`
530	`vector<VertexID> garbage_vertices;`	548	`vector<VertexID> garbage_vertices;`
531		549
532	`vector<HalfEdgeID> loop; // The halfedges which form the outer loop of the merged one ring.`	550	`vector<HalfEdgeID> loop; // The halfedges which form the outer loop of the merged one ring.`
533		551
534	`// Below we loop over all faces adjacent to the vertex and add their halfedges to a big loop`	552	`// Below we loop over all faces adjacent to the vertex and add their halfedges to a big loop`
535	`// which will form the loop of the new merged face. Below we remove from the loop edges`	553	`// which will form the loop of the new merged face. Below we remove from the loop edges`
536	`// that appear twice (as each other's opposite).`	554	`// that appear twice (as each other's opposite).`
537	`for(;!hew.full_circle(); hew = hew.circulate_vertex_ccw())`	555	`for(;!hew.full_circle(); hew = hew.circulate_vertex_ccw())`
538	`{`	556	`{`
539	`garbage_faces.push_back(hew.face());`	557	`garbage_faces.push_back(hew.face());`
540	`for(Walker hew2 = walker(hew.halfedge());`	558	`for(Walker hew2 = walker(hew.halfedge());`
541	`!hew2.full_circle(); hew2 = hew2.circulate_face_ccw())`	559	`!hew2.full_circle(); hew2 = hew2.circulate_face_ccw())`
542	`loop.push_back(hew2.halfedge());`	560	`loop.push_back(hew2.halfedge());`
543	`}`	561	`}`
544		562
545		563
Line 576...	Line 594...
576	`for(int i=0;i<loop.size();++i)`	594	`for(int i=0;i<loop.size();++i)`
577	`loop_len += length(*this, loop[i]);`	595	`loop_len += length(*this, loop[i]);`
578	`if(loop_len > max_loop_length)`	596	`if(loop_len > max_loop_length)`
579	`return InvalidFaceID;`	597	`return InvalidFaceID;`
580		598
581	`// The following block checks wheteher the same halfedge appears twice. In this`	599	`// The following block checks wheteher the same halfedge appears twice. In this`
582	`// case we fail since it means that the one ring contains the same face twice.`	600	`// case we fail since it means that the one ring contains the same face twice.`
583	`vector<HalfEdgeID> loop_tmp = loop;`	601	`vector<HalfEdgeID> loop_tmp = loop;`
584	`sort(loop_tmp.begin(), loop_tmp.end());`	602	`sort(loop_tmp.begin(), loop_tmp.end());`
585	`vector<HalfEdgeID>::iterator end_iter = unique(loop_tmp.begin(), loop_tmp.end());`	603	`vector<HalfEdgeID>::iterator end_iter = unique(loop_tmp.begin(), loop_tmp.end());`
586	`if(end_iter != loop_tmp.end())`	604	`if(end_iter != loop_tmp.end())`
Line 612...	Line 630...
612	`// Finally, we ensure boundary consitency for all vertices in the loop.`	630	`// Finally, we ensure boundary consitency for all vertices in the loop.`
613	`for(int i=0;i<loop.size(); ++i)`	631	`for(int i=0;i<loop.size(); ++i)`
614	`{`	632	`{`
615	`Walker hw = walker(loop[i]);`	633	`Walker hw = walker(loop[i]);`
616	`ensure_boundary_consistency(hw.vertex());`	634	`ensure_boundary_consistency(hw.vertex());`
617	`}`	635	`}`
618		636
619	`// Return the brand new merged face.`	637	`// Return the brand new merged face.`
620	`return f;`	638	`return f;`
621	`}`	639	`}`
622		640
Line 630...	Line 648...
630	`HalfEdgeID ho = kernel.opp(h);`	648	`HalfEdgeID ho = kernel.opp(h);`
631	`FaceID fo = kernel.face(ho);`	649	`FaceID fo = kernel.face(ho);`
632	`HalfEdgeID hn = kernel.next(h);`	650	`HalfEdgeID hn = kernel.next(h);`
633	`HalfEdgeID hon = kernel.next(ho);`	651	`HalfEdgeID hon = kernel.next(ho);`
634		652
635	`if(fo == f)`	653	`if(fo == f)`
636	`return false;`	654	`return false;`
637		655
638	`//boundary case`	656	`//boundary case`
639	`if(kernel.vert(hn) == kernel.vert(hon))`	657	`if(kernel.vert(hn) == kernel.vert(hon))`
640	`return false;`	658	`return false;`
Line 668...	Line 686...
668	`kernel.remove_halfedge(ho);`	686	`kernel.remove_halfedge(ho);`
669	`kernel.remove_face(fo);`	687	`kernel.remove_face(fo);`
670		688
671	`return true;`	689	`return true;`
672	`}`	690	`}`
-		691
673	`void Manifold::close_hole(HalfEdgeID h)`	692	`FaceID Manifold::close_hole(HalfEdgeID h)`
674	`{`	693	`{`
675	`// invalid face is a hole`	694	`// invalid face is a hole`
676	`if(kernel.face(h) == InvalidFaceID){`	695	`if(kernel.face(h) == InvalidFaceID){`
677	`FaceID f = kernel.add_face();`	696	`FaceID f = kernel.add_face();`
678	`kernel.set_last(f, h);`	697	`kernel.set_last(f, h);`
679	`do{`	698	`do{`
680	`kernel.set_face(h, f);`	699	`kernel.set_face(h, f);`
681	`h = kernel.next(h);`	700	`h = kernel.next(h);`
682	`}`	701	`}`
683	`while(kernel.face(h) != f);`	702	`while(kernel.face(h) != f);`
-		703	`return f;`
684	`}`	704	`}`
-		705	`return kernel.face(h);`
685	`}`	706	`}`
686	`void Manifold::flip_edge(HalfEdgeID h)`	707	`void Manifold::flip_edge(HalfEdgeID h)`
687	`{`	708	`{`
688	`HalfEdgeID hn = kernel.next(h);`	709	`HalfEdgeID hn = kernel.next(h);`
689	`HalfEdgeID hp = kernel.prev(h);`	710	`HalfEdgeID hp = kernel.prev(h);`
690	`HalfEdgeID ho = kernel.opp(h);`	711	`HalfEdgeID ho = kernel.opp(h);`
691	`HalfEdgeID hon = kernel.next(ho);`	712	`HalfEdgeID hon = kernel.next(ho);`
692	`HalfEdgeID hop = kernel.prev(ho);`	713	`HalfEdgeID hop = kernel.prev(ho);`
Line 724...	Line 745...
724	`if(kernel.out(hv) == ho)`	745	`if(kernel.out(hv) == ho)`
725	`kernel.set_out(hv, hn);`	746	`kernel.set_out(hv, hn);`
726	`if(kernel.out(hov) == h)`	747	`if(kernel.out(hov) == h)`
727	`kernel.set_out(hov, hon);`	748	`kernel.set_out(hov, hon);`
728		749
729	`//`	750	`//`
730	`// // if the flip occurs next to a boundary, ensure the boundary consistency`	751	`// // if the flip occurs next to a boundary, ensure the boundary consistency`
731	`// ensure_boundary_consistency(hv);`	752	`// ensure_boundary_consistency(hv);`
732	`// ensure_boundary_consistency(hov);`	753	`// ensure_boundary_consistency(hov);`
733	`}`	754	`}`
734		755
735		756
736	`/**********************************************`	757	`/**********************************************`
737	`* Private functions`	758	`* Private functions`
Line 781...	Line 802...
781	`// create key and search map for edge`	802	`// create key and search map for edge`
782	`EdgeKey ek(v0, v1);`	803	`EdgeKey ek(v0, v1);`
783	`EdgeMap::iterator em_iter = edge_map.find(ek);`	804	`EdgeMap::iterator em_iter = edge_map.find(ek);`
784		805
785	`// current edge has not been created`	806	`// current edge has not been created`
786	`if(em_iter == edge_map.end()){`	807	`if(em_iter == edge_map.end()){`
787	`// create edge for map`	808	`// create edge for map`
788	`Edge e;`	809	`Edge e;`
789	`e.h0 = kernel.add_halfedge();`	810	`e.h0 = kernel.add_halfedge();`
790	`e.h1 = kernel.add_halfedge();`	811	`e.h1 = kernel.add_halfedge();`
791	`e.count = 1;`	812	`e.count = 1;`
Line 810...	Line 831...
810	`else{`	831	`else{`
811	`// update current face with halfedge from edge`	832	`// update current face with halfedge from edge`
812	`fh.push_back(em_iter->second.h1);`	833	`fh.push_back(em_iter->second.h1);`
813		834
814	`// asserting that a halfedge is visited exactly twice;`	835	`// asserting that a halfedge is visited exactly twice;`
815	`// once for each face on either side of the edge.`	836	`// once for each face on either side of the edge.`
816	`em_iter->second.count++;`	837	`em_iter->second.count++;`
817	`assert(em_iter->second.count == 2);`	838	`assert(em_iter->second.count == 2);`
818	`}`	839	`}`
819	`}`	840	`}`
820		841
Line 842...	Line 863...
842		863
843	`// boundary check while avoiding unused vertices`	864	`// boundary check while avoiding unused vertices`
844	`for(VertexIDIterator v = vertices_begin(); v != vertices_end(); ++v){`	865	`for(VertexIDIterator v = vertices_begin(); v != vertices_end(); ++v){`
845	`if((*v) != InvalidVertexID)`	866	`if((*v) != InvalidVertexID)`
846	`ensure_boundary_consistency(*v);`	867	`ensure_boundary_consistency(*v);`
847	`}`	868	`}`
848	`}`	869	`}`
849	`void Manifold::link(HalfEdgeID h0, HalfEdgeID h1)`	870	`void Manifold::link(HalfEdgeID h0, HalfEdgeID h1)`
850	`{`	871	`{`
851	`kernel.set_next(h0, h1);`	872	`kernel.set_next(h0, h1);`
852	`kernel.set_prev(h1, h0);`	873	`kernel.set_prev(h1, h0);`
Line 921...	Line 942...
921	`vector<HalfEdgeID> Manifold::bridge_faces(FaceID f0, FaceID f1, const vector<pair<VertexID, VertexID> >& pairs)`	942	`vector<HalfEdgeID> Manifold::bridge_faces(FaceID f0, FaceID f1, const vector<pair<VertexID, VertexID> >& pairs)`
922	`{`	943	`{`
923	`// Let N be the number of vertex pairs to connect by edges`	944	`// Let N be the number of vertex pairs to connect by edges`
924	`size_t N = pairs.size();`	945	`size_t N = pairs.size();`
925		946
926	`// We now create N pairs of edges, glue each pair and let them point to the appropriate`	947	`// We now create N pairs of edges, glue each pair and let them point to the appropriate`
927	`// vertices.`	948	`// vertices.`
928	`vector<HalfEdgeID> new_halfedges(N);`	949	`vector<HalfEdgeID> new_halfedges(N);`
929	`vector<HalfEdgeID> new_halfedges_opp(N);`	950	`vector<HalfEdgeID> new_halfedges_opp(N);`
930	`for(int i=0;i<N; ++i)`	951	`for(int i=0;i<N; ++i)`
931	`{`	952	`{`
Line 1045...	Line 1066...
1045		1066
1046	`if(j.face() != InvalidFaceID && j.opp().face() != InvalidFaceID)`	1067	`if(j.face() != InvalidFaceID && j.opp().face() != InvalidFaceID)`
1047	`{`	1068	`{`
1048	`if(link.size()==1)`	1069	`if(link.size()==1)`
1049	`cout << "Vertex contains only a single incident edge" << endl;`	1070	`cout << "Vertex contains only a single incident edge" << endl;`
1050	`//`	1071	`//`
1051	`// cout << "Vertex contains only " << link.size() <<" incident edges" << endl;`	1072	`// cout << "Vertex contains only " << link.size() <<" incident edges" << endl;`
1052	`}`	1073	`}`
1053	`else`	1074	`else`
1054	`cout << "Boundary vertex contains only " << link.size() <<" incident edges" << endl;`	1075	`cout << "Boundary vertex contains only " << link.size() <<" incident edges" << endl;`
1055	`}`	1076	`}`
Line 1057...	Line 1078...
1057	`// verify components of faces`	1078	`// verify components of faces`
1058	`for(FaceIDIterator f = m.faces_begin(); f != m.faces_end(); ++f){`	1079	`for(FaceIDIterator f = m.faces_begin(); f != m.faces_end(); ++f){`
1059	`// count edges on face`	1080	`// count edges on face`
1060	`Walker j = m.walker(*f);`	1081	`Walker j = m.walker(*f);`
1061		1082
1062	`for(; !j.full_circle(); j = j.circulate_face_cw()){`	1083	`for(; !j.full_circle(); j = j.circulate_face_cw()){`
1063	`// test that all halfedges in faces bind properly to their face`	1084	`// test that all halfedges in faces bind properly to their face`
1064	`if(j.face() != *f){`	1085	`if(j.face() != *f){`
1065	`cout << "Face is inconsistent, halfedge is not bound to face" << endl;`	1086	`cout << "Face is inconsistent, halfedge is not bound to face" << endl;`
1066	`return false;`	1087	`return false;`
1067	`}`	1088	`}`
1068	`}`	1089	`}`
Line 1078...	Line 1099...
1078	`}`	1099	`}`
1079	`}`	1100	`}`
1080	`return true;`	1101	`return true;`
1081	`}`	1102	`}`
1082		1103
1083	`void bbox(const Manifold& m, Manifold::Vec& pmin, Manifold::Vec& pmax)`	1104	`void bbox(const Manifold& m, Manifold::Vec& pmin, Manifold::Vec& pmax)`
1084	`{`	1105	`{`
1085		1106
1086	`VertexIDIterator v = m.vertices_begin();`	1107	`VertexIDIterator v = m.vertices_begin();`
1087	`pmin = pmax = m.pos(*v);`	1108	`pmin = pmax = m.pos(*v);`
1088	`++v;`	1109	`++v;`
Line 1090...	Line 1111...
1090	`pmin = v_min(m.pos(*v), pmin);`	1111	`pmin = v_min(m.pos(*v), pmin);`
1091	`pmax = v_max(m.pos(*v), pmax);`	1112	`pmax = v_max(m.pos(*v), pmax);`
1092	`}`	1113	`}`
1093	`}`	1114	`}`
1094		1115
1095	`void bsphere(const Manifold& m, Manifold::Vec& c, float& r)`	1116	`void bsphere(const Manifold& m, Manifold::Vec& c, float& r)`
1096	`{`	1117	`{`
1097	`Manifold::Vec p0, p7;`	1118	`Manifold::Vec p0, p7;`
1098	`bbox(m, p0, p7);`	1119	`bbox(m, p0, p7);`
1099	`Manifold::Vec rad = (p7 - p0) * 0.5f;`	1120	`Manifold::Vec rad = (p7 - p0) * 0.5f;`
1100	`c = p0 + rad;`	1121	`c = p0 + rad;`
Line 1109...	Line 1130...
1109	`HalfEdgeID ho = hew.opp().halfedge();`	1130	`HalfEdgeID ho = hew.opp().halfedge();`
1110	`VertexID v0 = hew.opp().vertex();`	1131	`VertexID v0 = hew.opp().vertex();`
1111	`VertexID v1 = hew.vertex();`	1132	`VertexID v1 = hew.vertex();`
1112		1133
1113	`// get the one-ring of v0`	1134	`// get the one-ring of v0`
1114	`vector<VertexID> link0;`	1135	`vector<VertexID> link0;`
1115	`vector<FaceID> faces0;`	1136	`vector<FaceID> faces0;`
1116	`for(Walker vj = m.walker(h);`	1137	`for(Walker vj = m.walker(h);`
1117	`!vj.full_circle(); vj = vj.circulate_vertex_ccw()){`	1138	`!vj.full_circle(); vj = vj.circulate_vertex_ccw()){`
1118	`link0.push_back(vj.vertex());`	1139	`link0.push_back(vj.vertex());`
1119	`if(vj.halfedge() != h)`	1140	`if(vj.halfedge() != h)`
1120	`faces0.push_back(vj.face());`	1141	`faces0.push_back(vj.face());`
1121	`}`	1142	`}`
Line 1152...	Line 1173...
1152	`std::back_insert_iterator<vector<FaceID> > fii(fisect);`	1173	`std::back_insert_iterator<vector<FaceID> > fii(fisect);`
1153	`set_intersection(faces0.begin(), faces0.end(),`	1174	`set_intersection(faces0.begin(), faces0.end(),`
1154	`faces1.begin(), faces1.end(),`	1175	`faces1.begin(), faces1.end(),`
1155	`fii);`	1176	`fii);`
1156	`if(fisect.size() > 0)`	1177	`if(fisect.size() > 0)`
1157	`return false;`	1178	`return false;`
1158		1179
1159	`int k = 0;`	1180	`int k = 0;`
1160	`// if the adjacent face is a triangle (see 2)`	1181	`// if the adjacent face is a triangle (see 2)`
1161	`if(hew.next().next().next().halfedge() == h){`	1182	`if(hew.next().next().next().halfedge() == h){`
1162	`VertexID v = hew.next().vertex();`	1183	`VertexID v = hew.next().vertex();`
Line 1205...	Line 1226...
1205	`bool precond_flip_edge(const Manifold& m, HalfEdgeID h)`	1226	`bool precond_flip_edge(const Manifold& m, HalfEdgeID h)`
1206	`{`	1227	`{`
1207	`Walker j = m.walker(h);`	1228	`Walker j = m.walker(h);`
1208		1229
1209	`FaceID hf = j.face();`	1230	`FaceID hf = j.face();`
1210	`// HalfEdgeID ho = j.opp().halfedge();`	1231	`// HalfEdgeID ho = j.opp().halfedge();`
1211	`FaceID hof = j.opp().face();`	1232	`FaceID hof = j.opp().face();`
1212		1233
1213	`// boundary case`	1234	`// boundary case`
1214	`if(hf == InvalidFaceID \|\| hof == InvalidFaceID)`	1235	`if(hf == InvalidFaceID \|\| hof == InvalidFaceID)`
1215	`return false;`	1236	`return false;`
1216		1237
1217	`// We can only flip an edge if both incident polygons are triangles.`	1238	`// We can only flip an edge if both incident polygons are triangles.`
1218	`if(no_edges(m, hf) != 3 \|\| no_edges(m, hof) !=3)`	1239	`if(no_edges(m, hf) != 3 \|\| no_edges(m, hof) !=3)`
1219	`return false;`	1240	`return false;`
1220		1241
1221	`// non boundary vertices with a valency of less than 4(less than 3 after operation) degenerates mesh.`	1242	`// non boundary vertices with a valency of less than 4(less than 3 after operation) degenerates mesh.`
1222	`VertexID hv = j.vertex();`	1243	`VertexID hv = j.vertex();`
Line 1240...	Line 1261...
1240	`}`	1261	`}`
1241	`int valency(const Manifold& m, VertexID v)`	1262	`int valency(const Manifold& m, VertexID v)`
1242	`{`	1263	`{`
1243	`// perform full circulation to get valency`	1264	`// perform full circulation to get valency`
1244	`Walker vj = m.walker(v);`	1265	`Walker vj = m.walker(v);`
1245	`while(!vj.full_circle())`	1266	`while(!vj.full_circle())`
1246	`vj = vj.circulate_vertex_cw();`	1267	`vj = vj.circulate_vertex_cw();`
1247	`return vj.no_steps();`	1268	`return vj.no_steps();`
1248	`}`	1269	`}`
1249		1270
1250	`Manifold::Vec normal(const Manifold& m, VertexID v)`	1271	`Manifold::Vec normal(const Manifold& m, VertexID v)`
Line 1264...	Line 1285...
1264	`if(N<2)`	1285	`if(N<2)`
1265	`return Manifold::Vec(0);`	1286	`return Manifold::Vec(0);`
1266		1287
1267	`size_t N_count = N;`	1288	`size_t N_count = N;`
1268	`if(boundary(m, v))`	1289	`if(boundary(m, v))`
1269	`N_count -= 1;`	1290	`N_count -= 1;`
1270		1291
1271	`// sum up the normals of each face surrounding the vertex`	1292	`// sum up the normals of each face surrounding the vertex`
1272	`for(size_t i = 0; i < N_count; ++i){`	1293	`for(size_t i = 0; i < N_count; ++i){`
1273	`Manifold::Vec e0 = one_ring[i];`	1294	`Manifold::Vec e0 = one_ring[i];`
1274	`Manifold::Vec e1 = one_ring[(i+1) % N];`	1295	`Manifold::Vec e1 = one_ring[(i+1) % N];`
Line 1276...	Line 1297...
1276	`Manifold::Vec n_part = normalize(cross(e0, e1));`	1297	`Manifold::Vec n_part = normalize(cross(e0, e1));`
1277	`n += n_part * acos(max(-1.0, min(1.0, dot(e0, e1))));`	1298	`n += n_part * acos(max(-1.0, min(1.0, dot(e0, e1))));`
1278	`}`	1299	`}`
1279		1300
1280	`// normalize and return the normal`	1301	`// normalize and return the normal`
1281	`float sqr_l = sqr_length(n);`	1302	`float sqr_l = sqr_length(n);`
1282	`if(sqr_l > 0.0f) return n / sqrt(sqr_l);`	1303	`if(sqr_l > 0.0f) return n / sqrt(sqr_l);`
1283		1304
1284	`return n;`	1305	`return n;`
1285	`}`	1306	`}`
1286		1307
1287	`bool connected(const Manifold& m, VertexID v0, VertexID v1)`	1308	`bool connected(const Manifold& m, VertexID v0, VertexID v1)`
1288	`{`	1309	`{`
1289	`for(Walker vj = m.walker(v0); !vj.full_circle(); vj = vj.circulate_vertex_cw()){`	1310	`for(Walker vj = m.walker(v0); !vj.full_circle(); vj = vj.circulate_vertex_cw()){`
1290	`if(vj.vertex() == v1)`	1311	`if(vj.vertex() == v1)`
1291	`return true;`	1312	`return true;`
1292	`}`	1313	`}`
1293	`return false;`	1314	`return false;`
1294	`}`	1315	`}`
1295		1316
1296	`int no_edges(const Manifold& m, FaceID f)`	1317	`int no_edges(const Manifold& m, FaceID f)`
1297	`{`	1318	`{`
1298	`// perform full circulation to get valency`	1319	`// perform full circulation to get valency`
1299	`Walker w = m.walker(f);`	1320	`Walker w = m.walker(f);`
1300	`for(; !w.full_circle(); w = w.circulate_face_cw());`	1321	`for(; !w.full_circle(); w = w.circulate_face_cw());`
1301	`return w.no_steps();`	1322	`return w.no_steps();`
1302	`}`	1323	`}`
1303	`Manifold::Vec normal(const Manifold& m, FaceID f)`	1324	`Manifold::Vec normal(const Manifold& m, FaceID f)`
Line 1360...	Line 1381...
1360	`for(; !w.full_circle(); w = w.circulate_face_cw()) p += length(m, w.halfedge());`	1381	`for(; !w.full_circle(); w = w.circulate_face_cw()) p += length(m, w.halfedge());`
1361	`return p;`	1382	`return p;`
1362	`}`	1383	`}`
1363		1384
1364	`bool boundary(const Manifold& m, HalfEdgeID h)`	1385	`bool boundary(const Manifold& m, HalfEdgeID h)`
1365	`{`	1386	`{`
1366	`Walker w = m.walker(h);`	1387	`Walker w = m.walker(h);`
1367	`return w.face() == InvalidFaceID \|\| w.opp().face() == InvalidFaceID;`	1388	`return w.face() == InvalidFaceID \|\| w.opp().face() == InvalidFaceID;`
1368	`}`	1389	`}`
1369		1390
1370	`float length(const Manifold& m, HalfEdgeID h)`	1391	`float length(const Manifold& m, HalfEdgeID h)`
1371	`{`	1392	`{`
1372	`Walker w = m.walker(h);`	1393	`Walker w = m.walker(h);`
1373	`return (m.pos(w.vertex()) - m.pos(w.opp().vertex())).length();`	1394	`return (m.pos(w.vertex()) - m.pos(w.opp().vertex())).length();`
1374	`}`	1395	`}`
1375	`}`	1396	`}`

Subversion Repositories gelsvn

(root)/branches/ctl/hmesh_vector/src/HMesh/Manifold.cpp – Rev 589 → 593