用于查找共享三角形的最快算法

Question

[有索引和顶点缓冲区，如here所述，用于绘制三角形。

通常，在我的代码中，我需要查找共享特定顶点的三角形。最基本的方法是：

现在，我想知道我是否缺少更高效或更标准的算法。谢谢。

Answer 1

创建第二个查找表，该表将顶点的索引映射到包含该顶点的三角形的列表。

可以通过在索引缓冲区上循环并将三角形添加到所有三个顶点来创建。

例如，如果索引缓冲区是：

0, 1, 4
0, 2, 3

查找表将是

0 -> [t0, t1]
1 -> [t0]
2 -> [t1]
3 -> [t1]
4 -> [t0]

如果要更新数据，则此查找表必须相应地更新。根据共享一个顶点的三角形数量的多少以及添加/删除它们的频率，您可能需要使用哈希表而不是普通列表来存储这些三角形。