openmesh - src - trimesh delete and add elements

openmesh 版本 8.1

About

本文主要介紹openmesh的如下接口

• add_vertex
• add_face
• delete_vertex
• delete_edge
• delete_face
• delete_isolated_vertices

入口代碼位于：

\src\OpenMesh\Core\Mesh\PolyMeshT.hh

。涉及到的源代碼如下：

template <class Kernel>
class PolyMeshT : public Kernel
{
  /// Alias for new_vertex(const Point&).
  inline SmartVertexHandle add_vertex(const Point& _p)
  { return new_vertex(_p); }

  /**
   * \brief Adds a new vertex initialized to a custom position.
   *
   * \sa new_vertex(), new_vertex_dirty()
   */
  inline SmartVertexHandle new_vertex(const Point& _p)
  {
    VertexHandle vh(Kernel::new_vertex()); 
    this->set_point(vh, _p);
    return make_smart(vh, this);
  }
  //..............
}

// kernel::new_vertex
class OPENMESHDLLEXPORT ArrayKernel : public BaseKernel, public ArrayItems
{
  inline VertexHandle new_vertex()
  {
    vertices_.push_back(Vertex());
    vprops_resize(n_vertices());//TODO:should it be push_back()?

    return handle(vertices_.back());
  }
  // --- handle -> item ---
  VertexHandle handle(const Vertex& _v) const
  {
     return VertexHandle( int( &_v - &vertices_.front()));
  }
}

// AttribKernelT
// 頂點的位置，作為頂點的屬性進行管理
template <class MeshItems, class Connectivity>
class AttribKernelT : public Connectivity
{
  void set_point(VertexHandle _vh, const Point& _p)
  { this->property(points_, _vh) = _p; }
}
           

從上面中的代碼知，add_vertex的過程，就是建立了Vertex，然後建立關聯的VertexHandle，并将頂點的位置記錄到頂點property中。

src\OpenMesh\Core\Mesh\TriConnectivity.cc

SmartFaceHandle
TriConnectivity::add_face(const VertexHandle* _vertex_handles, size_t _vhs_size)
{
  // need at least 3 vertices
  if (_vhs_size < 3) return make_smart(InvalidFaceHandle, this);

  /// face is triangle -> ok
  if (_vhs_size == 3)
    return PolyConnectivity::add_face(_vertex_handles, _vhs_size);

  /// face is not a triangle -> triangulate
  else
  {
    //omlog() << "triangulating " << _vhs_size << "_gon\n";

    VertexHandle vhandles[3];
    vhandles[0] = _vertex_handles[0];

    FaceHandle fh;
    unsigned int i(1);
    --_vhs_size;

    while (i < _vhs_size)
    {
      vhandles[1] = _vertex_handles[i];
      vhandles[2] = _vertex_handles[++i];
      fh = PolyConnectivity::add_face(vhandles, 3);
    }

    return make_smart(fh, this);
  }
}
           

從上面的代碼可知，對于TriMesh，如果超過三個頂點，那麼會進行三角化的過程，這個三角化的過程是，将第一個頂點作為所有三角形的公共點，接下來數組中的相鄰兩個點作為每個三角形的另外兩個頂點。圖示如下：

進一步檢視

PolyConnectivity::add_face(_vertex_handles, _vhs_size);

，完整的代碼如下（TODO詳細剖析下面的代碼）：

SmartFaceHandle
PolyConnectivity::add_face(const VertexHandle* _vertex_handles, size_t _vhs_size)
{
  VertexHandle                   vh;
  size_t                         i, ii, n(_vhs_size);
  HalfedgeHandle                 inner_next, inner_prev,
                                 outer_next, outer_prev,
                                 boundary_next, boundary_prev,
                                 patch_start, patch_end;


  // Check sufficient working storage available
  if (edgeData_.size() < n)
  {
    edgeData_.resize(n);     // 資料類型為：std::vector<AddFaceEdgeInfo>；
                             // struct AddFaceEdgeInfo { HalfedgeHandle halfedge_handle; bool is_new; bool needs_adjust; }
    next_cache_.resize(6*n); //資料類型為：std::vector<std::pair<HalfedgeHandle, HalfedgeHandle> > 
                             // for set_next_halfedge and vertex' set_halfedge
  }

  size_t next_cache_count = 0;

  // don't allow degenerated faces
  assert (n > 2);

  // test for topological errors
  for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
  {
    // 需要添加三角形的頂點必須是位于目前拓撲結構的邊界
    if ( !is_boundary(_vertex_handles[i]) )
    {
      omerr() << "PolyMeshT::add_face: complex vertex\n";
      return make_smart(InvalidFaceHandle, this);
    }

    // Initialise edge attributes
    // 查找是否存在點i和點ii構成的半邊
    edgeData_[i].halfedge_handle = find_halfedge(_vertex_handles[i],
                                                 _vertex_handles[ii]);
    edgeData_[i].is_new = !edgeData_[i].halfedge_handle.is_valid();
    edgeData_[i].needs_adjust = false;

    // 如果存在這個半邊，并且該半邊不是邊界，那麼添加的為重複半邊，直接return
    if (!edgeData_[i].is_new && !is_boundary(edgeData_[i].halfedge_handle))
    {
      omerr() << "PolyMeshT::add_face: complex edge\n";
      return make_smart(InvalidFaceHandle, this);
    }
  }

  // re-link patches if necessary
  for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
  {
    // 如果存在點i點ii構成的半邊i-to-ii，和點ii和點ii+1建構的半邊，ii-to-ii+1
    if (!edgeData_[i].is_new && !edgeData_[ii].is_new)
    {
      inner_prev = edgeData_[i].halfedge_handle;
      inner_next = edgeData_[ii].halfedge_handle;


      // 如果i-to-ii的下一個半邊不是ii-to-ii+1，那麼需要修正拓撲結構關系
      // TODO：需要了解下出現此種情況的具體場景是什麼
      if (next_halfedge_handle(inner_prev) != inner_next)
      {
        // here comes the ugly part... we have to relink a whole patch

        // search a free gap
        // free gap will be between boundary_prev and boundary_next
        outer_prev = opposite_halfedge_handle(inner_next);
        outer_next = opposite_halfedge_handle(inner_prev);
        boundary_prev = outer_prev;
        do
          boundary_prev =
            opposite_halfedge_handle(next_halfedge_handle(boundary_prev));
        while (!is_boundary(boundary_prev));
        boundary_next = next_halfedge_handle(boundary_prev);

        // ok ?
        if (boundary_prev == inner_prev)
        {
          omerr() << "PolyMeshT::add_face: patch re-linking failed\n";
          return make_smart(InvalidFaceHandle, this);
        }

        assert(is_boundary(boundary_prev));
        assert(is_boundary(boundary_next));

        // other halfedges' handles
        patch_start = next_halfedge_handle(inner_prev);
        patch_end   = prev_halfedge_handle(inner_next);

        assert(boundary_prev.is_valid());
        assert(patch_start.is_valid());
        assert(patch_end.is_valid());
        assert(boundary_next.is_valid());
        assert(inner_prev.is_valid());
        assert(inner_next.is_valid());

        // relink
        next_cache_[next_cache_count++] = std::make_pair(boundary_prev, patch_start);
        next_cache_[next_cache_count++] = std::make_pair(patch_end, boundary_next);
        next_cache_[next_cache_count++] = std::make_pair(inner_prev, inner_next);
      }
    }
  }

  // create missing edges
  for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
    if (edgeData_[i].is_new)
      edgeData_[i].halfedge_handle = new_edge(_vertex_handles[i], _vertex_handles[ii]);

  // create the face
  FaceHandle fh(new_face());
  set_halfedge_handle(fh, edgeData_[n-1].halfedge_handle);

  // setup halfedges
  for (i=0, ii=1; i<n; ++i, ++ii, ii%=n)
  {
    vh         = _vertex_handles[ii];

    inner_prev = edgeData_[i].halfedge_handle;
    inner_next = edgeData_[ii].halfedge_handle;
    assert(inner_prev.is_valid());
    assert(inner_next.is_valid());

    size_t id = 0;
    if (edgeData_[i].is_new)  id |= 1;
    if (edgeData_[ii].is_new) id |= 2;


    if (id)
    {
      outer_prev = opposite_halfedge_handle(inner_next);
      outer_next = opposite_halfedge_handle(inner_prev);
      assert(outer_prev.is_valid());
      assert(outer_next.is_valid());

      // set outer links
      switch (id)
      {
        case 1: // prev is new, next is old
          boundary_prev = prev_halfedge_handle(inner_next);
          assert(boundary_prev.is_valid());
          next_cache_[next_cache_count++] = std::make_pair(boundary_prev, outer_next);
          set_halfedge_handle(vh, outer_next);
          break;

        case 2: // next is new, prev is old
          boundary_next = next_halfedge_handle(inner_prev);
          assert(boundary_next.is_valid());
          next_cache_[next_cache_count++] = std::make_pair(outer_prev, boundary_next);
          set_halfedge_handle(vh, boundary_next);
          break;

        case 3: // both are new
          if (!halfedge_handle(vh).is_valid())
          {
            set_halfedge_handle(vh, outer_next);
            next_cache_[next_cache_count++] = std::make_pair(outer_prev, outer_next);
          }
          else
          {
            boundary_next = halfedge_handle(vh);
            boundary_prev = prev_halfedge_handle(boundary_next);
            assert(boundary_prev.is_valid());
            assert(boundary_next.is_valid());
            next_cache_[next_cache_count++] = std::make_pair(boundary_prev, outer_next);
            next_cache_[next_cache_count++] = std::make_pair(outer_prev, boundary_next);
          }
          break;
      }

      // set inner link
      next_cache_[next_cache_count++] = std::make_pair(inner_prev, inner_next);
    }
    else edgeData_[ii].needs_adjust = (halfedge_handle(vh) == inner_next);


    // set face handle
    set_face_handle(edgeData_[i].halfedge_handle, fh);
  }

  // process next halfedge cache
  for (i = 0; i < next_cache_count; ++i)
    set_next_halfedge_handle(next_cache_[i].first, next_cache_[i].second);


  // adjust vertices' halfedge handle
  for (i=0; i<n; ++i)
    if (edgeData_[i].needs_adjust)
      adjust_outgoing_halfedge(_vertex_handles[i]);

  return make_smart(fh, this);
}
           

入口代碼位置見：

src\OpenMesh\Core\Mesh\PolyConnectivity.cc

void PolyConnectivity::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.is_valid(); ++vf_it)
    face_handles.push_back(*vf_it);


  // delete collected faces
  // 删除所有關聯的面
  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);
}
           

上述代碼實作中的重點部分是delete_face，那麼接下來先來看一下delete_face的代碼實作。

src\OpenMesh\Core\Mesh\PolyConnectivity.cc

void PolyConnectivity::delete_face(FaceHandle _fh, bool _delete_isolated_vertices)
{
  assert(_fh.is_valid() && !status(_fh).deleted());

  // mark face deleted，将該facehandle标記為已經删除
  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
  // 用來存儲面的所有頂點，用來更新這些頂點的outgoing 半邊；
  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.is_valid(); ++fh_it)
  {
    hh = *fh_it;

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

    // 如果邊界半邊opposite半邊也是邊界，那麼這個邊需要被删除
    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
  // these edges were all boundary
  // delete isolated vertices (if _delete_isolated_vertices is true)
  // 此處的邏輯可以見代碼後的圖示。
  if (!deleted_edges.empty())
  {
    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 if the mesh has a edge status
      if ( has_edge_status() )
    	 status(*del_it).set_deleted(true);


      // mark corresponding halfedges as deleted
      // As the deleted edge is boundary,
      // all corresponding halfedges will also be deleted.
      if ( has_halfedge_status() ) {
        status(h0).set_deleted(true);
        status(h1).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
  // 邊界的頂點對應的半邊必須是邊界的。
  std::vector<VertexHandle>::iterator v_it(vhandles.begin()),
                                      v_end(vhandles.end());
  for (; v_it!=v_end; ++v_it)
    adjust_outgoing_halfedge(*v_it);
}
           

deleted_edges相關的邏輯示意圖如下：

void PolyConnectivity::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);

  // If there is no face, we delete the edge
  // here
  if ( ! fh0.is_valid() && !fh1.is_valid()) {
    // mark edge deleted if the mesh has a edge status
    if ( has_edge_status() )
      status(_eh).set_deleted(true);

    // mark corresponding halfedges as deleted
    // As the deleted edge is boundary,
    // all corresponding halfedges will also be deleted.
    if ( has_halfedge_status() ) {
      status(halfedge_handle(_eh, 0)).set_deleted(true);
      status(halfedge_handle(_eh, 1)).set_deleted(true);
    }
  }
}
           

delete_edge的實作是将邊關聯的face删除，然後将edge和關聯的half_edge的狀态設定為删除。

unsigned int ArrayKernel::delete_isolated_vertices()
{
  assert(has_vertex_status());//this function requires vertex status property
  unsigned int n_isolated = 0;
  for (KernelVertexIter v_it = vertices_begin(); v_it != vertices_end(); ++v_it)
  {
    if (is_isolated(handle(*v_it)))
    {
      status(handle(*v_it)).set_deleted(true);
      n_isolated++;
    }
  }
  return n_isolated;
}
           

直接判斷出是否為孤立點，然後标記為删除。

版權說明

作者： grassofsky

出處： http://www.cnblogs.com/grass-and-moon

本文版權歸作者，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出, 原文連結 如有問題， 可郵件（[email protected]）咨詢.