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

Примечание: полный исходный код этого проекта выложен здесь: [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<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();
    }
}

Пример загрузки фрагментов при малом расстоянии рендеринга. Артефакты искажения экрана вызваны ПО записи видео. Иногда возникают заметные пики загрузок, в основном вызванные созданием мешей

Кроме того, я задал флаг, сообщающий, что рендерер должен заново создать меш загруженного фрагмента.

Класс 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-мир и значительно расширил её возможности, но подробнее об этом позже (однако код уже выложен онлайн)!