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 не для всего уровня, а лишь для определённых его частей.[1]
Согласно Crytek, «Sparse Voxel Octree», наряду с «Sparse Surfel Octrees», может стать одной из ключевых технологий хранения и представления данных в компьютерной графике реального времени в будущем. Были выделены её основные преимущества и недостатки.[1]
- Преимущества[1]:
- SVO как структура данных ориентирована в будущее и подходит для альтернативных методов рендеринга;
- очень хорошо подходит для уникальных геометрии и текстур, что будет актуальным в будущем, так как бюджеты на геометрические объекты и текстуры утрачивают свою актуальность;
- Обеспечивает истинную свободу для художников;
- Естественным образом автоматически реализует схему уровня детализации;
- Хорошо подходит для трассировки лучей.
- Недостатки[1]:
- SVO не имеет ни инфраструктуры, ни специализированного аппаратного обеспечения;
- имеет большие требования к памяти;
- все ещё слишком медленная.
Примечания[править | править вики-текст]
- ↑ 1 2 3 4 Джеват Ерли, Антон Капланян. Future graphics in games (англ.) (PPT). Crytek (25 июня 2010 года). — Доклад (презентация), представленный на конференции High Performance Graphics Conference 2010, в котором описываются прошлые и текущие на момент доклада технологии, изобретённые и используемые Crytek, а также рассказывается о перспективных технологиях и подходах, которые появятся в компьютерной графике реального времени в будущем.. Проверено 15 августа 2011.
Ссылки[править | править вики-текст]
- 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.
| Дерево (структура данных) | |
|---|---|
| Двоичное дерево поиска · Дерево (теория графов) · Древовидная структура | |
| Двоичные деревья | Двоичное дерево · T-дерево |
| Самобалансирующиеся двоичные деревья | АА-дерево · АВЛ-дерево · Красно-чёрное дерево · Расширяющееся дерево · Дерево со штрафами · Декартово дерево · Дерево Фибоначчи |
| B-деревья | B-дерево · 2-3-дерево · B+ дерево · B*-дерево · UB-дерево · 2-3-4 дерево · (a,b)-дерево · Танцующее дерево |
| Префиксные деревья | Суффиксное дерево · Radix tree · Ternary search tree |
| Двоичное разбиение пространства | k-мерное дерево · VP-дерево |
| Недвоичные деревья | Дерево квадрантов · Октодерево · Sparse Voxel Octree · Экспоненциальное дерево · PQ-дерево |
| Разбиение пространства | R-дерево · R+-дерево · R*-дерево · X-дерево · M-дерево · Дерево Фенвика · Дерево отрезков |
| Другие деревья | Куча · TTH · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree |
| Алгоритмы | Поиск в ширину · Поиск в глубину · DSW-алгоритм · Алгоритм связующего дерева |
