Nos dan un conjunto de triángulos. Cada triángulo es un triplete de puntos. Cada punto es un triplete de números reales. Podemos calcular la superficie normal para cada triángulo. Sin embargo, para el sombreado de Gouraud, necesitamos vértices normales. Por lo tanto, tenemos que visitar cada vértice y observar los triángulos que comparten ese vértice, promediar sus normales de superficie y obtenemos el vértice normal.

¿Cuál es el algoritmo y la estructura de datos más eficientes para lograr esto?

Un enfoque ingenuo es este (código de pseudo 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]])

¿Hay un enfoque más eficiente?