Я – хакер! Хроника потерянного поколения - Дмитрий Артимович

трехмерная графика так хорошо распараллеливается и рассчитывается на графических процессорах, как раз и заточенных под операции с матрицами.

Возвращаясь к примеру иллюстрации сверху — если сначала отрисовать куб, а потом сферу, все будет так, как надо. А вот если сделать это наоборот, то куб перекроет сферу, хоть и находится позади нее. Все это потому, что компьютер не знает, кто дальше находится от наблюдателя и кого нужно рисовать первым. Конечно, мы можем рассчитывать расстояния до объектов на каждом кадре, но что делать, если объектов слишком много, расчет расстояний для них становится затратным или объекты пересекаются (на рисунке куб заслонил сферу — возникнет артефакт)?

Самый простой алгоритм отсечения невидимых поверхностей — Z-буфер. Идея алгоритма в том, чтобы для каждого видимого пикселя на экране хранить его глубину, координату Z. При отрисовке глубина или значение Z каждого нового пикселя, который нужно занести в буфер кадра, сравнивается с глубиной того пикселя, который уже занесен в Z-буфер. Если новый пиксель расположен ближе к наблюдателю пикселя, находящегося в буфере кадра, то новый пиксель отрисовывается, а значение Z для него обновляется. Если же сравнение дает противоположный результат, то никаких действий не производится. Главное преимущество этого алгоритма — простота, так как все нужные расчеты выполнит сама графическая библиотека и графический ускоритель (при его наличии).

Конечно, такие игры как Quake и Half-Life, имели и программный визуализатор: в них, при отсутствии графического ускорителя, вся графика считалась на центральном процессоре.

Поэтому следующим моим шагом стало изучение алгоритмов, лежащих в основе визуализации Quake. Id Software (разработчик Quake) внесли много передовых технологий в разработку игр. Для визуализации виртуального мира они одними из первых использовали бинарное разделение пространства, популяризовав его.

Алгоритм двоичного разделения пространства (BSP — Binary Space Partition Tree) был первоначально разработан как эффективный метод упорядочивания множества многоугольников для решения проблемы определения видимых поверхностей. Алгоритм использует начальный этап предварительной обработки, что существенно экономит ресурсы при визуализации сцены.

Пусть дан набор многоугольников S = {s1;…; sn}. Мы можем построить BSP-дерево и разделить трехмерное пространство с использованием следующего простого рекурсивного алгоритма. Выбираем многоугольник из множества S. Плоскость, определяемая этим многоугольником, используется для создания корня дерева и делит пространство на два подпространства: заднее и переднее. Ссылка на многоугольник также сохраняется в узле дерева. Остальные многоугольники помещаются в два множества соответственно в зависимости от того, на какой стороне они лежат относительно выбранной плоскости. Любой многоугольник, частично лежащий в обоих подпространствах, разбивается по пересечению с плоскостью, и два фрагмента помещаются в соответствующие множества. Любой многоугольник, который оказался копланарным[9] с корневой плоскостью, сохраняется в корне вместе с корневым многоугольником (Рисунок 1).

Рисунок 1. Разбиение пространства и многоугольников плоскостью, определяемую многоугольником

Эта процедура повторяется рекурсивно снова. Многоугольник выбирается из каждого из двух множеств, а его плоскость образует корень соответствующего поддерева, которое далее разделяет пространство и остальные многоугольники. Это повторяется до тех пор пока не будут задействованы все многоугольники, а исходное пространство не будет разделено на однородные области (ячейки). На рис. 2 ячейки помечены от a до f и показаны как листья дерева.

Рисунок 2. Окончательное разбиение

BSP-дерево, подобное тому, которое построено выше на рис. 1 и 2, мы можем использовать для решения проблемы определения видимых граней. Для этого нужно пройти дерево от любой заданной точки обзора, чтобы получить отсортированный по удаленности к наблюдателю порядок многоугольников, хранящихся в узлах. А затем отрисовать многоугольники в указанном порядке. Многоугольники, находящиеся ближе к наблюдателю, закроют те, что находятся дальше.

Рисунок 3. Прохождение дерева для получения порядка дальше-ближе

Обход основан на том факте, что многоугольники на той же, ближней, стороне, что и точка обзора, не могут быть загорожены многоугольниками на другой стороне, дальней. Итак, чтобы получить обратный порядок многоугольников из дерева, можно использовать простой рекурсивный алгоритм, показанный на рис. 3: сравнить точку обзора с узловой плоскостью. Пройти по дальнему поддереву, отобразить корневой многоугольник(и), а затем пройти по ближнему поддереву.

BSP-деревья решают вопрос сортировки граней по удаленности к наблюдателю, но не решают вопрос отбрасывания невидимых граней. Представьте, что игровой уровень состоит из двух помещений, соединенных коридором. Если игрок находится в помещении 1, он никак не сможет увидеть помещение 2 при условии замкнутости стен. А значит, он не увидит и предметы, и противников, находящихся в помещении 2.

Для определения видимости зон в Quake использовали алгоритм PVS (Potential Visible Set), когда на стадии предварительной обработки для листов BSP-дерева составлялись списки видимых из них других листов дерева. Такая оптимизация дает значительный эффект на больших уровнях, когда отбрасываются значительные части невидимой геометрии. 3D Engine

Editor

Поняв, как работают эти алгоритмы, я решил реализовать их на практике — написать небольшой редактор уровней и визуализатор к нему. Проект назвал Jurassic 3D Engine.

У каждой игры есть свой редактор, где создается геометрия, накладываются текстуры, импортируются модели из 3D Studio Max и т. д. За основу как раз и был взят 3D Studio Max — три проекции и перспектива.

Редактор умел делать базовые вещи:

• создавать примитивы (многоугольники, кубы, сферы, цилиндры);

• накладывать на них текстуры;

• превращать двухмерные многоугольники в трехмерные примитивы вытяжением;

• импортировать сложные модели из 3D Studio Max;

• расставлять источники света.

Весь интерфейс был сделан полностью на OpenGL. На этом редакторе я сделал две небольшие карты: одна с текстурами[10] из Max Payne, вторая — квартира родителей из поселка под Кингисеппом. Под вторую локацию часть текстур пришлось искать в интернете, а другую часть я отснял на цифровую мыльницу. Проблема с отснятым была в том, что при заполнении такой текстурой какой-то поверхности ее противоположные края должны соединяться на стыках без каких-либо графических артефактов.

Завершающим этапом создания карты в редакторе был режим предварительной обработки: построение BSP-дерева, расчет видимости его листьев PVS.

Текстура Наложение текстуры

Rad

Следующий шаг — рассчитать карты освещенности (Lightmaps). Напомню, Lightmap — метод освещения пространства в 3D-приложениях, заключающийся в том, что создается текстура, содержащая