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

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

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

Наивный подход таков (псевдо-код 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]])

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


algorithm graphics normals gouraud
person Jayesh    schedule 03.11.2012    source источник

Ответы (2)


arrow_upward
4
arrow_downward

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

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

person Martin Beckett    schedule 03.11.2012
comment
Я думаю, что это то же самое, что я делаю в псевдокоде, который я написал в вопросе. Наверное, нет более эффективного подхода. - person Jayesh; 08.02.2013

arrow_upward
3
arrow_downward

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

Треугольник, который не присоединен к другим треугольникам, не может быть «сглажен». Он плоский. Только когда у лица есть соседи, можно подумать о том, чтобы сгладить их вместе.

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

A --- B
  \ /
   C

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

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

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

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

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

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

person Drew Noakes    schedule 07.02.2013