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

Введение

1 Методы построения нерегулярных тетраэдральных сеток

1.1 Метод дерева октантов.

1.2 Метод движущегося фронта.

1.3 Триангуляция Делоне.

1.4 Алгоритмы построения тетраэдризации Делоне множества вершин.

1.4.1 Алгоритм заметания.

1.4.2 Пошаговый алгоритм прямого построения.

1.4.3 Метод отображения в пространство большей размерности

1.4.4 Итеративные алгоритмы.

1.4.5 Геометрические тесты для построения триангуляции Делоне.

1.5 Критерии оценки качества сетки.

2 Построение тетраэдризации Делоне для тел с кусочно-линейными границами

2.1 Восстановление отсутствующих ребер.

2.2 Восстановление отсутствующих граней

2.3 Алгоритм построения тетраэдризации Делоне для тел с кусочно-липейными границами.

2.4 Обеспечение робастности геометрических расчетов.

2.5 Решение задач о локализации точки и поиска непустых диаметральных и экваториальных шаров.

3 Построение нерегулярных треугольных сеток на криволинейных гранях с использованием анизотропной триангуляции Делоне

3.1 Построение анизотропной триангуляции Делоне множества вершин.

3.2 Построение анизотропной триангуляции Делоне двумерной области

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

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

Методам построения расчетных сеток посвящено множество работ как отечественных, так и зарубежных ученых (см. [13,15-17,21,23,24,30,31,34,37] и др.).

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

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

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

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

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

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

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

В данной работе рассматривается метод построения сеток с тетраэдральными ячейками. В настоящее время для построения таких сеток широко используется тетраэдризацпя Делоне, что связано с ее геометрическими свойствами. Однако тетраэдризацпя Делоне и ее модификации определены лишь для областей с кусочпо-липейпой границей, и алгоритмы ее построения [70,112,114,117] существуют только для таких областей. Поэтому, когда требуется строить данный тип сеток для областей с криволинейной границей, исходную область приближают многогранником. Данный подход более или менее успешно применяется па практике, но он обладает одним существенным недостатком. В процессе генерации сетки возникает необходимость вставлять новые вершины на кусочпо-липейпую границу области. При этом перестроение поверхностной сетки, связанное с добавлением новой вершины, возможно лишь в пределах грани многогранника, на которой находится новая вершина, а это ограничение в некоторых случаях приводит к ухудшению качества сетки (см. главу 4). Таким образом, возникает задача о построении тетраэдризации Делопе и одновременном перестроении кусочно-линейной аппроксимации границы области.

Так как параллельно с тетраэдризацией будет перестраиваться и многогранник, то необходимо также решить задачу о построении поверхностной сетки на криволинейной границе заданной области. Причем не каждый метод построения поверхностных сеток может быть использован. Результирующая поверхностная сетка должна быть максимально близкой к триангуляции Делоне на криволинейных гранях [44,54]. Одним из методов генерации такой сетки является построение для каждой криволинейной грани двумерной анизотропной триангуляции Делопе в ее параметрическом пространстве и последующее ее отображение в трехмерное пространство. Сложность данного подхода, как и вообще триангуляции Делопе, состоит в необходимости поддерживать целостность границы, т.е. в данном случае криволинейные ребра должны явно присутствовать в триангуляции в параметрическом пространстве грани. Если целостность границы нарушена, то возникает задача о восстановлении границы. Эта задача успешно решена в изотропном случае для областей с кусочно-линейной границей (т.е. для стандартной двумерной триангуляции Делоне) [101,115] и в изотропном случае для областей с криволинейной границей (т.е. для двумерных областей с криволинейными границами) [45].

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

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

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

Исследования проведены при финансовой поддержке РФФИ (гранты: 04-01-00402, 02-01-00318). Цель исследования

• Разработка алгоритма построения поверхностных сеток для границ трехмерных областей произвольной формы с использованием двумерной анизотропной триангуляции Делоне.

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

• Создание программного комплекса но построению тетраэдральных сеток в сложных трехмерных областях с криволинейными границами.

• Проведение тестовых и методических расчетов по построению вычислительных сеток в сложных пространственных областях.

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

Научная новизна. Новыми в диссертационной работе являются следующие положения и результаты:

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

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

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

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

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

Практическая ценность

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

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

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

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

1) Метод восстановления криволинейных ребер при построении анизотропной триангуляции Делоне произвольной двумерной области.

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

3) Метод восстановления криволинейной границы при построении тетра-эдризации Делопе с ограничениями трехмерных областей сложной геометрической формы

4) Сравнение результатов работы созданного в диссертации алгоритма с результатами работы других генераторов сеток.

5) Комплекс программ для моделирования трехмерных нестационарных газодинамических течений в областях сложной геометрической формы.

G) Создание программного комплекса для построения тетраэдральных сеток произвольных трехмерных областей с криволинейными границами.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на 14th Int. Meshing Roundtable (San Diego, USA, 2005), Всероссийской конференции «Прикладная геометрия, построение расчетных сеток и высокопроизводительные вычисления» (ВЦ РАН, Москва, 2004), III-V международной конференции но неравновесным

А процессам в соплах и струях (NPNJ) (Истра-Москва, 2000, Санкт-Петербург,

2002, Самара, 2004), XI,XII,XIV международной конференции «Вычислительная механика и современные прикладные программные системы» (ВМ-СППС) (Москва, 2001, Владимир, 2003, Алушта, 2005), X, XII школе-семинаре «Современные проблемы аэрогидродинамики» (Сочи, 2002, Сочи, 2004), 9-ой международной школе-семинаре «Новые информационные технологии» (Судак, 2001), 23rd Int. Symposium on Shock Waves (Fort Worth, USA, 2001), 10th Int. Symposium on Flow Visualization (Kyoto, Japan, 2002), 5th Pacific Symposium on Flow Visualization and Image Processing (Chamonix, France, 2003), па семинаре института прикладной математики им. Келдыша (Москва, 2005).

Публикации. Приводимые в диссертации результаты отражены в 16 публи

• нациях [3-12,27,47,48,57,62,122].

Содержание диссертации. Диссертация состоит из введения, пяти глав и заключения.

Заключение

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

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

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

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

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

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

6) Разработан алгоритм и комплекс программ для моделирования трехмерных нестационарных газодинамических течений в областях сложной геометрической формы.

7) Проведенные расчеты задач газовой динамики продемонстрировали практическую значимость тетраэдральных сеток.

1. Белоцерковский О. М., Давыдов Ю. М. Метод крупных частиц в газовой динамике. — М.: Наука, 1982,— 391 с.

2. Богомолов К. JI., Тишкин В. Ф. Ячейки Дирихле в метрике кратчайшего пути // Математическое моделирование. — 2003. — Т. 15, № 5. — С. 71-79.

3. Боровиков С. Н. Особенности генерации трехмерной триангуляции Делоне для тел с криволинейной границей // Тезисы докладов V международной конференции по неравновесным процессам в соплах и струях, Самара. — М.: Вузовская книга, 2004.— С. 49.

4. Боровиков С. Н., Иванов И. Э., Крюков И. А. О построении нерегулярных пространственных тетраэдральных расчетных сеток // Тезисы докладов XII школы-семинара «Современные проблемы аэрогидродинамики», Сочи. М.: МГУ, 2004.- С. 19-20.

5. Боровиков С. Н., Иванов И. Э., Крюков И. А. Построение тетраэдризации Делоне с ограничениями для тел с криволинейными границами // Журнал вычислительной математики и математической физики. — 2005. Т. 45, № 8. - С. 1407-1423.

6. Боровиков С. Н., Крюков И. А. Построение нерегулярных пространственных расчетных сеток методом Делоне // Тезисы докладов IV международной конференции по неравновесным процессам в соплах и струях, Санкт-Петербург. — М.: МАИ, 2002. — С. 10G-107.

7. Боровиков С. Н., Крюков И. А., Иванов И. Э. Построение нерегулярных треугольных сеток на криволинейных гранях на основе триангуляции Делоне // Математическое моделирование.— 2005.— Т. 17, № 8. С. 31-45.

8. Гаранжа В. А. Барьерный метод построения квазиизометрических сеток // Журнал вычислительной математики и математической физики. 2000. - Т. 40, № 11. - С. 1617-1637.

9. Годунов С. К. Разностный метод численного расчета разрывных решений гидродинамики // Математический сборник. — 1959. — Т. 47(89), № 3. С. 271-306.

10. Годунов С. К., Прокопов Г. П. О расчете конформных отображений и построении разностных сеток // Журнал вычислительной математики и математической физики. — 1967. — Т. 7, № 5. — С. 1031-1059.

11. Дармаев Т. Г, Лисейкин Б. Д. Метод построения многомерных адаптивных разностных сеток // Моделирование в механике.— 1987.— Т. 18, JV« 1.-С. 49-57.

12. Дворников М. В., Тишкин В. Ф., Филатов А. Ю. Триангуляция произвольной мпогосвязной области со сложной границей // Институт математического моделирования РАН. — 1995. — Л'® 7.

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

14. Делоне Б. Н. Геометрия положительных квадратичных форм // Успехи математических наук. — 1937. — Т. 3. — С. 16-62.

15. Делоне Б. Н. Геометрия положительных квадратичных форм // Успехи математических наук. — 1938. — Т. 4. — С. 103-164.

16. Иваненко С. А. Адаптивно-гармонические сетки.— М.: ВЦ РАН, 1997. 181 с.

17. Колган В. П. Применение принципа минимальных значений производной к построению конечно-разностных схем для расчета разрывных решений газовой динамики // Уч. записки ЦАГИ. — 1972.— Т. 3, № 6. — С. 68-77.

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

19. Лисейкин В. Д. Технология конструирования трехмерных сеток для задач аэрогазодинамики // Вопросы атомной науки и техники. Серия математическое моделирование физических процессов.— 1996. — Т. 36, № 1.-С. 18-55.

20. Любимов А. Н., Русанов В. В. Течения газа около тупых тел. — М.: Наука, 1970.-Т. 1,2.

21. Неструктурированные адаптивные сетки для задач математической физики (обзор) / JI. В. Круглякова, А. В. Неледова, В. Ф. Тишкин, А. Ю. Филатов // Математическое моделирование. — 1998. — Т. 10, №3.-С. 93-116.

22. Основы методики «Медуза» численного расчета двумерных нестационарных задач газовой динамики / Ю. П. Глаголева, Б. М. Жогов, Ю. Ф. Кирянов и др. // Численные методы механики сплошной среды. 1972. - Т. 3, № 2. - С. 18-55. - Новосибирск.

23. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение: Пер. с англ. — N1.: Мир, 1989. — 478 с.

24. Сидоров А. Ф. Об одном алгоритме расчета криволинейных сеток, близких к равномерным // Численные методы механики сплошной среды. — 1977. Т. 8, № 4. — С. 149-156. — Новосибирск.

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

26. Теоретические основы и конструирование численных алгоритмов задач математической физики / Под ред. К. И. Бабенко. — М.: Наука, 1979.

27. Тилляева Н. И. Обобщение модифицированной схемы С.К. Годунова на произвольные нерегулярные сетки // Уч. записки ЦАГИ. — 1986. — Т. 17, № 2. С. 18-26.

28. Уэст, Коркеги. Структура течения при сверхзвуковом обтекании угла между пересекающимися клиньями в случае больших чисел Рей-нольдса // Ракетная техника и космонавтика. — 1972. — Т. 10, X9 5. — С. 115-121.

29. Численное решение многомерных задач газовой динамики / С. К. Годунов, А. В. Забродин, М. Я. Иванов и др. — М.: Наука, 1976. — 400 с.

30. Шикин Е. В., Боресков А. В. Компьютерная графика. Полигональные модели. — М.: ДИАЛОГ-МИФИ, 2000.

31. Automated adaptive time-discontinuous finite element method for unsteady compressible airfoil aerodynamics / В. E. Webster, M. S. Shephard, Z. Rusak, J. E. Flaherty // AIAA Journal 1993. - Vol. 32. - Pp. 748757.

32. Barth T. J., Jesperson D. C. The design and application of upwind schemes on unstructured meshes // Proceedings of the AIAA 27th Aerospace Sciences Meeting. — (Reno, Nevada): 1989, — AIAA 89-03G6.

33. Bechet E., Cuilliere J. C., Trochu F. Generation of a finite element MESH from stereolithography (STL) files // Computer Aided Design. — 2002.— Vol. 34, no. l.-Pp. 1-17.

34. Bern M., Eppstein D., Gilbert J. R. Provably good mesh generation // Proc. 31st IEEE Symp. Found of Computer Sci. 1990. - Pp. 231—241.

35. Blacker T. D., Myers R. J. Seams and wedges in plastering: A 3d hexahe-dral mesh generation algorithm // Engineering With Computers. — 1993. — Vol. 2. Pp. 83-93.

36. Boissonnat J.-D., Oudot S. Provably good surface sampling and approximation // Proceedings of Eurographics Symposium on Geometry Processing. 2003. - June. - Pp. 9-19.

37. Borovikov S. N., Lutsky A. E., Znamenskaya I. A. Computer visualization and animation of the flowfields with energy input // Proceedings of the 10th International Symposium on Flow Visualization, Kyoto, Japan. — 2002.

38. Dossen F. J., Heckbert P. S. A pliant method for anisotropic mesh generation // Proceedings of the 5th International Meshing Roundtable. — Pittsburgh, Pennsylvania, USA: 1996. — October.

39. Bowyer A. Computing Dirichlet tessellations // Computer Journal — 1981. Vol. 24, no. 2. - Pp. 162-166.

40. Canann S. A., Tristano J. R., Staten M. L. An approach to combined Laplacian and optimization-based smoothing for triangular, quadrilateral, and quad-dominant meshes // Proceedings of the 7th International Meshing Roundtable. — 1998.

41. Cass R. J. Automated quadrilateral surface mesh generation algorithm // International Journal For Numerical Methods In Engineering. — 1996. — Vol. 39. Pp. 1475-1489.

42. Chen H., Bishop J. Delaunay triangulation for curved surfaces // Proceedings of the 6th International Meshing Roundtable. — Park City, Utah, USA: 1997.-October.

43. Chew L. P. Guaranteed-quality mesh generation for curved surfaces // Proceedings of the 9th Annual ACM Symposium on Computational Geometry. — 1993. — May. — Pp. 274-280.

44. Cohen-Steiner D., Eric Colin de Verdiere, Yvinec M. Conforming Delaunay triangulations in 3D // Proceedings of the 18th Annual ACM Symposium on Computational Geometry. — Barcelona, Spain: 2002. —June.— Pp. 199-208.

45. Colella P. A direct Eulerian MUSCL scheme for gasdynamic // SI AM J. ScL Comput. 1985. - Vol. 6, no. 1. - Pp. 104-117.

46. Ed. by I. Babuska, J. E. Flaherty, W. D. Henshaw et al. — Springer-Verlag, 1995. Vol. 75. - Pp. 97-127.

47. Edelsbrunner H., Seidel R. Voronoi diagrams and arrangements // Discrete & Computational Geometry. — 1986. — Vol. 8, no. 1.— Pp. 25-44.

48. Field D. A. Laplacian smoothing and Delaunay triangulations // Commutations in Applied Numerical Methods. — 1988.— Vol. 4.— Pp. 709712.

49. Flow animation in shock waves researches / L. G. Gvozdeva, N. N. Sysoev, I. A. Znamenskaya, S. N. Borovikov // Proceedings of the 10th International Symposium on Flow Visualization, Kyoto, Japan. — 2002.

50. Fortune S. Voronoi diagrams and Delaunay triangulations // Computing in Euclidean Geometry / Ed. by D.-Z. Du, F. Hwang. — Vol. 1. — Singapore: World Scientific, 1992. Pp. 193-233.

51. Freitag L. A., Knupp P. M. Tetrahedral element shape optimization via the Jacobian determinant and condition number // Proceedings of the 8th International Meshing Roundtable. — South Lake Tahoe, California: 1999. October.

52. Freitag L. A., Ollivier-Gooch C. A comparison of tetrahedral mesh improvement techniques // Proceedings of the 5th International Meshing Roundtable. Pittsburgh, Pennsylvania: 1996. — Pp. 87—100.

53. Freitag L. A., Ollivier-Gooch C. Tetrahedral mesh improvement using swapping and smoothing // Int. J. Numer. Meth. Eng. — 1997. — Vol. 40, no. 21.-Pp. 3979-4002.

54. Frey P. J. About surface remeshing // Proceedings of the 9th International Meshing Roundtable. — New Orleans, Louisiana: 2000. — October.

55. Gabriel K. R., Sokal R. R. A new statistical approach to geographic variation analysis // Systematic Zoology. — 1969. — Vol. 18. — Pp. 259-278.

56. George P. L., Borouchaki H. Back to edge flips in 3 dimensions // Proceedings of the 12th International Meshing Roundtable. — Santa Fe, New Mexico, USA: 2003. September.

57. Goodman J. В., Leveque R. J. On the accuracy of stable schemes for 2D scalar conservation laws // Mathematics of computation.— 1985.— Vol. 45.- Pp. 15-21.

58. Harten A. High resolution schemes for hyperbolic conservation laws //J. Comput. Physics. — 1983. Vol. 49. - Pp. 357-393.

59. Hirsh G. Numerical computations of internal and external flows. — Wiley-Interscience, 1990. —Vol. 1,2.

60. Joe B. Three-dimensional triangulations from local transformations // SIAM Journal on Scientific and Statistical Computing. — 1989. — Vol. 10.- Pp. 718-741.

61. Joe B. Construction of three-dimensional improved-quality triangulations using local transformations // SIAM Journal on Scientific Computing. — 1995.-Nov.-Vol. 16, no. 6.- Pp. 1292—1307.

62. Lau Т., Lo S. Finite element mesh generation over analytical surfaces // Computers and Structures. 1996. — Vol. 59, no. 2. — Pp. 301-309.

63. Lawson C. L. Software for C1 surface interpolation // Mathematical Software III. 1977. - Pp. 161-194.

64. Li Т., McKeag R., Armstrong C. Hexahedral meshing using midpoint subdivision and integer programming // Computer Methods in Applied Mechanics and Engineering. — 1995. — Vol. 124. — Pp. 171-193.

65. Lohner R. Progress in grid generation via the advancing front technique // Engineering with Computers. — 1996. — Vol. 12.— Pp. 186-210.

66. Lo S. H. Volume discretization into tetrahedra-I. verification and orientation of boundary surfaces // Computers and Structures. — 1991. — Vol. 39, no. 5. Pp. 493-500.

67. Lo S. H. Volume discretization into tetrahedra II. 3D triangulation by advancing front approach // Computers and Structures. — 1991. — Vol. 39, no. 5.- Pp. 501-511.

68. Mavriplis D. J. Multigrid solution of the two-dimensional Euler equations on unstructured triangulations // AIAA Journal. — 1988. — Vol. 26, no. 7.

69. Miller G. L., Pav S. E., Walkington N. J. When and why Rup-pert's algorithm works // Proceedings of the 12th International Meshing Roundtable. — Santa Fe, New Mexico, USA: 2003. — September.

70. Mitchell S. A., Vavasis S. A. Quality mesh generation in higher dimensions // SI AM Journal on Computing. 2000. - Vol. 29. — Pp. 1334-1370.

71. Mitchell 5., Vavasis S. An aspect ratio bound for triangulating a d-grid cut by a hyperplane // Proceedings of the 12th Annual ACM Symposium on Computational Geometry. — 1996. — Pp. 48-57.

72. Owen S. J. Constrained triangulation: Application to hex-dominant mesh generation // Proceedings of the 8th International Meshing Roundtable. — South Lake Tahoe, California: 1999. October. — Pp. 31-41.

73. Owen S. J., Saigal S. H-Morph: An indirect approach to advancing front hex meshing // International Journal for Numerical Methods in Engineering. 2000. - Vol. 49, no. 1-2. - Pp. 289-312.

74. Owen S. — Meshing Software Survey. —http: / / www.andrew.cmu.edu/user/sowen / softsurv.html.

75. Parthasarathy V. N., Kodiyalam S. A constrained optimization approach to finite element mesh smoothing // Finite Elements in Analysis and Design. 1991. - Vol. 9. - Pp. 309—320.

76. Pav S. E., Walkington N. J. Robust three dimensional Delaunay refinement // Proceedings of the 13th International Meshing Roundtable. — Williamsburg, Virginia, USA: 2004. — September.

77. Price M., Armstrong C. Hexahedral mesh generation by medial surface subdivision: Part I // International Journal for Numerical Methods in Engineering.- 1995. — Vol. 38, no. 19. — Pp. 3335-3359.

78. Price M., Armstrong C. Hexahedral mesh generation by medial surface subdivision: Part II // International Journal for Numerical Methods in Engineering. 1997. — Vol. 40, — Pp. 111-136.

79. Roe P. L. Approximate Riemann solver, parameter vectors and difference schemes //J. Comput. Physics. — 1981. — Vol. 43. — Pp. 357-372.

80. Roe P. The use of Riemann problem in finite difference schemes // Lect. Notes Phys. 1981. - Vol. 141. - Pp. 354-359.

81. Schneiders R. Octree-based hexahedral mesh generation // International Journal of Computational Geometry & Applications. — 2000. — Vol. 10, no. 4. Pp. 383-398.

82. Schneiders R. — Software. — http: / / www-users.informatik.rwth-aachen.de/~roberts/software.html.

83. Schoberl J. NETGEN an advancing front 2D/3D-mesh generator based on abstract rules // Computing and Visualization in Science. — 1997. — Vol. 1, no. l.-Pp. 41-52.

84. Seveno E. Towards an adaptive advancing front method // Proceedings of the 6th International Meshing Roundtable. — Park City, Utah, USA: 1997. October.

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

86. Shewchuk J. R. Adaptive precision floating-point arithmetic and fast robust geometric predicates // Discrete & Computational Geometry. — 1997.— October. Vol. 18, no. 3. - Pp. 305-363.

87. Shewchuk J. R. Delaunay Refinement Mesh Generation: Ph.D. thesis / School of Computer Science, Carnegie Mellon University.— Pittsburgh, Pennsylvania, 1997. — May.

88. Shewchuk J. R. Tetrahedral mesh generation by Delaunay refinement // Proceedings of the 14th Annual Symposium on Computational Geometry / Association for Computing Machinery. — Minneapolis, Minnesota: 1998. — June. Pp. 86-95.

89. Shewchuk J. R. Mesh generation for domains with small angles // Proceedings of the 16th Annual Symposium on Computational Geometry / Association for Computing Machinery. — Hong Kong: 2000. — June. — Pp. 1-10.

90. Shewchuk J. R. Constrained Delaunay tetrahedralizations and provably good boundary recovery // Proceedings of the 11th International Meshing Roundtable / Sandia National Laboratories. — Ithaca, New York: 2002. — September. Pp. 193-204.

91. Shewchuk J. R. Delaunay refinement algorithms for triangular mesh generation // Computational Geometry: Theory and Applications. — 2002. — May. Vol. 22, no. 1-3. - Pp. 21-74.

92. Si H.— TetGen. A Quality Tetrahedral Mesh Generator and Three-Dimensional Delaunay Triangulator, 2004.— http://www.wias-berlin.de/publications/technicalreports/9;http: //tetgen.berlios.de.

93. Si H., Gartner К. An algorithm for three-dimensional constrained Delaunay tetrahedralizations // Proceeding of the 4th International Conference on Engineering Computational Technology. — Lisbon, Portugal: 2004. — September.

94. Spekreijse S. Multigrid solution of monotone, second order discretization of hyperbolic conservation laws // Mathematics of computation. — 1987. — Vol. 47.-Pp. 135-155.

95. Sweby P. K. High-resolution schemes using flux limiters for hyperbolic conservation laws // SIAM Journal от Numerical Analysis.-— 1984.— Vol. 21.-Pp. 995-1011.

96. Toussaint G. T. The relative neighborhood graph of a finite planar set // Pattern Recognition. — 1980. — Vol. 12, no. 4. — Pp. 2G2-2G8.

97. Tristano J. R., Owen S. J., Canann S. A. Advancing front surface mesh generation in parametric space using a riemannian surface definition // Proceedings of the 7th International Meshing Roundtable. — Dearborn, Michigan: 1998. — October.

98. Unsteady two-dimensional flow in impulse volume discharge / I. A. Zna-menskaya, S. N. Borovikov, I. Ivanov et al. // Proceedings of the 23rd International Symposium on Shock Waves, Fort Worth, USA. — 2001.— Pp. 1050-1055.

99. Van Leer Б. Towards the ultimate conservative difference scheme. A second order sequel to Godunov's method // J. Comput. Physics. — 1979. — Vol. 32. Pp. 101-137.

100. Van Leer D. Flux vector splitting for the Euler equations // Lecture notes in Physics. 1982. - Vol. 170. - Pp. 507-512.

101. Weiler F.} Schindler R., Schneiders R. Automatic geometry-adaptive generation of quadrilateral and hexahedral element meshes for the fem //

102. Proceedings of the 5th International Conference on Numerical Grid Generation in Computational Field Simmulations. — Mississippi State University: 1996. Pp. 689-697.

103. Yerry M. A., Shephard M. S. Automatic three-dimensional mesh generation by the modified-octree technique // Int. J. Numer. Meth. Eng. — 1984. Vol. 20. - Pp. 1965—1990.