Перевернута ли замкнутая полигональная сетка?

Question

У меня есть приложение для 3D-моделирования. Сейчас я рисую сетки с двух сторон, но я бы хотел переключиться на односторонние, когда объект закрыт.

Если полигональная сетка замкнута (без граничных ребер / полностью периодическая), кажется, что я всегда должен быть в состоянии определить, перевернут ли объект в данный момент, и автоматически исправить.

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

Одна вещь, о которой я думал, это взять ограничивающий прямоугольник, найти самую высокую точку и посмотреть, нет ли ее нормальных точек вверх или вниз - если она внизу, то объект переворачивается.

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

Есть ли надежный и простой способ сделать это? Надежный и тяжелый тоже сработает ..:)

Answer 1

Это надежный, но медленный способ добраться туда:

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

Измерьте угол между этим отрезком и нормалью треугольника.

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

При наличии нечетного числа пересечений угол между нормалью и отрезком должен составлять <180. Если есть четное число, оно должно быть> 180.

Если число пересечений четное, числа следует поменять местами.

Это должно работать для очень сложных поверхностей, но они должны быть закрыты, или это сломается.

Answer 2

«Я рисую сетки двухсторонними»

Почему ты это делаешь? Если вы используете OpenGL, есть гораздо лучший способ сэкономить всю работу. Применение:

glLightModeli(GL_LIGHT_MODEL_TWO_SIDE, 1);

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

Как правило, проблема, с которой вы сталкиваетесь, является открытой проблемой при обработке геометрии, и в AFAIK не существует надежного общего способа, который всегда может определить ориентацию. Как вы предлагаете, есть эвристики, которые работают почти всегда.
Другой подход напоминает известный алгоритм «точка-многоугольник»: выберите вершину на сетке и направьте луч от нее в направлении нормали. Если луч попадает на четное число граней, то нормаль направлена ​​наружу, если она нечетна, то нормаль направлена ​​внутрь. обратите внимание, чтобы не считать точку происхождения как пересечение. Этот подход будет работать только в том случае, если сетка является замкнутым коллектором, и он может достигать некоторых краевых случаев, если луч проходит точно между двумя полигонами, так что вы можете захотеть сделать это несколько раз и набрать лидирующий голос.