polymesht.cc

penMesh is a generic and efficient data structure for representing and manipulating polygonal meshes

//-----------------------------------------------------------------------------


template <class Kernel_>
void PolyMeshT<Kernel_>::
calc_vertex_normal_correct(VertexHandle _vh, Normal& _n) const
{
  _n[0]=_n[1]=_n[2]=Scalar(0.0);
  ConstVertexIHalfedgeIter cvih_it = cvih_iter(_vh);
  if (!cvih_it)
  {//don't crash on isolated vertices
    return;
  }
  Normal in_he_vec;
  calc_edge_vector(cvih_it, in_he_vec);
  for ( ; cvih_it; ++cvih_it)
  {//calculates the sector normal defined by cvih_it and adds it to _n
    if (is_boundary(cvih_it))
    {
      continue;
    }
    HalfedgeHandle out_heh(next_halfedge_handle(cvih_it));
    Normal out_he_vec;
    calc_edge_vector(out_heh, out_he_vec);
    _n += cross(in_he_vec, out_he_vec);//sector area is taken into account
    in_he_vec = out_he_vec;
    in_he_vec *= -1;//change the orientation
  }
}


//-----------------------------------------------------------------------------


template <class Kernel_>
void PolyMeshT<Kernel_>::
calc_vertex_normal_loop(VertexHandle _vh, Normal& _n) const
{
  static const LoopSchemeMaskDouble& loop_scheme_mask__ =
                  LoopSchemeMaskDoubleSingleton::Instance();

  Normal t_v(0.0,0.0,0.0), t_w(0.0,0.0,0.0);
  unsigned int vh_val = valence(_vh);
  unsigned int i = 0;
  for (ConstVertexOHalfedgeIter cvoh_it = cvoh_iter(_vh); cvoh_it; ++cvoh_it, ++i)
  {
    VertexHandle r1_v(to_vertex_handle(cvoh_it));
    t_v += (Normal)(point(r1_v) * loop_scheme_mask__.tang0_weight(vh_val, i));
    t_w += (Normal)(point(r1_v) * loop_scheme_mask__.tang1_weight(vh_val, i));
  }
  _n = cross(t_w, t_v);//hack: should be cross(t_v, t_w), but then the normals are reversed?
}


//-----------------------------------------------------------------------------


template <class Kernel_>
void PolyMeshT<Kernel_>::
calc_vertex_normal_angle_weighted(VertexHandle _vh, Normal& _n) const
{
  _n[0]=_n[1]=_n[2]=Scalar(0.0);

  ConstVertexVertexIter  v2_it(cvv_iter(_vh));

  if (v2_it)
  {
    ConstVertexVertexIter  v1_it(v2_it); ++v1_it;
    const Point&           p0 = point(_vh);
    Normal                 d1, d2;
    Normal                 n;
    Scalar                 cosine, angle, norm;
    const Scalar           mone(-1.0), one(1.0);
    FaceHandle             fh;

    for (; v2_it; ++v2_it, ++v1_it)
    {
      if ((fh=face_handle(v1_it.current_halfedge_handle())).is_valid())
      {
	const Point& p1 = point(v1_it);
	const Point& p2 = point(v2_it);

	// this casts suck, but OpenSG compatibility requires it
	(d1 = (Normal)p1) -= (Normal)p0;
	(d2 = (Normal)p2) -= (Normal)p0;

	d1.normalize();
	d2.normalize();

	cosine = dot(d1,d2) / sqrt(dot(d1,d1)*dot(d2,d2)); // saves one sqrt
	if      (cosine < mone) cosine = mone; 
	else if (cosine >  one) cosine =  one;
	angle = acos(cosine);

	n = normal(fh);
	n *= angle;
	_n += n;
      }
    }

    norm = _n.length();
    if (norm != 0.0f) _n *= (1.0f/norm);
  }
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
PolyMeshT<Kernel>::
update_vertex_normals(VertexNormalMode _mode)
{
  VertexIter  v_it(vertices_begin()), v_end(vertices_end());
  Normal      n;

  switch (_mode)
  {
    case FAST:
      for (; v_it!=v_end; ++v_it)
      {	calc_vertex_normal_fast(v_it, n); set_normal(v_it.handle(), n); }
      break;

    case CORRECT:
      for (; v_it!=v_end; ++v_it)
      {	calc_vertex_normal_correct(v_it, n); set_normal(v_it.handle(), n); }
      break;

    case LOOP:
      for (; v_it!=v_end; ++v_it)
      {	calc_vertex_normal_loop(v_it, n); set_normal(v_it.handle(), n); }
      break;

    case ANGLE_WEIGHTED:
      for (; v_it!=v_end; ++v_it)
      {	calc_vertex_normal_angle_weighted(v_it, n); set_normal(v_it.handle(), n); }
      break;
  }
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
PolyMeshT<Kernel>::
delete_vertex(VertexHandle _vh, bool _delete_isolated_vertices)
{
  // store incident faces
  std::vector<FaceHandle> face_handles;
  face_handles.reserve(8);
  for (VFIter vf_it(vf_iter(_vh)); vf_it; ++vf_it)
    face_handles.push_back(vf_it.handle());


  // delete collected faces
  typename std::vector<FaceHandle>::iterator
    fh_it(face_handles.begin()),
    fh_end(face_handles.end());

  for (; fh_it!=fh_end; ++fh_it)
    delete_face(*fh_it, _delete_isolated_vertices);

  status(_vh).set_deleted(true);
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
PolyMeshT<Kernel>::
delete_edge(EdgeHandle _eh, bool _delete_isolated_vertices)
{
  FaceHandle fh0(face_handle(halfedge_handle(_eh, 0)));
  FaceHandle fh1(face_handle(halfedge_handle(_eh, 1)));

  if (fh0.is_valid())  delete_face(fh0, _delete_isolated_vertices);
  if (fh1.is_valid())  delete_face(fh1, _delete_isolated_vertices);
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
PolyMeshT<Kernel>::
delete_face(FaceHandle _fh, bool _delete_isolated_vertices)
{
  assert(_fh.is_valid() && !status(_fh).deleted());

  // mark face deleted
  status(_fh).set_deleted(true);


  // this vector will hold all boundary edges of face _fh
  // these edges will be deleted
  std::vector<EdgeHandle> deleted_edges;
  deleted_edges.reserve(3);


  // this vector will hold all vertices of face _fh
  // for updating their outgoing halfedge
  std::vector<VertexHandle>  vhandles;
  vhandles.reserve(3);


  // for all halfedges of face _fh do:
  //   1) invalidate face handle.
  //   2) collect all boundary halfedges, set them deleted
  //   3) store vertex handles
  HalfedgeHandle hh;
  for (FaceHalfedgeIter fh_it(fh_iter(_fh)); fh_it; ++fh_it)
  {
    hh = fh_it.handle();

    set_boundary(hh);//set_face_handle(hh, InvalidFaceHandle);

    if (is_boundary(opposite_halfedge_handle(hh)))
        deleted_edges.push_back(edge_handle(hh));

    vhandles.push_back(to_vertex_handle(hh));
  }


  // delete all collected (half)edges
  // delete isolated vertices (if _delete_isolated_vertices is true)
  if (!deleted_edges.empty())
  {
    typename std::vector<EdgeHandle>::iterator
      del_it(deleted_edges.begin()),
      del_end(deleted_edges.end());

    HalfedgeHandle h0, h1, next0, next1, prev0, prev1;
    VertexHandle   v0, v1;

    for (; del_it!=del_end; ++del_it)
    {
      h0    = halfedge_handle(*del_it, 0);
      v0    = to_vertex_handle(h0);
      next0 = next_halfedge_handle(h0);
      prev0 = prev_halfedge_handle(h0);

      h1    = halfedge_handle(*del_it, 1);
      v1    = to_vertex_handle(h1);
      next1 = next_halfedge_handle(h1);
      prev1 = prev_halfedge_handle(h1);

      // adjust next and prev handles
      set_next_halfedge_handle(prev0, next1);
      set_next_halfedge_handle(prev1, next0);

      // mark edge deleted
      status(*del_it).set_deleted(true);

      // update v0
      if (halfedge_handle(v0) == h1)
      {
        // isolated ?
        if (next0 == h1)
        {
          if (_delete_isolated_vertices)
            status(v0).set_deleted(true);
          set_isolated(v0);
        }
        else set_halfedge_handle(v0, next0);
      }

      // update v1
      if (halfedge_handle(v1) == h0)
      {
        // isolated ?
        if (next1 == h0)
        {
          if (_delete_isolated_vertices)
            status(v1).set_deleted(true);
          set_isolated(v1);
        }
        else  set_halfedge_handle(v1, next1);
      }
    }
  }


  // update outgoing halfedge handles of remaining vertices
  typename std::vector<VertexHandle>::iterator
    v_it(vhandles.begin()),
    v_end(vhandles.end());

  for (; v_it!=v_end; ++v_it)
    adjust_outgoing_halfedge(*v_it);
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
PolyMeshT<Kernel>::
triangulate(FaceHandle _fh)
{
  /*
    Split an arbitrary face into triangles by connecting
    each vertex of fh after its second to vh.

    - fh will remain valid (it will become one of the
      triangles)
    - the halfedge handles of the new triangles will
      point to the old halfedges
  */

  HalfedgeHandle base_heh(halfedge_handle(_fh));
  VertexHandle start_vh = from_vertex_handle(base_heh);
  HalfedgeHandle next_heh(next_halfedge_handle(base_heh));

  while (to_vertex_handle(next_halfedge_handle(next_heh)) != start_vh)
  {
    HalfedgeHandle next_next_heh(next_halfedge_handle(next_heh));

    FaceHandle new_fh = This::new_face();
    set_halfedge_handle(new_fh, base_heh);

    HalfedgeHandle new_heh = new_edge(to_vertex_handle(next_heh), start_vh);

    set_next_halfedge_handle(base_heh, next_heh);
    set_next_halfedge_handle(next_heh, new_heh);
    set_next_halfedge_handle(new_heh, base_heh);

    set_face_handle(base_heh, new_fh);
    set_face_handle(next_heh, new_fh);
    set_face_handle(new_heh,  new_fh);

    base_heh = opposite_halfedge_handle(new_heh);
    next_heh = next_next_heh;
  }
  set_halfedge_handle(_fh, base_heh);  //the last face takes the handle _fh

  set_next_halfedge_handle(base_heh, next_heh);
  set_next_halfedge_handle(next_halfedge_handle(next_heh), base_heh);

  set_face_handle(base_heh, _fh);
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
PolyMeshT<Kernel>::
triangulate()
{
  /* The iterators will stay valid, even though new faces are added,
     because they are now implemented index-based instead of
     pointer-based.
  */
  FaceIter f_it(faces_begin()), f_end(faces_end());
  for (; f_it!=f_end; ++f_it)
    triangulate(f_it);
}


//-----------------------------------------------------------------------------


template <class Kernel>
void
PolyMeshT<Kernel>::split(FaceHandle fh, VertexHandle vh)
{
  /*
    Split an arbitrary face into triangles by connecting
    each vertex of fh to vh.

    - fh will remain valid (it will become one of the
      triangles)
    - the halfedge handles of the new triangles will
      point to the old halfeges
  */

  HalfedgeHandle hend = halfedge_handle(fh);
  HalfedgeHandle hh   = next_halfedge_handle(hend);

  HalfedgeHandle hold = new_edge(to_vertex_handle(hend), vh);

  set_next_halfedge_handle(hend, hold);
  set_face_handle(hold, fh);

  hold = opposite_halfedge_handle(hold);

  while (hh != hend) {

    HalfedgeHandle hnext = next_halfedge_handle(hh);

    FaceHandle fnew = This::new_face();
    set_halfedge_handle(fnew, hh);

    HalfedgeHandle hnew = new_edge(to_vertex_handle(hh), vh);

    set_next_halfedge_handle(hnew, hold);
    set_next_halfedge_handle(hold, hh);
    set_next_halfedge_handle(hh, hnew);

    set_face_handle(hnew, fnew);
    set_face_handle(hold, fnew);
    set_face_handle(hh,   fnew);

    hold = opposite_halfedge_handle(hnew);

    hh = hnext;
  }

  set_next_halfedge_handle(hold, hend);
  set_next_halfedge_handle(next_halfedge_handle(hend), hold);

  set_face_handle(hold, fh);

  set_halfedge_handle(vh, hold);
}


//-----------------------------------------------------------------------------


template <class Kernel>
unsigned int
PolyMeshT<Kernel>::
valence(VertexHandle _vh) const
{
  unsigned int count(0);

  for (ConstVertexVertexIter vv_it=cvv_iter(_vh); vv_it; ++vv_it)
    ++count;

  return count;
}


//-----------------------------------------------------------------------------


template <class Kernel>
unsigned int
PolyMeshT<Kernel>::
valence(FaceHandle _fh) const
{
  unsigned int count(0);

  for (ConstFaceVertexIter fv_it=cfv_iter(_fh); fv_it; ++fv_it)
    ++count;

  return count;
}


//=============================================================================
} // namespace OpenMesh
//=============================================================================