Rev 39 | Rev 62 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed
#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++;
}
}