Трехмерная триангуляция

Содержание

Введение

. Постановка задачи

1.1 Основные структуры данных

.1.1 Узлы с соседями

.1.2 Двойные ребра

.1.3 Узлы и треугольники

.1.4 Узлы, ребра и треугольники

1.2 Методы триангуляции

.2.1 Прямые методы

.2.2 Итерационные методы

.3 Особенности построения сеток в сложных областях

.4 Оценка качества сетки

Выводы по главе

. Реализация

2.1 Программная среда реализации

.2 Результаты работы программы

Заключение

Список использованных источников

Введение

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

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

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

Обычно математические методы, разработанные для случая двух измерений, легко переносятся на случай трех и более измерений. Однако, трехмерное пространство обладает рядом особенностей, которые затрудняют подобный перенос:

-   плоскость можно заполнить правильными треугольниками, пространство правильными тетраэдрами заполнить нельзя;

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

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

Важной задачей является автоматическое построение триангуляционной сетки объекта, представленного параллелепипедом, так как в дальнейшем она может использоваться для триангуляции более сложных областей. И ее применение значительно экономит машинные ресурсы и время.

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

1.     
Постановка задачи

математический моделирование компьютерный триангуляционный

Задачей является автоматическое построение триангуляционной сетки области, представленной прямоугольным параллелепипедом.

Изначально задается область и ее размеры. Это делается путем задания плоскостей каждой из шести граней прямоугольного параллелепипеда, используя нормальное уравнение плоскости (формула 2.1).

+ By + Cz + D = 0        (2.1)

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

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

-  исследование методов триангуляции;

-  исследование структур данных представления триангуляции;

-  выбор структуры и метода построения триангуляции;

-   написание программы, выполняющей автоматическое построение триангуляционной сетки на примере прямоугольного параллелепипеда;

1.1    Основные структуры данных

Структура для представления триангуляции влияет на трудоёмкость алгоритмов, а также на скорость конкретной реализации. Выбор структуры может зависеть от цели дальнейшего использования триангуляции. В триангуляции 3 вида объектов: узлы, рёбра и треугольники. В алгоритмах построения триангуляции возможны операции: получение координат узлов треугольника, списка образующих его рёбер, списка соседних треугольников, координат узлов ребра, списка смежных рёбер узла. Рассматриваются наиболее часто встречающиеся структуры [1].

1.1.1  Узлы с соседями

Для каждого узла хранятся его координаты на плоскости и список указателей на соседние узлы, с которыми есть общие рёбра (рисунок 2.1).

Рисунок 2.1 - Связи узлов структуры «Узлы с соседями»

Среднее число смежных узлов равно 6 [2].

Недостатки такого представления [2]:

-  треугольники не представляются, что является препятствием для дальнейшего использования триангуляции;

-   переменный размер структуры узла, который приводит к неэкономному расходу памяти.

1.1.2   Двойные ребра

Каждое ребро входит в структуру дважды, направленное в противоположные стороны (рисунок 2.2).

Рисунок 2.2 - Связи рёбер (слева) и неявное задание треугольников (справа) в структуре «Двойные рёбра»

Для ребра хранятся указатели [2]:

- на концевой узел ребра;

-   на следующее по часовой стрелке ребро в треугольнике, находящемся справа от данного ребра;

-   на ребро, соединяющее те же узлы триангуляции, что и данное, но направленное в противоположную сторону.

Дополнительно можно ввести указатель на треугольник, находящийся справа от ребра.

 Недостатками данной структуры является представление треугольников в неявном виде и большой расход памяти [2].

1.1.3   Узлы и треугольники

Для каждого треугольника хранятся три указателя на образующие его узлы и три указателя на смежные с ним треугольники (рисунок 2.3).

Рисунок 2.3 - Связи треугольников структуры «Узлы и треугольники»

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

Данная структура часто применяется на практике из-за простоты и удобства программирования алгоритмов на её основе [2].

1.1.4   Узлы, ребра и треугольники

Задаются узлы, ребра и треугольники. Для узла хранятся его координаты на плоскости, для ребра - указатели на два концевых узла и на два соседних треугольника, для треугольника - указатели на три образующих его ребра [3]. Нумерация точек и соседних треугольников производится в порядке обхода по часовой стрелке, напротив точки с номером находится ребро, соответствующее соседнему треугольнику с таким же номером (рисунок 2.4).

Рисунок 2.4 - Связи треугольников (слева) и рёбер (справа) структуры «Узлы, рёбра и треугольники»

Данная структура применяется в задачах, где требуется в явном виде представлять рёбра триангуляции [2]. Недостатком данной структуры является большой расход памяти.

1.2 Методы триангуляции

Все методы триангуляции по принципу построения можно разбить на две большие группы: прямые методы и итерационные методы (рисунок 2.5). В прямых методах сетка строится за один этап, причем ее топология (иначе говоря, граф связей между узлами) и координаты всех узлов известны изначально. В итерационных методах сетка строится последовательно; на каждом шаге добавляется один или несколько элементов, причем изначально не известны ни координаты узлов, ни топология сетки. Кроме того, координаты узлов и топология могут меняться прямо в процессе построения [1].

Сетки, построенные с помощью прямых методов, могут быть использованы и в итерационных методах. В первую очередь это касается методов граничной коррекции [3, 4].