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

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

АСТАХОВ ЮРИЙ СЕРГЕЕВИЧ

АЛГОРИТМЫ ФОРМИРОВАНИЯ ГЕОМЕТРИЧЕСКИХ МОДЕЛЕЙ В СИСТЕМАХ ВИРТУАЛЬНОГО ОКРУЖЕНИЯ

Специальность 05.01.01 - инженерная геометрия и компьютерная графика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

пгс-^и

0050бтг«и

Нижний Новгород - 2013

005061710

Работа выполнена в ФГБОУ ВПО «Нижегородский государственный архитектурно-строительный университет»

Научный руководитель

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

Официальные оппоненты:

Галактионов Владимир Александрович, доктор физико-математических наук, профессор, Федеральное государственное бюджетное учреждение науки «Институт прикладной математики им. М.В. Келдыша Российской академии наук», заведующий отделом

Толок Алексей Вячеславович доктор технических наук, профессор, ФГБОУ ВПО «Московский государственный технологический университет «СТАНКИН»», заведующий кафедрой начертательной геометрии

Ведущая организация:

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики» (ФГБОУ ВПО «СПбНИУ ИТМО»)

Защита состоится «18» июня 2013 года в 15-00 на заседании диссертационного совета Д 212.162.09 при ФГБОУ ВПО «Нижегородский государственный архитектурно-строительный университет» по адресу: 603950, г. Нижний Новгород, ул. Ильинская, д. 65, корпус 5, аудитория 202.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Нижегородский государственный архитектурно-строительный университет» Автореферат разослан «16» мая 2013 г.

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

кандидат педагогических наук, доцент

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

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

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

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

для каждой вершины заданы евклидовы координаты для нескольких временных шагов, что представляет собой анимированную трёхмерную модель. Такие модели состоят из миллионов полигонов, что существенно затрудняет их визуальное отображение из-за аппаратных вычислительных ограничений современного оборудования. Для уменьшения детализации (редукции) моделей используется геометрический подход, называемый методом прогрессивных сеток (децимация сеток), широко применяющийся для снижения числа полигонов без нарушения связности модели. В отечественной науке существенный вклад в развитие теоретических основ и практических решений в области геометрического моделирования внесен научными школами Васина Ю.Г., Галактионова В.А., Дебелова В.А., Кеткова Ю.Л., Роткова С.И., Кучуганова В.Н., Желтова С.Ю., Денискина Ю.И., Турлапова В.Е. и ряда других исследователей.

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

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

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

2. Разработка методов и алгоритмов устранения разрывов поверхности в САЭ-моделях, полученных в результате обработки данных лазерного сканирования и фотограмметрии.

3. Разработка метода и алгоритмов редуцирования моделей для их интерактивной визуализации в виртуальном окружении.

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

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

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

2. Разработан новый алгоритм для восстановления обширных и топологически неоднозначных областей недостающих поверхностей CAD-моделей.

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

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

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

Разработанные методы визуализации и алгоритмы были внедрены в практику научных исследований в Государственном научном центре РФ Научно-исследовательском институте теплоэнергетического приборостроения «НИИТеплоприбор», в Институте физико-технической информатики, в Фраунгоферовском Институте Медиакоммуникаций (Fraunhofer Institut Medienkommunikation) и Фраунгоферовском Институте Компьютерной Графики (Fraunhofer Institut Graphische Datenverarbeitung) и используются в качестве инструмента визуализации в системах виртуального окружения.

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

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

Основные положения, выносимые на защиту:

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

2. Алгоритм восстановления поля недостающей поверхности для обширных и топологически неоднозначных областей CAD-моделей.

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

4. Алгоритмы интерактивного проектирования и редуцирования моделей крэш-тестов на основе использования метода прогрессивных сеток.

Публикации. Основные результаты по теме диссертации изложены в 15 научных работах, 3 из которых опубликованы в изданиях, рекомендованных ВАК Минобрнауки России.

Апробация работы. Основные результаты работы докладывались и обсуждались на научных семинарах кафедры и Института физико-технической информатики; на Международной конференции Intuition 2007 (Греция, Афины); на Международных конференциях «Кибернетические Миры» (International Conference on Cyberworlds) CW2007 (Германия, Ганновер), CW2008 (КНР, Ханчжоу), CW2009 (Великобритания, Бредфорд); на Первой международной конференции «Трехмерная визуализация научной, технической и социальной реальности. Кластерные технологии моделирования» (Россия, Ижевск, 2009); на 19-й Международной конференции ГрафиКон-2009 (Россия, Москва); на 52-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» (Россия, Долгопрудный, 2009); на Международных научных конференциях MEDIAS2009, MEDIAS2010, MED1AS2011, MEDIAS2012 (Республика Кипр, Лимассол); на Международных конференциях «Ситуационные центры и информационно-аналитические системы класса 4i» (Россия, Москва, 2011) и «Системы виртуального окружения для комплексной

безопасности и антитеррористической защищенности зданий и сооружений» (Россия, Москва, 2011).

Диссертационная работа была выполнена при поддержке грантов Российского фонда фундаментальных исследований 09-08-01009, 10-07-00512, 10-07-00513, 10-07-00514, 11-07-00506, 12-07-00780.

Структура и объем работы. Диссертация состоит из введения, четырёх глав, заключения, библиографического списка литературы (85 наименований) и двух приложений. Общий объём текста работы — 119 страниц машинописного текста. Количество рисунков - 31. Количество таблиц - 3.

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

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

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

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

при личном участии автора для ГНЦ «НИИТеплоприбор». Архитектура упомянутых систем построена на использовании суперЭВМ и специального проекционного оборудования, позволяющего воспроизводить стереоизображение ЗЭ объектов и окружающей обстановки, а также изучать динамику поведения моделируемого объекта.

Программное обеспечение систем виртуальной реальности может быть основано на применении различных библиотек программ. Упомянутый выше вариант системы виртуальной реальности базируется на отечественной разработке «АВАНГО», в разработке которой автор принимал участие.

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

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

Основная идея метода прогрессивных сеток для моделей из треугольников и четырёхугольников состоит в последовательном исключении малозначащих полигонов (треугольников или четырёхугольников) из модели до получения модели с минимально подходящим качеством, затем проведением

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

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

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

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

хорошим параллелизациоиным возможностям решений, основанных на представлении поля недостающей поверхности (НП).

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

Рисунок 1 - Поле недостающей поверхности, аппроксимированное с помощью мостов

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

• потенциал У - скалярная величина, такая, что для некоторой точки (У) в окрестности ХЧ>у > Ч',., если вероятность того, что НП проходит через {X) больше вероятности, что НП проходит через (У); неположительные значения потенциала соответствуют нулевой вероятности прохождения НП через (X);

• сила ^ - вектор, показывающий наиболее предпочтительное направление моста, проходящего через (выходящего из) X. Длина вектора выражает вероятность корректности этого направления по сравнению с направлением, определенным вектором силы в некоторой соседней точке (У) по тому же принципу, что и для потенциала; (/•') является суммарным вектором действующих в (X) векторов элементарных сил, среди которых могут быть, в общем случае, как притягивающие, так и отталкивающие;

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

• нормаль N — вектор, показывающий наиболее вероятное направление вектора внешней нормали НП в X, длина вектора выражает вероятность корректности этого направления так же, как и в случае силы. Очевидно, что если Ч» = 0 (например, в том случае, если XпринадлежитРП), то |к| = 0, О^О и |1Ч| = 0. Таким образом, напряжённость ПНП является функцией координат

точки пространства: Ф = Ф(Х).

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

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

поля определяется с помощью совокупности точки на границе РП (О), а также нормального (п°) и касательного (т°) векторов в этой точке ({О,п°,т0}). Объект действия поля определяется совокупностью отслеженной точки (.¥) некоторой силовой линии, выходящей из соответствующей точки границы РП (в), вектора нормали в X (пА ) и касательного вектора х" к границе РП в В{{Х,п" ,хв}). Элементарный источник поля {О,п°,х0} воздействует на объект действия {Х,пх,х"} с силой КА":

РА = -сЛ" {\ХО\)т1тс1, если хвх° < 0;

Vх = 0, если х"х° > 0.

В интерполирующее онлайновое ПНП (ИСП) в качестве объекта действия нового поля определяется совокупностью последней отслеженной точки X силовой линии с определенными в ней векторами нормали (пА') и силы ИГП

В1 В1

(Vх): X, п\ Vх .

Рисунок 2 - Интерполирующее границы поле недостающей поверхности

Для предсказания поведения НП описываемое поле использует уравнение сплайновой кривой. Эта кривая (s) соединяет две точки пространства X и О с определёнными в них соответствующими векторами нормали пл, п° и лежит в плоскости р, содержащей прямую (ХО ) и вектор пА +п°. Поведение кривой в этой плоскости (см. рис. 2) описывается уравнением Эрмитова сплайна: s(t) = (2t3-3t2 + l)X + (t3 -212+ ()mx + (~2t3 + 3t2)0 + (t3 -t2)m° где t - параметр кривой л-, /e[o,l]; s[t) - радиус-вектор точки сплайновой кривой, соответствующей значению параметра t, s(0) ^ X, ,v(l) = О; XX) -

радиус—векторы точек х и О соответственно; пх, п°р - проекции на плоскость р соответственно векторов пЛ' и п°; шл, т° - определённые соответствующими векторами ах и п° касательные векторы к .V и соответствующих конечных точках X и О, от[0] = и[1],;и[1] = -и[0].

Радиальное ПНП (ПСТ) в качестве элементарного источника поля (см. рис. 3) принимает точку О исходного облака точек, не включённая в РП, с определённым в ней вектором нормали (п°): {О,п°]. Объектом действия поля определяется последняя отслеженная точка X силовой линии с определённым в точке вектором нормали пЛ : {Х,пх}.

О

Рисунок 3 - Сплайновая кривая Потенциал, созданный точкой в точке, определяется выражением: Vх =сЛт(\ХО\)\д°ххп°\пхп0, где се(0,1] — коэффициент доверия к координатам точки О; Л™ является

ОХ

функцией расстояния, аох =г—г.

\ох\

.............. С1

В

Рисунок 4 - Радиальное ПНП свободных точек

На базе теоретического материала была создана программная реализация и проведены тесты с использованием адаптивного композитного ПНП состоящего из ИГП (В/), ИСП (57), и ПСТ (141):

Ф = W Ф+ IV,., Ф+ w ф

где:

' к (0 ^ ri-Ar^j

1-н£ 1 'WSI = 0 >WPR = 0 0

, 1 v v 0 У . 0 ,

> 0 и Wy = О, если

= 0, ¿ = 0,7-

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

RFB-метамодель. В начале даётся определение метамоделирования с использованием интерполяции радиальными базисными функциями, обосновывается выбор функции мульти-квадриков в качестве радиальной базисной

функции (Ф(г) = -Jb2+r2 ), полиномиальным членом:

расширением интерполяции

/=1

где численное моделирование определяет отображение у = /(х): Я" —> Н'" из и-мерного пространства параметров в /»-мерное пространство результатов моделирования. Описываются характеристики интерполяции больших объёмов

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

Анализ надёжности. Даётся описание нескольких методов оценки доверительного интервала (CL) для результатов моделирования: P(y<CL) = C, где Р - мера вероятносги и С - заданный пользователем уровень доверительности. Каждый метод использует различные численные характеристики отображений /(*).

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

Причинно-следственный (темпоральный) анализ, как правило, осуществляется с помощью статистических методов, в частности, по оценке корреляции событий. Общеизвестно, что корреляция не означает прямую причинную связь (эта распространенная логическая ошибка обозначается как «cum hoc ergo propter hoc» - «вместе, значит из-за»). В действительности сильная корреляция двух событий означает, что они принадлежат к одной причинно-следственной цепи. Два сильно коррелированных события либо находятся в прямой причинно-следственной связи, либо имеют общую причину, то есть третье событие в прошлом, вызывающее этих два. Эту общую причину можно выявить, если восстановить всю причинно-следственную цепь, т.е. полную последовательность связанных событий.

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

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

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

Рисунок 4 - Темпоральная кластеризация модели Ford Taurus в системе DiffCrash: вверху слева: исходный шум, в мм. вверху справа - в центре слета - в центре справа: результаты последовательных итераций вычитания шума, внизу: две основные бифуркации, найденные при анализе

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

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

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

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

4. Разработанные методы и алгоритмы реализованы в инструментальной системе разработки виртуальных окружений Avango.

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

Публикации по теме диссертационной работы

Статьи, опубликованные в изданиях, рекомендованных ВАК: 1. Astakhov, Y. Towards Interactive Simulation in Automotive Design/ Y. Astakhov and oth.// The Visual Computer. Special Issue INTUITION. - 2008. -Vol.24, Num.11. - PP.947-953.

2. Астахов, Ю. С. Восстановление не полностью реконструированных CAD-моделей/ Ю. С. Астахов, А. И. Емельянов, С. В. Клименко, С. И. Ротков// Приволжский научный журнал - 2012. - № 3. - С. 94-99.

3.Астахов, Ю. С. Исправление CAD-моделей, полученных из сканированных данных/ Ю. С. Астахов, А. И. Емельянов, С. В. Клименко, С.И. Ротков // Приволжский научный журнал. - 2013. - № 1. - С. 26-32.

Статьи в сборниках научных трудов и сборниках конференций:

4. Astakhov, Y. Simulated Reality in Automotive Design/ Astakhov, Y. and oth. // Proceedings of Inteernational Conference on Cyberworlds 2007. - CW2007: IEEE Press, 2007. - PP. 23-27.

5. Астахов, Ю.С. Методы стохастического анализа больших объемов данных/ Ю.С. Астахов, С.В. Клименко, И.Н.Никитин, Л.Д.Никитина // SC-IAS4i-VRTerro2011, Ситуационные центры и информационно-аналитические системы класса 4i: тр. Междунар. науч. конф. - М.-Протвино: Изд-во ИФТИ, 2011.-С.6-16.

6. Astakhov, Yu.S., Estimation of Interpolation Properties of a Point/ Yu.S. Astakhov, E A.I.melyanov, S.V. Klimenko// Proceedings of International Conference on Cyberworlds 2008. - CW2008: IEEE Press, Piscataway, 2008. - PP.461-466.

7. Astakhov, Y. General Concept of Repairing CAD-Models/ A. Emelyanov, Y.Astakhov, S.Klimenko // Proc. CW2009 International Conference on CyberWorlds. - Bradford, West Yorkshire, UK, 2009. - PP.108-113. Digital Object Identifier 10.1109/CW .2009.53

8. Астахов, Ю.С. 3D моделирование виртуальных сцен для тренажерных комплексов с силовой обратной связью / Ю.С. Астахов и др.// Трехмерная визуализация научной, технической и социальной реальности. Кластерные технологии моделирования: 1-я Междунар. конф. - Ижевск, 2009. - С.10-13.

9. Астахов, Ю.С. Исследование и разработка методов повышения реалистичности 3D погружения в визуально-силовых тренажерах/ Ю.С.Астахов и др. // MEDIAS2010: Тр. Междунар. науч. конф. - Лимассол, Республика Кипр: Изд-во ИФТИ, 2010. - С. 18-22.

10. Astakhov, Y. 3D scenes simulation, animation, and synchronization in training systems with force back-coupling/ Y. Astakhov and oth. // The Proc. of the 19 International Conference GraphiCon-2009. - Moscow, Russia. - PP. 166-170.

П.Астахов, Ю.С. Параллельные архитектуры для реконструкции сеточных моделей/ Ю.С. Астахов, А.И. Емельянов, C.B. Клименко, П.Фролов// MEDIAS2010: Тр. Междунар. науч.конф. - Лимассол, Республика Кипр: Изд-во МФТИ, 2010. - С.140-148.

12. Астахов, Ю.С. Общее представление параллелизуемой обработки для восстановления CAD-моделей/ Ю.С. Астахов, А.И. Емельянов, С.В.Клименко// MEDIAS2011: тр. Междунар. науч. конф. Лимассол, Республика Кипр: Изд-во ИФТИ, 2011. - С. 17-24.

13. Астахов, Ю.С. Корректировка CAD-моделей, полученных из облака точек сканирования/ Ю.С. Астахов, А.И. Емельянов, C.B. Клименко, С.И. Ротков// SC-IAS4i-VRTerro2011 Ситуационные центры и информационно-аналитические системы класса 4i, Системы виртуального окружения для комплексной безопасности и антитеррористической защищенности зданий и сооружений: Тр. Междунар. науч. конф. - М.-Протвино: Изд-во ИФТИ, 2011. -С.92-102.

14. Астахов, Ю.С. Модернизация программно-технического комплекса ОАО ГНЦ «НИИТеплоприбор» для задач виртуального прототипирования приборов и систем объектов энергогенерации/ Ю.С. Астахов и др. // MEDIAS2012: Тр. Междунар. науч. конф. - Лимассол, Республика Кипр: Изд-во ИФТИ, 2012.-С.31-51.

15. Астахов, Ю.С. Алгоритмы формирования геометрических моделей в системах виртуального окружения/ Ю.С. Астахов // MEDIAS2012: Тр. Междунар. научн. конф. - Лимассол, Республика Кипр: Изд. ИФТИ, 2012. -С.85-100.

Подписано в печать Г Формат 60x90 1/16

Печать трафаретная. Бумага офсетная. Усл.печл. 1,0 Тираж 100 экз. Заказ № Федеральное государственное бюджетное образовательное учреждение высшего профессионального образовании «Нижегородский государственный архитектурно-строительный университет» 603950, Н.Новгород, Ильинская, 65. Полиграфцентр ННГАСУ, 603950, Н.Новгород, Ильинская, 65

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ (государственный университет) НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ

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

04201359989 АСТАХОВ ЮРИЙ СЕРГЕЕВИЧ

АЛГОРИТМЫ ФОРМИРОВАНИЯ ГЕОМЕТРИЧЕСКИХ МОДЕЛЕЙ В СИСТЕМАХ ВИРТУАЛЬНОГО ОКРУЖЕНИЯ

Специальность 05.01.01 - инженерная геометрия и компьютерная графика

Диссертация на соискание учёной степени кандидата технических наук

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

Никитин И.Н.

Москва - Нижний Новгород -2013

Оглавление

Введение...........................................................................................................................5

Глава 1. Программно-технический комплекс виртуального окружения различного назначения......................................................................................................................11

1.1. Общее описание системы...................................................................................13

1.2. Системы визуализации и виртуального окружения........................................19

1.3. Назначение систем виртуального окружения..................................................24

1.4. Архитектура систем виртуального окружения................................................26

1.4.1. Cave....................................................................................................................31

1.4.2. iCONE................................................................................................................32

1.5. Инструментальные программные средства......................................................32

1.5.1. Платформа CUDA C/C++............................................................................34

1.5.2. Платформа OpenCL.....................................................................................36

1.5.3. Платформа С++ AMP..................................................................................38

1.6. Выводы первой главы.........................................................................................39

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

2.1. Методы обработки сцен высокой сложности...................................................41

2.2. Смешанные полигональные модели.......................~..........................................44

2.3. Системы виртуального окружения....................................................................45

2.4. Среда виртуального окружения "Аванго"........................................................46

2.5. Реализация смешанных полигональных моделей............................................49

2.5.1. Формат хранения данных модели..............................................................49

2.5.2. Узлы сетки базовой модели (CHUNKJSÍODES)......................................51

2.5.3. Топология базовой модели (CHUNKJNDEXED_CELLS).....................52

2.5.4. Шаги анимации (CHUNK_TIMESTEP).....................................................52

2.5.5. Скалярные параметры узлов сетки (СНиМЕСНОБЕЗ С АЬ АЯО АТА8ЕТ)...........................................................53

2.5.6. Хранение прогрессивных сеток (СНШК_РКСЮКЕ881УЕ_0ЕТА1Ь).. 53

2.5.7. Реализация алгоритма разделения вершины для смешанных моделей. 54

2.5.8. Схема работы объекта визуализации........................................................57

2.6. Результаты............................................................................................................58

2.7. Выводы второй главы.........................................................................................59

Глава 3. Корректировка С АО-мод ел ей, полученных из облака точек сканирования .........................................................................................................................................60

3.1. Формализация входных данных........................................................................60

3.2. Существующие решения....................................................................................62

3.3. Представление мостов........................................................................................62

3.4. Представление поля недостающей поверхности.............................................65

3.4.1. Основные положения..................................................................................65

3.4.2. Формализация напряжённости поля..........................................................67

3.4.3. Разновидности реализаций ПНП...............................................................68

3.4.4. Определение силовой линии ПНП.............................................................70

3.4.5. Связь представления ПНП с другими подходами....................................70

3.4.6. Отслеживание силовых линий ПНП..........................................................71

3.5. Практические реализации ПНП.........................................................................72

3.5.1. Общие положения........................................................................................72

3.5.2. ПНП, интерполирующее границы РП.......................................................73

3.5.3. Интерполирующее сплайновое ПНП........................................................75

3.5.4. Радиальное ПНП свободных точек............................................................78

3.6. Реализация и тесты..............................................................................................79

3.7. Выводы третьей главы........................................................................................80

Глава 4. Приложение разработанных методов и алгоритмов к анализу больших

объемов данных.............................................................................................................82

4.1. RFB-метамодель..................................................................................................84

4.2. Анализ надёжности.............................................................................................87

4.2.1. Метод анализа надёжности первого порядка (FORM)............................88

4.2.2. Метод анализа надёжности второго порядка (SORM)............................89

4.2.3. Определение доверительных пределов методом Монте-Карло (CL-MC) ..................................................................................................................................89

4.2.4. Монте-Карло в сочетании с RFB-метамоделью (MC-RFB)....................90

4.3. Анализ причинно-следственных связей............................................................91

4.4. Примеры...............................................................................................................97

4.4.1. Ударопрочность стойки кузова (Audi)......................................................97

4.4.2. Ударопрочность полного автомобиля (Ford Taurus)................................98

4.5. Выводы четвёртой главы....................................................................................99

Заключение..................................................................................................................100

Благодарности..............................................................................................................101

Список литературы.....................................................................................................102

Приложение 1. Результаты тестовых испытаний алгоритмов корректировки

моделей.........................................................................................................................1 1 1

Приложение 2. Примеры анализа ударопрочности и темпоральной кластеризации

.......................................................................................................................................115

Приложение 3. Глоссарий: словарь сокращений и терминов................................117

Введение

«Постоянно растущая сложность физических явлений, изучаемых в научных и инженерных дисциплинах, требует разработки новых подходов и мощной техники для обработки и анализа сложных данных. Постоянно растущая сложность создаваемых машин и механизмов, зданий и сооружений, транспортных систем и технологических процессов, также требуют новых подходов при проектировании и создании прототипов. Постоянно растущая сложность управляемых человеком машин и механизмов, объектов и процессов требуют новых методов и средств для обучения персонала. Такими методами и средствами являются системы визуализации и виртуального окружения.» [Клименко C.B., Брусенцев П.А. Визуализация проектирования в виртуальном окружении//Клуб 3D. Инновационное проектирование. НИАЭП, Нижний Новгород, 2011, С. 37-48]

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

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

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

Чтобы сократить время вычислений и отрисовки в процессе проектирования проблема решается с использованием геометрического подхода к анализу данных, где в наборе параметров моделирования используется некоторое ограниченное число пробных точек, на основе которых с помощью интерполяции/аппроксимации данных быстро строится вычислимая модель, где критерии оптимизации и дизайн-переменные (параметры) связаны между собой прямой функциональной зависимостью. Современные модели описывают не только значения критериев, но и оценку их точности. Кроме того, вычисляется весь результат моделирования, представленный высоким разрешением в пространстве-времени. Результатом такого моделирования является набор полигональных (нерегулярных) сеток, состоящих из треугольников или четырёхугольников, где для каждой вершины заданы евклидовы координаты для нескольких временных шагов, что представляет собой анимированную трёхмерную модель (САО-модель). Такие модели состоят из миллионов полигонов, что существенно затрудняет их визуальное отображение из-за аппаратных вычислительных ограничений современного оборудования. Для уменьшения детализации (редукции) моделей используется геометрический подход, называемый методом прогрессивных сеток (децимация сеток), широко применяющийся для снижения числа треугольников без нарушения связности модели. В отечественной науке существенный вклад в развитие теоретических основ и практических решений в области геометрического моделирования внесен научными школами Васина Ю.Г., Галактионова В.А., Де-белова В.А., Денискина Ю.И., Желтова С.Ю., Кеткова Ю.Л., Кучуганова В.Н.,

Роткова С.И., Толока A.B., Турлапова В.Е., Утробина В.А. и ряда других исследователей.

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

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

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

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

3. Разработка метода и алгоритмов редуцирования моделей для их интерактивной визуализации в виртуальном окружении.

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

Основные положения, выносимые на защиту:

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

2. Представление поля недостающей поверхности и алгоритмов для восстановления обширных и топологически неоднозначных областей недостающих поверхностей CAD-моделей.

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

4. Методы интерактивного проектирования и редуцирования моделей крэш-тестов.

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

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

2. Разработан новый алгоритм для восстановления обширных и топологически неоднозначных областей недостающих поверхностей CAD-моделей.

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

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

Разработанные методы визуализации и алгоритмы были внедрены в практику научных исследований в Государственном научном центре РФ Научно-исследовательском институте теплоэнергетического приборостроения «НИИ-Теплоприбор», в Институте физико-технической информатики, в Фраунгоферов-ском Институте Медиакоммуникаций (Fraunhofer Institut Medienkommunikation) и Фраунгоферовском Институте Компьютерной Графики (Fraunhofer Institut Graphische Datenverarbeitung) и используются в качестве инструмента визуализации в системах виртуального окружения.

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на научных семинарах Кафедры и Института физико-технической информатики; на Международной конференции Intuition 2007 (Греция, Афины); на Международных конференциях «Кибернетические Миры» (International Conference on Cyberworlds) CW2007 (Германия, Ганновер), CW2008 (КНР, Ханчжоу), CW2009 (Великобритания, Бредфорд); на Первой международной конференции «Трехмерная визуализация научной, технической и социальной реальности. Кластерные технологии моделирования» (Россия, Ижевск, 2009); на 19-й Международной конференции ГрафиКон-2009 (Россия, Москва); на 52-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук» (Россия, Долгопрудный, 2009); на Международных научных конференциях МЕ-DIAS2009, MEDIAS2010, MEDIAS2011, MEDIAS2012 (Республика Кипр, Лимас-сол); на Международных конференциях «Ситуационные центры и информационно-аналитические системы класса 4i» (Россия, Москва, 2011) и «Системы виртуального окружения для комплексной безопасности и антитеррористической защищенности зданий и сооружений» (Россия, Москва, 2011).

Диссертационная работа была выполнена при поддержке грантов Российского фонда фундаментальных исследований 09-08-01009, 10-07-00512, 10-07-00513, 10-07-00514, 11-07-00506, 12-07-00780.

Личный вклад. Все результаты, составляющие основное содержание диссертации, получены автором самостоятельно. В работах [2, 3, 4] автором разработан и реализован алгоритм прогрессивных сеток, редуцирующий CAD-модели, состоящие из треугольников и четырёхугольников для интерактивной визуализации. Предложены и внедрены методы интерактивного проектирования и редуцирования моделей крэш-тестов в инструментальной системе разработки виртуальных окружений Avango.

В работе [5] автором разработан метод для оценки интерполяционных свойств точки заданной поверхности для интерполяции недостающих частей. Автору принадлежит идея использования этого метода для улучшения качества редукции CAD-моделей. В работах [6, 7, 8, 9, 10, 11] разработан метод и пред-

ставление для устранения разрывов поверхности в САБ-моделях с использованием абстрактного тензорного поля, позволяющие разработать и использовать любой метод оценки, имеющий более высокое качество работы и лучшую универсальность по сравнению с существующими. В работах [12, 13, 14] автору принадлежит реализация реконструкции поверхностей по облаку точек ряда ландшафтов горнолыжных трасс с использованием методов и алгоритмов оптимизации сеток и заполнения разрывов.

Публикации. Основные результаты по теме диссертации изложены в 17 печатных изданиях [2-18], 3 из которых изданы в журналах [3, 10, 11], рекомендованных ВАК, 12 — в Трудах Международных конференций [2, 3, 5, 6, 7, 8, 12, 13, 14, 15, 17, 18].

Глава 1. Программно-технический комплекс виртуального окружения различного назначения

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

Важным конк�