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

9

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

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

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

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

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

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

Спасибо!

Clonkex
источник
1
Вы должны использовать инстансинг для рендеринга ваших кубов. Вы можете найти учебное пособие здесь learnopengl.com/Advanced-OpenGL/Instancing . Для хранения кубов: есть ли у вас сильные ограничения памяти на оборудовании? 16 ^ 3 кубика не кажутся слишком много памяти.
Turms
@ Turms Спасибо за ваш комментарий! У меня нет сильных ограничений памяти, это просто обычный ПК. Но я подумал, что если на каждый верхний кусок приходится 50% воздуха, а мир очень большой, то памяти должно быть немало. Но это, вероятно, не так много, как вы говорите. Так я должен просто пойти на 16 * 16 * 16 кусков со статическим количеством блоков? А также, вы говорите, я должен использовать инстансинг, это действительно нужно? Моя идея состояла в том, чтобы создать сетку для каждого чанка, потому что таким образом я могу пропустить все невидимые треугольники.
6
Я не рекомендую использовать инстансинг для кубов, как описывает Турмс. Это только уменьшит ваши вызовы отрисовки, но ничего не сделает для перерисовки и скрытых граней - фактически это связывает ваши руки от решения этой проблемы, поскольку для инстансинга работают все кубы должны быть одинаковыми - вы не можете удалять скрытые грани некоторых кубов или объединять копланарные грани в большие одиночные многоугольники.
DMGregory
Выбор лучшего воксельного движка может быть сложной задачей. Большой вопрос, который нужно задать себе: «Какие операции мне нужно делать с моими вокселями?» Это направляет операции. Например, вы обеспокоены тем, насколько сложно определить, какой воксель находится в октавном дереве. Алгоритмы Oct-дерева отлично подходят для задач, которые могут генерировать эту информацию по мере необходимости, когда она обходит дерево (часто рекурсивным образом). Если у вас есть конкретные проблемы, когда это слишком дорого, то вы можете посмотреть на другие варианты.
Корт Аммон
Еще один большой вопрос, как часто обновляются вокселы. Некоторые алгоритмы хороши, если они могут предварительно обрабатывать данные для эффективного их хранения, но менее эффективны, если данные постоянно обновляются (как данные могут быть в моделировании жидкости на основе частиц)
Cort Ammon

Ответы:

23

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

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

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

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

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

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

введите описание изображения здесь

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

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

введите описание изображения здесь

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

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

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

Балинт
источник
Спасибо за ответ! Кажется, нужно идти к октри. (Так как мой воксельный движок будет 3D), у меня есть несколько вопросов, которые я хотел бы задать: Ваша последняя картинка показывает черные части с более крупными квадратами, так как я собираюсь иметь подобное Minecraft Двигатель, где вы можете изменять ландшафт вокселов, я бы предпочел, чтобы все, что имеет блок, было одинакового размера, потому что в противном случае это усложнило бы ситуацию, это возможно, верно? (Я бы все же упростил пустые / воздушные слоты курса). Есть ли какой-то учебник о том, как можно запрограммировать октри? Спасибо!
7
@ appmaker1358 это совсем не проблема. Если игрок пытается изменить большой блок, то в этот момент вы разбиваете его на более мелкие блоки . Нет необходимости хранить значения «рок» в формате 16x16x16, когда вместо этого можно сказать «весь этот кусок - сплошная порода», пока это уже не соответствует действительности.
DMGregory
1
@ appmaker1358 Как сказал DMGregory, обновление данных, хранящихся в октодереве, относительно просто. Все, что вам нужно сделать, это разделить ячейку, в которой произошло изменение, до тех пор, пока каждая вложенная ячейка не содержит только один тип блока. Вот интерактивный пример с quadtree . Генерация так же проста. Вы создаете одну большую ячейку, которая полностью содержит чанк, затем вы рекурсивно проходите через каждую конечную ячейку (ячейки, у которых нет дочерних элементов), проверяете, содержит ли часть местности, которую она представляет, несколько типов блоков, если да, подразделяйте камера
Балинт
@ appmaker1358 Большая проблема, на самом деле, в обратном - убедиться, что октре не заполнено листьями только одним блоком, что может легко произойти в игре в стиле Minecraft. Однако есть много решений этой проблемы - это просто выбор того, что вы считаете подходящим. И это становится реальной проблемой только тогда, когда идет много строительства.
Луаан
Octrees не обязательно лучший выбор. вот интересное прочтение: 0fps.net/2012/01/14/an-analysis-of-minecraft-like-engines
Polygnome
7

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
    );
}
ДМГригорий
источник
Спасибо за ответ! Кажется, октри - это путь. Но у меня есть 2 вопроса, вы говорите, что октри быстрее, чем сканирование через массив, и это правильно. Но мне не нужно этого делать, так как массив может быть статическим, то есть я могу рассчитать, где находится куб, который мне нужен. Так зачем мне сканировать? Второй вопрос, на последнем уровне октре (1x1x1), как мне узнать, где находится какой куб, так как, если я правильно понимаю, и у узла октри есть еще 8 узлов, как узнать, какой узел принадлежит какой позиции 3d ? (Или я должен сам это помнить?)
Да, вы уже рассмотрели случай исчерпывающего массива 16x16x16 вокселей в своем вопросе и, по-видимому, отклонили объем памяти 4K на чанк (предполагая, что каждый идентификатор вокселя является байтом) как чрезмерный. Упомянутый вами поиск происходит при сохранении списка вокселей с позицией, заставляя вас сканировать список, чтобы найти воксель в вашей целевой позиции. 4096 здесь - верхняя граница этой длины списка - обычно она будет меньше, чем это, но, как правило, все же глубже, чем соответствующий поиск октодерева.
DMGregory