Subversion Repositories gelsvn

#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++;

	}

}