Хабрахабр

[Перевод] Пишем собственный воксельный движок

image

Примечание: полный исходный код этого проекта выложен здесь: [source].

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

Казалось, что оно сдерживает возможности емерджентного поведения ботов. После выпуска первоначального концепта Task-Bot [перевод на Хабре] я почувствовал, что меня ограничивает двухмерное пространство, в котором я работал.

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

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

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

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

Концепция движка

Движок полностью написан с нуля на C++ (за некоторыми исключениями, например, поиска пути). Для рендеринга контекста и обработки ввода я использую SDL2, для отрисовки 3D-сцены — OpenGL, а для управления симуляцией — DearImgui.

Я решил использовать воксели в основном потому, что хотел работать с сеткой, которая имеет множество преимуществ:

  • Создание мешей для рендеринга хорошо мне понятно.
  • Возможности хранения данных мира более разнообразны и понятны.
  • Я уже создавал системы для генерации рельефа и симуляции климата на основе сеток.
  • Задачи ботов в сетке легче параметризировать.

Движок состоит из системы данных мира, системы рендеринга и нескольких вспомогательных классов (например, для звука и обработки ввода).

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

Класс World

Класс мира служит базовым классом для хранения всей информации мира. Он обрабатывает генерацию, загрузку и сохранение данных блоков.

В больших мирах практически необходимо хранить в памяти только определённую часть мира, поэтому я и выбрал такой подход. Данные блоков хранятся во фрагментах (chunks) постоянного размера (16^3), а мир хранит вектор фрагментов, загруженный в виртуальную память.

class World{
public: World(std::string _saveFile) //Data Storage std::vector<Chunk> chunks; //Loaded Chunks std::stack<int> 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<int> remove; std::vector<glm::vec3> 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<bufferObject> 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<bufferObject>()); //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) количество удалось снизить ещё на 1/3 (с 6 вершин на грань до 4 вершин).

При рендеринге сцены из 5x1x5 фрагментов в окне, не развёрнутом на весь экран, я получаю в среднем около 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<SDL_Event*> inputs; //General Key Inputs std::deque<SDL_Event*> scroll; //General Key Inputs std::deque<SDL_Event*> 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-мирр и значительно расширил её возможности, но подробнее об этом позже (однако код уже выложен онлайн)!

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть