Нам дан набор треугольников. Каждый треугольник представляет собой тройку точек. Каждая точка представляет собой тройку действительных чисел. Мы можем вычислить нормаль поверхности для каждого треугольника. Однако для затенения Гуро нам нужны вершинные нормали. Поэтому мы должны посетить каждую вершину и посмотреть на треугольники, которые разделяют эту вершину, усреднить их нормали поверхности, и мы получим нормаль вершины.

Какой алгоритм и структура данных наиболее эффективны для этого?

Наивный подход заключается в следующем (псевдо-код Python):

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]])

Есть ли более эффективный подход?