从顶点初始化半边数据结构 [英] Initializing Half-edge data structure from vertices

问题描述

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

I'm working on implementing various subdivision algorithms (such as catmull-clark); to do this efficiently requires a good way to store information about a grid of tesselated polygons. I implemented the half-edge data structure as outlined by flipcode, but now I'm not sure how to populate the data structure from vertices!

我最初的尝试是

• 创建顶点
• 组顶点到面
• 排序顶点面（使用的角度相对于他们的心）在
• 在每个面，抢到第一个顶点，然后遍历排序的顶点列表来创建一个半边名单。

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

However, this creates a list of faces (with half-edges) that don't have any information about adjacent faces! This also feels a bit wrong, because it seems as if the faces are really the first-class object and the edges provide auxiliary information; I really feel like I should be creating edges from the vertices and then sorting out the faces from there. But again, I'm not really sure how to go about it that way -- I can't think of a way to create a list of half-edges without creating the faces first.

有去什么是最好的方式转过来的顶点（和面）到半边缘的数据有什么建议？

Any suggestions for what the best way to go turning data about vertices (and faces) into half-edges?

推荐答案

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

First, I'd like to point you to an excellent C++ implementation of the half-edge data structure: OpenMesh. If you want to use it, make sure you work you way through the tutorial. If (and only if) you do that, working with OpenMesh is quite straightforward. It also contains some nice methods on top of which you can implement subdivision or reduction algorithms.

现在你的问题：

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

However, this creates a list of faces (with half-edges) that don't have any information about adjacent faces! This also feels a bit wrong, because it seems as if the faces are really the first-class object and the edges provide auxiliary information

我觉得这个有点忽略了半边数据结构的点。在一个半边缘结构，它是半边缘携带最多信息！

I think this somewhat misses the point of the half-edge data structure. In a half-edge structure, it is the half-edges that carry the most information!

从 OpenMesh文档报价耍赖（参见图有）：

Quoting shamelessly from the OpenMesh documentation (see also the figure there):

• 在每个顶点引用一个即将离任的半边，也就是说，在这个顶点开始一个半边。
• 在每个面都引用halfedges之一包围了。
• 在每半边提供了一个句柄
  • 顶点它指向，
  • 在它所属的脸
  • 面（有序逆时针）内的下一个半边，
  • 相反的半边，
  • 。（可选：在previous的脸半边）
  • Each vertex references one outgoing halfedge, i.e. a halfedge that starts at this vertex.
  • Each face references one of the halfedges bounding it.
  • Each halfedge provides a handle to
    • the vertex it points to ,
    • the face it belongs to
    • the next halfedge inside the face (ordered counter-clockwise) ,
    • the opposite halfedge ,
    • (optionally: the previous halfedge in the face ).

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

    As you see, most information is stored in the half-edges - these are the primary objects. Iterating over meshes in this data-structure is all about cleverly following pointers.

    然而，这产生面的列表（用半边）不具有关于相邻面的任何信息！

    However, this creates a list of faces (with half-edges) that don't have any information about adjacent faces!

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

    This is perfectly ok! As you see above, a face references only one bounding half edge. Assuming a triangle mesh, the chain of pointers you follow to get the 3 adjacent triangles to a given face F is the following:

    F - ＆GT;半边 - ＆GT; oppositeHalfEdge - ＆GT;面对

    F - ＆GT;半边 - ＆GT; nextHalfEdge - ＆GT; oppositeHalfEdge - ＆GT;面对

    F - ＆GT;半边 - ＆GT; previousHalfEdge - ＆GT; oppositeHalfEdge - ＆GT;面对

    另外，您可以使用 nextHalfEdge - ＆GT; nextHalfEdge 如果你不使用'previous'指针。当然，这，很容易推广到四边形或更高阶的多边形。

    Optionally, you can use nextHalfEdge -> nextHalfEdge if you don't use the 'previous' pointers. This, of course, generalizes easily to quads or higher order polygons.

    如果您设置高于正常构建网格的时候，那么你就可以遍历各种邻接在你的网这样列出的指针。如果你使用OpenMesh，您可以用一堆特殊的迭代器的指针追逐你。

    If you set the pointers listed above correctly when building your mesh, then you can iterate over all kinds of adjacencies in your mesh like this. If you use OpenMesh, you can use a bunch of special iterators that to the pointer chasing for you.

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

    Setting the "opposite half edge" pointers is of course the tricky part when building a half-edge structure from a "triangle soup". I suggest to use a map data-structure of some kind to keep track of half-edges already created.

    具体而言，这里是一些非常概念化的伪code 创建从面临着半边网格。予省略了顶点的一部分，这是更简单的，并且可以以同样的精神来实现。我认为迭代一个面边是有序的（如顺时针）。

    To be more specific, here is some very conceptual pseudo-code for creating a half-edge mesh from faces. I omitted the vertex part, which is simpler, and can be implemented in the same spirit. I assume that iteration over a face edges is ordered (e.g. clock-wise).

    我认为半边缘被实现为类型结构半边，其含有以上作为成员列出的指针。

    I assume half edges are implemented as structs of type HalfEdge, which contain the pointers listed above as members.

       struct HalfEdge
       {
          HalfEdge * oppositeHalfEdge;
          HalfEdge * nextHalfEdge;
          Vertex * vertex;
          Face * face;
       }
    

    让边缘从对顶点标识符的指针映射到实际的半边实例，如：

    Let Edges be a map from pairs of vertex identifiers to pointers to the actual half-edge instances, e.g.

    map< pair<unsigned int, unsigned int>, HalfEdge* > Edges;
    

    在C ++中。这里是建设伪code（不带顶点和脸部分）：

    in C++. Here is the construction pseudo-code (without the vertex and face part):

    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) ];
           }
        }
     }
    

    编辑：提出的codea的少一点假，更加明确了边缘地图和指针

    Made the code a bit less pseudo, to be more clear about the Edges map and the pointers.

    这篇关于从顶点初始化半边数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！