Как написать воксельный движок

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

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

Дисклеймер: несмотря на многие ограничения и практически отсутствующий инструментарий, этот проект все-таки является 3д-движком, т. к. позволяет в режиме реального времени визуализировать трехмерную сцену. Unity3d используется исключительно как способ доступа к нужным мне технологиям. Штатный рендер Unity не используется.

Немного теории

Рендер трехмерного мира являет собой чрезвычайно сложную задачу, как с точки зрения объема работы, так и с используемого математического аппарата. В связи с этим проще и эффективнее доработать старое двигло с учетом новых технологий, чем писать с нуля движок. Даже самые новые игровые движки, типа CryEngeich, Unity 2015-2020, EU4-5 содержат в своей основе год бородатых годов. А может и не содержат, свечку не держал, исходники не видел. Итак, позволить себе создание нового 3д движка могут или крупные компании или, напротив, инди-студии, которым нечего терять можно и можно пуститься во все тяжкие

Самый распространенным способ описание трехмерной модели объекта является полигональная модель. Модель задается в виде массива вершин и отношений между ними:

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

Другой способ задание трехмерной сцены — это использование так называемых вокселей — трехмерных писелей. В этом случае трехмерная сцена задается как трехмерный массив цветов. Это решение кажется довольно интуитивным, но из-за многих проблем не получило должного распространения. Основным ограничениями являются:

Однако, воксели имеют уникальные положительные стороны:

Как я дошел до жизни такой

Предистория разработки этого движка началась ещё в 2003 году, когда в журнале Game. exe была выпущена статья о разработке компьютерной игры «Периметр: Геометрия войны». В моей памяти навсегда остались описание деформируемого в реальном времени ландшафта, по которому медленно ползут танки, которые обстреливают гаубицы на искусственных насыпях. »Периметр» навеки стал для меня эталоном стратегии, пускай даже сама игра была не столько хороша, как в моих мечтах. Идея использовать ландшафт в качестве основного элемента игрового процесса крепко поселилась в голове. И, когда я в 2019 году узрел на Хабре статьи, посвященные использованию вычислительных шейдеров я понял — настало то самое время. Идея создать свой воксельный движок не имела конкретной цели (вроде создания игры), но начав я уже не мог остановится.

Базовый принцип работы

Сцена для рендера представляет собой Texture3D, т. е. трехмерный массив, где индекс обозначает положение вокселя в трехмерном пространстве, а хранится в нем его цвет в формате RGBA (Red, Green, Blue, Alpha). Размер сцены составляет 256x256x256 вокселей. Для каждого пикселя экрана из точки положения наблюдателя (камеры) выпускается луч, в направлении данного пикселя. Далее в цикле происходит «шагание» по лучу, где читается цвет из трехмерной текстуры, где индекс — это округленные координаты текущей точки. Если прозрачность цвета близка к нулю — то цикл продолжается дальше. Если прозрачность цвета больше нуля — то пиксель закрашивается в этот цвет и цикл прерывается. Вот такой простой алгоритм, дающий, тем не менее рендер в реальном времени. На самом деле я его позаимствовал его из этой статьи.

Так как я статью не понял, у меня получился свой собственный рабочий алгоритм.

Первые шаги

Что бы не тянуть интригу — мне удалось сделать с нуля рабочий рендер 3d сцены на Юнити, собрав при этом чуть ли не все возможные проблемы.

Самого старого варианта, с белым шаром в пустом пространстве, не сохранилось. Однако, и на этом скриншоте видны характерные черты воксельного рендера — угловатость пейзажа и его низкое разрешение. Но картинка есть! Я не знаю, кто будет читать эту статью и настолько мой читатель будет грамотен в вопросах компьютерной графики. Поэтому, я должен сказать, что сделанное мной даже на этапе скриншота — значительный успех. На каждом шагу меня подстерегали неразрешимые проблемы, любая из которых могла меня навсегда остановить, а хитроумным решениям для обхода глюков несть числа. Результатом является стабильный рендер картинки с частотой 30 герц и смутные перспективы на будущее технологии. Останавливаться на достигнутом было слишком просто, к тому же такой результат не годился для практического применения.

Реализация

Иметь алгоритм — это хорошо, но иметь конкретную реализацию — несравнимо лучше. Для простоты я использовал игровой движок Unity. Мой движок состоит из двух основных компонентов — скрипты для управления процессом рендера и compute shader (вычислительный шейдер) для самого процесса рендера. Вычислительный шейдер — это очень полезная и оригинальная технология, которая позволяет запускать на видеокарте любой выполнимый код и возвращать результат обратно на сторону процессора. В отличии от процессора, видеокарта при помощи compute shader может параллельно обрабатывать миллионы потоков, что идеально подходит под задачу. Однако, сложность заключается в том, что вычислительными шейдерами трудно управлять и ещё сложнее отлаживать.

Просто рендера непрозрачных тел не хватает для красивой и убедительной картинки, поэтому следующий логический шаг — это добавление к рендеру освещения. Собственно, освещение — это и есть основная задача 3д-движков. Все графические технологии направлены на улучшение освещения и приближения его к реальной физике распространения света. Для моего случая вполне допустимо использовать простые законы геометрической оптики. Алгоритм:

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

Однако, данный метод можно улучшить, добавив отображение нескольких источников света.

На скриншоте видно две цветные тени от источников света. В общем случае такой эффект некорректен с точки зрения оптики, поскольку тени должны быть черными, а цвет должно иметь освещенное пространство. Дальнейшая работа над освещением — это использование более сложной модели освещения. Прошлая модель не учитывала расстояние от источника света и угол его падения. Новая учитывает это, что позволяет получить более красивую картинку. Для пояснения принципа работы следует рассказать, что такое нормаль. Нормалью называется вектор, который перпендикулярен поверхности и имеет длину, равную единице. По закона оптики, интенсивность освещения поверхности тела пропорциональна скалярному произведению нормали поверхности и луча света. Для создания этого механизма я для каждого вокселя вычислял его нормаль путем проверки его соседей на прозрачность. В итоге я получал карту нормалей всей сцены, которую использовал для дальнейших расчетов. В итоге, лучи света, падающие полого к поверхности, хуже освещают поверхность, чем те, которые падают перпендикулярно. Это создает более правдоподобную картинку и визуально скругляет острые грани.

На рендер на последнем скриншоте — это, пожалуй, предел того, что можно вытащить из расчет освещения в экранным пространстве. Этот метод очень производителен и дает красивую картинку. К моей великой печали, он не позволяет работать с полупрозрачными объектами, а это одно из главных потенциальных достоинств воксельной технологии. Я испробовал много СПОБСобов обойти это ограничение, но лишь доказал, что это невозможно. печальный результат можно увидеть на картинке ниже.

Объемное освещение

Когда я понял фундаментальные ограничения старой системы, то было сложно справится с печалью. Требовалось радикально отойти от старого алгоритма, что бы продвинутся дальше. Мой новый алгоритм (названный «Accumulation de perte de lumière» или «Pertalum») имитирует реальное распространение света. Суть этого алгоритма заключается в использовании особой трехмерной текстуры, названной картой светопотерь. При расчете лучей в эту текстуру сохраняется цвет, который равен потери яркости луча при прохождении через данный воксель. Эти вычисления применяются для всех вокселей сцены. Да, для всех 16 миллионов. Результатом была довольно красивая картинка ценой чудовищных вычислительных затрат.

При запуска получилась приятная картинка и неприятное явление в лице загрузки видеокарты на 100%. Я долго думал как уменьшить загрузку, пока не придумал поистине гениальный план.

Я купил новую видеокарту! RTX2060 (на то время она была весьма мощной).

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

Можно видеть так называемыелучи Бога— безо всяких дополнителньных махинаций, которые нужны в обычном движке.

На данном этапе движок выполняет максимум того, что можно выжать с существующих технологий. Дальнейшее развитие требует совершенно новых решений. Для оптимизации воксельной сцены используется так называемое восьмидрево — древовидная структура данных, в которой сцена разбивается на 8 элементов. Каждый элемент, если он не пустой, так же разбивается на восемь элементов и так до тех пор, пока не будет достигнут некий минимальный размер элемента. Если элемент оказывается пустым (содержит только прозрачные воксели) то он обрабатывается как один воксель и на нем разбиение прекращается. Как вы можете догадаться, до полноценной реализации этого у меня руки не дошли.

Реализация и беды с ней

Создание и отладка двигла — это отдельное сказание, по эпичности сравнимое с Махабарахтой и Рагнарёком. За каждым скриншотом скрывается драма

Разработка движка началась с Unity3d. Звучит немного абсурдно, но этой самый простой способ получить доступ к необходимым мне технологиям. Разумеется, я изучил возможности главного конкурента Unity — Unreal Ingeich (ну ладно, Engine) 4. В Анрыле написание, компиляция и запуск compute shader занимают гораздо больше усилий и сомнительных плюсах. Работа с вычислительными шейдерами в Юнити укладывается в простую последовательность:

В Анрыле для этого надо выполнить множество сложных и неочевидных операций и написать уйму кода, который делает неизвестно что (во всяком случае для меня) и неизвестно как (аналогично). Возможно, подход Анрыла имеет свой плюс. Или даже два плюса (++).

Как я уже писал в прошлой части, Compute Shader — это технология, которая позволяет выполнять на видеокарте любой произвольный код и даже возвращать его на сторону центрального процессора. При обычной работе видеокарта обрабатывает 3д-сцену, формирует картинку и отправляет её в кадровый буффер, после чего она оправляется на монитор. Использование вычислительных шейдеров превращает видеокарту в отдельное вычислительное устройство. Видеокарта из-за особенностей архитектуры идеально приспособлена для параллельного выполнения множества однотипных операций над данными. Например, обработка текстуры (фильтрация, наложение эффектов и т. д.). Возьмем текстуру размером 1024х1024. В этом случае ComputeShader (далее — CS) позволяет параллельно обрабатывать все пиксели, благодаря чему этот процесс завершается за считанные миллисекунды. Центральный процессор может обрабатывать текстуру в 5-10 потоков и завершит работу за несколько секунд, чего недостаточно для создания эффектов в режиме реального времени. Однако, даже CS будет тормозить при слишком большом количестве потоков.

Сам CS представляет собой код, написанный на языке HLSL (англ. высокоуровневый язык шейдеров). Это один из диалектов си, с вырезанной работой с памятью и добавленной векторной арифметикой. CS состоит из глобальных переменных и ядер (kernel). Кернель — это обычная функция, которая имеет параметр id, который имеет уникальное значение для каждого потока. Шейдер запускается на стороне скрипта с указанным количеством потоков. Подробная информация о этой технологии тайной не является и доступна по первым ссылкам в гугле.

Беды

Если бы у меня CS и другие технологии работали точно так же, как и в руководстве — я бы добился бы такого же результата за две недели, а не за три месяца. Среди самых неожиданных проблем:

Физическая симуляция

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

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

Принцип работы физической симуляции был таков:

Я смело предположил, что это должно работать. А на самом деле — нет. Все, что у меня получилось — это сделать падение под действием гравитации и обнаружение столкновений.

Редактор

В процессе работы я сталкивался с тем, что мне надо прямо во время работы добавить или удалить объекты на сцене. Это значит, что пришло время создать 3д-редактор на основе моего движка! На этот раз дело шло безо всяких эпических превозмоганий, некоторую сложность составило создание отката рисования (undo-redo, как в любом редакторе). Захват всей сцены требовам большого объема памяти и на несколько секунд тормозил рендер. Я решил эту проблему сохраняя в памяти только измененный фрагмент сцены.

Сейчас редактор имеет следующие функции:

Ну наверное, все. На этой ноте я прекратил работу над проектом, что бы заняться другим, более важным для себя. Если кому-нибудь нужны исходники — пишите.

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

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

Introduction

This series of posts will focus on creating a voxel engine, from scratch, based on BabylonJS for the low-level 3D routines support.

To begin, here is in the video below, the first target we will have to reach, in order to manage the rendering of the world.

So what is a voxel ?

To keep it simple, a voxel is in 3D what a pixel is in 2D. It is value in grid, in a 3D space.

Strictly speaking, the voxel is like a pixel, in the meaning that it has only one value, its color.

Voxel engines generally have a little more flexibility in the degree to which the display of a voxel is done. It can display a cube single colored, or textured as in Minecraft.

So displaying cubes is not a big deal, isn’t it ?

Short answer : Yes… and no.

A 3D engine, in order to keep a good frame rate, can apply many optimizations to the 3D scene to render.

It can hide the non visible objects, or simplify the objects according to the camera distance.

The problem with voxels is that you will have a very large quantity of cube, so even if you try to hide some of them, you will quickly struggle in rendering speed.

Moreover, a cube is a simple geometric shape, and therefore, simplifying this object cannot be done without severely deforming it. Remove one node and the cube becomes anything you want except… a simpler cube.

So okay, but where to start then?

Let’s start with something basic, which is to define some target functionalities that we are going to implement.

We’re going to take our inspiration from the way Minecraft handles the rendering of worlds in the game, at least in the early versions of the game.

We will try to use as few technical terms as possible, just the bare minimum required, in order to keep all the explanations understandable to everyone.

World structure

The world

A world represents a set of voxels that it will be possible to display.The world is divided into regions.

The region

A region represents a piece of the world. Each region has the same number of voxels. A region is also represented by a 3D coordinate. A region is composed by a data chunk.

A chunk

A chunk is composed of a set of voxels, in a 3-dimensional grid, where each dimension is the same size. This can be simplified as a cube filled with small cubes.

Let’s assume for example that a data chunk is composed of 3 dimensions of size 32. A region thus has 32*32*32 voxels, a total of 32768 voxels.

If our world has 100*100 regions per layer and let’s say 3 layers of height, we will have a total of 100*100*3 regions, so 30000 regions.

Our world will thus have a total of 100*100*3*32768 = 983 040 000 voxels. Our very small world already has close to a billion potential voxels.

Block definition

Our voxel, in our engine, will be presented as a block, more complex in structure than a simple 3D point.

export type Block = {
  name  : string; // Block name
  guid  : string; // Unique global Id
  uid   : number; // Unique local id
  sidesTex : [ // Array of textures
    string, // BACK
    string, // FRONT
    string, // RIGHT
    string, // LEFT
    string, // TOP
    string  // BOTTOM
  ];
  size: [ // Edges size
    number, // WIDTH
    number, // HEIGHT
    number  // DEPTH
  ];
  type    : string; // GAZ, LIQUID, BLOCK
  opacity : number;
  speed   : number; // 0 - 1
};

So we have the smallest usable unit.

Each block will need some data to represent each side, for optimization purpose. Let’s define an enum to represents sides.

export enum Side {
  Left     = 1  ,
  Right    = 2  ,
  Forward  = 4  ,
  Backward = 8  ,
  Top      = 16 ,
  Bottom   = 32 ,
  Z_Axis   = 3  ,
  X_Axis   = 12 ,
  Y_Axis   = 48 ,
  All      = 63
}

Chunk definition

A chunk will store different kind of data, including the full and the optimized version of the blocks.

export type Chunk = {
  position   : Vector3       ; // 3D position in the world
  size       : number        ; // Size of the chunk, default will be 32
  data       : Array<number> ; // The original data
  dataSize   : number        ; // The number of non empty blocks
  rcData     : Array<number> ; // An optimized version of visible only visible data
  rcDataSize : number        ; // The number of visible blocks
  hasRc      : boolean       ; // Define if a chunk has been optimized or not
};

1D array or the power of flattening everything

When dealing with Typescript / Javascript, it is easy to deal with array of array. It seems common to proceed like this.

But here, we need to keep in mind that performance will decrease rapidly as soon as we add new features, so we need to avoid wasting our precious frame per second by taking the easy way out.

Using a one-dimensional array to simulate a 3-dimensional access will always be faster. We will therefore use functions to simplify our work.

/**
 * Convert a vector 3 coordinate to a flat array index
 * @param x {number} The x coordinate
 * @param y {number} The y coordinate
 * @param z {number} The z coordinate
 * @param size {number} The size of each dimension, the size is the same for each one
 */
export function vector3ToArrayIndex(x: number, y: number, z: number, size: number = 32) {
  return (size * size * x) + (size * y) + z;
}

/**
 * Convert a flat array index to a 3D coordinate representation
 * @param index {number} The array index
 * @param size {number} The size of x,y,z dimension
 */
export function arrayIndexToVector3(index: number, size: number = 32) {
  return new BABYLON.Vector3(
    (index / (size * size)) >> 0,
    ((index / size) % size) >> 0,
    (index % size) >> 0
  );
}

This will conclude our introduction. In the next post, we will see how to render our blocks using Babylon Js, and the minimum of 3D terminology necessary to understand the next posts.

Enjoy !

Изначально я использовал наивную версию создания мешей: просто создавал куб и отбрасывал вершины, не касающиеся пустого пространства. Однако такое решение было медленным, и при загрузке новых фрагментов создание мешей оказывалось даже более узким «бутылочным горлышком», чем доступ к файлу.

Основной проблемой было эффективное создание из фрагментов рендерящихся VBO, но мне удалось реализовать на C++ собственную версию «жадного создания мешей» (greedy meshing),

Тут я не совсем понял, что именно в итоге получается. Вот картинка:
http://i.piccy.info/i9/3ed4fab4365bebb9fb194162e75f4b84/1573063991/63783/1346249/collider_mesh.jpg Голубыми линиями показана сетка, которая рендерится, а зелёными ? упрощённая модель для физического движка. У тебя в итоге получается какой вариант?

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