ТЕПЛОВ А.А. , бакалавр, МГТУ имени Н.Э. Баумана, кафедра «Программное обеспечение ЭВМ и информационные технологии», Москва, [email protected]
МАЙКОВ К.А. , д.т.н., профессор, МГТУ имени Н.Э. Баумана, кафедра «Программное обеспечение ЭВМ и информационные технологии», Москва, [email protected]
Модифицированный алгоритм
триангуляции Делоне
Приведены результаты сравнительного анализа методов триангуляции Делоне, обладающих высоким быстродействием и низкой ресурсоемкостью. Обосновывается выбор прототипа для последующей модернизации применительно кпостроению динамических трехмерных объектов в реальном времени с практически необходимой степенью детализации. Предложен алгоритм интервального разбиения массива точек триангуляции в соответствии с плотностью распределения, позволяющий избежать ошибок при аппаратной реализации. Проведен анализ предложенного модифицированного алгоритма триангуляции Делоне
Введение
Одним из этапов, определяющих ресурсоемкость построения динамических 3D объектов с заданной степенью детализации, является триангуляция . На практике возникает необходимость определения прототипа метода триангуляции, удовлетворяющего требованию высокого быстродействия и низкой ресурсоемкости с последующей модификацией для конкретного класса задач.
Постановка решаемых задач
Ряд практических задач характеризуется необходимостью моделирования 3D объектов, описанных соответствующим набором точек с неизвестным законом распределения. Примером подобных задач является моделирование горной гряды или сложных и нерегулярных поверхностных структур, значения высот которых заранее получены средствами дистанционного зондирования. В этом случае необходимо произвести триангуляцию на исходном наборе точек, обеспечивающую наибольшую «степень правильности» треугольников, для которой характерно исключение построения «тонких» треугольников с минимальным значением суммы радиусов описанных окружностей.
Проблема «степени правильности» треугольников решается триангуляцией, удовлетворяющей условию Делоне .
Известные алгоритмы триангуляции Делоне можно разделить на следующие четыре категории : итеративные алгоритмы, алгоритмы слияния, двухпроходные алгоритмы и пошаговые; основные особенности указанных алгоритмов рассматриваются ниже.
Итеративные алгоритмы построения триангуляции Делоне
В итеративных алгоритмах реализуется последовательное добавление точек в частично построенную триангуляцию Делоне . Трудоемкость итеративных алгоритмов Делоне определяется как O(N2) , а для случая равномерного распределения точек – O(N) . Недостатками итеративных алгоритмов Делоне являются большое число итеративных циклов, зависимость алгоритма сортировки от структуры исходных данных, а также необходимость проверки на условие Делоне в каждом цикле. Преимущества итеративных алгоритмов Делоне – простота реализации и высокое быстродействие выбора эффективного алгоритма сортировки, основывающегося на определенном наборе входных данных .
Алгоритмы построения триангуляции Делоне слиянием
Алгоритмы слияния реализуют разбиение исходного множества точек на ряд подмножеств, в которых производится построение триангуляций с последующим объединением ряда решений . Трудоемкость алгоритмов слияния составляет всреднем O(N) . Алгоритмам слияния свойственна избыточность, определяемая необходимостью построения выпуклых областей для «узких» полос , а следовательно, формированием длинных, «узких» треугольников , перестраиваемых при слиянии. Алгоритмы слияния обладают высоким быстродействием, что обуславливает их практическое преимущество.
Двухпроходные алгоритмы построения триангуляции Делоне
Преимущественная особенность двухпроходных алгоритмов состоит в том, что на первом цикле строится некоторая триангуляция без учета условия Делоне, которая на втором этапе модифицируется согласно условию Делоне . Трудоемкость двухпроходных алгоритмов составляет в среднем O(N) , а в наименее благоприятном случае – O(N 2) . Недостатком двухпроходных алгоритмов Делоне является необходимость в большом количестве сортировок длякаждой полосы. В то же время данный алгоритм характеризуется высоким быстродействием, т.к. очередной треугольник, попадающий в триангуляцию, не подвергается проверке на удовлетворение условию Делоне, требующему значительных аппаратных ресурсов.
Пошаговые алгоритмы построения триангуляции Делоне
Алгоритмы пошагового построения реализуют лишь треугольники, удовлетворяющие условию Делоне в конечной триангуляции, а поэтому не требуют перестроения . При большой концентрации точек применение пошагового клеточного алгоритма является нецелесообразным. Трудоемкость данного алгоритма в среднем составляет O(N), а в худшем случае – O(N 2).
Выбор прототипа для модификации триангуляции Делоне
Практические особенности задачи построения динамических 3D-объектов в реальном времени определяют такие требования к алгоритмам триангуляции Делоне, как высокое быстродействие и низкая ресурсоемкость. Как следует изприведенных выше результатов анализа, рассмотренные алгоритмы не удовлетворяют в полной мере этим требованиям. Поэтому возникает необходимость построения алгоритма, который не зависит от разбиения области триангуляции напримитивы, содержащие точки самой триангуляции, и не требует проверки условия Делоне на каждой итерации добавления текущего треугольника в исходную триангуляцию.
Из приведенных выше результатов сравнительного анализа следует, что двухпроходные алгоритмы триангуляции Делоне, в частности двухпроходной веерный алгоритм , лишь частично удовлетворяют критериям высокого быстродействия и низкой ресурсоемкости.
Однако алгоритмы данного типа нуждаются в модификации в целях повышения быстродействия применимо к задачам реального времени. Двухпроходной веерный алгоритм избыточен в определении центра масс точек. Определяя координату точки центр масс по OX или OY, при большом количестве точек нецелесообразно вычислять значение среднего арифметического, и при больших значениях координат точек может произойти переполнение данных, что повлечет за собой ошибку или сбой программы. Поэтому целесообразно все значения точек триангуляции разделить на интервалы по оси X на Δх 1 , Δх 2 , Δх 3 ... Δх n и по оси Y на Δy 1 , Δy 2 , Δy 3 ... Δy n . Также необходимо определить количество точек, принадлежащих соответствующим интервалам по осям X и Y. Результирующие формулы получения центра координат масс точек имеют следующий вид:
Последующие этапы триангуляции реализуются согласно классическому веерному алгоритму . Схема разработанного модифицированного веерного алгоритма триангуляции Делоне представлена на рис. 1.
 |
Наиболее трудоемкими этапами в представленной схеме являются этапы сортировки и построения триангуляции до выпуклой. В качестве алгоритма сортировки был выбран алгоритм слияния , а в качестве алгоритма построения выпуклой триангуляции – алгоритм Грэхема . Оба алгоритма работают за приемлемое время и являются наиболее предпочтительными в практическом аспекте среди своих представителей.
Анализ модифицированного веерного алгоритма триангуляции Делоне
Из приведенной на рис. 1 схемы видно, что значение времени построения триангуляции модифицируемым веерным алгоритмом определяется выражением:
Рассмотрим каждую временную зависимость отдельно.
При определении оптимального числа интервалов по оси X и Y, воспользуемся правилом Стерджеса , согласно которому количество интервалов n определяется как:
Очевидно, что временные зависимости T 1 и T 2 имеют константные представления c 1 и c 2 .
На этапах определения значений X min , X max , Y min , Y max псевдокод будет выглядеть следующим образом:
Xmin ← M
for i ← 1 to lenght(M) – 1
If Xmin › M[i]
Xmin ← M[i]
Xmax ← M
for i ← 1 to lenght(M) – 1
If Xmax < M[i]
Xmax ← M[i]
Ymin ← M
for i ← 1 to lenght(M) – 1
If Ymin › M[i]
Ymin ← M[i]
Ymax ← M
for i ← 1 to lenght(M) – 1
If Ymax < M[i]
Ymax ← M[i]
Из вышеуказанного псевдокода отчетливо видно, что время нахождения максимального или минимального значения величин x или y имеет линейную зависимость O(N), следовательно, T 3 (n), T 4 (n),T 5 (n),T 6 (n), имеют временную характеристику O(N) соответственно.
Схема определения значений интервалов по оси X представлена на рис. 2.
Из выше представленной схемы также видна линейная временная зависимость O(N), т.к. в определении величин участвует весь набор координат значений массива точек. Схема определения величин интервалов по оси Y имеет аналогичную структуру и временные характеристики, следовательно, временная зависимость для T 7 (n) и T 8 (n) имеет вид O(N).
Схема определения значений полярного угла для исходного массива точек представлена на рис. 3.
В виде псевдокода данная схема будет выглядеть следующим образом:
for points to points
# Если точка лежит на оси координат между I и IV четвертями
If point.x ≥ Xc and point.y = Yc
Point.angle ← 0
# Если точка лежит строго в I четверти
Else if point.x > Xc and point.y > Yc
Foundation ← |point.x – Xc|
Point.angle ← arctg(perpendicular/foundation)
# Если точка лежит на оси координат между I и II четвертями
Else if point.x = Xc and point.y > Yc
Point.angle ← p/2
# Если точка лежит строго в II четверти
Else if point.x < Xc and point.y > Yc
Foundation ← |point.y – Yc|
Point.angle ← p/2 + arctg(perpendicular/foundation)
# Если точка лежит на оси координат между II и III четвертями
If point.x < Xc and point.y = Yc
Point.angle ← p
# Если точка лежит строго в III четверти
If point.x < Xc and point.y > Yc
Foundation ← |point.x – Xc|
Perpendicular ← |point.y – Yc|
Point.angle ← p + arctg(perpendicular/foundation)
# Если точка лежит на оси координат между III и IV четвертями
If point.x = Xc and point.y < Yc
Point.angle ← 3p/2
# Если точка лежит строго в IV четверти
If point.x > Xc and point.y < Yc
Foundation ← |point.y – Yc|
Perpendicular ← |point.x – Xc|
Point.angle ← 3p/2 + arctg(perpendicular/foundation)
Очевидно, что временная характеристика определения значений полярного угла для исходного массива координат точек имеет вид O(N), следовательно, T 9 (n) = O(N).
Как показано в , сортировка слиянием имеет временную зависимость вида O(N), следовательно, T 10 (n) = O(NlnN).
Схема построения ребра, соединяющего точки исходного массива, представлена на рис. 4.
Псевдокод вышеуказанной схемы будет иметь вид:
for i ← 0 to length(Points) – 1
Draw(Xc,Yc,Points[i].x, Points[i].y)
Временная характеристика также линейна, следовательно, T 11 (n) = O(N).
Достроение получившейся триангуляции до выпуклой осуществляется согласно алгоритму Грэхема . В качестве входных данных процедуры выступает множество точек Q, где |Q|≥3. В ней вызывается функция Top(S), которая возвращает точку, находящуюся на вершине стека S, не изменяя при этом его содержимое. Кроме того, используется также функция NextToTop(S), которая возвращает точку, расположенную в стеке S, на одну позицию ниже от верхней точки; стек S при этом не изменяется.
Graham(Q)
Пусть p 0 – точка из множества Q с минимальной координатой.
Пусть ‹p 1 , p 2 ,...,p N › – точки множества Q, отсортированные
В порядке возрастания полярного угла.
Push(p 0 ,S)
Push(p 1 ,S)
for i=2 to N do
While угол, образованный точками NextToTop(S), Top(S) и pi,
Образуют не левый поворот
# при движении по ломаной, образованной этими
# точками, движение осуществляется прямо или вправо
Do Pop(S)
Push(pi,S)
return S
Время работы процедуры Graham равно O(NlnN), где N=length(Q). Как несложно показать, что циклу while потребуется время O(N), а сортировка полярных углов займет O(NlnN) времени, откуда и следует общая асимптотика процедуры Graham, следовательно, T 12 (n) = O(NlnN).
Временная характеристика перестроения триангуляции, удовлетворяющей условию Делоне, как показано в , имеет линейную зависимость O(N), таким образом, T 13 (n) = O(N).
Если подставить все найденные временные характеристики в выражение (3), то результирующая временная зависимость будет иметь вид:
T(n) = c 1 +c 2 +O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+O(N)+ +O(NlnN)+O(N)+O(NlnN)+O(N)
T(n) = O(NlnN)
Проведенный теоретический анализ временных характеристик модифицированного алгоритма триангуляции Делоне подтверждает работоспособность и высокое быстродействие предложенного алгоритма.
Выводы
В результате проведенного сравнительного анализа практически востребованных алгоритмов триангуляции Делоне, показано, что рассмотренные методы не удовлетворяют требованиям построения в реальном времени динамических трехмерных объектов с заранее определенной степенью детализации, а следовательно, возникает практическая необходимость их модификации. Предложена модификация веерного двухпроходного алгоритма триангуляции Делоне, функциональной особенностью которого является вычисление значений центра масс массива координат точек триангуляции посредством разбиения массива точек на подмножества по оси X и Y. Произведен анализ временных характеристик модифицированного алгоритма триангуляции Делоне. Указанные вычисления позволяют существенно выиграть в производительности на большом массиве точек при определении координат точки центра масс и избежать переполнения данных, а следовательно, ошибки при программной реализации.
Ключевые слова: виртуальная реальность, триангуляция на заданном массиве точек, триангуляция Делоне, построение динамических трехмерных объектов.
The modified Delaunay’s triangulation algorithm
Teplov A.A. , Bachelor, MSTU Bauman, Department of "Software and Information Technologies", Moscow, [email protected]
Maikov K.A. , Doctor of Technical Sciences, Professor, MSTU Bauman, Department of "Software and Information Technologies", Moscow, [email protected]
Abstract: The results of the comparative analysis of the virtually popular methods of the Delaunay’s triangulation with high performance and low resource consumption are described in this article. The choice of the method for further modernization with the aim of building of dynamic 3-D objects in real time with a certain degree of detail is justified. One of the main stages of a fibered the two-pass algorithm of the Delaunay’s triangulation is modified. There is the proposal of the algorithm for the interval partitioning of the cell array of the triangulation in accordance with the density of distribution, allowing to avoid the errors in the hardware implementation.
Keywords: virtual reality, triangulation on a given cell array, Delaunay’s triangulation, building of dynamic 3-D objects.
Вконтакте
GRID- модели – модели регулярных ячеек.
Пусть
введена система координат
и
и
.
Пользователь задает
и шаги дискретизации
.
,
-
физические координаты точки.
Вычисляем
и
,
- разрядная сетка.
-
квантованные значения. Реальные:
-
параметр алгоритма – количество точек,
- вес. Чем ближе точка, тем больше вес.
-
степень расстояния (1 или 2).
Нормировочный
коэффициент: 
Чем
ближе к 1, тем больше учитываются точки
с большим весом.
Это
метод IDW – долгий, для каждой т. необходимо
найти соседей. Набор соседей может быть
эффективно найден - ближайшим. Каждая
из точек продуцирует «колышек»
определенной высоты. От нерегулярности
постановок точки многое зависит, для
этого берут
или
т.е. разделяют на сектора и в окрестности
точки строим.
Преимущество – простота
Недостаток:
Триангуляция – построение функции в виде совокупности кусочно - линейной функции
Триангуляция – интерполяция внутри выпуклой области.
Триангуляция – планарный граф, все внутренние ребра которого – треугольники; способ представления пространства в виде примыкающих друг к другу треугольников без перекрытий. На наборе точек триангуляция строится несколькими способами.
Нужен алгоритм для построения оптимальной триангуляции.
Плоскость, проходящая через 3 точки.
1)
Найдем треугольник, который
;
2)
- строим уравнение плоскости.
Чтобы проверить находятся ли точки внутри треугольника или нет, необходимо подставить значение в уравнение линий – ребер треугольника. Если все 3 уравнения > 0, то внутри.
Структура представления:
Каждая триангуляция содержит одинаковое количество треугольников.
,
где
– количество внутренних точек,
– количество точек.
Жадный триангуляция.
Все точки соединяем ребрами, выбираем минимум, добавляем в триангуляцию. Далее берем следующий минимум, не пересекающийся с предыдущими и т.д. В результате получена жадная триангуляция.
Триангуляция Делоне.
Внутрь окружности, описанной вокруг любого треугольника, не попадают точки других треугольников. Строится единственным образом.
Флипом называется переброска ребер. Она позволяет перейти от обычной триангуляции к триангуляции Делоне. Чтобы проверить принадлежность точки к окружности: подставить, если < R, то внутри.
Условие Делоне.
Уравнение окружности, проходящей через три точки:
Если меньше нуля, то внешняя, иначе – внутренняя.
–условие Делоне.
Алгоритм построения триангуляции Делоне:
1) Подследственного добавления точек – простой итеративный алгоритм:
Есть
набор
добавляем в треугольник, осуществляется
построение
разбиение треугольника
перестроение. На нулевом этапе добавляем
3-4 фиктивные точки, которые заведомо
покрывают наш конверт, все точки внутри.
После кидаем точку, смотрим в какой
треугольник попала, разбиваем на 3, для
каждого треугольника проверяем условие
Делоне и осуществляем флип переброску
ребер. Среднее количество перестроений
равно трем.
Теоретическая
сложность
2) Методы ускорения. Основан на статистически зависимых точках. Затравочный треугольник – треугольник в который попала предыдущая точка. Затем соединяем две точки – предыдущую и новую.
Перемещаемся из первой точки в другую.
Для количественной оценки качества построенной триангуляции определим два типа критериев топологический и геометрически .
Топологический критерий основан на ближайших соседях точки из множества. В идеальном случае точка имеет для двумерной области 6 соседей, для трехмерной 12 соседей. Топологическую оценку получим с помощью формулы (1), где - общее количество точек в области, - степень или количество соседних точек с вязаных с внутренней точкой.
Геометрический критерий основан на разнице вписанной и описанной окружности вокруг расчетного треугольного элемента. Геометрическую оценку получим с помощью формулы (2), где - количество треугольников, - радиус вписанной окружности, - радиус описанной окружности.
Для построения триангуляции существует большое количество алгоритмов. Они различаются между собой трудоёмкостью, сложностью реализации на ЭВМ, подходами к построению. Подробнее об алгоритмах можно узнать в книге А.В. Скворцова . Рассмотрим некоторые алгоритмы.
Одним из первых был предложен жадный алгоритм построения триангуляции. Триангуляция Делоне называется жадной, если она построена с помощью жадного алгоритма. Трудоемкость работы жадного алгоритма при некоторых его улучшениях составляет . В связи со столь большой трудоемкостью на практике он почти не применяется. Рассмотрим алгоритм по шагам:
Шаг 1. Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и он сортируется по длинам отрезков.
Шаг 2. Начиная с самого короткого, последовательно выполняется вставка отрезков в триангуляцию. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается.
Заметим, что если все возможные отрезки имеют разную длину, то результат работы этого алгоритма однозначен, иначе он зависит от порядка вставки отрезков одинаковой длины.
Итеративный алгоритм имеют в своей основе очень простую идею последовательного добавления точек в частично построенную триангуляцию Делоне. Сложность данного алгоритма складывается из трудоёмкости поиска треугольника, в который на очередном шаге добавляется точка, трудоёмкости построения новых треугольников, а также трудоёмкости соответствующих перестроений структуры триангуляции в результате неудовлетворительных проверок пар соседних треугольников полученной триангуляции на выполнение условия Делоне. Рассмотрим алгоритм по шагам:
Шаг 1. На первых трех исходных точках строим один треугольник.
Шаг 2. В цикле по для всех остальных точек выполняем шаги 3-5.
Шаг 3. Очередная -я точка добавляется в уже построенную структуру триангуляции следующим образом. Вначале производится локализация точки, т.е. находится треугольник (построенный ранее), в который попадает очередная точка. Либо, если точка не попадает внутрь триангуляции, находится треугольник на границе триангуляции, ближайший к очередной точке.
Шаг 4. Если точка попала на ранее вставленный узел триангуляции, то такая точка обычно отбрасывается, иначе точка вставляется в триангуляцию в виде нового узла. При этом если точка попала на некоторое ребро, то оно разбивается на два новых, а оба смежных с ребром треугольника также делятся на два меньших. Если точка попала строго внутрь какого-нибудь треугольника, он разбивается на три новых. Если точка попала вне триангуляции, то строится один или более треугольников.
Шаг 5. Проводятся локальные проверки вновь полученных треугольников на соответствие условию Делоне и выполняются необходимые перестроения.
При построении новых треугольников возможны две ситуации, когда добавляемая точка попадает либо внутрь триангуляции, либо вне её. В первом случае строятся новые треугольники и число выполняемых алгоритмом действий фиксировано. Во втором необходимо построение дополнительных внешних к текущей триангуляции треугольников, причём их количество может в худшем случае равняться? 3. Однако за все шаги работы алгоритма будет добавлено не более треугольников, где - общее число исходных точек. Поэтому в обоих случаях общее затрачиваемое время на построение треугольников составляет.
Цепной алгоритм один из первых эффективных алгоритмов построения триангуляции основан на процедуре регуляризации планарного графа и триангуляции монотонных многоугольников . Трудоемкость этого алгоритма составляет, где - количество исходных отрезков. Рассмотрим алгоритм по шагам:
Шаг 1. Из множества исходных структурных отрезков формируем связанный планарный граф (Рисунок 4,а).
Шаг 2. Выполняется регуляризация графа, т.е. добавляются новые рёбра, не пересекающие другие, так что каждая вершина графа становится смежной хотя бы с одной вершиной выше неё и одной ниже. Регуляризация выполняется в два прохода с помощью вертикального плоского заметания . В первом проходе снизу вверх последовательно находятся все вершины, из которых не выходят рёбра, ведущие вверх. Например, на (Рисунок 4,б) такой является вершина B. Проводя горизонтальную линию, обнаруживаем ближайшие пересекаемые ею слева и справа рёбра графа AD и EF. Затем в четырехугольнике DEHG находим самую низкую вершину и проводим в неё ребро из B. Аналогично выполняется второй проход сверху вниз (Рисунок 4,в). В результате работы этого шага каждая область планарного графа становится монотонным многоугольником.
Шаг 3. Каждую область графа необходимо разбить на треугольники. Для этого можно воспользоваться алгоритмом невыпуклого слияния двух триангуляций (Рисунок 4,г).
Рисунок 4. Схема работы цепного алгоритма триангуляции: а) - исходные отрезки; б - проход снизу вверх регуляризации графа; в) - проход сверху вниз; г) - триангуляция монотонных многоугольников
Для реализации цепного алгоритма лучше всего использовать структуры данных, в которых рёбра представляются в явном виде, например «Двойные рёбра» или «Узлы, рёбра и треугольники» .
Недостатком цепного алгоритма является то, что о форме получаемой триангуляции ничего заранее сказать нельзя. Это не оптимальная триангуляция, не жадная и не триангуляция Делоне с ограничениями. В цепном алгоритме могут получаться очень длинные вытянутые треугольники.
Для улучшения качества полученной триангуляции можно проверить все пары смежных треугольников, не разделенных структурным ребром, на выполнение условия Делоне и при необходимости произвести перестроения. В результате будет получена триангуляция Делоне с ограничениями.
(Development and Implementation of Algorithms for Constrained Volume Triangulations:
Iterative Algorithms
Preprint, Inst. Appl. Math., the Russian Academy of Science)
ИПМ им. М.В.Келдыша РАН
Рассмотрены итерационные методы трехмерной дискретизации пространственных областей (построения тетраэдрических сеток): методы граничной коррекции, методы на основе критерия Делоне и методы исчерпывания. Приведены варианты алгоритмов для каждого из указанных методов. Обсуждены особенности построения сеток в сложных областях.
Three main families of iterative algorithms for free and constrained simplicial volume triangulation are described: boundary correction (including "octree" algorithm), Delaunay-based methods and advancing front approach. For each method type an example algorithm is given.
1. Введение 3
2. Методы граничной коррекции4
2.1 Построение первичной сетки4
2.2 Коррекция первичной сетки6
3. Методы на основе критерия Делоне9
3.1 Построение триангуляции Делоне на заданном наборе точек 12
3.2. Триангуляция Делоне с ограничениями17
3.3 Особенности технической реализации
алгоритмов на основе
критерия Делоне
22
4. Методы исчерпывания23
4.1 Пример алгоритма исчерпывания26
Список литературы3 0
Среди двух классов методов триангуляции - прямых и итерационных - последние обладают достаточной универсальностью и поэтому, в отличие от прямых, могут быть использованы для триангуляции областей довольно произвольного вида. За эту универсальность приходится расплачиваться существенно большим потреблением ресурсов и более трудоемкой реализацией метода в конкретном алгоритме.
В настоящее время разработано большое количество программных пакетов на основе того или иного итерационного метода, реализующих построение сеток (частично или полностью) в автоматическом режиме. В основном эти пакеты коммерческие, что вполне оправдано с учетом затрачиваемых на их создание усилий, ведь трехмерное пространство имеет ряд неприятных особенностей, существенно затрудняющих жизнь разработчику .
Сетки, построенные итерационными методами, как правило, неструктурированы и неоднородны. Неструктурированность обусловлена тем, что топология сетки формируется в процессе построения, и поэтому естественно может варьироваться даже в пределах одной подобласти. По этой же причине однородность если и может возникнуть, то только случайно.
Поскольку перед построением сетки ничего нельзя сказать о ее будущей структуре, нельзя гарантировать и ее качества. Часто построенную сетку можно существенно улучшить с помощью одного из многочисленных методов оптимизации . Этой возможностью обычно не пренебрегают, благо что время, затрачиваемое на оптимизацию, как правило, существенно меньше времени, затрачиваемого на построение.
Целью данной работы является рассмотрение и классификация существующих методов построения тетраэдрических сеток в трехмерных областях. Ввиду значительного объема информации ниже рассматриваются только так называемые "итерационные методы". Прямые методы описаны в .
Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (проект № 06-01-00421).
Рис. 11. Триангуляция области, представляющей собой объединение додекаэдра и икосаэдра (триангуляция Делоне с ограничениями)
Качество сеток, построенных данным методом, находится на среднем уровне (тетраэдры у границ могут иметь очень плохую форму), поэтому обычно дополнительно прибегают к одному из методов оптимизации.
В работах Б. Джо предложены другие варианты алгоритма, не использующие дополнительных точек и полностью основанные на локальных трансформациях, аналогичных "трейду".
4) объем тетраэдра не больше максимально допустимого ().
Из всех тетраэдров () выбирается тетраэдр наилучшего качества и производится переход к п. 5; если же тетраэдров, удовлетворяющих указанным условиям, не оказалось, то осуществляется переход к п. 4.
4. Находится такая точка внутри еще неисчерпанной области, что:
1) тетраэдр () удовлетворяет всем условиям п. 3;
2) в шаре нет ни одной удаленной точки F (это предотвращает размещение узла p слишком близко от граней и вершин существующих тетраэдров).
Вариант алгоритма поиска узла p рассмотрен ниже.
5. Удаляются все вершины F , попавшие внутрь (и на границы) сформированного тетраэдра. Затем фронт обновляется по следующей схеме: рассматривается каждая грань сформированного тетраэдра и
1) если грань является гранью фронта, то она удаляется из фронта;
2) если грань НЕ является гранью фронта, она добавляется во фронт.
6. Если еще остались неудаленные точки F или (что эквивалентно) фронт не пуст (то есть область еще не исчерпана полностью), осуществляется переход к п. 1, иначе процесс окончен.
Таким образом, массив F используется сразу для нескольких целей: для оценки величины телесного угла, для контроля правильности построения и для контроля размещения новых узлов. Также массив F удобно использовать для индикации процесса выполнения. Отношение числа удаленных во время работы алгоритма точек F к начальному числу существующих точек F фактически показывает, какая часть области уже исчерпана.
Вернемся к вопросу нахождения координат нового узла для построения тетраэдра (п. 4 описанного алгоритма). Пусть заданы три узла - .
1. На первом шаге находятся - центр масс треугольника (как среднее арифметическое координат его узлов) и единичная нормаль к плоскости грани (через нормированное векторное произведение).
2. Далее определяется первое приближение для расстояния от до искомой точки p (H ), исходя из максимального объема тетраэдра: . Заметим, что площадь грани S фактически найдена на предыдущем шаге (результат векторного произведения двух ребер равен удвоенной площади грани), а максимальный объем обусловлен значением контрольной функции.
3. Проверяется точка . Если тетраэдр () удовлетворяет всем требованиям, происходит переход к п. 6, иначе - к п. 4.
4. Проверяется точка . Если тетраэдр () удовлетворяет всем требованиям, происходит переход к п. 6, иначе - к п. 5.
5. Полагают и переходят к п. 3.
6. Искомый узел найден.
Заметим, что в 99% случаев искомая точка находится на 1 или 2 итерации данного алгоритма.
В описанном выше алгоритме исчерпывания на каждом шаге из области изымается один тетраэдр. Сотрудник НАСА Ш. Пирзаде (Shahyar Pirzadeh ) предложил другой вариант алгоритма, в котором за один раз из области изымается сразу целый слой тетраэдров (то есть на каждой итерации тетраэдры строятся сразу для всех граней текущего фронта) . Вопреки ожиданию, этот вариант не позволяет сколько-нибудь существенно ускорить процесс построения (т.к. все новые тетраэдры все равно необходимо проверять на корректность), однако он избавляет от необходимости искать наиболее подходящую для построения тетраэдра грань. Это, однако, скорее минус, чем плюс, так как из-за этой особенности вариант Пирзаде менее надежен и может дать сбой на геометрически сложных областях. Вместе с тем на сравнительно простых областях он показывает неплохие результаты.
Сетки, построенные методами исчерпывания, как правило, обладают неплохим качеством, а последующая оптимизация положения узлов дает дополнительную прибавку к качеству. Подводя итог, заметим, что методы исчерпывания наиболее эффективны, если изначально задана триангуляция границы области. В этом и состоит их основное отличие от методов на основе критерия Делоне, для которых ситуация прямо обратная.
Список литературы
1. Шайдуров В.В. Многосеточные методы конечных элементов. - М., Наука, 1989. - 288с.
2. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне // , 2002, №3, c . 14-39.
3. Скворцов А.В. Алгоритмы построения триангуляции с ограничениями // Вычислительные методы и программирование , 2002, №3, c . 82-92.
4. I.Babushka, W.C. Rheinboldt. A-posteriori Error Estimates for Finite Element Method // Int. J. Numer. Meth. Eng. , Vol. 12, p.p. 1597-1615, 1978.
5. T.J. Baker. Automatic Mesh Generation for Complex Three-Dimensional Regions Using a Constrained Delaunay Triangulation // Engineering With Computers , Springer-Verlag, № 5, p.p. 161-175, 1989.
6. M. Bern, D. Eppstein. Mesh Generation and Optimal Triangulation // Computing in Euclidean Geometry , World Scientific Publishing Co., p.p. 23-90, 1995.
7. D.K. Blandford, G. Blelloch, D. Cardoze, C. Kadow. Compact Representations of Simplicial Meshes In Two and Three Dimensions // Proceedings of 12th International Meshing Roundtable , Sandia National Laboratories, p.p.135-146, Sept. 2003.
8. H. Borouchaki, S.H. Lo. Fast Delaunay Triangulation In Three Dimensions // Computer Methods In Applied Mechanics And Engineering , Elsevier, Vol. 128, p.p. 153-167, 1995.
9. E.K. Buratynski. A Three-Dimensional Unstructured Mesh Generator for Arbitrary Internal Boundaries // Numerical Grid Generation in Computational Fluid Mechanics , Pineridge Press, p.p. 621-631, 1988.
10. P.R. Cavalcanti, U.T. Mello. Three-Dimensional Constrained Delaunay Triangulation: A Minimalist Approach // Proceedings of the 8th International Meshing Roundtable , p.p. 119-129, 1999.
11. Dey, K. Tamal, K. Sugihara, C.L. Bajaj. Delaunay Triangulations In Three Dimensions With Finite Precision Arithmetic // Computer Aided Geometric Design , North-Holland, № 9, p.p. 457-470, 1992.
12. H.N. Djidjev. Force-Directed Methods For Smoothing Unstructured Triangular And Tetrahedral Meshes // Proceedings of 9th International Meshing Roundtable , Sandia National Laboratories, p.p. 395-406, October 2000.
13. L. Durbeck. Evaporation: A Technique For Visualizing Mesh Quality // Proceedings of 8th International Meshing Roundtable , South Lake Tahoe, CA, U.S.A., p.p. 259-265, October 1999.
14. D.A. Field. Laplacian Smoothing And Delaunay Triangulations // , vol. 4, p.p. 709-712, 1988.
15. P.J. Frey, H. Borouchaki, P.-L. George. Delaunay Tetrahedralization Using an Advancing-Front Approach // Proceedings of 5th International Meshing Roundtable , Sandia National Laboratories, p.p. 31-46, October 1996.
16. L.A. Freitag, C. Ollivier-Gooch. A Comparison of Tetrahedral Mesh Improvement Techniques // Proceedings of 5th International Meshing Roundtable , Sandia National Laboratories, p.p. 87-106, October 1996.
17. L.A. Freitag, C. Ollivier-Gooch.Tetrahedral Mesh Improvement Using Swapping and Smoothing // , vol. 40, p.p. 3979-4002, 1995.
18. L.A. Freitag, C. Ollivier-Gooch. The Effect Of Mesh Quality On Solution Efficiency // Proceedings of 6th International Meshing Roundtable , Sandia National Laboratories, p.p.249, October 1997.
19. P.L. George. TET MESHING: Construction, Optimization and Adaptation // Proceedings of 8th International Meshing Roundtable , p.p.133-141, 1999.
20. N.A. Golias, T.D. Tsiboukis. An Approach to Refining Three-Dimensional Tetrahedral Meshes Based on Delaunay Transformations // , John Wiley, № 37, p.p.793-812, 1994.
21. C. Hazlewood. Approximating Constrained Tetrahedralizations // Computer Aided Geometric Design , vol. 10, p.p. 67–87, 1993.
22. B. Joe. Delaunay Triangular Meshes in Convex polygons, SIAM J. Sci. Stat. Comput ., Vol. 7, p.p. 514-539, 1986.
23. B. Joe. Construction Of Three-Dimensional Delaunay Triangulations Using Local Transformations // Computer Aided Geometric Design , Vol. 8, p.p. 123-142, 1991.
24. B. Joe. Construction of Three-Dimensional Improved-Quality Triangulations Using Local Transformations // Siam J. Sci. Comput. , vol. 16, p.p. 1292-1307, 1995.
25. R.W. Lewis, Yao Zheng, D.T. Gethin. Three-Dimensional Unstructured Mesh Generation: Part 3. Volume Meshes // Computer Methods In Applied Mechanics And Engineering , Elsevier, Vol 134, p.p.285-310, 1996.
26. A.Liu, B. Joe. On The Shape Of Tetrahedra From Bisection // Mathematics of Computation , vol. 63, №207, 141–154, 1994.
27. S.H. Lo. Volume Discretization into Tetrahedra-I. Verification and Orientation of Boundary Surfaces // Computers and Structures , Pergamon Press, Vol. 39, № 5, p.p. 493-500, 1991.
28. S.H. Lo. Volume Discretization into Tetrahedra - II. 3D Triangulation by Advancing Front Approach // Computers and Structures , Pergamon, Vol. 39, № 5, p.p. 501-511, 1991.
29. R. Lohner. Generation Of Three-Dimensional Unstructured Grids By The Advancing Front Method //Proceedings of the 26th AIAA Aerospace Sciences Meeting , Reno, Nevada, 1988.
30. S.J. Owen. A Survey of Unstructured Mesh Generation Technology // Proceedings of 7th International Meshing Roundtable , p.p. 239-269, Dearborn, MI, 1998.
31. V.N. Parthasarathy, C.M. Graichen, A.F. Hathaway. A Comparison of Tetrahedron Quality Measures // Finite Elements in Analysis and Design , Elsevier, №. 15, p.p. 255-261, 1993.
32. S. Pirzadeh. Unstructured Viscous Grid Generation by Advancing-Layers Method // AIAA-93-3453-CP, AIAA, p.p. 420-434, 1993.
33. V.T. Rajan. Optimality of Delaunay Triangulation in // Proc. 7th ACM Symp. Comp. Geometry , p.p. 357-363, 1991.
34. A.Rassineux. Generation and Optimization of Tetrahedral Meshes by Advancing Front Technique // International Journal for Numerical Methods in Engineering , Wiley, Vol. 41, p.p. 651-674, 1998.
35. S. Rebay. Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm // Journal Of Computational Physics , vol. 106, p.p. 125-138, 1993.
36. M.-C. Rivara. Selective Refinement/Derefinement Algorithms For Sequences Of Nested Triangulations // International Journal for Numerical Methods in Engineering , №28, p.p. 2889-2906, 1998.
37. M.-C. Rivara, C. Levin. A 3D Refinement Algorithm Suitable For Adaptive And Multigrid Techniques // Communications in Applied Numerical Methods , № 8, p.p. 281-290, 1998.
38. J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation // Journal of Algorithms , №18, p.p. 548-585, 1995.
39. M.S. Shephard, M.K. Georges. Three-Dimensional Mesh Generation by Finite Octree Technique // International Journal for Numerical Methods in Engineering , vol. 32, p.p. 709-749, 1991.
40. M.S. Shephard, F. Guerinoni, J.E. Flaherty, R.A. Ludwig, P.L. Baehmann. Finite octree mesh generation for automated adaptive 3D Flow Analysis // Numerical grid generation in computational Fluid mechanics , Miami, 1988
41. K. Shimada, D.C. Gossard. Bubble Mesh: Automated Triangular Meshing of Non-manifold Geometry by Sphere Packing // Proceedings of 3rd Symposium on Solid Modeling and Applications , p.p. 409-419, 1995.
42. K. Shimada, A. Yamada, T. Itoh. Anisotropic Triangular Meshing of Parametric Surfaces via Close Packing of Ellipsoidal Bubbles // Proceedings of 6th International Meshing Roundtable , p.p. 375-390, 1997.
43. D.F. Watson. Computing the Delaunay Tessellation with Application to Voronoi Polytopes // The Computer Journal , Vol. 24(2), p.p. 167-172, 1981.
44. M.A. Yerry, M.S. Shephard. Three-Dimensional Mesh Generation by Modified Octree Technique // International Journal for Numerical Methods in Engineering , Vol. 20, p.p. 1965-1990, 1984.
45. Галанин М.П., Щеглов И.А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: прямые методы. Препринт ИПМ им. М.В. Келдыша РАН, 2006, в печати. points , т.е. узлы Штейнера - дополнительные узлы, не входившие в изначальный набор
Может показаться, что из условия 3 следует условие 2, но на самом деле это не так. Например, существующий тетраэдр может целиком оказаться внутри проверяемого тетраэдра.
В целом, все алгоритмы имеют в своей основе очень простую идею последовательного добавления точек в частично построенную триангуляцию Делоне. Формально это выглядит так.
Дано множество из N точек.
1. На первых трех исходных точках строим один треугольник.
2. В цикле по n для всех остальных точек выполняем шаги 3-5.
3. Очередная n-я точка добавляется в уже построенную структуру триангуляции следующим образом. Вначале производится локализация точки, т.е. находится треугольник (построенный ранее), в который попадает очередная точка. Либо, если точка не попадает внутрь триангуляции, находится треугольник на границе триангуляции, ближайший к очередной точке.
4. Если точка попала на ранее вставленный узел триангуляции, то такая точка обычно отбрасывается, иначе точка вставляется в триангуляцию в виде нового узла. При этом если точка попала на некоторое ребро, то оно разбивается на два новых, а оба смежных с ребром треугольника также делятся на два меньших. Если точка попала строго внутрь какого - нибудь треугольника, он разбивается на три новых. Если точка попала вне триангуляции, то строится один или более треугольников.
5. Проводятся локальные проверки вновь полученных треугольников на соответствие условию Делоне и выполняются необходимые перестроения.
Конец алгоритма.
Ниже приводится подробное описание нескольких алгоритмов.
Одним из первых был предложен следующий алгоритм построения триангуляции.
Жадный метод - это такой метод, при котором никогда не отменяется то, что уже было сделано ранее. В алгоритме последовательно выполняются следующие шаги.
1. Во множество исходных точек помещаются концы всех структурных отрезков.
2. Генерируются отрезки, соединяющие все пары точек, отрезки сортируются по длине.
3. В триангуляцию вставляются все отрезки структурных линий.
4. В триангуляцию последовательно отбираются отрезки из множества отсортированных по длине отрезков (от более коротких к более длинным). Если отрезок пересекается с каким-нибудь из уже вставленных, то он отбрасывается, иначе вставляется в триангуляцию.
Шаг 4 повторяется, пока не кончатся отрезки.
Заметим, что если все возможные отрезки имеют разную длину, то результат работы этого алгоритма однозначен, иначе он зависит от порядка вставки отрезков одинаковой длины.
Триангуляция называется жадной, если она построена жадным алгоритмом.
"Удаляй и строй" не выполняется никаких перестроений. Вместо этого при каждой вставке нового узла (а) сразу же удаляются все треугольники, у которых внутрь описанных окружностей попадает новый узел (б). При этом все удаленные треугольники неявно образуют некоторый многоугольник. После этого на месте удаленных треугольников строится заполняющая триангуляция путем соединения нового узла с этим многоугольником (рис. в).
Рис. 4. Алгоритм "Удаляй и строй"
Данный алгоритм строит сразу все необходимые треугольники в отличие от обычного итеративного алгоритма, где при вставке одного узла возможны многократные перестроения одного и того же треугольника. Однако здесь на первый план выходит процедура выделения контура удаленного многоугольника, от эффективности работы которого зависит общая скорость алгоритма. В целом в зависимости от используемой структуры данных этот алгоритм может тратить времени меньше, чем алгоритм с перестроениями, и наоборот.
Алгоритм вставки структурных отрезков "Строй, разбивая" является наиболее простым в реализации и устойчивым в работе.
В нем необходимо, последовательно переходя по треугольникам вдоль вставляемого отрезка, находить точки его пересечения с рёбрами триангуляции. В этих точках пересечения нужно поставить но-вые узлы триангуляции, разбив существующие рёбра и треугольники на части. После этого все вновь построенные треугольники долж-ны быть проверены на выполнение условия Делоне и при необходимости перестроены, не затрагивая фиксированных рёбер.
Рис. 5. Алгоритм "Строй, разбивая"
В некоторых случаях недостатком данного алгоритма вставки может быть создание большого числа дополнительных узлов и рёбер триангуляции. В то же время в других случаях этот недостаток становится преимуществом, не позволяя образовываться длинным узким треугольникам, что особенно ценится при моделировании рельефа.
Другое преимущество этого алгоритма вставки по сравнению с последующими проявляется при попытке вставки структурного отрезка в триангуляцию, в которой среди пересекаемых им рёбер есть фиксированные. Такие рёбра, как и все остальные, просто разбиваются на две части.
В алгоритме триангуляции с индексированием центров треугольников k-D-деревом в k-D-дерево (при k = 2) помещаются только центры треугольников. При удалении старых треугольников необходимо удалять их центры из k-D-дерева, а при построении новых - заносить.
Для выполнения поиска треугольника, в который попадает текущая вставляемая в триангуляцию точка, необходимо выполнить нестандартный точечный запрос к k-D-дереву. Поиск в дереве необходимо начинать с корня и спускаться вниз до листьев. В случае если потомки текущего узла k-D-дерева (охватывающий потомки прямоугольник) не покрывают текущую точку, то необходимо выбрать для дальнейшего спуска по дереву потомка, ближайшего к точке поиска.
В результате будет найден некоторый треугольник, центр которого будет близок к заданной точке. Если в найденный треугольник не попадает заданная точка, то далее необходимо использовать обычный алгоритм поиска треугольника из простого итеративного алгоритма построения триангуляции Делоне.
