WebSVN – gelsvn – Diff – /branches/ray-debug/src/HMesh/Manifold.cpp


#include <iostream>
 
#include "Manifold.h"
#include "VertexCirculator.h"
#include "FaceCirculator.h"
 
 
namespace HMesh
{
	using namespace std;
	using namespace CGLA;
 
	void Manifold::remove_unused()
	{
    for(size_t i=0;i<unused_vertices.size(); ++i)
			vertex_db.erase(unused_vertices[i]);
 
    std::vector<VertexIter> vdummy(0);
    unused_vertices = vdummy;
 
    for(size_t i=0;i<unused_faces.size(); ++i)
			face_db.erase(unused_faces[i]);
 
    std::vector<FaceIter> fdummy(0);
    unused_faces = fdummy;
 
    for(size_t i=0;i<unused_halfedges.size(); ++i)
			halfedge_db.erase(unused_halfedges[i]);
 
    std::vector<HalfEdgeIter> hdummy(0);
    unused_halfedges = hdummy;
	}
	
	void Manifold::clear()
	{
		vertex_db.clear();
		face_db.clear();
		halfedge_db.clear();
 
		std::vector<VertexIter> vdummy(0);
		unused_vertices = vdummy;
					
		std::vector<FaceIter> fdummy(0);
		unused_faces = fdummy;
 
		std::vector<HalfEdgeIter> hdummy(0);
		unused_halfedges = hdummy;
	}
 
 
	void Manifold::erase_halfedge(HalfEdgeIter h)
	{
		if(erase_immediately)
			halfedge_db.erase(h);
		else
			{
				unused_halfedges.push_back(h);
				HalfEdge h_dummy;
				(*h) = h_dummy;
			}
	}
 
	void Manifold::erase_vertex(VertexIter v)
	{
		if(erase_immediately)
			vertex_db.erase(v);
		else
			{
				unused_vertices.push_back(v);
				Vertex v_dummy(v->pos);
				(*v) = v_dummy;
			}
	}
 
	void Manifold::erase_face(FaceIter f)
	{
		if(erase_immediately)
			face_db.erase(f);
		else
			{
				unused_faces.push_back(f);
				Face f_dummy;
				(*f) = f_dummy;
			}
	}
 
 
 
 
	void Manifold::get_bbox(Vec3f& pmin, Vec3f& pmax)
	{
    VertexIter vi = vertices_begin();
    pmin = pmax = vi->pos;
    for(++vi;vi != vertices_end(); ++vi)
			{
        pmin = v_min(vi->pos, pmin);
        pmax = v_max(vi->pos, pmax);
			}
	}
 
	void Manifold::get_bsphere(CGLA::Vec3f& c, float& r)
	{
    Vec3f p0,p7;
    get_bbox(p0, p7);
    Vec3f rad = (p7 - p0)/2.0;
    c = p0 + rad;
    r = rad.length();
	}
 
 
	VertexIter Manifold::split_edge(HalfEdgeIter h)
	{
    HalfEdgeIter ho = h->opp;
    VertexIter v  = h->vert;
    VertexIter vo = ho->vert;
    Vec3f np = (v->pos+vo->pos)/2.0f;
 
    VertexIter vn = create_vertex(np);
    vn->he = h;
 
    HalfEdgeIter hn = create_halfedge();
    HalfEdgeIter hno = create_halfedge();
 
    vo->he = hn;
    v->he = ho;
 
    glue(hn,hno);
    link(h->prev, hn);
    link(hn,h);
    hn->vert = vn;
 
    link(hno,ho->next);
    link(ho, hno);
    hno->vert = vo;
    ho->vert = vn;
 
    if(h->face != NULL_FACE_ITER)
			h->face->last = hn;
    if(ho->face != NULL_FACE_ITER)
			ho->face->last = ho;
 
    hn->face = h->face;
    hno->face = ho->face;
 
    check_boundary_consistency(vn);
    check_boundary_consistency(v);
    check_boundary_consistency(vo);
    return vn;
	}
 
 
	void Manifold::remove_face_if_degenerate(HalfEdgeIter h0)
	{
    if(h0->next->next == h0)
			{
        HalfEdgeIter h1 = h0->next;
 
        HalfEdgeIter h0o = h0->opp;
        HalfEdgeIter h1o = h1->opp;
 
        glue(h0o, h1o);
 
        VertexIter v0 = h1->vert;
        VertexIter v1 = h0->vert;
        v0->he = h1o;
        v1->he = h0o;
 
        if(h0->face != NULL_FACE_ITER)
					erase_face(h0->face);
        erase_halfedge(h0);
        erase_halfedge(h1);
 
        check_boundary_consistency(v0);
        check_boundary_consistency(v1);
 
			}
	}
 
	bool Manifold::collapse_precond(HalfEdgeIter h)
	{
    VertexIter v1 = h->opp->vert;
    VertexIter v2 = h->vert;
 
    std::vector<Vertex*> link1;
    VertexCirculator vc1(v1);
    for(;!vc1.end();++vc1)
			link1.push_back(&(*vc1.get_vertex()));
    assert(link1.size()>=2);
 
    std::vector<Vertex*> link2;
    VertexCirculator vc2(v2);
    for(;!vc2.end();++vc2)
			link2.push_back(&(*vc2.get_vertex()));
    assert(link2.size()>=2);
 
    sort(link1.begin(),link1.end());
    sort(link2.begin(),link2.end());
 
    vector<Vertex*> lisect;
    back_insert_iterator<vector<Vertex*> > lii(lisect);
 
    set_intersection(link1.begin(), link1.end(),
                     link2.begin(), link2.end(),
                     lii);
 
 
    // If the adjacent face is a triangle (see 2)
    int k=0;
    if(h->next->next->next == h)
			{
        // VALENCY 4 TEST
        if(valency(h->next->vert)<4)
					return false;
 
        vector<Vertex*>::iterator iter;
        iter = find(lisect.begin(),	lisect.end(),&(*h->next->vert));
        assert(iter != lisect.end());
        lisect.erase(iter);
        ++k;
 
			}
    // If the adjacent face is a triangle (see 2)
    if(h->opp->next->next->next == h->opp)
			{
        // VALENCY 4 TEST
        if(valency(h->opp->next->vert)<4)
					return false;
 
        vector<Vertex*>::iterator iter;
        iter = find(lisect.begin(),	lisect.end(),&(*h->opp->next->vert));
        assert(iter != lisect.end());
        lisect.erase(iter);
        ++k;
 
			}
    if(lisect.size() !=0) // See 3.
			return false;
 
    // TETRAHEDRON TEST
    if(k==2 && (link1.size()+link2.size()==6))
			return false;
 
    // Test that we are not merging holes (see 6)
    if(is_boundary(v1) && is_boundary(v2) &&
			 (h->face != NULL_FACE_ITER) &&
			 (h->opp->face != NULL_FACE_ITER))
			return false;
 
 
    return true;
	}
 
 
	void Manifold::collapse_halfedge(HalfEdgeIter h, bool avg_vertices)
	{
    VertexIter v = h->opp->vert;
    HalfEdgeIter ho = h->opp;
    VertexIter n = h->vert;
 
    if(avg_vertices)
			n->pos = ((v->pos + n->pos) / 2.0f);
 
    HalfEdgeIter hn = h->next;
    HalfEdgeIter hp = h->prev;
    HalfEdgeIter hon = ho->next;
    HalfEdgeIter hop = ho->prev;
 
    VertexCirculator vc(v);
    for(;!vc.end();++vc)
			vc.get_opp_halfedge()->vert = n;
 
    n->he = h->next;
 
    link(hp, hn);
    if(h->face != NULL_FACE_ITER)
			h->face->last = hn;
 
    link(hop, hon);
    if(ho->face != NULL_FACE_ITER)
			ho->face->last = hon;
 
 
 
    erase_vertex(v);
    erase_halfedge(h);
    erase_halfedge(ho);
 
    remove_face_if_degenerate(hn);
    remove_face_if_degenerate(hon);
 
    check_boundary_consistency(n);
	}
 
	bool Manifold::is_valid()
	{
    HalfEdgeIter he0 = halfedges_begin();
    while(he0 != halfedges_end())
			{
        if(he0->prev == NULL_HALFEDGE_ITER)
					{
            cout << "Halfedge lacks previous" << endl;
            return false;
					}
        if(he0->next == NULL_HALFEDGE_ITER)
					{
            cout << "Halfedge lacks next" << endl;
            return false;
					}
        if(he0->opp == NULL_HALFEDGE_ITER)
					{
            cout << "Halfedge lacks opposite" << endl;
            return false;
					}
        if(he0->vert == NULL_VERTEX_ITER)
					{
            cout << "Halfedge lacks vertex" << endl;
            return false;
					}
        ++he0;
			}
 
    VertexIter vi = vertices_begin();
    while(vi != vertices_end())
			{
        std::vector<Vertex*> link;
        VertexCirculator vc(vi);
        int k=0;
        for(;!vc.end();++vc,++k)
					{
            if(vc.get_halfedge() == NULL_HALFEDGE_ITER)
							{
                cout << "Vertex has null outgoing he" << endl;
                return false;
							}
            Vertex* x = &(*vc.get_vertex());
            if(find(link.begin(), link.end(), x) != link.end())
							{
                cout << "Vertex appears two times in one-ring of other vertex" << endl;
                return false;
							}
            link.push_back(x);
            if(k==1e6)
							{
                cout << "infin. loop around vertex" << endl;
                return false;
							}
					}
        if(link.size()==2)
					{
						if(!is_boundary(vi))
							cout << "Warning: A vertex with only two incident edges" << endl;
						else
							cout << "Comment: A boundary vertex with only two incident edges" << endl;
					}
        assert(link.size()>=2);
        ++vi;
			}
 
    HMesh::FaceIter f = faces_begin();
    for(;f != faces_end(); ++f)
			{
        if(no_edges(f)<3)
					{
            cout << "Degenerate face" << endl;
					}
        FaceCirculator fc(f);
        int k=0;
        while(!fc.end())
					{
            if(fc.get_halfedge()->face != f)
							{
                cout << "Inconsistent face" << endl;
                return false;
							}
            if(++k==1e6) cout << "infin. loop around face" << endl;
            ++fc;
					}
			}
    return true;
	}
 
	FaceIter Manifold::split_face(FaceIter f, VertexIter v0, VertexIter v1)
	{
    // Make sure this is not a triangle
    assert(no_edges(f)>3);
 
    // Make sure we are not trying to connect a vertex to itself.
    assert(v0 != v1);
 
    // Find the halfedge emanating from v0 which belongs to the
    // face, we need to split.
    VertexCirculator vc0(v0);
    while(vc0.get_halfedge()->face != f && !vc0.end()) vc0++;
    assert(!vc0.end());
    HalfEdgeIter h0 = vc0.get_halfedge();
    assert(h0->face == f); // Sanity check.
 
    // 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.
    HalfEdgeIter h = h0;
    while(h->vert != v1)
			h = h->next;
 
    // Create a new halfedge ha which connects v1 and v0 closing the first
    // loop. This new halfedge becomes f->last
    assert(h != h0);
    HalfEdgeIter h1 = h->next;
    HalfEdgeIter ha = create_halfedge();
    link(h,ha);
    link(ha, h0);
    ha->face = f;
    ha->vert = v0;
    f->last = ha;
 
    // Create a new face, f2, and set all halfedges in the remaining part of
    // the polygon to point to this face.
    h = h1;
    FaceIter f2 = create_face();
    while(h->vert != v0)
			{
        h->face = f2;
        h = h->next;
			}
    h->face = f2;
    assert(h != h1);
 
    // Create a new halfedge hb to connect v0 and v1. this new halfedge
    // becomes f2->last
    HalfEdgeIter hb = create_halfedge();
    link(h,hb);
    link(hb, h1);
    hb->face = f2;
    hb->vert = v1;
    f2->last = hb;
 
    // Complete the operation by gluing the two new halfedges.
    glue(ha, hb);
 
    // Assert that the pointers are sane :-)
    assert(h1->prev->opp->next == h0);
    assert(h0->prev->opp->next == h1);
    assert(hb->next->face == f2);
    assert(hb->next->next->face == f2);
    assert(hb->face == f2);
 
    // Return the newly created face
    return f2;
	}
 
	void Manifold::triangulate(FaceIter f)
	{
    // Assert sanity of pointers
    assert(f->last->next->next != f->last);
    assert(f->last->next != f->last);
    assert(--(++f) == f);
    // As long as f is not a triangle.
    while(f->last->next->next->next != f->last)
			{
        assert(no_edges(f) != 3);
        // Call split face to split f into a triangle
        // from the first three vertices and a polygon
        // containing the rest of the vertices. In the
        // next iteration, f becomes this polygon.
 
        assert(f->last->next->next != f->last);
        VertexIter v0 = f->last->vert;
        VertexIter v1 = f->last->next->next->vert;
        assert(v0 != v1);
        f = split_face(f, v0, v1);
			}
	}
 
	bool Manifold::merge_faces(FaceIter f1, HalfEdgeIter h)
	{
    assert(h->face == f1);
 
    HalfEdgeIter ho = h->opp;
    FaceIter f2 = ho->face;
    HalfEdgeIter hn = h->next;
    HalfEdgeIter hon = ho->next;
 
    if(hn->vert == hon->vert) return false;
 
    HalfEdgeIter hp = h->prev;
    HalfEdgeIter hop = ho->prev;
    VertexIter v  = h->vert;
    VertexIter vo = ho->vert;
 
    link(hop, hn);
    v->he = hn;
 
    link(hp, hon);
    vo->he = hon;
 
    f1->last = hn;
    HalfEdgeIter hx = hon;
    assert(hx->face == f2);
    while(hx->face != f1)
			{
        hx->face = f1;
        hx = hx->next;
			}
 
    check_boundary_consistency(v);
    check_boundary_consistency(vo);
 
    erase_halfedge(h);
    erase_halfedge(ho);
    erase_face(f2);
 
    return true;
	}
 
 
	VertexIter Manifold::safe_triangulate(FaceIter f)
	{
    Vec3f p(0.0f);
    FaceCirculator fc(f);
    for(;!fc.end(); ++fc)
			p += fc.get_vertex()->pos;
    int n = fc.no_steps();
    p /= n;
    VertexIter v = create_vertex(p);
    face_insert_point(f,v);
    return v;
	}
 
 
	void Manifold::face_insert_point(FaceIter f, VertexIter v)
	{
    vector<HalfEdgeIter> eout;
    vector<HalfEdgeIter> ein;
 
    HalfEdgeIter hlast = f->last;
    HalfEdgeIter h = hlast;
 
    do
			{
        HalfEdgeIter hn = h->next;
 
        HalfEdgeIter o = create_halfedge();
        HalfEdgeIter i = create_halfedge();
 
        FaceIter fn = create_face();
        i->face = fn;
        i->vert = v;
        o->face = fn;
        o->vert = h->opp->vert;
        h->face = fn;
        fn->last = o;
 
        link(i,o);
        link(o,h);
        link(h,i);
 
        eout.push_back(o);
        ein.push_back(i);
 
        h = hn;
			}
    while(h != hlast);
 
    int N = eout.size();
    for(int i=0;i<N;++i)
			glue(ein[i],eout[(i+1)%N]);
 
    v->he = eout[0];
    erase_face(f);
	}
 
 
	bool Manifold::flip(HalfEdgeIter h1)
	{
    FaceIter f1 = h1->face;
    HalfEdgeIter h2 = h1->opp;
    FaceIter f2 = h2->face;
 
    if(f1 == NULL_FACE_ITER || f2 == NULL_FACE_ITER)
			return false;
 
    // We can only flip an edge if both incident polygons
    // are triangles. Otherwise, this operation makes no sense.
    if(no_edges(f1) != 3)
			return false;
    if(no_edges(f2) !=3)
			return false;
 
    // If the valency of either vertex incident on the edge
    // being flipped is three, we cannot perform this operation.
    // That is because the vertex would then have valency two
    // after the operation which means it would be degenerate.
    VertexIter va = h1->vert;
    VertexIter vb = h2->vert;
    int vala = valency(va);
    int valb = valency(vb);
    if((vala <= 3 && !is_boundary(va)) ||
			 (valb <= 3 && !is_boundary(vb)))
			return false;
 
    // If the two vertices being connected by the flip are already
    // connected, the mesh would become degenerate, so we disallow
    // the operation.
    VertexIter vc = h1->next->vert;
    VertexIter vd = h2->next->vert;
    if(is_connected(vc,vd))
			return false;
 
    HalfEdgeIter ha = h1->next;
    HalfEdgeIter hb = h1->prev;
    HalfEdgeIter hc = h2->next;
    HalfEdgeIter hd = h2->prev;
 
    hd->face = f1;
    hb->face = f2;
    f1->last = h1;
    f2->last = h2;
 
    link(ha,h1);
    link(h1,hd);
    link(hd,ha);
 
    link(hc,h2);
    link(h2,hb);
    link(hb,hc);
 
    h1->vert = vd;
    h2->vert = vc;
 
    va->he = ha;
    vb->he = hc;
 
    check_boundary_consistency(va);
    check_boundary_consistency(vb);
    return true;
	}
 
	/** Give each vertex a unique id corresponding to its iterator
			position */
	void Manifold::enumerate_vertices()
	{
    int i=0;
    for(VertexIter vi=vertices_begin(); vi != vertices_end(); ++vi)
			vi->touched = i++;
	}
 
	/** Give each halfedge a unique id corresponding to its iterator
			position */
	void Manifold::enumerate_halfedges()
	{
    int i=0;
    for(HalfEdgeIter h=halfedges_begin(); h != halfedges_end(); ++h)
			h->touched = i++;
	}
 
	/** Give each face a unique id corresponding to its iterator
			position */
	void Manifold::enumerate_faces()
	{
    int i=0;
    for(FaceIter f=faces_begin(); f != faces_end(); ++f)
			f->touched = i++;
	}
 
 
}
 
 

Rev 178	Rev 307
1	`#include <iostream>`	1	`#include <iostream>`
2		2
3	`#include "Manifold.h"`	3	`#include "Manifold.h"`
4	`#include "VertexCirculator.h"`	4	`#include "VertexCirculator.h"`
5	`#include "FaceCirculator.h"`	5	`#include "FaceCirculator.h"`
6		6
7		7
8	`namespace HMesh`	8	`namespace HMesh`
9	`{`	9	`{`
10	`using namespace std;`	10	`using namespace std;`
11	`using namespace CGLA;`	11	`using namespace CGLA;`
12		12
13	`void Manifold::remove_unused()`	13	`void Manifold::remove_unused()`
14	`{`	14	`{`
15	`for(size_t i=0;i<unused_vertices.size(); ++i)`	15	`for(size_t i=0;i<unused_vertices.size(); ++i)`
16	`vertex_db.erase(unused_vertices[i]);`	16	`vertex_db.erase(unused_vertices[i]);`
17		17
18	`std::vector<VertexIter> vdummy(0);`	18	`std::vector<VertexIter> vdummy(0);`
19	`unused_vertices = vdummy;`	19	`unused_vertices = vdummy;`
20		20
21	`for(size_t i=0;i<unused_faces.size(); ++i)`	21	`for(size_t i=0;i<unused_faces.size(); ++i)`
22	`face_db.erase(unused_faces[i]);`	22	`face_db.erase(unused_faces[i]);`
23		23
24	`std::vector<FaceIter> fdummy(0);`	24	`std::vector<FaceIter> fdummy(0);`
25	`unused_faces = fdummy;`	25	`unused_faces = fdummy;`
26		26
27	`for(size_t i=0;i<unused_halfedges.size(); ++i)`	27	`for(size_t i=0;i<unused_halfedges.size(); ++i)`
28	`halfedge_db.erase(unused_halfedges[i]);`	28	`halfedge_db.erase(unused_halfedges[i]);`
29		29
30	`std::vector<HalfEdgeIter> hdummy(0);`	30	`std::vector<HalfEdgeIter> hdummy(0);`
31	`unused_halfedges = hdummy;`	31	`unused_halfedges = hdummy;`
32	`}`	32	`}`
33		33
34	`void Manifold::clear()`	34	`void Manifold::clear()`
35	`{`	35	`{`
36	`vertex_db.clear();`	36	`vertex_db.clear();`
37	`face_db.clear();`	37	`face_db.clear();`
38	`halfedge_db.clear();`	38	`halfedge_db.clear();`
39		39
40	`std::vector<VertexIter> vdummy(0);`	40	`std::vector<VertexIter> vdummy(0);`
41	`unused_vertices = vdummy;`	41	`unused_vertices = vdummy;`
42		42
43	`std::vector<FaceIter> fdummy(0);`	43	`std::vector<FaceIter> fdummy(0);`
44	`unused_faces = fdummy;`	44	`unused_faces = fdummy;`
45		45
46	`std::vector<HalfEdgeIter> hdummy(0);`	46	`std::vector<HalfEdgeIter> hdummy(0);`
47	`unused_halfedges = hdummy;`	47	`unused_halfedges = hdummy;`
48	`}`	48	`}`
49		49
50		50
51	`void Manifold::erase_halfedge(HalfEdgeIter h)`	51	`void Manifold::erase_halfedge(HalfEdgeIter h)`
52	`{`	52	`{`
53	`if(erase_immediately)`	53	`if(erase_immediately)`
54	`halfedge_db.erase(h);`	54	`halfedge_db.erase(h);`
55	`else`	55	`else`
56	`{`	56	`{`
57	`unused_halfedges.push_back(h);`	57	`unused_halfedges.push_back(h);`
58	`HalfEdge h_dummy;`	58	`HalfEdge h_dummy;`
59	`(*h) = h_dummy;`	59	`(*h) = h_dummy;`
60	`}`	60	`}`
61	`}`	61	`}`
62		62
63	`void Manifold::erase_vertex(VertexIter v)`	63	`void Manifold::erase_vertex(VertexIter v)`
64	`{`	64	`{`
65	`if(erase_immediately)`	65	`if(erase_immediately)`
66	`vertex_db.erase(v);`	66	`vertex_db.erase(v);`
67	`else`	67	`else`
68	`{`	68	`{`
69	`unused_vertices.push_back(v);`	69	`unused_vertices.push_back(v);`
70	`Vertex v_dummy(v->pos);`	70	`Vertex v_dummy(v->pos);`
71	`(*v) = v_dummy;`	71	`(*v) = v_dummy;`
72	`}`	72	`}`
73	`}`	73	`}`
74		74
75	`void Manifold::erase_face(FaceIter f)`	75	`void Manifold::erase_face(FaceIter f)`
76	`{`	76	`{`
77	`if(erase_immediately)`	77	`if(erase_immediately)`
78	`face_db.erase(f);`	78	`face_db.erase(f);`
79	`else`	79	`else`
80	`{`	80	`{`
81	`unused_faces.push_back(f);`	81	`unused_faces.push_back(f);`
82	`Face f_dummy;`	82	`Face f_dummy;`
83	`(*f) = f_dummy;`	83	`(*f) = f_dummy;`
84	`}`	84	`}`
85	`}`	85	`}`
86		86
87		87
88		88
89		89
90	`void Manifold::get_bbox(Vec3f& pmin, Vec3f& pmax)`	90	`void Manifold::get_bbox(Vec3f& pmin, Vec3f& pmax)`
91	`{`	91	`{`
92	`VertexIter vi = vertices_begin();`	92	`VertexIter vi = vertices_begin();`
93	`pmin = pmax = vi->pos;`	93	`pmin = pmax = vi->pos;`
94	`for(++vi;vi != vertices_end(); ++vi)`	94	`for(++vi;vi != vertices_end(); ++vi)`
95	`{`	95	`{`
96	`pmin = v_min(vi->pos, pmin);`	96	`pmin = v_min(vi->pos, pmin);`
97	`pmax = v_max(vi->pos, pmax);`	97	`pmax = v_max(vi->pos, pmax);`
98	`}`	98	`}`
99	`}`	99	`}`
100		100
101	`void Manifold::get_bsphere(CGLA::Vec3f& c, float& r)`	101	`void Manifold::get_bsphere(CGLA::Vec3f& c, float& r)`
102	`{`	102	`{`
103	`Vec3f p0,p7;`	103	`Vec3f p0,p7;`
104	`get_bbox(p0, p7);`	104	`get_bbox(p0, p7);`
105	`Vec3f rad = (p7 - p0)/2.0;`	105	`Vec3f rad = (p7 - p0)/2.0;`
106	`c = p0 + rad;`	106	`c = p0 + rad;`
107	`r = rad.length();`	107	`r = rad.length();`
108	`}`	108	`}`
109		109
110		110
111	`VertexIter Manifold::split_edge(HalfEdgeIter h)`	111	`VertexIter Manifold::split_edge(HalfEdgeIter h)`
112	`{`	112	`{`
113	`HalfEdgeIter ho = h->opp;`	113	`HalfEdgeIter ho = h->opp;`
114	`VertexIter v = h->vert;`	114	`VertexIter v = h->vert;`
115	`VertexIter vo = ho->vert;`	115	`VertexIter vo = ho->vert;`
116	`Vec3f np = (v->pos+vo->pos)/2.0f;`	116	`Vec3f np = (v->pos+vo->pos)/2.0f;`
117		117
118	`VertexIter vn = create_vertex(np);`	118	`VertexIter vn = create_vertex(np);`
119	`vn->he = h;`	119	`vn->he = h;`
120		120
121	`HalfEdgeIter hn = create_halfedge();`	121	`HalfEdgeIter hn = create_halfedge();`
122	`HalfEdgeIter hno = create_halfedge();`	122	`HalfEdgeIter hno = create_halfedge();`
123		123
124	`vo->he = hn;`	124	`vo->he = hn;`
125	`v->he = ho;`	125	`v->he = ho;`
126		126
127	`glue(hn,hno);`	127	`glue(hn,hno);`
128	`link(h->prev, hn);`	128	`link(h->prev, hn);`
129	`link(hn,h);`	129	`link(hn,h);`
130	`hn->vert = vn;`	130	`hn->vert = vn;`
131		131
132	`link(hno,ho->next);`	132	`link(hno,ho->next);`
133	`link(ho, hno);`	133	`link(ho, hno);`
134	`hno->vert = vo;`	134	`hno->vert = vo;`
135	`ho->vert = vn;`	135	`ho->vert = vn;`
136		136
137	`if(h->face != NULL_FACE_ITER)`	137	`if(h->face != NULL_FACE_ITER)`
138	`h->face->last = hn;`	138	`h->face->last = hn;`
139	`if(ho->face != NULL_FACE_ITER)`	139	`if(ho->face != NULL_FACE_ITER)`
140	`ho->face->last = ho;`	140	`ho->face->last = ho;`
141		141
142	`hn->face = h->face;`	142	`hn->face = h->face;`
143	`hno->face = ho->face;`	143	`hno->face = ho->face;`
144		144
145	`check_boundary_consistency(vn);`	145	`check_boundary_consistency(vn);`
146	`check_boundary_consistency(v);`	146	`check_boundary_consistency(v);`
147	`check_boundary_consistency(vo);`	147	`check_boundary_consistency(vo);`
148	`return vn;`	148	`return vn;`
149	`}`	149	`}`
150		150
151		151
152	`void Manifold::remove_face_if_degenerate(HalfEdgeIter h0)`	152	`void Manifold::remove_face_if_degenerate(HalfEdgeIter h0)`
153	`{`	153	`{`
154	`if(h0->next->next == h0)`	154	`if(h0->next->next == h0)`
155	`{`	155	`{`
156	`HalfEdgeIter h1 = h0->next;`	156	`HalfEdgeIter h1 = h0->next;`
157		157
158	`HalfEdgeIter h0o = h0->opp;`	158	`HalfEdgeIter h0o = h0->opp;`
159	`HalfEdgeIter h1o = h1->opp;`	159	`HalfEdgeIter h1o = h1->opp;`
160		160
161	`glue(h0o, h1o);`	161	`glue(h0o, h1o);`
162		162
163	`VertexIter v0 = h1->vert;`	163	`VertexIter v0 = h1->vert;`
164	`VertexIter v1 = h0->vert;`	164	`VertexIter v1 = h0->vert;`
165	`v0->he = h1o;`	165	`v0->he = h1o;`
166	`v1->he = h0o;`	166	`v1->he = h0o;`
167		167
168	`if(h0->face != NULL_FACE_ITER)`	168	`if(h0->face != NULL_FACE_ITER)`
169	`erase_face(h0->face);`	169	`erase_face(h0->face);`
170	`erase_halfedge(h0);`	170	`erase_halfedge(h0);`
171	`erase_halfedge(h1);`	171	`erase_halfedge(h1);`
172		172
173	`check_boundary_consistency(v0);`	173	`check_boundary_consistency(v0);`
174	`check_boundary_consistency(v1);`	174	`check_boundary_consistency(v1);`
175		175
176	`}`	176	`}`
177	`}`	177	`}`
178		178
179	`bool Manifold::collapse_precond(HalfEdgeIter h)`	179	`bool Manifold::collapse_precond(HalfEdgeIter h)`
180	`{`	180	`{`
181	`VertexIter v1 = h->opp->vert;`	181	`VertexIter v1 = h->opp->vert;`
182	`VertexIter v2 = h->vert;`	182	`VertexIter v2 = h->vert;`
183		183
184	`std::vector<Vertex*> link1;`	184	`std::vector<Vertex*> link1;`
185	`VertexCirculator vc1(v1);`	185	`VertexCirculator vc1(v1);`
186	`for(;!vc1.end();++vc1)`	186	`for(;!vc1.end();++vc1)`
187	`link1.push_back(&(*vc1.get_vertex()));`	187	`link1.push_back(&(*vc1.get_vertex()));`
188	`assert(link1.size()>=2);`	188	`assert(link1.size()>=2);`
189		189
190	`std::vector<Vertex*> link2;`	190	`std::vector<Vertex*> link2;`
191	`VertexCirculator vc2(v2);`	191	`VertexCirculator vc2(v2);`
192	`for(;!vc2.end();++vc2)`	192	`for(;!vc2.end();++vc2)`
193	`link2.push_back(&(*vc2.get_vertex()));`	193	`link2.push_back(&(*vc2.get_vertex()));`
194	`assert(link2.size()>=2);`	194	`assert(link2.size()>=2);`
195		195
196	`sort(link1.begin(),link1.end());`	196	`sort(link1.begin(),link1.end());`
197	`sort(link2.begin(),link2.end());`	197	`sort(link2.begin(),link2.end());`
198		198
199	`vector<Vertex*> lisect;`	199	`vector<Vertex*> lisect;`
200	`back_insert_iterator<vector<Vertex*> > lii(lisect);`	200	`back_insert_iterator<vector<Vertex*> > lii(lisect);`
201		201
202	`set_intersection(link1.begin(), link1.end(),`	202	`set_intersection(link1.begin(), link1.end(),`
203	`link2.begin(), link2.end(),`	203	`link2.begin(), link2.end(),`
204	`lii);`	204	`lii);`
205		205
206		206
207	`// If the adjacent face is a triangle (see 2)`	207	`// If the adjacent face is a triangle (see 2)`
208	`int k=0;`	208	`int k=0;`
209	`if(h->next->next->next == h)`	209	`if(h->next->next->next == h)`
210	`{`	210	`{`
211	`// VALENCY 4 TEST`	211	`// VALENCY 4 TEST`
212	`if(valency(h->next->vert)<4)`	212	`if(valency(h->next->vert)<4)`
213	`return false;`	213	`return false;`
214		214
215	`vector<Vertex*>::iterator iter;`	215	`vector<Vertex*>::iterator iter;`
216	`iter = find(lisect.begin(), lisect.end(),&(*h->next->vert));`	216	`iter = find(lisect.begin(), lisect.end(),&(*h->next->vert));`
217	`assert(iter != lisect.end());`	217	`assert(iter != lisect.end());`
218	`lisect.erase(iter);`	218	`lisect.erase(iter);`
219	`++k;`	219	`++k;`
220		220
221	`}`	221	`}`
222	`// If the adjacent face is a triangle (see 2)`	222	`// If the adjacent face is a triangle (see 2)`
223	`if(h->opp->next->next->next == h->opp)`	223	`if(h->opp->next->next->next == h->opp)`
224	`{`	224	`{`
225	`// VALENCY 4 TEST`	225	`// VALENCY 4 TEST`
226	`if(valency(h->opp->next->vert)<4)`	226	`if(valency(h->opp->next->vert)<4)`
227	`return false;`	227	`return false;`
228		228
229	`vector<Vertex*>::iterator iter;`	229	`vector<Vertex*>::iterator iter;`
230	`iter = find(lisect.begin(), lisect.end(),&(*h->opp->next->vert));`	230	`iter = find(lisect.begin(), lisect.end(),&(*h->opp->next->vert));`
231	`assert(iter != lisect.end());`	231	`assert(iter != lisect.end());`
232	`lisect.erase(iter);`	232	`lisect.erase(iter);`
233	`++k;`	233	`++k;`
234		234
235	`}`	235	`}`
236	`if(lisect.size() !=0) // See 3.`	236	`if(lisect.size() !=0) // See 3.`
237	`return false;`	237	`return false;`
238		238
239	`// TETRAHEDRON TEST`	239	`// TETRAHEDRON TEST`
240	`if(k==2 && (link1.size()+link2.size()==6))`	240	`if(k==2 && (link1.size()+link2.size()==6))`
241	`return false;`	241	`return false;`
242		242
243	`// Test that we are not merging holes (see 6)`	243	`// Test that we are not merging holes (see 6)`
244	`if(is_boundary(v1) && is_boundary(v2) &&`	244	`if(is_boundary(v1) && is_boundary(v2) &&`
245	`(h->face != NULL_FACE_ITER) &&`	245	`(h->face != NULL_FACE_ITER) &&`
246	`(h->opp->face != NULL_FACE_ITER))`	246	`(h->opp->face != NULL_FACE_ITER))`
247	`return false;`	247	`return false;`
248		248
249		249
250	`return true;`	250	`return true;`
251	`}`	251	`}`
252		252
253		253
254	`void Manifold::collapse_halfedge(HalfEdgeIter h, bool avg_vertices)`	254	`void Manifold::collapse_halfedge(HalfEdgeIter h, bool avg_vertices)`
255	`{`	255	`{`
256	`VertexIter v = h->opp->vert;`	256	`VertexIter v = h->opp->vert;`
257	`HalfEdgeIter ho = h->opp;`	257	`HalfEdgeIter ho = h->opp;`
258	`VertexIter n = h->vert;`	258	`VertexIter n = h->vert;`
259		259
260	`if(avg_vertices)`	260	`if(avg_vertices)`
261	`n->pos = ((v->pos + n->pos) / 2.0f);`	261	`n->pos = ((v->pos + n->pos) / 2.0f);`
262		262
263	`HalfEdgeIter hn = h->next;`	263	`HalfEdgeIter hn = h->next;`
264	`HalfEdgeIter hp = h->prev;`	264	`HalfEdgeIter hp = h->prev;`
265	`HalfEdgeIter hon = ho->next;`	265	`HalfEdgeIter hon = ho->next;`
266	`HalfEdgeIter hop = ho->prev;`	266	`HalfEdgeIter hop = ho->prev;`
267		267
268	`VertexCirculator vc(v);`	268	`VertexCirculator vc(v);`
269	`for(;!vc.end();++vc)`	269	`for(;!vc.end();++vc)`
270	`vc.get_opp_halfedge()->vert = n;`	270	`vc.get_opp_halfedge()->vert = n;`
271		271
272	`n->he = h->next;`	272	`n->he = h->next;`
273		273
274	`link(hp, hn);`	274	`link(hp, hn);`
275	`if(h->face != NULL_FACE_ITER)`	275	`if(h->face != NULL_FACE_ITER)`
276	`h->face->last = hn;`	276	`h->face->last = hn;`
277		277
278	`link(hop, hon);`	278	`link(hop, hon);`
279	`if(ho->face != NULL_FACE_ITER)`	279	`if(ho->face != NULL_FACE_ITER)`
280	`ho->face->last = hon;`	280	`ho->face->last = hon;`
281		281
282		282
283		283
284	`erase_vertex(v);`	284	`erase_vertex(v);`
285	`erase_halfedge(h);`	285	`erase_halfedge(h);`
286	`erase_halfedge(ho);`	286	`erase_halfedge(ho);`
287		287
288	`remove_face_if_degenerate(hn);`	288	`remove_face_if_degenerate(hn);`
289	`remove_face_if_degenerate(hon);`	289	`remove_face_if_degenerate(hon);`
290		290
291	`check_boundary_consistency(n);`	291	`check_boundary_consistency(n);`
292	`}`	292	`}`
293		293
294	`bool Manifold::is_valid()`	294	`bool Manifold::is_valid()`
295	`{`	295	`{`
296	`HalfEdgeIter he0 = halfedges_begin();`	296	`HalfEdgeIter he0 = halfedges_begin();`
297	`while(he0 != halfedges_end())`	297	`while(he0 != halfedges_end())`
298	`{`	298	`{`
299	`if(he0->prev == NULL_HALFEDGE_ITER)`	299	`if(he0->prev == NULL_HALFEDGE_ITER)`
300	`{`	300	`{`
301	`cout << "Halfedge lacks previous" << endl;`	301	`cout << "Halfedge lacks previous" << endl;`
302	`return false;`	302	`return false;`
303	`}`	303	`}`
304	`if(he0->next == NULL_HALFEDGE_ITER)`	304	`if(he0->next == NULL_HALFEDGE_ITER)`
305	`{`	305	`{`
306	`cout << "Halfedge lacks next" << endl;`	306	`cout << "Halfedge lacks next" << endl;`
307	`return false;`	307	`return false;`
308	`}`	308	`}`
309	`if(he0->opp == NULL_HALFEDGE_ITER)`	309	`if(he0->opp == NULL_HALFEDGE_ITER)`
310	`{`	310	`{`
311	`cout << "Halfedge lacks opposite" << endl;`	311	`cout << "Halfedge lacks opposite" << endl;`
312	`return false;`	312	`return false;`
313	`}`	313	`}`
314	`if(he0->vert == NULL_VERTEX_ITER)`	314	`if(he0->vert == NULL_VERTEX_ITER)`
315	`{`	315	`{`
316	`cout << "Halfedge lacks vertex" << endl;`	316	`cout << "Halfedge lacks vertex" << endl;`
317	`return false;`	317	`return false;`
318	`}`	318	`}`
319	`++he0;`	319	`++he0;`
320	`}`	320	`}`
321		321
322	`VertexIter vi = vertices_begin();`	322	`VertexIter vi = vertices_begin();`
323	`while(vi != vertices_end())`	323	`while(vi != vertices_end())`
324	`{`	324	`{`
325	`std::vector<Vertex*> link;`	325	`std::vector<Vertex*> link;`
326	`VertexCirculator vc(vi);`	326	`VertexCirculator vc(vi);`
327	`int k=0;`	327	`int k=0;`
328	`for(;!vc.end();++vc,++k)`	328	`for(;!vc.end();++vc,++k)`
329	`{`	329	`{`
330	`if(vc.get_halfedge() == NULL_HALFEDGE_ITER)`	330	`if(vc.get_halfedge() == NULL_HALFEDGE_ITER)`
331	`{`	331	`{`
332	`cout << "Vertex has null outgoing he" << endl;`	332	`cout << "Vertex has null outgoing he" << endl;`
333	`return false;`	333	`return false;`
334	`}`	334	`}`
335	`Vertex* x = &(*vc.get_vertex());`	335	`Vertex* x = &(*vc.get_vertex());`
336	`if(find(link.begin(), link.end(), x) != link.end())`	336	`if(find(link.begin(), link.end(), x) != link.end())`
337	`{`	337	`{`
338	`cout << "Vertex appears two times in one-ring of other vertex" << endl;`	338	`cout << "Vertex appears two times in one-ring of other vertex" << endl;`
339	`return false;`	339	`return false;`
340	`}`	340	`}`
341	`link.push_back(x);`	341	`link.push_back(x);`
342	`if(k==1e6)`	342	`if(k==1e6)`
343	`{`	343	`{`
344	`cout << "infin. loop around vertex" << endl;`	344	`cout << "infin. loop around vertex" << endl;`
345	`return false;`	345	`return false;`
346	`}`	346	`}`
347	`}`	347	`}`
348	`if(link.size()==2)`	348	`if(link.size()==2)`
349	`{`	349	`{`
350	`if(!is_boundary(vi))`	350	`if(!is_boundary(vi))`
351	`cout << "Warning: A vertex with only two incident edges" << endl;`	351	`cout << "Warning: A vertex with only two incident edges" << endl;`
352	`else`	352	`else`
353	`cout << "Comment: A boundary vertex with only two incident edges" << endl;`	353	`cout << "Comment: A boundary vertex with only two incident edges" << endl;`
354	`}`	354	`}`
355	`assert(link.size()>=2);`	355	`assert(link.size()>=2);`
356	`++vi;`	356	`++vi;`
357	`}`	357	`}`
358		358
359	`HMesh::FaceIter f = faces_begin();`	359	`HMesh::FaceIter f = faces_begin();`
360	`for(;f != faces_end(); ++f)`	360	`for(;f != faces_end(); ++f)`
361	`{`	361	`{`
362	`if(no_edges(f)<3)`	362	`if(no_edges(f)<3)`
363	`{`	363	`{`
364	`cout << "Degenerate face" << endl;`	364	`cout << "Degenerate face" << endl;`
365	`}`	365	`}`
366	`FaceCirculator fc(f);`	366	`FaceCirculator fc(f);`
367	`int k=0;`	367	`int k=0;`
368	`while(!fc.end())`	368	`while(!fc.end())`
369	`{`	369	`{`
370	`if(fc.get_halfedge()->face != f)`	370	`if(fc.get_halfedge()->face != f)`
371	`{`	371	`{`
372	`cout << "Inconsistent face" << endl;`	372	`cout << "Inconsistent face" << endl;`
373	`return false;`	373	`return false;`
374	`}`	374	`}`
375	`if(++k==1e6) cout << "infin. loop around face" << endl;`	375	`if(++k==1e6) cout << "infin. loop around face" << endl;`
376	`++fc;`	376	`++fc;`
377	`}`	377	`}`
378	`}`	378	`}`
379	`return true;`	379	`return true;`
380	`}`	380	`}`
381		381
382	`FaceIter Manifold::split_face(FaceIter f, VertexIter v0, VertexIter v1)`	382	`FaceIter Manifold::split_face(FaceIter f, VertexIter v0, VertexIter v1)`
383	`{`	383	`{`
384	`// Make sure this is not a triangle`	384	`// Make sure this is not a triangle`
385	`assert(no_edges(f)>3);`	385	`assert(no_edges(f)>3);`
386		386
387	`// Make sure we are not trying to connect a vertex to itself.`	387	`// Make sure we are not trying to connect a vertex to itself.`
388	`assert(v0 != v1);`	388	`assert(v0 != v1);`
389		389
390	`// Find the halfedge emanating from v0 which belongs to the`	390	`// Find the halfedge emanating from v0 which belongs to the`
391	`// face, we need to split.`	391	`// face, we need to split.`
392	`VertexCirculator vc0(v0);`	392	`VertexCirculator vc0(v0);`
393	`while(vc0.get_halfedge()->face != f && !vc0.end()) vc0++;`	393	`while(vc0.get_halfedge()->face != f && !vc0.end()) vc0++;`
394	`assert(!vc0.end());`	394	`assert(!vc0.end());`
395	`HalfEdgeIter h0 = vc0.get_halfedge();`	395	`HalfEdgeIter h0 = vc0.get_halfedge();`
396	`assert(h0->face == f); // Sanity check.`	396	`assert(h0->face == f); // Sanity check.`
397		397
398	`// The halfedge belonging to f, going out from v0, is denoted h.`	398	`// The halfedge belonging to f, going out from v0, is denoted h.`
399	`// Move along h until we hit v1. Now we have the halfedge which`	399	`// Move along h until we hit v1. Now we have the halfedge which`
400	`// belongs to f and points to v1.`	400	`// belongs to f and points to v1.`
401	`HalfEdgeIter h = h0;`	401	`HalfEdgeIter h = h0;`
402	`while(h->vert != v1)`	402	`while(h->vert != v1)`
403	`h = h->next;`	403	`h = h->next;`
404		404
405	`// Create a new halfedge ha which connects v1 and v0 closing the first`	405	`// Create a new halfedge ha which connects v1 and v0 closing the first`
406	`// loop. This new halfedge becomes f->last`	406	`// loop. This new halfedge becomes f->last`
407	`assert(h != h0);`	407	`assert(h != h0);`
408	`HalfEdgeIter h1 = h->next;`	408	`HalfEdgeIter h1 = h->next;`
409	`HalfEdgeIter ha = create_halfedge();`	409	`HalfEdgeIter ha = create_halfedge();`
410	`link(h,ha);`	410	`link(h,ha);`
411	`link(ha, h0);`	411	`link(ha, h0);`
412	`ha->face = f;`	412	`ha->face = f;`
413	`ha->vert = v0;`	413	`ha->vert = v0;`
414	`f->last = ha;`	414	`f->last = ha;`
415		415
416	`// Create a new face, f2, and set all halfedges in the remaining part of`	416	`// Create a new face, f2, and set all halfedges in the remaining part of`
417	`// the polygon to point to this face.`	417	`// the polygon to point to this face.`
418	`h = h1;`	418	`h = h1;`
419	`FaceIter f2 = create_face();`	419	`FaceIter f2 = create_face();`
420	`while(h->vert != v0)`	420	`while(h->vert != v0)`
421	`{`	421	`{`
422	`h->face = f2;`	422	`h->face = f2;`
423	`h = h->next;`	423	`h = h->next;`
424	`}`	424	`}`
425	`h->face = f2;`	425	`h->face = f2;`
426	`assert(h != h1);`	426	`assert(h != h1);`
427		427
428	`// Create a new halfedge hb to connect v0 and v1. this new halfedge`	428	`// Create a new halfedge hb to connect v0 and v1. this new halfedge`
429	`// becomes f2->last`	429	`// becomes f2->last`
430	`HalfEdgeIter hb = create_halfedge();`	430	`HalfEdgeIter hb = create_halfedge();`
431	`link(h,hb);`	431	`link(h,hb);`
432	`link(hb, h1);`	432	`link(hb, h1);`
433	`hb->face = f2;`	433	`hb->face = f2;`
434	`hb->vert = v1;`	434	`hb->vert = v1;`
435	`f2->last = hb;`	435	`f2->last = hb;`
436		436
437	`// Complete the operation by gluing the two new halfedges.`	437	`// Complete the operation by gluing the two new halfedges.`
438	`glue(ha, hb);`	438	`glue(ha, hb);`
439		439
440	`// Assert that the pointers are sane :-)`	440	`// Assert that the pointers are sane :-)`
441	`assert(h1->prev->opp->next == h0);`	441	`assert(h1->prev->opp->next == h0);`
442	`assert(h0->prev->opp->next == h1);`	442	`assert(h0->prev->opp->next == h1);`
443	`assert(hb->next->face == f2);`	443	`assert(hb->next->face == f2);`
444	`assert(hb->next->next->face == f2);`	444	`assert(hb->next->next->face == f2);`
445	`assert(hb->face == f2);`	445	`assert(hb->face == f2);`
446		446
447	`// Return the newly created face`	447	`// Return the newly created face`
448	`return f2;`	448	`return f2;`
449	`}`	449	`}`
450		450
451	`void Manifold::triangulate(FaceIter f)`	451	`void Manifold::triangulate(FaceIter f)`
452	`{`	452	`{`
453	`// Assert sanity of pointers`	453	`// Assert sanity of pointers`
454	`assert(f->last->next->next != f->last);`	454	`assert(f->last->next->next != f->last);`
455	`assert(f->last->next != f->last);`	455	`assert(f->last->next != f->last);`
456	`assert(--(++f) == f);`	456	`assert(--(++f) == f);`
457	`// As long as f is not a triangle.`	457	`// As long as f is not a triangle.`
458	`while(f->last->next->next->next != f->last)`	458	`while(f->last->next->next->next != f->last)`
459	`{`	459	`{`
460	`assert(no_edges(f) != 3);`	460	`assert(no_edges(f) != 3);`
461	`// Call split face to split f into a triangle`	461	`// Call split face to split f into a triangle`
462	`// from the first three vertices and a polygon`	462	`// from the first three vertices and a polygon`
463	`// containing the rest of the vertices. In the`	463	`// containing the rest of the vertices. In the`
464	`// next iteration, f becomes this polygon.`	464	`// next iteration, f becomes this polygon.`
465		465
466	`assert(f->last->next->next != f->last);`	466	`assert(f->last->next->next != f->last);`
467	`VertexIter v0 = f->last->vert;`	467	`VertexIter v0 = f->last->vert;`
468	`VertexIter v1 = f->last->next->next->vert;`	468	`VertexIter v1 = f->last->next->next->vert;`
469	`assert(v0 != v1);`	469	`assert(v0 != v1);`
470	`f = split_face(f, v0, v1);`	470	`f = split_face(f, v0, v1);`
471	`}`	471	`}`
472	`}`	472	`}`
473		473
474	`bool Manifold::merge_faces(FaceIter f1, HalfEdgeIter h)`	474	`bool Manifold::merge_faces(FaceIter f1, HalfEdgeIter h)`
475	`{`	475	`{`
476	`assert(h->face == f1);`	476	`assert(h->face == f1);`
477		477
478	`HalfEdgeIter ho = h->opp;`	478	`HalfEdgeIter ho = h->opp;`
479	`FaceIter f2 = ho->face;`	479	`FaceIter f2 = ho->face;`
480	`HalfEdgeIter hn = h->next;`	480	`HalfEdgeIter hn = h->next;`
481	`HalfEdgeIter hon = ho->next;`	481	`HalfEdgeIter hon = ho->next;`
482		482
483	`if(hn->vert == hon->vert) return false;`	483	`if(hn->vert == hon->vert) return false;`
484		484
485	`HalfEdgeIter hp = h->prev;`	485	`HalfEdgeIter hp = h->prev;`
486	`HalfEdgeIter hop = ho->prev;`	486	`HalfEdgeIter hop = ho->prev;`
487	`VertexIter v = h->vert;`	487	`VertexIter v = h->vert;`
488	`VertexIter vo = ho->vert;`	488	`VertexIter vo = ho->vert;`
489		489
490	`link(hop, hn);`	490	`link(hop, hn);`
491	`v->he = hn;`	491	`v->he = hn;`
492		492
493	`link(hp, hon);`	493	`link(hp, hon);`
494	`vo->he = hon;`	494	`vo->he = hon;`
495		495
496	`f1->last = hn;`	496	`f1->last = hn;`
497	`HalfEdgeIter hx = hon;`	497	`HalfEdgeIter hx = hon;`
498	`assert(hx->face == f2);`	498	`assert(hx->face == f2);`
499	`while(hx->face != f1)`	499	`while(hx->face != f1)`
500	`{`	500	`{`

Subversion Repositories gelsvn

(root)/branches/ray-debug/src/HMesh/Manifold.cpp – Rev 178 → 307