26

我正在实现各种细分算法（例如 catmull-clark）；要有效地做到这一点，需要一种很好的方法来存储有关镶嵌多边形网格的信息。我实现了flipcode概述的半边数据结构，但现在我不确定如何从顶点填充数据结构！

我最初的尝试是

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

但是，这会创建一个没有关于相邻面的任何信息的面列表（带有半边）！这也感觉有点不对劲，因为看起来人脸真的是第一类对象，边缘提供了辅助信息；我真的觉得我应该从顶点创建边缘，然后从那里整理出面。但是同样，我不确定如何以这种方式进行 - 我想不出一种方法来创建半​​边列表而不先创建面。

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

4

1 回答 1

27

首先，我想向您指出半边数据结构的一个出色的 C++ 实现：OpenMesh。如果您想使用它，请确保您按照教程进行操作。如果（且仅当）您这样做，使用 OpenMesh 将非常简单。它还包含一些不错的方法，您可以在这些方法之上实现细分或归约算法。

现在回答你的问题：

但是，这会创建一个没有关于相邻面的任何信息的面列表（带有半边）！这也感觉有点不对劲，因为看起来人脸真的是第一类对象，边缘提供了辅助信息

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

从OpenMesh 文档中无耻地引用（另见那里的图）：

  • 每个顶点引用一个输出半边，即从该顶点开始的半边。
  • 每个面都引用围绕它的半边之一。
  • 每个半边提供一个句柄
    • 它指向的顶点，
    • 它所属的脸
    • 面内的下一个半边（逆时针顺序），
    • 对面的半边，
    • （可选：面中的前一个半边）。

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

但是，这会创建一个没有关于相邻面的任何信息的面列表（带有半边）！

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

F -> halfEdge -> oppositeHalfEdge -> face

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

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

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

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

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

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

我假设半边被实现为 type 的结构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地图和指针。

于 2013-03-12T16:16:59.403 回答