Тетраэдризация

В трёхмерном случае симплексом является тетраэдр, поэтому аналогом триангуляции становится тетраэдризация: объёмную область нужно разбить на тетраэдры так, чтобы они не накладывались друг на друга, целиком покрывали область и попарно пересекались только по общим граням, рёбрам или вершинам. Как и в двумерном случае, мы требуем выполнения условия Делоне — теперь уже для описанной сферы тетраэдра: внутри неё не должно быть других вершин сетки. Это условие помогает избегать части плохо вытянутых элементов, но само по себе не гарантирует хорошую форму всех тетраэдров; поэтому дальше дополнительно задаются критерии качества и выполняется оптимизация сетки.

Минимальный трёхмерный симплекс строится на четырёх точках:

Почему трёхмерный случай сложнее

Классическая схема «разделяй и властвуй», описанная для триангуляции в приложении, в трёхмерном случае существенно усложняется. При сшивании двух частей в плоскости зазор между ними — это пара цепочек рёбер, и заполнить его легко. В пространстве зазор образуется уже целым набором граней, и его приходится корректно закрывать тетраэдрами. Кроме того, локальная перестройка Делоне в плоскости — это простая замена диагонали четырёхугольника (flip 2–2), тогда как в пространстве элементарные перестройки (flip 2–3 и 3–2) меняют само число тетраэдров и требуют аккуратной проверки допустимости. Наконец, в отличие от плоскости, не всякую трёхмерную область можно разбить на тетраэдры без добавления новых точек — классический пример: многогранник Шёнхардта.

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

Область как кусочно-линейный комплекс

Расчётная трёхмерная область задаётся своей границей — замкнутой ориентированной триангулированной поверхностью. Такое описание называют кусочно-линейным комплексом (PLC, piecewise linear complex): набор вершин, рёбер и плоских граней, согласованно покрывающих поверхность тела. Это прямой трёхмерный аналог граничных контуров из двумерной триангуляции: там границей служили замкнутые ломаные, здесь — замкнутые треугольные сетки.

Для трёх характерных тел поверхность строится явно:

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

Ограничения: восстановление рёбер и граней

Грани и рёбра граничной поверхности играют роль ограничений — так же, как непересекаемые рёбра в двумерной триангуляции Делоне с ограничениями. Они обязаны присутствовать в итоговой сетке: тетраэдры не должны пересекать границу тела по внутренности, а острые рёбра (рёбра куба, кромки торцов цилиндра) должны сохраняться как рёбра сетки, а не «срезаться». Острые рёбра выделяются автоматически по двугранному углу между смежными гранями и восстанавливаются отдельно, после чего поверхность остаётся вписанной в объёмную сетку.

Критерии качества

В отличие от плоского случая, где плотность задавалась лишь числом и расположением точек, объёмная сетка строится под управлением полей размера и критериев формы:

• ограничение на размер тетраэдра управляет плотностью сетки: в CGAL оно задаётся параметром cell_size, то есть верхней границей радиуса описанной сферы тетраэдра. В демонстрационной утилите целевой масштаб оценивается как $\sqrt[3]{V/n}$, где $V$ — объём тела, а $n$ — заданное число точек;
• ограничение на отношение радиуса описанной сферы к кратчайшему ребру (radius–edge ratio) не даёт появляться многим вытянутым тетраэдрам-«иглам»; плоские «сливеры», которые этот критерий не отлавливает, устраняются финальной оптимизацией;
• критерии аппроксимации границы (угол, размер и отклонение граничных треугольников) управляют точностью поверхностной сетки, а для шара и цилиндра точность также зависит от того, насколько хорошо построена исходная полиэдральная аппроксимация поверхности.

Алгоритм добавляет внутренние точки (вставка по Делоне) и измельчает сетку до тех пор, пока все критерии не будут выполнены. Затем финальная оптимизация — сдвиг вершин и выдавливание сливеров, то есть перевзвешивание вершин для удаления почти плоских тетраэдров, — улучшает форму элементов.

Реализация

Низкоуровневое построение делегировано модулю Mesh_3 библиотеки CGAL — той же, что используется для двумерной триангуляции. Граничная поверхность каждого тела представляется типом Mesh_polyhedron_3<K>::type, область — классом Polyhedral_mesh_domain_with_features_3 (с автоматическим выделением острых рёбер), а собственно тетраэдризация выполняется вызовом make_mesh_3 с описанными выше критериями (Mesh_criteria_3). Используется ядро точных предикатов Exact_predicates_inexact_constructions_kernel, благодаря чему проверки принадлежности сфере и ориентации тетраэдров вычисляются устойчиво. На выходе получается набор тетраэдральных симплексов вида (4.3)$\displaystyle T$ $\displaystyle = (p_1, p_2, p_3, p_4).$, по которым на дальнейших этапах строятся локальные матрицы и собирается глобальная система метода конечных элементов.

Примеры

Все сетки ниже — реальные результаты утилиты tetrahedralize вычислительного ядра; в тексте указаны параметры полной тетраэдральной сетки. Интерактивные модели показывают её поверхностную оболочку: поверхность можно вращать мышью или пальцем, а раскраска по освещённости подчёркивает граничные грани тетраэдров.

На рисунке «Куб» показана тетраэдризация куба со стороной 1 при $n$ $= 600$: 674 вершины, 2809 тетраэдров. Грани куба плоские, поэтому вся «кривизна» сетки уходит внутрь, а на поверхности видны треугольные грани приграничных тетраэдров; рёбра куба сохранены как острые.

Рисунок «Шар» показывает работу поверхностной аппроксимации: икосферная граница шара ($R$ $= 1$, $n$ $= 800$; 737 вершин, 3417 тетраэдров) приближает сферу с заданной точностью, без острых рёбер.

Наконец, на рисунке «Полый цилиндр» показан полый цилиндр ($R$ $= 1$, $r$ $= 0.4$, высота $1.5$) при $n$ $= 1000$: 1118 вершин, 4588 тетраэдров. Сквозное отверстие и кромки торцов сохранены ограничениями: острые рёбра выделены по двугранному углу и восстановлены в сетке.