Wir erhalten eine Reihe von Dreiecken. Jedes Dreieck ist ein Triplett von Punkten. Jeder Punkt ist ein Triplett von reellen Zahlen. Wir können die Flächennormale für jedes Dreieck berechnen. Für die Gouraud-Schattierung benötigen wir jedoch Scheitelpunktnormalen. Daher müssen wir jeden Scheitelpunkt besuchen und uns die Dreiecke ansehen, die diesen Scheitelpunkt teilen, ihre Oberflächennormalen mitteln und wir erhalten Scheitelpunktnormalen.

Was ist der effizienteste Algorithmus und die effizienteste Datenstruktur, um dies zu erreichen?

Ein naiver Ansatz ist folgender (Pseudo-Python-Code):

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

Gibt es einen effizienteren Ansatz?