[Перевод] Пишем собственный воксельный движок
Примечание: полный исходный код этого проекта выложен здесь: [source].
Когда проект, над которым я работаю, начинает выдыхаться, я добавляю новые визуализации, дающие мне мотивацию двигаться дальше.
После выпуска первоначального концепта Task-Bot [перевод на Хабре] я почувствовал, что меня ограничивает двухмерное пространство, в котором я работал. Казалось, что оно сдерживает возможности емерджентного поведения ботов.
Предыдущие неудачные попытки изучения современного OpenGL поставили передо мной мысленный барьер, но в конце июля я каким-то образом наконец пробил его. Сегодня, в конце октября, у меня уже достаточно уверенное понимание концепций, поэтому я выпустил собственный простой воксельный движок, который будет средой для жизни и процветания моих Task-Bots.
Я решил создать собственный движок, потому что мне требовался полный контроль над графикой; к тому же я хотел себя испытать. В каком-то смысле я занимался изобретением велосипеда, но этот процесс мне очень понравился!
Конечной целью всего проекта была полная симуляция экосистемы, где боты в роли агентов манипулируют окружением и взаимодействуют с ним.
Так как движок уже довольно сильно продвинулся вперёд и я снова перехожу к программированию ботов, я решил написать пост о движке, его функциях и реализации, чтобы в будущем сосредоточиться на более высокоуровневых задачах.
Концепция движка
Движок полностью написан с нуля на C++ (за некоторыми исключениями, например, поиска пути). Для рендеринга контекста и обработки ввода я использую SDL2, для отрисовки 3D-сцены — OpenGL, а для управления симуляцией — DearImgui.
Я решил использовать воксели в основном потому, что хотел работать с сеткой, которая имеет множество преимуществ:
- Создание мешей для рендеринга хорошо мне понятно.
- Возможности хранения данных мира более разнообразны и понятны.
- Я уже создавал системы для генерации рельефа и симуляции климата на основе сеток.
- Задачи ботов в сетке легче параметризировать.
Движок состоит из системы данных мира, системы рендеринга и нескольких вспомогательных классов (например, для звука и обработки ввода).
В статье я расскажу о текущем списке возможностей, а также подробнее рассмотрю более сложные подсистемы.
Класс World
Класс мира служит базовым классом для хранения всей информации мира. Он обрабатывает генерацию, загрузку и сохранение данных блоков.
Данные блоков хранятся во фрагментах (chunks) постоянного размера (16^3), а мир хранит вектор фрагментов, загруженный в виртуальную память. В больших мирах практически необходимо хранить в памяти только определённую часть мира, поэтому я и выбрал такой подход.
class World{
public:
World(std::string _saveFile){
saveFile = _saveFile;
loadWorld();
}
//Data Storage
std::vector chunks; //Loaded Chunks
std::stack updateModels; //Models to be re-meshed
void bufferChunks(View view);
//Generation
void generate();
Blueprint blueprint;
bool evaluateBlueprint(Blueprint &_blueprint);
//File IO Management
std::string saveFile;
bool loadWorld();
bool saveWorld();
//other...
int SEED = 100;
int chunkSize = 16;
int tickLength = 1;
glm::vec3 dim = glm::vec3(20, 5, 20);
//...
Фрагменты хранят данные блоков, а также некоторые другие метаданные, в плоском массиве. Изначально я реализовал для хранения фрагментов собственное разреженное октодерево, но оказалось, что время произвольного доступа слишком высоко для создания мешей. И хотя плоский массив неоптимален с точки зрения памяти, он обеспечивает возможность очень быстрого построения мешей и манипуляций с блоками, а также доступ к поиску пути.
class Chunk{
public:
//Position information and size information
glm::vec3 pos;
int size;
BiomeType biome;
//Data Storage Member
int data[16*16*16] = {0};
bool refreshModel = false;
//Get the Flat-Array Index
int getIndex(glm::vec3 _p);
void setPosition(glm::vec3 _p, BlockType _type);
BlockType getPosition(glm::vec3 _p);
glm::vec4 getColorByID(BlockType _type);
};
Если я когда-нибудь реализую многопоточное сохранение и загрузку фрагментов, то преобразование плоского массива в разреженное октодерево и обратно может быть вполне возможным вариантом для экономии памяти. Здесь ещё есть пространство для оптимизации!
Моя реализация разреженного октодерева сохранилась в коде, поэтому можете спокойно ею воспользоваться.
Хранение фрагментов и работа с памятью
Фрагменты видимы только тогда, когда они находятся в пределах расстояния рендеринга текущей позиции камеры. Это значит, что при движении камеры нужно динамически загружать и составлять в меши фрагменты.
Фрагменты сериализованы при помощи библиотеки boost, а данные мира хранятся как простой текстовый файл, в котором каждый фрагмент — это строка файла. Они генерируются в определённом порядке, чтобы их можно было «упорядочить» в файле мира. Это важно для дальнейших оптимизаций.
В случае большого размера мира основным узким местом является считывание файла мира и загрузка/запись фрагментов. В идеале нам нужно выполнять только одну загрузку и передачу файла мира.
Для этого метод World::bufferChunks() удаляет фрагменты, которые находятся в виртуальной памяти, но невидимы, и интеллектуально загружает новые фрагменты из файла мира.
Под интеллектуальностью подразумевается, что он просто решает, какие новые фрагменты нужно загрузить, сортируя их по их позиции в файле сохранения, а затем выполняя один проход. Всё очень просто.
void World::bufferChunks(View view){
//Load / Reload all Visible Chunks
evaluateBlueprint(blueprint);
//Chunks that should be loaded
glm::vec3 a = glm::floor(view.viewPos/glm::vec3(chunkSize))-view.renderDistance;
glm::vec3 b = glm::floor(view.viewPos/glm::vec3(chunkSize))+view.renderDistance;
//Can't exceed a certain size
a = glm::clamp(a, glm::vec3(0), dim-glm::vec3(1));
b = glm::clamp(b, glm::vec3(0), dim-glm::vec3(1));
//Chunks that need to be removed / loaded
std::stack remove;
std::vector load;
//Construct the Vector of chunks we should load
for(int i = a.x; i <= b.x; i ++){
for(int j = a.y; j <= b.y; j ++){
for(int k = a.z; k <= b.z; k ++){
//Add the vector that we should be loading
load.push_back(glm::vec3(i, j, k));
}
}
}
//Loop over all existing chunks
for(unsigned int i = 0; i < chunks.size(); i++){
//Check if any of these chunks are outside of the limits
if(glm::any(glm::lessThan(chunks[i].pos, a)) || glm::any(glm::greaterThan(chunks[i].pos, b))){
//Add the chunk to the erase pile
remove.push(i);
}
//Don't reload chunks that remain
for(unsigned int j = 0; j < load.size(); j++){
if(glm::all(glm::equal(load[j], chunks[i].pos))){
//Remove the element from load
load.erase(load.begin()+j);
}
}
//Flags for the Viewclass to use later
updateModels = remove;
//Loop over the erase pile, delete the relevant chunks.
while(!remove.empty()){
chunks.erase(chunks.begin()+remove.top());
remove.pop();
}
//Check if we want to load any guys
if(!load.empty()){
//Sort the loading vector, for single file-pass
std::sort(load.begin(), load.end(),
[](const glm::vec3& a, const glm::vec3& b) {
if(a.x > b.x) return true;
if(a.x < b.x) return false;
if(a.y > b.y) return true;
if(a.y < b.y) return false;
if(a.z > b.z) return true;
if(a.z < b.z) return false;
return false;
});
boost::filesystem::path data_dir( boost::filesystem::current_path() );
data_dir /= "save";
data_dir /= saveFile;
std::ifstream in((data_dir/"world.region").string());
Chunk _chunk;
int n = 0;
while(!load.empty()){
//Skip Lines (this is dumb)
while(n < load.back().x*dim.z*dim.y+load.back().y*dim.z+load.back().z){
in.ignore(1000000,'\n');
n++;
}
//Load the Chunk
{
boost::archive::text_iarchive ia(in);
ia >> _chunk;
chunks.push_back(_chunk);
load.pop_back();
}
}
in.close();
}
} Your browser does not support HTML5 video.
Пример загрузки фрагментов при малом расстоянии рендеринга. Артефакты искажения экрана вызваны ПО записи видео. Иногда возникают заметные пики загрузок, в основном вызванные созданием мешей
Кроме того, я задал флаг, сообщающий, что рендерер должен заново создать меш загруженного фрагмента.
Класс Blueprint и editBuffer
editBuffer — это сортируемый контейнер bufferObjects, содержащий информацию о редактировании в мировом пространстве и пространстве фрагментов.
//EditBuffer Object Struct
struct bufferObject {
glm::vec3 pos;
glm::vec3 cpos;
BlockType type;
};
//Edit Buffer!
std::vector editBuffer;
Если при внесении изменений в мир записывать их в файл сразу же после внесения изменения, то нам придётся передавать весь текстовый файл целиком и записывать КАЖДОЕ изменение. Это ужасно с точки зрения производительности.
Поэтому сначала я записываю все изменения, которые нужно внести, в editBuffer при помощи метода addEditBuffer (который также вычисляет позиции изменений в пространстве фрагментов). Прежде чем записывать их в файл, я сортирую изменения по порядку фрагментов, которым они принадлежат по расположению их в файле.
Запись изменений в файл заключается в одной передаче файла, загрузке каждой строки (т.е. фрагмента), для которого имеются изменения в editBuffer, внесении всех изменений и записи его во временный файл, пока editBuffer не станет пустым. Это выполняется в функции evaluateBlueprint(), которая достаточно быстра.
bool World::evaluateBlueprint(Blueprint &_blueprint){
//Check if the editBuffer isn't empty!
if(_blueprint.editBuffer.empty()){
return false;
}
//Sort the editBuffer
std::sort(_blueprint.editBuffer.begin(), _blueprint.editBuffer.end(), std::greater());
//Open the File
boost::filesystem::path data_dir(boost::filesystem::current_path());
data_dir /= "save";
data_dir /= saveFile;
//Load File and Write File
std::ifstream in((data_dir/"world.region").string());
std::ofstream out((data_dir/"world.region.temp").string(), std::ofstream::app);
//Chunk for Saving Data
Chunk _chunk;
int n_chunks = 0;
//Loop over the Guy
while(n_chunks < dim.x*dim.y*dim.z){
if(in.eof()){
return false;
}
//Archive Serializers
boost::archive::text_oarchive oa(out);
boost::archive::text_iarchive ia(in);
//Load the Chunk
ia >> _chunk;
//Overwrite relevant portions
while(!_blueprint.editBuffer.empty() && glm::all(glm::equal(_chunk.pos, _blueprint.editBuffer.back().cpos))){
//Change the Guy
_chunk.setPosition(glm::mod(_blueprint.editBuffer.back().pos, glm::vec3(chunkSize)), _blueprint.editBuffer.back().type);
_blueprint.editBuffer.pop_back();
}
//Write the chunk back
oa << _chunk;
n_chunks++;
}
//Close the fstream and ifstream
in.close();
out.close();
//Delete the first file, rename the temp file
boost::filesystem::remove_all((data_dir/"world.region").string());
boost::filesystem::rename((data_dir/"world.region.temp").string(),(data_dir/"world.region").string());
//Success!
return true;
}
Класс blueprint содержит editBuffer, а также несколько методов, позволяющих создавать editBuffers конкретных объектов (деревьев, кактусов, хижин, и т.д.). Затем blueprint можно преобразовать в позицию, в которую нужно поместить объект, а далее просто записать его в память мира.
Одна из самых больших сложностей при работе с фрагментами заключается в том, что изменения в нескольких блоках между границами фрагментов могут оказаться монотонным процессом со множеством арифметики по модулю и разделения изменений на несколько частей. Это основная проблема, с которой блестяще справляется класс blueprint.
Я активно использую его на этапе генерации мира, чтобы расширить «бутылочное горлышко» записи изменений в файл.
void World::generate(){
//Create an editBuffer that contains a flat surface!
blueprint.flatSurface(dim.x*chunkSize, dim.z*chunkSize);
//Write the current blueprint to the world file.
evaluateBlueprint(blueprint);
//Add a tree
Blueprint _tree;
evaluateBlueprint(_tree.translate(glm::vec3(x, y, z)));
}
Класс world хранит собственный blueprint изменений, внесённых в мир, чтобы при вызове bufferChunks () все изменения записывались на жёсткий диск за один проход, а затем удалялись из виртуальной памяти.
Рендеринг
Рендерер по своей структуре не очень сложен, но для понимания требует знаний OpenGL. Не все его части интересны, в основном это обёртки функциональности OpenGL. Я довольно долго экспериментировал с визуализацией, чтобы получить то, что мне понравится.
Так как симуляция происходит не от первого лица, я выбрал ортографическую проекцию. Её можно было реализовать в формате псевдо-3D (т.е. предварительно спроецировать тайлы и наложить их в программном рендерере), но это показалось мне глупым. Я рад, что перешёл к использованию OpenGL.
Базовый класс для рендеринга называется View, он содержит большинство важных переменных, управляющих визуализацией симуляции:
- Размер экрана и текстуры теней
- Объекты шейдеров, множители приближения камеры, матрицы и т.п.
- Булевы значения для почти всех функций рендерера
- Меню, туман, глубина резкости, зернистость текстур и т.п.
- Цвета для освещения, тумана, неба, окна выбора и т.п.
Кроме того, существует несколько вспомогательных классов, выполняющих сам рендеринг и обёртывание OpenGL!
- Класс Shader
- Загружает, компилирует, компонует и использует шейдеры GLSL
- Класс Model
- Содержит VAO (Vertex Arrays Object) данных фрагментов для отрисовки, функцию создания мешей и метод render.
- Класс Billboard
- Содержит FBO (FrameBuffer Object), в который выполняется рендеринг — полезно для создания эффектов постобработки и наложения теней.
- Класс Sprite
- Отрисовывает ориентированный относительно камеры четырёхугольник, загружаемый из файла текстуры (для ботов и предметов). Также может обрабатывать анимации!
- Класс Interface
- Для работы с ImGUI
- Класс Audio
- Очень рудиментарная поддержка звука (если вы скомпилируете движок, нажмите «M»)
Высокая глубина резкости (DOF). При больших расстояниях рендеринга может быть тормозной, но я всё это делал на своём ноутбуке. Возможно, на хорошем компьютере тормоза будут незаметны. Я понимаю, что это напрягает глаза и сделал так просто ради интереса.
На изображении выше показаны некоторые параметры, которые можно изменять в процессе манипуляций. Также я реализовал переключение в полноэкранный режим. На изображении виден пример спрайта бота, отрендеренного как текстурированный четырёхугольник, направленный в сторону камеры. Домики и кактусы на изображении построены при помощи blueprint.
Создание мешей фрагментов
Изначально я использовал наивную версию создания мешей: просто создавал куб и отбрасывал вершины, не касающиеся пустого пространства. Однако такое решение было медленным, и при загрузке новых фрагментов создание мешей оказывалось даже более узким «бутылочным горлышком», чем доступ к файлу.
Основной проблемой было эффективное создание из фрагментов рендерящихся VBO, но мне удалось реализовать на C++ собственную версию «жадного создания мешей» (greedy meshing), совместимую с OpenGL (не имеющую странных структур с циклами). Можете с чистой совестью пользоваться моим кодом.
void Model::fromChunkGreedy(Chunk chunk){
//... (this is part of the model class - find on github!)
}
В целом, переход к greedy meshing снизил количество отрисовываемых четырёхугольников в среднем на 60%. Затем, после дальнейших мелких оптимизаций (индексирования VBO) количество удалось снизить ещё на ⅓ (с 6 вершин на грань до 4 вершин).
При рендеринге сцены из 5×1x5 фрагментов в окне, не развёрнутом на весь экран, я получаю в среднем около 140 FPS (с отключенным VSYNC).
Хотя меня вполне устраивает такой результат, мне бы по-прежнему хотелось придумать систему для отрисовки некубических моделей из данных мира. Её не так просто интегрировать при greedy meshing, поэтому над этим стоит подумать.
Шейдеры и выделение вокселей
Реализация GLSL-шейдеров — одна из самых интересных, и в то же время самых раздражающих частей написания движка из-за сложности отладки на GPU. Я не специалист по GLSL, поэтому многому приходилось учиться на ходу.
Реализованные мной эффекты активно используют FBO и сэмплирование текстур (например, размытие, наложение теней и использование информации о глубинах).
Мне всё ещё не нравится текущая модель освещения, потому что она не очень хорошо обрабатывает «темноту». Надеюсь, это будет исправлено в дальнейшем, когда я буду работать над циклом смены дня и ночи.
Также я реализовал простую функцию выбора вокселей при помощи модифицированного алгоритма Брезенхэма (это ещё одно преимущество использования вокселей). Она полезна для получения пространственной информации в процессе работы симуляции. Моя реализация работает только для ортографических проекций, но можете ею воспользоваться.
«Выделенная» тыква.
Игровые классы
Создано несколько вспомогательных классов для обработки ввода, отладочных сообщений, а также отдельный класс Item с базовой функциональностью (который будет в дальнейшем расширен).
class eventHandler{
/*
This class handles user input, creates an appropriate stack of activated events and handles them so that user inputs have continuous effect.
*/
public:
//Queued Inputs
std::deque inputs; //General Key Inputs
std::deque scroll; //General Key Inputs
std::deque rotate; //Rotate Key Inputs
SDL_Event* mouse; //Whatever the mouse is doing at a moment
SDL_Event* windowevent; //Whatever the mouse is doing at a moment
bool _window;
bool move = false;
bool click = false;
bool fullscreen = false;
//Take inputs and add them to stack
void input(SDL_Event *e, bool &quit, bool &paused);
//Handle the existing stack every tick
void update(World &world, Player &player, Population &population, View &view, Audio &audio);
//Handle Individual Types of Events
void handlePlayerMove(World &world, Player &player, View &view, int a);
void handleCameraMove(World &world, View &view);
};
Мой обработчик событий (event handler) некрасив, зато функционален. С радостью приму рекомендации по его улучшению, особенно по использованию SDL Poll Event.
Последние примечания
Сам движок — это просто система, в которую я помещаю своих task-bots (подробно о них я расскажу в следующем посте). Но если вам показались интересными мои методы, и вы хотите узнать больше, то напишите мне.
Затем я портировал систему task-bot (настоящее сердце этого проекта) в 3D-мирр и значительно расширил её возможности, но подробнее об этом позже (однако код уже выложен онлайн)!
