Хранение вокселей для воксельного движка в C ++

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

Я читал о октреях и из того, что я понимаю, он начинается с 1 куба, и в этом кубе может быть еще 8 кубов, и во всех этих 8 кубах может быть еще 8 кубов и т. Д. Но я не думаю, что это соответствует моему вокселевому движку, мои воксельные кубы / предметы будут одинакового размера.

Поэтому другой вариант - просто создать массив размером 16 * 16 * 16 и иметь один кусок, и вы заполните его элементами. И части, где нет никаких предметов, будут иметь значение 0 (0 = воздух). Но я боюсь, что это приведет к потере большого количества памяти и не будет очень быстрым.

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

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

Но другая проблема - рендеринг. Просто прочитать каждый блок и отправить его в графический процессор с помощью OpenGL легко, но очень медленно. Генерация одного меша на чанк будет лучше, но это означает, что каждый раз, когда я разбиваю один блок, мне приходится перестраивать весь чанк, что может занять некоторое время, вызывая незначительный, но заметный сбой, который я, очевидно, тоже не хочу. Так что это будет сложнее. Так как бы я рендерил кубики? Просто создайте все кубы в одном буфере вершин для каждого чанка и визуализируйте это и, возможно, попытайтесь поместить это в другой поток, или есть другой способ?

Спасибо!

Хранение блоков как позиций и значений на самом деле очень неэффективно. Даже без каких-либо накладных расходов, вызванных используемой структурой или объектом, вам нужно хранить 4 различных значения на блок. Было бы разумно использовать его только для метода «хранение блоков в фиксированных массивах» (тот, который вы описали ранее), когда только четверть блоков являются сплошными, и таким образом вы даже не учитываете другие методы оптимизации. Счет.

Octrees действительно хороши для воксельных игр, поскольку они специализируются на хранении данных с более крупными функциями (например, патчи одного и того же блока). Чтобы проиллюстрировать это, я использовал quadtree (в основном, октре в 2d):

Это мой стартовый набор, содержащий плитки размером 32х32, что равняется 1024 значениям:

Сохранение 1024 отдельных значений не кажется неэффективным, но как только вы достигнете размеров карт, подобных играм, таким как Terraria , загрузка экранов займет несколько секунд. И если вы увеличите его до третьего измерения, оно начнет использовать все пространство в системе.

Quadtree (или октреусы в 3d) могут помочь ситуации. Чтобы создать его, вы можете либо перейти от плиток и сгруппировать их вместе, либо выйти из одной огромной ячейки и разделить ее, пока не дойдете до плиток. Я буду использовать первый подход, потому что его проще визуализировать.

Итак, в первой итерации вы группируете все в ячейки 2x2, и если ячейка содержит только плитки одного типа, вы отбрасываете плитки и просто сохраняете тип. После одной итерации наша карта будет выглядеть так:

Красные линии отмечают то, что мы храним. Каждый квадрат это всего лишь 1 значение. Это уменьшило размер с 1024 до 439, что на 57% меньше.

Но вы знаете мантру . Давайте сделаем еще один шаг и сгруппируем их в ячейки:

Это уменьшило количество хранимых значений до 367. Это всего лишь 36% от исходного размера.

Очевидно, вам нужно делать это деление до тех пор, пока каждая 4 соседняя ячейка (8 смежных блоков в 3d) внутри чанка не будет сохранена в одной ячейке, по существу, преобразовав чанк в одну большую ячейку.

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

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

Тот факт, что ваши воксели имеют одинаковый размер, просто означает, что у вашего дерева фиксированная глубина. например. для блока размером 16x16x16 вам нужно максимум 5 уровней дерева:

• корень чанка (16x16x16)
  • октант первого уровня (8x8x8)
    • октант второго уровня (4x4x4)
      • октант третьего уровня (2x2x2)
        • один воксель (1x1x1)

Это означает, что у вас есть не более 5 шагов, чтобы узнать, есть ли воксель в определенной позиции в чанке:

• корень чанка: является ли весь чанк одинаковым значением (например, весь воздух)? Если так, мы закончили. Если не...
  • Первый уровень: является ли октант, содержащий эту позицию, одним и тем же значением? Если не...
    • второй ярус...
      • третий уровень ...
        • Теперь мы обращаемся к одному вокселю и можем вернуть его значение.

Намного короче, чем сканирование даже на 1% пути через массив до 4096 вокселей!

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

Для обращения к дочерним элементам чанка обычно мы будем действовать в порядке Мортона , что-то вроде этого:

1. X- Y- Z-
2. X- Y- Z +
3. X- Y + Z-
4. X- Y + Z +
5. X + Y- Z-
6. X + Y- Z +
7. X + Y + Z-
8. X + Y + Z +

Итак, наша навигация по узлу Octree может выглядеть примерно так:

GetOctreeValue(OctreeNode node, int depth, int3 nodeOrigin, int3 queryPoint) {
    if(node.IsAllOneValue)
        return node.Value;

    int childIndex =  0;
    childIndex += (queryPoint.x > nodeOrigin.x) ? 4 : 0;
    childIndex += (queryPoint.y > nodeOrigin.y) ? 2 : 0;
    childIndex += (queryPoint.z > nodeOrigin.z) ? 1 : 0;

    OctreeNode child = node.GetChild(childIndex);

    return GetOctreeValue(
                child, 
                depth + 1,
                nodeOrigin + childOffset[depth, childIndex],
                queryPoint
    );
}