Rev 178 | Rev 595 | 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::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++;
}
}