Введение 4
1 Обзор предметной области 7
1.1 Обзор литературных источников 7
1.2 Двоичное разбиение пространства 13
1.2.1 Выбор разбивающей плоскости 13
1.3 Инструменты и технологии 14
1.3.1 Игровой движок Unity 14
1.3.2 Интегрированная среда разработки Visual Studio 15
2 Реализация инструментария для выполнения булевых операций 16
2.1 Определение возможностей разрабатываемого проекта 16
2.2 Необходимые компоненты игрового движка Unity и их особенности . 16
2.3 Структура создаваемой библиотеки 19
2.3.1 Класс Extensions 19
2.3.2 Структура PostionUVPair 20
2.3.3 Перечисление PolygonType 20
2.3.4 Класс VertexInfo 21
2.3.5 Перечисление BooleanType 21
2.3.6 Класс Node 21
2.3.7 Класс BinarySpacePartitioning 22
2.3.8 Класс BooleanOperation 22
2.4 Вычисление булевых операций 23
2.4.1 Этап инициализации 23
2.4.2 Построение BSP-деревьев 23
2.4.3 Объединение
2.4.4 Разность
2.4.5 Пересечение 27
2.4.6 Заключительный этап 27
2.5 Параллелизация обработки 27
2.6 Результаты работы системы 29
2.6.1 Скорость обработки 30
2.6.2 Недостатки разработанной системы 33
Заключение 35
Список использованных источников 36
Глоссарий 40
Приложение А. Исходный код разработанной библиотеки классов 44
В сфере трёхмерной компьютерной графики при взаимодействии в реальном времени существует проблема изменения полигональных моделей при их соприкосновении с другими полигональными объектами. Как, например, при использовании симуляции взаимодействия ножа и органических тканей, ткани должны менять свою топологическую структуру при касании ножа, что необходимо при создании хирургических симуляторов [1; 2]. Так как в данный момент мало исследований посвящённых обработке взаимодействий объектов в реальном времени, приводящих к изменению их топологии, эта проблема является актуальной.
При условии создания универсального инструмента, модифицирующего объекты логическими операциями в реальном времени, данная проблема будет частично решена.
В данный момент большинство разработок булевых операций для полигональных сеток входят в состав программных обеспечений для 3D- моделирования и решают проблему создания моделей на этапе разработки какого-либо продукта [3; 4]. Проблемы стабильности и точности алгоритмов логических операций над полигональными сетками в таких случаях решаются предоставлением дизайнеру нескольких способов обработки, тем самым пользователь выбирает соотношение между качеством и скоростью выполнения данных действий.
Данный вариант реализован в Blender - открытом программном обеспечении для создания трёхмерной компьютерной графики, где имеется два набора алгоритмов, используемых для вычисления логических операций. Carve использует внешнюю библиотеку Carve, а BMesh использует встроенную библиотеку Blender и даёт лучшие результаты [4].
Для пользователей различных симуляторов и игр, не владеющих базовыми навыками ЗБ-моделирования, такие процессы могут вызывать дополнительные сложности. Так же в таких продуктах изменение полигональных сеток может происходить без участия пользователя, предоставляя лишь результаты вычислений. В таком случае важно сохранение приложением свойств системы реального времени. Так же точность алгоритмов может держаться в пределах малоотличимых человеческим глазом.
В игровых движках возможно создание множества типа продуктов, таких как симуляторы различных сфер деятельности человека, игры любых жанров и видов, демонстрации интерьеров или исторических событий и предметов, визуальные материалы: видео, фильмы, мультфильмы [5]. Большинство объектов в игровых движках представляется в виде полигональных сеток. Возможность обрабатывать логические операции над ними в готовых проектах, созданных в такой среде, не теряя свойств системы реального времени увеличило бы реалистичность создаваемых разработчиками виртуальных сцен.
Объектом исследования является реализация инструмента, позволяющая производить булевы операции в реальном времени над двумя полигональными объектами. Предметами исследования являются методы булевых операций, способные производить вычисления в реальном времени.
Целью исследования является создание библиотеки на языке C# в игровом движке Unity для изменения топологической структуры игровых объектов путём применения логических операций.
Для реализации цели были поставлены следующие задачи:
• оценить существующие методы булевых операций над 3D объектами;
• выбрать наиболее подходящий для визуализации в реальном времени метод логических операций над полигональной сеткой;
• задать такую временную характеристики ПО как дедлайн для обеспечения работы в реальном времени;
• разработать алгоритм с использованием найденного метода;
• создать библиотеку для игрового движка Unity с помощью языка программирования C#;
• протестировать реализацию и дать оценку полученному результату.
В данной работе была выделена проблема изменения полигональных моделей при их соприкосновении с другими полигональными объектами. Так как создание универсального инструмента, позволяющего производить булевы операции над полигональными объектами, частично решает данную проблему, была поставлена цель создания библиотеки на языке C# в игровом движке Unity для изменения топологической структуры игровых объектов путём применения логических операций.
Все поставленные цели были достигнуты, а задачи были успешно выполнены. Были изучены новейшие исследования по изменению полигональных трёхмерных моделей с помощью логических операций над ними, выявлены достоинства и недостатки существующих методов решения выделенной проблемы. В данной работе была создана необходимая библиотека классов, способная выполнять быстрые булевы операции:
• объединения,
• разности,
• пересечения.
При условии дальнейшего развития данной работы возможно увеличение стабильности и скорости работы системы с высокополигональными объектами. Поиск новейших методов триангуляции и последующее их применение для полигонов, полученных при их разбиении с помощью, разделяющей плоскости. Создание генератора трёхмерных моделей для дальнейшего изучения достоинств и недостатков реализованной программы.
