Subversion Repositories gelsvn

#include <iostream>

#include <iterator>

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

	}

}