2D алгоритм контура для проецируемой 3D сетки

Question

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

Проблема: Найти 2-мерный контур спроецированной произвольно повернутой сетки на произвольной плоскости.

Проекция проста. Задача состоит в том, чтобы найти «корпус» спроецированных ребер треугольника на плоскости. Мне нужна помощь с вводом / указателями при исследовании этого алгоритма. Для простоты можно предположить, что трехмерные ребра проецируются прямо на плоскость xy.

Answer 1

• Начните с самой правой точки (точки с наибольшей координатой x)
• Получить все ребра с этой точки
• Следуйте за ребром с наименьшим углом к ​​положительной оси x, а также добавьте его в набор решений
• Из достигнутой точки следуйте и добавьте ребро с наименьшим углом к ​​ребру, из которого вы пришли
• Повторяйте, пока не достигнете исходной точки

Answer 2

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

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

Наконец, вы можете объединить края оболочки в одно кольцо, соединив их вместе.

Answer 3

Двухмерный контур проекции сетки является подмножеством проекции его ребер.

Используя это наблюдение, можно определить двухмерный контур, используя следующий метод:

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

Обратите внимание, что этот метод сообщит все края, которые ортогональны плоскости проекции, даже те, которые не видны с точки зрения плоскости проекции. Например, с помощью тора он найдет внутренние и внешние контуры, даже если торус повернут таким образом, что его внутреннее отверстие не видно с точки зрения плоскости проекции. Чтобы разобраться, какие края видны, вам понадобится какой-то тест видимости. Если предполагаемое использование предназначено для отображения пользователем, вы можете использовать буфер глубины, рассчитанный с помощью матрицы ортогональной проекции, для визуализации геометрии с точки зрения плоскости проекции и выполнить некоторое z-тестирование, чтобы определить, какие края видны с плоскости. Если вам нужна точность, вам необходимо выполнить пересечение луча / треугольника, чтобы определить видимость.

Answer 4

Техника альфа-форм, упомянутая в этом вопросе, обрабатывает общий набор точек, где связи вершин неизвестны:

Существует ли эффективный алгоритм для создания 2D вогнутой оболочки?

Однако, поскольку вы уже знаете информацию о «лице», которую можно сохранить с помощью проекции, это, вероятно, не лучший подход.

Алгоритм грубой силы может быть осуществим, особенно если используются пространственные сортирующие структуры. например, для каждого аспекта:

1. Фасет проекта на плоскости
2. Проверьте, полностью ли окружен проецируемый фасет существующей геометрией, если да: сделано (нет необходимости расширять проецируемый силуэт)
3. Если точки выходят за пределы существующей геометрии, выполните пересечения треугольник-треугольник, чтобы определить, какие части выпадают за пределы, построить произвольный н-гон (возможно, вогнутый), чтобы заполнить недостающее пространство, а затем нарезать н-гон на треугольники

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

Answer 5

Просто добавлю: очень интуитивно понятный способ найти края в проекции - это выборка задней поверхности! Любое ребро между выбракованным и необработанным лицом должно быть контуром. Если вы хотите скрыть внутренние края, просто используйте z-буфер. Выделение задних граней - это просто порядок вершин после проекции и очень дешевый для вычисления.

Answer 6

Это просто вопрос проецирования точек xyz в точки x'Y 'на произвольной плоскости и затем просто выпуклой оболочки в этих координатах?