NSDT工具推荐： Three.js AI纹理开发包 - YOLO合成数据生成器 - GLTF/GLB在线编辑 - 3D模型格式在线转换 - 可编程3D场景编辑器 - REVIT导出3D模型插件 - 3D模型语义搜索引擎 - AI模型在线查看 - Three.js虚拟轴心开发包 - 3D模型在线减面 - STL模型在线切割 - 3D道路快速建模

表示多边形网格的常用方法是共享顶点列表和存储其顶点索引的面列表。这种表示既方便又对于许多目的都是有效的，但是在某些领域它被证明是无效的。Half Edge就是解决网格中邻接元素查询的一种数据结构。

1、多边形网格的邻接查询问题

例如，网格简化通常需要将一条边折叠成一个顶点。此操作需要删除与边相邻的面并更新共享顶点的面。这种类型的多边形"手术"要求我们发现网格元素的邻接关系，例如面和顶点。虽然我们当然可以利用上面提到的简单网格表示进行这些操作，但很可能会成本高昂，需要搜索整个面或顶点列表，甚至可能两者兼而有之。

多边形网格上的其他类型的邻接查询包括：

  • 哪些面使用此顶点？
  • 哪些边使用此顶点？
  • 哪些面与这条边相邻？
  • 哪些边与这个面相邻？
  • 哪些面与此面相邻？

为了高效、复杂地实现这些类型的邻接查询已经开发了边界表示（B-reps），它显式地模拟了 网格的顶点、边和面，在其中存储了其他邻接信息。

这些类型的表示中最常见的一种是翼边（Winged Edge）数据结构，边使用指向其接触的两个顶点、与其相邻的两个面、以及发出的四个边进行增强描述。这种结构使我们能够在常量时间内确定哪些面或顶点与边相邻，但其他类型的查询可能需要更昂贵的处理。

半边数据结构（Half Edge）是一个稍微复杂的b-rep，它支持上面列出的所有查询（以及其他查询）都能在恒定时间内执行。此外，即使我们为面、顶点和边保存了邻接信息，它们的大小依然可以保持固定（不使用动态数组），因此相当紧凑。

这些属性使半边数据结构成为许多人的绝佳选择，但是，它只能表示流形曲面，其中有些情况可能令人望而却步。从数学定义来说，流形（Manifold）是一个曲面，其中每个点都被一个具有圆盘拓扑结构的小区域包围。 对于多边形网格，这意味着每条边都恰好邻接两个面，不允许在网格中使用 t 形交汇点、内部多边形和断开。

2、Half Edge数据结构

之所以这样称呼半边数据结构，是因为我们不是存储网格的边（Edge），而是存储半边（Half Edge）。顾名思义，半边是边的一半并且是通过沿其长度分割边来构造的。我们将构成边的两个半边称为半边对（Pair）。半边是定向的，半边对的两条边有相反的方向。

下图显示了三角形网格的局部的半边表示。黄点是网格的顶点，浅蓝色条是半边。图中的箭头表示指针，为了保持图表变得过于杂乱，省略了一些内容。

如图所示，与面邻接的半边围绕其周边形成一个圆形链表。此链表可以顺时针或逆时针表示，只要在整个过程中使用相同的约定。每个循环中的半边存储指向它所邻接的面（图中未显示，在其终点的顶点（也未显示）和指向半边对的指针。在 C 程序中看起来是这样的：

 struct HE_edge
    {

        HE_vert* vert;   // vertex at the end of the half-edge
        HE_edge* pair;   // oppositely oriented adjacent half-edge 
        HE_face* face;   // face the half-edge borders
        HE_edge* next;   // next half-edge around the face
    
    };

半边数据结构中的顶点（Vertex）存储其 x、y 和 z 位置以及指向使用该顶点作为起点的半边之一。 在任何给定的顶点上，我们都可以为此选择超过一个半边，但是我们只需要一个，是哪一个并不重要。我们将在稍后介绍查询方法是解释为什么这是可行的。在 C 语言中，顶点结构如下所示：

struct HE_vert
    {

        float x;
        float y;
        float z;

        HE_edge* edge;  // one of the half-edges emantating from the vertex
    
    };

对于半边数据结构而言，面（Face）只需要存储指向与其邻接的半边之一的指针。在更实际的实现中，我们可能还会在面部存储有关纹理、法线等的信息。面中的半边指针类似于顶点结构中的指针，因为虽然每个面都有多个半边，但我们只需要存储其中一个，哪一个都无所谓。这是 C 语言中的面结构：

struct HE_face
    {

        HE_edge* edge;  // one of the half-edges bordering the face

    };

3、邻接查询

大多数邻接查询的答案直接存储在边、顶点和面的数据结构中。例如，与半边相邻的顶点或面可以很容易地找到：

    HE_vert* vert1 = edge->vert;
    HE_vert* vert2 = edge->pair->vert;

    HE_face* face1 = edge->face;
    HE_face* face2 = edge->pair->face;

一个稍微复杂一些的例子是迭代与面相邻的半边。 由于面周围的半边形成圆形链表，并且面结构存储了指向这些半边之一的指针，我们这样做：

     HE_edge* edge = face->edge;

     do {

        // do something with edge
        edge = edge->next;
     
     } while (edge != face->edge);

同样，我们可能有兴趣迭代与特定顶点相邻的边或面 。回到前面的图，你可能会看到，除了围绕面形成圆形链表之外，半边还在顶点周围形成循环。迭代过程和查询与顶点相邻的边或面一样，这是在 C 中的实现：

    HE_edge* edge = vert->edge;

     do {

          // do something with edge, edge->pair or edge->face
          edge = edge->pair->next;

     } while (edge != vert->edge);

请注意，在这些迭代示例中，不包括对空指针的检查。 这是因为对曲面流形的限制;为了这个要满足的要求，所有指针都必须有效。

按照这些示例，可以快速找到其他邻接关系。

4、结束语

The Harvard Graphics Archive Mesh库包含半边数据结构的完整实现。源代码可在线获取。

如前所述，半边对表示流形的要求，使其无法用于某些目的。翼边（Winged Edge）数据结构能够克服其中一些限制，更复杂的径向边（Radial Edge）数据结构支持完全非流形网格。

原文链接：The Half-Edge Data Structure by Max McGuire

BimAnt翻译整理，转载请标明出处