从顶点初始化半边缘数据结构(Initializing Half-edge data structur

我正在实现各种细分算法（如卡特莫尔 - 克拉克）; 有效地做到这一点，需要存储有关tesselated多边形网格信息的好方法。我实现了半边缘的数据结构由flipcode概括，但现在我不知道如何从顶点填充数据结构！

我最初的尝试是

创建顶点
顶点组成面
面内的顶点的排序（使用他们的角度相对于所述质心）
每个面，抢到第一个顶点，然后通过排序顶点列表走到创建半边名单。

然而，这将创建没有关于相邻面的任何信息面的列表（半边缘）！这也感觉有点不对劲，因为它好像脸上是真正一流的对象和边缘提供辅助信息; 我真的觉得我应该创建一个从顶点的边，然后从那里整理出来的面孔。但同样，我真的不知道如何去这种方式 - 我不能想办法创造半边缘的列表，而无需首先创建的面孔。

什么最好的办法有什么建议去了解顶点（和面）成半边缘转动的数据？

首先，我想你指向一个优秀的C ++实现的半边缘的数据结构： OpenMesh 。如果你想使用它，请确保您的工作方式，通过本教程。如果（且仅当）你这样做，与OpenMesh工作是非常简单的。它也包含在上面一些不错的方法，其中可以实现细分或减少算法。

现在，你的问题：

然而，这将创建没有关于相邻面的任何信息面的列表（半边缘）！这也感觉有点不对劲，因为它好像脸上是真正一流的对象和边缘提供辅助信息

我想，这一定程度上忽略了半边数据结构的点。在一个半边缘结构，它是半边缘携带最多信息！

从无耻地引用OpenMesh文件（也见图那里）：

每个顶点引用一个传出半边，即开始在这个顶点半边。
每个面引用halfedges包围它的一个。
每个半边提供了一个句柄
- 它所指向的顶点，
- 面对它属于
- 面对境内的下半边（逆时针排序）
- 相反半边，
- （任选地：在面对前半边）。

正如你看到的， 大部分信息存储在半边缘 -这些是主要的对象。在此数据结构遍历网格是所有关于巧妙以下指针。

然而，这将创建没有关于相邻面的任何信息面的列表（半边缘）！

这是完全OK！正如你看到的上面，一张脸只引用一个边界半边。假设一个三角形网格，按照得到3个相邻三角形到给定面指针链F如下：

F -> halfEdge -> oppositeHalfEdge -> face

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

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

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

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

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

更具体地讲，这里是一个用于创建从面的半边网一些非常概念性的伪代码 。我省略了顶点的部分，这是更简单，并可以以同样的精神来实现。我认为迭代过面边是有序（如顺时针）。

我假定半边缘类型的结构实现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地图和指针。