Знакомство с воксельной графикой
В процессе поиска алгоритмов расчета коллизий на сайте GameDev, я наткнулся на маленькую статью про движок idTech 6 и заинтересовался воксельной графикой, которую противопоставляют полигональной графике, на которой сейчас основана почти вся компьютерная графика.
Вообще, воксел расшифровывается как "объемный пиксель", однако сейчас под вокселом в основном понимается некий примитив, чаще всего куб или прямоугольный параллелепипед, который имеет определенный размер и цвет. В idTech 6 и в движке Кена Сильвермана Voxlap они хранятся в разреженном октодереве (SVO — sparse voxel octree), что позволяет экономить память и делает возможным простую реализацию "уровня детализации".
Иными словами, вокселы — это такой конструктор LEGO, где из одинаковых деталек разного размера (а также, соеденяя маленькие детальки в большие) можно реализовать самые разнообразные модели, фигуры и т.д.
Одно из самых больших преимуществ вокселей относительно полигонов, то, что их можно разрушать — программа точно знает, что если воксел частично разрушен, то его можно поделить на более мелкие вокселы, которые будут из того же материала, что и их родитель.
Первые попытки
Штурмовать сразу трехмерное пространство я не решился — слишком пугающе выглядел весь тот список формул, которые бы пришлось освоить (о них речь пойдет чуть ниже), и решил просто переписать код, чтобы платформер использовал "боксы" — квадраты, и соответственно хранились не в разреженном октодереве, а в разреженном квадродереве.
Первый код был ужасен — все функции работы с деревом, такие как удаление, обход дерева, создание узлов, были итеративными отдельными от класса QuadTree функциями. В прочем, даже добавление их в пределы класса особо не сыграло роли, так как в последствии выяснилось, что рекурсивные функции сильно выигрывают в данном случае. Единственное, что принесли полезного эти первые попытки — это четкая формулировка, какие функции мне нужны, а также основы реализации деревьев на С++, что в дальнейшем очень помогало и, я надеюсь, еще будет помогать. И, конечно же, именно те первые попытки подтолкнули изучать OpenGL (правда до этого прельстился Direct2D, но очень быстро разочаровался в нем).
Переход в объем
OpenGL я начал изучать на NeHe gamedev и как то очень быстро втянулся в трехмерное пространство и начал планировать движок для Quake-подобной игры. Квадродерево было переписано в октодерево и начались первые сложности. Октодеревья потребляют памяти гораздо больше, и даже не смотря на то, что все основные функции стали рекурсивными, все равно они тратили слишком много времени и памяти. Для решения этой проблемы были реализованы следующие методы:
Оптимизация памяти
В октодереве очень часто приходится использовать операторы new/delete, которые выделяют для указателя место в динамической памяти (куче). Динамическая память медленнее, чем статическая (стек), а также сами функции new/delete выполнялись для меня слишком медленно. Из-за чего был написан собственный класс MemoryPool и шаблон mem_pool_tree.
mem_pool_tree был написан под впечатлением от BST-дерева, с которым я познакомился из книги Т. Кормана "Алгоритмы. Построение и анализ", и не работает напрямую с памятью, а только оперирует цифрами, которые в последствии используются для смещение указателя с начала массива в статической области памяти. Предугадать удаления не представлялось возможным, а вот выделять "правильные" куски памяти было реально, из-за чего я взял у BST дерева идею и повороты, и добавил "блочность" — mem_pool_tree хранит узлы, в котором две переменные хранят начало и конец блока, и еще две переменные — начало и конец занятого пространства. Если происходит попытка удалить кусок в середине занятого пространства, то узел делится, если вызывается функция выделения куска, то алгоритм ищет такой блок, где выделение пространства позволит ему объединится с соседним блоком. И периодически вызывается функция балансировки.
Многопоточность
Из-за строения дерева, в котором у родительского узла есть указатель на массив из восьми дочерних узлов, функции, где требуется полный обход дерева (такие, как удаление всего дерева, удаление лишних элементов, вычисление средних вокселов и т.д.), были написаны с возможностью включить многопоточность. Многопоточность была реализована с помощью OpenMP. К примеру, надо оптимизировать дерево (например, зачем хранить восемь дочерних узлов, если можно их цвет передать родительскому узлу, а их удалить). Реализуем:
class Octree
{
class Node
{
Node * son;
void Optimize();
};
void Optimize()
{
#pragma omp parallel
{
#pragma omp for
for(int n = 0; n<8; ++n)
{
son[n].Optimize();
}
}
}
};Так как дочерние узлы между собой никак не связаны, такая операция не требует мьютексов, что очень хорошо в условиях, когда требуются минимальные затраты памяти.
Загрузка и сохранение вокселей
Долго пришлось искать оптимальный метод хранения вокселей в файле — ведь в условиях, когда оперативная память ценна, хранить лишние вокселы в оперативке является непозволительной роскошью. После долгих исканий, выбор остановился на SQLite3, в котором есть кэширование, а также возможность загрузить только те вокселы, которые требуются исходя из значений "уровня детализации". Самая быстрая работа с SQLite3 базами оказалось при встраивании в проект исходного кода sqlite3 и самостоятельной компиляции (точных цифр не помню, но что то вроде полмиллиона переменных за 200-250 ms, причем на нетбуке с Intel Atom). Естественно, в SQLite3 использовались для ускорения "Begin transaction;", "Commit transaction;", "PRAGMA journal_mode = MEMORY;", "PRAGMA synchronous = OFF;" и т.д.
Скриншоты
Собственно, здесь я покажу небольшие скриншоты, так как дальше идет описания кода, который на стадии реализации. Объекты на скриншотах, конечно, очень простенькие, но единственная причина этого в том, что у меня все не доходят руки нарисовать нормальную сложную модель, или переконвертировать существующие. Более того, это самые первые скриншоты, и для растеризации был написан малюсенький код с использованием GDI, а не OpenGL, и трассировку лучей выполнял самый обычный цикл, в котором расчеты матрицы поворота и прочие расчеты выполнялись на CPU.
Текущие задачи и заключение
Полиморфизм
Сейчас октодерево в очередной раз переписывается с применением полиморфизма. Основная задача — чтобы дерево было не чистым октодеревом, а скрещением с kd-tree (дерево, в котором идет не разбиение воксела на 8 маленьких вокселей, а разбиение на два воксела с определенной пропорцией и по определенной оси), и еще другими модификациями.
RayCasting
Октодерево позволяет Ray Casting, алгоритм "бросания лучей", с помощью которого сейчас пишу растеризатор. Также реализации алгоритма используется OpenGL (генерация текстуры из массива и отображение его на полигоне), "групповая трассировка" и C++ AMP. В целом, эта тема хорошо раскрыта на ray-tracing.ru.
Заключение
В целом, тема интересная, и можно много интересного найти по ней. Например: статья на хабре про движок Atomontage и презентация технологии SVO с SIGGRAPH 2012.
UPD
Написанный мною класс распределения памяти с использованием массива в статической памяти, после замеров, выдал следующие данные:
- удаление 20 млн. объектов по 100 байт каждый (в общей сложности все это занимало более 220 Мб) заняло 2-3 секунды (естественно, объекты удалялись в случайном порядке)
- замеры выделения памяти проводил давно, но последние результаты вроде были 50 млн. объектов по 8 байт за 4-5 секунд
- чтение быстрее, ибо память стека быстрее памяти кучи, но пока тестирую на разном железе, чтобы выяснить среднюю разницу скорости
- при попытке выделить память обычным оператором new из динамической памяти на 50 млн. объектов, программа закидала меня исключениями std::bad_alloc, а когда я написал try-catch, чтобы их обработать, программа нагрузила память настолько, что почти все работающие приложения на компьютере вылетели.