@KillAstronauts

3D триангуляция?

Привет!

Не знаю как решить задачу с 3D триангуляцией. Не отправляйте меня сразу в гугл, я уже там был, но остались вопросы. Давайте я сначала опишу свою задачу.

В качестве входных данных я получаю «скелет» 3D объекта, состоящий из линий. Мне нужно триангулировать этот объем. Вроде звучит просто, но решения я не нашел.

Допустим я получил «скелет» объекта, сразу стоит заметить, что объект может быть «впуклым», это и является сутью проблемы. Мне нужно заполнить этот объем тетраэдрами, причем нет цели в достижении большой сегментации. На картинке ниже показан «скелет» (слева) и то, что должно получиться (справа).

372a72b9cc59.png

Для того чтобы заполнить объем «скелета» тетраэдрами, необходимо создавать дополнительные ребра. На картинке ниже изображено, как это примерно должно происходить.

747ec6b4cb89.png

Именно в создании новых ребер заключается проблема. Так как фигура может быть «впуклой», то новое ребро может быть построено вне нужного объема, вследствие чего получим не правильный объект.

bcd483d9079f.png

Есть ли какой-нибудь алгоритм? Возможно ли это сделать с помощью каких-то библиотек (например OpenGL или DirectX)?
  • Вопрос задан
  • 5195 просмотров
Решения вопроса 1
Mrrl
@Mrrl
Заводчик кардиганов
В общем, делается так.
Пусть фигура задана набором треугольных граней с известной ориентацией. В каждом ребре сходится чётное число граней (возможна, например, фигура из двух тетраэдров, склеенных по ребру), и при обходе любого ребра ориентации граней, сходящихся в нём, чередуются (например, идут грани ABC, BAD, ABE, BAF). Даже если в исходной модели таких странных рёбер нет, они могут возникнуть на промежуточном этапе.
Выбираем любые две грани со следующими свойствами:
- у них есть общее ребро AB;
- при обходе этого ребра они являются последовательными
- внутренний угол между этими гранями меньше 180 гр.
Такие грани найдутся всегда. Пусть это ABC и BAD.
Рассмотрим тетраэдр ABCD. Проверим, нет ли у него внутри других вершин. Если нет - заменим грани ABC и BAD на CAD и BCD (вырезав, тем самым, ABCD из модели). Если есть - возьмём ту вершину E из них, которая ближе всего к грани ABC, и заменим грань ABC на три грани ABE, AEC, EBC.
После этого просмотрим грани, и если оказалось, что какая-то грань встречается дважды с противоположными ориентациями (ABC и ACB) - выбрасываем обе копии.
Процесс повторяем, пока все грани не исчезнут.
Всё.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
gbg
@gbg
Баянист. Тамада. Услуги.
Триангуляция Делоне обобщается на случаи любой размерности.
Ответ написан
@alec_kalinin
Исходный код разных алгоритмов триагуляции и ссылки на научные статьи по этой теме можно глянуть по ссылке: geuz.org/gmsh/. На мой взгляд, gmsh очень неплохой мешер.
Ответ написан
@vitalijlysanov
Сохранить в формате STL, который только из треугольников. В общем случае можно выбрать качество преобразования. Прямоугольник всегда разбивается на два треугольника. Результат координат точек треугольников можно получить в текстовом формате.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы