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

Тип работы:
Курсовая
Предмет:
Экономические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Содержание

  • Введение
  • 1. Постановка задачи
    • 1.1 Основные структуры данных
    • 1.1.1 Узлы с соседями
    • 1.1.2 Двойные ребра
    • 1.1.3 Узлы и треугольники
    • 1.1.4 Узлы, ребра и треугольники
  • 1.2 Методы триангуляции
  • 1.2.1 Прямые методы
  • 1.2.2 Итерационные методы
  • 1.3 Особенности построения сеток в сложных областях
  • 1.4 Оценка качества сетки
  • Выводы по главе
  • 2. Реализация
    • 2.1 Программная среда реализации
    • 2.2 Результаты работы программы
  • Заключение
  • Список использованных источников

Введение

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

Триангуляция используется в различных областях деятельности человека, таких, как медицина, строительство, физика, химия и т. д. Например, в медицине с помощью триангуляции можно решить вопросы диагностики объема поражения органа, планирования и характера оперативного вмешательства, правильной оценки состояния костных фрагментов, а в строительстве — расчет прочностных характеристик здания.

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

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

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

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

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

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

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

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

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

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

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

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

Ax + 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]. Размещение узлов в методах на основе критерия Делоне нередко осуществляется с помощью одного из прямых алгоритмов (с последующей коррекцией) [5].

Рисунок 2.5 — Классификация методов дискретизации

1.2.1 Прямые методы

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

Рассмотрим, например, так называемую «кубическую сетку» (рисунок 2. 6), то есть сетку, полученную разбиением исходного параллелепипеда на равные «кубы». Если размеры куба — hx, hy, hz, и он ориентирован по осям координат, то узел с индексами i, j, k имеет координаты (Ox + i*hx, Oy + j*hy, Oz + k*hz), а его соседями являются узлы с индексами (i ± 1, i, k), (i, j ± 1, k) и (i, j, k ± 1).

Рисунок 2.6 — Кубическая сетка

Методы на основе шаблонов

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

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

Рисунок 2.7 — Разбиение куба на шесть (слева) и пять (справа) тетраэдров

Также существуют другие шаблоны, обладающие лучшими показателями за счет введения дополнительных узлов, каждый из которых соединяется с вершинами куба (рисунок 2. 8).

Рисунок 2.8 — Вставка внутрь кубической сетки дополнительных вершин; справа отдельно изображен получающийся в результате ромбовидный элемент

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

1) граничные — в виде четырехугольной пирамиды (т.е. пирамиды, основанием которой является квадрат);

2) внутренние — в виде объемного ромба, составленного из двух четырехугольных пирамид, соединенных основаниями.

Чтобы разбить граничные пирамидальные элементы, достаточно вставить диагональное ребро (причем произвольно ориентированное); при этом получаются два одинаковых тетраэдра с АХ порядка 0.5 [1].

Разбить внутренние ромбовидные элементы можно уже несколькими различными способами, и именно выбранным вариантом различаются между собой 2 вида шаблонов:

1) Шаблон 1 — вставка диагонального ребра между узлами кубической сетки (рисунок 2. 10):

2) Шаблон 2 — вставка ребра между дополнительными узлами (рисунок 2. 6):

Рисунок 2.9 — вставка ребра между узлами кубической сетки

Рисунок 2. 10 — вставка ребра между дополнительными узлами

Триангуляцию цилиндра разумнее всего проводить путем разбиения его на слои (рисунок 2. 11).

Рисунок 2. 11 — Построение призматической сетки в цилиндре

Далее нужно разбить конечный элемент — пятигранную призму — на тетраэдры (рисунок 2. 12).

Рисунок 2. 12 — Вставка в призматическую сетку дополнительных узлов

Методы отображения

Методы отображения основаны на возможности построения взаимно-однозначного отображения между областями различной геометрической формы. Таким образом, используя оператор отображения, можно перенести сетку из некоторой (более простой) области на заданную.

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

Как правило, для отображения используются два типа преобразований — «простейшие» аффинные (линейные), позволяющие только растягивать/сжимать сетку и более универсальные изопараметрические, позволяющие отображать сетки даже в криволинейные области (рисунок 2. 13).

Рисунок 2. 13 — Виды преобразований

Аффинным называется линейное преобразование координат:

(2. 2)

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

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

Сущность изопараметрического преобразования заключается в следующем: задается некая система внутренних координат (называемых «барицентрическими»), которая однозначным образом связывает положение любой точки данной геометрической формы (треугольник, квадрат, тетраэдр и т. д.) с определенным множеством базисных точек, также принадлежащих данной геометрической форме (в качестве таких точек обычно выбираются углы, середины сторон и т. п.). Таким образом, изменив положение базисных точек, можно легко определить и новое положение всех остальных точек, используя их барицентрические координаты [1].

Для каждой точки x=(x1, x2) невырожденного треугольника с вершинами б1, б2, б3 (вершина бi имеет координаты (бi1, бi2)), барицентрические координаты л1, л2, л3 вводятся как решение системы:

Барицентрические координаты легко определяются через отношения площадей треугольников (рисунок 2. 14):

Рисунок 2. 14 — Барицентрические координаты

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

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

Методы на основе критерия Делоне

В первую очередь напомним, что такое критерий Делоне. Говорят, что треугольная сетка на плоскости удовлетворяет критерию Делоне (или является триангуляцией Делоне), если внутрь окружности, описанной вокруг любого треугольника, не попадают никакие другие узлы этой сетки [7].

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

Рисунок 2. 15 — Сетка, удовлетворяющая критерию Делоне (слева), и не удовлетворяющая ему (справа)

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

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

У двумерного «флипа» есть и трехмерный аналог, хотя основанный на другой идее. Почти любые два соседних тетраэдра можно превратить в три. Для этого достаточно вставить внутрь шестигранника, образованного тетраэдрами, внутреннее ребро (рисунок 2. 16), причем сделать это можно единственным образом. Слово «почти» стоит здесь потому, что если любые три вершины этого шестигранника лежат на одной прямой либо четыре его вершины лежат в одной плоскости, то эта операция приведет к образованию вырожденных тетраэдров. Операция замены 2 тетраэдров на 3 и наоборот называется «трейд» (от англ. trade) [3].

Рисунок 2. 16 — «Трейд» — замена 2 тетраэдров на 3

Попытки использовать «трейд» для приведения произвольной трехмерной сетки к триангуляции Делоне закончились неудачно, поскольку такие алгоритмы очень часто зацикливались в локальных оптимумах. Вместе с тем не так давно был получен важный теоретический результат: канадский математик Б. Джо (Barry Joe) доказал, что если к уже существующей триангуляции Делоне добавить новые тетраэдры (разбив один из внутренних или присоединив тетраэдр к внешней грани), то полученную сетку можно гарантированно привести к триангуляции Делоне с помощью последовательных «трейдов» [9]. Этот факт играет огромную роль в построении триангуляций Делоне с ограничениями.

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

Частичным решением этой проблемы может быть использование числовых типов с фиксированной запятой. За счет отдельного хранения в 24-байтной структуре целой и десятичной частей числа (в виде целых чисел), на указанных выше плохо обусловленных задачах можно добиться точности вплоть до 10 знака, что является уже более-менее допустимым результатом [5].

Недостатком этого подхода является (весьма существенное) снижение скорости вычислений. Поэтому все эти операции приходится реализовывать на уровне подпрограмм, что приводит к дополнительным затратам ресурсов.

Методы исчерпывания

Общая идея этого класса методов заключается в последовательном изымании из заданной области фрагментов тетраэдрической формы до тех пор, пока вся область не окажется «исчерпана». Впрочем, этот легко представимый в воображении процесс на самом деле имеет мало общего с практической реализацией. Английское название «advancing front» (что можно перевести как «продвижение фронта»), пожалуй, лучше отражает сущность алгоритмов.

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

Триангуляции границы является тем самым «фронтом», упоминаемым в названии. Используя какой-либо треугольник из фронта, можно на его основе построить тетраэдр, причем четвертой вершиной тетраэдра может быть либо другая вершина фронта, либо дополнительный узел, помещаемый внутрь заданной области. При изъятии полученного тетраэдра из фронта может быть удалено от 1 (случай вставки дополнительного узла) до 4 граней и одновременно добавлено от 1 до 3 новых граней. Таким образом, текущий фронт дискретизации постепенно продвигается в пространстве — откуда и само название «advancing front». Обновив данные о фронте, можно вновь изъять тетраэдр, снова обновить фронт и так далее, пока вся область не окажется «исчерпана».

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

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

Стоит также помнить, что во время работы алгоритма фронт может разбиться на несвязанные фрагменты.

Четвертой особенностью алгоритмов исчерпывания является необходимость контроля над объемом и/или линейными размерами получающихся тетраэдров [3].

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

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

Уcловно можно выделить два типа сложных областей:

1) области, состоящие из непересекающихся замкнутых подобластей (рисунок 2. 17);

2) области с внутренними ограничениями в виде поверхностей или кривых (рисунок 2. 18).

Примером области первого типа служит модели композитных материалов, примером второго — модели, исследующие развитие трещин в материале.

Рисунок 2. 17 — Пример сложной области I типа: шар в кубе (композитный материал)

Рисунок 2. 18 — Пример сложной области II типа: фрагмент плоскости в кубе

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

Для сложных областей второго типа обычно используются методы на основе критерия Делоне, либо методы граничной коррекции [7, 9, 10]. Эти методы с некоторыми дополнительными условиями можно использовать и для дискретизации областей первого типа.

1.4 Оценка качества сетки

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

, (2. 4)

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

Поскольку величина полученная из формулы (2. 4) имеет порядок десятых и сотых, для наглядности ее удобно относить к значению идеального случая — правильного тетраэдра. (Для него, как можно подсчитать, эта величина равна). Назовем это отношение «аппроксимационной характеристикой» (АХ) элемента. Возможные значения АХ лежат в пределах от 0 до 1; чем ближе к 1, тем лучше.

Для качественного анализа сетки наибольшую важность имеют минимальное и среднее значения АХ: первое участвует в оценках качества аппроксимации, второе свидетельствует об общем качестве сетки. Для геометрически сложных областей хорошим результатом будет среднее значение АХ, равное хотя бы ½. [12]

Существуют и другие критерии оценки качества элементов сетки (таблица 2. 1)

Таблица 2.1 — Критерии оценки качества элементов сетки

Критерий

Формула

Интервал возможных значений

Оптимальное значение

1

2

3

4

Отношение радиуса описанной сферы к радиусу вписанной

3. 0

Отношение длины наибольшего ребра к радиусу вписанной окружности

4. 898 979…

Отношение радиуса описанной окружности к длине наибольшего ребра

0. 612 375…

Отношение длин наибольшего и наименьшего ребер

1. 0

Отношение 4-й степени объема тетраэдра к кубу суммы квадратов площадей граней

4. 572 474*10-4

Отношение куба среднего арифметического длин ребер к объему тетраэдра

8. 4 852 816…

Отношение куба среднего геометрического длин ребер к объему тетраэдра

8. 4 852 816…

Наибольший двугранный угол

(1. 23…)

Минимальный телесный угол

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

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

Сетки, полученные прямыми методами, являются структурированными, т. е. зная только индексы узла, можно определить всех его соседей, а также вычислить координаты. Это важное свойство позволяет существенно экономить компьютерные ресурсы [1].

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

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

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

Поскольку перед построением сетки ничего нельзя сказать о ее будущей структуре, нельзя гарантировать и ее качества. Часто построенную сетку можно существенно улучшить с помощью одного из многочисленных методов оптимизации [7, 8].

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

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

2. Реализация

В работе реализован алгоритм построения триангуляционной сетки для области, представленной параллелепипедом. Применяется прямой метод на основе шаблонов.

2. 1 Программная среда реализации

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

Для создания программы, выполняющей построение триангуляционной сетки, не требуется использование сложных графических эффектов, достаточно использования интерфейса GDI [13]. Вывод графической информации может проходить с использованием объектов: пера и кисти. Для вывода графической информации могут быть применены методы рисования линий LineTo, MoveTo.

В Delphi и C++ Builder используемые графические функции библиотеки VCL являются надстройками над аналогичными функциями из WinAPI, при этом размер исполняемого файла Delphi больше, как и размер файла C++ Builder. MFC — библиотека классов С++, надстройка над WinAPI [13]. Поэтому средой реализации можно выбрать Win32 Application, непосредственно взаимодействующее с функциями WinAPI.

Программа написана на языке Visual C++ 2008 с помощью Win32 Application. Используются заголовочные (*. h) и исходные файлы (*. cpp), файлы ресурсов (*. rc). Используется библиотека документов по технологиям Microsoft MSDN и WIN API Help.

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

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

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

В качестве входных данных задается размер области в трехмерных координатах, а также размер отдельного «куба» «кубической сетки».

Затем в массиве сохраняются координаты каждого узла «кубической сетки». Каждый «куб», в зависимости от заданного шаблона, разбивается на тетраэдры. Информация об узлах каждого тетраэдра, об их соседях, о количестве тетраэдров хранится в заданной структуре данных.

Далее с использованием графической библиотеки языка С++, для визуальной оценки качества, сетка рисуется на экране.

Так как визуально оценить качество сетки весьма трудно, это делается при помощи уравнений для оценки качества сетки [1]. Чтобы убедиться, что весь объем параллелепипеда заполнен тетраэдрами, нужно при построении сетки высчитать объем каждого тетраэдра, а затем сложить и сравнить с объемом параллелепипеда.

Сравнение шаблонов

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

Рисунок 3.1 — Триангуляция параллелепипеда со вставкой внутрь кубической сетки дополнительных узлов

Разбить граничные элементы можно вставкой произвольного диагонального ребра.

Разбить внутренние ромбовидные элементы можно уже несколькими различными способами, и именно выбранным вариантом различаются между собой 2 вида шаблонов:

1) Шаблон 1 — вставка диагонального ребра между узлами кубической сетки (рисунок 3. 2):

— допускает 2 варианта вставки ребер;

— неоднородность сетки (дополнительные узлы имеют всего по 8 соседей);

— полная элементная однородность — все элементы одинаковы;

— хорошее качество сетки (все тетраэдры имеют АХ порядка 0. 5);

2) Шаблон 2 — вставка ребра между дополнительными узлами (рисунок 3. 3):

— допускает единственный вариант вставки ребер (для внутренних элементов);

— подавляющая однородность сетки (все внутренние узлы, за исключением дополнительных приграничных узлов, имеют по 14 соседей);

— приграничные элементы отличаются от внутренних;

— очень высокое качество сетки (приграничные тетраэдры имеют АХ порядка 0. 5, внутренние -порядка 0. 9).

Рисунок 3.2 — Триангуляция параллелепипеда со вставкой внутрь кубической сетки дополнительных узлов; внутренние ребра соединяют вершины кубов

Рисунок 3.3 — Триангуляция параллелепипеда со вставкой внутрь кубической сетки дополнительных узлов; внутренние ребра соединяют дополнительные узлы

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

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

На рисунке 3.4 видно, что каждый куб разбивается на 5 тетраэдров. Данная сетка обладает следующими характеристиками:

— сетка неоднородна, узлы имеют «сильно» разное число соседей («половина» — 6, а «половина» — 18);

— хорошее качество сетки (средняя АХ тетраэдров — 0. 7);

— большая сложность построения и согласования (из-за необходимости чередовать направления диагональных ребер).

Рисунок 3.4 — Триангуляция параллелепипеда с разбиением элементов кубической сетки на 5 тетраэдров (1)

Рисунок 3.5 — Триангуляция параллелепипеда с разбиением элементов кубической сетки на 5 тетраэдров (2)

При разбиении кубов на 6 тетраэдров (рисунок 3. 6):

— однородность сетки: все внутренние узлы имеют одинаковое число соседей (по 14);

— низкое качество сетки (средняя АХ получающихся тетраэдров — 0. 3);

— простота построения и согласования сетки на границе.

Рисунок 3.6 — Триангуляция параллелепипеда с разбиением элементов кубической сетки на 6 тетраэдров (1)

Рисунок 3.7 — Триангуляция параллелепипеда с разбиением элементов кубической сетки на 6 тетраэдров (2)

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

Рисунок 3.8 — Триангуляция параллелепипеда с разбиением элементов кубической сетки на 5 тетраэдров со сложной областью

Также было проведено сравнение шаблонов по другим критериям оценки качества элементов триангуляционной сетки (таблица 3. 1).

Таблица 3.1 — Оценка качества элементов сетки

Критерий

На 5 тетраэдров

На 6 тетраэдров

Доп. узел. Ребра между узлами кубов

Доп. узел. Ребра между доп. узлами

Оптимальное значение

1

2

3

4

5

6

Отношение длин наибольшего и наименьшего ребер

1. 44

1. 77

1. 66

Вн. — 1. 15

Гр. — 1. 66

1. 0

Отношение 4-й степени объема тетраэдра к кубу суммы квадратов площадей граней

3,02*10-5

2,12*10-4

2. 04*10-4

Вн. — 3. 89*10-4

Гр. — 2. 04*10-4

4. 572 474*10-4

Отношение куба среднего арифметического длин ребер к объему тетраэдра

1. 44

1. 77

1. 66

Вн. — 1. 15

Гран. — 1. 66

8. 4 852 816…

Отношение куба среднего геометрического длин ребер к объему тетраэдра

10. 36

11. 36

11. 58

Вн. — 9. 65

Гр. — 11. 58

8. 4 852 816…

Исходя из всех рассмотренных шаблонов, наиболее оптимальным является шаблон с дополнительными узлами, в котором ребра вставлены между дополнительными узлами.

Заключение

По результатам выполненной работы можно сделать следующие выводы:

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

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

— выбрана структура данных «узлы с соседями», так как занимает меньше памяти, а явное представление тетраэдров упрощает построение триангуляции Делоне;

— выбран прямой метод триангуляции на основе шаблонов, так как сетки на его основе обладают высоким качеством (апроксимационная характеристика доходит до 0. 9), они структурированы, что экономит машинные ресурсы и время;

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

— были проанализированы все четыре шаблона и выбран шаблон со вставкой дополнительных узлов, где ребра соединяют дополнительные узлы, так как он обладает наилучшим качеством элементов, среди всех шаблонов (приграничные тетраэдры имеют апроксимационную характеристику порядка 0. 5, внутренние — порядка 0. 9),

Также данный метод может быть использован для построения сеток имеющих сложные области (рисунок 3. 8).

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

1. Галанин М. П., Щеглов И. А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: прямые методы. Препринт ИПМ им. М. В. Келдыша РАН, 2006, в печати;

2. А. В. Скворцов Триангуляция Делоне и её применение. — Томск: Издательство Томского университета, 2002. — 128 с.

3. Галанин М. П., Щеглов И. А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: итерационные методы. Препринт ИПМ им. М. В. Келдыша РАН, 2006, в печати;

4. S.J. Owen. A Survey of Unstructured Mesh Generation Technology // Proceedings of 7th International Meshing Roundtable, p.p. 239−269, Dearborn, MI, 1998;

5. 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;

6. Шайдуров В. В. Многосеточные методы конечных элементов. — М., Наука, 1989. — 288с;

7. Скворцов А. В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование, 2002, № 3, c. 14−39;

8. 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. 5.

9. 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;

10. B. Joe. Construction Of Three-Dimensional Delaunay Triangulations Using Local Transformations // Computer Aided Geometric Design, Vol. 8, p.p. 123−142, 1991;

11. 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;

12. 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;

13. Уроки Delphi начинающим с нуля [Электронный ресурс]: статья — URL: http: //www. delphi-manual. ru/ (дата обращения: 09. 06. 2012).

ПоказатьСвернуть
Заполнить форму текущей работой