Nos é dado um conjunto de triângulos. Cada triângulo é um trio de pontos. Cada ponto é um trio de números reais. Podemos calcular a superfície normal para cada triângulo. Para o sombreamento de Gouraud, no entanto, precisamos de normais de vértice. Portanto, temos que visitar cada vértice e observar os triângulos que compartilham esse vértice, calcular a média dos seus normais de superfície e obter o vértice normal.

Qual é o algoritmo mais eficiente e estrutura de dados para conseguir isso?

Uma abordagem ingênua é essa (código 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]])

Existe uma abordagem mais eficiente?