注意:说明变得比预期的要长。您知道使用此网格的该算法的可读实现吗？请告诉我!
我正在尝试使用Matlab实现Catmull-Clark subdivision，因为稍后必须将结果与Matlab中已实现的其他一些东西进行比较。第一次尝试使用Vertex-Face网格，该算法有效，但效率不高，因为您需要边缘和面的相邻信息。因此，我现在正在使用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
卡特穆尔-克拉克(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 也是已知的，Next HalfEdge 的也是如此。 面孔也很出名(因为它是您要创建的新面孔!)。只有 Twin HalfEdge 是未知的，我应该怎么知道？
顺便说一下，在遍历新Face的顶点时，将 Outgoing_HalfEdge 分配给顶点。这可能是找出Half Half Edge是Twin的地方。
最后，在创建了4个新的HalfEdges之后，使用 HalfVertex 索引保存Face，这是最后一个新创建的HalfVertex。
我希望这很清楚，如果需要的话，我可以发布我的(显然还没有完成)Matlab代码。
编辑:感谢您移动我的主题。我在评论中发布了到源代码的链接，请注意，此实现考虑的是通用多边形网格，因此不仅考虑了四边形网格。
此外，如果您考虑将旧的四边形面划分为4个新的Faces(绿色的数字)，则很容易找到新的HalfEdges 1和4的双胞胎(每个新Face中的红色数字):
那么，如何找到2和3 HalfEdges的 Twins ？
最佳答案
看来您遇到的概念性问题是，您试图一次添加一个半边，然后想知道它们是如何相加的。但是，边缘是修改的真正单位，因此您应该始终成对添加它们。
为了实现算法(单次通过)，我将使用“新创建”标志注释每个模型元素，该标志指示该元素是否是由于算法而创建的。顶级循环将在未修改的面上进行迭代。
- 一种。要分割一条边，我们首先找到相应的半边。创建一个新的顶点。我们在每个链表中插入一对新的半边，将端点调整为新的顶点。将所有四个半边标记为新边以及新顶点。
V，然后选择一个入射到该面的新顶点W。我们将按以下方式连接它们。假设W附近的边的链接列表看起来像..aWb..。创建一对新的半边c和d。将链接列表中的W替换为WcVdW，以使列表为“..aWcVdWb ..”。这样会在脸部中央创建一个“ float 边缘”。但是，数据结构可确保我们拥有一个代表多边形内周的半边链表。将顶点W和半边c和d标记为新标记。 ..cVdWb..链接列表序列。由于所有原始边缘均已分割，因此该列表扩展为..cVdWbXeYf..。 X是一个旧的顶点，而Y是一个新的顶点。创建一对新的半边g和g，它们将连接顶点V和Y。从链接列表中提取序列VdWbXeY，并向其中添加g，以创建一个新的面孔[VdWbXeYg]。添加半边h以在旧面上连接V和Y以制作..cVhYf..。将新面孔标记为新面孔。如果没有更多的新顶点，我们就完成了。如果不是，请将名称..cVhYf..映射到..cVdWb..进行迭代。 这种表示法有点讨厌，但从概念上讲却很简单。这三个步骤中的每一个都成对地添加半边；在第1步中通过划分边线，在第2步和第3步中将它们相加。这些添加中的每一个都使多面体表示的入射不变性保持不变，这意味着您可以在代码中获得改进的修改局部性。