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->get_pos();

		for(++vi;vi != vertices_end(); ++vi)

			{

				pmin = v_min(vi->get_pos(), pmin);

				pmax = v_max(vi->get_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->get_pos()+vo->get_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;

 		h->face->last = hn;

 		ho->face->last = ho;

		hn->face = h->face;

		hno->face = ho->face;

		vn->check_boundary_consistency();

		v->check_boundary_consistency();

		vo->check_boundary_consistency();

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

				v0->check_boundary_consistency();

				v1->check_boundary_consistency();

			}

	}

	bool Manifold::collapse_precond(VertexIter v1, HalfEdgeIter h)

	{

		/* The goal of this (fiendishly complex) function is to test

			 whether an edge is collapsible. The test is as follows.

			 1. For the two vertices adjacent to the edge, we generate

			 a list of all their neighbouring vertices. We then generate a 

			 list of the vertices that occur in both these lists. That is, 

			 we find all vertices connected by edges to both endpoints

			 of the edge and store these in a list.

			 2. For both faces incident on the edge, check whether they

			 are triangular. If this is the case, the face will be removed,

			 and it is ok that the the third vertex is connected to both 

			 endpoints. Thus the third vertex in such a face is removed

			 from the list generated in 1.

			 3. If the list is now empty, all is well. Otherwise, there

			 would be a vertex in the new mesh with two edges connecting

			 it to the same vertex. Return false.

			 4. TETRAHEDRON TEST:

			 If the valency of both vertices is 

			 three, and the incident faces are triangles, we also disallow

			 the operation. Reason: It introduces a vertex of valency two

			 and if the final two polygons incident on the vertices 

			 that are adjacent to the edge being collapsed are triangles, then

			 the construction will collapse

			 5. VALENCY 4 TEST:

			 If a face adjacent to the edge being collapsed is a triangle,

			 it will disappear, and the valency of the final vertex beloning to

			 this edge will be reduced by one. Hence this valency should be at

			 least 4. A valency three vertex will be reduced to a valency two

			 vertex which is considered illegal.

			 6. PREVENT MERGING HOLES:

			 We do not want to collapse an edge if its end points are boundary

			 vertices, but its two adjacent faces are not NULL faces, because

			 in that case we create a vertex where two holes meet. A non manifold

			 situation.

		*/

		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(v1->is_boundary() && v2->is_boundary() &&

			 (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->set_pos((v->get_pos() + n->get_pos()) / 2.0f);

		HalfEdgeIter hn = h->next;

		HalfEdgeIter hp = h->prev;

		HalfEdgeIter hon = ho->next;

		HalfEdgeIter hop = ho->prev;

		bool neighbour_is_boundary = n->is_boundary();

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

		n->check_boundary_consistency();

	}

	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;

			}

		v->check_boundary_consistency();

		vo->check_boundary_consistency();

 		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()->get_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) || (valb <= 3))

			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;

		va->check_boundary_consistency();

		vb->check_boundary_consistency();

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

		}

}