使用半边网格实现Catmull-Clark细分时查找双胞胎

Question

注意:描述变得比预期的要长一些.您是否知道使用此网格的此算法的可读实现？请告诉我!

---

我正在尝试使用Matlab 实现Catmull-Clark细分,因为稍后必须将结果与已经在Matlab中实现的其他一些东西进行比较.首先尝试使用Vertex-Face网格,算法可以工作,但效率不高,因为边缘和面需要相邻信息.因此,我现在使用的是半边网格.另见 Lutz Kettner 设计多面体表面的数据结构(该页面上的PDF链接).

我的问题在于找到Twin HalfEdges,我只是不确定如何做到这一点.下面我将描述我对实现的看法,试图保持简洁.

---

半边网格(使用Vertices/HalfEdges/Faces的索引):

Vertex (x,y,z,Outgoing_HalfEdge)
HalfEdge (HeadVertex (or TailVertex, which one should I use), Next, Face, Twin).
Face (HalfEdge)

为了保持现在的简单,假设每个面都是四边形.实际网格是Vertices,HalfEdges和Faces的列表.新网格将由NewVertices,NewHalfEdges和NewFaces组成,如下所示(注意:Number _...是......的数量):

NumberNewVertices: Number_Faces + Number_HalfEdges/2 + Number_Vertices
NumberNewHalfEdges: 4 * 4 * NumberFaces
NumberNewfaces: 4 * NumberFaces

卡特莫尔 - 克拉克:

Find the FacePoint (centroid) of each Face:
--> Just average the x,y,z values of the vertices, save as a NewVertex. 
Find the EdgePoint of each HalfEdge:
--> To prevent duplicates (each HalfEdge has a Twin which would result in the same HalfEdge)
--> Only calculate EdgePoints of the HalfEdge which has the lowest index of the Pair.
Update old Vertices

好了,现在计算了所有新的顶点(但是,它们的Outgoing_HalfEdge仍然未知).下一步保存新的HalfEdges和Faces.这是导致我出问题的部分!

Loop through each old Face, there are 4 new Faces to be created
  (because of the quadrilateral assumption)
First create the 4 new HalfEdges per New Face, starting at the FacePoint to the Edgepoint
Next a new HalfEdge from the EdgePoint to an Updated Vertex
Another new one from the Updated Vertex to the next EdgePoint
Finally the fourth new HalfEdge from the EdgePoint back to the FacePoint.

该HeadVertex每个新半边的是已知的,下一步半边了.该面也是已知的(因为它是正在创建的新面貌!).只有Twin HalfEdge是未知的,我该怎么知道呢？

顺便说一下,在循环遍历新Face的顶点时,将Outgoing_HalfEdge指定给顶点.这可能是找出哪个HalfEdge是Twin的地方.

最后,在创建4个新的HalfEdges之后,使用HalfVertex索引保存Face 最后新创建的HalfVertex.

---

我希望这很清楚,如果需要,我可以发布我的(显然尚未完成的)Matlab代码.

---

编辑:感谢您移动我的主题.我在评论中发布了源代码的链接,请注意这个实现考虑了一般的多边形网格,所以不仅仅是四边形网格.

此外,如果您考虑将旧的四边形脸分为4个新面(绿色数字),则新的HalfEdges 1和4的双胞胎(每个新脸中的红色数字)相当容易找到:

那么,如何找到双胞胎 2-和3- HalfEdges的？

Answer 1

看来您遇到的概念问题是您尝试一次添加一个半边，然后想知道它们是如何相加的。不过，边是修改的真正单位，因此您应该始终将它们成对添加。

为了实现该算法（单次传递），我将使用“新创建”标志来注释每个模型元素，该标志指示该元素是否是作为算法的结果而创建的。顶层循环是在未修改的面上进行迭代。

1. 首先确保面的每条原始边缘都已被分割。执行此操作时，创建与面无关的每个“新”顶点的列表；这些是中点。 - A。要分割一条边，我们首先找到相应的半边。创建一个新顶点。我们在每个链表中插入一对新的半边，将端点调整为新的顶点。将所有四个半边以及新顶点标记为新的。

2. 细分面的第一站与其他的不同。创建一个V位于旧面中间的新顶点，并选择W与该面相关的新顶点。我们将按如下方式连接它们。假设靠近的边的链表W看起来像..aWb..。创建一对新的半边c和d。W将链接列表中的WcVdW内容替换为 '..aWcVdWb..'。这会在脸部中间创建一个“浮动边缘”。然而，数据结构确保我们有一个代表多边形内周长的半边链接列表。将顶点和W半边标记为新的。cd

3. 现在，对于每个剩余的新顶点，我们将创建一对新的半边，但这次每对还将创建一个新面。选择前一个..cVdWb..链表序列。因为所有原始边都已被细分，所以该列表扩展到..cVdWbXeYf..。X是一个旧顶点，Y也是一个新顶点。创建一对新的半边g，g它将连接顶点V和Y。VdWbXeY从链表中提取序列并将g其添加到其中以创建新的面[VdWbXeYg]。添加半边h连接V并Y在旧面上进行制作..cVhYf..。将新面孔标记为新面孔。如果没有更多的新顶点，我们就完成了。如果不是，则将名称映射..cVhYf..到..cVdWb..迭代。

这种表示法有点令人讨厌，但从概念上讲它非常简单。这三个步骤中的每一个都成对添加半边；在步骤 1 中通过分割边，在步骤 2 和 3 中通过将它们相加。这些添加中的每一个都保持多面体表示的关联不变量完整，这意味着您可以改进代码中修改的局部性。