Mesh is Art (3): Half-Edge Data Structure

#前言
在前文中，作为预热，我们大概说明了网格的某些特性在实际工程中的应用，由于后面还有更多的网格算法的讲解，要想理解这些算法，我们需要一套基本的处理网格的工具，所以这次继续回到关于网格的数据结构上，从底层架构讲起。在第一篇，我们讲述了半边数据结构，这是一种在相邻元素查找问题上非常高效实用的数据结构，广泛应用于很多网格编辑算法中。本文将重点剖析这种数据结构所带来的优势以及组成原理。

#半边数据结构的底层架构
半边数据结构（Half-Edge Data Structure）是一个以网格边为基础的数据结构，在这种数据结构中，我们认为网格的每条边被划分为两条方向相反的半边（HalfEdge，如图1）。为了帮助大家更好的理解，还请跟着我的思路，从几何的角度一步步体验这种数据结构的妙处。不难想到，如果我们对一张网格面中的所有边按照顺序做同样的操作，我们可以在每一张网格面的内部得到一个闭合的、首尾相接的“回路”。接下来我们对半边网格所包含的元素分别做讲解。

##半边

类似向量，每一条半边都有它的起点（Start Vertex）和终点（End Vertex），首先，起点和终点对调，我们可以得到一条半边的反向半边（Opposite Halfedge），其次，根据终点我们可以找到以一条半边的终点为起点的半边，同理，也可以找到以一条半边的起点为终点的半边，这样就定义了一条半边的下一条半边（Next Halfedge）和上一条半边（Prev Halfedge）。

这里，我们可能会抛出一个问题，正如我们第一篇所讲到的，网格是有流形网格和非流形网格的，那么我们能否用半边网格去表示非流形网格？所谓非流形网格，最简单的例子就是一条网格边连接了三张网格面，但是每条边只能被划分成方向相反的两条半边。如图3， 我们可以很轻松地对两张面画出它们的半边，但是对于那条非流形边（三张面的交线），如果按照半边网格的画法，它需要三个方向的半边，但是方向只有正负，我们没有办法画出第三张面的半边。因此，半边网格是无法表示非流形网格的。

接着，我们继续来挖掘这种数据结构所带来的便利。如前文所述，这是一种查找相邻元素极其高效的数据结构。因为半边的划分，我们能在每一张网格面的内部**得到一个闭合的、首尾相接的“回路”，**这这里其实我们就已经将一张网格面内部的半边看作是这张网格面的属性了。举个例子，如图4，半边1->0，0->2，2->3和3->1，它们属于绿色网格面。那如果我们要检索与绿色网格面相邻的网格面，我们只需要求边2->3的反向半边所在的网格面即可。以此类推，我们会发现，我们可以将相邻网格面的索引作为一条半边的属性，**对于一个封闭流形网格，每条边的半边都会伴随一张唯一的相邻网格面（Adjacent Face）的索引，对于开放流形网格，我们可以让这个索引的值设为-1。**这样一来，检索相邻网格面几乎变成了零成本，因为这个数据从一开始就已经记录好了。

了解了这些信息，我们已经很容易去定义半边了，在Plankton（Daniel Piker开发的C#半边网格库）中，一条半边的构造方法只需要起始点（StartVertex）、相邻网格面的索引（AdjacentFace）、下一条半边（NextHalfedge）和上一条半边（PrevHalfedge）。

注意：终点不再被需要，因为它可以通过检索下一条半边的起点来得到。反向半边也不需要，因为半边是成对存在的，获取反向半边可以通过已知半边的索引来查找。（C#代码：halfedgeIndex % 2 == 0 ? halfedgeIndex + 1 : halfedgeIndex - 1;）

##顶点

先来思考一个问题，在最常用的面-顶点网格数据结构中，当多个顶点重合时，我们会用网格焊接（Weld）来处理重复的顶点，并求这些顶点的法向量的合向量，使网格看起来更圆滑。那么半边网格有没有这个概念呢？答案是没有的，举个例子，如图4，在面-顶点网格数据结构中，3号点理应是两个重合点，分别属于绿色网格面和红色网格面，如果半边网格也是两个重合点，那么边2->3应该会产生4条半边，就变成了两张独立的网格面。因此在一个半边网格内不存在重合点的情况。

顶点除了常规网格数据结构中记录的XYZ三个坐标外，还有一个**以此顶点为源点的半边连接指向信息，即出半边（Outgoing Halfedge）。**此外，半边数据结构还规定了，**对于位于边界的顶点，出半边必为边界半边。**但是我们知道，只要不在网格边界内部的顶点都会与多条半边相连，半边数据结构的顶点不存在重合点情况，那么一个连接多条半边的顶点的出半边是什么呢？

为了探究这个问题，我们做一个小测试，如图5所示，调用了Plankton半边网格库，把顶点索引、选取顶点和该顶点的出半边显示出来，以便观察规律。

测试代码如下：

  private void RunScript(Mesh x, int y, ref object Point, ref object OutgoingHalfEdge, ref object VertexIndices, ref object OutgoingStartPoint)
  {
    PlanktonMesh pm = x.ToPlanktonMesh();
    Point = pm.Vertices[y].ToPoint3d();
    Point3d startpoint = pm.Vertices[pm.Halfedges[pm.Vertices[y].OutgoingHalfedge].StartVertex].ToPoint3d();
    Point3d endpoint = pm.Vertices[pm.Halfedges[pm.Halfedges[pm.Vertices[y].OutgoingHalfedge].NextHalfedge].StartVertex].ToPoint3d();
    OutgoingHalfEdge = new Vector3d(endpoint - startpoint);
    OutgoingStartPoint = startpoint;
    List<Point3d> vertices = new List<Point3d>();
    for (int i = 0; i < pm.Vertices.Count; i++)
    {
      vertices.Add(pm.Vertices[i].ToPoint3d());
    }
    VertexIndices = vertices;
  }

首先，根据“位于边界的顶点，出半边必为边界半边”这条性质，我们先确定出半边的走向，如图6所示。图中，我们查看2号点的出半边，是由2号点指向1号点，出半边是边界半边，所以是位于三角面片的外侧，以此类推可以画出整张网格面的半边走向。

下面我们来添加一张网格面，就以2号点为连接点，添加3号点，生成第二张面（如图7）。我们可以看到出半边马上由2->1变成了2->3，这还是因为“位于边界的顶点，出半边必为边界半边”。

然后我们继续添加4号点，构成面2-3-4，发现出半边继续变化，由2->3变成了2->4（图8），紧接着最后一步，添加面0-2-4，此面添加后，2号点由边界顶点变成了内部顶点，它的出半边没有变化，出半边锁定在了将它变成内部顶点前的状态（图9）。

通过以上尝试，我们发现了，对于内部顶点，其出半边为其被封闭前（添加最后一个面片即被封闭）的出半边。

##面

半边数据结构的网格的构建通常是通过面列表来创建的，也就是说，正常的构建半边数据结构网格是通过一个一个面片的添加来构建的。半边网格的面仅包含半边网格的第一条半边（FirstHalfedge）的索引。因为每条半边对应一个起点，添加面时要按顺序添加顶点，只凭第一个顶点无法确定面的法向，但是顶点对应的半边可以。另外一点，因为半边已经记录了下一条半边和上一条半边的信息，面就不再需要顶点的拓扑信息了。因此第一条半边决定了“环路”的方向，决定了面的法向，还决定了顶点的拓扑关系。

最后我们再思考最后一个问题，**半边数据结构能表达边数多于4的多边形网格吗？**答案是肯定的，根据半边数据结构的底层架构我们能看到这种数据结构下已经不再受限于面片中的边的数量，一切关系都由半边紧密连接。

##总结

**顶点(Vertex)：**包含顶点坐标，出半边（OutgoingHalfedge）的索引。

**半边(HalfEdge)：**包含起始点（StartVertex）、邻接面(AdjacentFace)、下一条半边(NextHalfedge)、上一条半边(PrevHalfedge)的索引。

**面片(Face)：**包含一条起始边（FirstHalfedge）的索引。

##特性
（1）半边数据结构不能表达非流形网格；
（2）半边数据结构能够表达边数>4的多边形网格；
（3）半边数据结构多用来处理相邻元素检索的问题。