查找哪些三角形共享一个顶点的最快算法

Question

像here描述的那样有索引和顶点缓冲区来绘制三角形。

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

• 遍历索引缓冲区并找到包含该特定顶点索引的三角形。

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

Answer 1

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

它可以通过遍历索引缓冲区并将三角形添加到它的所有三个顶点来创建。

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

0, 1, 4
0, 2, 3

查找 table 将是

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

如果正在更新数据，则此查找 table 必须相应更新。根据共享单个顶点的三角形的数量，以及您 adding/deleting 它们的频率，您可能需要使用散列 table 而不是普通列表来存储这些三角形。