Sparse Voxel Octree

Построение воксельного октодерева

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 не для всего уровня, а лишь для определённых его частей.

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

Преимущества:

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

Недостатки:

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

Ссылки

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