Методы отсечения невидимых объектов и поверхностей в Quake
Несмотря на серьезные успехи в области разработки видеокарт и клятвенные заверения разработчиков о двух-трех миллионах полигонов в кадре без особой просадки FPS, на деле всё обстоит не так радужно.
Это зависит и от способов отрисовки, и от кол-ва используемых текстур, и от сложности и кол-ва используемых шейдеров, что в конечном итоге приводит к высоким показателям, только в демках, любезно предложенных самими разработчиками. В подобных демках, какие-нибудь сферические дракончики в вакууме, состоящие из доброй сотни тысяч полигонов действительно рисуются очень быстро, однако реальная игровая ситуация почему-то никогда не похожа на вот этого забавного дракончика из демки, вследствие чего многие товарищи забрасывают разработку своего "убийцы кризиса" уже отрендерив одну комнату с парой источников света, поскольку FPS в этой комнатке даже на ихнем 8800GTS почему-то колеблется в районе 40-60, а после создания второй комнатки падает вообще до 20.
Разумеется было бы некорректным утверждать, что беда таких разработчиков - исключительно в отсутствии грамотного куллинга[1], но вот у тех, кто уже преодолел "синдром первой комнаты", и попытался нарисовать какой-никакой мир, это проблема встаёт особенно остро.
Впрочем, надо оговориться, что Quake, написанный в те далёкие времена, был рассчитан исключительно на "коридорный" тип уровней, поэтому методы отсечения, рассмотренные в данной статье, малоприменимы к ландшафтам, как например в сталкере или кризисе, там работают совершенно другие методы, рассмотрение которых выходит за рамки данной статьи. А мы с вами поговорим именно о классическом коридорном подходе к картостроению и эффективном отсечении невидимых поверхностей, равно как и целых объектов.
Как вам известно, в Quake используется BSP - Binary Spacing Partition tree. Это подразумевает деление трехмерного объекта на определенное кол-во ветвей и листьев. В ветвях обычно содержится информация о поверхностях, которые содержит в себе данная ветвь, а в листья являются пустым пространством, не заполненным ничем. Хотя иногда листья могут содержать в себе например воду (в виде переменной, которая указывает, что вот конкретно в этом листе у нас вода). Так же листы содержат в себе указатель на данные потенциальной видимости (PVS) и список всех промаркированных поверхностей, которые видны из этого листа. Собственно, сам такой подход предполагает, что мы в состоянии нарисовать наш мир, используя как листья, так и ветви. Это особенно хорошо заметно в разных версиях квейка, так как в Q1, мы к примеру в листе лишь помечаем наши поверхности как видимые, а собираем в цепочки для дальнейшего рисования, перебирая последовательно поверхности в ветви, в в то время как в Q3, мы аккумулируем видимые поверхности непосредственно из листа.
Содержание
Отсечение мировых(неподвижных) полигонов
Отсечение невидимых полигонов мира (именно мира, про игровые объекты поговорим чуть ниже), базируется на двух методах. Первый метод - это использование bit векторов видимости (т.н. PVS - Potential Visible Set), второй метод - обычный фруструм куллинг, который к BSP отношения не имеет, но работает ничуть не менее эффективно для оговоренного ряда условий.
PVS
В целом два этих метода обеспечивают практически идеальное отсечение невидимых полигонов, рисуя от громадного мира совсем маленький видимый кусочек. Давайте более подробно рассмотрим как работает PVS. Основная идея PVS - определить видимость одного листа из другого. Средствами BSP это сделать практически невозможно, поскольку листья из совершенно разных веток могут быть видны одновременно и никоим образом выявить закономерность при каких условиях лист из одной ветки может видеть лист из другой ветки не удастся - её попросту нет. Поэтому компилятору приходится пыхтеть за нас, вручную проверяя видимость всех листьев из всех листьев.
Информация о видимости при этом мизерная - одна булевая переменная, принимающая значения 0 и 1. 0 означает что лист не виден, а единичка - что виден. Легко догадаться, что для каждого листа существует уникальный набор таких булевых переменных, размером с общее кол-во листьев на карте. Тогда набор для всех листьев займет места на порядок больше: кол-во листьев умноженное на кол-во листьев и умноженное на размер нашей переменной в которой мы будем хранить информацию о видимости (0\1). А количество листьев, как легко догадаться, определяется размерами карты и компилятором, который по достижению определенного размера перестаёт делить мир и считает конечный узел листом. Размеры листьев разнятся от квейка к квейку.
Так например в первом квейке листья очень маленькие. Скажу для примера, что стандартная карта-коробка делится компилятором аж на четыре листа, в то же время как в третьем квейка подобная карта-коробка займет всего один лист. Но мы отвлеклись.
Прикинем размеры нашего будущего файла с PVS. Предположим у нас среднестатистическая карта, и на ней пара тысяч листьев. Если представить что информация о видимости листа у нас хранится в переменной типа char (1 байт), то размер виздаты для такого вот уровня составит ни много ни мало, а почти 4 мегабайта. То есть охренеть как много. Конечно современный среднестатистический разработчик пожал бы плечами и сжал конечный результат в zip-архив, но в далёком 95 году у конечных пользователей машинки были скромные, памяти мало, и поэтому виздату упаковали более другими способами.
Первый шаг к оптимизации - хранение данных не побайтово, а побитово. Легко догадаться, что подобный подход уменьшил конечный результат аж в 8 раз, ЧСХ - безо всяких ресурсоёмких алгоритмов, типа деревьев Хаффмана. Правда подобный подход несколько ухудшил удобство работы и читабельность кода. К чему я это пишу?
К непониманию многими разработчиками условий, типа: Код:
if( pvs[leafnum>>3] & ( 1<<( leafnum & 7 ))) { }
Собственно это условие реализует простой, красивый и изящный доступ к нужному биту в массиве (как мы помним, адресовать менее одного байта невозможно, только работать с ними через битовые операции).
Таким же образом производится проверка видимой части мира: мы определяем текущий лист, в котором находится игрок (в квейке это реализовано функцией Mod_PointInLeaf), затем мы получаем указатель на виздату для текущего листа (для нашего удобства она прилинкована прямо к листу в виде указателя compressed_vis), затем тупо перебираем все листы и ветви на карте и проверяем их на предмет видимости из нашего листа (это можно увидеть в функции R_MarkLeaves). Если какой-то лист оказывается виден из текущего, то мы присваиваем ему уникальный номер секвенции r_visframecount, которая увеличивается на единичку каждый кадр.
Таким образом мы подчеркиваем, что для построения данного кадра данный лист виден. В следующем кадре r_framecount увеличивается на единичку и все листы становятся снова невидимыми. Как вы понимаете, это намного удобнее и быстрее, нежели в конце кадра заново перебирать все листы и ставить им переменную visible в ноль.
Я обратил внимание на эту особенность, поскольку данный механизм тоже кое-кого смущает и они не понимают как он работает. По помеченным таким образом листьям и ветвям "ходит" функция R_RecursiveWorldNode, отсекая заведомо невидимые листья и накапливая поверхности из видимых.
Первая проверка, конечно же делается на эквивалентность r_visframecount и visframe для рассматриваемого узла. Затем ветвь проходит проверку на пирамиду фруструма, если таковая оканчивается неудачно, то дальше мы по этой ветви не лезем. Наткнувшись на лист, мы также помечаем все принадлежащие ему поверхности, присваивая visframe текущее значение r_framecount (это в дальнейшем поможет быстро определить является ли данная поверхность видимой в текущем кадре, или же нет). Затем, при помощи несложной функции определяем с какой стороны от плоскости ветви мы находимся (каждая ветвь имеет свою плоскость, plane), и добавляем все прилинкованные к ветви поверхности в цепочку для отрисовки (т.н. texturechain), хотя, собственно нам никто не мешает нарисовать их прямо здесь же (в исходниках первого квейка вы увидите оба варианта), но предварительно проведя проверку этих поверхностей на отсечение пирамидой фруструма, ну или хотя бы удостовериться, что поверхность обращена к нам лицом.
В квейке у каждой поверхности есть особый флаг SURF_PLANEBACK, который помогает нам определить ориентацию поверхности. А вот в Quake3 такого флага уже нету, и отсечение поверхностей там работает уже не так эффективно, отправляя на отрисовку их в два раза больше. Впрочем общее их кол-во после проведения всех проверок не так уж и велико. Однако, как ни крути, введение подобной проверки в Xash3D в среднем подняло FPS на карте почти в полтора раза, по сравнению с оригинальным Half-Life. Это к вопросу о том, есть ли от нее какая-то польза или же без разницы. Но мы отвлеклись.
И так после добавления\отрисовки видимых поверхностей, мы снова вызываем R_RecursiveWorldNode, теперь уже на вторую ветвь BSP-дерева. На всякий случай. Потому что там тоже вполне могут оказаться видимые поверхности. Когда рекурсия закончится, у нас в виде результата останется нарисованный мир\цепочки с видимыми поверхностями. Это уже, собственно то что можно подавать на отрисовку через OpenGL\D3D, ну, если мы конечно не нарисовали наш мир прямо внутри функции R_RecursvieWorldNode.
Собственно данный метод успешно используется во всех трех квейках с небольшими модернизациями. Одна из модернизаций заключается в введении т.н. ареапорталов. Это - еще один способ оптимизации, он пришел к нам из второго квейка. Смысл использования ареапорталов заключается в том, что игровая логика может включать\выключать видимость целых секторов по своему усмотрению. Технически это достигается следующим образом: мир делится на зоны, подобно BSP-дереву, однако самих зон не может быть более 256 штук (почему - поясню позже), и они друг с другом никак не связаны. В нормальном режиме видимость определяется точно также как и в Quake1, однако мы можем принудительно заставить компилятор раздробить одну зону (area) на две, установкой специальной энтити func_areaportal. Механизм дробления действует примерно по тому же принципу, что и алгоритм поиска дырок на карте, поэтому обмануть компилятор, поставив func_areaportal посреди чистого поля не получится - он его попросту проигнорирует. Хотя, если сделать его размером с поперечник этого поля (до скайбокса во все стороны), то зоны таки разделятся. Данный приём мы можем наблюдать в Half-Life 2, где попытка вернуться на старые места (при помощи читов, например), демонстрирует нам разъединенные ареапорталы и краткий переход по пустоте из одной зоны в другую. Собственно, именно этот механизм, помог Half-Life 2 успешно имитировать большие пространства при BSP-разбиении уровня (я уже говорил, что для открытых пространств BSP не слишком хорошо подходит).
И так постановленный areaportal принудительно разбивает одну зону на две, разбиение на остальные зоны остается на усмотрение компилятора, который следит, чтобы не выйти за лимит в 256 зон, поэтому их размеры могут быть совершенно разные. Ну и опять таки это зависит от общего размера карты. Наш areaportal связан с какой-нибудь дверью, разделяющей эти две зоны. Когда дверь закрыта - она выключает areaportal, и зоны оказываются разорванными. А следовательно, если игрока нет в отрезанной зоне, то рендерить её целиком не стоит. В Quake1 нам потребовалось бы сделать кучу проверок и возможно отсечь только часть полигонов (ведь сама по себе дверь не является препятствием ни для проверки на видимость, ни уж тем более для фруструма), а тут одна команда - и целая комната исключена из зоны видимости.
Неплохо, скажете вы, но как об этом узнает рендерер? Ведь все наши операции мы производили на сервере и клиенту о них ничего не ведомо. А вот как раз здесь мы и возвращаемся к вопросу, почему зон не может быть более 256. Дело в том, что информация о всей их видимости точно также пакуется в битовые флаги (подобно PVS) и передается в сетевом сообщении на клиент. 256 бит, поделить на 8 это 32 байта, что в целом не так уж и много. Кроме того хвост этой информации может быть легко отсечен, если в нём находятся одни нули. Правда расплатой за такую оптимизацию станет лишний байт, который придется передать по сети, чтобы указать реальный размер сообщения о видимости наших зон. Но в целом оно себя оправдывает.
Фруструм куллинг
Второй метод оптимизации заключается, как я уже и говорил, в увеличении размеров конечных листьев в Quake3. Считается, что видеокарта определенный объем полигонов нарисует гораздо быстрее, чем проверять на CPU, видны они или же нет. Это исходит из самой концепции проверки видимости, согласно которой, если проверка на видимость отнимает больше времени, чем собственно, отрисовка, то ну её к ч0рту такую проверку. Спорность такого подхода определяется наличием широкого ряда видеокарт у конечных юзеров, а особенно нахлынувшей моде на ноутбуки и нетбуки, где видеокарта - понятие очень условное и очень слабое (не смотри, что третьи шейдеры держит).
Поэтому для настольных геймерских машин эффективнее нарисовать больше за один раз, а вот для слабеньких видеокарт ноутбуков, всё-таки надежнее традиционный куллинг. Хотя бы и такой, как я описал выше. Правда стоит еще упомянуть о принципах работы фруструм куллинга, возможно кому-то они непонятны.
Собственно отсечение по пирамиде фруструма - чистая математика, безо всяких предрасчетов компилятора. Из текущего направления взгляда игрока строится пирамида отсечения (пирамида если вдруг кто не понял, своей верхушкой ориентирована к точке взгляда игрока, а её основание - по его направлению). Пирамида может быть острой и тупой - это, как вы уже наверное догадались, зависит от FOV игрока. Кроме того, её дальнюю стенку можно принудительно придвигать к себе поближе (да-да, тот самый параметр MaxRange у worldspawn). Разумеется аналогичную пирамиду строит себе и OpenGL для своих внутренних нужд, беря информацию из матрицы проекции, но мы сейчас про локальную. Готовая пирамида состоит из 4-6 плоскостей (quake1 использует всего 4 плоскости, доверяя OpenGL самостоятельно отсекать дальние и ближние полигоны, но если вы в своем рендерере собираетесь делать поддержку зеркал и порталов, то вам понадобится шесть плоскостей, как раз для этих случаев). Ну а сам тест на фруструм - элементарная проверка на попадание AA-ящика в пирамиду фруструма. Или, выражаясь корректнее, - на их пересечение. Напомню, что каждая ветвь имеет свои размеры, которые собственно и проверяются на пересечение.
Но к сожалению тест на фруструм имеет один принципиальный недостаток - он не может отсекать то, что находится прямо по взгляду игрока. Мы можем регулировать дистанцию отсечения, даже сделать такой финт ушами как в QFusion, когда там каждый кадр перед отрисовкой выявлялось конечное значение zFar и потом учитывалось при клиппинге энтить, но ведь само-то значение, как ни крути было получено с учетом PVS-информации. Поэтому ни один из двух этих методов не заменяет другой, они взаимно друг-друга дополняют. Об этом следует помнить.
Отсечение подвижных объектов
С отрисовкой мира, вроде бы разобрались, теперь плавно переходим к отсечению подвижных объектов, коими являются все видимые объекты в мире. Даже те, которые на первый взгляд стоят неподвижно и никуда перемещаться не собираются. Игрок-то движется! С одной точки он видит этот неподвижный объект, с другой, понятное дело, не видит. Этот момент тоже следует учитывать. Собственно о механизме проверки объектов на видимость я подробно рассказал уже в начале нашей статьи - находим видимый лист для игрока, находим видимый лист для энтити и посредством виздаты проверяем видят ли они друг-друга.
Хотелось так же уточнить (если вдруг кто-то не понял), что движущаяся энтить получает текущий видимый лист для себя, непосредственно для своего текущего положения, а сами листы, конечно же неподвижны и всегда находятся на одном и том же месте. Так вот. В вышеописанном методе потенциально кроются две проблемы. Первая проблема заключается в том, если A равно B, то B далеко не всегда равно A. Иными словами, энтить A может видеть энтить B, но это еще не значит, что энтить B видить энтить A. Почему такое происходит? Чаще всего по двум причинам. Первая причина заключается в том, что оригин одной из энтить плотно сидит в стенке, и Mod_PointInLeaf выдает для него наружный лист, из которого видно ВСЁ (ну кто из вас не летал вокруг карты?). В то же время, изнутри карты ни один из листьев увидеть наружный не в состоянии - этим, собственно, и объясняется тот интересный факт, что при вылете за пределы карты вся геометрия становится видимой, а все объекты наоборот пропадают. В штатном режиме схожие проблемы могут возникать у объектов, прикрепленных или утопленных в стенку. Например пропадание звуков у нажатой кнопки\двери, поскольку её текущая позиция выходит за границы мира.
С данным явлением борются, меняя местами объекты A и B, либо получая альтернативные точки для позиции объекта, но всё это не слишком надежно. Кроме того, как я говорил, существует еще и другая проблема. Она заключается в том, что далеко не каждая энтить помещается в одном листе. Это игрок маленький, он всегда может находится только в одном листе (ну в самом крайнем случае - в двух, на границе между водой и воздухом. С этим явлением, кстати, борются разными хаками), а вот какой-нибудь гигантский тентакль, или наоборот лифт в виде двери запросто может занимать 30-40 листьев одновременно. Проверка одного листа (например того, которому соответствует центр модели), будет неизбежно приводить к плачевному результату - как только позиция объекта окажется вне зоны видимости игрока, объект исчезнет полностью.
Самый распространенный случай - пресловутый func_door, устроенный как лифт. В Quake на e1m1 такой имеется. Вот он проезжает половину своего пути, оригин его оказывается за пределами карты и он должен исчезнуть из поля видимости игрока. Однако же он никуда не исчезает, правда? Рассмотрим более подробно, как это сделано. Самая простая мысль, которая приходит на ум - раз уж объект занимает несколько листьев, то нам надо сохранить их все куда-нибудь в структуру объекта и проверять по очереди. Если хотя бы один из этих листьев виден, значит виден и весь объект (например его краешек). Именно так и было реализовано в Quake: статичный массив на 16 листьев и простенькая рекурсивная функция SV_FindTouchedLeafs, которая ищет все листья в объеме, жестко заданные перемеными pev->absmins и pev->absmax. Эти переменные пересчитываются каждый раз при вызове SV_LinkEdict (или более частный случай UTIL_SetOrigin). Отсюда вполне закономерный вывод, что простая смена оригина без пересчета видимых листьев, рано или поздно выведет объект из зоны видимости, даже если технически игрок его всё равно видит. Это к вопросу зачем нужно вызвать UTIL_SetOrigin, не проще ли присваивать pev->origin новые значения, без вызова этой функции. Используя данный метод мы превоходно решаем обе вышеописанных проблемы - боремся с пропадаеним видимости, если оригин объекта ушел за границы мира и нивелируем разницу между сравнением A->B и B->A. Правда нас подстерегает еще одна проблема, которая проявляется далеко не сразу. Как вы помните у нас массив на 16 листьев. А что будет, если его не хватит? В Quake1 слава богу нету лучей, да и сильно длинных лифтов, изготовленных при помощи func_door, тоже нету. Вот как раз по этой причине. Потому что при заполнении массива до отказу, функция SV_FindTouchedLeafs просто прекращает свою работу и нам остается только надеятся, что случаев когда объект исчезнет прямо на наших глазах будет не так уж и много. Но в оригинальном первом квейке таких случаи вполне могут быть.
В Half-Life положение еще хуже - как вы помните, там есть лучи, которые тянутся на полкарты, например от tripmine. При этом вполне может случится ситуация, когда мы видим самый краешек луча. Для большинства таких лучей 16 листьев явно недостаточно. Valve попыталась исправить ситуацию, увеличив массив до 48 листьев. Помогло. На первых картах. Если вы помните в самом начале игры, когда игрок уже слез с вагончика, он заходит в такой эпичный лифт, который везет его вниз. Лифт сделан дверью и занимает ровно 48 листьев. По-видимому финальное расширение массива было ориентировано именно на его размеры. Потом программисты сообразили, что это не дело, сколько ни расширяй, а всё равно куда-нибудь да не хватит. И прикрутили альтернативный метод проверки видимости по головной ветви - headnode. Вкратце, это тот же SV_FindTouchedLeafs, только с непосредственным вызовом по месту проверки видимости и передачей туда виздаты. В целом он используется не слишком часто, поскольку медленнее проверки заранее накопленных листьев, то есть только вот для таких случаев.
Заключение
Ну и поскольку, я надеюсь, у вас уже начала вырисовываться общая картина о механизме отсечения, закончу в нескольких словах. Все объекты, прошедшие проверку на видимость на сервере добавляются в сетевое сообщение, содержащее информацию о видимых объектах.
Таким образом список видимых энтить на клиенте оказывается уже отсечен по PVS, и нам не надо делать это заново на клиенте. Достаточно простой проверки на фруструм. Вы спросите, а почему же нам непременно надо было отсекать объекты на сервере, когда можно было и на клиенте?
Отвечаю, можно да, но отсеченные объекты, таки не попали в сетевое сообщение, и сэкономили нам траффик. а поскольку игрок их всё равно не видит, то какой же смысл передавать их на клиент, чтобы потом отсекать по видимости? Вот такая двойная оптимизация.
На этом, пожалуй, закончу. Если у вас остались какие-то вопросы либо неясные моменты, просьба задать их прямо в теме, постараюсь ответить.
