algorithm - 从顶点初始化半边数据结构

Question

我正致力于实现各种分割算法(例如 catmull-clark)；要有效地做到这一点，需要一种好的方法来存储有关镶嵌多边形网格的信息。我将半边数据结构实现为 outlined by flipcode , 但现在我不确定如何从顶点填充数据结构!

我最初的尝试是

• 创建顶点
• 将顶点分组为面
• 对面内的顶点进行排序(使用它们相对于质心的角度)
• 对于每个面，获取第一个顶点，然后遍历排序的顶点列表以创建半边列表。

但是，这会创建一个面列表(带有半边)，其中没有任何关于相邻面的信息!这也感觉有点不对，因为看起来脸真的是一等对象，边缘提供辅助信息；我真的觉得我应该从顶点创建边，然后从那里整理出面孔。但同样，我不太确定该怎么做——我想不出一种方法来创建半​​边列表而不先创建面。

对于将有关顶点(和面)的数据转换为半边的最佳方法有什么建议吗？

Answer 1

首先，我想向您介绍半边数据结构的出色 C++ 实现:OpenMesh .如果您想使用它，请确保您已完成本教程。如果(且仅当)您这样做，使用 OpenMesh 将非常简单。它还包含一些不错的方法，您可以在这些方法之上实现分割或缩减算法。

现在回答你的问题:

However, this creates a list of faces (with half-edges) that don't have any information about adjacent faces! This also feels a bit wrong, because it seems as if the faces are really the first-class object and the edges provide auxiliary information

我认为这有点忽略了半边数据结构的要点。在半边结构中，携带最多信息的是半边!

无耻地引用自OpenMesh documentation (另请参见此处的图):

• 每个顶点引用一个输出半边，即从该顶点开始的半边。
• 每个面都引用了它的半边之一。
• 每个半边提供一个句柄
  • 它指向的顶点，
  • 它所属的面孔
  • 面内的下一个半边(逆时针排列)，
  • 对面的半边，
  • (可选:前面的半边)。

如您所见，大部分信息存储在半边 - 这些是主要对象。迭代此数据结构中的网格就是巧妙地遵循指针。

However, this creates a list of faces (with half-edges) that don't have any information about adjacent faces!

这完全没问题!正如您在上面看到的，一张脸仅引用了一个边界半边。假设一个三角形网格，将 3 个相邻三角形指向给定面 F 所遵循的指针链如下:

F -> halfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> nextHalfEdge -> oppositeHalfEdge -> face

F -> halfEdge -> previousHalfEdge -> oppositeHalfEdge -> face

可选地，如果您不使用“previous”指针，则可以使用 nextHalfEdge -> nextHalfEdge。当然，这很容易推广到四边形或更高阶的多边形。

如果您在构建网格时正确设置了上面列出的指针，那么您可以像这样迭代网格中的各种邻接。如果你使用 OpenMesh，你可以使用一堆特殊的迭代器来为你追逐指针。

设置“相反的半边”指针当然是从“三角形汤”构建半边结构时的棘手部分。我建议使用某种 map 数据结构来跟踪已创建的半边。

更具体地说，这里有一些非常概念化的伪代码，用于从面创建半边网格。我省略了顶点部分，这样更简单，同样可以实现。我假设对面部边缘的迭代是有序的(例如顺时针方向)。

我假设半边作为 HalfEdge 类型的结构实现，其中包含上面列出的指针作为成员。

   struct HalfEdge
   {
      HalfEdge * oppositeHalfEdge;
      HalfEdge * nextHalfEdge;
      Vertex * vertex;
      Face * face;
   }

设 Edges 是从成对的顶点标识符到指向实际半边实例的指针的映射，例如

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges;

在 C++ 中。这是构造伪代码(没有顶点和面部分):

map< pair<unsigned int, unsigned int>, HalfEdge* > Edges;

for each face F
{
   for each edge (u,v) of F
   {
      Edges[ pair(u,v) ] = new HalfEdge();
      Edges[ pair(u,v) ]->face = F;
   }
   for each edge (u,v) of F
   {
      set Edges[ pair(u,v) ]->nextHalfEdge to next half-edge in F
      if ( Edges.find( pair(v,u) ) != Edges.end() )
      {
         Edges[ pair(u,v) ]->oppositeHalfEdge = Edges[ pair(v,u) ];
         Edges[ pair(v,u) ]->oppositeHalfEdge = Edges[ pair(u,v) ];
       }
    }
 }

编辑:使代码不那么伪，以便更清楚地了解 Edges 映射和指针。