PROSAGA码农传奇-边缘数据治理-从顶点初始化半边数据结构

<div class =“post-text”itemprop =“text”>
  
    首先，我想指出一个优秀的半边数据结构的C ++实现：
    <a href="http://www.openmesh.org/" rel="noreferrer">
      OpenMesh
    </A>
    。如果您想使用它，请确保您完成整个教程。如果（并且仅当）您这样做，使用OpenMesh非常简单。它还包含一些很好的方法，您可以在其上实现细分或缩减算法。
  
  
    现在问你的问题：
  
  <BLOCKQUOTE>
    
      但是，这会创建一个没有任何关于相邻面信息的面（一半边）列表！这也感觉有点不对，因为看起来好像是真正的第一类对象，而边缘提供了辅助信息
    
  </BLOCKQUOTE>
  
    我认为这有点忽略了半边数据结构的要点。在半边结构中，半边缘带有最多的信息！
  
  
    引用无耻地引用
    <a href="http://openmesh.org/Documentation/OpenMesh-Doc-Latest/mesh_hds.html" rel="noreferrer">
      OpenMesh文档
    </A>
     （另见图）：
  
  <UL>
    <LI>
      每个顶点引用一个出局半边，即从该顶点开始的半边。
    </LI>
    <LI>
      每个面都引用了一个限定它的半边。
    </LI>
    <LI>
      每个halfedge提供一个句柄

<UL>
        <LI>
          它指向的顶点，
        </LI>
        <LI>
          它所属的面孔
        </LI>
        <LI>
          面部内的下一半（逆时针方向），
        </LI>
        <LI>
          相反的半边，
        </LI>
        <LI>
          （可选：前面的半边脸）。
        </LI>
      </UL>
    </LI>
  </UL>
  
    正如你看到的，
    的
      大多数信息存储在半边
    </强>
      - 这些是主要对象。在这个数据结构中迭代网格就是巧妙地遵循指针。
  
  <BLOCKQUOTE>
    
      但是，这会创建一个没有任何关于相邻面信息的面（一半边）列表！
    
  </BLOCKQUOTE>
  
    这完全没问题！如上所示，面部参考
    的
      只要
    </强>
     一个边缘半边缘。假设有一个三角形网格，你遵循的指针链将3个相邻的三角形放到给定的面上
     <code>
 F
 </code>
     如下：
  
  
     <code>
 F -> halfEdge -> oppositeHalfEdge -> face
 </code>
  
  
     <code>
 F -> halfEdge -> nextHalfEdge -> oppositeHalfEdge -> face
 </code>
  
  
     <code>
 F -> halfEdge -> previousHalfEdge -> oppositeHalfEdge -> face
 </code>
  
  
    您也可以选择使用
     <code>
 nextHalfEdge -> nextHalfEdge
 </code>
     如果你不使用'previous'指针。当然，这很容易推广到四边形或更高阶的多边形。
  
  
    如果在构建网格时正确设置上面列出的指针，那么您可以像这样迭代网格中的各种邻接。如果你使用OpenMesh，你可以使用一堆特殊的迭代器来指向你。
  
  
    当设置“三角汤”的半边结构时，设置“相对的半边”指针当然是棘手的部分。我建议使用某种地图数据结构来跟踪已创建的半边。
  
  
    更具体地说，这里有一些
    的
      非常概念性的伪代码
    </强>
     用于从面创建半边网格。我省略了顶点部分，这更简单，并且可以以相同的精神实现。我假设对面边缘的迭代是有序的（例如，顺时针方向）。
  
  
    我假设半边被实现为类型的结构
     <code>
 HalfEdge
 </code>
    ，其中包含上面列为成员的指针。
  
   <pre>
 <code>
 struct HalfEdge
 {
 HalfEdge * oppositeHalfEdge;
 HalfEdge * nextHalfEdge;
 Vertex * vertex;
 Face * face;
 }

</code>
 </pre>
  
    让
     <code>
 Edges
 </code>
     是从顶点标识符对到实际半边实例的指针的映射，例如，
  
   <pre>
 <code>
 map< pair<unsigned int, unsigned int>, HalfEdge* > Edges;

</code>
 </pre>
  
    在C ++中。这是构造伪代码（没有顶点和面部分）：
  
   <pre>
 <code>
 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) ];
       }
    }
 }

</code>
 </pre>
  
    的
      编辑：
    </强>
     使代码更少伪，更清楚
     <code>
 Edges
 </code>
     地图和指针。
  
</DIV>