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

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

Существуют и другие, более сложные методы. Так, метод под названием "упаковка пузырьков" ("bubble packing") основан на физической аналогии заполнения области мыльными пузырьками. В данном приложении модель этого процесса, разумеется, сильно упрощена - до уровня сил отталкивания между центрами пузырьков. Возникающие при этом дополнительные (довольно значительные) затраты на решение системы дифференциальных уравнений компенсируются максимально оптимальным размещением узлов, позволяющим получить сетки с априори высоким качеством триангуляции [41]. Используются и другие варианты [5, 8, 9, 35, 42].

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

Алгоритм состоит из следующих шагов:

1. Формирование множества U - набора заданных узлов.

2. Создание так называемой "суперструктуры", представляющей собой произвольный выпуклый многогранник с треугольными гранями такой, что все заданные узлы лежат внутри него. Вершинами многогранника могут быть как элементы U, так и дополнительные узлы. В дальнейшем до определенного этапа с этими узлами обращаются как и со всеми остальными. В качестве суперструктуры может быть использован и тетраэдр.

3. Формирование множества G узлов сетки, куда переносятся все узлы U, использованные как вершины суперструктуры (если такие есть).

4. Если в качестве суперструктуры использован тетраэдр, производится переход к п. 5; иначе на основе узлов суперструктуры формируется триангуляция Делоне. Если в качестве суперструктуры использован правильный многогранник (октаэдр или икосаэдр), то это можно сделать следующим образом: выбрав произвольный узел из U, перенести его в G и путем вставки ребер между этим узлом и всеми вершинами многогранника сформировать сетку из n тетраэдров, где n - число граней, равное 8 или 20 соответственно. Эта сетка будет являться триангуляцией Делоне [22].

5.Поиск для всех тетраэдров сетки центров и радиусов описанной сферы.

6. Выбор произвольного узла q из множества U и перенос его в G, затем удаление всех тетраэдров, для которых q попадает внутрь описанной сферы. При этом в сетке образуется полость в виде многогранника, в общем случае имеющего звездную форму. При этом любой луч, исходящий из q, должен пересекать границу этого многогранника в единственной точке. Если обнаруживаются тетраэдры, для которых q лежит в плоскости одной из граней (это возможно в случае неоднозначности триангуляции Делоне, если, например, пять или больше точек лежат на одной сфере), то их тоже необходимо удалить. Заметим, что фактически ребро (или грань) удаляется только в том случае, если удаляются все смежные с ним тетраэдры; при этом ребра и грани суперструктуры не удаляются никогда. Новые тетраэдры образуются путем вставки ребер между q и вершинами этого многогранника. Доказано [23], что при этом получается триангуляция Делоне.

7. Нахождение для новообразованных тетраэдров центра и радиуса описанной сферы.

8. Если множество U не пусто, то переход к п. 6, иначе - к п. 9.

9. Удаление из сетки всех тетраэдров, в числе вершин которых есть вспомогательные узлы, использовавшиеся для построения суперструктуры. В результате получается сетка, построенная только на заданных узлах (G).

Двумерный аналог этого процесса проиллюстрирован на рис. 8.

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

Рис. 8. Двумерный вариант алгоритма на основе критерия Делоне

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

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

3.2. Триангуляции Делоне с ограничениями

Триангуляцией Делоне с ограничениями в виде поверхностей называют такую сетку, для которой внутрь сферы, описанной вокруг любого тетраэдра этой сетки, не попадают никакие другие видимые вершинам этого тетраэдра узлы сетки (считается, что точка а видима точке b (и наоборот), если отрезок [a,b] не пересекает никаких поверхностей ограничений). Что такое триангуляция Делоне с ограничениями, если ограничения представлены в том числе и отрезками, до сих пор общепринятого определения нет.

В двумерном случае проблема построения триангуляции Делоне с ограничениями давно и успешно решена, причем самыми разными способами [3]. Что касается трех измерений, то к настоящему времени разработано лишь несколько алгоритмов, и все они базируются на одном и том же принципе. Их идея заключается в том, чтобы сначала в заданной области построить триангуляцию Делоне без ограничений, а затем восстановить поверхности и линии ограничений путем локальной перестройки сетки. Различие между алгоритмами состоит как раз в том, как именно осуществляется эта перестройка [5, 6, 24, 25].

Рассмотрим один из вариантов такого алгоритма, основанный на идее
К. Хэзлвуд (Carol Hazlewood). В своей работе [21] она доказала, что возможно построить триангуляцию Делоне с ограничениями, ретриангулируя (только) те тетраэдры, которые пересекаются поверхностями ограничений. В статье Хэзлвуд этот факт доказывается для случая пересечения тетраэдра произвольным выпуклым многогранником. Для ясности упростим алгоритм, введя дополнительные несложные требования к входным данным. А именно, потребуем, чтобы поверхности ограничения были представлены либо плоскостями, либо слабо изогнутыми (радиус кривизны много больше линейных размеров элементов) сплайнами, а также, чтобы все угловые точки поверхностей ограничения использовались на первом этапе для построения триангуляции Делоне. В результате все тетраэдры построенной триангуляции могут пересекаться только либо "ребрами" поверхностей ограничений, либо самими поверхностями. Поскольку вариантов таких пересечений немного, для каждого из них можно использовать заранее подготовленный шаблон ретриангуляции. Процесс можно упростить еще больше, если предварительно добиться, чтобы все ребра ограничений были аппроксимированы цепочкой ребер триангуляции. Тогда тетраэдры смогут быть пересечены только плоскостями (сплайнами), а возможных вариантов такого пересечения всего ТРИ (рис. 9).