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

На правах рукописи

ФРЯЗИНОВ ОЛЕГ ВЯЧЕСЛАВОВИЧ

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2004

Работа выполнена в МГТУ «Станкин» на кафедре «Когнитивные Технологии Проектирования»

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

ст. науч.сотр. ЕЛ.Карташева.

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

профессор Уварова Л.А.

кандидат физико-математических наук, ст. науч.сотр. Марченко М.П.

Ведущая организация: Институт Проблем Межаники

Российской Академии Наук

Защита диссертации состоится « 23 » декабря 2004 г. в «_» часов на заседании диссертационного совета Д 212.142.03 при Московском государственном технологическом университете «СТАНКИН» по адресу: 101472, ГСП, г. Москва, Вадковский пер., 1..

С диссертацией можно ознакомиться в библиотеке МГТУ «СТАНКИН».

Автореферат разослан " 22 " ноября 2004 г.

Ученый секретарь

диссертационного Совета Д 212.142.03 к.т.н., доц.

Семячкова Е.Г.

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

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

БИБЛИОТЕКА

¿ЧЕЙ»

ние неявно заданных моделей долгое время сдерживалось высокой трудоемкостью получения дискретного описания поверхностей неявно заданных моделей и сложностью их визуализации. Однако быстрое развитие компьютерной техники, обеспечивает сегодня возможность манипулирования неявно заданными моделями со скоростями, приемлемыми для интекрактивного проектирования. Поэтому последнее время в компьютерном моделировании интерес к неявно заданным моделям неуклонно возрастает. Указанные модели обеспечивают компактное и интуитивно понятное представление сложных объектов, поддерживают теоретико-множественные операции, и позволяют также выполнять такие операции, как сглаживание, пространственная деформация, конволюция и другие. Для практического применения неявно заданных моделей в таких приложениях, как конечно-элементное и конечно-разностное моделирование (FEA/FDA), автоматизированное проектирование, инженерный анализ и подготовка производства (CAD/CAM/CAE) необходимо гарантировать выполнение для этих моделей различных вычислительных процедур, которые основаны на использовании дискретных моделей или сеток. Во многих приложениях, связанных с численным моделированием (CAD/CAE/CAM, вычислительная физика, математическое моделирование, вычислительная геометрия и топология и т.д.) требуется учет внутренней структуры рассматриваемых геометрических объектов. Однако до сих пор в связи с широким распространением явных моделей алгоритмы генерации сеток были ориентированы в основном на граничные модели и модели пространственного перечисления, основанные на явном описании. Методы дискретизации неявно заданных объектов в настоящее время активно развиваются в визуализации и обработке изображений. Однако требования, которые предъявляются к дискретным моделям в численном моделировании жестче, чем в других приложениях. Это связано с тем, что в численном моделировании сетки являются основой для аппроксимации систем уравнений математической физики, описывающих сложные процессы и явления. При этом размеры и форма элементов, а также сама структура сетки оказывают серьезное влияние на устойчивость процедур численного моделирования и точность получаемых решений. Поэтому зачастую сетки, используемые для визуализации геометрических объектов, оказываются неприемлемыми для конечно-элементного и конечно-разностного анализа. В связи с этим представляется актуальной задача построения дискретных моделей неявно заданных объектов, которые отвечают требованиям конечно-элементного моделирования. Еще одной важной современной тенденцией в компьютерной геометрии и графики является возрастание интереса к неоднородным моделям, которые наряду с гео-

метрическими и топологическими данными содержат информацию о других свойствах объектов, например, материале, цвете, характеристиках среды и др. Задание негеометрических свойств играет важную роль в конечно-элементном моделировании (FEA/FDA) и автоматизированном проектировании (CAD/CAM/CAE), поэтому в данной работе задача дискретизации решается с учетом неоднородности свойств моделируемых геометрических объектов. Задача построения дискретных моделей и задача дискретизации с учетом неоднородности свойств определили необходимость разработки методов представления и дискретизации неявно заданных неоднородных геометрических объектов. Это позволило сформулировать цель работы и поставить научную задачу.

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

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

• исследования существующих методов представления и дискретизации неоднородных геометрических объектов;

• разработки методов представления неоднородных геометрических объектов, основанных на применении неявно заданных моделей;

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

• разработки методики дискретизации неявно заданных неоднородных геометрических объектов;

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

Научная новизна:

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

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

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

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

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

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

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

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

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

Разработанные программные средства применяются для построения расчетных сеток при решении задач многофазовой газовой динамики и магнитной гидродинамики в Институте Математического Моделирования РАН. Средства оптимизации поверхностных сеток применяются для качественной полигониза-ции неявно заданных объектов в международном проекте Hyperfim (www.hvperfun. org). целью которого является развитие геометрических моделей, основанных на функциональном представлении. Разработанные средства генерации объемных сеток были использованы в совместном российско-корейском предприятии RUCORERC при подготовке данных для проведения

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

Апробация работы. Результаты диссертации докладывались на:

• VIII Международном симпозиуме по твердотельному моделированию и приложениям ACM Solid Modeling and Applications, г. Сиэтл, США в июне 2003 г.

• XXX Звенигородской конференции по физике плазмы и УТС, г. Звенигород Московской обл., февраль 2003 г.

• торгово-промышленных выставках «Информационные технологии в промышленности» Ганновер, Германия, апрель 2001г., апрель 2002г.

• IV Международной конференции по математическому моделированию МГТУ «Станкин» Москва 2001.

Результаты работы использовались в ходе проведения курсовых и лабораторных работ по дисциплинам «Системы машинной графики и геометрического моделирования» и «Моделирование и алгоритмизация в САПР» для специальностей факультета «Информационных технологий» и обсуждались на заседании кафедры «Когнитивные технологии проектирования» и кафедры Прикладной математики МГТУ «СТАНКИН»

Публикации. По теме диссертации опубликовано 5 работ, список которых содержится в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (80 наименований) и приложений. Работа содержит 204 страницы сквозной нумерации, включая 43 рисунка и 32 страницы приложений.

Основное содержание работы

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

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

В твердотельном моделировании в настоящее время особое внимание уделяется моделированию гетерогенных объектов с множеством атрибутов и их неоднородным внутренним распределением. Для представления таких объектов используются разные подходы: граничное представление, функциональное представление, вексельные и сеточные модели, рассмотренные в работах таких отечественных и зарубежных ученых, как А. А. Пасько, В. П. Аджиев, В. Ю. Суцзиловский, Л.В. Баранов, Ю.М. Баяковский, СИ. Ротков, В. Кумар, Я. Рос-синьяк, В. Шапиро, М. Чен, К. Шин и др. Так, граничное представление гетерогенных объектов предполагает их разбиение на компоненты, однородные по негеометрическим свойствам. Вексельные массивы в объемном моделировании и графике могут быть рассмотрены как модели дискретных атрибутов с геометрией, по умолчанию представленной ограничивающим параллелепипедом. Конструктивная твердотельная геометрия использует вексельные массивы и непрерывные скалярные поля для представления одновременно геометрии и фотометрических атрибутов (прозрачность, цвет и т.д.). Функциональное представление использовалось для моделирования неоднородных геометрических объектов как многомерных наборов точек с множеством атрибутов.

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

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

поверхность и обеспечить для нее выполнение требований конечно-элементного анализа. Далее с учетом указанных ограничений необходимо построить объемную сетку, согласованную с уже построенной поверхностной дискретизацией. Подробный обзор методов дискретизации дается в книге ПФрэя и П.-Л. Джорджа, описание различных алгоритмов генерации симплициальных сеток приводится в работах Р. Ленера, В.А. Гаранжи, В.Ф. Тишкина и др.

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

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

Во второй главе в рамках разработанной гибридной геометрической модели дается формализованная постановка задачи построения конечно-элементных сеток в неявно заданных объектах с учетом их негеометрических свойств.

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

Как известно, функциональное представление (F-rep) определяет геометрический объект в л-мерном Евклидовом п р о с е Р:Еп —>91 вещественная функция векторного аргумента X еЕп, обладающая как минимум свойством С0 -непрерывности. F-rep обеспечивает широкие возможности для неявного описания многомерных пространственных объектов. Применение аппарата R-функций делает функциональное представление замк-

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

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

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

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

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

Под неоднородным геометрическим объектом Б понимается подмножество О евклидова пространства Е3, вместе с заданными на нем атрибутами Аь так что - общее количество атрибутов.

Геометрия объекта О может задаваться либо функциональным представлением вида: либо клеточным представлени-

ем обозначает тело комплекса Мы

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

значений Л^, в многомерном пространстве Л"", соответствующей размерности пи (Я - множество действительных чисел). Интерпретация значений элементов множества с: Я.'"' индивидуальна для каждого атрибута Л,-. Конкретные значения атрибута А{ присваиваются точкам Xпространства Ё* путем задания некоторого отображения При этом считается, что каждый из

атрибутов определен на всем пространстве независимо от других атрибутов и геометрических объектов. Для того чтобы можно было распространить на все пространство моделирования определение тех атрибутов, которые заданы только на точках конкретного геометрического объекта, мы дополняем все пространства В.т' соответствующими нейтральными элементами 0т!. Таким образом, множество значений атрибута Л,- принадлежит расширенному пространству Поскольку множества значений атрибутов принадлежат

математическим пространствам

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

соответствующего пространства и определяет трактовку числовых зна-

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

По аналогии с геометрическим объектом для задания атрибутов используется функциональное описание и описание на основе комплексов, а также смешанное клеточно-функциональное представление. Разные модели атрибутов различаются способом задания отображения «УДЛТ). Функциональное представление атрибута соответствует самому общему заданию в ви-

де функции координат точек пространства Е*. Клеточно-функциональная модель атрибута A¡ предполагает, что отбражение S¡ задается в виде совокупности локальных отображений {¿'¡у}, где каждое отображение Sg есть ограничение S¡ на множество точек соответствующего элемента Cj некоторого комплекса К. Для реализации клеточно-функциональной модели атрибутов вводится понятие нагруженного комплекса, т.е. комплекса, с элементами которого ассоциированы некоторые дополнительные негеометрические данные. Наконец, в клеточной модели атрибута значения которого принадлежат множеству

соответствующее ему задает отображение некоторого комплекса

в комплекс расположенный в евклидовом пространстве раз-

мерности n=3 + mi. При этом структура и размерность комплекса Wполно-стью совпадают со структурой и размерностью комплекса К.

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

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

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

Задан неоднородный объект в котором геометрия

описана неявно с помощью функционального представления

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

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

рибуты дискретного объекта по количеству, способам описания и

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

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

так что

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

5 = (6с,Аь...,Ат).

Граница неявно заданного тела представляет собой неявную поверхность В, описываемую моделью Вр ={Х\Х = ,Р(Х) = 0}. В

общей дискретизации разбиению поверхности Вс соответствует

полиэдральный комплексом который является граничным подкомплексом

К3, 1}<=.Кг, так что Вс={Х\Хе£1яЕ ,Х41?\}. Поскольку атрибуты задаются независимо в пространстве моделирования, то они могут применяться одновременно для описания свойств и всего объемного элемента, и отдельных его частей. Таким образом предложенная геометрическая модель неоднородных объектов обеспечивает единое описание тела и его граничной поверхности как в неявном функциональном, так и в дискретном представлениях. При этом граница неоднородного телу Л и его дискретного аналога О описываются соответственно неоднородной функционально заданной поверхностью и неоднородной клеточной поверхностью В соответствии с требованиями конечно-элементного анализа дискретная модель должна удовлетворять следующим условиям:

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

от нормалей к исходной неявной поверхности В.

2. В комплексах Къ и I? на форму элементов, их размер, а также и на соотношение размеров соседних элементов накладываются ограничения в виде

различные количественные оценки,

основанные на метрических характеристиках элементов, таких, например, как длина наибольшей стороны, или объем (площадь), или радиус описанной сферы (окружности) и т.д., а Е,3 - некоторые константы.

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

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

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

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

ровать соответствующую объемную сетку и атри-

буты А] =А]{<Э¥,(}с,Ах,...,Ак), ./ = 1,..т.

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

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

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

В целом методы полигонизации с учетом восстановления острых углов и ребер обеспечивают построение сетки =1%(Вр), задающей клеточную модель 2?с0, которая удовлетворяет первой группе перечисленных выше ограничений. Данная дискретная модель используется как исходное приближение для построения конечно-элементной дискретизации. Процедура конечно-элементной адаптации включает два основных этапа. Цель первого этапа - получить поверхностную сетку, удовлетворяющую ограничениям на форму элементов, которая обеспечивает качественную аппроксимации геометрии объекта, и имеет при этом по возможности минимальное количество элементов. Цель второго этапа - адаптировать поверхностную сетку к требованиям конечно-элементного анализа и к атрибутам, зависящим от прикладной задачи. На первом этапе строится сетка удовлетворяющая ограничениям второй группы. Затем формируется сетка Ь\ которая отвечает требованиям третьей группы перечисленных выше ограничений.

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

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

Для сеточных ребер е, функция 8к(е) задается в виде:

5Л(е) = |1> если

. о. *

(1+(пУ)-п(12)Ь

<<ртл

1+(МТ(11)-К(12)) 2

<<р

2

в противном случае

Здесь и(<1),л(<2) - единичные нормали к соседним треугольникам ¡1,£2, для которых е - общее ребро. N(¿2) - нормали к исходной поверхности в

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

Для сеточных узлов Р в работе вводятся три функция остроты. Первая функция 5Л/0 позволяет выделять узлы, лежащие на острых ребрах. Эта функция определяется следующим образом: где суммирование

проводится по всем ребрам с,, инцидентным вершине Р. Если 8Н1(Р)=2, то вершина Рлежит на остром ребре, в случае, когда £й/(Ту>2, мы имеем дело с угловой точкой.

Чтобы выявить те острые выступы, которые не лежат на острых ребрах, используется вторая функция остроты

В данном случае при поиске минимумов рассматриваются все треугольники ti, инцидентные вершине Р. Здесь n(tf) - единичные нормали треугольников tj, N(t,) - нормали к поверхности в центрах масс треугольников tt, т =[л<о x/i/i] - вектор нормали к плоскости, построенной по двум нормалям Hio,niкоторым соответствует наибольший угол среди всех пар нормалей к треугольникам tj, инцидентным вершине Р, вектор М = [N(t0) х Af(il)] вычисляется аналогично, но на основе нормалей к поверхности, а г - пороговое значение. Наконец, общая функция остроты узла определяется как

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

Геометрические методы перестройки сетки включают две операции: проецирование узлов сетки на аппроксимируемую неявную поверхность и сглажи-

J

Sh(P) = max (SA, (Р), Sh2 (Р))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1 Пример дискретизации неявно заданного объемного тела. а) - исходная полигонизация поверхности b) - результат оптимизации поверхностной сетки с) - фрагмент объемной сетки

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

Программные средства разработаны на базе объектно-ориентированного подхода и предназначены для использования в ОС Windows,. В качестве

средств реализации выбран язык C++ в среде Microsoft Visual C++. Программная реализация включает в себя разработку:

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

• программных модулей, обеспечивающих выполнение описанных выше алгоритмов перестройки и оптимизации сеток;

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

Основу объектно-ориентированной реализации структур данных составляют классы CGrid3D, CRelation и CFrep. Класс CGrid3D служит для описания трехмерных полиэдральных комплексов. Класс CGric3D содержит информацию о топологии и геометрии комплекса. Каждый комплекс представляет собой множество элементов и множество отношений между этими элементами. Множество элементов трехмерного комплекса включает множество узлов, ребер и граней. Эти множества - пронумерованные, нумерация начинается с нуля и поддерживается в процессе выполнения всех операций над комплексом. Геометрия комплекса задается координатами узлов и зависит от связей между элементами. Порядковый номер элемента является его идентификатором внутри комплекса и используется при описании отношений. Топология комплекса задается набором из 6 отношений инцидентности и 6 отношений смежности. Каждое отношение описывается объектом класса CRelation, который содержит пары номеров элементов, связанных данным отношением. Операции класса CRelation позволяют по заданному номеру получать номера всех связанных элементов, а также добавлять и удалять пары номеров. Соответственно в классе CGrid3D есть функции для добавления и удаления элементов, модификации хранимых отношений и получения информации о связях. В классе CRelation реализованы также операции над отношениями: композиция двух отношений и построение отношения, обратного данному. При разработке данных классов CRelation и CGrid3D учитывались два основных фактора - это разнообразие отношений заданных на комплексе и большие размеры множеств, на которых определены отношения. Поэтому в классе CGricBD постоянно хранятся только основные отношения, остальные вычисляются динамически на базе основных с использованием операций композиции и вычисления обратного отношения.

Описание функциональных представлений строится на базе абстрактного класса CFrep<xdim> параметризованного по размерности пространства. Класс CFrep<xdim> имеет виртуальный метод getValue() для вычисления значения функции в точке. От шаблона CFrep<xdim> наследуются классы, описывающие

конкретные функционально заданные примитивы и операции. Разработанный программный комплекс включает библиотеку функций, описывающих основные объемные примитивы, а также теретико-множественные операции и аффинные преобразования. Набор йгер примитивов легко расширяется, для создания нового примитива достаточно создать новый объект, унаследованный от Сйгер<хШт>, описав соответствующую реализацию виртуального метода get-Уа1иеО. Описание атрибутов также строится на основе классов СОМЗБ, СЯе1а-tion и Сйгер. При этом функциональная и клеточная модели атрибутов задаются экземплярами классов Сйгер, СОпёЗБ, соответственно, а для описания клеточ-но-функциональной модели атрибутов необходимо задать экземпляр класса CGrid3D, множество значений атрибута, ассоциированных с элементами комплекса, и экземпляр класса СЯеМюп, описывающего ассоциации значений атрибутов с номерами соответствующих элементов комплекса.

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

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

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

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

Средства оптимизации поверхностных сеток применяются для качественной полигонизации неявно заданных объектов в международном проекте Hyperfun (www hvpeTfun.org).

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

Рис.2 Пример конечно-элементной сетки на поверхности неявно заданной модели миксера, используемого в химическом реакторе а) - Полигонизация неявной поверхности с острыми ребрами Ь) - Оптимизация сетки с целью удовлетворения требований конечно-элементного анализа к форме элементов; с) - Адаптация к атрибуту.

В заключении представлены краткие выводы по теме диссертации, а также показаны основные направления перспективных исследований по предложенной теме.

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

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

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

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

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

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

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

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

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

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

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

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

Список работ, опубликованных по теме диссертации

1. E.Kartasheva, VAdzhiev, A. Pasko, О. Fryazinov, V. Gasilov Surface and Volume Discretization of Functional based Heterogeneous Objects Journal of Computing and Information Science in Engineering, Transactions of the ASME, 2003, Vol. 3, No. 4, pp. 285-294.

2. E.Kartasheva, VAdzhiev, A. Pasko, O. Fryazinov, V. Gasilov Discretization of Functionally-based Heterogeneous Objects Proc. 8th ACM Symposium on Solid Modeling and Applications, G. Elber and V. Shapiro (Eds.), Seattle, USA, ACM Press, 2003, pp. 145-156.

3. Гасилов В.А.,Карагичев А.Б., Карташева Е.Л.,Кутанова А.В., Тарасов Д.С., Фрязинов О.В. Интерактивная система генерации тетраэдральных сеток ITERA. В сборнике трудов «Четвертая международная конференция по математическому моделированию» М.: MEIY «Станкин» 2001. Т.2. 84-91с

4. В.А.Гасилов, А.С.Чуватин, АЮ.Круковский, Е.Л. Карташева, О.Г.Ольховская, А.С.Болдарев, Д.С.Тарасов, Н.В.Серова, СВ. Дьяченко, О.В.Фрязинов Комплекс программ РАЗРЯД: Моделирование ускорения плазмы в сильноточных импульсных системах. - Математическое Моделирование, 2003, Т.15, No. 9, стр.107-124

5. В .А. Гасилов, А.С. Чуватин, А.Ю. Круковский, Е.Л. Карташева, О.Г. Ольховская, А.С. Болдарев, Д.С. Тарасов, Н.В. Серова, С.В. Дьяченко, О.В. Фрязинов. Исследование сжатия магнитного потока плазменным лайнером. - В сб. "Тезисы докладов XXX Звенигородской конференции по физике плазмы и УТС г.3венигород, 24-28 февраля 2003". Москва, Науч. Совет РАН по физике плазмы, 2003, стр. 132

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Фрязинов Олег Вячеславович

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

Лицензия на издательскую деятельность ЛР №01741 от 11.05.2000 Подписано в печать 17.11.2004. Формат 60x90'/« Уч.изд. л. 1,5. Тираж 50 экз. Заказ № 219

Отпечатано в Издательском Центре МГТУ «СТАНКИН» 103055, Москва, Вадковский пер., д.3а

Введение.

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

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

1.2.Анализ методов описания неоднородных геометрических объектов.

1.3. Анализ методов построения сеток.

1.3.1. Общий обзор методов генерации сеток.

1.3.2. Анализ методов дискретизации неявно заданных геометрических объектов.

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

2. Формализация задачи построения конечно-элементных сеток в неявно заданных неоднородных объектах.

2.1 Функциональное представление геометрических объектов.

2.2 Дискретные геометрические модели.

2.3 Гибридная неоднородная геометрическая модель.

2.4 Формальное описание постановки задачи дискретизации неоднородного объекта, представленного гибридной геометрической моделью.

3. Методы поверхностной и объемной дискретизации неявно заданных неоднородных геометрических объектов.

3.1 Дискретизация граничной поверхности.

3.1.1 Генерация полигонального приближения граничной поверхности.

3.1.2. Восстановление поверхностных особенностей.

3.1.3. Улучшение и упрощение сетки на поверхности.

3.1.4 Адаптация поверхностной сетки.

3.2 Построение объемной сетки.

3.2.1 Генерация тетраэдральной сетки.

3.2.2 Оптимизация объемной сетки.

3.2.3 Преобразование атрибутов.

3.3. Процедуры оптимизация поверхностной сетки.

3.3.1 Функция остроты.

3.3.2 Операции перестройки сетки.

3.4 Процедуры генерации объемной сетки.

3.4.1. Модифицированный алгоритм фронтальной тетраэдризации.

3.4.2. Процедуры оптимизации объемной сетки.

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

4.1 Структуры данных.

4.1.1 Реализация отношений, заданных на множествах элементов комплекса.

4.1.2 Реализация модели трехмерного полиэдрального комплекса.

4.1.3 Реализация функционального представления.

4.1.4 Реализация моделей атрибутов.

4.1.5 Реализация гибридной модели.

4.2 Алгоритмы оптимизации поверхностных сеток.

4.2.1 Алгоритмы выполнения базовых операций перестройки сеток.

4.2.2 Алгоритмы основных операций оптимизации.

4.3 Интерактивные средства оптимизации поверхностных сеток.

4.4 Инструментальные средства для визуализации и динамического анализа неоднородных сеточных моделей.

4.5 Инструментальные средства создания объемных сеток.

4.6 Примеры использования программного комплекса.

4.6.1 Тетраэдризация твердого тела, заданного с помощью функционального представления.

4.6.2 Дискретизация неоднородного объекта с различными атрибутами

4.6.3 Моделирование миксера, используемого в химическом реакторе.

4.6.4 Оптимизация поверхностных сеток, импортированных из CAD системы.

В настоящее время математическое моделирование: широко применяется в различных областях науки и техники [1,2]. Математические модели ? дают формализованное представление исследуемых процессов и явлений, что открывает возможность использования аналитических и численных методов для решения практических задач- [1]. Неотъемлемой частью математического моделирования является геометрическое моделирование. Геометрические модели активно используются в приложениях, которые непосредственно связаны с решением различных геометрических задач: автоматизированное проектирование, компьютерный дизайн, анимация. Однако;нередко они является составной частью решения более общей математической задачи. Так, при изучении физических, химических, биологических и других процессов и явлений возникает необходимость исследования уравнений в частных производных, определенных в сложных пространственных областях. Для решения указанных уравнений используются обычно численные методы [3], в которых требуетсяv пространственная дискретизация, то- есть расчетная область должна быть представлена в виде, как правило, конечной совокупности достаточно простых геометрических объектов. Такая совокупность объектов, задающая разбиение пространственного; объекта, называется сеткой.

В силу сложности формализации представления пространственных объектов; не существует универсальных геометрических моделей. На сегодняшний день известны разные способы описания геометрии, каждый из которых имеет свои преимущества и недостатки [4]. В целом можно выделить два основных типа геометрических моделей. Это явные и неявно заданные модели [5]. В явных моделях обычно используются параметрические представления кривых и поверхностей. Исторически явные модели получили более широкое применение в системах автоматизированного проектирования и компьютерной графике. Это связано с относительной* простотой: численной обработки и визуализации явных моделей. Однако: при задании; сложных форм; с помощью? явных параметрических описаний приходится использовать составные поверхности и кривые, состоящие * из большого числа; сегментов. Это усложняет процесс задания- и модификации геометрических моделей и приводит к возникновению большого количества ошибок. В" работах [6, 7] отмечаются основные недостатки полиномиальных и рациональных параметрических представлений; Они- связаны в первую очередь с неоднозначностью параметрического описания и; со» сложностями, которые возникают при; вычислении пересечений; Для обеспечения гладкого сопряжения кривых и поверхностей- в автоматизированном проектировании приходится использовать параметрические: функции высоких порядков: При этом, как известно [7], порядок алгебраической, поверхности; которая соответствует параметрическому описанию с координатными функциями порядка л, равен

7 7

2п или п . Порядок алгебраической поверхности определяет максимальное число возможных точек; пересечения прямой с этой поверхностью: Таким; образом, порядок поверхностей напрямую влияет на численную устойчивость, надежность ш точность процедур' вычисления пересечений. При использовании параметрических описаний порядок применяемых поверхностей искусственно завышается; что снижает точность ненадежность, вычислительных процедур. Кроме того; при: выполнении различных операций; над объектами, заданными явными моделями; возникает необходимость- дополнительного i дробления; составных поверхностей и; кривых, что в целом усложняет модель, ш может привести; к снижению» точности ее представления. Вычислительные погрешности могут приводить к несоответствию геометрического и топологического представления; объекта, что делает модель- объекта некорректной. Неоднозначность параметрического описания; кривых и поверхностей* и основанного на их использовании граничного представления объемных тел усложняет интерпретацию описаний моделей, импортируемых из других систем;. Поэтому, несмотря на разработку универсальных форматов [8], не удается обеспечить надежный обмен данными между различными системами; геометрического моделирования и. автоматизированного проектирования. В работах [9, 10] отмечается, что перечисленных недостатков лишен подход, основанный на неявном представлении поверхностей: Анализ возможностей применения неявных алгебраических поверхностей второго и? третьего порядка при проектировании объектов сложной формы приводится в работах [10, 11]. Основные проблемы практического применения! алгебраических поверхностей5 связаны, со сложностью выбора интуитивно: понятных механизмов управления их формой, аналогичных по простоте, аппарату контрольных точек, используемому в»В-сплайнах и; кривых Безье. С другой! стороны,, важным; преимуществом; неявных моделей является: возможность единого описания объемных тел и ограничивающих их поверхностей,, которое достигается, например,' при использовании функционального представления[ 12] . Такое представление замкнуто относительно теоретико-множественных операций; и обеспечивает корректность математического представления сложных объемных тел, получаемых в процессе автоматизированного конструирования. Неявные поверхности; которые описываются» неполиномиальными' функциями, как правило, не имеют аналогичных параметрических представлений, поэтому применение неявных моделей может открыть принципиально новые возможности; в проектировании и дизайне.

Широкое: распространение неявно заданных моделей долгое время, сдерживалось, высокой трудоемкостью' получения дискретного описания поверхностей неявно заданных тел: и, как следствие, сложностью их: визуализации и численного анализа; Однако быстрое развитие компьютерной техники, обеспечивает сегодня возможность манипулирования! неявно заданными моделями со скоростями, приемлемыми для интерактивного проектирования. Поэтому последнее время в компьютерном моделировании интерес к неявно заданным моделям» неуклонно» возрастает. Указанные модели; обеспечивают компактное- и интуитивно понятное представление сложных объектов, поддерживают теоретико-множественные операции, и позволяют также выполнять такие операции, как сглаживание, пространственная деформация, конволюция и другие.

Однако для практического/ применения неявно» заданных моделей в таких приложениях, как конечно-элементное и конечно-разностное моделирование (FEA/FDA) [13, 14] автоматизированное проектирование, инженерный* анализ и подготовка производства (CAD/CAM/CAE) [15] необходимо гарантировать выполнение для этих моделей различных вычислительных процедур, которые основаны на использовании дискретных моделей или сеток. Во- многих приложениях, связанных с численным моделированием; (CAD/CAE/CAM, вычислительная! физика, математическое моделирование, вычислительная геометрия и топология и т.д.) требуется учет внутренней- структуры рассматриваемых геометрических объектов. Однако до сих пор в связи с широким: распространением явных моделей алгоритмы генерации? сеток были ориентированы; в основном на граничные модели и модели; пространственного перечисления, основанные на явном описании. Методы дискретизации неявно? заданных, объектов в настоящее время; активно г развиваются? в визуализации и обработке изображений. Однако требования;, которые предъявляются к дискретным моделям в численном моделировании жестче,, чем в других приложениях; Это связано с тем, что в; численном моделировании сетки являются- основой для аппроксимации; систем уравнений математической физики, описывающих сложные процессы и явления. При этом размеры и форма элементов, а также сама структура сетки оказывают серьезное влияние на устойчивость процедур! численного моделирования и точность получаемых решений. Поэтому зачастую сетки, используемые для: визуализации > геометрических объектов, оказываются неприемлемыми* для конечно-элементного- и конечноразностного анализа. В связи с. этим представляется актуальной задача построения дискретных моделей неявно заданных объектов, которые отвечают требованиям конечно-элементного моделирования.

Еще одной; важной современной тенденцией: в компьютерной' геометрии, и графике является; возрастание интереса к неоднородным моделям; которые наряду- с геометрическими и топологическими данными содержат информацию о других свойствах объектов, например, материале, цвете, характеристиках среды и так далее. Задание негеометрических свойств играет важную роль в конечно-элементном моделировании (FEA/FDA) и; автоматизированном проектировании (CAD/GAM/GAE), поэтому в данной: работе; задача дискретизации решается* с учетомнеоднородности- свойств; моделируемых геометрических объектов.

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

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

Заключение

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

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

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

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

4. Разработаны алгоритмы оптимизации и адаптации дискретных моделей; неявно заданных геометрических объектов с учетом особенностей их граничных поверхностей; а также с учетом значений? и характера распределения: их негеометрических атрибутов. Указанные алгоритмы обеспечивают построение адаптивных конечно-элементных сеток на; неявных поверхностях.

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

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

7. Разработаны программные средства, реализации? предложенных, алгоритмов оптимизации дискретных моделей1 неявно* заданных неоднородных геометрических объектов.

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

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

10.Разработанные программные средства* применяются для построения расчетных сеток при решении задач многофазовой газовой динамики и * магнитной^ гидродинамики в Институте Математического Моделирования РАН: Средства оптимизации поверхностных сеток используются для качественной? полигонизации неявно заданных объектов в международном проекте Hyperfun (www.hyperfun.org). Разработанные средства генерации объемных сеток были использованы в совместном российско-корейском; предприятии RUCORERC при подготовке данных для проведения инженерного анализа гидродинамики и тепло-массопереноса в химических реакторах с вынужденным перемешиванием.

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

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

1. E.Kartasheva, V.Adzhiev, A. Pasko,- О. Fryazinov, V. Gasilov Surface and Volume Discretization of Functional based Heterogeneous Objects Journal of Computing and Information Science in Engineering; Transactions of the ASME, 2003vVoL 3, No. 4, pp. 285-294.

2. E.Kartasheva, V.Adzhiev , A. Pasko, O. Fryazinov, V. Gasilov Discretization of Functionally-based* Heterogeneous Objects. Proc. 8th ACM Symposium».on Solid Modeling and Applications,, G. Elber and V. Shapiro (Eds.), Seattle, USA, ACM Press, 2003, pp. 145-156.

31 Гасилов В1А.,Карагичев А.Б., Карташева Е.Л.,Кутанова А.В., Тарасов Д.С., Фрязинов О.В1 Интерактивная система генерации тетраэдральных сеток ITERA; В сборнике трудов «Четвертая международная конференция по математическому моделированию» М: МГТУ «Станкин» 2001. Т.2. 84-91с

4. В.А.Гасилов, А.С.Чуватин, А.Ю.Круковский, E.JI. Карташева, О.Г.Ольховская, А.С.Болдарев, Д.С.Тарасов, Н.В.Серова, С.В. Дьяченко, О.В.Фрязинов Комплекс программ РАЗРЯД: Моделирование ускорения плазмы в сильноточных импульсных системах. - Математическое Моделирование, 2003, Т. 15, No. 9, стр. 107-124

5. В.А. Гасилов, А.С. Чуватин, А.Ю. Круковский, E.JI. Карташева, О.Г. Ольховская, А.С. Болдарев, Д.С. Тарасов, Н.В. Серова, С.В. Дьяченко, О.В. Фрязинов. Исследование сжатия магнитного потока плазменным лайнером. - В сб. "Тезисы докладов XXX Звенигородской конференции по физике плазмы и УТС г.Звенигород, 24-28 февраля 2003". Москва, Науч. Совет РАН по физике плазмы, 2003, стр. 132

1. Самарский А.А., Михайлов А.П. Математическое моделирование. М.: Наука, Физматлит, 1997, 205с.

2. Математическое моделирование: Проблемы и результаты,-М. Наука, 2003

3. Федоренко Р.П. Введение в вычислительную физику. М.: МФТИ. 1994. 528с

4. Foley J, A.van Dam, S.Feiner, J.Hughes, R.Philips Introduction to Computer Graphics, Addison Wesley, 1994

5. А.Фокс, M. Пратт Вычислительная геометрия: Пер.с англ.-М.: Мир, 1982.

6. Pratt M.J., Geisow A.D. Surface/surface intersection problems. In The Mathematics of Surfaces ed. By Gregory J.A., Oxford University Press, 1986

7. Owen J. STEP: En introduction. Information Geometers, Winchester, UK, 1993

8. Bloomenthal J. et al.: Introduction to Implicit Surfaces. Morgan Kaufmann, 1997.

9. Pasko A., Adzhiev V., Sourin A., Savchenko V. Function representation in. geometric modeling: concepts, implementation and applications, The Visual Computer, vol.11, N 8, 1995, pp. 429-446.

10. Зенкевич О., Морган К. Конечные элементы и аппроксимация М.: Мир 1986,318с

11. Н.Сабоннадьер Ж.-К.,. Кулон Ж.-Л. Метод конечных элементов и САПР:Пер.с франц.-М; :Мир, 1989.

12. Гардан И:, Люка М. Машинная графика и автоматизация конструирования; Пер. с фр.-М.,Мир,1987

13. Ефимов Н; В., Высшая геометрия, 4 изд., М., 196117.3ейфертГ.,Трельфалль В; Топология, ГОНТИ, 193818;Mortenson М, Geometric Modeling, Wiley, New York, 198519;Ходж В., Пидо Д., Методы алгебраической геометрии, пер. с англ., т. 1-3,М., 1954- 55;

14. Понтрягин Л.С. Основы комбинаторной топологии, М., Наука, 1986

15. Requicha A.A.G. Representstion for Rigid Solid: Theory, Methods and5 Systems. // Computing Surveys, 1980, V2, № 14, p. 437-464.

16. Химушин Ф.Ф.Обзор методов геометрического моделирования для; САПР.- В сб. Программное обеспечение САПР, ВЦ АН СССР, М., 1987, с.78-101

17. Mantylia М. Introduction to- Solid Modeling, Computer Science Press, Rockville; MD, 1988;

18. Химушин Ф.Ф. Конструктивное геометрическоемоделирование.-В сб. Программное обеспечение САПР.ВЦАНСССР,М., 1987, с.102-121

19. ЧельцовА.Ю., ДавыдченкоЭ.А. Представление данных ш алгоритмы для системы геометрического моделирования, основанной на заметании.- В сб. Программное обеспечение САПР, ВЦ АН СССР.,М:, 1987, с. 121-133.

20. Samet Н.,Webber R.E.Hierarchical; data structures and; algorithms for computer graphics. IEEE Comput.Graph & Appl., 1988,V 8,N 4,p.59-75.

21. Соллогуб А.И., Валыдин, А.Т. Система трехмерного геометрического моделирования пространственных тел с использованием характеристических и R-функций.,Программирование, 1991, N3,c.86-96'

22. Shapiro V., Tsukanov, I. Implicit functions with' guaranteed; differential properties, Proceedings; of the Fifth ACM Symposium on<■ Solid Modeling and Applications, ACM, 1999, 258-269.

23. Kobbelt, L., Botsch, M., Schwanecke, U., Seidel; H.-P. Feature sensitive surface extraction from volume data, Computer Graphics (Proceedings of SIGGRAPH 2001), 57-66.

24. Рвачев JI. Методы логической алгебры в математической физике. Наукова думка; Киев, 1974г.

25. Пасько А.А., Пилюгин В.В., Покровский В.Н. Геометрическое моделирование в задаче анализа функций трех переменных, Сообщение ОИЯИ Р10-86-310, Дубна, 1986. Publication in English: Computers and Graphics, vol.12, # # 3/4, 1988, pp. 457-465.

26. Whitehead J.H.C. Combinatorial homotopy, I, Bull. Amer. Math. Soc., 55(1949), 213-245.35;Александров П.С. Комбинаторная топология., ОГИЗ, Гостехиздат, 1947

27. Fritsch F, Piccinini RA. Cellular structures in topology. Cambridge University Press, Cambridge, 1990

28. Fomenko, A.T., Kunii, T.L. Topological modeling for visualization, Springer-Verlag, Tokyo and Heidelbrg, 1997

29. Rossignac J., O'Connor M. SGC: A dimension independent model5 for pointsets with internal structures and incomplete boundaries. In Geometricmodeling for product engineering, ed. by M: Wozny, J. Turner, K. Preiss, 1990.

30. Armstrong C., Bowyer A., Cameron S. et all: Djinn. A Geometric interface for solid modeling. Information Geometers, Winchester, UK, 2000.

31. Карташева ЕЛ. Инструментальные средства подготовки и анализа данных для решения трехмерных задач математической физики -Математическое моделирование. 1997. Т. 9. №6. G. 20.

32. Kumar V., Burns D., Dutta D., Hoffmann C.: A framework for object modeling. Computer-Aided Design 31, 9, (1999), 541-556.

33. Cutler В., Dorsey J., McMillan L., Mueller M., Jagnow R.: A procedural approach to authoring solid models. In Proc. SIGGRAPH'02, ACM TOG 21, 3(2002), 302-311.

34. Park S. M., Crawford R., Beaman J.: Volumetric multi-texturing for functionally gradient material- representation. In Proc. Sixth ACM Symposium on, Solid Modeling and! Applications, D. Anderson, K. Lee (Eds.), ACM Press, 2001, 216-224.

35. Siu Y.K., Tan S.T.: "Source-based" heterogeneous solid modeling. Computer-Aided Design 34, (2002), 41-55

36. Rossignac J;: Structured Topological; Complexes: A feature-based API for non-manifold topologies. In Proc. the ACM Symposium on Solid Modeling, 1997, 1-9.

37. Pasko A., Adzhiev V., Schmitt В., Schlick G.: Constructive hypervolume modeling. Graphical Models 63, 6 (2001), 413-442.

38. Biswas, A., Shapiro, V., Tsukanov, I. Heterogeneous material modeling with distance fields, Technical Report SAL 2002-4, University of Wisconsin-Madison, June, 2002

39. Frey, P.J;, George, P.-L. Mesh Generation: Application to Finite Elements -HERMES Science Europe, OXFORD & PARIS, 2000; 814p.

40. Ho-Le, К Finite element mesh generation methods: a review and; classification./CAD, 1988, V.20,N 1, p. 27-38.

41. Lohner, R. Automatic unstructured grid generators, Finite Elements in Analysis and Design, 25, 1997, 114-134

42. Owen,. S. J., A survey of unstructured mesh generation: technology,. Proceedings 7th International Meshing Roundtable,, Dearborn, MI, October 1998

43. Построение расчетных сеток: Теория и приложения — В сб. под ред. Иваненко С.А., Гаранжа В.А., ВЦ РАН, М. 2002

44. Brawn P.R. A non-interactive method for the automatic generation of finite element meshes using Schwarz-Christoffel transformation. Сотр. Methods in Appl. Mech. Eng., 1981, V. 25, p. 101-126.

45. Baldwin K.H., Schreyer H.L. Automatic generation of quadrilateral elements by a conformal mapping. Eng. Comput., 1985, V.2, p. 187-194.

46. Cook W.A. Body oriented* (natural) coordinates for generating three dimensional meshes. Int. J. Num. Meth. Eng., 1974, V.8, p. 27-43.

47. Blum H A transformation for extracting new descriptors of shape. In. Models for the perception of speech and visual form, ed. By W.Wathen-Dunn, Cambridge, MA, the MIT Press, 1967, p.326-380

48. Arantes, E.R., Oliveira, E., Babuska, I:, Zienkiewicz, O.C., Gado J.P., eds. Proceedings International Conference on Accuracy Estimates and Adaptive Refinement in Finite Element Computation, Lisbon, 1984.

49. Thompson J.F. A survey of dynamically adaptive grids in the numerical solution of partial differential equations. / AIAA Paper 84-1606, 1984.

50. Rivara, M., Levin, С. A 3D refinement algorithm suitable for adaptive and5-multi-grid techniques, J. Сотр. and Appl. Math., 8, 1992, 281-290.

51. D. A. Field; The legacy of automatic mesh generation from solid modeling, Computer-Aided Geometric Des,V12, 1995,651-674

52. Bloomenthal, J. An Implicit Surface Polygonizer, Graphics Gems IV, Academic Press, 1994 •

53. Hartmann, E. A marching: method for the triangulation < of surfaces, The Visual Computer, 14(3), 1998; 95-108;

54. Karkanis, Т., Stewart, A. J. Curvature-dependent triangulation; of implicit surfaces, IEEE Computer Graphics and Applications, 21(2), 2001, 60-69.

55. Lorensen, W., Cline, H. Marching Cubes: a high resolution 3D surface construction algorithm, Computer Graphics, 21(4), 1987, 163-169.

56. Frey, P.J., Borouchaki, H., Geometric surface mesh optimizasion, Computing and Visualization in Science, 1(3), 1998, 113-121

57. Kobbelt, L. V3-Subdivision, Computer Graphics (Proceedings of SIGGRAPH'2000), 103-112.

58. Garland M., Heckbert, P.S. Surface simplification using error metrics, Computer Graphics (Proceedings of SIGGRAPIT97), 209-216.

59. Sheffer, A., Model simplification for meshing using face clustering, CAD, 33(13), 2001,925-934

60. Pasko A.A., Savchenko V.V. Algebraic sums for deformation of constructive solids, Third ACM Symposium on Solid Modeling and Applications, C.Hoffmann and J.Rossignac (Eds.), Salt Lake City, Utah, USA (May 17-19, 1995), ACM Press, 1995, pp. 403-408.

61. Александров П.С. Комбинаторная топология., ОГИЗ, Гостехиздат, 1947

62. Massey W.S. Algebraic topology: An introduction. Harcourt, Brace&World, Inc., New York-Chicago-San Francisco-Atlanta, 1967

63. Handbook of Discrete and Computational Geometry, ed. by Goodman J., O'Rourke J., CRC Press, 1997

64. Freitag, L., Ollivier-Gooch, C. Tetrahedral mesh improvement using swapping and smoothing, Int. J. Numer. Meth. Eng., 40, 1997, 3937-4002.

65. P.-A. FayoIIe, A. Pasko, E. Kartasheva, N. Mirenkov, "Shape recovery using functionally represented constructive models", Proc. International Conference on Shape Modeling and Applications 2004 (SMI'04),IEEE Computer Society, 2004, pp. 375-378