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

ЩЕГЛОВ Илья Александрович

ДИСКРЕТИЗАЦИЯ СЛОЖНЫХ ДВУМЕРНЫХ И ТРЕХМЕРНЫХ ОБЛАСТЕЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

Специальность 05.13.18 - "Математическое моделирование, численные методы и комплексы программ"

АВТОРЕФЕРАТ диссертация на соискание ученой степени кандидата физико-математических наук

- 7

°КТ 2010

Москва - 2010

004609879

Работа выполнена на кафедре "Прикладная математика" Московского государственного технического университета имени Н.Э. Баумана

Научный руководитель: доктор физико-математических наук, профессо

Галанин Михаил Павлович

Официальные оппоненты: доктор физико-математических наук, профессо

Мажукин Владимир Иванович

доктор физико-математических наук, профессо Мухин Сергей Иванович

Ведущая организация: ФГУП «Центральный институт авиационного

моторостроения имени П.И. Баранова»

Защита состоится " 19 - oUVít},; 2010 года в /} ч. мин. н заседании диссертационного совета Д 212.141.15 при Московско государственном техническом университете им. Н.Э. Баумана по адресу: 105005, Москва, ул. 2-ая Бауманская, д. 5.

Отзыв на автореферат в двух экземплярах, заверенный печатью организации, просим высылать по адресу: 105005, Москва, 2-я Бауманская ул., д. 5, МГТУ им. Н.Э. Баумана, ученому секретарю совета Д 212.141.15

С диссертацией можно ознакомиться в библиотеке Московского государственного технического университета им. Н.Э. Баумана.

Автореферат разослан " " C&tf ТУс)^}- 2010 года.

Ученый секретарь диссертационного совета Д 212.141.15, к. т. н., с. н. е., доцент

А.В. Аттетков

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

На защиту выносятся следующие положения:

• Разработанные автором алгоритмы двумерной и трехмерной дискретизации

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

• Разработанный программный комплекс Gridder.

• Решенные с помощью комплекса Gridder задачи математического

моделирования.

Апробация работы. Результаты работы докладывались на следующих семинарах и конференциях: II научно-методическая конференция аспирантов и молодых исследователей «Актуальные проблемы фундаментальных наук», МГТУ им. Н.Э. Баумана, (Москва, 2008); VI Республиканская научная конференция молодых учёных и студентов «Современные проблемы математики и вычислительной техники», (Брест, Беларусь, 2009); VII International Seminar on Mathematical Models and Modeling in Laser-Plasma Processes (Москва, 2010); семинар отдела №11 ИПМ им. M.B. Келдыша РАН "Вычислительные методы и математическое моделирование", (Москва, 2010).

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

ведущих научных журналов и изданий ВАК РФ [4, 5], в составе энциклопедического издания [7], в четырех препринтах [1, 2, 3, 6] и в двух тезисах докладов [8, 9].

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы. Работа представлена на 163 страницах и содержит 101 иллюстрацию. Список литературы содержит 99 наименований.

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

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

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

В первом разделе поставлена проблема оценки качества сеток. Всего таких оценок предложено достаточно много; некоторые варианты приведены в таблицах 1 и2.

Таблица 1. Некоторые критерии оценки качества треугольных элементов

Критерий Формула Интервал возможных значений Оптимальное значение

Отношение радиуса описанной окружности к радиусу вписанной -Rf [2,-но) 2.0

Отношение длины наибольшего ребра к радиусу вписанной окружности [гД-юо) 2-Я

Отношение радиуса описанной окружности к длине наибольшего ребра К 1в = —— 4« [л/з,-н») Гз

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

Наибольший угол в треугольнике ^шлх [Я-/З.Я-) я! 3

Таблица 2. Некоторые критерии оценки качества тетраэдрических элементов

Критерий Формула Интервал возможных значений Оптимальное значение

Отношение радиуса описанной сферы к радиусу вписанной Н [1,+») 3.0

Отношение длины наибольшего ребра к радиусу вписанной сферы [1,+со) 4.898979...

Отношение радиуса описанной сферы к длине наибольшего ребра С0=-— Апах "1 1.2 ) 0.612375...

Отношение куба среднего арифметического длин ребер к объему тетраэдра Г а = — V [1,+оо) 8.4852816...

Минимальный телесный угол в (0,я-/2] тг/2

Отношение объема тетраэдра к наибольшему из произведений длин тройки ребер, выходящих из одной вершины V V- , Л 4 тах ' м (0,л/2/12] л/2/12

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

Во втором разделе приведена авторская классификация методов дискретизации, представленная в форме диаграммы на рис. 1.

Методы дискретизации

| Прямые ) | Итерационные ]

| Методы дроблевля ]—

Мрго,ш на основе шабловоя

Методы отображения | Ц Методы имерп^^")

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

_ Методы граничной коррекгот

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

—I Методы печерпывапяя ]

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

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

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

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

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

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

Блок-схема I. Общий алгоритм дискретизации сложной трехмерной области

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

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

Блок-схема 2. Алгоритм двумерной триангуляции "от угла"

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

Блок-схема 3. Алгоритм трехмерной дискретизации "от ребра"

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

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

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

г) ° " 1

Рис. 2. Этапы построения сетки в сложной двумерной области с помощью ПК (ЗпсЫег

АХ: [0.06. 0.94] Углы: [2.4,169.9*] Триангуляция Делоне: НЕТ

АХ: [0.88, 0.99] Углы: |32.1,122.0°] Триангуляция Делоне: НЕТ

« АХ 1

АХ: |0.77, 0.98] Углы: [41.3,97°] Триангуляция Делоне: ДА

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

Рис. 3. Примеры двумерных сеток

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

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

и

ЕЕ 4.8

— 4.6

— 4.4

_ 4.2 4

- 3.8 3.6

— 3.4

— 12

— 3

— 26

— 16

— 24

— 22

2

16

Ё> 1.2

потенциала, на остальной границе задано производная). Внутренних источников нет.

г\Т 1

&1/ = 0; и\г =р„ / = 1 ..п; — =0.

условие Неймана (нулевая

Здесь и (потенциал) - функции от х и у в двумерном и от х, у и г - в трехмерном случае; fp¡ - константы, Г = Г0 и Г, и ...и Г„- граница области. На рис. 5 показаны сетка и решение для одного из двумерных вариантов задачи, а на рис. 6 - для одного из трехмерных.

Рис. 5. Сетка и полученное на ней решение двумерной задачи для уравнения Лапласа. В точечном контакте 1 задано условие 11=1, в контакте 2 - и=5

РМ

85

— 9

— 8.5

— е

75

- 65

— 5.5

— 5

— 4 5

— Л

— 3.5

— 3

— 25

я 2

ы 1.5

Рис. б. Срез сетки и полученное на ней решение трехмерной задачи для уравнения Лапласа. На нижней грани задано условие 11=10, а одном из углов верхней грани - и=1

МГД-насос - это устройство для перекачки жидкого метала с помощью бегущего магнитного поля. На рис. 7,а представлена принципиальная схема этого устройства. Область моделирования в этой задаче состоит из большого количества подобластей сильно разнящихся размеров, что требует использования сеток со сгущением. Задача обладает осевой симметрией, поэтому решается в

11

пространственно-двумерном приближении. Математическая модель представлена уравнениями Максвелла в МГД-приближении (1), уравнениями Навье-Стокса (2) и уравнением теплового баланса (3).

ЙВ 1

— =rot(vxB-E); rot—B = j; j = <xE; divB = 0; B = //H. (1)

dt ¡л

Здесь E и H - напряженности электрического (в системе координат, где вещество покоится) и магнитного полей соответственно, В - магнитная индукция, /л - магнитная проницаемость, j - вектор плотности тока, t - время, v - скорость движения вещества (в данном случае жидкого металла; скорость остальных частиц в области равна нулю).

p^^ + (vV)vj = -grad/? + /7Av+F, divv = 0. (2)

Здесь р - плотность вещества, р - гидродинамическое давление, r\ = р v -коэффициент динамической вязкости, v - коэффициент кинематической вязкости, v - вектор скорости, F =jxH = rotHxH = (jflHl, 0, - jpHr )т - сила Лоренца.

+ (v, УГ) j = div(srgradr) + Ф. (3)

Здесь Т - температура среды, с„ - удельная теплоемкость вещества, к -теплопроводность, Ф = (jE)+ pvd -d - мощность выделения энергии, включающая в себя джоулеву теплоту и источник теплоты за счет вязкости.

Вектор индукции бегущего магнитного поля меняется по закону В = ВтБт(ю0/+у/0), где Вт =(5т,0,Вг„)Т - вектор амплитуды индукции , а i//0 - начальная фаза колебаний. На верхней и нижней границах области поставлены периодические граничные условия, что соответствует "идеальному" случаю бесконечного индуктора. Таким образом, на текущем этапе модель не учитывает краевые искажения нормальной структуры бегущего магнитного поля, возникающие из-за конечной длины сердечников индуктора.

На рис. 7,6 и 7,в приведены построенная сетка и полученное решение в один из моментов времени (показаны тангенциальная компонента напряженности электрического поля и моментальные линии тока для г- и z-компонент напряженности магнитного поля).

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

Вол -

Ярко индукторЛ

Плзы с обиоткой

а)

б)

Рис. 7. Схема области (а), построенная сетка (б) и решение на ней (в) для задачи

об МГД-насосе

В-индуктор

А-лайнер

•С-

А-лаинер

& индуктор

Рис. 8. Принципиальная схема магнитного компрессора

Электродинамическая часть математической модели представлена уравнениями Максвелла в МГД-приближении (1), дополненными уравнениями для внешних электрических цепей:

Ыв, +Чв -"Б-^в-ХА*. = 0' ^ВГ-'В-

Здесь Ь, Я, С - индуктивность, сопротивление и емкость в цепи соответственно, / и II - сила тока в цепи и напряжение на обкладках конденсатора, %к - плотность поверхностных магнитных токов.

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

В модели термоупругого тела лайнер описывается уравнениями:

1ч=+М - № -Г°>^>>

Ра

дг да,

1 [ дик ди, дит ди \ /^За, 9ай да,)

где р и р0 - текущая и начальная плотности материала лайнера, х, и аг-эйлеровы и лагранжевы (используется общая лагранжева система координат) переменные, и, = - а, - компоненты вектора перемещения, Р = ] х Н - сила Лоренца, действующая на тело, тензор напряжений Лагранжа, Я и /л -коэффициента Ламе, /? = (ЗА+ 2[л)аТ, ат - коэффициент линейного теплового расширения. уа, /,, /2 - тензор деформации и два его первых инварианта. Здесь использовано правило суммирования по повторяющимся индексам. Так как в процессе движения возникают значительные деформации лайнера, в тензоре деформации учтены квадратичные слагаемые.

Рис. 9. Схема области в начальный момент времени (слева) и построенная в области сетка в один из последующих моментов времени (справа). Отдельно показаны увеличенные фрагменты сетки

Соответствующее уравнение энергии записано в виде уравнения теплопроводности:

дТ д

РасV — + рТ—1 = —

0 г д( да,

дТ

к{Т)—

.. ч да, ,

-А

Р

где су - удельная массовая теплоемкость при постоянной деформации, к(Т) -коэффициент теплопроводности, ф = (]'Е) - мощность тепловыделения.

На рис. 9 показана схема области решения и построенная для нее сетка в один из моментов времени. На рис. 10 приведено распределение напряженности электрического поля в этот же момент времени для модели термоупругого лайнера.

Рис. 10. Напряженность электрического поля для модели термоупругого лайнера в один из моментов времени. Справа показан увеличенный фрагмент графика

вблизи края лайнера

На примере данной задачи также можно продемонстрировать, сколь велико может быть влияние качества сетки на качество решения. На рис. 11 приведены решения одной и той же задачи (показаны положение и форма лайнера в варианте модели жидкого тела в различные моменты времени). Решение на графике слева получено на качественных сетках, созданных с помощью ПК (Зп<1<1ег, а решение на графике справа - на низкокачественных сетках, содержащих большое количество вытянутых треугольников. Хотя качественно решения похожи, между ними имеются значительные количественные различия.

Рис. 11. Положение и форма лайнера в варианте модели жидкого тела в различные моменты времени. Решение на графике слева получено на сетках, построенных в ПК (ЗпсМег, а решение на графике справа - на низкокачественных сетках, использовавшихся ранее

Основные выводы и результаты работы

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

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

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

Основные результаты диссертации опубликованы в работах

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

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

3. Применение метода конечных суперэлементов для расчета напряженно-деформированного состояния композиционных материалов / И.А. Щеглов [и др.] 2006. 32 с. (Препринт ИПМ им. М.В. Келдыша РАН, № 36).

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

5. Щеглов И.А. Использование вспомогательного массива узлов при дискретизации сложной трехмерной области методом исчерпывания // Вестник МГТУ им. Н.Э. Баумана. Естественные науки. 2008. № 2. С. 270-283.

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

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

8. Щеглов И.А. Разработка программного комплекса для дискретизации сложных пространственных областей II Актуальные проблемы фундаментальных наук: Сборник трудов. М., 2008. С. 78-81.

9. Щеглов И.А. Методы дискретизации сложных пространственных областей // Современные проблемы математики и вычислительной техники: Материалы VI Республиканской научной конференции молодых ученых и студентов. Брест, 2009. Ч. 1. С. 113-115.

Подписано к печати 14.09.10. Заказ №517 Объем 1,0 печл. Тираж 100 экз. Типография МГТУ им. Н.Э. Баумана 105005, Москва, 2-я Бауманская ул., д.5 (499) 263-62-01

Введение.

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

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.