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

Question

我正在努力实现各种细分算法(例如catmull-clark); 要有效地执行此操作,需要一种很好的方法来存储有关细分多边形网格的信息.我实现了flipcode概述的半边数据结构,但现在我不确定如何从顶点填充数据结构!

我最初的尝试是

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

但是,这会创建一个没有任何关于相邻面信息的面(一半边)列表!这也感觉有点不对,因为看起来好像是真正的第一类物体,边缘提供辅助信息; 我真的觉得我应该从顶点创建边缘,然后从那里整理出面.但同样,我不太确定如何以这种方式去做 - 我想不出一种方法来创建一个半边列表而不先创建面.

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

Answer 1

首先,我想指出一个优秀的半边数据结构的C++实现:OpenMesh.如果您想使用它,请确保您完成整个教程.如果(并且仅当)您这样做,使用OpenMesh非常简单.它还包含一些很好的方法,您可以在其上实现细分或缩减算法.

现在问你的问题:

但是,这会创建一个没有任何关于相邻面信息的面(一半边)列表!这也感觉有点不对,因为看起来好像是真正的第一类对象,而边缘提供了辅助信息

我认为这有点忽略了半边数据结构的要点.在半边结构中,半边缘带有最多的信息!

从OpenMesh文档中无耻地引用(参见那里的图):

• 每个顶点引用一个出局半边,即从该顶点开始的半边.
• 每个面都引用了一个限定它的半边.
• 每个halfedge提供一个句柄
  • 它指向的顶点,
  • 它所属的面孔
  • 面部内的下一半(逆时针方向),
  • 相反的半边,
  • (可选:前面的半边脸).

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

但是,这会创建一个没有任何关于相邻面信息的面(一半边)列表!

这完全没问题!如上所示,一个面仅引用一个边界半边.假设有一个三角形网格,您遵循的指针链将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地图和指针.