Как разбить многогранник на тетраэдры с помощью TetGen?
Необходимо у многогранников находить объем. Один из способов это сделать, разбить многогранник на тетраэдры, желательно чтобы число тетраэдров было наименьшим, а, соответственно, размер каждого тетраэдра максимальным. В данной теме я абсолютный новичок, прочитал, что тетраэдрическую сетку можно построить с помощью библиотеки С++ TetGen. Она простая в использовании, как 3 рубля, и нужно дергать одну единственную функцию tetrahedralize(). Но у меня серьезный затык в понимании основ:
1) Правильно ли я понимаю, что тетраэдрическая сетка многогранника и разбиение многогранника на тетраэдры это одно и то же?
2) Что такое facets и segments многогранника? Из примеров вроде бы понял, что одно из них это грань, а второе нужно для обозначения вырезов, пазов и прочего.
Теперь вопросы по самой библиотеке TetGen, может кто-то её использовал:
1) Как получить набор этих самых тетраэдров после разбиения фигуры? Был бы очень благодарен простому примеру, например, на кубике. Т.е. задать вершины я могу, но опять возникает затык с заданием facets и segments и извлеканием тетраэдров после вызова tetrahedralize().
2) Библиотека принимает много критериев оптимальности разбиения на тетраэдры. Как мне указать нужный мне - тетраэдры максимального объема\размера (или другими словами, минимальное число тетраэдров)?
Решение задачи зависит от типа ваших многогранников - выпуклые или нет, с плоскими гранями или нет, насколько точный объем нужен.
Разбиение многогранника на тетраэдры действительно дает возможность вычисления объема многогранника через вычисление определителей.
Только если грани многогранника не плоские, точно описать тетраэдрами многогранник уже не получится и будет иметь место ошибка приближения и, возможно, фокусы с усреднением по нескольким видам разбиения.
Если вам нужен объем, думаю, не важно, много или мало тетраэдров у вас в итоге получится.
Для разбиения на тетраэдры для вычисления объема многогранника не стоит использовать генераторы типа TetGen или NetGen и подобные. Эти библиотеки решают задачу построения сетки, годной для расчетов, или для дальнейшего построения более сложных расчетных сеток, т.е. являются инструментами решения более сложных задач.
Скорее полезным будет посмотреть в сторону алгоритмов и библиотек вычислительной геометрии - CGAL, например.
Ради интереса можно поиграться с пакетом Salome, там можно строить геометрию и сетки, в том числе тетраэдральные, там же в кодах есть алгоритмы разбиения многогранников на тетраэдры, но не помню, есть ли там общий случай.
В самом простом варианте выпуклого многогранника - разбиваете на треугольники грани, ставите точку в геометрический центр многогранника - из трех точек треугольников и точки центра формируете набор тетраэдров.
В итоге я разобрался с TetGen, он оказался довольно простым, подключил к проекту 2 файлика, дернул 1 метод и всё работает. Работает очень быстро.
Подскажите, пожалуйста, почему Вы его не советуете, на so как раз многие советуют именно TetGen?
Относительно числа тетраэдров. У меня несколько сотен фигур, если каждую разбить не на 1000 тетраэдров, а допустим на 100, то и объем будем вычислять уже не у 10*n тетраэдров, а у n.
becks:
Я не советую TetGen так как заранее посчитал, что у вас достаточно простые многогранники, для которых можно написать конкретные простые алгоритмы разбиения на тетраэдры. А с какими фигурами вы работаете и в какой предметной области?
Пусть у вас несколько сотен фигур, думаю, все равно 99.99% времени будет тратится на тетраэдризацию. Вычисление объема будет занимать копейки. На то же выделение памяти скорее уйдет больше.
Думаю - сотни объектов не должно быть критично, если это не сильно сложные модели.
TetGen на самом деле относительно быстр. Как всегда, решение зависит от ваших целей и ограничений.
Чтобы получать как можно меньше тетраэдров, обычно в сеточных генераторах нужно задать большой размер линейного элемента (равный или больше линейных размеров вашей фигуры), тогда генератор будет строить по возможности максимально большие тетраэдры.
На самом деле, многогранники у меня действительно довольно простые, но бывают редкие случаи, когда они содержат пазы, сквозные отверстия и различные углубления. Многогранники - это отсеки и помещения судна.
Еще раз, большое спасибо за Ваш ответ.
Простой
