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

Question

[KillAstronauts]

Привет!

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

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

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



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



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



Есть ли какой-нибудь алгоритм? Возможно ли это сделать с помощью каких-то библиотек (например OpenGL или DirectX)?

Answer 1

[Mrrl]

В общем, делается так.
Пусть фигура задана набором треугольных граней с известной ориентацией. В каждом ребре сходится чётное число граней (возможна, например, фигура из двух тетраэдров, склеенных по ребру), и при обходе любого ребра ориентации граней, сходящихся в нём, чередуются (например, идут грани ABC, BAD, ABE, BAF). Даже если в исходной модели таких странных рёбер нет, они могут возникнуть на промежуточном этапе.
Выбираем любые две грани со следующими свойствами:
- у них есть общее ребро AB;
- при обходе этого ребра они являются последовательными
- внутренний угол между этими гранями меньше 180 гр.
Такие грани найдутся всегда. Пусть это ABC и BAD.
Рассмотрим тетраэдр ABCD. Проверим, нет ли у него внутри других вершин. Если нет - заменим грани ABC и BAD на CAD и BCD (вырезав, тем самым, ABCD из модели). Если есть - возьмём ту вершину E из них, которая ближе всего к грани ABC, и заменим грань ABC на три грани ABE, AEC, EBC.
После этого просмотрим грани, и если оказалось, что какая-то грань встречается дважды с противоположными ориентациями (ABC и ACB) - выбрасываем обе копии.
Процесс повторяем, пока все грани не исчезнут.
Всё.

Comments

[KillAstronauts]

Еще не думал над вашем алгоритмом, но звучит хорошо. Правда терзают сомнения...

Вы написали "Пусть фигура задана набором треугольных граней с известной ориентацией.", но это не так. Мне предоставлен только массив прямых/линий. Причем линии могут объединяется в многоугольники, например - квадраты (как у меня на картинках), поэтому придется достраивать ребра для создания треугольников и тетраэдров. Мне даны только прямые. Я не знаю никаких граней, и куда смотрят нормали граней (которых нет). В этом и проблема :)

Эту задачу можно решить с такими входными данными (массивом линий каркаса)?

[Mrrl]

KillAstronauts: В таком виде задача неразрешима. Представьте себе, что вам дали каркас перспективной проекции гиперкуба (как его обычно рисуют - один куб внутри другого, вершины внешнего и внутреннего соединены рёбрами). Что это за фигура? Вы можете взять, например, кольцо из четырёх усечённых пирамид, идущих вокруг вертикальной оси внутреннего куба. Все 32 ребра окажутся использованными. Но такое же кольцо можно провести вокруг любой из горизонтальных осей - получится три разных многогранника. Какой из них правильный?
Задача построения многогранника по рёберному каркасу - совершенно отдельная задача, никак не связанная с разбиением на тетраэдры (кроме того, что выход одной задачи является входом другой). Надо над ней думать. Вам придётся найти все плоские циклы на графе рёбер, убедиться, что грань, построенную на этом цикле, не пересекают другие рёбра, и как-то отловить случай "грани с дыркой", когда есть два квадрата - один внутри другого - лежащие в одной плоскости, но вершины которых не соединены рёбрами друг с другом. Потом построить мультиграф, в котором вершинами будут заданные рёбра, а "рёбрами" - найденные потенциальные грани. И найти в нём все подграфы, в которых каждая вершина принадлежит ровно двум "рёбрам" (эквивалентная формулировка: из набора множеств выбрать поднаборы, образующие покрытия, в которых каждый элемент принадлежит ровно двум множествам). После этого каждый набор проверить на геометрическую корректность - потому что по набору рёбер октаэдра алгоритм вполне может построить самопересекающуюся поверхность Штейнера. Наборы, которые дадут корректную поверхность - и есть ответ к этой задаче.

[KillAstronauts]

Во, вот это похоже на правду, правда очень горькую х)
Не знаете ли библиотеки способны сделать это?

[Mrrl]

Не знаю. Я в таких вопросах библиотекам не доверяю - что их авторы могут понимать? Самому как-то надёжнее.

Answer 2

[Армянское Радио]

Триангуляция Делоне обобщается на случаи любой размерности.

Comments

[KillAstronauts]

Не понял вас, не мог ли бы вы развернуть ответ? Триангуляция Делоне - это первое на что натыкаешься когда ищешь информацию по триангуляции. В 2D это все отлично понятно, но как это применить в 3D я не пойму.

[Армянское Радио]

KillAstronauts: В 2D при триангуляции треугольник добавляется так, чтобы в описанную около него окружность не попадало ни одной точки

В 3D тетраэдр добавляется так, чтобы чтобы в описанную около него сферу не попадало ни одной точки.

Вычислять координаты центра описанной сферы удобно при помощи определителя Кэли-Менгера.

[Eddy_Em]

KillAstronauts: Можно отсюда начать gts.sourceforge.net

[Eddy_Em]

И даже готовое в 3D есть: linux.die.net/man/1/triangulate

[KillAstronauts]

Армянское Радио: Так как это поможет избежать заполнения отверстий? Мне не ясно как определить те объемы, которые не нужно заполнять.

Японский Городовой: Надо будет глянуть, пока не ясно, но выглядит мощно х)

[Армянское Радио]

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

[Mrrl]

Армянское Радио: Проблема в том, что многие тетраэдры окажутся разрезанными границей модели, тем более, что сама модель невыпукла. Работает ли тетрангуляция для области с произвольной топологией и произвольной триангуляцией края?

[Армянское Радио]

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

[Mrrl]

Армянское Радио: Но чтобы узнать, насколько её надо измельчить, надо сначала понять, в каких случаях эти тетраэдры могут образоваться?

[Армянское Радио]

Mrrl: там критерий можно вывести - так как при триангуляции Делоне добавляются только симплексы, описанные сферы которых не содержат других точек, достаточно измельчить границу так, чтобы расстояние между соседними точками не превосходило половины минимального расстояния от границы до точек внутри объекта.

[KillAstronauts]

Армянское Радио: Так у меня "ненужные" тетраэдры могу быть и внутри объема. Представьте что есть куб, и внутри куба был вырезан (булево вычитание) более маленький куб. Проблема в том, что я не знаю как не заполнить этот маленький куб в результате триангуляции.

Mrrl, Армянское Радио я перезалил картинки, думаю сейчас будет ясно, что я хочу получить. Мне нужно заполнить объем какой то фигуры, от которой у меня есть "скелет". Я не вижу другого выхода, кроме создания тетраэдров. Но я не могу понять как написать алгоритм, чтобы он не заполнял "впуклости" и отверстия. Не стоит задачи сделать мелкий мэш, главное - заполнить объем.

[Mrrl]

KillAstronauts: Несколько вопросов:
1) нужна ли эффективность, или алгоритм, например, за N^4 годится?
2) Топология фигуры может произвольной - и шар, и тор, и шар с полостями и т.д.?
3) Как фигура задана?

Answer 3

[alec_kalinin]

Исходный код разных алгоритмов триагуляции и ссылки на научные статьи по этой теме можно глянуть по ссылке: geuz.org/gmsh/. На мой взгляд, gmsh очень неплохой мешер.

Answer 4

[vitalijlysanov]

Сохранить в формате STL, который только из треугольников. В общем случае можно выбрать качество преобразования. Прямоугольник всегда разбивается на два треугольника. Результат координат точек треугольников можно получить в текстовом формате.