怎样遍历网格

介绍

  遍历大家都清楚的吧，学习数据结构的时候就经常讲到遍历，比如八叉树中，要遍历每一个节点，有各种遍历方法，什么深度优先遍历，广度优先遍历神马的。在一个网格中，有时候我们也要遍历网格中的每一个点、面、边等基本元，这就是这篇文章的内容。

遍历半边(Halfedge)

  首先介绍网格中的半边的遍历，如下图所示的网格拓扑：

  根据选择的遍历初始半边的不同，有两种可能的遍历过程：

1. 如果选择的半边落在网格边界上，及不与任意边相邻，通过使用函数
next_halfedge_handle() 或
prev_halfedge_handle()，遍历就会沿着网格的边界（洞）进行；

2. 如果选择的半边与一个面相邻，那么通过使用上面相同的函数，遍历会沿着所有与这个面相邻的半边进行遍历。

  当然无论是上面的哪种方式遍历，其实都差不多如下：

[...]
TriMesh::HalfedgeHandle heh, heh_init;
// Get the halfedge handle assigned to vertex[0]
heh = heh_init = mesh.halfedge_handle(vertex[0].handle());
// heh now holds the handle to the initial halfedge.
// We now get further on the boundary by requesting
// the next halfedge adjacent to the vertex heh
// points to...
heh = mesh.next_halfedge_handle(heh);
// We can do this as often as we want:
while(heh != heh_init) {
    heh = mesh.next_halfedge_handle(heh);
}
[...]

网格边界

  从上一节可以发现，遍历网格边界比较简单，那么我们什么时候知道我们所选择的半边是属于一个边界（洞）的呢。在OpenMesh中提供了点、边界、面的边界属性，通过使用is_boundary()函数，返回点、边界（半边）、面是否是一个边界。

注意
从上一节我们知道，只要我们选择的第一条半边是属于一个边界的话，那么它的下一条半边依然会是属于边界的。

  所以对于每一种基本元，我们可以如下使用返回边界属性的函数：

// Test if a halfedge lies at a boundary (is not adjacent to a face)
bool is_boundary (HalfedgeHandle _heh) const
// Test if an edge lies at a boundary
bool is_boundary (EdgeHandle _eh) const
// Test if a vertex is adjacent to a boundary edge
bool is_boundary (VertexHandle _vh) const
// Test if a face has at least one adjacent boundary edge.
// If _check_vertex=true, this function also tests if at least one
// of the adjacent vertices is a boundary vertex
bool is_boundary (FaceHandle _fh, bool _check_vertex=false) const

向内或者向外的半边

  OpenMesh提供了2个用来遍历某一个点的所有向内或者向外的半边的函数VertexIHalfedgeIter 和 VertexOHalfedgeIter。如下图，假设我们选择的是最下面的点，那么VertexIHalfedgeIter就会遍历所有的向内半边（蓝色），而VertexOHalfedgeIter就会遍历所有的向外半边（红色）。

相应的代码类似如下：

[...]
// Get some vertex handle
PolyMesh::VertexHandle v = ...;
for(PolyMesh::VertexIHalfedgeIter vih_it = mesh.vih_iter(v); vih_it; ++vih_it) {
    // Iterate over all incoming halfedges...
}
for(PolyMesh::VertexOHalfedgeIter voh_it = mesh.voh_iter(v); voh_it; ++voh_it) {
    // Iterate over all outgoing halfedges...
}
[...]

反向半边

  在半边数据结构中，每一条边都被拆分成了两条方向相反的半边，所以对于每一条半边，存在着对应的反向半边。在OpenMesh中可以通过函数opposite_halfedge_handle()得到某一条半边的反向半边。
  例子代码类似如下：

// Get the halfedge handle of i.e. the halfedge
// that is associated to the first vertex
// of our set of vertices
PolyMesh::HalfedgeHandle heh = mesh.halfedge_handle(*(mesh.vertices_begin()));
// Now get the handle of its opposing halfedge
PolyMesh::HalfedgeHandle opposite_heh = mesh.opposite_halfedge_handle(heh);

  当然除了反向半边之外，OpenMesh中还提供了一下的函数得到一个元的相反元：

// Get the face adjacent to the opposite halfedge
OpenMesh::PolyConnectivity::opposite_face_handle();
// Get the handle to the opposite halfedge
OpenMesh::Concepts::KernelT::opposite_halfedge_handle();
// Get the opposite vertex to the opposite halfedge
OpenMesh::TriConnectivity::opposite_he_opposite_vh();
// Get the vertex assigned to the opposite halfedge
OpenMesh::TriConnectivity::opposite_vh();

得到起点和终点

  这部分最简单了，就是给定一个半边，因为半边是有方向的，所以肯定有一个起点和一个终点，OpenMesh中起点和终点可以通过如下两个函数得到：

// Get the handle of the to vertex
OpenMesh::Concepts::KernelT::to_vertex_handle();
// Get the handle of the from vertex
OpenMesh::Concepts::KernelT::from_vertex_handle();