П., Щеглов И. А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: прямые методы



Скачать 287.52 Kb.
страница1/3
Дата28.10.2016
Размер287.52 Kb.
  1   2   3


РОССИЙСКАЯ АКАДЕМИЯ НАУК

Ордена Ленина Институт прикладной математики

им. М.В. Келдыша

Галанин М.П., Щеглов И.А.



Разработка и реализация алгоритмов

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

сложных пространственных областей:

прямые методы

Москва – 2006




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

M.P. Galanin, I.A. Sheglov



Development And Implementation of Algorithms For Constrained Volume Triangulations:

Direct Methods
Abstract

A short overview and a classification of existing simplicial discretization algorithms are given. A mesh quality evaluation method is proposed. Direct discretization methods are discussed with the emphasis on optimal patterns for sphere-like, cylinder-like and box-like volumes. Also a method for mesh mapping (based on isoparametric mapping) is described.


Содержание


1. Введение

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

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

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

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

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

Более того, любой треугольник можно разбить на треугольники, подобные ему (на 4, 9, 16 и т.д.). Тетраэдр в общем случае нельзя разбить на подобные тетраэдры. Это является основным препятствием на пути использования методов дробления, эффективно применяющихся в двумерном случае.



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

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

Целью данной работы является рассмотрение и классификация существующих методов построения тетраэдрических сеток в трехмерных областях. Ввиду значительного объема информации ниже рассматриваются только так называемые "прямые методы". Методы других классов, включая оригинальные, описаны в работе [45].

Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (проект № 06-01-00421).



1.1 Классификация методов

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

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

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

Прямых методов разработано немного (из-за ограниченной возможности их использования); все они условно могут быть разделены на две тесно связанные группы: методы на основе шаблонов и методы отображения (изопараметрические). Методы на основе шаблонов подразумевают разбиение областей заданного вида (параллелепипед, шар, цилиндр, и т.д.). Соответственно, для каждого вида области используется свой шаблон, то есть принцип размещения узлов и установки связей между ними.

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

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

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

Методы граничной коррекции являются самыми быстрыми из итерационных методов, но, к сожалению, имеют ряд неискоренимых недостатков. Построение сеток в этих методах осуществляется в два этапа. На первом этапе производится триангуляция некой простой "супер-области", полностью включающей в себя заданную область. Как правило, эта супер-область представляет собой параллелепипед (из-за простоты триангуляции), триангуляция которого осуществляется на основе одного из многочисленных шаблонов. На втором этапе все узлы полученной сетки, лежащие вблизи границы заданной области, проецируются на поверхность границы; а узлы, лежащие вне заданной области - удаляются. Чтобы компенсировать неизбежные геометрические искажения элементов сетки вблизи границ, часто дополнительно проводят еще один этап - этап оптимизации сетки, что в итоге позволяет получить достаточно хорошие результаты.

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

Сущность методов исчерпывания заключается в последовательном "вырезании" из заданной области фрагментов тетраэдрической формы до тех пор, пока вся область не окажется "исчерпана". В англоязычной литературе этот метод получил название "advancing front", что также хорошо отражает идею метода. Исходными данными на каждой итерации является "фронт", то есть триангуляция границы еще не "исчерпанной" части области. Каждый треугольник этой триангуляции является основанием изымаемого из области тетраэдра; причем на каждой итерации может изыматься либо один тетраэдр, либо сразу целый слой тетраэдров. После изъятия тетраэдра (-ов) "фронт" обновляется, после чего происходит переход к следующей итерации.

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

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

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





Диаграмма 1. Классификация методов дискретизации


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

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



(1)

где - радиус вписанного в шара, а - диаметр [1]. Поскольку прямое нахождение (1) хотя и возможно, но весьма трудоемко, на практике используются различные альтернативные оценки. Таких оценок предложено большое количество, некоторые наиболее популярные приведены в таблице 1. Однако оптимальной с точки зрения точности, полноты оценки качества сетки и удобства нахождения является следующая оценка [1, 31]:



, (2)

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

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

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




Критерий

Формула

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

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

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





3.0

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





4.898979...

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





0.612375...

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





1.0

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





4.572474e-4

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





8.4852816...

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





8.4852816...

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





(1.2309594...)



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






Таблица 1. Критерии оценки качества элементов сетки [25]



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

Одной из распространенных задач дискретизации является триангуляция сложных областей, т.е. областей, на которые наложены различные дополнительные ограничения, обусловленные, например, изменением свойств материала либо некими конструкционными особенностями моделируемого объекта. Как правило, ограничения, накладываемые на область, а точнее говоря, на сетку в этой области, носят характер запрета на пересечение ребрами сетки некоторых заданных поверхностей. То есть, например, если речь идет о композитном материале, ребра сетки не должны пересекать границу между включением и матрицей. Фактически это равнозначно тому, что каждый конечный элемент сетки должен "состоять" строго из одного материала. Это ограничение вызвано вполне понятными причинами, и его необходимо учитывать при построении сетки.

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

Таким образом, условно можно выделить два типа сложных областей:

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

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

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






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

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

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

1) триангуляция границ смежных подобластей;

2) дискретизация подобластей исходя из заданной триангуляции границ.

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

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

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



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

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

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

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

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

Рассмотрим, например, так называемую "кубическую сетку", то есть сетку, полученную разбиением исходного параллелепипеда на равные "кубы" (слово "куб" здесь употребляется исключительно в топологическом смысле, поскольку ребра у такого "куба" необязательно строго равны). Если размеры куба - 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).

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

Рис. 3. Кубическая сетка

  1   2   3


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница