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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация

Низкоуровневое построение делегировано модулю Mesh_3 библиотеки CGAL — той же, что используется для двумерной триангуляции. Граничная поверхность каждого тела представляется классом Mesh_polyhedron_3, область — классом Polyhedral_mesh_domain_with_features_3 (с автоматическим выделением острых рёбер), а собственно тетраэдризация выполняется вызовом make_mesh_3 с описанными выше критериями (Mesh_criteria_3). Используется ядро точных предикатов Exact_predicates_inexact_constructions_kernel, благодаря чему проверки принадлежности сфере и ориентации тетраэдров вычисляются устойчиво. На выходе получается набор тетраэдральных симплексов вида (4.3)$$T = (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 тетраэдров. Сквозное отверстие и кромки торцов сохранены ограничениями: острые рёбра выделены по двугранному углу и восстановлены в сетке.