Subversion Repositories gelsvn

#include <iostream>

#include "Manifold.h"

#include "VertexCirculator.h"

#include "FaceCirculator.h"

namespace HMesh

{

	using namespace std;

	using namespace CGLA;

	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(VertexIter v1, HalfEdgeIter h)

	{			

		VertexIter v2 = h->vert;

		std::vector<int> link1;

		VertexCirculator vc1(v1);

		for(;!vc1.end();++vc1)

			link1.push_back(reinterpret_cast<int>(&(*vc1.get_vertex())));

		assert(link1.size()>=2);

		std::vector<int> link2;

		VertexCirculator vc2(v2);

		for(;!vc2.end();++vc2)

			link2.push_back(reinterpret_cast<int>(&(*vc2.get_vertex())));

		assert(link2.size()>=2);

		sort(link1.begin(),link1.end());

		sort(link2.begin(),link2.end());

		vector<int> lisect;

		back_insert_iterator<vector<int> > 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<int>::iterator iter;

			iter = find(lisect.begin(),	lisect.end(),

									reinterpret_cast<int>(&(*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<int>::iterator iter;

			iter = find(lisect.begin(),	lisect.end(),

									reinterpret_cast<int>(&(*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(VertexIter v, HalfEdgeIter h, 

																	 bool avg_vertices)

	{

		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;

		bool neighbour_is_boundary = is_boundary(n);

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

							}

						int x = reinterpret_cast<int>(&(*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)

					{

						cout << "Warning: A 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;

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

		}

}