Воксельная графика своими руками — первые шаги

Предисловие

Так получилось, что программированием я стал заниматься совсем недавно — первая книжка по С++ была куплена когда я пошел в 11 класс, в сентябре 2011, а первый работающий «hello_world.exe» скомпилирован только в ноябре. До этого я благополучно потратил 6-7 лет на шутеры, и на экономику, олимпиады по которой обеспечили мне поступление в экономический университет (о котором я уже жалею) и знакомство с группой экономистов, которые параллельно осваивали web-программирование и которые меня подтолкнули изучать программирование.

Осваивать С++ я решил с помощью написания простеньких игрулек, изучая параллельно разные аспекты программирования, которые могли бы понадобиться для их написания.
Первая и вторая были своеобразным клоном игры Pong. Различались между собой только наличием цвета и таймера во второй версии.

Скриншоты

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

Скриншоты

Знакомство с воксельной графикой

В процессе поиска алгоритмов расчета коллизий на сайте GameDev, я наткнулся на маленькую статью про движок idTech 6 и заинтересовался воксельной графикой, которую противопоставляют полигональной графике, на которой сейчас основана почти вся компьютерная графика.
Вообще, воксел расшифровывается как «объемный пиксель», однако сейчас под вокселом в основном понимается некий примитив, чаще всего куб или прямоугольный параллелепипед, который имеет определенный размер и цвет. В idTech 6 и в движке Кена Сильвермана Voxlap они хранятся в разреженном октодереве (SVO — sparse voxel octree), что позволяет экономить память и делает возможным простую реализацию «уровня детализации».

Снеговик из вокселей

Иными словами, вокселы — это такой конструктор LEGO, где из одинаковых деталек разного размера (а также, соеденяя маленькие детальки в большие) можно реализовать самые разнообразные модели, фигуры и т.д.
Одно из самых больших преимуществ вокселей относительно полигонов, то, что их можно разрушать — программа точно знает, что если воксел частично разрушен, то его можно поделить на более мелкие вокселы, которые будут из того же материала, что и их родитель.

Разрушения в тестовой игре на движке Voxlap

Первые попытки

Штурмовать сразу трехмерное пространство я не решился — слишком пугающе выглядел весь тот список формул, которые бы пришлось освоить (о них речь пойдет чуть ниже), и решил просто переписать код, чтобы платформер использовал «боксы» — квадраты, и соответственно хранились не в разреженном октодереве, а в разреженном квадродереве.
Первый код был ужасен — все функции работы с деревом, такие как удаление, обход дерева, создание узлов, были итеративными отдельными от класса 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.

Автор: kaor4bp

Источник