Воксельные модели введение
Воксел (в разговорной речи воксель, англ. Voxel — образовано из слов: объёмный (англ. volumetric) и пиксел (англ. pixel) — элемент объёмного изображения, содержащий значение элемента растра в трёхмерном пространстве. Вокселы являются аналогами пикселов для трехмёрного пространства.
Вокселы давно используются в компьютерных играх, однако их использование ограниченно из-за серьёзных требований к аппаратной части. Чаще всего в играх вокселы используются для отрисовки моделей. Иногда используются воксельные ландшафты вместо обычного поля высот — это позволяет создавать более сложные пространства с пещерами и мостами. Одной из самых важных возможностей воксельных ландшафтов, интерьеров и объектов является возможность их динамического изменения, и разрушения в реальном времени. В движке Build Engine есть возможность использования воксельных объектов.
Программное обеспечение
Для того чтобы создать и добавить воксельную модель, нам потребуется следующий набор программ:
POLY2VOX – Конвертер полигональных моделей в воксельные, написан самим Кеном. Поддерживаемые форматы трехмерных моделей: *.ASC, *.3DS, *.MD3, *.MD2. Имеется исходный код.
SLAB6 –Редактор от Кена Сильвермана. Позволяет создавать, редактировать и сохранять воксельные модели в несколько форматов. Лучше скачать самую последнюю версию, поскольку в ней была добавлена важная для нас функция изменения размера моделей. В этой статье не будет рассмотрено рисование в данном редакторе– это очень долго, неудобно, а в итоге получается не реалистично. Гораздо лучше использовать полноценные трехмерные редакторы (3d Studio Max, Blender и т.д.), однако SLAB6 необходим для сохранения в правильный формат и назначения нужной палитры для вокселя.
EDITART – Всем известная программа для добавления новых спрайтов в *.ART файлы.
ARTEDIT – Понадобится нам, чтобы назначить воксельный идентификатор добавленному спрайту.
BARF – Необходим для добавления модели в ресурсный архив игры.
Создание воксельной модели Этап 1. Конвертирование
Д
ля примера я буду использовать заранее заготовленную простую полигональную модель ящика, которую можно скачать в главе «Дополнительно». Если же вы хотите использовать другую, но никогда не работали в трехмерных редакторах, могу посоветовать ресурсы проекта «Transfusion». Файлы *.PK3 можно открыть с помощью архиватора WinRar.
Переместите модель и скин в одну папку с конвертером. Важно, чтобы скин был в одной папке с моделью, в противном случае вы получите белый куб.
Откройте файл *.3DS с помощью POLY2VOX и дождитесь конца операции.
Если вы все сделали правильно, после окончания в этой же папке появится файл с расширением *.KVX – это и есть воксельная модель, но прежде чем добавить в игру, нам необходимо ее отредактировать.
Этап 2. Редактирование
Запустите SLAB6, выберите меню «File», щелкните пункт «Open» и выберите вашу *.KVX модель. Скорее всего, вы увидите огромный ящик, который закрывает весь вид.
Дело в том, что все полигональные модели по умолчанию конвертируются с максимальной сеткой, поэтому ширина, высота и объем их всегда будет 128x128x256 (макс. размер модели в Build Engine), что нежелательно, если мы рисуем мелкие объекты.
Если уменьшать ее в редакторе карт – неизбежны подвисания игры и исчезновение моделей прямо перед носом у игрока. Еще хуже, когда Blood начнет вылетать с сообщением о нехватке памяти.
Здесь лучше использовать функцию «Halve Dimensions» (вкладка Tools), что позволяет уменьшать ее в 2 раза.
При слишком сильном уменьшении у сложных моделей может пострадать качество, поэтому оптимальной шириной\высотой модели я считаю – 64x64 и 32×32, а затем, если модель кажется вам большой, ее можно уменьшить вручную в редакторе карт – это гарантировано позволит сэкономить память игры и не слишком ухудшит качество.
До уменьшения После уменьшения
Огромные полигональные модели, например, машины при конвертировании также будут уменьшены до 128x128x256, что приведет к большой потере качества. Фактически вместо сглаженной машины, вы будете видеть пикселы и кубы, поскольку воксельная модель не использует текстурирование, а красит каждый пиксел в свой цвет. Поэтому не стоит использовать слишком большие объекты, либо заранее разделить конвертируемую модель на несколько частей в 3D редакторе.
Следующим шагом на данном этапе будет изменение цветов палитры. Об этой функции лучше не забывать, иначе вы будете видеть «серо-буро-малиново-красный» куб в игре без всякого узора, или того хуже – Blood вообще откажется запускаться.
Щ
елкните вкладку «Tools» и выберите пункт «Replace palette and convert colors». Перед вами появится диалоговое окно, в котором вам будет предложено выбрать палитру. Палитрой может служить скриншот или модель, взятая из Blood. Так же ею может быть файл PALETTE.DAT, который все равно понадобится вам, чтобы работать в EDITART – его-то я и предлагаю использовать в качестве палитры для нашего ящика. После того, как вы изменили палитру, фон станет серым – это значит, что палитра была успешно заменена на выбранную вами. Теперь, для того, чтобы увидеть, как модель будет отображаться в игре, нужно щелкнуть вкладку «View» и убрать галку с пункта «Normal Shading». К сожалению, SLAB6 не сохраняет настройки, поэтому убирать галку придется каждый раз заново, как только вы перезапустите программу.
М
ы подходим к заключительному шагу редактирования – создание спрайта для игры. Для любой модели необходима картинка, которая будет отображаться в редакторе карт, или в игре, если уменьшить уровень детализации. Спрайт желательно сделать того же размера, что и сама модель, чтобы в игре ваши объекты не висели в воздухе, или же наоборот были вмяты в землю. Снова щелкните вкладку «Tools» и нажмите пункт «Adjust Pivots». В левом нижнем углу появятся три окна «Z. \??», «Y:?\??» и «X:?\??», где «?» означает точный размер модели в игре. Нас интересуют последние два значения – именно они определяют ширину и высоту нашего спрайта. Для ящика я использовал значения 64, но вы ограничены только вашей фантазией и возможностями редактора. Создайте спрайт такого же размера (можно сделать скриншот прямо в редакторе) и сохраните его в формате *.GIF. Совсем необязательно обрабатывать его в фотошопе, ведь вместо спрайта в игре будет отображаться модель, но если не хотите чтобы игроки ужаснулись, когда уменьшат детализацию или будут играть с 3DFX патчем, который не поддерживает воксели – рекомендую прочесть эту статью по добавлению спрайтов в игру.
Пишем собственный воксельный движок
Когда проект, над которым я работаю, начинает выдыхаться, я добавляю новые визуализации, дающие мне мотивацию двигаться дальше.
После выпуска первоначального концепта Task-Bot [перевод на Хабре] я почувствовал, что меня ограничивает двухмерное пространство, в котором я работал. Казалось, что оно сдерживает возможности емерджентного поведения ботов.
Предыдущие неудачные попытки изучения современного OpenGL поставили передо мной мысленный барьер, но в конце июля я каким-то образом наконец пробил его. Сегодня, в конце октября, у меня уже достаточно уверенное понимание концепций, поэтому я выпустил собственный простой воксельный движок, который будет средой для жизни и процветания моих Task-Bots.
Я решил создать собственный движок, потому что мне требовался полный контроль над графикой; к тому же я хотел себя испытать. В каком-то смысле я занимался изобретением велосипеда, но этот процесс мне очень понравился!
Конечной целью всего проекта была полная симуляция экосистемы, где боты в роли агентов манипулируют окружением и взаимодействуют с ним.
Так как движок уже довольно сильно продвинулся вперёд и я снова перехожу к программированию ботов, я решил написать пост о движке, его функциях и реализации, чтобы в будущем сосредоточиться на более высокоуровневых задачах.
Концепция движка
Движок полностью написан с нуля на C++ (за некоторыми исключениями, например, поиска пути). Для рендеринга контекста и обработки ввода я использую SDL2, для отрисовки 3D-сцены — OpenGL, а для управления симуляцией — DearImgui.
Я решил использовать воксели в основном потому, что хотел работать с сеткой, которая имеет множество преимуществ:
- Создание мешей для рендеринга хорошо мне понятно.
- Возможности хранения данных мира более разнообразны и понятны.
- Я уже создавал системы для генерации рельефа и симуляции климата на основе сеток.
- Задачи ботов в сетке легче параметризировать.
В статье я расскажу о текущем списке возможностей, а также подробнее рассмотрю более сложные подсистемы.
Класс World
Класс мира служит базовым классом для хранения всей информации мира. Он обрабатывает генерацию, загрузку и сохранение данных блоков.
Данные блоков хранятся во фрагментах (chunks) постоянного размера (16^3), а мир хранит вектор фрагментов, загруженный в виртуальную память. В больших мирах практически необходимо хранить в памяти только определённую часть мира, поэтому я и выбрал такой подход.
Фрагменты хранят данные блоков, а также некоторые другие метаданные, в плоском массиве. Изначально я реализовал для хранения фрагментов собственное разреженное октодерево, но оказалось, что время произвольного доступа слишком высоко для создания мешей. И хотя плоский массив неоптимален с точки зрения памяти, он обеспечивает возможность очень быстрого построения мешей и манипуляций с блоками, а также доступ к поиску пути.
Если я когда-нибудь реализую многопоточное сохранение и загрузку фрагментов, то преобразование плоского массива в разреженное октодерево и обратно может быть вполне возможным вариантом для экономии памяти. Здесь ещё есть пространство для оптимизации!
Моя реализация разреженного октодерева сохранилась в коде, поэтому можете спокойно ею воспользоваться.
Хранение фрагментов и работа с памятью
Фрагменты видимы только тогда, когда они находятся в пределах расстояния рендеринга текущей позиции камеры. Это значит, что при движении камеры нужно динамически загружать и составлять в меши фрагменты.
Фрагменты сериализованы при помощи библиотеки boost, а данные мира хранятся как простой текстовый файл, в котором каждый фрагмент — это строка файла. Они генерируются в определённом порядке, чтобы их можно было «упорядочить» в файле мира. Это важно для дальнейших оптимизаций.
В случае большого размера мира основным узким местом является считывание файла мира и загрузка/запись фрагментов. В идеале нам нужно выполнять только одну загрузку и передачу файла мира.
Для этого метод World::bufferChunks() удаляет фрагменты, которые находятся в виртуальной памяти, но невидимы, и интеллектуально загружает новые фрагменты из файла мира.
Под интеллектуальностью подразумевается, что он просто решает, какие новые фрагменты нужно загрузить, сортируя их по их позиции в файле сохранения, а затем выполняя один проход. Всё очень просто.
Пример загрузки фрагментов при малом расстоянии рендеринга. Артефакты искажения экрана вызваны ПО записи видео. Иногда возникают заметные пики загрузок, в основном вызванные созданием мешей
Кроме того, я задал флаг, сообщающий, что рендерер должен заново создать меш загруженного фрагмента.
Класс Blueprint и editBuffer
editBuffer — это сортируемый контейнер bufferObjects, содержащий информацию о редактировании в мировом пространстве и пространстве фрагментов.
Если при внесении изменений в мир записывать их в файл сразу же после внесения изменения, то нам придётся передавать весь текстовый файл целиком и записывать КАЖДОЕ изменение. Это ужасно с точки зрения производительности.
Поэтому сначала я записываю все изменения, которые нужно внести, в editBuffer при помощи метода addEditBuffer (который также вычисляет позиции изменений в пространстве фрагментов). Прежде чем записывать их в файл, я сортирую изменения по порядку фрагментов, которым они принадлежат по расположению их в файле.
Запись изменений в файл заключается в одной передаче файла, загрузке каждой строки (т.е. фрагмента), для которого имеются изменения в editBuffer, внесении всех изменений и записи его во временный файл, пока editBuffer не станет пустым. Это выполняется в функции evaluateBlueprint() , которая достаточно быстра.
Класс blueprint содержит editBuffer, а также несколько методов, позволяющих создавать editBuffers конкретных объектов (деревьев, кактусов, хижин, и т.д.). Затем blueprint можно преобразовать в позицию, в которую нужно поместить объект, а далее просто записать его в память мира.
Одна из самых больших сложностей при работе с фрагментами заключается в том, что изменения в нескольких блоках между границами фрагментов могут оказаться монотонным процессом со множеством арифметики по модулю и разделения изменений на несколько частей. Это основная проблема, с которой блестяще справляется класс blueprint.
Я активно использую его на этапе генерации мира, чтобы расширить «бутылочное горлышко» записи изменений в файл.
Класс world хранит собственный blueprint изменений, внесённых в мир, чтобы при вызове bufferChunks() все изменения записывались на жёсткий диск за один проход, а затем удалялись из виртуальной памяти.
Рендеринг
Рендерер по своей структуре не очень сложен, но для понимания требует знаний OpenGL. Не все его части интересны, в основном это обёртки функциональности OpenGL. Я довольно долго экспериментировал с визуализацией, чтобы получить то, что мне понравится.
Так как симуляция происходит не от первого лица, я выбрал ортографическую проекцию. Её можно было реализовать в формате псевдо-3D (т.е. предварительно спроецировать тайлы и наложить их в программном рендерере), но это показалось мне глупым. Я рад, что перешёл к использованию OpenGL.
Базовый класс для рендеринга называется View, он содержит большинство важных переменных, управляющих визуализацией симуляции:
- Размер экрана и текстуры теней
- Объекты шейдеров, множители приближения камеры, матрицы и т.п.
- Булевы значения для почти всех функций рендерера
- Меню, туман, глубина резкости, зернистость текстур и т.п.
- Класс Shader
- Загружает, компилирует, компонует и использует шейдеры GLSL
- Содержит VAO (Vertex Arrays Object) данных фрагментов для отрисовки, функцию создания мешей и метод render.
- Содержит FBO (FrameBuffer Object), в который выполняется рендеринг — полезно для создания эффектов постобработки и наложения теней.
- Отрисовывает ориентированный относительно камеры четырёхугольник, загружаемый из файла текстуры (для ботов и предметов). Также может обрабатывать анимации!
- Для работы с ImGUI
- Очень рудиментарная поддержка звука (если вы скомпилируете движок, нажмите “M”)
Высокая глубина резкости (DOF). При больших расстояниях рендеринга может быть тормозной, но я всё это делал на своём ноутбуке. Возможно, на хорошем компьютере тормоза будут незаметны. Я понимаю, что это напрягает глаза и сделал так просто ради интереса.
На изображении выше показаны некоторые параметры, которые можно изменять в процессе манипуляций. Также я реализовал переключение в полноэкранный режим. На изображении виден пример спрайта бота, отрендеренного как текстурированный четырёхугольник, направленный в сторону камеры. Домики и кактусы на изображении построены при помощи blueprint.
Создание мешей фрагментов
Изначально я использовал наивную версию создания мешей: просто создавал куб и отбрасывал вершины, не касающиеся пустого пространства. Однако такое решение было медленным, и при загрузке новых фрагментов создание мешей оказывалось даже более узким «бутылочным горлышком», чем доступ к файлу.
Основной проблемой было эффективное создание из фрагментов рендерящихся VBO, но мне удалось реализовать на C++ собственную версию «жадного создания мешей» (greedy meshing), совместимую с OpenGL (не имеющую странных структур с циклами). Можете с чистой совестью пользоваться моим кодом.
В целом, переход к greedy meshing снизил количество отрисовываемых четырёхугольников в среднем на 60%. Затем, после дальнейших мелких оптимизаций (индексирования VBO) количество удалось снизить ещё на 1/3 (с 6 вершин на грань до 4 вершин).
При рендеринге сцены из 5x1x5 фрагментов в окне, не развёрнутом на весь экран, я получаю в среднем около 140 FPS (с отключенным VSYNC).
Хотя меня вполне устраивает такой результат, мне бы по-прежнему хотелось придумать систему для отрисовки некубических моделей из данных мира. Её не так просто интегрировать при greedy meshing, поэтому над этим стоит подумать.
Шейдеры и выделение вокселей
Реализация GLSL-шейдеров — одна из самых интересных, и в то же время самых раздражающих частей написания движка из-за сложности отладки на GPU. Я не специалист по GLSL, поэтому многому приходилось учиться на ходу.
Реализованные мной эффекты активно используют FBO и сэмплирование текстур (например, размытие, наложение теней и использование информации о глубинах).
Мне всё ещё не нравится текущая модель освещения, потому что она не очень хорошо обрабатывает «темноту». Надеюсь, это будет исправлено в дальнейшем, когда я буду работать над циклом смены дня и ночи.
Также я реализовал простую функцию выбора вокселей при помощи модифицированного алгоритма Брезенхэма (это ещё одно преимущество использования вокселей). Она полезна для получения пространственной информации в процессе работы симуляции. Моя реализация работает только для ортографических проекций, но можете ею воспользоваться.
«Выделенная» тыква.
Игровые классы
Создано несколько вспомогательных классов для обработки ввода, отладочных сообщений, а также отдельный класс Item с базовой функциональностью (который будет в дальнейшем расширен).
Мой обработчик событий (event handler) некрасив, зато функционален. С радостью приму рекомендации по его улучшению, особенно по использованию SDL Poll Event.
Последние примечания
Сам движок — это просто система, в которую я помещаю своих task-bots (подробно о них я расскажу в следующем посте). Но если вам показались интересными мои методы, и вы хотите узнать больше, то напишите мне.
Затем я портировал систему task-bot (настоящее сердце этого проекта) в 3D-мир и значительно расширил её возможности, но подробнее об этом позже (однако код уже выложен онлайн)!
100 Days of Code: Building a Voxel Engine
Over the years, I’ve watched my friends (most recently @geometricdaydream) and various people I follow take on various 30/100/365 day challenges. I’ve always sat in the stands rooting for them and at the same time, wishing I was in the game. Welp, here’s me saying, “Put me in coach!”
I’m taking on the #100daysofcode challenge and I’m doing it for a few reasons:
- Starting is Easy. Finishing is Hard (without some accountability of course). Accountability is always present at work, but rarely for things I do in my spare time. So this is a good way to get some built-in accountability.
- I want some structure to do something related to my work, but just enough outside that it’ll feel fresh, I’ll learn something, and in-turn, help myself personally and professionally.
- I want to engage more on Twitter rather than just use it as a one-way source of information. I’m hoping to connect with other people who are also doing this challenge and also people who know more (or less!) about this subject matter than I do.
Why Voxels?
I follow a lot of graphics and graphics programmer accounts and nothing gets my split-brain going more than some gorgeous #voxelart. Something about the underlying simplicities and complexities of a grid being transformed into a graphically beautiful thing speaks a lot about the nature of computation and representation.
From what I can tell from the outside looking in, there are a lot of interesting optimization problems in this space that I’m looking forward to tackling. My hope is that it will give me quite a confined space to dig deeper into the types of things I deal with on more of a surface level every day, including:
- Efficient representation and transfer of data
- Algorithms specific to graphics programming
- The mathematics behind lighting and materials
- GPU optimization techniques
End Goal
Here’s what I want to do in 100 days: build a basic voxel engine that allows me to create some interesting art in an interactive and performant way.
Is 100 days enough? We’ll find out. It’s purposefully a pretty broad goal and I’m sure I’ll adapt it to the bumps I hit along the way. Looking forward to joining the #100daysofcode challenge and meeting all of you along the way!
Building a voxel engine like Minecraft in Unity (1 of 2)
This is part 1 of 2. These posts are meant to give a basic introduction to voxel engines. In later posts I will dig into optimization techniques and benchmarking.
So its that wonderful time of the year again where I play with something of my own choosing, uninterrupted for a few days. I left my work at work, ignore all the tasks I have to do and dig deep into something that interests me. This is my vacation, my relaxation, my Christmas.
In last years Christmas project I was optimizing a voxel rendering engine. I ran into some issues, and uncovered a problem in Unity 3D’s implementation of structs that I wrote a detailed blog post about and reported to Unity. I’m pleased to see that they have fixed the issue.
Voxels
To give some background: I got interested in developing a voxel game back in 2013. It is one of those things where you can build everything from scratch with code. I spent quite some time on it back then, but after a long period of heavy focus on other work I had forgotten most of the source code and building upon it was difficult. It was my first attempt, and from the perspective of a game it got pretty far.
This video shows some of it. It was functional with multiplayer support.
This year, I want to take last years project one step further. This is a fun activity for playing around with benchmarking to understand the intrinsic of .Net, operating system and hardware.
But first I thought I would give an introduction into how to write a voxel engine, so that the optimizations would make sense for those not familiar with the concept.
The basics of voxel engines
Polygon meshes
Standard 3D graphics is made up of 3D polygon mesh. A polygon mesh usually consists of many triangles that make an object appear solid.
Image source: WikipediaThere are many ways to represent a mesh. One of the most basic mesh formats is storing a list of points in 3D space (vertex), and triangles that form by connecting 3 vertices.
For example a cube would have 8 vertices (one for each corner) and 12 triangles. So a full cube can be described as:
Does it matter what order we address the vertices? Yes. It affects what direction is considered the “front” of the triangle. This affects what angle it will be visible from.
Voxels
Just like an image can be made up of pixels in 2 dimensions, a volumetric shape can be made up of voxels in 3 dimensions. This picture shows one voxel highlighted in red:
Image source: Wikipedia
Graphics cards don’t render voxels directly, so a rendering engine needs to translate voxel data into meshes before it can be rendered as 3D on the screen. The choice of a cube as an example of mesh was not random, and we’ll get back to the actual translation between voxel and polygon mesh in part 2.
Although most people were introduced to voxels through Minecraft, the technology has been around for many years. In the early years a common use was medical scanners, and optimizing it was a matter of saving minutes for every zoom or rotate a doctor made to a scan. A lot of research has been made into rendering voxels, and there are papers out there that detail many different techniques. Today we use it for games, and we are optimizing in the 0-5 ms range.
Voxel storage
Lets just jump straight in and tackle this one first. Lets assume you are using voxels in a game such as Minecraft, so you need to store 1 voxel for each 1x1x1 meter in the world.
If you are storing a world that is (x, y, z) 10x10x10, and each voxel is represented by one byte (8-bit) then you need 1000 bytes of storage. If each voxel is one int (32-bit) then you need 4000 bytes of storage. You would probably want a much larger world than 10x10x10 voxels, so you may need to balance the number of voxel types you support with how much memory you can use. 2 bytes gives you 65536 unique voxel types, and could be a good balance.
If your world is 1.000.000×1.000.000×1.000.000 (1 million meter in each direction) and you use 2 bytes per voxel you end up with 2.000.000.000.000.000.000 bytes, or 2.000.000.000 gigabytes of RAM. Clearly this can be a bit much to load all at once on an average computer.
Even if you size down your world, anything bigger than a few meters means you run into memory access problems. This is because of how modern computers work. I’ll get back to that in discussing cache locality/cache optimized memory access in a later blog post.
So splitting the world into smaller areas (chunks) and loading only the chunks required will make the demand for RAM a bit lighter. One common size is 16x16x16=4096*2=8192 bytes per chunk. If you want to look 10 chunks (160 voxels) in any direction (radius) that is 20 chunks in each axis. This adds up to 20^3=8000 chunks*8192 bytes per chunk=65536000 bytes/1.000.000=65.536 MB (64MB RAM). Most computers can handle 64MB of RAM without any problem, for example my home computer has 64GB of RAM.