Разъяснение об октодеревьях и о том, как они работают в мире вокселей

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

Вот вопросы, по которым я хочу получить разъяснения:

  • Какой тип структуры данных вы бы использовали? Как можно превратить трехмерный массив вокселей в массив с вокселами разного размера, которые занимают несколько мест в массиве?
  • Что такое узлы и для чего они используются?
  • Соединяет ли октодерево воксели, чтобы были ТОЛЬКО квадратные формы, или это может быть прямоугольник, или L-образная форма, или целый Y-столбец вокселей, или что?
  • Действительно ли октодеревья улучшают производительность воксельной игры? Если да, то на сколько?

multidimensional-array opengl lwjgl voxel octree
person Amit Assaraf    schedule 05.06.2013    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Быстрые ответы:

  • Дерево:
    Каждый узел имеет 8 дочерних узлов, верхний-задний-левый, верхний-задний-правый и т. д. до определенного уровня.
    Код для этого может быть довольно сложным, особенно если воксели могут изменяться в время выполнения.
  • Тип вокселя (цвет, материал, список элементов)
  • Ага. Только кубы
    В частности, 1x1, 2x2, 4x4, 8x8 и т. д. Это должен быть целый узел.
    Если вы действительно хотите, вы можете определить какие-то шаблоны, но это уже не октодерево.
  • да, но это зависит от ваших данных. Представьте, что вы описываете 256 одинаковых блоков по отдельности или один раз (как воздух в Minecraft).

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

person Tom    schedule 05.06.2013

arrow_upward
3
arrow_downward

Правильно выполненное октодерево также может помочь вам с поиском соседей, что позволит вам определить, считается ли лицо «видимым» (т. е. вы получаете видимую оболочку вокселей). После того, как вы установили свое октодерево, вы затем используете его для хранения своих координат XYZ, которые затем извлекаете в один массив. Затем вы загружаете этот массив в свой буфер VERTEX (это требуется для решений GL), который затем вы можете отображать в виде фрагментов по мере необходимости (по мере движения камеры вперед и т. д.).

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

Если все сделано правильно, вы получите множество фрагментов, у которых в буферах вершин видны только внешние «грани». Теперь вам также нужно создать свой собственный алгоритм Occlusion Culling, который затем уменьшает видимость поверх этого, что приводит к меньшему количеству требуемого рендеринга.

Я сделал пример здесь:

https://vimeo.com/71330826

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

person Scott Barnes    schedule 03.08.2013