Особенности технической реализации алгоритмов на основе критерия Делоне

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

Типичная ошибка, допускаемая в реализации этого класса алгоритмов, заключается в использовании приближенных вычислений и операций, например, использование для сравнения не нуля (x>0.0), а заданной точности (x>EPS или x>-EPS). Такой подход вполне оправдан и верен во многих других случаях, но только не в методах на основе критерия Делоне.

К сожалению, простое увеличение точности не дает существенных результатов. Использование числовых типов с удвоенной точностью перестает работать уже на задачах средней сложности (сетки с несколькими тысячами узлов). Частичным решением этой проблемы может быть использование числовых типов с фиксированной запятой. За счет отдельного хранения в 24-байтной структуре целой и десятичной частей числа (в виде целых чисел), на указанных выше плохо обусловленных задачах можно добиться точности вплоть до 10 знака, что является уже более-менее допустимым результатом [11].

Также возможно использование так называемой "точной арифметики", модули для реализации которой уже разработаны для многих популярных прикладных языков программирования (С++, Фортран и др.). В точной арифметике все иррациональные числа представляются как набор предикатов (арифметических и алгебраических операторов) от рациональных/целых чисел и установленных констант (таких, как ,  и т.п.). То есть, например, в точной арифметике  - это действительно , а не 1,73205080756887729...

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

Иной путь улучшения ситуации - оптимизация процедур вычисления. Так, например, сотрудники исследовательского центра IBM Павло Кавальканти и Улисс Мелло сумели создать устойчивый алгоритм построения триангуляции Делоне, сведя все геометрические операции к двум предикатам: проверке условия "пустой сферы" и нахождению положения точки относительно заданной плоскости [10].

Методы исчерпывания

Впервые идея метода исчерпывания была предложена Рейнальдом Лонером (R. Lohner), а его трехмерный вариант разработал профессор Гонконгского университета С.Х. Ло. Алгоритм Ло вот уже многие годы успешно используется в программном комплексе ANSYS для дискретизации произвольных объемных областей.

Общая идея этого класса методов заключается в последовательном изымании из заданной области фрагментов тетраэдрической формы до тех пор, пока вся область не окажется "исчерпана". Впрочем, этот легко представимый в воображении процесс на самом деле имеет мало общего с практической реализацией. Английское название "advancing front" (что можно перевести как "продвижение фронта"), пожалуй, лучше отражает сущность алгоритмов.

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

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

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

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

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

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

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

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

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