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

Question

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

algorithmc++11data-structurespolygoncomputational-geometry

27

我正在实现各种细分算法（例如catmull-clark）；为了高效地实现此操作，需要一种良好的方法来存储有关网格化多边形的信息。我按照flipcode所述的方式实现了半边数据结构，但现在我不确定如何从顶点填充数据结构！

我的初始尝试是：

创建顶点
将顶点分组成面
排序面内的顶点（使用相对于重心的角度）
对于每个面，获取第一个顶点，然后遍历排序后的顶点列表以创建半边列表。

然而，这会创建一个没有关于相邻面任何信息的面（带有半边）。这也感觉有些不对，因为似乎面才是一等对象，而边提供辅助信息；我真的觉得应该从顶点创建边，然后从那里解决面。但同样，我真的不确定如何以这种方式进行 - 我无法想出一种在创建面之前创建半边列表的方法。

你有什么建议，将关于顶点（和面）的数据转换为半边数据结构？

- nathan lachenmyer

2个回答

0

考虑我们有一个三角形列表，每个三角形由逆时针顺序的3个顶点ID指定，任务是构建半边数据结构来表示这个三角剖分。如果顶点被给定为3D向量（如STL文件格式中），则工作从为每个不同的顶点分配唯一标识符开始，这是通过从3D向量到顶点ID的哈希映射完成的。

之后，我们逐步考虑列表中的每个三角形。首先要做的是找到或创建其三条边（每条边由一对半边组成）。如果某条边被两个三角形共享，并且另一个三角形已经添加到数据结构中，则我们找到该边，否则必须创建新边。

为了查找顶点v1和v2之间是否已经存在边，我们使用从一个顶点到其中一个半边的平面映射。所有其他具有相同起点的半边可以使用已构建的半边数据结构进行枚举。因此，这一步的算法是查看每个起点在v1的半边，并测试其终点是否为v2。如果没有找到这样的边，则必须创建两个半边。根据flipcode的术语：pair中的一个新创建的半边指向另一个半边，vert分别位于v1和v2上，next位于v1和v2中的现有半边上，或者如果它是顶点中的第一个半边，则位于自身上。

当当前三角形的所有3条边被找到或创建时，拥有该三角形的半边的face字段指向表示该三角形的新HE_face记录。

所有三角形都被处理完后，数据结构就准备好了。虽然还有一些优化和改进可以实现，但基本思路如上所述。

所有基于半边数据结构的网格库都是在打开标准文件格式（如STL/PLY/OBJ/OFF/…）时构建它的。因此，至少要查看它们的代码，并可能将它们集成到您的软件中，而不是创建自己的实现：

OpenMesh 是一个很好的C++库，已经在其他答案中介绍过。
MeshLib 是一个年轻的库，也是用C++编写的，它可以更快地打开标准文件格式（根据我的观察，特别是STLs）；这表明在半边数据结构（MRMeshTopology.h）中进行转换时有更好的优化（请参见MRMeshBuilder.cpp）。

- Fedor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- DCS · Accepted Answer

首先，我要向你介绍一个优秀的C++半边数据结构实现：OpenMesh。如果您想使用它，请确保您按照教程进行操作。只有这样，使用OpenMesh才相当简单。它还包含一些不错的方法，可以实现细分或减少算法。

现在来回答你的问题：

然而，这会创建一个没有关于相邻面的任何信息的面（带有半边）列表！这也感觉有点不对，因为似乎面才是第一等对象，而边提供附加信息。

我认为这有点误解了半边数据结构的重点。在半边数据结构中，最多的信息都是由半边携带的！

抄袭自OpenMesh文档（请参见其中的图）：

每个顶点引用一个出射半边，即从该顶点开始的半边。
每个面引用其边界之一的半边。
每个半边提供一个句柄，指向
- 它指向的顶点，
- 它所属的面，
- 面内的下一条半边（逆时针排序），
- 相对应的另一个半边，
- （可选：面内的前一条半边）。

正如你看到的，大部分信息都存储在半边中 - 这些是主要的对象。在这个数据结构中迭代网格就是聪明地跟随指针。

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

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

F -> halfEdge -> oppositeHalfEdge -> face

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

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

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

如果在构建网格时正确设置了上述指针，则可以像这样迭代网格中的所有类型的邻接关系。如果使用 OpenMesh，则可以使用一些特殊的迭代器为您执行指针跟踪。

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

更具体地说，以下是一些非常概念性的伪代码，用于从面创建半边网格。我省略了顶点部分，其更简单，并且可以采用同样的方法实现。我假设对于一个面的边的迭代是有序的（例如按顺时针方向）。

我假设半边被实现为类型为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映射和指针更加明确。