algorithm - 在使用半边网格实现 Catmull-Clark 分割时找到双胞胎

Question

注意:描述比预期的要长一些。您知道使用此网格实现此算法的可读吗？请让我知道!

---

我正在尝试实现 Catmull-Clark subdivision使用 Matlab，因为稍后必须将结果与已经在 Matlab 中实现的其他一些东西进行比较。首先尝试使用顶点面网格，该算法有效但效率不高，因为您需要边和面的相邻信息。因此，我现在使用 half-edge mesh .也可以看看 Designing a Data Structure for Polyhedral Surfaces, by Lutz Kettner (该页面上的 PDF 链接)。

我的问题在于找到Twin HalfEdges，我只是不确定该怎么做。下面我将描述我对实现的想法，尽量保持简洁。

---

半边网格(使用顶点/半边/面的索引):

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

为了简单起见，假设每个面都是四边形。实际的网格是顶点、半边和面的列表。新网格将由 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仍然未知)。下一步保存新的半边和面。 这是导致我出现问题的部分!

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.

每个新 HalfEdge 的 HeadVertex 都是已知的，Next HalfEdge 也是已知的。 Face 也是已知的(因为它是您正在创建的新面孔!)。只有 Twin HalfEdge 是未知的，我应该如何知道？

顺便说一下，在循环遍历新面的顶点时，将 Outgoing_HalfEdge 分配给顶点。这可能是找出哪个 HalfEdge 是双胞胎的地方。

最后，在创建了 4 个新的 HalfEdges 之后，将具有 HalfVertex 索引的 Face 保存为最后一个新创建的 HalfVertex。

---

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

---

编辑:感谢您移动我的主题。我在评论中发布了指向源代码的链接，请注意此实现考虑了一般的多边形网格，因此不仅是四边形网格。

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

那么，如何找到 2 条和 3 条 HalfEdge 的 Twins？

Answer 1

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

为了实现(单次通过)算法，我将使用“新创建”标志对每个模型元素进行注释，该标志指示元素是否作为算法的结果创建。顶层循环是迭代未修改的面孔。

1. 首先确保面部的每条原始边缘都已被分割。在这样做的同时，创建一个列表，列出每个不利于面部的"new"顶点；这些是中点。 - A。要分割一条边，我们首先要定位相应的半边。创建一个新顶点。我们在每个链表中插入一对新的半边，将端点调整到新顶点。将所有四个半边标记为新的以及新的顶点。

2. 分割面部的第一站与其他人不同。创建一个新的顶点 V 使其位于旧面的中间，并选择一个新的顶点 W 入射到该面。我们将按如下方式连接它们。假设 W 附近的边链表看起来像 ..aWb..。创建一对新的半边 c 和 d。将链表中的 W 替换为 WcVdW 以生成列表“..aWcVdWb..”。这会在面部中间创建一个“ float 边缘”。然而，该数据结构确保我们有一个表示多边形内周的半边链表。将顶点 W 和半边 c 和 d 标记为新的。

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

符号有点讨厌，但从概念上讲它很简单。这三个步骤中的每一个都成对添加半边；在步骤 1 中划分一条边，在步骤 2 和 3 中添加它们。这些添加中的每一个都保持多面体表示的关联不变量不变，这意味着您可以改进代码中的修改局部性。