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

1) Для каждого элемента массива "особых точек" находится ближайший узел первичной сетки и передвигается в эту точку с сохранением всех связей.

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

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

4) В итоге проводится отсечение всех фрагментов первичной сетки, оставшихся за пределами заданной области. (Иначе говоря, удаляются все узлы и ребра первичной сетки, лежащие вне заданной области).

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

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

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

3. Методы на основе критерия Делоне

В первую очередь напомним, что такое критерий Делоне. Говорят, что треугольная сетка на плоскости удовлетворяет критерию Делоне (или является триангуляцией Делоне), если внутрь окружности, описанной вокруг любого треугольника, не попадают никакие другие узлы этой сетки. Этот термин также употребляется и по отношению к треугольнику сетки: треугольник удовлетворяет критерию Делоне (или условию "пустой окружности"), если критерию Делоне удовлетворяет сетка, составленная только из самого треугольника и соседних с ним треугольников [2, 6].

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

Триангуляция Делоне обладает рядом интересных свойств [2, 23, 30]. В частности, триангуляция Делоне обладает наибольшей суммой минимальных углов всех своих треугольников, а также наименьшей суммой радиусов описанных вокруг треугольников окружностей среди всех возможных сеток на той же системе точек. Поскольку величины минимальных углов явным образом фигурируют в некоторых оценках качества аппроксимации [4], можно сказать, что триангуляция Делоне для заданного набора точек в определенном смысле является оптимальной.

Алгоритмы построения сеток на основе критерия Делоне впервые были предложены Чарльзом Лоусоном (Charles Lawson) и Дэйвом Уотсоном (Dave Watson) [43]. За короткое время их идеи были существенно развиты, и в настоящий момент проблема двумерной триангуляции методами на основе критерия Делоне фактически является закрытой. Разработаны быстрые и эффективные алгоритмы построения и оптимизации сеток, в том числе и в сложных (двумерных) областях [2, 3].

Рис. 6. Сетка, удовлетворяющая критерию Делоне (слева), и не удовлетворяющая ему (справа).

При попытках обобщить идеи алгоритмов на случай трех измерений обнаружился ряд проблем. Во-первых, выяснилось, что критерий Делоне в трехмерном случае не работает в том смысле, что сетка, удовлетворяющая критерию Делоне, не максимизирует минимальные углы[2]. Во-вторых, обнаружилось, что в пространстве не работают также и алгоритмы последовательного улучшения. Остановимся на этом подробнее.

В двумерном случае существует простой метод приведения произвольной триангуляции к триангуляции Делоне. Идея основана на том факте, что пару треугольников, не удовлетворяющих критерию Делоне, можно заменить на пару дуальных к ним треугольников, которые уже обязательно удовлетворяют критерию. Это достигается перестановкой внутреннего ребра четырехугольника, образованного треугольниками (см. рис. 6). Операцию (так называемый "флип", от англ. flip) продолжают итерационно для каждой пары треугольников, не удовлетворяющих критерию, до тех пор, пока такие треугольники остаются.

У двумерного "флипа" есть и трехмерный аналог, хотя основанный на другой идее. Оказывается, почти любые два соседних тетраэдра можно превратить в три. Для этого достаточно вставить внутрь шестигранника, образованного тетраэдрами, внутреннее ребро (рис. 7), причем сделать это можно единственным образом. Слово "почти" стоит здесь потому, что если любые три вершины этого шестигранника лежат на одной прямой либо четыре его вершины лежат в одной плоскости, то эта операция приведет к образованию вырожденных тетраэдров. Операция замены 2 тетраэдров на 3 и наоборот называется "трейд[3]" (от англ. trade). Как и "флип", "трейд" позволяет заменять элементы, не удовлетворяющие критерию Делоне, на элементы, ему удовлетворяющие.

Рис. 7. "Трейд" - замена 2 тетраэдров на 3

Попытки использовать "трейд" для приведения произвольной трехмерной сетки к триангуляции Делоне закончились неудачно, поскольку такие алгоритмы очень часто зацикливались в локальных оптимумах. Вместе с тем не так давно был получен важный теоретический результат: канадский математик Б. Джо (Barry Joe) доказал, что если к уже существующей триангуляции Делоне добавить новые тетраэдры (разбив один из внутренних или присоединив тетраэдр к внешней грани), то полученную сетку можно гарантированно привести к триангуляции Делоне с помощью последовательных "трейдов" [23]. Этот факт играет огромную роль в построении триангуляций Делоне с ограничениями.

3.1. Построение триангуляции Делоне на заданном наборе точек

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

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