Построение тетраэдральных и гексаэдральных сеток в неявных областях

Задание областей сложной формы как нулевых изоповерхностей некоторой функции, напоминающей функцию расстояния со знаком, является достаточно гибким и универсальным механизмом геометрического моделирования. Неявные функции можно строить по поверхностной триангуляции, по набору плоских сечений, по «супу» из точек, ребер и плоских граней, по сплайнам, и все это можно комбинировать с наборами примитивов при помощи булевых операций. Для построения тетраэдральных сеток в неявных областях предложен итерационный метод самоорганизации точек, который позволяет распределить их по области согласно заданной функции характерного размера. При этом точки распределяются так, что острые ребра на поверхности аппроксимируются ребрами Делоне, без использования алгоритмов выделения острых ребер. Таким образом, одновременно строится объемная и поверхностная сетка. Этот алгоритм носит эвристический характер, но продемонстрировал работоспособность для достаточно сложных тестовых задач. В полученной сетке Делоне, как правило, присутствует небольшое число плоских тетраэдров. Для их удаления используется вариационный метод оптимизации с возможностью движения вершин сетки по границе области. По существу этот же вариационный метод используется для построения гексаэдральных сеток. При этом возникает проблема вариационного построения поверхностных сеток на неявных поверхностях, а также задача одновременной оптимизации объемных и поверхностных сеток. Для решения этой задачи используется итерационный метод, который можно отнести к классу методов проекции градиента. Критическим этапом в задаче построения структурированных гексаэдральных сеток является этап распутывания для построения допустимой начальной сетки. Предложена достаточно эффективная техника распутывания, позволяющая строить допустимые сетки с сотнями тысяч степеней свободы.