Наиболее эффективный алгоритм вычисления нормалей вершин из набора треугольников для затенения Гуро

Question

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

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

Наивный подход заключается в следующем (псевдо-код 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]])

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

Answer 1

Посетите каждый треугольник, вычислите нормаль для каждого треугольника, ДОБАВЬТЕ их в нормаль для каждой угловой вершины.
Затем в конце нормализуйте нормали для каждой вершины.

Тогда, по крайней мере, вам нужно пройти только треугольники один раз, и вы сохраняете только одну нормаль / вершину.

Answer 2

Каждая вершина принадлежит одной или нескольким граням (обычно треугольники, иногда квадраты - я буду использовать треугольники в этом ответе).

Треугольник, который не привязан ни к каким другим треугольникам, не может быть "сглажен". Это квартира. Только когда у лица есть соседи, вы можете рассуждать о сглаживании их вместе.

Для вершины, где встречаются несколько граней, вычислите нормали для каждой из этих граней. Перекрестное произведение двух векторов возвращает перпендикулярный (нормальный) вектор, чего мы и хотим.

A --- B
  \ /
   C

v1 = B - A
v2 = C - A
normal = v1 cross v2

Будьте осторожны, чтобы рассчитать эти векторы последовательно для всех граней, иначе ваш нормальный может быть в отрицательном направлении, что вам нужно.

Таким образом, в вершине, где встречаются несколько граней, суммируйте нормали граней, нормализуйте результирующий вектор и примените его к вершине.

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

РЕДАКТИРОВАТЬ есть действительно хорошее видео, показывающее технику для вычисления затенения Гурада, хотя это не обсуждает фактический алгоритм.

Возможно, вы захотите взглянуть на источник Three.js. В частности, computeVertexNormals функция. Не поддерживает сохранение острых краев. Эффективность вашего алгоритма во многом зависит от того, как вы моделируете свои примитивы.