Najbardziej wydajny algorytm do obliczania normalnych wierzchołków ze zbioru trójkątów dla cieniowania Gourauda

Otrzymujemy zestaw trójkątów. Każdy trójkąt jest trójką punktów. Każdy punkt to trójka liczb rzeczywistych. Możemy obliczyć normalną powierzchnię dla każdego trójkąta. Jednak w przypadku cieniowania Gourauda potrzebujemy normalnych wierzchołków. Dlatego musimy odwiedzić każdy wierzchołek i przyjrzeć się trójkątom, które dzielą ten wierzchołek, uśrednić ich normalne powierzchnie i uzyskać normalny wierzchołek.

Jaki jest najbardziej wydajny algorytm i struktura danych do osiągnięcia tego celu?

Jest to naiwne podejście (kod pseudo pytona):

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

Czy istnieje bardziej efektywne podejście?

questionAnswers(2)

yourAnswerToTheQuestion