使用半边数据结构实现Catmull-Clark细分时如何找到双胞胎顶点

Question

注意：描述比预期的要长一些。您知道使用这个网格实现这个算法的可读性更好的方法吗？请告诉我！

---

我正在尝试使用Matlab实现Catmull-Clark细分，因为后续需要将结果与已在Matlab中实现的其他内容进行比较。第一次尝试使用顶点-面网格，算法可以工作，但效率不高，因为需要邻近边和面的信息。因此，我现在使用半边网格。请参见{{link3：设计多面体表面数据结构，作者Lutz Kettner}}（该页面上有PDF链接）。

我的问题在于找到孪生半边，我不确定如何做到这一点。下面我将描述我的实现想法，力求简洁。

---

半边数据结构网格（使用顶点/半边/面的索引）：

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

Catmull-Clark：

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.

每个新HalfEdge的HeadVertex已知，下一个HalfEdge也是如此。由于它是创建的新面，因此Face也是已知的！唯一未知的是Twin HalfEdge，我该如何知道呢？

顺便说一下，在循环遍历新面的顶点时，将Outgoing_HalfEdge分配给顶点。这可能是找到Twin HalfEdge的地方。

最后，在创建4个新的HalfEdges之后，使用最后一个新创建的HalfVertex的HalfVertex索引保存Face。

---

我希望您能理解，如果需要的话，我可以发布我的（显然还未完成的）Matlab代码。

---

编辑：感谢您把我的帖子移动了过来。我在评论中发布了源代码链接，请注意，此实现考虑了一般多边形网格，而不仅仅是四边形网格。

此外，如果您将旧的四边形面分为4个新面（绿色数字），则可以相对容易地找到新HalfEdges 1和4的孪生兄弟（每个新面中的红色数字）：

那么，如何找到 2 和 3 HalfEdges 的 Twins（孪生）呢？

- Ailurus

---

顺便提一下，每个第二和第三个新半边的孪生半边是未知的，其他的都已知。这是迄今为止我的实现链接：http://www.redpanda.nl/CatmullClark2.m - Ailurus

在花费数小时绘制网格和编写细分后，问题得到了解决。 - Ailurus

如果您解决了问题，请将解决方案作为独立的答案添加并接受它。这样，其他用户就会知道问题已经解决了。 - Florian Brucker

Answer 1

看起来你遇到的概念问题是你试图一次添加半边，然后想知道它们如何相加。然而，边缘才是真正的修改单位，因此您应该总是成对添加它们。

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

1. 首先确保已经分割了面的每个原始边缘。在此过程中，创建一个列表，其中包含与该面相邻的每个“新”顶点；这些是中点。 -- a. 要分割边缘，我们首先要找到相应的半边。创建一个新的顶点。我们将一对新的半边插入到每个链接列表中，调整端点到新的顶点。标记所有四个半边以及新的顶点。

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

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

这个符号看起来有些复杂，但是从概念上讲它很容易理解。每一步都成对地添加半边；在第一步中通过划分边来实现，在第二和第三步中则是通过添加边来实现。每次添加都会保持多面体表示的关联不变量不变，这意味着在代码中你将得到更好的修改局域性。

- eh9

---

如果有人想要列出这些步骤，我完全支持。 - eh9

谢谢你的答案。我在发布这个问题几天后解决了它（说实话，在那之后我完全忘记我在这里发过它）。我解决的方法是添加单个半边（不是一次添加一对，而是单个半边），为了找到其对偶边，我编写了一个高效的算法。去年我尝试了一些其他方法（将其添加到现有网格中，而不是完全重写它），并查看了许多其他方案。当我有更多时间时，我会研究你的建议。 - Ailurus

我写下了我的答案，因为我认为有趣的是，你可以得到一个算法，它在仅使用三个原始操作之外保持所有表示不变式，而且不需要对表示的全局知识。 - eh9