Sparse Voxel Octree (SVO, рус. Разреженное воксельное октодерево) — программная технология, позволяющая делать эффективную детализацию визуализируемых объектов и эффективную обработку облаков точек.

SVO — регулярная иерархическая структура данных, в основе которой лежит регулярная трёхмерная сетка. Первый узел дерева — корень, является кубом, содержащим весь объект целиком. Каждый узел или имеет 8 потомков или не имеет никаких потомков. Эти 8 потомков формируют 2×2×2 регулярных подразбиения родительского узла. Узел с потомками называют внутренним узлом, узел без потомков называют листом. В результате всех подразбиений получается регулярная трёхмерная сетка вокселей, однако, не все воксели содержат части объекта, поэтому в созданном дереве такие воксели не будут содержаться, то есть дерево будет разреженным. Для того, чтобы каждый раз не обрабатывать пустой воксел — вместо сетки используется октодерево, оно также имеет информацию об индексации вокселей и позволяет оптимальным образом находить соседей вокселя и другую информацию.

Использование

Графическая подсистема игрового движка id Tech 6 разработки американской компании id Software будет использовать технологию SVO для визуализации статических объектов, состоящих из вокселей, методом рейкастинга. Благодаря SVO будет обеспечен полностью автоматический Level of Detail. SVO будет работать параллельно с другой эксклюзивной технологией id Software — мегатекстурой.

«Sparse Voxel Octree» в качестве структуры данных используется в игровом движке «CryEngine 3» от немецкой компании Crytek. В отличие от своего классического назначения, в «CryEngine 3» SVO служит не для хранения вокселей, а для хранения полигонов и «запеченных» геометрии и текстур уровня во время его экспорта. Crytek отдала предпочтение технологии SVO, так как она, в отличие от виртуальных текстур, не требует вычислений на графическом процессоре, обеспечивает автоматическое и корректное создание уровней детализации (LOD), предоставляет возможность создания адаптивных геометрических и текстурных деталей в зависимости от геймплея, а также благодаря ей очень легко управлять геометрией и текстурами и производить их «стриминг» (подгрузку в реальном времени во время работы приложения). Вместе с тем было отмечено большое требование к объёму памяти для SVO. Для ликвидации этого недостатка Crytek использовала агрессивное сжатие текстур и применяла SVO не для всего уровня, а лишь для определённый его частей.^[1]

Согласно Crytek, «Sparse Voxel Octree», наряду с «Sparse Surfel Octrees», может стать одной из ключевых технологий хранения и представления данных в компьютерной графики реального времени в будущем. Были выделены её основные преимущества и недостатки.^[1]

Преимущества^[1]:

• SVO как структура данных ориентирована в будущее и подходит для альтернативных методов рендеринга;
• очень хорошо подходит для уникальных геометрии и текстур, что будет актуальным в будущем, так как бюджеты на геометрические объекты и текстуры утрачивают свою актуальность;
• Обеспечивает истинную свободу для художников;
• Естественным образом автоматически реализует схему уровня детализации;
• Хорошо подходит для трассировки лучей.

Недостатки^[1]:

• SVO не имеет ни инфраструктуры, ни специализированного аппаратного обеспечения;
• имеет большие требования к памяти;
• все ещё слишком медленная.

Примечания

Ссылки

• SIGGRAPH 2008: Current and Next Generation Parallelism in Games  (англ.). Архивировано из первоисточника 1 апреля 2012. Проверено 5 июня 2009.
• admin Efficient Sparse Voxel Octrees  (англ.). realtimerendering.com (17 февраля 2010 года). Архивировано из первоисточника 10 апреля 2012. Проверено 8 марта 2010.
• Tero Karras, Samuli Laine, Gregory J. Ward efficient-sparse-voxel-octrees Open-source implementation of "Efficient Sparse Voxel Octrees"  (англ.). Архивировано из первоисточника 10 апреля 2012. Проверено 8 марта 2010.
• Sparse Voxel Octree (SVO) Demo by Jon Olick  (англ.). Архивировано из первоисточника 10 апреля 2012. Проверено 8 марта 2010.
• Samuli Laine, Tero Karras Efficient Sparse Voxel Octrees – Analysis, Extensions, and Implementation  (англ.). Архивировано из первоисточника 10 апреля 2012. Проверено 11 июня 2010.