ДонНТУ   Портал магистров

Радченко Вячеслав Ильич

Факультет компьютерных наук и технологий

Специальность «Инженерия программного обеспечения»

Исследование методов анимации воксельных моделей

Научный руководитель: к.т.н., Карабчевский Виталий Владиславович

Резюме Биография Реферат Библиотека Ссылки Отчет о поиске Индивидуальный раздел

Реферат по теме выпускной работы

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

Содержание

• Введение
• 1. Актуальность темы
• 2. Цель и задачи исследования, планируемые результаты
• 3. Обзор исследований и разработок
• 3.1 Обзор международных источников
• 3.2 Обзор локальных источников
• 4. Описание предложенного метода анимирования воксельных моделей
• Выводы
• Список источников

Введение

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

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

Вокселы — это кубоиды. Идея состоит в том, чтобы апроксимировать 3D модели множеством (миллионами) небольших кубоидов, как это представленно на рисунке 1. Если разрешение воксельной модели достаточно высоко, вокселы становятся меньшими чем пиксели дисплея и больше не различимы на итоговом изображении. Модель воспринимается как сглаженная, без видимых выступов. Методы улучшения изображения, сглаживание, антиалайзинг полностью скрывают базовую структуру кубоида воксельной модели – тем же способ, которым они скрывают, структуру полигональной модели[1].

Исследования в области анимирования, используещего реальные физические свойства и законы, предполагает нахождения новых методов для моделирования физических явлений, таких как динамика твердых тел, деформируемых объектов или потока жидкости. Традиционный подход к моделированию динамических объектов работает с силами. В начале каждого временного шага пересчитываются внутренние и внешние силы. Примеры внутренних сил – упругие силы в деформируемых объектах или силы вязкости и давления в жидкостях. Сила тяжести и силы столкновения – примеры внешних сил. Второй закон движения Ньютона связывает силы с ускорением тела и его массой. Используя плотность или усредненные массы вершин, силы преобразуются в ускорение. Любая схема интегрирования времени может быть использована, чтобы сначала вычислить скорости на основе ускорений и затем положения на основе скоростей. Некоторые подходы для управления анимацией используют импульсы вместо сил. Поскольку импульсы непосредственно изменяют скорости, один уровень просчетов может быть опущен [6].

Методы моделирования должны удовлетворять четырем главным требованиям, чтобы быть применимыми в компьютерных играх. Они должны быть быстрыми, устойчивыми, управляемыми и простыми в реализации, для того чтобы разработчики игр смогли использовать их в своих проектах [7]. В компьютерных играх, где устойчивость и скорость часто более важны, чем точность, более простые и устойчивые геометрические методы, такие как динамика на основе позиций (Position Based Dynamics (PBD))[6], может быть достаточным, чтобы создать требуемые физические эффекты.

1. Актуальность темы

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

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

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

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

2. Цель и задачи исследования, планируемые результаты

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

Основные задачи исследования:

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

Объект исследования: анимация воксельных моделей.

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

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

3. Обзор исследований и разработок

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

3.1 Обзор международных источников

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

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

В работе [2] Ciryl Crassin рассматривает метод рендеринга больших наборов данных используя вокселы. Он использует информацию, полученную во время процесса рендеринга, чтобы регулировать процесс потоковой передачи. Их технология, Gigavoxels не ограничена стереометрией, но в состоянии представлять атмосферные эффекты, такие как облака.

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

Технология Unlimited Detail[21] разрабатывается австралийской компанией Euclideon с 2004 года. Основными разработчиками являются Bruce Dell и Greg Douglas. Unlimited Detail — программная технология в трёхмерной компьютерной графике, предназначенная для хранения и рендеринга виртуальной трёхмерной сцены посредством облака точек в режиме реального времени. Основные технологические аспекты «Unlimited Detail» публично не известны, однако разработчики заявляют, что их технология позволяет отображать на сцене неограниченное количество объектов с очень высокой детализацией без существенной потери производительности.

В работах [6] и [7] представлен универсальный подход анимирования объектов Position Based Dynamics (PBD), позволяющий моделировать сложные физические объекты и процессы.

3.2 Обзор локальных источников

В результате поиска работ, посвященных тематике данной работы, не было найдено ни одной работы соответствующей данному направлению. Поверхностный обзор воксельной графики как таковой был дан в работах магистров С.С. Захаров Моделирование земной поверхности[17], Н.О. Харченко Структурно-алгоритмическая организация устройств генерации произвольных дуг и секторов в 3D пространстве для объёмных дисплеев[18] и В.Н. Кудря Исследование и разработка алгоритмов синтеза моделей геометрических объектов[19]. Тем не менее, само содержение этих работ имеет другую направленность.

4. Описание предложенного метода анимирования воксельных моделей

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

Вероятно, самый простой формат хранения воксельной модели — регулярная координатная сетка. Модель может быть представлена как трехмерный массив в котором каждая ячейка описывает один воксел. Данное представление является неэффективным с точки зрения используемой памяти. Более эффективное решение, используемое в большинстве случаев — разреженное воксельное октодерево (Sparse Voxel Octree (SVO)). SVO — это древовидная структура данных, в которой у каждого узла может быть до восьми дочерних элементов. Дерево разреженно в том смысле, что оно не включает поддеревья, соответствующие пустому вокселю. Основная идея состоит в том, чтобы начиная с одного большого кубоида и равномерно разделяя его на восемь меньших кубоидов, повторять рекурсивно этот процесс для каждого дочернего элемента пока необходимая детализация не будет достигнута. Рисунок 2 иллюстрирует это понятие.

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

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

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

В компьютерной графике и особенно в компьютерных играх часто желательно иметь прямое управление положениями объектов или вершинами полигональной сетки. Пользователь может привязать вершину к кинематическому объекту или удостовериться, что вершина всегда остается вне определенной области. Метод динамики на основе позиций (Position Based Dynamics (PBD)) работает непосредственно с позициями, что делает такие манипуляции легко реализуемыми.

В исходном подходе PBD моделируемый объект представляется набором из N контрольных точек и множеством из M ограничений. Каждая контрольная точка i имеет атрибуты приведенные в таблице 1.

Ограничение j определяется пятью атрибутами приведенными в таблице 2. Ограничение с типом равенство удовлетворяется если C_j(x_i1,...,x_inj)=0. Если тип неравенство, то ограничение удовлетворяется если C_j(x_i1,...,x_inj ) ≥ 0. Параметр жесткости k_j определяет силу воздействия ограничения и может принимать значение от 0 до 1.

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

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

Результат моделирования взаимодействия двух объектов приведен на рисунке 3 (слева показаны контрольные точки и связи, справа – конечный результат). В этом примере мяч представляет собой твердое тело, сетка — деформируемую систему (контрольные точки выделены красным цветом). Все вычисления при моделировании выполнены с использованием динамики на основе позиций (PBD).

Основную идеи предлагаемого подхода анимации воксельного октодерева можно изложить в следующих утверждениях:

1. Каждый узел SVO дерева обрабатывается как отдельная частица, может быть модифицирован/трансформирован независимо от родительских узлов.
2. Каждый узел SVO дерева либо имеет свой набор свойств и ограничений, либо наследует их от родителя.
3. На каждом шаге узлы SVO дерева трансформируются определенным образом.
4. На каждом шаге, использую динамику на основе позиций (PBD), происходит пересчет и корректировка позиций и скоростей.

Выводы

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

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

Дальнейшие исследования направлены на следующие аспекты:

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

При написании данного реферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2012 года. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.

Список источников

1. Bautembach D., Animated Sparse Voxel Octrees // Bachelor’s Thesis – University of Hamburg, Department of Informatics, 2011, http://www.bautembach.de ...
2. Crassin C., GigaVoxels: A Voxel-Based Rendering Pipeline For Efficient Exploration Of Large And Detailed Scenes // PhD thesis – Universite de Grenoble, 2011 http://www.maverick.inria.fr ...
3. Muller M., Teschner M., Gross M., Physically-Based Simulation of Objects Represented by Surface Meshes // Proceedings of Computer Graphics International (CGI), Crete, Greece, Jun 16-19 2004, pp 26-33, http://www.matthiasmueller.info ...
4. Gibson S., Mirtich B., A Survey of Deformable Modeling in Computer Graphics // Mitsubishi electric research laboratories, Technical Report TR-97-19, MERL, 1997 http://www.merl.com ...
5. Nealen A., Muller M., Keiser R., Boxerman E., Carlson M., Physically Based Deformable Models in Computer Graphics // Computer Graphics Forum, 2006, Volume 25, pp 809–836, http://citeseerx.ist.psu.edu ...
6. Muller M., Heidelberger B., Hennix M., Ratcliff J., Position Based Dynamics // Proceedings of Virtual Reality Interactions and Physical Simulations (VRIPhys), – Madrid, 2006, – pp 71-80, http://www.matthiasmueller.info ...
7. Muller M., Hierarchical Position Based Dynamics // Proceedings of Virtual Reality Interactions and Physical Simulations (VRIPhys2008), Grenoble, 2008 http://www.matthiasmueller.info ...
8. Muller M., Chentanez N., Solid Simulation with Oriented Particles // ACM Transactions on Graphics (SIGGRAPH 2011), 2011, pp 92:1-92:10, http://www.matthiasmueller.info ...
9. Karabassi A., Papaioannou G., Theoharis T., A Depth Buffer Based Voxelization Algorithm // Department of Informatics, University of Athens, 2000 http://www.cgi.di.uoa.gr ...
10. Figueiredo M., Oliveira J., Araujo B., Pereira J., An efficient collision detection algorithm for point cloud models // Международная конференция по компьютерной графике GraphiCon, 2010, http://www.graphicon.ru ...
11. Limtrakul S., Hantanong W., Kanongchaiyos P., Nishita T., Reviews on physically based controllable fluid animation // Engineering Journal, Vol 14, 2010, http://www.engj.org ...
12. Belyaev S., Laevsky I., Chukanov V., Real-time Animation, Collision and Rendering of Grassland // Международная конференция по компьютерной графике GraphiCon, 2011, http://www.graphicon.ru ...
13. Катасонов А.В., Вяткин С.И., Долговесов Б.С., Вокселизация функциональных форм // Международная конференция по компьютерной графике GraphiCon, 2005, http://www.graphicon.ru ...
14. Семакин М.М., Метод синтеза движений в задачах трехмерной компьютерной анимации // Bachelor’s Thesis – University of Hamburg, Department of Informatics, 2011, http://www.graphicon2002 ...
15. Бобков В.А., Мельман С.В., Роньшин Ю.И., Оптимизация трассировки лучей в октантных деревьях // Международная конференция по компьютерной графике GraphiCon, 2005, http://www.graphicon.ru ...
16. Лисицин Е., Конушин А., Подгонка параметрических моделей к облакам трехмерных точек // Международная конференция по компьютерной графике GraphiCon, 2006, http://www.graphicon.ru ...
17. Захаров С.С. , Моделирование земной поверхности // Магистерская работа, руководитель: д.т.н., профессор Башков Е.А., 2005, http://masters.donntu.ru ...
18. Харченко Н.О. , Структурно-алгоритмическая организация устройств генерации произвольных дуг и секторов в 3D пространстве для объёмных дисплеев.// Магистерская работа, руководитель: д.т.н., профессор Башков Е.А., 2011, http://masters.donntu.ru ...
19. Кудря В.Н., Исследование и разработка алгоритмов синтеза моделей геометрических // Магистерская работа, руководитель к.т.н., доц. Карабчевский В.В., 2003, http://masters.donntu.ru ...

20. Официальный сайт проекта Аtomontage Engine // Режим доступа http://www.atomontage.com

21. Официальный сайт проекта Unlimited Detail // Режим доступа http://www.euclideon.com/