Содержание к диссертации
Введение
1 Методы построения нерегулярных тетраэдральных сеток 14
1.1 Метод дерева октантов 17
1.2 Метод движущегося фронта 18
1.3 Триангуляция Делоне 19
1.4 Алгоритмы построения тетраэдризации Делоне множества вершин 24
1.4.1 Алгоритм заметания 24
1.4.2 Пошаговый алгоритм прямого построения 27
1.4.3 Метод отображения в пространство большей размерности 29
1.4.4 Итеративные алгоритмы 30
1.4.5 Геометрические тесты для построения триангуляции Делоне 40
1.5 Критерии оценки качества сетки 41
2 Построение тетраэдризации Делоне для тел с кусочно-линейными границами 45
2.1 Восстановление отсутствующих ребер 47
2.2 Восстановление отсутствующих граней 52
2.3 Алгоритм построения тетраэдризации Делоне для тел с кусочно-линейными границами 59
2.4 Обеспечение робастности геометрических расчетов 63
2.5 Решение задач о локализации точки и поиска непустых диаметральных и экваториальных шаров 70
3 Построение нерегулярных треугольных сеток на криволи нейных гранях с использованием анизотропной триангуля ции Делоне 72
3.1 Построение анизотропной триангуляции Делоне множества вершин 75
3.2 Построение анизотропной триангуляции Делоне двумерной области 79
3.3 Особенности использования анизотропной триангуляции Делоне для построения поверхностных сеток 87
3.4 Заключение 94
4 Построение тетраэдризации Делоне с ограничениями для об ластей с криволинейными границами 97
4.1 Алгоритм построения 101
4.2 Метод восстановления криволинейных граней в тетраэдризации 102
4.2.1 Первая стадия восстановления граней 104
4.2.2 Вторая стадия восстановления грани 107
4.3 Завершение работы алгоритма 118
4.4 Улучшение качества сетки 128
4.5 Описание комплекса программ по построению тетраэдральных сеток 132
4.6 Сравнение результатов работы с другими генераторами сеток 134
5 Моделирование простраствепных течений идеального газа с использованием тетраэдральных сеток 155
5.1 Квазимонотонный численный метод повышенного порядка точности для решения уравнений Эйлера на расчетных сет ках нерегулярной структуры с тетраэдральными ячейками . 155
5.1Д Система уравнений 155
5.1.2 Численная схема 156
5.1.3 Граничные и начальные условия 159
5.1.4 Алгоритмы восстановления параметров на расчетном слое 162
5.2 Численные эксперименты 167
5.2.1 Отражение косой ударной волны от твердой стенки . 167
5.2.2 Дифракция плоской ударной волны на двугранном угле 170
5.2.3 Обтекание затупленного конуса 173
5.2.4 Обтекание модели самолета 175
Заключение 178
Литература
- Алгоритмы построения тетраэдризации Делоне множества вершин
- Алгоритм построения тетраэдризации Делоне для тел с кусочно-линейными границами
- Построение анизотропной триангуляции Делоне двумерной области
- Первая стадия восстановления граней
Введение к работе
Для численного моделирования физических процессов, описываемых дифференциальными уравнениями, необходимо иметь дискретное представление области, в которой протекают исследуемые физические процессы. Такое дискретное представление может задаваться расчетной сеткой.
Методам построения расчетных сеток посвящено множество работ как отечественных, так и зарубежных ученых (см. [13,15-17,21,23,24,30,31,34,37] и др.).
Относительно способа хранения информации об узлах расчетные сетки делятся на две большие группы: регулярные (структурированные) и нерегулярные (неструктурированные). В регулярных сетках элементы и взаимосвязь между ними однозначно характеризуется набором индексов узловых точек. Нерегулярной сеткой называют сетку, которая не является регулярной.
Структурированные сетки используются в конечно-разностных методах, при этом их регулярная структура позволяет эффективно организовать работу с разреженными матрицами при решении возникающих систем уравнений. Очевидным недостатком регулярных сеток является то, что они не могут быть построены для произвольной области. Существует подход, позволяющий увеличить класс областей, для которых можно использовать структурированные сетки. Этот подход заключается в использовании многоблочных сеток. В этом случае исходная область разбивается па несколько блоков, и в каждом блоке строится регулярная сетка. Однако этот подход обладает определенными недостатками. Во-первых, операция разбиения области на блоки является плохо автоматизируемой, что приводит к необходимости во многих случаях задавать блоки вручную. Во-вторых, для многих областей из-за их сложной геометрии либо невозможно построить многоблочную
сетку, либо количество блоков будет соизмеримо с количеством элементов неструктурированной сетки, построенной для этой области.
Нерегулярные сетки могут быть построены для любой произвольной области, в том числе и для динамически изменяющейся области, и в этом их основное преимущество. Для таких сеток достаточно просто производить локальную адаптацию к решению, не затрагивая топологию всей сетки. Процесс генерации таких сеток хорошо автоматизируется (см. обзор методов в [26]). Основным недостатком использования нерегулярных сеток является некоторая сложность методов численного решения задач математической физики на таких сетках. К таким методам относятся: метод конечных элементов и метод конечных объемов.
Таким образом, для выполнения численного моделирования физических процессов, протекающих в трехмерных областях сложной формы, возникает задача о построении сеток в таких областях. Это актуальная задача вычислительной математики.
Нерегулярные сетки различаются по типу составляющих их элементов, В двумерном случае выделяют треугольные, четырехугольные, смешанные и многоугольные сетки. Смешанные сетки — это сетки, состоящие из треугольных и четырехугольных элементов. Под многоугольными сетками понимают сетки, форма ячеек которых заранее не определена. Это сетки, получающиеся из ячеек Дирихле или сетки, получающиеся из равномерных прямоугольных при геометрической локальной адаптации их к сложной границе. В трехмерном случае выделяют тетраэдральные, шестигранные, смешанные (гибридные) и многогранные сетки. Трехмерные смешанные сетки могут состоять из тетраэдров, пирамид, призм и параллелепипедов. Наиболее распространенными в трехмерном случае являются тетраэдральные и смешанные сетки.
В данной работе рассматривается метод построения сеток с тетраэдральными ячейками. В настоящее время для построения таких сеток широко используется тетраэдризация Делоне, что связано с ее геометрическими свойствами. Однако тетраэдризация Делоне и ее модификации определены лишь для областей с кусочно-линейной границей, и алгоритмы ее по-
строения [70,112,114,117] существуют только для таких областей. Поэтому, когда требуется строить данный тин сеток для областей с криволинейной границей, исходную область приближают многогранником. Данный подход более или менее успешно применяется на практике, но он обладает одним существенным недостатком. В процессе генерации сетки возникает необходимость вставлять новые вершины на кусочно-линейную границу области. При этом перестроение поверхностной сетки, связанное с добавлением новой вершины, возможно лишь в пределах грани многогранника, на которой находится новая вершина, а это ограничение в некоторых случаях приводит к ухудшению качества сетки (см. главу 4). Таким образом, возникает задача о построении тетраэдризации Делоне и одновременном перестроении кусочно-линейной аппроксимации границы области.
Так как параллельно с тетраэдризацней будет перестраиваться и многогранник, то необходимо также решить задачу о построении поверхностной сетки на криволинейной границе заданной области. Причем не каждый метод построения поверхностных сеток может быть использован. Результирующая поверхностная сетка должна быть максимально близкой к триангуляции Делоне на криволинейных гранях [44,54]. Одним из методов генерации такой сетки является построение для каждой криволинейной грани двумерной анизотропной триангуляции Делоне в ее параметрическом пространстве и последующее ее отображение в трехмерное пространство. Сложность данного подхода, как и вообще триангуляции Делоне, состоит в необходимости поддерживать целостность границы, т.е. в данном случае криволинейные ребра должны явно присутствовать в триангуляции в параметрическом пространстве грани. Если целостность границы нарушена, то возникает задача о восстановлении границы. Эта задача успешно решена в изотропном случае для областей с кусочно-линейной границей (т.е. для стандартной двумерной триангуляции Делоне) [101,115] и в изотропном случае для областей с криволинейной границей (т.е. для двумерных областей с криволинейными границами) [45].
Построение двумерной анизотропной сетки с заданными криволинейными границами является актуальной задачей современной вычислительной
геометрии. Применение этого подхода при построении поверхностных сеток добавляет определенные сложности, связанные с тем, что отображение параметрического пространства в трехмерное может быть не взаимно однозначным. Рассмотрим основные сложности. Во-первых, параметризация грани может быть периодической функций по одной из переменных, что приводит к образованию стыковочных ребер в трехмерном пространстве. Во-вторых, параметризация поверхности может быть нерегулярной, т.е. иметь особые точки. В-третьих, наличие неоднозначностей может приводить к тому, что трехмерная триангуляция, полученная отображением двумерной анизотропной триангуляции в трехмерное пространство, может быть некорректной (см. рисунки 3.14, 3.16, 3.17 в разделе 3.3).
Эти три обстоятельства значительно увеличивают сложность построения поверхностных сеток, и возникает актуальная задача об адаптации существующих методов построения анизотропной сетки с учетом этих особенностей.
В данной работе задача о построении поверхностных сеток является вспомогательной, а вообще же она имеет самостоятельное значение. Поверхностные сетки используются в геоинформационных системах, а также в компьютерной графике, где полигональные модели применяются при рендеринге изображений.
Исследования проведены при финансовой поддержке РФФИ (гранты: 04-01-00402, 02-01-00318). Цель исследования
Разработка алгоритма построения поверхностных сеток для границ трехмерных областей произвольной формы с использованием двумерной анизотропной триангуляции Делоне.
Создание алгоритма построения тетраэдральных сеток в произвольных трехмерных областях, не требующего предварительной аппроксимации криволинейных границ кусочно-линейными элементами.
Создание программного комплекса по построению тетраэдральных сеток в сложных трехмерных областях с криволинейными границами.
Проведение тестовых и методических расчетов по построению вычислительных сеток в сложных пространственных областях.
Разработка алгоритма и программы, расчета нестационарных трехмерных газодинамических течений, базирующегося на использовании тетраэдральных сеток. Проведение тестовых расчетов задач газовой динамики па полученных тетраэдральных сетках.
Научная новизна. Новыми в диссертационной работе являются следующие положения и результаты:
Разработан алгоритм построения двумерной анизотропной триангуляции Делоне с заданными криволинейными границами. Дано обобщение метода восстановления ребер на случай криволинейных ребер и анизотропной триангуляции Делоне. Разработаны модификации алгоритма построения двумерных анизотропных сеток, связанные с использованием данного типа сеток для построения поверхностных сеток для произвольных трехмерных областей. Данные модификации учитывают особенности параметризации поверхностей, связанные с наличием стыковочных ребер и особых точек.
Предложено обобщение методов восстановления ребер в тетраэдризации Делоне с ограничениями для случая криволинейных ребер.
Разработан метод решения одной из самых сложных задач при построении тетраэдризации Делоне с ограничениями — задаче о восстановлении граней исходной области, причем она была решена для общего случая криволинейной границы.
Предложены методы уменьшения чувствительности алгоритмов построения тетраэдральных сеток к ошибкам округления.
Обоснованность и достоверность выводов и результатов обеспечена использованием современных средств вычислительной геометрии, сравнением результатов работы с результатами, полученных с помощью пакетов программ построения тетраэдральных сеток, а также сравнение результатов расчетов на полученных сетках с аналитическими решениями и с опубликованны-
ми расчетными и экспериментальными результатами, полученными другими авторами.
Практическая ценность
Разработанный и реализованный метод генерации тетраэдральных сеток для произвольных трехмерных областей с криволинейными границами позволяет получать качественные сетки для численного моделирования задач математической физики, таких как задачи прочности, упругости, механики жидкости и газа, теплоїіереноса.
Данные тетраэдральные сетки также могут быть использованы в качестве начальных данных для построения трехмерных смешанных (гибридных) сеток соответствующими непрямыми методами.
Предложенные методы построения поверхностных сеток могут быть использованы в компьютерной графике для создания полигональных моделей объектов, составляющих сцепу. На защиту выносятся следующие результаты и положения:
Метод восстановления криволинейных ребер при построении анизотропной триангуляции Делоне произвольной двумерной области.
Модификации метода построения двумерных анизотропных сеток, связанные с использованием данного типа сеток для построения поверхностных сеток трехмерных областей и учитывающие особенности параметризации поверхностей (наличие стыковочных ребер и особых точек),
Метод восстановления криволинейной границы при построении тетра-эдризации Делоне с ограничениями трехмерных областей сложной геометрической формы
Сравнение результатов работы созданного в диссертации алгоритма с результатами работы других генераторов сеток.
Комплекс программ для моделирования трехмерных нестационарных газодинамических течений в областях сложной геометрической формы.
Создание программного комплекса для построения тетраэдральных сеток произвольных трехмерных областей с криволинейными границами.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на 14th Int. Meshing Roundtable (San Diego, USA, 2005), Всероссийской конференции «Прикладная геометрия, построение расчетных сеток и высокопроизводительные вычисления» (ВЦ РАН, Москва, 2004), III—V международной конференции по неравновесным процессам в соплах и струях (NPNJ) (Истра-Москва, 2000, Санкт-Петербург, 2002, Самара, 2004), XI,XII,XIV международной конференции «Вычислительная механика и современные прикладные программные системы» (ВМ-СППС) (Москва, 2001, Владимир, 2003, Алушта, 2005), X, XII школе-семинаре «Современные проблемы аэрогидродинамики» (Сочи, 2002, Сочи, 2004), 9-ой международной школе-семинаре «Новые информационные технологии» (Судак, 2001), 23rd Int. Symposium on Shock Waves (Fort Worth, USA, 2001), 10th Int. Symposium on Flow Visualization (Kyoto, Japan, 2002), 5th Pacific Symposium on Flow Visualization and Image Processing (Chamonix, France, 2003), на семинаре института прикладной математики им. Келдыша (Москва, 2005).
Публикации. Приводимые в диссертации результаты отражены в 16 публикациях [3-12,27,47,48,57,62,122].
Содержание диссертации. Диссертация состоит из введения, пяти глав и заключения.
Первая глава посвящена обзору методов построения тетраэдральных сеток. В разделе 1.1 рассматривается метод дерева октантов, в разделе 1.2 рассматривается метод движущегося фронта.
В разделе 1.3 приводится определение d-мерной триангуляции Делоне, и рассматриваются ее геометрические свойства. Приводится обоснование выбора данного типа сеток в качестве основного метода построения тетраэдральных сеток в трехмерных областях.
В разделе 1.4 рассматриваются методы построения тетраэдризации Делоне заданного множества вершин: алгоритм заметания, пошаговый алгоритм прямого построения, метод отображения в пространство большей размерности. Особое внимание уделено итеративным алгоритмам построения тетраэдризации Делоне, т.к. в диссертационной работе именно итератив-
ные алгоритмы используются при построении тетраэдризации произвольной трехмерной области.
Для одной и той же области можно построить множество сеток. В разделе 1.5 приводится критерии оценки качества сеток, с помощью которых можно сравнивать сетки между собой.
Вторая глава посвящена построению тетраэдризации Делоне для областей кусочно-линейной границей. Тетраэдризация таких областей строится следующим образом. Сначала строится тетраэдризация вершин многогранника. (Область с кусочно-линейной границей это есть многогранник). Свойством с-мерной триангуляции Делоне является то, что она не допускает произвольного соединения вершин между собой. Это приводит к тому, что*-ребра и грани тела (трехмерной области), которые мы хотели бы видеть в тетраэдризации, там могут отсутствовать. Таким образом, следующий этап после построения тетраэдризации вершин многогранника — это решение задачи о восстановлении границы, которая в трехмерном случае разбивается на две подзадачи: восстановление отсутствующих ребер тела и восстановление отсутствующих граней тела. В разделах 2.1 и 2.2 описываются методы восстановления ребер и граней в случае кусочно-линейной границы. После восстановления границы происходит добавление вершин внутрь области. В разделе 2.3 приводится детальное описание алгоритма построения тетраэдризации Делоне с ограничениями для тел с кусочно-линейной границей.
Алгоритмы построения сеток очень чувствительны к ошибкам округления. Это происходит вследствие того, что в алгоритме определяется, какие операции должны быть выполнены в зависимости от результатов геометрических вычислений и ошибка в вычислениях, возникшая вследствие округлений, может приводить к построению неправильной сетки. Одним из методов решения проблемы чувствительности к ошибкам округления является использование арифметики повышенной точности. Однако, как показывается в разделе 2.4, применение одной арифметики повышенной точности недостаточно для обеспечения робастности геометрических расчетов. Наиболее чувствительной задачей к ошибкам округления является задача о положении точки относительно тетраэдра, т.е. определение того, где находится точ-
ка относительно тетраэдра: вне тетраэдра, внутри тетраэдра, па его грани или ребре. В разделе 2.4 рассматривается данная задача и сложности в ее решении, возникающие вследствие особенностей машинной арифметики, а также предложенные в диссертации дополнительные способы их преодоления. В частности, рассматривается метод использования априорной геометрической информации.
В разделе 2.5 рассказывается о разработанном в диссертации алгоритме локализации точки внутри тетраэдризации, т.е. решение задач о нахождении такого тетраэдра из тетраэдризации внутри которого или же на его границе находится заданная точка. Временная сложность этого алгоритма составляет 0(\ogn) операций, где п — количество тетраэдров в сетке. Также в данном разделе приводится алгоритм решения еще одной геометрической задачи: дано конечное множество Р точек, требуется указать все точки из Р, которые находятся внутри заданного шара.
Методы и алгоритмы, изложенные в разделах 2,4 и 2.5, имеют самостоятельную практическую значимость для вычислительной геометрии. Хотя они описаны во второй главе, посвященной построению тетраэдризации Делоне для тел с кусочно-линейной границей, тем не менее, они используются и при построении тетраэдризации для тел с криволинейной границей.
Построение тетраэдризации области начинается с тетраэдризации вершин некоторой поверхностной сетки границы области. Следователь]го, необходимо построить поверхностную сетку для этой области. Поверхность тела состоит из криволинейных граней, разделенных ребрами. Построим поверхностные сетки для каждой грани в отдельности и состыкуем их вдоль ребер тела. (Очевидно, что разбиение одного и того же ребра тела на отрезки должно быть одинаковым для всех граней тела, к которым ребро принадлежит; в противном случае состыковать сетки невозможно.) Следовательно, встает задача о построении поверхностной сетки для криволинейной грани. В главе 3 рассказывается о решении данной задачи. Для этого строится двумерная анизотропная триангуляция Делоне в параметрическом пространстве грани тела, а затем полученная сетка отображается в трехмерное пространство. В разделе 3.1 описывается используемая в диссертации
модификация алгоритма Лоусона для построения анизотропной триангуляции множества вершин. В разделе 3.2 рассматриваются разработанные в диссертации методы восстановления криволинейных ребер при построении двумерной анизотропной триангуляции Делоне. В разделе 3.3 рассматриваются особенности использования анизотропной триангуляции Делоне для построения поверхностных сеток, связанные с наличием в параметризации поверхностей стыковочных ребер и особых точек.
В главе 4 рассказывается о построении тетраэдризации Делоне с ограничениями для тел с криволинейными границами. Основное внимание уделено задаче восстановления криволинейных граней в тетраэдр изаци и (разделы 4.2 и 4.3). В разделе 4.4 описываются реализованные в диссертации методы улучшения качества сетки (сглаживание и топологическое усовершенствование сетки). В разделе 4.5 рассказывается о комплексе программ по построению тетраэдральных сеток. В разделе 4.6 производится сравнение генератора сеток, разработанного в диссертации, с тремя открытыми пакетами программ построения тетраэдральных сеток: TetGen, QMG и NetGen,
В пятой главе приводятся примеры расчетов на полученных сетках. Численно решались трехмерные уравнения Эйлера с использованием схемы Годунова С.К. высокого порядка точности. Данная схема приводится в разделе 5.1. В диссертации были выполнены следующие тестовые расчеты задач газовой динамики (раздел 5.2): отражение косой ударной волны, дифракция плоской ударной волны па двугранном угле и сверхзвуковое обтекание затупленного конуса под углом атаки. Для этих задач были сделаны сравнения с опубликованными расчетными и экспериментальными результатами.
Также сетка, построенная реализованным в диссертации алгоритмом, использовалась в Институте Математического Моделирования РАН для расчета обтекания полной компоновки модели самолета. В диссертации приводятся результаты соответствующих расчетов.
Алгоритмы построения тетраэдризации Делоне множества вершин
Рассмотрим двумерный линейный алгоритм заметания плоскости (англ. plane-sweep algorithm) [03]. Пусть ly является горизонтальной линией с у-координатой равной у. Пусть ymin минимальное значение у-координаты среди всех вершин V и предположим у ymiri. Для каждой точки р Є ly будем строить окружность Ср (рис. 1.7), верхняя точка которой совпадает с р, постепенно увеличивая ее радиус до тех пор, пока она не коснется какой-либо вершины v множества V. Обозначим Iy{v) С 1у открытый интервал, каждая точка которого р имеет соответствующую окружность Ср касающуюся только одной вершины і?. Для граничной точки р интервала Iy(v) соответствующая окружность Ср также касается другой вершины w, а, возможно, и некоторых других вершин. Последовательность интервалов Iy(vi),Iy(v2),..., Iy{vk) определяет упорядоченный набор ребер Делоне Fy = 1 2, 2 3,..., Ufc_iVfc. Fy может рассматриваться как разделитель треугольников Делоне, описанные круги которых имеют внутренности, лежащие ниже прямой 1у.
Рассмотрим теперь, что происходит, если прямая 1У сдвигается вверх. Набор Fy может изменяться в двух случаях. Во-первых, набор Fy изменится, если 1У коснется верхней точки описанной окружности вокруг трех вершин s,t,u таких, что ребра st и tu следуют друг за другом в наборе Fy. В этом случае интервал Iy(t) исчезнет и ребро su заменит в наборе Fy ребра st и tu. В этом случае треугольник stu является треугольником Делоне, а ребро su становится ребром Делоне. Если бы $ не была вершиной, то точка s лежала бы внутри некоторого интервала /у(2), который слева окружен некоторым интервалом Iy(v), а справа - интервалом 1у(и). Так как s является вершиной из V, то для слегка увеличенного значения у появится интервал Iy(s) и часть набора Fy, состоящая из ребер vt и tu, будет заменена набором vt,ts,st,tu.
Таким образом, линейный алгоритм заметания плоскости состоит в следующем. Алгоритм сохраняет текущий набор Fy и очередь событий, отсортированных по -координате. События бывают двух видов1, прохождение горизонтальной линией 1У новой вершины из V и прохождение верхней точки окружности. Изначально заметающая линия имеет у-координату, равную у тіш и очередь событий состоит из всех вершин V. Также будем предполагать, что очередь событий содержит события для каждой окружности, проходящей через три вершины s, t, и, такие, что ребра st и tu последовательно следуют друг за другом в наборе Fy. Если очередное событие это прохождение через верхнюю точку окружности, сформированную ребрами st и tu, то данные ребра замещаются в наборе Fy ребром su) и треугольник stu помечается как треугольник Делоне. Если очередное событие это прохождение через новую вершину, то происходит соответствующая модификация набора
Сложность данного алгоритма в двумерном случае составляет 0(nlog(n)), где п - число вершин. Изложенный здесь метод предполагает, что для каждого значения у не существует более одного события, т.е. не допускаются вершины, имеющие одинаковые у-координаты, и вершины, лежащие в верхней точке окружности описанной вокруг некоторого треугольника Делоне.
Данный алгоритм обобщается па трехмерный случай, только вместо заметающей линии рассматривается заметающая плоскость, параллельная одной из координатных плоскостей.
В англоязычной литературе данный алгоритм известен как "gift-wrapping algorithm". Он может применяться для построения и d-мернои триангуляции Делоне. Основная идея метода состоит в том, чтобы построив один d-мерный симплекс, постепенно рекурсивно к нему достроить все остальные rf-мерные симплексы Делоне [111].
Построение первого d-симплекса осуществляется следующим образом. Возьмем произвольную вершину г о их множества V. Это, очевидно, О-мерный симплекс Делоне. Т.е. существует d-мерный шар, содержащий данную вершину на своей границе и никаких других вершин множества V внутри себя. Будем постепенно увеличивать радиус шара, как бы раздувая его, до тех пор, пока не он не коснется другой вершины v\. Соединим эти две вершины, и получим ребро Делоне VQV\ (рис. 1.10 слева). Это есть 1-мерный симплекс S\. Пусть построен -мерный симплекс Делоне Sk {к d). Построим (к + 1)-мерпый симплекс Делоне Sk+i но следующему правилу (рис. 1.10 справа). Т.к. Sk является симплексом Делоне, то существуют описанный вокруг него шар S, не содержащий внутри себя других вершин из V, кроме вершин Sk- Будем увеличивать радиус этого шара таким образом, чтобы его центр Os перемещался в направлении, перпендикулярном к ft-мерной гиперплоскости, которая содержит sjt, как показано на рисунке. В этом случае центр шара 0$ остается равноудаленным от вершин симплекса Sk, следова-телыю, всегда возможно выбрать радиус для шара S, такой, что S продолжит касаться вершин Sk- Растяжение шара прекращается, когда он коснется новой вершины Vk+i- Данная вершина и вершины из Sk определяют новый симплекс Делоне Sfc+j,. Он действительно является симплексом Делоне, т.к. построенный вокруг него шар не содержит внутри себя вершин множества V.
Алгоритм построения тетраэдризации Делоне для тел с кусочно-линейными границами
В данном разделе производится обобщение предыдущих двух разделов. Основное внимание уделяется тому, как объединить все этапы построения сетки (восстановление ребер, измельчение двумерной сетки на грани, построении тетраэдризации и т.д.) в единый алгоритм.
1. Сначала подготавливаются структуры данных: для каждой вершины, ребра и грани тела создаются структуры данных. Для каждой грани выполняются подготовительные действия по построению для нее отдельной двумерной триангуляции Делоне (строится охватывающий грань прямоугольник, создаются два треугольника и в эту триангуляцию вставляются все вершины грани).
2. Построение сетки начинается с декомпозиции всех ребер тела на отрезки, пока все отрезки не будут иметь размер меньше заданного. При этом новые вершины также вставляются в двумерную триангуляцию Делоне каждой грани, на которой находится ребро. Каждый раз, когда вершина вставляется в триангуляцию или тетраэдризацию выполняется восстановление свойства Делоне. Далее об этом отдельно более упоминаться не будет.
3. Создаются кластеры для ребер, сходящихся под острыми углами. Соответствующий алгоритм описан в разделе 2.1. Для каждой двумерной триангуляции грани происходит восстановление ее ребер.
4. Происходит измельчение сетки на гранях до того момента, пока все треугольники не будут иметь заданные свойства (например, длина ребер треугольников не превышает заданную величину или минимальный угол в треугольнике больше заданного значения).
5. Строится тетраэдризация Делоне полученного на предыдущих этапах множества вершин. До этого этапа построение тетраэдризации не производится.
6. Происходит восстановление ребер в тетраэдризации. Если во время восстановления ребер требуется вставить новую вершину па ребро, то она вставляется во все двумерные триангуляции граней, на которых находится ребро, а также в тетраэдризацию.
7. Происходит восстановление граней тела в тетраэдризации (см. раздел 2.2).
8. Измельчается сетка внутри тела до того момента, пока все тетраэдры не будут иметь удовлетворять заданным критериям. Для тетраэдров обычно рассматривают два критерия. Первый критерий — длина ребер тетраэдров не превышает заданную величину. Второй критерий — это ограничение на максимальное значение В, где В — отношение радиуса описанной сферы к длине минимального ребра тетраэдра. Новые вершины вставляются в центр описанной сферы.
На данном этапе уже не производится проверка на попадание новой вершины в экваториальные сферы граничных треугольников. Поэтому необходимо «вручную» следить за тем, чтобы новые вершины не находились слишком близко к границе. Делается следующим образом. Пусть 1тах — заданное ограничение на длину максимального ребра тетраэдра. Пусть h — высота правильного тетраэдра со стороной 1тах- Тогда новая вершина не вставляется, если она расстояние от нее до ближайшей грани меньше, чем ОМ.
Пример работы изложенного здесь алгоритма для тела с кусочно-линейной границей приведен на рисунке 2.13.
Рассмотрим более подробно как влияет требование, согласно которому диаметральные и экваториальные шары граничных элементов должны быть пустыми, на результирующую сетку. Основное следствие из этого является то, не допускается создание сетки плохого качества вблизи границы. Этот факт иллюстрируется рисунком 2.14. Треугольник ADE должен быть удален. Центр его описанной окружности v попадает в диаметральную окружность отрезка ВС ребра е исходного тела. Если бы вершина v была бы вставлена, то был бы образован треугольник BvC, который удовлетворяет свойству Делоне, и как следствие не будет удален перестановками. Этот треугольник является «плохим» с точки зрения качества сетки, так как имеет острые углы. Более того, он не может быть удален стандартными средствами, так как центр его описанной окружности лежит вне грани. Поэтому вершина v не вставляется в триангуляцию, а вместо этого делится отрезок ВС. После вставки новой вершины в центр отрезка ВС и восстановления свойства Делоне &ADE перестанет существовать. Таким образом, AADE будет удален без ухудшения качества сетки. Для конформной триангуляции Делоне верны следующие две леммы [ПО, 115]. Лемма 2.1
Пусть Т —- двумерная триангуляция Делоне и каждое ее ребро, принадлежащее только одному треугольнику (внешнее ребро), имеет диаметральный круг, внутрь которого не попадает пи одной вершины триангуляции Т. Тогда центр описанной окружности вокруг любого из треугольников лежит внутри Т.
Лемма 2.2
Пусть Т — тетраэдризацпя Делоне и каждая ее грань тетраэдра, принадлежащая только одному тетраэдру (внешняя грань), имеет экваториальный шар, внутрь которого не попадает ни одной вершины тетраэдризации Т. Тогда центр описанной сферы вокруг любого из тетраэдров лежит внутри Т.
Эти две леммы означают, что в случае конформной триангуляции (тетраэдризации) Делоне, удовлетворяющей условиям леммы, удаление каждого треугольника или тетраэдра приводит к вставки новой вершины в триангуляцию (тетраэдризацию). На этом факте основывается доказательство, что измельчением сетки можно добиться заданного качества сетки, если входное тело не имеет острых углов, т.к. каждый плохой элемент может быть удален.
В трехмерном случае, если нет двугранных углов меньших, чем 90, то значение В можно сделать для всех тетраэдров не превышающее Dmax = 2.
В данной работе не требуется, чтобы диаметральные и экваториальные шары оставались пустыми всегда. Во-первых, для экваториальных шаров этого добиться очень сложно, а, во-вторых, это не всегда нужно (рис. 2.9). Конечно, отказ от строгого выполнения этих требований может приводить к некоторому ухудшению качества сетки, но в целом качество падает несильно. Бесспорное преимущество строго выполнения этих требований то, что это позволяет всегда улучшить наихудший элемент.
Построение анизотропной триангуляции Делоне двумерной области
Построение триангуляции по набору точек это лишь часть задачи, которую необходимо решить. Для того чтобы успешно построить анизотропную триангуляцию Делоне области (и, как следствие, поверхностную сетку), надо построить такую сетку, граница которой присутствует в триангуляции в виде ребер треугольников, т.е. решить задачу о восстановлении криволинейных ребер. Рассмотрим, как можно использовать методы, описанные в разделе 2.1, для случая криволинейных ребер и анизотропной триангуляции. Определение 3.2
Пусть ребро -- это часть кривой c(t) = (x(t),y(t),z(t))T, t Є [ о і], огра-ниченная вершинами VQ = c(to), V\ = c(ti), to t\. Пусть po,... ,pn последовательность точек в трехмерном пространстве на ребре грани, и рг = г(иг,Уі) = c{ti), причем ро и рп совпадают с вершинами ребра. Набор отрезков {si — [pi, РІ+І],І = 0 ... n — 1} составляют в трехмерном пространстве ломаную, вписанную в данное ребро. Ребро называется восстановленным в параметрическом пространстве грани, если:
1. Существует ломаная, для каждого отрезка Si \рі(щ,Уі), pi+i(ui+i, Vi+i)] которой в параметрическом пространстве существует ребро треугольника с вершинами (щ,У{) и (щ+\, fj+i).
2. Выпуклые оболочки СІ множеств Mi = {c(t), U t U+i}, і = 0 ... n — 1 пересекаются только в конечных точках pi (рис. 3.5).
3. Внутренность множества СІ (І = О ... п — 1) не содержит ни одной вершины qj, где qj - вершины треугольников, составляющих триангуляцию грани в параметрическом пространстве (рис. 3.6)
Анизотропная триангуляция строится по следующей схеме. Сначала происходит измельчение ребер таким образом, чтобы получившиеся отрезки удовлетворяли условию аппроксимации криволинейных ребер (угол между касательными к ребру в концах отрезка не должен быть больше указанного значения), а также, чтобы их длина не превышала заданную величину. Далее для полученного набора точек строится триангуляция в параметрическом пространстве грани, как описано в разделе 3.1.
Следующим этапом является восстановление ребер в параметрическом пространстве грани. Ребра восстанавливается по аналогии со случаем кусочно-линейной границы — путем удовлетворения критерию пустоты диаметральных эллипсов соответствующих отрезков ломаной. Диаметральный эллипс — это эллипс, середина которого совпадает с серединой отрезка, а квадратичной формой является либо значение метрического тензора в середине отрезка либо полусумма значений метрического тензора в его вершинах. Следует отметить, что в общем случае наличие пустого диаметрального эллипса у отрезка не гарантирует его наличия в триангуляции в параметрическом пространстве, как это было в случае плоской грани. Связано это с тем, что кривую 7, состоящую из множества точек, равноудаленных от заданной точки, мы приближаем эллипсом. И чем больше изменение значений первой квадратичной формы внутри эллипса, тем сильнее кривая 7 отличается от эллипса. Однако при измельчении сетки на грани эта разница все меньше и меньше, т.к. первые производные координатных функций являются непрерывными функциями. Таким образом, после того как диаметральный эллипс перестал содержать внутри себя и на своей границе другие точки триангуляции, необходимо проверить действительно ли для данного отрезка ломаной Si = \pi(ui,Vi), pi+i(ui+i} Vt+i)] существует ребро треугольника с вершинами (ui,Vi) и (щ+\, fj+i). Если нет, то отрезок декомпозируется путем вставки новой вершины на кривую. Причем делится не сам отрезок ломаной, а добавляются два новых звена в ломаную путем вставки новой вершины р на ребро такой, что р = c(t ) = r(u ,v )\ U t ii+1. Параметр і подбирается таким образом, чтобы новые два отрезка имели приблизительно равную длину. В идеале желательно, чтобы новых два отрезка имели равную длину, однако это задача является вычислительно сложной. В данной работе просто полагается t — (l/2)(ti + ti+i). Пустота диаметрального эллипса не гарантирует появление отрезка в триангуляции (хотя на практике этот отрезок почти всегда присутствует в триангуляции), однако выполнение этого условия позволяет получать хорошую сетку вблизи ребер, так как новые вершины не допускаются близко к границам грани (рис. 2.14).
Чтобы не возникло бесконечного цикла по восстановлению ребер, описанного в разделе 2.1, также необходимо для каждой вершины создать кластеры, состоящие из отрезков ребер, сходящихся в трехмерном пространстве в данной вершине под углами менее СО градусов. II здесь возникает определенная сложность. Обратимся к рисунку 3.7 слева. Отрезки О А и ОВ имеют угол, чуть больший 60 градусов. То есть данные отрезки не должны образовывать кластер, однако при более точном представлении ребер отрезки ОС и OD образуют угол меньше 60. А угол между касательными ребер (а и (3), проведенных из их общей точки О еще меньше. Возможна и обратная ситуация (рис. 3.7 справа). Угол между касательными а и (3 больше GO градусов, а угол между отрезками ломаной меньше. Поэтому кластер создается при выполнении хотя бы одного из двух условий: либо угол между касательными а и j3 меньше 60, либо отрезки ломаных двух ребер сходятся в общей вершине О под углом меньшим, чем 60. Здесь действует простое правило: лучше создать излишний кластер, чем его не создать там, где это действительно необходимо. Несмотря на то, что пустота диаметрального эллипса и не гарантирует присутствие отрезка в триангуляции грани, криволинейные ребра всегда восстанавливаются, т.к. здесь можно применить те же рассуждения, что приведены в конце раздела 2.1.
После восстановления ребер в параметрическом пространстве необходимо определить, какие треугольники принадлежат грани (являются внутренними), а какие нет (являются внешними). В случае кусочно-линейной границы эта операция не вызывает сложностей. Достаточно взять любую внутреннюю точку Р (рис. 3.9) треугольника и с помощью алгоритма проверки принадлежности точки многоугольнику [38[ определить тип данного треугольника.
Первая стадия восстановления граней
Рассмотрим находящиеся в трехмерном пространстве треугольники всех триангуляции t\d граней тела. На первой стадии восстановления граней происходит измельчение сеток на гранях тела и тетраэдризации до того момента, пока экваториальный шар каждого такого треугольника из t\d будет содер треугольника и данная вершина v находятся на одной грани тела (рис. 4.5).
Пусть внутри экваториального шара треугольника t находится несмежная с ним вершина v3d. Тогда соответствующий треугольник tps из параметрического пространства удаляется путем вставки новой вершины wps в центр его описанного эллипса. Трехмерная вершина w3d, являющаяся образом вершины wps, в свою очередь вставляется в тетраэдризацию. После вставки вершины wps в триангуляцию tpS выполняются необходимые перестановки для восстановления свойства Делоне (раздел 3.1). Также соответствующие перестановки (раздел 1.4.4) выполняются после вставки вершины wZd в тетраэдризацию. Если новая вершина wps должна попасть в треугольник rps, и при этом г3й и ум являются смежными, то wps не вставляется в триангуляцию tps. ,3d Вместо этого вершине v разрешается находиться внутри диаметрального шара треугольника t 3d
Также необходимо следить, чтобы ребра тела оставались восстановленными: если вершина w3d попадает в диаметральный шар отрезка $ ребра тела, то вершины wps и ь)ы не вставляются, а вместо этого делится отрезок s.
Бесконечного цикла, описанного в разделе 2.2, не возникнет, так как не требуется, чтобы экваториальные шары всех треугольников из t\d были пустыми. Фактически, разрешение определенным вершинам находиться внутри диаметральных шаров треугольников вводилось только с одной целью — избежать бесконечного цикла.
Рассмотрим, для чего нужен данный этап. Если две криволинейные грани расположены близко друг от друга, то возможна ситуация, когда некоторый треугольник из t\d одной грани тела в трехмерном пространстве пересекает другую грань тела (см. рис. 4.6), что может приводить к самопересечению триангуляции t d этих граней. Такое может произойти из-за того, что условие аппроксимации для криволинейных граней выбрано неудачно. (Данное условие есть ограничение на максимальное значение угла между нормалями к грани в вершинах треугольника.) На данном этапе происходит одновременное перестроение тетраэдризации и триангуляции ts граней тела, и самопересечения удаляются.
В случае кусочно-линейной границы обеспечение пустоты экваториальных шаров нужно лишь для создания сетки хорошего качества вблизи границы. Правда при этом наблюдается чувствительность триангуляции одной грани к триангуляции другой несмежной грани (см. раздел 2.3), что обычно рассматривается как недостаток триангуляции Делоне. Однако в случае криволинейной границы этот недостаток оборачивается преимуществом.
Непосредственной проверки на самопересечение не производится, что связанно с вычислительной сложностью этих операций, т.е. нет теоретических гарантий, что на данном этапе все самопересечения будут удалены. Тем не менее, тестирование данного алгоритма для тонкостенных тел с сильно искривленными границами показало его практическую работоспособность. Одно из таких тел изображено на рисунке 4.7.
После выполнения первой стадии, для каждой грани выполняется вторая стадия, являющаяся основной. На второй стадии криволинейные грани тела восстанавливается по отдельности, т.е. следующая грань рассматриваются тогда и только тогда, когда предыдущая грань была полностью восстановлена.
Основная идея восстановления грани тела на втором этапе следующая. Найти некоторые грани тетраэдров, заведомо принадлежащих кусочно-линейной аппроксимации Ту криволинейной грани Г в тетраэдризации. Затем рекурсивно, используя эти грани тетраэдров как начальные, найти по некоторому правилу все остальные грани тетраэдров, составляющие аппрок симацию Тг криволинейной грани в тетраэдризации. Рассмотрим теперь второй этап более подробно.
Каждая криволинейная грань тела восстанавливается следующим образом. Сначала создается список L из граней тетраэдров трехмерной сетки, являющихся образами треугольников из двумерной триангуляции грани tp3 в параметрическом пространстве. Такие грани тетраэдров маркируются как принадлежащие аппроксимации Тг. Если каждый треугольник из t\d присутствует в тетраэдризации в виде грани тетраэдра, и набор получившихся граней тетраэдров удовлетворяет условиям топологической целостности сетки (см. ниже), то грань уже восстановлена, и никаких дальнейших действий не нужно. Если же такой список оказывается пустым, т.е. пи для одного треугольника из двумерной триангуляции грани tpS в параметрическом пространстве нет соответствующей ему грани тетраэдра в трехмерной сетке, то это означает, что триангуляция t d достаточно сильно отличается от тетраэдрнзации Делоне множества вершин грани. Будем полагать, что чем большее количество треугольников из t d присутствует в виде граней тетраэдров тетраэдрнзации Делоне множества вершин грани, тем «ближе» /3(; к соответствующей тетраэдральной сетке. Свойством метода построения поверхностных сеток, изложенного в главе 3, является то, что чем мельче сетка tpS в параметрическом пространстве, тем «ближе» соответствующая ей сетка t d к тетраэдрнзации Делоне. Следовательно, проводим измельчение сетки tpS в параметрическом пространстве грани и добавление полученных вершин в тетраэдризацию до тех пор, пока в список не попадет хотя бы одна грань тетраэдра.
