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

问题描述

我正在努力实现各种细分算法（如catmull-clark）;要做到这一点有效地需要一个很好的方法来存储关于网格多边形的信息。我将半边数据结构实施为由flipcode 概述，但现在我'我不知道如何从顶点填充数据结构！

我的初始尝试是

• 创建顶点


• 将顶点组合成面


• 在面内排列顶点（使用其相对于质心的角度）


• 为每个脸，抓住第一个顶点，然后穿过排序的顶点列表创建一个半边列表。

但是，这将创建一个没有关于相邻面的信息的面（有半边）的列表！这也感觉有点错误，因为它似乎好像面孔真的是一流的对象，边缘提供辅助信息;我真的觉得我应该从顶点创建边，然后从那里整理出面。但是，再一次，我不太确定如何去做 - 我不能想到创建一个半边列表的方法，而不是首先创建面。

任何有关顶点（和面）数据转换成半边的最佳方式的建议？

解决方案

p>首先，我想指出一个优秀的C ++实现的半边数据结构： OpenMesh 。如果您想使用它，请确保您通过本教程工作。如果（并且只有）你这样做，使用OpenMesh是非常简单的。它还包含一些很好的方法，您可以在其上实现细分或缩减算法。

现在您的问题：

但是，这将创建一个没有任何关于相邻面的信息的面（有半边）的列表！这也感觉有点错误，因为看起来好像脸上真的是一流的对象，边缘提供辅助信息

我认为这有点错过了半边数据结构的要点。在半边的结构中，它是传递最多信息的半边缘！

从 OpenMesh文档（另见图中）：

• 每个顶点引用一个外出的半边，即从该顶点开始的半边。


• 每个面都引用一个包围它的半边。


• 每个半边提供一个句柄，它指向
  
  
  
  
  • 它指向的顶点，
  
  
  
  • 面部下一个半边（逆时针顺序），
  
  
  • 相反的一半，
  
  
  
  

如你所见， strong>大多数信息存储在半边缘中 - 这些是主要对象。在这个数据结构中迭代网格是关于巧妙地遵循指针。

但是，这创建了一个面（一半边） ）没有关于相邻面的任何信息！

这是完全可以的！如上所述，一个脸部仅引用仅一个半边。假设一个三角形网格，您所遵循的指针链，以获得给定面部的三个相邻三角形 F 如下：

F - > halfEdge - >对面HalfEdge - >面对

F - > halfEdge - > nextHalfEdge - >对面HalfEdge - >面对

F - > halfEdge - > previousHalfEdge - >对面HalfEdge - >面对

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

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

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

更具体地说，这里有一些非常概念伪代码，用于从面部创建半边网格。我省略了顶点部分，这更简单，可以以同样的精神实现。我假设在边缘上的迭代是有序的（例如，顺时针方向）。

我假定半边被实现为类型为$ code的结构HalfEdge ，其中包含上面列出的指针作为成员。

  struct HalfEdge 
 {
 HalfEdge * oppositeHalfEdge; 
 HalfEdge * nextHalfEdge; 
顶点*顶点; 
脸*脸; 
} 
  

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

  map<对< unsigned int，unsigned int>，HalfEdge *>边缘; C ++中
  

这里是构造伪代码（没有顶点和面部分）：

  map<对< unsigned int，unsigned int>，HalfEdge *>边缘;每个面的
 
 F 
 {
每个边（u，v）的F 
 {
边[对（u，v）] =新的HalfEdge（）; 
边[pair（u，v）]  - > face = F; 
 
对于F 
 {
设置边缘（u，v）]  - > nextHalfEdge到F $的下一个半边b $ b if（Edges.find（pair（v，u））！= Edges.end（））
 {
边[对（u，v）]  - >对面HalfEdge =边（v，u）]; 
边缘[对（v，u）]  - >对面HalfEdge =边缘[对（u，v）]; 
} 
} 
} 
  

编辑： / strong>使代码稍微伪，更清楚地说明边缘地图和指针。

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!

My initial attempt was to

• create vertices
• group vertices into faces
• sort vertices within faces (using their angle relative to the centroid)
• for each face, grab the first vertex and then walk through the sorted vertex list to create a half-edge list.

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?

解决方案

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.

Now to your question:

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!

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

• 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!

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 -> halfEdge -> oppositeHalfEdge -> face

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

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

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.

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.

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;

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

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

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