Дискретизация сложных двумерных и трехмерных областей для решения задач математического моделирования тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Щеглов, Илья Александрович

• Щеглов, Илья Александрович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Щеглов, Илья Александрович

Введение.

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

0.2. Примеры задач в сложных двумерных и трехмерных областях.

0.2.1. Задача об МГД-насосе.

0.2.2. Задача линейной упругости в композиционном материале.

0.2.3. Задача о движении пластинчатого лайнера в магнитном компрессоре.

0.3. Требования к сеткам в сложных областях.

0.4. Краткое описание известных алгоритмов триангуляции.

0.5. Возможные подходы к дискретизации сложных областей.

0.6. Обзор существующих программ для дискретизации.

0.6.1. Geompack.

0.6.2. TetGen.

0.6.3. Méfisto-maillages.

0.6.4. NetGen.

0.6.5. T3D.

0.6.6. Gmsh.

0.7. Авторский программный комплекс.

0.8. Содержание работы.

Глава 1. Методы дискретизации.

1.1. Методы оценки качества сетки.

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

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

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

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

1.4.1. Методы граничной коррекции.

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

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

1.5. Некоторые методы улучшения сеток.

1.5.1. Оптимизация расположения узлов, или сглаживание сетки.

1.5.2. Оптимизация связей.

1.5.3. Сгущение сетки.

Глава 2. Реализация методов и разработка программного комплекса.

2.1. Подходы к решению задачи дискретизации сложной области.

2.2. Обзор проблем трехмерной дискретизации.

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

2.3.1. Проблема задания области.

2.3.2. Проблема хранения сеток в оперативной памяти и на жестком диске.

2.3.3. Проблема контроля корректности сетки.

2.3.4. Проблема визуализации и оценка качества.

2.4. Общий алгоритм решения задачи.

2.5. Двумерная триангуляция.

2.5.1. Задание области.

2.5.2. Алгоритм триангуляции "от угла" без сгущения.

2.5.3. Проверка корректности элемента сетки.

2.5.4. Алгоритм триангуляции "от угла" со сгущением.

2.5.5. Оптимизация двумерной сетки.

2.6. Трехмерная дискретизация.

2.6.1. Задание области.

2.6.2. Алгоритм дискретизации "от ребра".

2.6.3. Проверка корректности тетраэдра.

2.6.4. Оптимизация трехмерной сетки.

Глава 3. Описание программного комплекса и примеры его использования.

3.1. Описание программного комплекса Gridder.

3.1.1. Структура программного комплекса.

3.1.2. Модуль Gridder2D.

3.1.3. Модуль Gridder2D-VI (Visual Interface).

3.1.4. Модуль Gridder3D.

3.1.5. Модуль Gridder3D-VI.

3.1.6. Модуль оценки качества сеток GridQuality.

3.1.7. Модули импорта геометрии.

3.1.8. Экспорт данных.

3.2. Примеры сеток и решенных на них задач.

3.2.1. Модельная задача для уравнения Лапласа.

3.2.2. Задача об МГД-насосе.

3.2.3. Задача линейной упругости в ячейке композита.

3.2.4. Задача о движении пластинчатого лайнера в магнитном компрессоре.

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

Благодаря значительному прогрессу в области вычислительной техники численные методы стали основным инструментом математического моделирования. При этом по ряду причин наибольшее распространение получили сеточные методы, в частности, метод конечных элементов (МКЭ) и его многочисленные варианты [15, 20, 23, 26]. Все эти методы предполагают построение в области, в которой решается задача (далее — области решения), расчетной сетки, т.е. ее дискретизацию на мелкие фрагменты (элементы) определенного вида - треугольники, тетраэдры, призмы, и др. При этом к размерам и форме элементов также предъявляются определенные требования, так как они существенно влияют на ошибку аппроксимации и сходимость методов.

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

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

Именно проблеме автоматического построения расчетных сеток в сложных областях и посвящена данная работа.

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

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

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

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

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

0.2. Примеры задач в сложных двумерных и трехмерных областях

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

0.2.1. Задача об МГД-насосе

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

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

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

Вал

Ярмо индуктора

Пазы с обмоткой

Рис. 0-1. Схема поперечного сечения МГД-насоса

0.2.2. Задача линейной упругости в композиционном материале

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

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

Рис. 0-2. Некоторые варианты ячеек композитов: а) гранулы б) волокна в) слои

0.2.3. Задача о движении пластинчатого лайнера в магнитном компрессоре

Для генерации сверхмощных электрических импульсов может быть использован усилительный каскад мощности, принцип работы которого основан на сжатии магнитного потока лайнером, ускоренным электродинамическими силами до скорости порядка 1 км/с. Данное устройство состоит из замкнутой металлической ленты, помещаемой внутри индуктора магнитного поля, и набора коммутируемых электрических цепей (см. рис. 0-3). В начальный момент времени конденсатор Св в цепи индуктора заряжен до некоторого начального напряжения. После замыкания цепи ключом Кв по индуктору (и лайнеру) начинает течь разрядный ток. Созданное им в зазоре ускорителя магнитное поле взаимодействует с протекающим по лайнеру током, ускоряя лайнер вдоль оси X. В некоторый момент времени (вероятно, отличный от момента начала ускорения) ключом КЛ замыкается цепь контура лайнера с (возможно) заряженным конденсатором Сд- Соответствующий ток протекает по лайнеру и создает внутри полости лайнера дополнительное магнитное поле. Ускорившись, лайнер сжимает это поле, которое окончательно и выводится из системы в виде импульса тока во внешней цепи лайнера.

Задача решается в пространственно двумерном приближении. Все величины считаются зависящими только от координат х и у, В уравнениях производные по г отсутствуют. Это означает формально бесконечную протяженность ускорительной системы в данном направлении. При этом в модели учитывается «эффективная» длина системы в г — направлении, в значительной степени определяющая процесс перекачки энергии из внешней электрической цепи в кинетическую энергию лайнера. Соответственно у скоростей ненулевыми являются только х и у компоненты. Аналогично отличные от нуля х и у компоненты имеет напряженность магнитного поля.

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

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

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

0.3. Требования к сеткам в сложных областях

Практика показывает, что качество сетки может оказывать существенное влияние на точность решения. Также сетка может влиять и на сходимость методов. Например, для двумерных симплициальных сеток известно, что наличие очень малых углов у элементов ведет к значительному увеличению ошибки аппроксимации методом конечных элементов и интегро-интерполяционными методами, а наличие очень больших (более 170 градусов) - к экспоненциальному ухудшению обусловленности матрицы системы, что, в свою очередь, влечет за собой дополнительные вычислительные затраты и вносит дополнительную погрешность в решение. Аналогичная ситуация имеет место и для трехмерного случая [30, 36, 57, 60, 70, 97].

Таким образом, одно из главных требований к любой расчетной сетке — высокое качество. Часто автоматически построенные сетки в силу ряда причин обладают низким качеством, и их требуется оптимизировать различными методами. В 99% случаев затраты на оптимизацию сетки окупаются последующим ускорением расчетов и уменьшением погрешности. В первой главе работы рассмотрены различные методики оценки качества сетки и описаны некоторые варианты улучшения сеток. Алгоритмы улучшения сеток, примененные в авторском программном комплексе, описаны во второй главе.

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

0.4. Краткое описание известных алгоритмов триангуляции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существуют и различные комбинированные алгоритмы [12, 16, 62, 64,

79].

0.5. Возможные подходы к дискретизации сложных областей

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

Метод коррекции

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

Метод перестройки

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

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

Согласование по границе

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

0.6. Обзор существующих программ для дискретизации

Как уже упоминалось выше, сетка оказывает весьма существенное влияние на точность решения проекционно-сеточными методами (а в некоторых случаях и на сходимость методов). Качество сетки с точки зрения точности решения определяется тремя обстоятельствами: размерами элементов, их формой и тем, насколько хорошо сетка аппроксимирует исходную область [27]. Таким образом, с учетом высказанных в разделе 0.3 соображений, можно сформулировать следующие требования к любой системе автоматической триангуляции (CAT).

1) Максимально точная аппроксимация границ области и ее внутренних ограничений: линии соединений поверхностей должны быть аппроксимированы цепочками ребер сетки, а сами поверхности -множеством плоских треугольных граней.

2) Форма элементов должна быть по возможности близка к форме правильного симплекса.

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

Немаловажной также является возможность проверки качества и корректности построенной сетки.

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

0.6.1. Geompack

Пакет Geompack разработан доктором Барри Джо, известным своими работами в области дискретизации методами на основе критерия Делоне. Первые версии пакета появились более 15 лет назад и имели- вид программной библиотеки на языке FORTRAN77 (старые версии пакета распространяются с открытым кодом). Теперь Geompack является мощной консольной программой для выполнения различных операций с сетками — построения, сгущения, оптимизации, перестройки и т.п. В основе алгоритма используется метод коррекции совместно с методом на основе критерия Делоне.

Пакет Geompack бесплатен для академического использования. В комплекте с пакетом поставляется подробная документация на английском языке и множество примеров. Автор осуществляет ограниченную поддержку пользователей по электронной почте. Визуальный интерфейс и возможности по визуализации отсутствуют. Импорт и экспорт данных осуществляется через текстовые и бинарные файлы специальных (нестандартных) форматов. Пакет может быть использован под операционными системами семейств Unix и Windows.

К недостаткам пакета следует отнести невозможность прямого контроля над размерами элементов.

Домашняя страница пакета в Интернете: http://members.shaw.ca/bjoe/.

0.6.2. TetGen

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

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

Пакет может быть использован под любыми операционными системами, для которых существует компилятор С++.

Домашняя страница пакета в Интернете: http://tetgen.berlios.de/

0.6.3. Mefisto-maillages

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

Программный комплекс Mefisto предназначен для работы под управлением операционных систем семейства Unix. Распространяется вместе с исходными кодами (написан на языках FORTRAN77 и С) и демонстрационными примерами. Документация на французском языке. Поддержка авторами не оказывается.

Для триангуляции поверхности и внутренности области используется комбинированный метод на основе критерия Делоне и алгоритма Quad-tree (см. подраздел 1.4.1). Управление размерами элементов осуществляется с помощью специальных функций (т.е. сгущение сетки можно получить в процессе построения). Область для триангуляции можно задавать с помощью текстовых файлов специального формата или визуального интерфейса. Экспорт сетки производится в текстовые файлы специального формата.

Домашняя страница программного комплекса в Интернете: http://www.ann.jussieu.fr/~perronnet/mefistoa.gene.html

0.6.4. NetGen

NetGen - один из самых популярных бесплатных пакетов для дискретизации сложных областей. Распространяется с открытым кодом, сопровождается документацией на английском языке, множеством примеров, а также имеет собственный Интернет-форум. Может быть использован под любыми операционными системами, для которых существует компилятор С++. Обладает визуальным интерфейсом, но может быть запущен и как консольная программа. Позволяет сгущать и оптимизировать сетки.

В пакете используется алгоритм на основе комбинированного метода исчерпывания и метода на основе критерия Делоне. Импорт и экспорт данных может быть осуществлен через самые разнообразные форматы, в том числе и через стандартные. В частности, NetGen "знает" многие форматы CAD-систем.

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

Разработка программы была завершена в 2004 г. Продукт автором более не поддерживается.

Автор программы - Joachim Schöberl. Страница в Интернете: http ://www.hpfem.j ku. at/netgen/.

0.6.5. T3D

T3D - программа для построения качественных сеток методом исчерпывания. Сложные области дискретизируются методом согласования по границе. Сама область задается как совокупность поверхностей границы и ограничений. Данные импортируются и экспортируются через текстовые файлы специального формата. Кроме того, пакет умеет работать напрямую с системами CAD.

Существуют версии пакета для ОС Windows и Linux. Программа обладает консольным интерфейсом. Для ОС семейства Unix предусмотрена возможность визуализации сеток с помощью сторонней программы (Elixir). Также возможна запись сеток в графических форматах VRML 2.0 и VTK.

Пакет бесплатен для академического использования, но автором поддерживается весьма ограниченно. Автор пакета - Daniel Rypl. Домашняя страница проекта: http://ksm.fsv.cvut.cz/Mlr/t3d.h1ml

0.6.6. Gmsh

Gmsh — проект, призванный объединить наработки многих авторов в один мощный программный проект. В частности, в Gmsh входят алгоритмы пакетов NetGen и TetGen, описанные выше. Gmsh обладает визуальным интерфейсом (также может быть запущен как консольное приложение или подключен как программная библиотека), позволяет строить, оптимизировать и сгущать сетки. Данные об области могут быть импортированы через файлы различных форматов (включая стандартные) или напрямую из CAD-систем. Область также можно задать вручную через удобный визуальный интерфейс. Экспортировать данные также можно через ряд форматов.

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

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

Авторы - Christophe Geuzaine, Jean-François Remacle. Домашняя страница проекта: http://www.geuz.org/gmsh/.

0.7. Авторский программный комплекс

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

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

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

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

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

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

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

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

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

На рис. 0.4-0.8 приведены примеры сеток, построенных в комплексе ОпсМег.

Рис. 0-4. Пример сетки, построенной с помощью ПО ОпсМег2Б - несвязная область с отверстием в одном из фрагментов

Рис. 0-5. Пример сетки, построенной с помощью ПО ОпсЫейБ - область, состоящая из нескольких подобластей

Рис. 0-6. Примеры сеток со сгущением

Рис. 0-8. Триангуляция поверхности шестеренки в программе Оп(1с1егЗВ

0.8. Содержание работы

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

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

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

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

Четвертый раздел посвящен итерационным методам. В первом его подразделе рассмотрены методы граничной коррекции. Описана проблема построения первичной сетки на примере алгоритма (ЗиасГГгее. Приведен разработанный автором алгоритм коррекции первичной сетки для трехмерного случая. Указаны достоинства (высокая, в сравнении с другими итерационными методами, скорость работы; возможность применения для дискретизации сложных областей) и недостатки (низкая надежность, ограниченная возможность применения) данного класса методов. Во втором подразделе обсуждаются методы на основе критерия Делоне. Указана принципиальная отличительная черта методов - сначала в области размещаются узлы, а затем между узлами расставляются связи с помощью критерия Делоне либо иного схожего критерия. Описана методика преобразования произвольной двумерной сетки к триангуляции Делоне. Приведен пример одного из вариантов алгоритма построения триангуляции Делоне на заданном наборе точек. Описана методика построения триангуляции Делоне с ограничениями в двумерном и трехмерном случае. Обозначены проблемы, затрудняющие применение методов на основе критерия Делоне в трехмерном случае. В третьем подразделе описаны методы исчерпывания, их общая идея и некоторые варианты реализации. Указана их ключевая особенность - в качестве входных данных требуется триангуляция границы, что может быть как достоинством (при построении согласованной триангуляции), так и недостатком (в остальных случаях).

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

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

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

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

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

Во втором разделе приведены примеры реальных и модельных задач, решенных с помощью комплекса "Опёёег": модельная задача для уравнения Лапласа, модельная задача линейной упругости в композиционном материале, задача об МГД-насосе и задача о движении пластинчатого лайнера в магнитном компрессоре.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Щеглов, Илья Александрович

Заключение

В рамках данной работы получены следующие основные результаты:

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

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

3. С помощью разработанного программного комплекса решен ряд задач математического моделирования: модельная задача для уравнения Лапласа, задача об МГД-насосе, модельная задача теории линейной упругости в ячейке композиционного материала, задача о движении пластинчатого лайнера в магнитном компрессоре.

Список литературы диссертационного исследования кандидат физико-математических наук Щеглов, Илья Александрович, 2010 год

1. Применение одного класса квазиконформных отображений для построения разностных сеток в областях с криволинейными границами / П.П. Белинский и др.. // Журнал вычислительной математики и математической физики. 1975. Т. 15, №6. С. 1493-1511.

2. Галанин М.П., Потоцкий А.П., Родин A.C. Математическое моделирование электромагнитного ускорения лайнера в различных двумерных приближениях. М., 2007. 32 с. (Препринт ИПМ им. М.В. Келдыша РАН, № 4).

3. Галанин М.П., Потоцкий А.П., Родин A.C. Математическое моделирование движения лайнера в продольном сечении магнитного компрессора. М., 2009. 32 с. (Препринт ИПМ им. М.В. Келдыша РАН, №57).

4. Движение лайнера в магнитном компрессоре: сравнение моделей упругого, жидкого и пластического лайнера / М.П. Галанин и др. М., 2009. 32 с. (Препринт ИПМ им. М.В. Келдыша РАН, №58).

5. Галанин М.П., Родин A.C. Математическое моделирование работы МГД-насоса. М., 2010. 32 с. (Препринт ИПМ им. М.В. Келдыша РАН).

6. Применение метода конечных суперэлементов для расчета характеристик дисперсно-армированных композиционных материалов / М.П. Галанин и др. // Вестник МГТУ им. Н.Э. Баумана. Естественные науки. 2007. №3. С. 54-68.

7. Двумерная и трехмерная триангуляция / М.П. Галанин, И.А. Щеглов // Энциклопедия низкотемпературной плазмы. М.: Янус-К, 2008. Т. VII, Ч. 1. С. 319-342.

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

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

10. Ю.Данаев Р.Т., Лисейкин В.Д., Яненко H.H. О вариационном методе построения сеток. // Численные методы механики сплошной среды. 1977. Т. 8, №7. С. 100-104.

11. П.Дарьин H.A., Мажукин В.И. Математическое моделирование нестационарных двумерных краевых задач на сетках с динамической адаптацией//Математическое моделирование. 1989. Т. 1, №3. С. 29—43.

12. Дворников М.В., Тишкин В.Ф., Филатов А.Ю. Триангуляция произвольной многосвязной области со сложной границей. М., 1995. 32 с. (Препринт ИММ РАН, №7).

13. Делоне Б.Н. О пустоте сферы // Известия АН СССР. Отделение математических и естественных наук. 1934. №4. С. 793-800.

14. Димитриенко Ю.И. Нелинейная механика сплошной среды. М.: Физматлит, 2009. 624 с.15.3инкевич О., Морган К. Конечные элементы и аппроксимация. М.: Мир, 1986.318 с.

15. Иванов Е.Г. Автоматическая генерация трехмерных неструктурированных сеток для вычислительной механики // Вычислительные технологии. 2006. Т. 11, №1. С. 3-17.

16. Неструктурированные адаптивные сетки для задач математической физики (обзор) / J1.B. Круглякова и др. // Математическое моделирование. 1998. Т. 10, №3. С. 93-116.

17. Лисейкин В.Д. Технология конструирования трехмерных сеток для задач аэрогазодинамики // Вопросы атомной науки и техники. Математическое моделирование физических процессов. 1991. Т. 3. С. 31-45.

18. Лисейкин В.Д. Обзор методов построения структурных адаптивных сеток // Журнал вычислительной математики и математической физики. 1996. Т. 36, №1. С. 3-41.

19. Марчук Г.И., Агошков В.И. Введение в проекционно-сеточные методы. М.: Наука, 1981.416 с.

20. Похилко В.И., Тишкин В.Ф. Метод построения адаптивных неструктурированных сеток. М., 1994. 32 с. (Препринт ИММ РАН, №18).

21. Самарский А.А., Попов Ю.П. Разностные методы решения задач газовой динамики. М.: Наука, 1992. 424 с.

22. Сегерлинд JI. Применение метода конечных элементов. М.: Мир, 1979. 392 с.

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

24. Скворцов А.В. Алгоритмы построения триангуляции с ограничениями // Вычислительные методы и программирование. 2002. №3. С. 82-92.

25. Федоренко Р.П. Введение в вычислительную физику: учеб. пособие для вузов. М.: Изд-во Моск. физ.-техн. ин-та, 1994. 528 с.

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

27. Щеглов И А. Программа для триангуляции сложных двумерных областей Gridder2D. М., 2008. 32 с. (Препринт ИПМ им. М.В. Келдыша РАН, №60).

28. Amenta N., Bern М., Eppstein D. Optimal point placement for mesh smoothing // 7th Annual ACM-Siam Symposium on Discrete Algorithms. New Orleans, 1997. P. 528-537.

29. Babushka I., Rheinboldt W.C. A-posteriori error estimates for finite element method // International Journal for Numerical Methods in Engineering. 1978. V. 12. P. 1597-1615.

30. Baker T.J. Automatic mesh generation for complex three-dimensional regions using a constrained Delaunay triangulation // Engineering With Computers. 1989. №5. P. 161-175.

31. Baker T.J. Mesh movement and metamorphosis // 10th International Meshing Roundtable: proceedings. Sandia National Laboratories, 2001. P. 387-396.

32. Baker T.J. Generation of tetrahedral meshes around complete aircraft // Numerical Grid Generation in Computational Fluid Mechanics: proceedings. Pineridge Press, 1988. P. 675-684.

33. Bank R.E., Kent Smith R. Mesh smoothing using a posteriori error estimates // SLAM Journal on Numerical Analysis. 1997. V. 34. P. 979-997.

34. Bern M., Eppstein D. Mesh generation and optimal triangulation // Computing in Euclidean geometry: lecture notes series on computing; ed. Ding-Zhu Du and Frank Kwang-Ming Hwang. World Scientific Publishing Co., 1995. P. 23-90.

35. Berzins M., Mesh quality: a function of geometry, error estimates or both // 7th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1998. P. 229-238.

36. Compact representations of simplicial meshes in two and three dimensions / D.K. Blandford, et al. // 12th International Meshing Roundtable: proceedings. Sandia National Laboratories, 2003. P. 135-146.

37. Boender E. Reliable Delaunay-based mesh generation and mesh improvement // Communications in Numerical Methods in Engineering. 1994. V. 10. P. 773-783.

38. Bogomolov K. Robust construction of 3-D conforming Delaunay meshes using arbitrary-precision srithmetic // 14th International Meshing Roundtable: proceedings. Springer-Verlag, 2005. P. 183-202.

39. Borouchaki H., Lo S.H. Fast Delaunay triangulation in three dimensions // Computer Methods In Applied Mechanics And Engineering. 1995. V. 128. P. 153-167.

40. Borouchaki H., George P.L., Lo S.H. Optimal Delaunay point insertion // International Journal for Numerical Methods in Engineering. 1996. V. 39. P. 3407-3437.

41. Branets L.3 Carey G.F. Cell quality metric and variational grid smoothing algorithm // 12th International Meshing Roundtable: proceedings. Sandia National Laboratories, 2003. P. 371-390.

42. Buratynski E.K. A three-dimensional unstructured mesh generator for arbitrary internal boundaries // Numerical Grid Generation in Computational Fluid Mechanics: proceedings. Pineridge Press, 1988. P. 621-631.

43. Canann S.A., Muthukrishnan S.N., Phillips R.K. Topological refinement procedures for triangular finite element meshes // Engineering with Computers. 1996. V. 12. P. 243-255.

44. Cavalcanti P.R., Mello U.T. Three-dimensional constrained Delaunay triangulation: a minimalist approach // 8th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1999. P. 119-129.

45. Chan C.T., Anastasiou K. An automatic tetrahedral mesh generation scheme by the advancing front method // Communications in Numerical Methods in Engineering. 1997. V. 13. P. 33-46.

46. Chen L. Mesh smoothing schemes based on optimal Delaunay triangulations // 13th International Meshing Roundtable: proceedings. Sandia National Laboratories, 2004. P. 109-120.

47. Cyrus M., Beck J. Generalized two- and three-dimensional clipping // Computers and Graphics. 1978. V. 3(1). P. 23-28.

48. De Cougny H.L., Shephard M.S. Parallel refinement and coarsening of tetrahedral meshes // International Journal for Numerical Methods in Engineering. 1999. №46. P. 1101-1125.

49. De Cougny H.L., Shephard M.S. Surface meshing using vertex insertion // 5th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1996. P. 243-256.

50. Dey K.T., Sugihara K., Bajaj C.L. Delaunay triangulations in three dimensions with finite precision arithmetic // Computer Aided Geometric Design. 1992. № 9. P. 457-470.1.f

51. Djidjev H.N. Force-directed methods for smoothing unstructured triangular and tetrahedral meshes // 9th International Meshing Roundtable: proceedings. Sandia National Laboratories, 2000. P. 395-406.

52. How to subdivide pyramids, prisms, and hexahedra into tetrahedra / J. Dompierre, et al. // 8th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1999. P. 195-204.

53. Durbeck L. Evaporation: a technique for visualizing mesh quality // 8th International Meshing Roundtable. Sandia National Laboratories, 1999. P.259-265;

54. Facello M. Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions // Computer Aided Geometric Design. 1995: V. 12. P. 349-370.

55. Field D.A. Laplacian smoothing and Delaunay triangulations // Communications in Applied Numerical Methods. 1988. V. 4. P. 709-712.

56. Fleishmann P., Kosik R., Selberherr S. Simple mesh examples to illustrate specific finite element mesh requirements // 8th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1999. P. 241-246.

57. Freitag L.A., Ollivier-Gooch C. A comparison of tetrahedral mesh improvement techniques // 5th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1996. P. 87-106.

58. Freitag L.A., Ollivier-Gooch C. Tetrahedral mesh improvement using swapping and smoothing // International Journal for Numerical Methods in Engineering. 1995. V. 40. P. 3979—4002.

59. Freitag L.A., Ollivier-Gooch C. The effect of mesh quality on solution efficiency // 6th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1997. P. 249.

60. Frey W.H., Field D.H. Mesh relaxation: a new technique for improving triangulations // International Journal For Numerical Methods in Engineering. 1991. V. 31. P. 1121-1133.

61. Frey P.J., Borouchaki H., George P.L. Delaunay tetrahedralization using an advancing front approach // 5th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1996. P. 31—46.

62. George P.L. Tet meshing: construction, optimization and adaptation // 8th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1999. P.133-141.

63. George P.L., Seveno E. The advancing-front mesh generation method revisited // International Journal for Numerical Methods in Engineering. 1994. V. 37. P. 3605-3619.

64. Golias N.A., Tsiboukis T.D: An approach to refining three-dimensional tetrahedral meshes based on Delaunay transformations // International Journal for Numerical Methods in Engineering. 1994. №37. P. 793-812.

65. Hazlewood C. Approximating constrained tetrahedralizations // Computer Aided Geometric Design. 1993. V. 10. P. 67-87.

66. Joe B. Delaunay triangular meshes in convex polygons // SIAM Journal on Scientific Computing. 1986. V. 7. P. 514-539.

67. Joe B. Construction of three-dimensional Delaunay triangulations using local transformations // Computer Aided Geometric Design. 1991. V. 8. P. 123-142.

68. Joe В. Construction of three-dimensional improved-quality triangulations using local transformations I I SIAM Journal on Scientific Computing. 1995. V. 16. P. 1292-1307.

69. Krizek M. On the maximum angle condition for linear tetrahedral elements // SIAM Journal of Numerical Analysis. 1992. V. 29, №2. P. 513-520.

70. Lewis R.W., Yao Zheng, Gethin D.T. Three-dimensional unstructured mesh generation: part 3. Volume meshes // Computer Methods In Applied Mechanics And Engineering. 1996. V. 134. P. 285-310.

71. Li X.-Y. Functional Delaunay refinement // 7th International Conference on Numerical Grid Generation in Computational Field Simulations: abstracts. The International Society of Grid Generation, 2000. P. 253-262.

72. Liu A., Joe B. On the shape of tetrahedra from bisection // Mathematics of Computation. 1994. V. 63, №207. P. 141-154.

73. Lo S.H. Generation of high quality gradation finite element mesh // Engineering Fracture Mechanics. 1992. V. 2, №41. P. 191-202.

74. Lo S.H. Volume discretization into tetrahedra I. Verification and orientation of boundary surfaces // Computers and Structures. 1991. V. 39, №5. P. 493-500.

75. Lo S.H. Volume discretization into tetrahedra II. 3D triangulation by advancing front approach // Computers and Structures. 1991. V. 39, №5. P. 501-511.

76. L6hner R, Parikh P. Generation of three-dimensional unstructured grids by the advancing front method // International Journal for Numerical Methods in Fluids. 1987. V. 8, №10. P. 1135-1149.

77. Quality improvement of surface triangulations / R. Montenegro, et al. // 14th International Meshing Roundtable: proceedings. Sandia National Laboratories, 2005. P. 469^484.

78. Owen S.J. A survey of unstructured mesh generation technology // 7th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1998. P. 239-269.

79. Parthasarathy V.N., Graichen C.M., Hathaway A.F. A comparison of tetrahedron quality measures // Finite Elements in Analysis and Design. 1993. №15. P. 255-261.

80. Plaza A., Carey G.F. About local refinement of tetrahedral grids based on bisection // 5th International Meshing Roundtable. Sandia National Laboratories, 1996. P. 123-136.

81. Pirzadeh S. Unstructured viscous grid generation by advancing-layers method // AIAA paper 93-3453-CP. AIAA, 1993. P. 420^134.

82. Prasad N.S., Rajagopal C.J. Effect of node placement algorithm on adaptive mesh generation // Computers and Structures. 1997. V. 62, №5. P. 909-917.

83. Rajan V.T. Optimality of Delaunay triangulation in Rd II 7th ACM Symposium Computational Geometry: proceedings. ACM, 1991. P. 357-363.

84. Rassineux A. Generation and optimization of tetrahedral meshes by advancing front technique // International Journal for Numerical Methods in Engineering. 1998. V. 41. P. 651-674.

85. Rebay S. Efficient unstructured mesh generation by means of Delaunay triangulation and Bowyer-Watson algorithm // Journal Of Computational Physics. 1993. V. 106. P. 125-138.

86. Rivara M.-C. Selective refinement/derefinement algorithms for sequences of i; nested triangulations // International Journal for Numerical Methods in

87. Engineering. 1998. №28. P. 2889-2906.

88. Rivara M.-C., Levin C. A 3D refinement algorithm suitable for adaptive and multigrid techniques // Communications in Applied Numerical Methods. 1998. №8. P. 281-290.

89. Ruppert J. A Delaunay refinement algorithm for quality two-dimensional mesh generation//Journal of Algorithms. 1995. №18. P. 548-585.

90. Shephard M.S., Georges M.K. Three-dimensional mesh generation by finite octree technique // International Journal for Numerical Methods in Engineering. 1991. V. 32. P. 709-749.

91. Finite octree mesh generation for three-dimensional flow analysis / M.S. Shephard, et al. // Numerical grid generation in computational Fluid mechanics: proceedings. Pineridge Press, 1988. P. 709-718.

92. Shimada K., Gossard D.C. Bubble mesh: automated triangular meshing of non-manifold geometry by sphere packing // 3rd Symposium on Solid Modeling and Applications: proceedings. ACM, 1995. P. 409-419.

93. Shimada K., Yamada A., Itoh T. Anisotropic triangular meshing of parametric surfaces via close packing of ellipsoidal bubbles // 6th International Meshing Roundtable: proceedings. Sandia National Laboratories, 1997. P. 375-390.

94. Van der Burg J.W. Tetrahedral grid optimisation: towards a structured tetrahedral grid // Numerical Grid Generation in Computational Field Simulations. The International Society of Grid Generation, 2000. P. 347-356.

95. Watson D.F. Computing the Delaunay tessellation with application to Voronoi polytopes // The Computer Journal. 1981. V. 24(2). P. 167-172.

96. Yee K.S. Numerical solution of initial boundary value problems involving Maxwell's equations in isotropic media // IEEE Transactions on Antennas and Propagation. 1966. V. 17. P." 585-589.

97. Yerry M.A., Shephard M.S. Three-dimensional mesh generation by modified octree technique // International Journal for Numerical Methods in Engineering. 1984. V. 20. P. 1965-1990.

98. An automatic adaptive meshing technique for Delaunay triangulations / X. Xu, et al. // Computer methods in applied mechanics and engineering. 1998. V. 161. P. 297-303.