Методы самоорганизации и оптимизации для построения трехмерных расчетных сеток тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат наук Кудрявцева, Людмила Николаевна

• Кудрявцева, Людмила Николаевна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Кудрявцева, Людмила Николаевна

ОГЛАВЛЕНИЕ

Стр.

ВВЕДЕНИЕ

ГЛАВА 1. МЕТОД САМООРГАНИЗАЦИИ ДЛЯ ПОСТРОЕНИЯ ТЕТРАЭДРАЛЬНЫХ СЕТОК В НЕЯВНО ЗАДАННЫХ ОБЛАСТЯХ С НЕГЛАДКОЙ ГРАНИЦЕЙ

1.1 Алгоритм построения тетраэдральных сеток в неявных областях

1.2 Алгоритм самоорганизации

1.3 Удаление тетраэдров

1.4 Задание неявной функции

ГЛАВА 2. МЕТОД САМООРГАНИЗАЦИИ: ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ

ГЛАВА 3. МЕТОДЫ НЕЛИНЕЙНОЙ ТЕОРИИ УПРУГОСТИ

ДЛЯ ПОСТРОЕНИЯ РАСЧЕТНЫХ СЕТОК

3.1 Вариационный принцип гиперупругости в лагранжевых переменных

3.2 Меры искажения

3.3 Управление свойствами отображений

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

3.5 Функционалы для распутывания расчетных сеток

ГЛАВА 4. АЛГОРИТМ РАСПУТЫВАНИЯ И ОПТИМИЗАЦИИ РАСЧЕТНЫХ СЕТОК

4.1 Дискретизация меры искажения и метод минимизации

4.2 Геометрические квадратуры

4.3 Итерационная схема минимизации

4.4 Распутывание сеток

ГЛАВА 5. АЛГОРИТМЫ РАСПУТЫВАНИЯ РАСЧЕТНЫХ СЕТОК: ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ

ГЛАВА 6. ПОСТРОЕНИЕ КРИВОЛИНЕЙНЫХ СЕТОК ВОКРУГ ТЕЛ С РУЛЯМИ И КРЫЛЬЯМИ СО СГУЩЕНИЕМ К ЗОНАМ БОЛЬШОЙ КРИВИЗНЫ ПОВЕРХНОСТИ ТО

ГЛАВА 7. ПРИМЕНЕНИЕ ВАРИАЦИОННОГО МЕТОДА ДЛЯ ПОСТРОЕНИЯ ТОЛСТЫХ ПРИЗМАТИЧЕСКИХ СЕТОЧНЫХ СЛОЕВ

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

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

ВВЕДЕНИЕ

Актуальность темы диссертации. Методы построения расчетных сеток в настоящее время достигли высокой степени развития. Для построения тетраэдральных сеток хорошо себя зарекомендовали методы Делоне и подвижного фронта [42], а также их комбинации. В этих методах необходим предварительный этап выделения острых ребер и конических вершин на поверхности, и построения поверхностных сеток. Если области заданы неявно как изоповерхности одной или нескольких функций, то поиск особых линий и вершин оказывается достаточно сложной задачей. Методы построения тетраэдральных сеток в неявно заданных областях с регулярной границей также хорошо изучены, в частности, методы самоорганизации сеток позволяют строить тетраэдральные сетки высокого качества в областях с регулярной границей [35], но задача построения и обоснования эффективных алгоритмов одновременного построения расчетной сетки и реконструкции нерегулярной области с воспроизведением особых линий на границе окончательно не решена.

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

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

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

быть совмещено с реконструкцией области и построением поверхностной сетки.

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

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

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

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

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

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

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

Все основные результаты диссертации являются новыми.

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

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

Апробация работы. Результаты работы докладывались на Международной научной конференции "Science of the future", Санкт-Петербург, 17-20 сентября 2014 г.; на XXXVIII Академических чтениях по космонавтике "Королевские чтения", Москва, 28-31 января 2014 г.; на Международной конференции "The Joint MASCOT12-12th Meeting on Applied Scientific Computing and Tools and ISGG12-12th International Conference on Numerical Grid Generation", Jlac-Пальмас-де-Гран-Канария, Испания, 22-26 октября, 2012 г.; на II Международной конференции "Optimization and applications" (OPTIMA-2011), Петровац, Черногория, 25 сентября - 2 октября, 2011 г., на 51-ой, 54-ой, 55-ой и 56-ой конференции МФТИ, Москва-Долгопрудный, 2008, 2011, 2012, 2013; на XI Междуна-

родной конференции "Забабахинские научные чтения" (ЗНЧ-2012), Снежинск, 16-20 апреля 2012 г.; на XIV Международной Байкальской школе-семинаре "Методы оптимизации и их приложения Северобайкальск, 2-8 июля 2008 г.; на Международной конференции "Numerical geometry, grid generation and scientific computing"(NUMGRID2008, NUMGRID2010, NUMGRID2012), Москва; на семинаре ВЦ РАН (рук. Ю.Г. Евтушенко), Москва, 2014 г.; на семинаре Лаборатория математического моделирования нелинейных процессов в газовых средах "Flowmodellium Laboratory" (рук. C.B. Утюжников), Москва, 2014 г.

Публикации. Основные результаты диссертации опубликованы в 11 работах, включая 2 статьи в российских и международных рецензируемых журналах, рекомендованных ВАК [93], [98].

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

Структура и объем диссертации. Диссертация состоит из введения, семи глав, заключения и списка литературы. Она изложена на 102 страницах текста, набранного в редакционного-издательской системе Latex2e, содержит 48 рисунков и 1 таблицу. Библиография содержит 98 наименований.

ГЛАВА 1

МЕТОД САМООРГАНИЗАЦИИ ДЛЯ ПОСТРОЕНИЯ ТЕТРАЭДРАЛЬНЫХ СЕТОК В НЕЯВНО ЗАДАННЫХ ОБЛАСТЯХ С НЕГЛАДКОЙ ГРАНИЦЕЙ

Задача построения расчетных сеток является важным этапом численного моделирования и возникает во многих фундаментальных и прикладных задачах. В настоящее время методы построения тетраэдральных сеток в областях сложной формы достигли зрелости [32], [42], [45], [60], [65], [77].

На их основе написано большое количество пакетов прикладных программ, которые используются в самых разных предметных областях. При этом задачу построения расчетной сетки предваряет этап построения геометрической модели объекта. Как правило, для построения такой модели, например, самолета или автомобиля, используются методы геометрического моделирования и системы автоматизированного проектирования (САПР). В итоге геометрическая модель собирается из набора криволинейных граней, заданных Л-сплайнами, и правил склейки таких граней. В биологических задачах и задачах инженерного анализа геометрическая модель часто строится по данным трехмерного сканирования, томографии или электронной микроскопии. При этом требуется предварительный этап реконструкции поверхности, выходными данными которого является поверхность, состоящая из плоских треугольников, см., например, [19], [20], [26], [59], [64].

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

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

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

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

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

Отправной точкой для создания предлагаемого алгоритма послужила рабо-

та [69], в которой был предложен простой алгоритм построения двумерных и трехмерных сеток Делоне в неявных областях. Этот алгоритм был реализован в виде небольшой программы в системе Матлаб. Идея алгоритма из [69] состоит в следующем: ребра сетки интерпретируются как упругие распорки с заданным распределением длины, а задача построения сетки рассматривается как задача достижения равновесия механической системы. При этом длины распорок выбираются так, чтобы на квазиравновесном решении они находились в сжатом состоянии. Топология связей, т.е. выбор тех точек, которые соединяются ребрами, следует из принципа пустого шара Делоне. Для задания неявной области в [69] было предложено использовать функцию расстояния от границы со знаком. Замечательным свойством этого алгоритма в двумерном случае является высокая степень регулярности получаемых треугольных сеток, даже если начальное приближение задается хаотически. Сравнительный анализ (см. [90]) показал , что как алгоритм самоорганизации двумерных сеток данный алгоритм является одним из лучших, в частности, он менее зависим от начального приближения по сравнению с известным алгоритмом самоорганизации Ллойда, см. [63]. Различные обобщения алгоритма Ллойда рассмотрены, например, в [18], [35]. Известно, что в трехмерном случае алгоритм Ллойда сталкивается с рядом трудностей. Поиск равновесного состояния в сочетании с выбором связности согласно принципу Делоне, оказывается недостаточным для удаления из получаемой сетки плоских тетраэдров, которые ниже за свой внешний вид будут именоваться "конвертами". Таким образом, обычно требуется дополнительный этап удаления подобных тетраэдров.

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

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

1.1 Алгоритм построения тетраэдральных сеток в неявных областях

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

Пусть задана некоторая функция и{х) : М3 —» М. такая, что во внутренних точках области выполнено условие и(х) < 0, а в дополнении области условие и(х) > 0, (см. рис. 1.1).

Рис. 1.1. Пример неявного задания двумерной области

Предполагается, что функция и(х) непрерывна по Липшицу, представима в виде разности выпуклых функций, является кусочно-гладкой, и ее производные вдоль некоторого невырожденного векторного поля, транверсалыюго к дО,, существуют и не равны нулю в некотором конечном слое 5 около дП. Слой определяется следующим образом: предполагается что существует некоторая постоянная го > 0 такая, что 5 содержит объединение всех шаров радиуса г о с центрами, лежащими на дО,. На рис. 1.1 иллюстрируется задание области по-

средством подобной неявной функции.

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

Тетраэдральная сетка в неявной области. Обсудим, что следует рассматривать в качестве допустимого результата для алгоритма построения трехмерных расчетных сеток. Трехмерная область О,, задаваемая неравенством и(х) < 0, аппроксимируется многогранником граница которого составлена из плоских треугольников, склеенных по целым ребрам. Внутри многогранника строится нормальное тетраэдральное разбиение Т, причем множество граничных треугольников является подмножеством граней этого разбиения. При этом требуется, чтобы при стремлении размера ребер граничной сетки к нулю поверхность сЮ^ сходилась поточечно к дО,. Кроме того, необходимо, чтобы кусочно-постоянное поле щ единичных нормалей к дПь сходилось бы к кусочно-непрерывному полю единичных нормалей и поверхности . Параметр к играет роль размера ячеек, т.е. предполагается, что максимальная длина ребра сетки Т не превышает С/г, где С - некоторая постоянная.

Таким образом, предполагается, что существует гомеоморфизм грь : К3 —> М3 такой, что — = дО., и а) для всех р е д^ь справедливо

\р — фн(р)\ 0 при Н —> 0, б) для всех р € не принадлежащих множеству острых ребер Т, справедливо |щ(р) — 1'(фь(р))\ 0 при к —> 0.

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

согласно заданной плотности распределения. Плотность распределения задается функцией : К3 —» Е, > 0, которую можно рассматривать как целевое значение длины ребра сетки в точке х. Как показано в [69], задание функции непосредственно не всегда является удобным. На практике для задания целевой длины ребер используется функция = М/(х), где функция /(х) задает относительный характерный размер, т.е. отношение целевых длин ребер сетки в различных точках расчетной области, а коэффициент М зависит от К и объема области 17. При этом на каждом шаге алгоритма по заданному множеству вершин строится тетраэдральная сетка, удовлетворяющая условию Делоне (см. [1], [10], [83]).

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

1.2 Алгоритм самоорганизации

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

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

Итак, предположим, что в М3 задана точечная система 8 = {р\,р2, • • • ,Рп} ■ Обозначим через Т{£) тетраэдральное разбиение Делоне, из которого удалена некоторая совокупность тетраэдров, не удовлетворяющих критерию принадлежности к расчетной области. Объединение всех тетраэдров из Т составляет многогранник О.и, который в общем случае может не аппроксимировать область О,. Будем считать, что сетка Т(£) является равновесной, если выполняется условие

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

Здесь Fe - сила расталкивания вершин вдоль ребер сетки Т, Fee - сила, возникающая из-за отталкивания противолежащих ребер каждого из тетраэдров сетки, a Fvf - сила, возникающая из-за отталкивания вершины тетраэдра от противолежащей грани. Вектор Fb{pi) обозначает так называемую "обостряющую" граничную силу, которая служит для уменьшения угла между нормалью к граничной грани и направлением вектора градиента неявной функции и. При этом Fb(pi) = 0, если р{ - внутренняя вершина сетки. Оператор U определяется следующим образом:

Таким образом, можно говорить, что проектор I/ удаляет из вектора д в граничной вершине р^ компоненту, ортогональную изоповерхности и, проходящей

F(Pi) = 0, г < щ

F(pi) = U(weFe(pi) + weeFee(pi) + wvfFvf(pi)) + wbFb(pi)

ее

внутренняя точка из Qh Pi € dQh

через Р1. Заметим, что проектор С/ определен лишь для тех точек Pi, в которых вектор Уи{рг) определен и отличен от нуля. Из свойств функции и следует, что в произвольной точке х изоповерхность и(х) = 0 обладает касательным конусом К(х). Если этот конус является плоскостью, то это - точка гладкости функции, и градиент определен однозначно. В общем случае, для того, чтобы определить направление вектора обобщенного градиента, можно использовать, например, луч, соединяющий точку х с центром шара, который является ближайщим к х среди всех шаров единичного радиуса, лежащих внутри конуса К(х) [4]. Далее, величины гуе, тее, ть - это некоторые положительные весовые коэффициенты.

Расталкивающие силы вычисляются следующим образом. Рассмотрим вначале силы расталкивания вдоль ребер. Положим -Ре(рг) = 0 для всех г. Рассмотрим ребро ек с вершинами р{ и pj из множества ребер сетки Т. Тогда вклад от этого ребра в силы, действующие на вершины р{ и р^, записывается в виде следующего псевдокода:

^е(Рг) := Ре(р1) + (Рг - р^ае, := ^е(^) + (р,- - р{)ае,

ГД6 Ь0 1

ае = тах(~г~ - 0)» ь = \Pi-Pjl, и = М/(-{рг (1.1)

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

Рассмотрим вычисление силы, расталкивающей противолежащие ребра тетраэдра. Положим .Рее(рг) = 0 для всех г. Пусть Т& £ Т - некоторый тетраэдр, четыре вершины которого в локальной нумерации обозначены через {1,2,3,4}. При этом в глобальном списке этим вершинам соответствуют вершины с номерами ц, ¿2, г'з, ¿4. Рассмотрим силу отталкивания ребра (рьрг) от ребра (Р31Р4), вычисление которой иллюстрируется на рис. 1.2 а).

Рис. 1.2. а) Сила расталкивания противолежащих ребер; б) сила отталкивания вершины от

противолежащей грани.

Пусть пе обозначает вектор, начальная точка которого а принадлежит ребру \Рз,Ра\, а конечная Ь - ребру [рьРгЬ и который ортогонален этим ребрам. Если такого отрезка вектора не существует, то положим пе = 0. Данная сила вносит следующий вклад в Fee :

FeeiPh) := FeeiPn) + (1 ~ A*)neVee, FeeiPb) •= Fee(Pi2) + ЦПеУее,

Fee(Pi3) := ^ее(Рг4) ~ i1 ~ ¿О^ее» ^ее(Рг4) '•= ^eefej ~ ^е^ее,

где

vee = max(^ - 1,0), L = \a- b\, L0 =

\a-pi

и =

\Ь~Ръ

\Р2 Pl |' " \Р4~Рз\ а с = +Р2 +Р4) - центроид тетраэдра. Суммируя вклады от трех пар противолежащих ребер для каждого тетраэдра, получаем величины Fee во всех вершинах сетки.

Рассмотрим теперь силу расталкивания грани / с вершинами Р1,Р2,Рз и противолежащей ей вершины р4, как показано на рис. 1.2 б). Вклад от пары "грань-вершина" в силу Fvf можно записать в следующем виде

FvfÍPu) '■= Fvf(pi4) + nf\q\vvf sin2 а

Fvf{Pim) := Fvf(pim) - \nf\q\vv} sin2 a, m = 1,2,3

где

Lq 1 Fl

vvf = max(-^-l,0), L=\q\, q = P4 - ~(pi + P2 + Рз), L0= J-Mf(c)

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

Обостряющая граничная сила -Рь(рг) для граничной точки Рг задается следующей формулой (см. [67])

=

£ агеа(Г)

Т^аг^)

(1.2)

где star(p¿) обозначает совокупность граничных треугольников содержащих вершину Рг, точка с - центроид треугольника Т. На рис. 1.3 а) показано, что если точка р{ не лежит на "сравнительно остром" ребре принадлежащем <9Г2, то проекция граничной силы Рь(р{) на касательную плоскость к изоповерхности и(х) направлена в сторону ребра. Если же вершина рг находится на ребре, как показано на рис. 1.3 б), то граничная сила оказывается почти сонаправлена с вектором градиента и.

а)

б)

уи(р{)

Уи(р{)

Рис. 1.3. Граничная обостряющая сила: а) вершина притягивается к потенциальному острому ребру; б) вершина близка к равновесному состоянию.

Квазиравновесная сетка строится следующим образом. Пусть на к-й итерации задана точечная система £к, состоящая из п точек р\. Шаг алгоритма самоорганизации выглядит так.

1) Построение тетраэдрального разбиения Делоне Тк(£к) точечной системы £к посредством алгоритма С^шскЬиП (см. [24]), встроенного в Матлаб;

Список литературы диссертационного исследования кандидат наук Кудрявцева, Людмила Николаевна, 2014 год

СПИСОК ЛИТЕРАТУРЫ

1. Вороной Г.Ф. Исследования о примитивных параллелоэдрах // Собр. соч. Т.2. - Киев: Изд-во АН УССР, 1952. - С. 239-368.

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

3. Гаранжа В.А. Поливыпуклые потенциалы, обратимые деформации и термодинамически согласованная запись уравнений нелинейной теории упругости. // Ж. вычисл. матем. и матем. физ. - 2010. - Т. 50, № 9. - С. 1561-1587.

4. Гаранжа В.А. Дискретные кривизны, квазиизометрические отображения и квазиоптимальные расчетные сетки. Диссертация на соискание ученой степени доктора физико-математических наук - Новосибирск, 2011. - 286 с.

5. Гаранжа В.А., Капорин И.Е. Регуляризация барьерного вариационного метода построения расчетных сеток // Ж. вычисл. матем. и матем. физ. - 1999. - Т. 39, № 9. - С. 1489-1503.

6. Гаранжа В.А., Капорин И.Е. О сходимости градиентного метода минимизации функционалов теории упругости с конечными деформациями и барьерных сеточных функционалов // Ж. вычисл. матем. и матем. физ. - 2005. -Т. 45, № 8. - С. 1450-1465.

7. Годунов С.К., Гордиенко В.М., Чумаков Г.А. Квазиизометрическая параметризация криволинейного четырехугольника и метрика постоянной кривизны // Труды Института математики СО РАН. - 1994. - Т.26. - С. 3-19.

8. Годунов С.К., Роменский Е.И. Элементы механики сплошных сред и законы сохранения. - Новосибирск: Научн. книга, 1998. - 280 с.

9. Данилов A.A. Технология построения неструктурированных тетраэдральных сеток // Ж. вычисл. матем. и матем. физ. - 2010. - Т. 50, № 1. - С. 146-163.

10. Делоне В.Н. О пустоте сферы // Изв. АН СССР. - 1934. - № 4. - С. 793-800.

11. Иваненко С.Л.Построение невырожденных сеток // Ж. вычисл. матем. и матем. физ. - 1988. - V. 28, №10. - С. 1498-1506

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

13. Иваненко С. А. Управление формой ячеек в процессе построения сетки // Ж. вычисл. матем. и матем. физ. - 2000. - Т. 40, № 11. - С. 1662-1684.

14. Иваненко С.А., Чарахчьян А.А. Криволинейные сетки из выпуклых четырехугольников // Ж. вычисл. матем. и матем. физ. - 1988. - Т. 28, № 4. - С. 503-514.

15. Козелков А. С., Дерюгин Ю. Н., Зеленский Д. К. и др. Многофункциональный пакет программ ЛОГОС для расчета задач гидродинамики и тепломас-сопереноса на суперЭВМ: базовые технологии и алгоритмы // Труды XII Международного семинара "Супервычисления и математическое моделирование". - Саров: ФГУП РФЯЦ-ВНИИЭФ, 2011. - С. 215-230.

16. Лисейкин В. Д. О конструировании регулярных сеток на n-мерных поверхностях // Ж. вычисл. матем. и матем. физ. - 1991. - Т. 31, № И. - С. 47-57.

17. Съярле Ф. Математическая теория упругости. - М.: Мир, 1992. - 472 с.

18. Alliez P., Cohen-Steiner D., Yvinec M., Desbrun M. Variational tetrahedral meshing // ACM Trans. Graphics. - 2005. - V. 24. - P. 617-625.

19. Amenta N., Bern M. Surface reconstruction by Voronoi filtering // Discrete Comput. Geometry. - 1999. - V. 22, N.4. - P. 481-504.

20. Amenta N., Choi S, Dey T., Leekha N. A simple algorithm for homeomorphic surface reconstruction // Proc. 16th Ann. ACM Symp. Comput. Geometry. -New York: ACM Press, 2000. - P.213-222.

21. Ball J.M. Convexity conditions and existence theorems in nonlinear elasticity. // Archive for Rational Mechanics and Analysis. - 1977. - V. 63, N. 4. - P. 337-403.

22. Ball J.M. Global invertibility of Sobolev functions and the interpénétration of matter. // Proc. Roy. Soc. of Edinburgh. Section: A Mathematics - 1981. - V. 88, N. 3-4. - P. 315-328.

23. Ball J.M. Some open problems in elasticity // Geometry, Mechanics, and Dynamics. - Berlin, Heidelberg, New York: Springer, 2002. - P. 3-59.

24. Barber C.B., Dobkin D.P., Huhdanpaa H. The Quickhull algorithm for convex hulls 11 ACM Trans. Math. Software. - 1996. - V. 22, N. 4. - P. 469-483.

25. Beg M.F., Miller M.I., Trouve A., Younes L. Computing large deformation metric mappings via geodesies flows of diffeomorphisms // International Journal of Computer Vision. - 2005. - V. 61, N. 2. - P. 139-157.

26. Blum H. A transformation for extracting new descriptors of shape // Models Perception of Speech and Visual Form. - Cambridge, MA: M.I.T. Press, 1967. -P. 362-380.

27. Boissonat J.-D., Cohen-Steiner D., Mourrain B. et al. Meshing of surfaces // Effective Comput. Geometry for Curves and Surfaces. - Berlin, Heidelberg, New York: Springer, 2007. - P. 181-230.

28. Brackbill J. U., Saltzman J.S. Adaptive zoning for singular problems in two dimensions // J. Comput. Phys. - 1982. - V. 46, N. 3. - P. 342-368.

29. Branets L. V., Garanzha V.A. Distortion measure for trilinear mapping. Application to 3-D grid generation. // Num. Linear Algebra Appl. - 2002. -V. 9, N. 6-7. - P. 511-526.

30. Branets L, Carey G.F. Extension of a mesh quality metric for elements with a curved boundary edge or surface. // J. Comp. Infor. Sci. Eng. - 2005. - V. 5, N. 4. - P. 302-308

31. Charakhch'yan A.A., Ivanenko S.A. A variational form of the Winslow grid generator. //J. Comput. Phys. - 1997. - V. 136, N. 2. - P. 385-398.

32. Carey G. F. Computational Grids: Generation, Adaptation, and Solution Strategies. - Boca Raton: CRC Press, 1997. - 472 p.

33. Crowley W.P. An equipotential zoner on a quadrilateral mesh. // Technical report, Lawrence Livermore National Lab, Livermore, 1962.

34. Danczyk J., Surech K. Finite element analysis over tangled simplicial meshes: Theory and implementation. // Finite Elements in Analysis and Design - 2013. - V. 70-71. - P.57-67.

35. Du Q., Wang, D. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations // Internat. J. Numer. Meth. in Engrg. - 2003. -V. 56, N. 9. - P. 1355-1373.

36. Escobar J.M., Rodriguez E., Montenegro R., Montero G., Gonsalez-Yuste J.M. Simultaneous untangling and smoothing of tetrahedral meshes. // Comput. Meth.

Appl. Mech. Eng. - 2003. - V. 192, N. 25. - P. 2775-2787.

37. Farin G. Curves and surfaces for computer-aided geometric design. 4th edition.

- Orlando, FL: Academic Press, 1997. - 429 p.

38. Floater M.S., Hormann K. Surface Parameterization: a Tutorial and Survey. // Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization. Part 4. - Berlin, Heidelberg, New York: Springer, 2005. - P. 157186.

39. Freitag L., Ollivier-Gooch C. A comparison of tetrahedral mesh improvement techniques. // Proc. 5th Int. Meshing Roundtable. - Albuquerque: Sandia National Laboratories, 1996. - P. 87-100.

40. Freitag L.A. Plassmann P, Local optimization-based simplicial mesh untangling and improvement. // Int. J. Numer. Methods Eng. - 2000. - V. 49, N. 1-2. -P. 109-125.

41. Freitag L.A., Knupp P.M. Tetrahedral mesh improvement via optimization of the element condition number // Int. J. Numer. Methods Eng. - 2002. - V. 53. - P. 1377-1391.

42. Frey J. L., George P. L. Mesh generation: Applications to finite elements. - Paris: Herm'es, 2000. - 817 p.

43. Garanzha V.A. Maximum norm optimization of quasi-isometric mappings // Num. Linear Algebra Appl. - 2002. - V. 9, N. 6-7. - P. 493-510.

44. Garanzha V.A. Quasi-isometric surface parameterization. // Appl. Numer. Math.

- 2005. - V. 55, N. 3. - P. 295-311.

45. George P.L., Saltel E. "Ultimate" robustness in meshing an arbitrary polyhedron // Int. J. Numer. Meth. Engrg. - 2003. - V. 58. - P. 1061-1089.

46. Hildebrandt K., Polthier K., Wardetzky M. On the convergence of metric and geometric properties of polyhedral surfaces // Geometriae Dedicata. - 2006. - V. 123, N. 1. - P. 89-112.

47. Jacquotte O-P. A mechanical model for a new mesh generation method in computational fluid dynamics. // Comp. Meth. Appl. Mech. Eng. - 1988. - V. 66, N. 3. - P. 323-338.

48. Jacquotte O-P. Grid optimization methods for quality improvement and

adaptation. // Thompson J.F., Soni B.K., Weatherill N., eds. Handbook of Grid Generation. - CRC Press, 1998. - P. 33:1 - 33:24.

49. Joe B. Construction of three-dimensional improved-quality triangulations using local transformations // SIAM J. Sci. Comput. - 1995. - V. 16, N.6. - P. 12921307.

50. Kansa E.J. Multiquadrics—a scattered data approximation scheme with applications to computational fluid-dynamics. II. Solutions to parabolic, hyperbolic and elliptic partial differential equations // Comput. Math. Appl. - 1990. - V. 19, N. 8-9. - P. 147-161.

51. Kansa E.J., Carlson R.C. Radial basis functions: A class of grid-free, scattered data approximations // CFD Journal. - 1995. - V. 3, N 4. - P. 479-496.

52. Kim J., Panitanarak T., Shontz S.M. A multiobjective mesh optimization framework for mesh quality improvement and mesh untangling // International Journal of Numerical Methods in Engineering. - 2013. - V. 94, N. 1. - P. 20-42.

53. Knupp P.M. Achieving finite element mesh quality via optimization of the Jacobian matrix norma nd associated quantities. Part I: a framework for surface mesh optimization // Int. J. Numer. Methods Eng. - 2000. - V. 48, N. 3. - P. 401-420.

54. Knupp P.M. Achieving finite element mesh quality via optimization of the Jacobian matrix norm and associated quantities. Part II: a framework for volume mesh optimization and the condition number of the Jacobian matrix // Int. J. Numer. Methods Eng. - 2000. - V. 48, N. 8. - P. 1165-1185.

55. Knupp P. Algebraic mesh quality metrics. // SIAM J. Sci. Comput. - 2001. -V. 23, N.l - P. 193-218.

56. Knupp P.M. Hexahedral and tetrahedral mesh untangling. // Eng. Comput. -2001. - V. 17, N. 3. - P. 261-268.

57. Knupp P.M. A method for hexahedral mesh shape optimization. // Int. J. Numer. Methods Eng. - 2003. - V. 58, N. 2 - P. 319-332.

58. Labelle F., Shewchuk J.R. Isosurface stuffing: fast tetrahedral meshes with good dihedral angles //ACM Trans. Graphics: Special Issue on the Proc. of ACM SIGGRAPH 2007. - New York: ACM Press, 2007. - V. 26, N 3. - P. 57:1-57:10.

59. Levoy M., Pulli K., Curless B., et al. The digital michelangelo project: 3D scanning of large statues // Proc. of ACM SIGGRAPH 2000. - New York: ACM Press, 2000. - P. 131-144.

60. Liseikin V.D. Grid generation methods. 2nd Ed. - Berlin, Heidelberg, New York: Springer, 2010. - 390 p.

61. Liu A, Joe B. On the shape of tetrahedra from bisection. // Mathematics of computation. - 1994. - V. 63, N. 207. - P. 141-154.

62. Lopez E.J., Nigro N.M., Storti M.A. Simultaneous untangling and smoothing of moving grids // Int. J. Numer. Methods Eng. - 2008. - V. 76, N. 7. - P. 994-1019.

63. Lloyd S.P. Least squares quantization in PCM. // IEEE Trans. Inform. Theory.

- 1982. - V. 28, N. 2. - P. 129-137.

64. Lorensen W.E., Cline H.E. Marching cubes: a high resolution 3D surface construction algorithm // Proc. of ACM SIGGRAPH '1987. - New York: ACM Press, 1987. - V. 21, N 4. - P. 163-170.

65. Marcum D.L., Weatherill N.P. Unstructured grid generation using iterative point insertion and local reconnection // AIAA Journal. - 1995. - V. 33, N. 9. - P. 1619-1625.

66. Ohtake Y., Belyaev A., Alexa M., et al. Multi-level partition of unity implicits 11 ACM Trans, on Graphics. - 2003. - V. 22, N. 3. - P. 463-470.

67. Ohtake Y., Belyaev A., Pasko A. Dynamic mesh optimization for polygonized implicit surfaces with sharp features // The Visual Computer. - 2003. - V. 19, N. 2. - P. 115-126

68. Orenstein J.A. Multidimensional tries used for associative data searching. // Inform. Proc. Lett. - 1982. - V. 14, N. 4. - P. 150-157.

69. Persson P.-O., Strang G. A Simple Mesh Generator in MATLAB // SIAM Rev.

- 2004. - V. 46, N 2. - P. 329-345.

70. Powell M.J.D. Radial basis functions for multivariable interpolation: a review // J.C. Mason, M.G. Cox (Eds.), Algorithms for Approximations. - Oxford: Clarendon Press, 1987. - P. 143-167.

71. Riemslagh K, Vierendeels J, Dick E. Two-dimensional incompressible Navier-Stokes calculations in complex-shaped moving domains. //J. Engrg. Math. -

1998. - V. 34, N. 1-2. - P. 57-73.

72. Rumpf M. A variational approach to optimal meshes. // Numer. Math. - 1996.

- V. 72, N. 4. - P. 523-540.

73. Samet H. The design and analysis of spatial data structures. - Reading: Addison-Wesley, 1990. - 499 p.

74. Sastry S.P., Shontz S.M., Vavasis S.A. A log-barrier method for mesh quality improvement and untangling. // Engineering with Computers - 2014. - V. 30, N. 3. - P. 315-329.

75. Shen C., O'Brien J.F., Shewchuk J.R. Interpolating and approximating implicit surfaces from polygon soup. // Proc. of ACM SIGGRAPH 2004. - New York: ACM Press, 2004. - P. 896-904.

76. Shontz S.M., Vavasis S.A. A robust solution procedure for hyperelastic solids with large boundary deformation. // Engineering with Computers - 2012. - V. 28, N. 2. - P. 135-147.

77. Teng S.-H., Wong C. W., Lee D. T. Unstructured mesh generation: Theory, practice, and perspectives // Internat. J. Comput. Geometry and Applic. - 2000.

- V. 10, N. 3. - P. 227-266.

78. Thompson J.F., Soni B.K., Weatherill N., eds. Handbook of Grid Generation -CRC Press, 1998.

79. Tournois J., Wormser C., Alliez P., Desbrun M. Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation // ACM Trans. Graphics. - 2009. - V. 28, N. 3. - P.75:l-75:9.

80. Trouve A. An approach of pattern recognition through infinite dimensional group action // Technical report, LMENS-95-9, Ecole. Normale Supérieure, France, 1995.

81. Vachal P., Garimella R.V., Shashkov M.J. Untangling of 2D meshes in ALE simulations // J. Comput. Phys. - 2004. - V. 196, N. 2. - P. 627-644.

82. Vavasis S.A. A Bernstein-Bezier Sufficient Condition for Invertibility of Polynomial Mapping Functions. // Research report CoRR cs.NA/0308021, Cornell University Library, 2003.

83. Voronoi G.F. Nouveles applications des paramétrés continus a la theorie de formes

quadratiques //J. Reine Angew. Math. - 1908. - V. 134. - R 198-287.

84. Winslow A.M. Numerical solution of the quasilinear Poisson equation in a nonuniform triangle mesh. // J. Comput. Phys. - 1966. -V. 1, N. 2. - P. 149-172.

85. Белокрыс-Федотов А.И., Гаранжа В.А., Кудрявцева JI.H. Построение тетраэдральных и гексаэдральных сеток в неявных областях // Тезисы XIII Международного семинара "Супервычисления и математического моделирование". - Саров: ФГУП РФЯЦ-ВНИИЭФ, 2011. - С. 43-45

86. Белокрыс-Федотов А.И., Гаранжа В.А., Кудрявцева JI.H. Построение тетраэдральных сеток при неточном и противоречивом задании входных данных // Тезисы XI Международная конференция "Забабахинские научные чтения" (ЗНЧ-2012). - Снежинск: РФЯЦ-ВНИИТФ, 2012. - С.309.

87. Белокрыс-Федотов А.И., Гаранжа В.А., Кудрявцева Л.Н., Титарев В.А., Утюэ/сников C.B. Построение трехмерных расчетных сеток для вычислительного комплекса по математическому моделированию задач высотной гиперзвуковой аэродинамики лаборатории Flowmodellium // Труды 56-й научной конференции МФТИ: Управление и прикладная математика. Т. 2. -Москва: МФТИ, 2013. - С. 86-87

88. Б елокрыс-Федотов А.И., Гаранжа В.А., Кудрявцева Л.Н., Утюжников C.B. Построение толстых призматических сеточных слоев около тел сложной формы // Сборник научных трудов Международной конференции «Разностные схемы и их приложения», посвященной 90-летию профессора В.С.Рябенького. - Москва: ИПМ им. М.В. Келдыша РАН, 2013 г. - С. 48-50.

89. Белоусова Л.Н., Гаранжа В.А. Построение сеток Делоне в неявно заданных областях с негладкой границей // Труды 51-й научной конференции МФТИ: Часть VII. Управление и прикладная математика Том 2. - Москва: МФТИ, 2008. - С. 98-101.

90. Белоусова Л.Н., Гаранжа В.А. Сравнение алгоритмов глобальной оптимизации расчетных сеток // Труды XIV Международной Байкальской школы-семинара "Методы оптимизации и их приложения". Т. 3. Вычислительная математика. - Иркутск: ИСЭМ СО РАН, 2008. ISBN 978-5-93908-052-1. - С. 21-26.

91. Гаранжа В.А., Забарко Д.А., Котенёв В.П., Кудрявцева JI.H. Построение блочных расчётных сеток с использованием вариационного метода вокруг тел с рулями и крыльями // Труды секции 22 имени академика В.Н. Чело-мея XXXVIII Академических чтений по космонавтике: "Ракетные комплексы и ракетно-космические системы - проектирование, экспериментальная отработка, лётные испытания, эксплуатация". - Реутов: ОАО "ВПК "НПО машиностроения" , 2014. - С. 84-91

92. Гаранэюа В.А., Кудрявцева JI.H. Построение трехмерных сеток Делоне по слабоструктурированным и противоречивым данным // Оптимизация и приложения: сборник статей. - М.: ВЦ РАН, 2010. - С. 42-74.

93. Гаранжа В. А., Кудрявцева JI. Н. Построение трехмерных сеток Делоне по слабоструктурированным и противоречивым данным //Ж. вычисл. матем. и матем. физ. - 2012. - Т. 52, №3 - С. 499-520

94. Гаранжа В.А., Кудрявцева JI.H. Меры качества трехмерных сеток // Труды 56-й научной конференции МФТИ: Всероссийской научной конференции "Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе". Управление и прикладная математика. Том 2. - Москва: МФТИ, 2013. - С. 84-85.

95. Гаранжа В.А., Кудрявцева JI.H., Утюжников С.В. Построение поверхностных и объемных сеток вариационным методом с адаптацией к кривизне поверхности // Тезисы XI Международная конференция "Забабахинские научные чтения" (ЗНЧ-2012). - Снежинск: РФЯЦ-ВНИИТФ, 2012. - С. 308.

96. Garanzha V.A., Kudriavtseva L.N. Gradient projection based optimization methods for untangling and optimization of 3d meshes in implicit domains. // Proc. II International conference "Optimization and applications"(OPTIMA-2011). - Moscow: Computing Center RAS, 2011. - P. 86-89.

97. Garanzha V.A., Kudriavtseva L.N. Preconditioned iterative algorithms for variational hexahedral meshing and mesh untangling in implicit domains. // Abstracts of 3rd International Conference on Matrix Methods in Mathematics and Applications, MMMA-2011. - Moscow: INM RAS, 2011. - P. 22.

98. Garanzha V.A., Kudryavtseva L.N., Utyzhnikov S.V. Untangling and

optimization of spatial meshes // Journal of Computational and Applied Mathematics. - 2014. - October. - V. 269 - P. 24-41.