我们有一组三角形,每个三角形由三个点构成,每个点都是三个实数的三元组。我们可以计算每个三角形的表面法向量。然而,对于Gouraud着色,我们需要顶点法向量。因此,我们必须访问每个顶点,并查看共享该顶点的三角形,平均它们的表面法向量,就可以得到顶点法向量。
最有效的算法和数据结构是什么?
一个朴素的方法是这样的(伪代码):
有更高效的方法吗?
最有效的算法和数据结构是什么?
一个朴素的方法是这样的(伪代码):
MAP = dict()
for T in triangles:
for V in T.vertices:
key = hash(V)
if MAP.has(key):
MAP[key].append(T)
else:
MAP[key] = []
MAP[key].append(T)
VNORMALS = dict()
for key in MAP.keys():
VNORMALS[key] = avg([T.surface_normal for T in MAP[key]])
有更高效的方法吗?