Рис. 5. Пример триангуляции простой трехмерной области (призма с двумя цилиндрическими отверстиями) методом граничной коррекции. Показаны только граничные узлы "видимых" сплайнов.
Триангуляция Делоне обладает рядом интересных свойств [2, 23, 30]. В частности, триангуляция Делоне обладает наибольшей суммой минимальных углов всех своих треугольников, а также наименьшей суммой радиусов описанных вокруг треугольников окружностей среди всех возможных сеток на той же системе точек. Поскольку величины минимальных углов явным образом фигурируют в некоторых оценках качества аппроксимации [4], можно сказать, что триангуляция Делоне для заданного набора точек в определенном смысле является оптимальной.
Алгоритмы построения сеток на основе критерия Делоне впервые были предложены Чарльзом Лоусоном (Charles Lawson) и Дэйвом Уотсоном (Dave Watson) [43]. За короткое время их идеи были существенно развиты, и в настоящий момент проблема двумерной триангуляции методами на основе критерия Делоне фактически является закрытой. Разработаны быстрые и эффективные алгоритмы построения и оптимизации сеток, в том числе и в сложных (двумерных) областях [2, 3].
Рис. 6. Сетка, удовлетворяющая критерию Делоне (слева), и не удовлетворяющая ему (справа).
При попытках обобщить идеи алгоритмов на случай трех измерений обнаружился ряд проблем. Во-первых, выяснилось, что критерий Делоне в трехмерном случае не работает в том смысле, что сетка, удовлетворяющая критерию Делоне, не максимизирует минимальные углы Следует отметить, что свойство минимизации радиусов описанных сфер сохраняется; более того, как показывает работа сотрудника исследовательского центра IBM В.Т. Раджана (V.T. Rajan), это справедливо и для n-мерного случая [33]. Во-вторых, обнаружилось, что в пространстве не работают также и алгоритмы последовательного улучшения. Остановимся на этом подробнее.
В двумерном случае существует простой метод приведения произвольной триангуляции к триангуляции Делоне. Идея основана на том факте, что пару треугольников, не удовлетворяющих критерию Делоне, можно заменить на пару дуальных к ним треугольников, которые уже обязательно удовлетворяют критерию. Это достигается перестановкой внутреннего ребра четырехугольника, образованного треугольниками (см. рис. 6). Операцию (так называемый "флип", от англ. flip) продолжают итерационно для каждой пары треугольников, не удовлетворяющих критерию, до тех пор, пока такие треугольники остаются.
У двумерного "флипа" есть и трехмерный аналог, хотя основанный на другой идее. Оказывается, почти любые два соседних тетраэдра можно превратить в три. Для этого достаточно вставить внутрь шестигранника, образованного тетраэдрами, внутреннее ребро (рис. 7), причем сделать это можно единственным образом. Слово "почти" стоит здесь потому, что если любые три вершины этого шестигранника лежат на одной прямой либо четыре его вершины лежат в одной плоскости, то эта операция приведет к образованию вырожденных тетраэдров. Операция замены 2 тетраэдров на 3 и наоборот называется "трейд В англоязычной литературе также часто называется "2-to-3 flip" " (от англ. trade). Как и "флип", "трейд" позволяет заменять элементы, не удовлетворяющие критерию Делоне, на элементы, ему удовлетворяющие.
Рис. 7. "Трейд" - замена 2 тетраэдров на 3
Попытки использовать "трейд" для приведения произвольной трехмерной сетки к триангуляции Делоне закончились неудачно, поскольку такие алгоритмы очень часто зацикливались в локальных оптимумах. Вместе с тем не так давно был получен важный теоретический результат: канадский математик Б. Джо (Barry Joe) доказал, что если к уже существующей триангуляции Делоне добавить новые тетраэдры (разбив один из внутренних или присоединив тетраэдр к внешней грани), то полученную сетку можно гарантированно привести к триангуляции Делоне с помощью последовательных "трейдов" [23]. Этот факт играет огромную роль в построении триангуляций Делоне с ограничениями.
2.1 Построение триангуляции Делоне на заданном наборе точек
Как следует из названия раздела, исходными данными алгоритма является некий набор точек, которые должны стать узлами будущей триангуляции. Очевидным достоинством такого подхода является крайне точный контроль над размерами элементов сетки - фактически, эти размеры определяются плотностью размещения узлов. Увеличивая плотность размещения узлов в особенных местах области, можно автоматически добиться локального сгущения сетки вблизи этих особенностей. Кроме того, если область является сложной, можно столь же легко обеспечить размещение узлов на поверхностях и ребрах ограничений.
Что касается самого способа предварительного размещения узлов, то здесь возможно множество вариантов. Заметим, что следует категорически воздержаться от принципа случайного размещения узлов, поскольку при этом весьма вероятно появление точек, лежащих очень близко друг к другу, что, в свою очередь, неминуемо влечет появление в сетке очень коротких ребер и, соответственно, тетраэдров предельно низкого качества.
Самый простой и часто используемый метод размещения узлов основан на принципах граничной коррекции. Исходная область помещается в некоторую супер-область, заполняемую узлами в соответствии с заданной плотностью размещения узлов, затем узлы, лежащие близ границы области, проецируются на нее, а узлы вне области удаляются.
Существуют и другие, более сложные методы. Так, метод под названием "упаковка пузырьков" ("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). С другой стороны, если такая триангуляция уже есть, то проще получить итоговую сетку методами дробления - измельчив имеющиеся тетраэдры до нужных размеров, что будет гораздо быстрее и с учетом последующей минимальной оптимизации обеспечит примерно такое же качество. Поэтому такой вариант может быть использован, только если необходимо обеспечить локальное сгущение сетки в нужных местах области (т.к. сетки, полученные методами дробления, являются равномерными). При этом остается вопрос о построении начальной грубой сетки, что само по себе является отдельной задачей. Именно поэтому куда большее значение имеет задача построения триангуляции Делоне с ограничениями
2.2 Триангуляции Делоне с ограничениями
Триангуляцией Делоне с ограничениями в виде поверхностей называют такую сетку, для которой внутрь сферы, описанной вокруг любого тетраэдра этой сетки, не попадают никакие другие видимые вершинам этого тетраэдра узлы сетки (считается, что точка а видима точке b (и наоборот), если отрезок [a,b] не пересекает никаких поверхностей ограничений). Что такое триангуляция Делоне с ограничениями, если ограничения представлены в том числе и отрезками, до сих пор общепринятого определения нет.
В двумерном случае проблема построения триангуляции Делоне с ограничениями давно и успешно решена, причем самыми разными способами [3]. Что касается трех измерений, то к настоящему времени разработано лишь несколько алгоритмов, и все они базируются на одном и том же принципе. Их идея заключается в том, чтобы сначала в заданной области построить триангуляцию Делоне без ограничений, а затем восстановить поверхности и линии ограничений путем локальной перестройки сетки. Различие между алгоритмами состоит как раз в том, как именно осуществляется эта перестройка [5, 6, 24, 25].
Рассмотрим один из вариантов такого алгоритма, основанный на идее К. Хэзлвуд (Carol Hazlewood). В своей работе [21] она доказала, что возможно построить триангуляцию Делоне с ограничениями, ретриангулируя (только) те тетраэдры, которые пересекаются поверхностями ограничений. В статье Хэзлвуд этот факт доказывается для случая пересечения тетраэдра произвольным выпуклым многогранником. Для ясности упростим алгоритм, введя дополнительные несложные требования к входным данным. А именно, потребуем, чтобы поверхности ограничения были представлены либо плоскостями, либо слабо изогнутыми (радиус кривизны много больше линейных размеров элементов) сплайнами, а также, чтобы все угловые точки поверхностей ограничения использовались на первом этапе для построения триангуляции Делоне. В результате все тетраэдры построенной триангуляции могут пересекаться только либо "ребрами" поверхностей ограничений, либо самими поверхностями. Поскольку вариантов таких пересечений немного, для каждого из них можно использовать заранее подготовленный шаблон ретриангуляции. Процесс можно упростить еще больше, если предварительно добиться, чтобы все ребра ограничений были аппроксимированы цепочкой ребер триангуляции. Тогда тетраэдры смогут быть пересечены только плоскостями (сплайнами), а возможных вариантов такого пересечения всего ТРИ (рис. 9).