Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: итерационные методы (стр. 5 из 6)

Триангуляции границы является тем самым "фронтом", упоминаемым в названии. Используя какой-либо треугольник из фронта, можно на его основе построить тетраэдр, причем четвертой вершиной тетраэдра может быть либо другая вершина фронта, либо дополнительный узел, помещаемый внутрь заданной области. При изъятии полученного тетраэдра из фронта может быть удалено от 1 (случай вставки дополнительного узла) до 4 граней и одновременно добавлено от 1 до 3 новых граней. Таким образом, текущий фронт дискретизации постепенно продвигается в пространстве - откуда и само название "advancing front". Обновив данные о фронте, можно вновь изъять тетраэдр, снова обновить фронт и так далее, пока вся область не окажется "исчерпана".

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

Несмотря на кажущуюся простоту идеи, реализация алгоритма исчерпывания таит в себе ряд тонкостей (заметим, что реализация алгоритмов исчерпывания в двумерном случае намного проще). Самый сложный момент любого алгоритма исчерпывания заключается в проверке правильности построенного тетраэдра, ведь необходимо удостовериться, что этот новый тетраэдр не пересекается ни с какими уже существующими. Причем на каждой итерации алгоритма эта процедура с различными параметрами может вызываться от 5 до 20 раз (иногда и больше). От того, каким образом реализована эта проверка, главным образом и зависит производительность алгоритма.

Второй сложный момент является краеугольной проблемой трехмерной дискретизации. Нередка ситуация, когда в результате работы алгоритма образуются области, которые невозможно дискретизировать, не используя дополнительных внутренних узлов (в плоском случае любой многоугольник можно разбить на треугольники одними только внутренними ребрами).

Стоит также помнить, что во время работы алгоритма фронт может разбиться на несвязанные фрагменты.

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

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

Наконец, еще одна сложность связана с выбором текущей грани фронта для построения тетраэдра. Дело в том, что для этого весьма желательно использовать грань, вершинами которой являются узлы с наименьшими значениями внутренних телесных углов. В то время как вычисление планарных и двугранных углов тривиально, вычисление телесных углов представляет собой куда более трудоемкую задачу (особенно если учесть, что каждый телесный угол в данном случае может быть сформирован различным числом граней) [27, 28, 29, 30, 34].

Рис. 12. Триангуляция пространства вокруг модели самолета для решения задачи аэродинамики[6]

4.1. Пример алгоритма исчерпывания

Рассмотрим алгоритм исчерпывания, разработанный вторым автором данной работы и предназначенный для построения равномерных сеток в произвольных областях.

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

(то есть плотность их размещения должна быть на порядок больше плотности размещения узлов триангуляции.) Заметим, что, поскольку координаты этих узлов можно легко вычислять ( ), под этот массив не потребуется много памяти. Фактически, множество F будет описываться трехмерным массивом 1-битных булевых переменных (TRUE = точка существует, FALSE = точка удалена). Таким образом, хранение 8 миллионов элементов F потребует около мегабайта оперативной памяти. После формирования множества F из него удаляются все точки, лежащие вне заданной области. Оставшиеся точки будут представлять своего рода объемное растровое изображение заданной области. Именно с помощью множества F в этом алгоритме и решаются многие проблемы, указанные выше.

Поскольку алгоритм рассчитан на построение равномерных сеток, контрольная функция

считается константой, равной (объем правильного тетраэдра с ребром h плюс допуск 25%).

Далее производятся следующие действия:

1. Формируется множество узлов G, состоящее из вершин фронта (т.е. изначально в него входят все существующие узлы сетки); для каждого узла G проводится оценка телесного угла. Эта оценка сводится к нахождению числа существующих (т.е., неудаленных) точек F, находящихся от данного узла на расстоянии не более чем

(что требует существенно меньших затрат ресурсов, чем прямое вычисление телесных углов).

2. Находится вершина

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

3. Формируется множество

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

1) строго внутри этого тетраэдра нет ни одной удаленной точки F (существование таких точек на гранях допускается);

2) внутри этого тетраэдра нет других существующих узлов сетки, за исключением самих вершин этого тетраэдра;

3) тетраэдр не пересекается никаким существующим ребром сетки (считается, что тетраэдр пересекается ребром, не являющимся ребром этого тетраэдра, если у него с этим ребром есть хотя бы одна общая точка, не являющаяся вершиной этого тетраэдра.)[7];

4) объем тетраэдра не больше максимально допустимого (

).

Из всех тетраэдров (

) выбирается тетраэдр наилучшего качества [45] и производится переход к п. 5; если же тетраэдров, удовлетворяющих указанным условиям, не оказалось, то осуществляется переход к п. 4.

4. Находится такая точка

внутри еще неисчерпанной области, что:

1) тетраэдр (

) удовлетворяет всем условиям п. 3;

2) в шаре

нет ни одной удаленной точки F (это предотвращает размещение узла p слишком близко от граней и вершин существующих тетраэдров).

Вариант алгоритма поиска узла p рассмотрен ниже.

5. Удаляются все вершины F, попавшие внутрь (и на границы) сформированного тетраэдра. Затем фронт обновляется по следующей схеме: рассматривается каждая грань сформированного тетраэдра и

1) если грань является гранью фронта, то она удаляется из фронта;

2) если грань НЕ является гранью фронта, она добавляется во фронт.