arraykernelt.hh

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

  // --- vertex connectivity ---

  HalfedgeHandle halfedge_handle(VertexHandle _vh) const {
    return vertex(_vh).halfedge_handle_;
  }

  void set_halfedge_handle(VertexHandle _vh, HalfedgeHandle _heh)
  {
//     assert(is_valid_handle(_heh));
    vertex(_vh).halfedge_handle_ = _heh;
  }

  bool is_isolated(VertexHandle _vh) const
  {
    return !halfedge_handle(_vh).is_valid();
  }

  void set_isolated(VertexHandle _vh)
  {
    vertex(_vh).halfedge_handle_.invalidate();
  }


  // --- halfedge connectivity ---


  VertexHandle to_vertex_handle(HalfedgeHandle _heh) const {
    return halfedge(_heh).vertex_handle_;
  }

  VertexHandle from_vertex_handle(HalfedgeHandle _heh) const {
    return to_vertex_handle(opposite_halfedge_handle(_heh));
  }

  void set_vertex_handle(HalfedgeHandle _heh, VertexHandle _vh)
  {
    assert(is_valid_handle(_vh));
    halfedge(_heh).vertex_handle_ = _vh;
  }


  FaceHandle face_handle(HalfedgeHandle _heh) const {
    return halfedge(_heh).face_handle_;
  }

  void set_face_handle(HalfedgeHandle _heh, FaceHandle _fh)
  {
//     assert(is_valid_handle(_fh));
    halfedge(_heh).face_handle_ = _fh;
  }

  void set_boundary(HalfedgeHandle _heh)
  {
    halfedge(_heh).face_handle_.invalidate();
  }

  /// Is halfedge _heh a boundary halfedge (is its face handle invalid) ?
  bool is_boundary(HalfedgeHandle _heh) const
  {
    return !face_handle(_heh).is_valid();
  }

  HalfedgeHandle next_halfedge_handle(HalfedgeHandle _heh) const {
    return halfedge(_heh).next_halfedge_handle_;
  }

  void set_next_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _nheh)
  {
    assert(is_valid_handle(_nheh));
//     assert(to_vertex_handle(_heh) == from_vertex_handle(_nheh));
    halfedge(_heh).next_halfedge_handle_ = _nheh;
    set_prev_halfedge_handle(_nheh, _heh);
  }


  void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh)
  {
    assert(is_valid_handle(_pheh));
    set_prev_halfedge_handle(_heh, _pheh, HasPrevHalfedge());
  }

  void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh,
        GenProg::True) {
    halfedge(_heh).prev_halfedge_handle_ = _pheh;
  }
  void set_prev_halfedge_handle(HalfedgeHandle _heh, HalfedgeHandle _pheh,
        GenProg::False) {}


  HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh) const {
    return prev_halfedge_handle(_heh, HasPrevHalfedge() );
  }

  HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh,
              GenProg::True) const {
    return halfedge(_heh).prev_halfedge_handle_;
  }

  HalfedgeHandle prev_halfedge_handle(HalfedgeHandle _heh,
              GenProg::False) const
  {
    if (is_boundary(_heh))
    {//iterating around the vertex should be faster than iterating the boundary
      HalfedgeHandle curr_heh(opposite_halfedge_handle(_heh));
      HalfedgeHandle next_heh(This::next_halfedge_handle(curr_heh));
      do
      {
        curr_heh = opposite_halfedge_handle(next_heh);
        next_heh = This::next_halfedge_handle(curr_heh);
      }
      while (next_heh != _heh);
      return curr_heh;
    }
    else
    {
      HalfedgeHandle  heh(_heh);
      HalfedgeHandle  next_heh(This::next_halfedge_handle(heh));
      while (next_heh != _heh) {
        heh = next_heh;
        next_heh = This::next_halfedge_handle(next_heh);
      }
      return heh;
    }
  }


  HalfedgeHandle opposite_halfedge_handle(HalfedgeHandle _heh) const {
    return HalfedgeHandle((_heh.idx() & 1) ? _heh.idx()-1 : _heh.idx()+1);
  }


  HalfedgeHandle ccw_rotated_halfedge_handle(HalfedgeHandle _heh) const {
    return opposite_halfedge_handle(prev_halfedge_handle(_heh));
  }


  HalfedgeHandle cw_rotated_halfedge_handle(HalfedgeHandle _heh) const {
    return next_halfedge_handle(opposite_halfedge_handle(_heh));
  }



  // --- edge connectivity ---


  HalfedgeHandle halfedge_handle(EdgeHandle _eh, unsigned int _i) const {
    assert(_i<=1);
    return HalfedgeHandle((_eh.idx() << 1) + _i);
  }


  EdgeHandle edge_handle(HalfedgeHandle _heh) const {
    return EdgeHandle(_heh.idx() >> 1);
  }



  // --- face connectivity ---


  HalfedgeHandle halfedge_handle(FaceHandle _fh) const {
    return face(_fh).halfedge_handle_;
  }

  void set_halfedge_handle(FaceHandle _fh, HalfedgeHandle _heh)
  {
//     assert(is_valid_handle(_heh));
    face(_fh).halfedge_handle_ = _heh;
  }

private:

  // iterators
  typedef std::vector<Vertex>                         VertexContainer;
  typedef std::vector<Edge>                           EdgeContainer;
  typedef std::vector<Face>                           FaceContainer;
  typedef typename VertexContainer::iterator          KernelVertexIter;
  typedef typename VertexContainer::const_iterator    KernelConstVertexIter;
  typedef typename EdgeContainer::iterator            KernelEdgeIter;
  typedef typename EdgeContainer::const_iterator      KernelConstEdgeIter;
  typedef typename FaceContainer::iterator            KernelFaceIter;
  typedef typename FaceContainer::const_iterator      KernelConstFaceIter;


  KernelVertexIter vertices_begin()             { return vertices_.begin(); }
  KernelConstVertexIter vertices_begin() const  { return vertices_.begin(); }
  KernelVertexIter vertices_end()               { return vertices_.end(); }
  KernelConstVertexIter vertices_end() const    { return vertices_.end(); }

  KernelEdgeIter edges_begin()                  { return edges_.begin(); }
  KernelConstEdgeIter edges_begin() const       { return edges_.begin(); }
  KernelEdgeIter edges_end()                    { return edges_.end(); }
  KernelConstEdgeIter edges_end() const         { return edges_.end(); }

  KernelFaceIter faces_begin()                  { return faces_.begin(); }
  KernelConstFaceIter faces_begin() const       { return faces_.begin(); }
  KernelFaceIter faces_end()                    { return faces_.end(); }
  KernelConstFaceIter faces_end() const         { return faces_.end(); }


private:

  VertexContainer    vertices_;
  EdgeContainer      edges_;
  FaceContainer      faces_;
};


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


template <class AttribKernel, class FinalMeshItems>
void
ArrayKernelT<AttribKernel, FinalMeshItems>::
garbage_collection(bool _v, bool _e, bool _f)
{
  int            i, i0, i1,
                 nV(n_vertices()),
                 nE(n_edges()),
                 nH(2*n_edges()),
                 nF(n_faces());

  std::vector<VertexHandle>    vh_map;
  std::vector<HalfedgeHandle>  hh_map;
  std::vector<FaceHandle>      fh_map;

  // setup handle mapping:
  vh_map.reserve(nV);
  for (i=0; i<nV; ++i) vh_map.push_back(VertexHandle(i));

  hh_map.reserve(nH);
  for (i=0; i<nH; ++i) hh_map.push_back(HalfedgeHandle(i));

  fh_map.reserve(nF);
  for (i=0; i<nF; ++i) fh_map.push_back(FaceHandle(i));


  // remove deleted vertices
  if (_v && n_vertices() > 0)
  {
    i0=0;  i1=nV-1;

    while (1)
    {
      // find 1st deleted and last un-deleted
      while (!AttribKernel::status(VertexHandle(i0)).deleted() && i0 < i1)  ++i0;
      while ( AttribKernel::status(VertexHandle(i1)).deleted() && i0 < i1)  --i1;
      if (i0 >= i1) break;

      // swap
      std::swap(vertices_[i0], vertices_[i1]);
      std::swap(vh_map[i0],  vh_map[i1]);
      AttribKernel::vprops_swap(i0, i1);
    };

    vertices_.resize(AttribKernel::status(VertexHandle(i0)).deleted() ? i0 : i0+1);
    vprops_resize(n_vertices());
  }


  // remove deleted edges
  if (_e && n_edges() > 0)
  {
    i0=0;  i1=nE-1;

    while (1)
    {
      // find 1st deleted and last un-deleted
      while (!AttribKernel::status(EdgeHandle(i0)).deleted() && i0 < i1)  ++i0;
      while ( AttribKernel::status(EdgeHandle(i1)).deleted() && i0 < i1)  --i1;
      if (i0 >= i1) break;

      // swap
      std::swap(edges_[i0], edges_[i1]);
      std::swap(hh_map[2*i0], hh_map[2*i1]);
      std::swap(hh_map[2*i0+1], hh_map[2*i1+1]);
      AttribKernel::eprops_swap(i0, i1);
      AttribKernel::hprops_swap(2*i0,   2*i1);
      AttribKernel::hprops_swap(2*i0+1, 2*i1+1);
    };

    edges_.resize(AttribKernel::status(EdgeHandle(i0)).deleted() ? i0 : i0+1);
    eprops_resize(n_edges());
    hprops_resize(n_halfedges());
  }


  // remove deleted faces
  if (_f && n_faces() > 0)
  {
    i0=0;  i1=nF-1;

    while (1)
    {
      // find 1st deleted and last un-deleted
      while (!AttribKernel::status(FaceHandle(i0)).deleted() && i0 < i1)  ++i0;
      while ( AttribKernel::status(FaceHandle(i1)).deleted() && i0 < i1)  --i1;
      if (i0 >= i1) break;

      // swap
      std::swap(faces_[i0], faces_[i1]);
      std::swap(fh_map[i0], fh_map[i1]);
      AttribKernel::fprops_swap(i0, i1);
    };

    faces_.resize(AttribKernel::status(FaceHandle(i0)).deleted() ? i0 : i0+1);
    fprops_resize(n_faces());
  }


  // update handles of vertices
  if (_e)
  {
    KernelVertexIter v_it(vertices_begin()), v_end(vertices_end());
    VertexHandle     vh;

    for (; v_it!=v_end; ++v_it)
    {
      vh = handle(*v_it);
      if (!AttribKernel::status(vh).deleted() && !is_isolated(vh))
        set_halfedge_handle(vh, hh_map[halfedge_handle(vh).idx()]);
    }
  }

  HalfedgeHandle hh;
  // update handles of halfedges
  for (KernelEdgeIter e_it(edges_begin()); e_it != edges_end(); ++e_it)
  {//in the first pass update the (half)edges vertices
    hh = halfedge_handle(handle(*e_it), 0);
    set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()]);
    hh = halfedge_handle(handle(*e_it), 1);
    set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()]);
  }
  for (KernelEdgeIter e_it(edges_begin()); e_it != edges_end(); ++e_it)
  {//in the second pass update the connectivity of the (half)edges
    hh = halfedge_handle(handle(*e_it), 0);
    set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()]);
    if (!is_boundary(hh))
    {
      set_face_handle(hh, fh_map[face_handle(hh).idx()]);
    }
    hh = halfedge_handle(handle(*e_it), 1);
    set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()]);
    if (!is_boundary(hh))
    {
      set_face_handle(hh, fh_map[face_handle(hh).idx()]);
    }
  }


  // update handles of faces
  if (_e)
  {
    KernelFaceIter  f_it(faces_begin()), f_end(faces_end());
    FaceHandle      fh;

    for (; f_it!=f_end; ++f_it)
    {
      fh = handle(*f_it);
      set_halfedge_handle(fh, hh_map[halfedge_handle(fh).idx()]);
    }
  }

}


//=============================================================================
} // namespace OpenMesh
//=============================================================================
#endif // OPENMESH_ARRAY_KERNEL_HH defined
//=============================================================================