Я – хакер! Хроника потерянного поколения

Самый простой алгоритм отсечения невидимых поверхностей — 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