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

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

Subversion Repositories gelsvn

(root)/trunk/src/HMesh/Manifold.cpp – Rev 178 → 336