Я с удовольствием погрузился в изучение исходного кода Quake World и изложил в статье всё, что я понял. Надеюсь, это поможет желающим разобраться. Эта статья разделена на четыре части:
- Архитектура
- Сеть
- Прогнозирование
- Визуализация
Архитектура
Клиент Quake
Изучение Quake стоит начать с проекта
qwcl (клиента). Точка входа WinMain находится в sys_win.c. Вкратце код выглядит так:
WinMain
{
while (1)
{
newtime = Sys_DoubleTime ();
time = newtime - oldtime;
Host_Frame (time)
{
setjmp
Sys_SendKeyEvents
IN_Commands
Cbuf_Execute
/* Сеть */
CL_ReadPackets
CL_SendCmd
/* Прогнозирование//коллизии */
CL_SetUpPlayerPrediction(false)
CL_PredictMove
CL_SetUpPlayerPrediction(true)
CL_EmitEntities
/* Визуализация */
SCR_UpdateScreen
}
oldtime = newtime;
}
}
Здесь мы можем выделить три основных элемента Quake World:
- Сеть
CL_ReadPacketsиCL_SendCmd - Прогнозирование
CL_SetUpPlayerPrediction,CL_PredictMoveиCL_EmitEntities - Визуализация
SCR_UpdateScreen
Сетевой слой (также называемый Net Channel) выводит информацию о мире в переменную
frames (массив frame_t). Они передаются в слой прогнозирования, в котором обрабатываются коллизии, и данные выводятся в форме указаний о видимости (cl_visedicts) с определением области видимости (POV). VisEdicts используются в слое визуализации вместе с переменными POV (cl.sim*) для рендеринга сцены.
setjmp:
Установка промежуточной точки кода, если случается что-то плохое, то программа возвращается сюда.
Sys_SendKeyEvents:
Получение сообщений ОС Windows, сворачивание окна и т.п. Соответствующее обновление переменной движка (например, если окно свёрнуто, то мир не рендерится).
IN_Commands:
Получение информации о вводе с джойстика.
Cbuf_Execute:
В каждом цикле игры выполняются команды в буфере. Команды генерируются в основном через консоль, но могут прийти и от сервера или даже от нажатия клавиши.
Игра начинается с exec quake.rc в буфере команд.
CL_ReadPackets и CL_SendCmd:
Обработка сетевой части движка.
CL_SendCmd перехватывает ввод мыши и клавиатуры, генерирует команду, которая затем отправляется.
Поскольку в Quake World использовался UDP, надёжность передачи гарантировалась набором sequence/sequenceACK в заголовках пакетов netChannel. Кроме того, последняя команда систематически отправлялась повторно. Со стороны клиента не было никаких ограничений на передачу пакетов, обновления отправлялись как можно чаще. Со стороны сервера сообщение клиенту отправлялось только если пакет был получен и скорость отправки была ниже скорости обработки. Этот предел устанавливался клиентом и отправлялся на сервер.
Весь раздел «Сеть» посвящён этой теме.
CL_SetUpPlayerPrediction, CL_PredictMove и CL_EmitEntities:
Выполняли прогнозирование в движке и расчёт коллизий. В основном они предназначены для борьбы с латентностью передачи по сети.
Этой теме посвящён весь раздел «Прогнозирование».
SCR_UpdateScreen:
Визуализация в движке. В этой части активно используются BSP/PVS. Здесь происходит ветвление кода на основании include/define. Движок Quake может рендерить мир или программно, или с аппаратным ускорением.
Этому целиком посвящён раздел «Визуализация».
Открытие архива zip и компилирование
Открытие zip:
В архиве q1sources.zip есть две папки/два проекта Visual Studio: QW and WinQuake.
WinQuake— это код с объединённым кодом клиента и сервера, работающий как единый процесс (в идеале это должны быть два отдельных процесса, если DOS поддерживала их). Игра по сети была возможна только в LAN.QW— это проект «Quake World», в котором сервер и клиент должны выполняться на отдельных машинах (заметьте, что точка входа клиента — этоWinMain(вsys_win.c), а точка входа сервера —main(тоже вsys_win.c)).
Я изучил Quake World с рендерингом openGL. В этом проекте есть четыре подпроекта:
gas2asm— утилита для портирования ассемблерного кода из GNU ASM в x86 ASMqwcl— клиентская часть QuakeQWFwd— прокси, расположенный перед серверами Quakeqwsv— серверная часть Quake
Компиляция:
После установки Windows и SDK DirectX компиляция в Visual Studio 2008 выявляет одну ошибку:
.\net_wins.c(178) : error C2072: '_errno' : initialization of a function
В настоящее время
_errno — это макрос Microsoft, используемый для чего-то другого. Можно исправить эти ошибки, заменив имя переменной с _errno например на qerrno.
net_wins.c
if (ret == -1)
{
int qerrno = WSAGetLastError();
if (qerrno == WSAEWOULDBLOCK)
return false;
if (qerrno == WSAEMSGSIZE) {
Con_Printf ("Warning: Oversize packet from %s\n",
NET_AdrToString (net_from));
return false;
}
Sys_Error ("NET_GetPacket: %s", strerror(qerrno));
}
Компоновщик жалуется на LIBC.lib в проекте qwcl. Просто добавьте его в список игнорируемых библиотек «Ignored Library» и сборка четырёх проектов выполнится.
Инструменты
В качестве IDE замечательно подошла Visual Studio Express (бесплатная). Рекомендую прочитать несколько книг, если вы хотите глубже разбираться в движке на основе BSP/PVS, Id Software и Quake:
Моя полка с книгами на неделе работы с исходным кодом Quake выглядела так:
Сеть
Сетевая архитектура QuakeWorld в своё время считалась потрясающей инновацией. Во всех последующих сетевых играх использовался тот же подход.
Сетевой стек
Элементарной единицей обмена информацией в Quake была
команда. Они используются для обновления положения, ориентации, здоровья, ущерба игрока и т.д. В TCP/IP есть множество отличных функций, которые пригодились бы в симуляции реального времени (контроль передачи, надёжность доставки, сохранение порядка пакетов), но в движке Quake World этот протокол нельзя было использовать (он использовался в оригинальном Quake). В шутерах от первого лица информация, не полученная вовремя, не стоит повторной пересылки. Поэтому был выбран UDP/IP. Для обеспечения надёжности доставки и сохранения порядка пакетов создали сетевой слой абстракции "NetChannel".
С точки зрения OSI NetChannel удобно расположен поверх UDP:
Итак, подведём итог: движок в основном работает с командами. Когда нужно отправить или получить данные, он поручает эту задачу методам Netchan_Transmit и Netchan_Process из netchan.c (эти методы одинаковы для клиента и сервера).
Заголовок NetChannel
Заголовок NetChannel имеет следующую структуру:
| Битовое смещение | Биты 0-15 | 16-31 |
|---|---|---|
| 0 | Sequence | |
| 32 | ACK Sequence | |
| 64 | QPort | Команды |
| 94 | ... | |
- Sequence — это число
int, инициализируемое отправителем и увеличивающееся на единицу при каждой отправке пакета.Sequenceиспользуется во многих целях, но самая важная задача — предоставить получателю возможность распознавания утерянных/дублированных/внеочередных пакетов UDP. Самый значимый бит этого целого числа является не частью sequence, а флагом, указывающим на то, содержит ли (команда) надёжные данные (подробнее об этом позже). - ACK Sequence — это тоже
int, оно равно последнему полученному числу sequence. Благодаря ему другая сторона NetChannel может понять, что пакет был утерян. - QPort — это обход ошибки маршрутизаторов NAT (подробнее см. в конце раздела). Его значение — случайное число, задаваемое при запуске клиента.
- Команды: передаваемые значимые данные.
Надёжные сообщения
Ненадёжные команды группируются в пакет UDP, он помечается последним исходящим числом sequence и отправляется: отправителю не важно, будет ли он потерян. Надёжные команды обрабатываются иначе. Главное — понять, что между отправителем и получателем может быть только один неподтверждённый надёжный пакет UDP
В каждом игровом цикле при генерировании новой надёжной команды она добавляется в массив message_buf (управляемый через переменную message) (1). Набор надёжных команд затем перемещается из message в массив reliable_buf (2). Это происходит только если reliable_buf пуст (если он не пуст, это значит, что ранее был отправлен другой набор команд и его получение пока не подтверждено).
Затем формируется окончательный пакет UDP: добавляется заголовок NetChannel (3), затем содержимое reliable_buf и текущие ненадёжные команды (при наличии достаточного места).
На принимающей стороне сообщение UDP парсится, входящее число sequence передаётся в исходящее sequence ACK (4) (вместе с битовым флагом, указывающим на то, что пакет содержит надёжные данные).
При следующем получаемом сообщении:
- Если битовый флаг надёжности имеет значение true, это значит, что пакет UDP доставлен получателю. NetChannel может очистить
reliable_buf(5) и готов к отправке нового набора команд. - Если битовый флаг надёжности имеет значение false, то пакет UDP не дошёл до получателя. NetChannel делает повторную попытку отправки содержимого
reliable_buf. Новые команды накапливаются вmessage_buf. Если массив переполняется, то клиент сбрасывается.
Контроль передачи
Насколько я понял, контроль передачи выполняется только на стороне сервера. Клиент отправляет обновления своего состояния как можно чаще.
Первое правило контроля передачи, активное только на сервере: отправлять пакет, только если пакет был получен от клиента. Второй тип контроля передачи — это «choke», параметр, который клиент устанавливает командой консоли rate. Он позволяет серверу пропускать сообщения обновлений, уменьшая количество данных, отправляемых клиенту.
Важные команды
Команды содержат код типа, хранящийся в
байте, за которым следует полезная информация команды. Наверно, самыми важными являются команды, дающие информацию о состоянии игры (frame_t):
svc_packetentitiesиsvc_deltapacketentities: обновляют такие объекты, как следы от ракет, взрывы, частицы и т.д.svc_playerinfo: отправляет обновления о положении игрока, последней команде и длительности команды в миллисекундах.
Подробнее о qport
Qport был добавлен в заголовок NetChannel для исправления ошибки. До qport сервер Quake идентифицировал клиента по комбинации «удалённый IP-адрес, удалённый порт UDP». Чаще всего это работало хорошо, но некоторые маршрутизаторы NAT могут произвольно менять свою схему трансляции портов (удалённого порта UDP). Порт UDP становится ненадёжным, и Джон Кармак (John Carmack) объяснил, что он решил идентифицировать клиент по «удалённому IP-адресу, Qport в заголовке NetChannel». Это исправило ошибку и позволило серверу на лету изменять целевой порт ответа UDP.
Вычисление латентности
Движок Quake хранит 64 последних отправленных команды (в массиве
frame_t: frames) вместе с senttime. К ним можно получить доступ непосредственно по числу sequence, использованному для их передачи (outgoing_sequence).
frame = &cl.frames[cls.netchan.outgoing_sequence & UPDATE_MASK];
frame->senttime = realtime;
//Отправка пакета серверу
После получения подтверждения от сервера время отправки команды получается из
sequenceACK. Латентность вычисляется следующим образом:
//Получение ответа от сервера
frame = &cl.frames[cls.netchan.incoming_acknowledged & UPDATE_MASK];
frame->receivedtime = realtime;
latency = frame->receivedtime - frame->senttime;
Элегантные решения
Зацикленность индекса массива
Сетевая часть движка хранит 64 последних полученных пакетов UDP. Наивным решением циклического прохода по массиву было бы использование оператора остатка целочисленного деления:
arrayIndex = (oldArrayIndex+1) % 64;
Вместо этого вычисляется новое значение с двоичной операцией И для UPDATE_MASK. UPDATE_MASK равняется 64-1.
arrayIndex = (oldArrayIndex+1) & UPDATE_MASK;
Настоящий код выглядит так:
frame_t *newpacket;
newpacket = &frames[cls.netchan.incoming_sequence&UPDATE_MASK];
Обновление: вот комментарий, полученный от Dietrich Epp относительно оптимизации операции деления с остатком:
Есть проблема с последней частью, где использование оператора деления с остатком называется "наивным".
Вот пример разницы между остатком целочисленного деления и оператором И:
Создаём файл file.c:
unsigned int modulo(unsigned int x) { return x % 64; }
unsigned int and(unsigned int x) { return x & 63; }
Запускаем gcc -S file.c и смотрим на файл вывода file.s.
Заметно, что функции построчно одинаковы, несмотря на отключенную оптимизацию!
То же относится к "остроумным" решениям типа использования << 5 вместо *32.
Такие изменения делают код менее читаемым, а преимуществ не дают,
поэтому я считаю, что варианты решений с << 5 или & 63 "наивны", а варианты с *32 или %64 более умны.
--Dietrich
.globl modulo
.type modulo, @function
modulo:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax
andl $63, %eax
popl %ebp
ret
.size modulo, .-modulo
.globl and
.type and, @function
and:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %eax
andl $63, %eax
popl %ebp
ret
.size and, .-and
Прогнозирование
Мы рассмотрели абстракцию NetChannel для сетевого обмена данными. Теперь мы узнаем, как латентность компенсируется с помощью прогнозирования. Вот материал для изучения:
- Статья самого Джона Кармака.
- Другая статья (архив) компании Valve с описанием движка Half-life (в Half-life используется движок Quake).
Прогнозирование
Прогнозирование — это, вероятно, сложнейшая, меньше всего задокументированная и важнейшая часть движка Quake World. Цель прогнозирования — победить латентность, а именно компенсировать задержку, необходимую среде для передачи информации. Прогнозирование выполняется на стороне клиента. Этот процесс называется «Client Side Prediction». На стороне сервера техники компенсации лага не применяются.
Проблема:
Как видно, состояние игры «старее» на половину величины латентности (latency). Если добавить время на отправку команды, нам нужно ждать полный цикл (латентность), чтобы увидеть результаты наших действий:
Чтобы разобраться в системе прогнозирования Quake, нужно понять, как NetChannel заполняет переменную frames (массив frame_t).
Каждая команда, отправляемая серверу, сохраняется в frames вместе с senttime по индексу netchannel.outgoingsequence.
Когда сервер подтверждает получение команды с помощью sequenceACK, можно принять отправленную команду и вычислить латентность:
latency = senttime-receivedtime;
На этом этапе мы знаем мир таким, каким он был latency/2 назад. В NAT латентность вполне низкая (<50 мс), но в Интернете она огромна (>200ms), и необходимо выполнять прогнозирование для симуляции текущего состояния мира. Этот процесс выполняется по-разному для локального игрока и других игроков.
Локальный игрок
Для локального игрока латентность снижена почти до 0 благодаря экстраполяции того, что будет состоянием сервера. Это выполняется с помощью последнего полученного от сервера состояния и «проигрывания» всех команд, отправленного с того момента.
Поэтому клиент прогнозирует, каким будет его положение на сервере в момент t+latency/2.
С точки зрения кода это выполняется с помощью метода CL_PredictMove. Сначала движок Quake выбирает предел sentime для «проигрываемых» команд:
cl.time = realtime - cls.latency - cl_pushlatency.value*0.001;
Примечание:
cl_pushlatency — это консольная переменная (cvar), значение которой устанавливается на стороне клиента. Оно равно отрицательной латентности клиента в миллисекундах. Из этого легко заключить, что: cl.time = realtime.
Затем все другие игроки определяются в CL_SetSolidPlayers (cl.playernum); как твёрдые объекты (чтобы можно было протестировать коллизии) и «проигрываются» команды, отправленные с последнего полученного состояния до момента: cl.time <= to->senttime (коллизии тестируются на каждой итерации с помощью CL_PredictUsercmd).
Другие игроки
Для других игроков у движка Quake нет «отправленных, но ещё не подтверждённых команд», поэтому вместо них используется интерполяция. Начиная с последнего известного положения
cmd интерполируются для прогнозирования получаемого положения. Прогнозируется только положение, без углового поворота.
Quake World учитывает также латентность других игроков. Латентность каждого игрока отправляется вместе с обновлением мира.
Код
Код прогнозирования и расчёта коллизий можно вкратце представить следующим образом:
CL_SetUpPlayerPrediction(false)
CL_PredictMove
| /* Локальный игрок переместился */
| CL_SetSolidPlayers
| | CL_PredictUsercmd
| | PlayerMove
| Линейная интерполяция
CL_SetUpPlayerPrediction(true)
CL_EmitEntities
CL_LinkPlayers
| /* Другие игроки переместились */
| для каждого игрока
| | CL_SetSolidPlayers
| | CL_PredictUsercmd
| | PlayerMove
CL_LinkPacketEntities
CL_LinkProjectiles
CL_UpdateTEnts
Эта часть сложна, потому что Quake World не только выполняет прогнозирование для игроков, но и распознаёт коллизии исходя из прогнозов.
CL_SetUpPlayerPrediction(false)
Первый вызов не выполняет прогнозирование, он только расставляет игроков в положения, полученные от сервера (то есть с задержкой в t-latency/2).
CL_PredictMove()
Здесь выполняется перемещение локального игрока:
- Ориентация не интерполируется и выполняется полностью в реальном времени.
- Положение и скорость: все команды, отправленные до текущего момента (
cl.time <= to->senttime) применяются к последним положению/скорости, полученным от сервера.
Подробнее про обновление положения и скорости:
- Сначала другие игроки превращаются в твёрдые объекты (в их последнем известном положении, установленном в
CL_SetUpPlayerPrediction(false)) с помощьюCL_SetSolidPlayers. - Движок циклически проходит по всем отправленным командам, проверяя коллизии и прогнозируя положение с помощью
CL_PredictUsercmd. Также тестируются коллизии для других игроков. - Полученные положение и скорость сохраняются в
cl.sim*. Они будут использованы позже для настройки точки обзора.
CL_SetUpPlayerPrediction(true)
Во втором вызове на стороне сервера прогнозируется положение других игроков в текущий момент (но перемещение пока не выполняется). Положение экстраполируется исходя из последних известных команд и последнего известного положения.
Примечание: Здесь возникает небольшая проблема: Valve рекомендует (для cl_pushlatency) прогнозировать состояние локального игрока на стороне сервера в момент t+latency/2. Однако положение других игроков прогнозируется на стороне сервера в момент t. Возможно, лучшим значением для cl_pushlatency в QW было -latency/2?
CL_EmitEntities
Здесь генерируются указания о видимости. Затем они передаются в рендерер.
- CL_LinkPlayers : Выполняется перемещение других игроков, другие игроки превращаются в твёрдые объекты и выполняется распознавание коллизий для их спрогнозированного положения.
- CL_LinkPacketEntitiesPacket: объекты из последнего состояния, полученного от сервера, прогнозируются и связываются с указаниями о видимости. Именно поэтому возникает лаг для выпущенной ракеты.
- CL_LinkProjectiles: обработка гвоздей и других снарядов.
- CL_UpdateTEnts: стандартное обновление лучей света и объектов.
Визуализация
При разработке оригинальной игры больше всего усилий было потрачено на модуль рендерера Quake. Это подробно описано в книге Майкла Абраша (Michael Abrash) и в файлах .plan Джона Кармака.
Визуализация
Процесс визуализиции сцены неотъемлемо связан с BSP карты. Рекомендую почитать подробнее о Binary Space Partitioning (двоичном разбиении пространства) в Wikipedia. Если вкратце, то карты Quake проходили серьёзную предварительную обработку. Их объём рекурсивно разрезался следующим образом:
Этот процесс создавал BSP с листьями (правила создания таковы: выбрать существующий полигон в качестве секущей плоскости и выбрать разделитель, разрезающий меньшее количество полигонов). После создания BSP для каждого листа вычислялся PVS (Potentially Visible Set, потенциально видимый набор). Пример: лист 4 может потенциально видеть листья 7 и 9:
Окончальный PVS для этог листа сохранялся как битовый вектор:
| Ид. листа | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| PVS для листа 4 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Сжатый PVS для листа 4 | 3 | 2 | 1 | 7 |
|---|
Закодированный PVS содержал только количество нулей между единицами. Хотя это и не выглядит очень эффективной техникой сжатия, большое количество листьев (32767) в сочетании с очень ограниченным набором видимых листьев снижали размер всего PVS до 20КБ.
Предварительная обработка в действии
Благодаря наличию предварительно рассчитанных BPS и PVS процедура визуализации карты движком была простой:
- Обход BSP для определения того, на какой лист направлена камера.
- Извлечение и распаковка PVS для этого листа, итеративный проход по PVS и пометка листьев в BSP.
- Обход BSP, начиная от ближних к дальним.
- Если узел (Node) не помечен, то он пропускается.
- Тестирование общей границы узлов на присутствие в пирамиде видимости камеры.
- Добавление текущего листа в список визуализации.
Примечание: BSP используется несколько раз. Например, для обхода карты от ближайших точек вдаль для каждого активного источника освещения и пометки полигонов на карте.
Примечание 2: При программном рендеринге обход BSP-дерева выполнялся с дальних точек до ближних.
Анализ кода
Вкратце код визуализации можно представить так:
SCR_UpdateScreen
{
GL_BeginRendering
SCR_SetUpToDrawConsole
V_RenderView
| R_Clear
| R_RenderScene
| | R_SetupFrame
| | Mod_PointInLeaf
| | R_SetFrustum
| | R_SetupGL
| | R_MarkLeaves
| | | Mod_LeafPVS
| | | Mod_DecompressVis
| | R_DrawWorld
| | | R_RecursiveWorldNode
| | | DrawTextureChains
| | | | R_RenderBrushPoly
| | | | DrawGLPoly
| | | R_BlendLightmaps
| | S_ExtraUpdate
| | R_DrawEntitiesOnList
| | GL_DisableMultitexture
| | R_RenderDlights
| | R_DrawParticles
| R_DrawViewModel
| R_DrawAliasModel
| R_DrawWaterSurfaces
| R_PolyBlend
GL_Set2D
SCR_TileClear
V_UpdatePalette
GL_EndRendering
}
SCR_UpdateScreen
Вызовы:
GL_BeginRendering(устанавливает значения переменных (glx,gly,glwidth,glheight), позже используемых вR_SetupGLдля установки области просмотра и матрицы проецирования)SCR_SetUpToDrawConsole(Определяет высоту консоли: почему это находится здесь, а не в части, относящейся к 2D?!)V_RenderView(рендеринг 3D-сцены)GL_Set2D(переключение к ортогональной проекции (2D))SCR_TileClear(Дополнительная отрисовка множества 2D-объектов, консоли, метрик FPS и т.д.)V_UpdatePalette(название соответствует программному рендереру, в openGL метод устанавливает режим смешивания соответственно полученному урону или активному бонусу, делая экран красным, ярким и т.д.). Значение хранится вv_blendGL_EndRendering(переключение буфера (двойная буферизация)!)
V_RenderView
Вызовы:
V_CalcRefdef(простите, в этой части не разобрался)R_PushDlightsПометка полигонов каждым источником освещения для наложения эффекта (см. примечание)R_RenderView
Примечание: R_PushDlights вызывает рекурсивный метод (
R_MarkLights). Он использует BSP для пометки полигонов (с помощью целочисленного битового вектора), на которые воздействуют источники освещения. BSP обходится с ближних точек до дальних (с точки обзора источников освещения). Метод проверяет, активен ли источник освещения и находится ли он в пределах доступности. Метод R_MarkLights особенно примечателен, потому что здесь мы видим прямую реализацию статьи Майкла Абраша о расстоянии между точкой и плоскостью «Frames of Reference» (dist = DotProduct (light->origin, splitplane->normal) - splitplane->dist;)).
R_RenderView
Вызовы:
R_Clear(очистка при необходимости GL_COLOR_BUFFER_BIT и/или GL_DEPTH_BUFFER_BIT)R_RenderSceneR_DrawViewModel(рендеринг модели игрока в режиме наблюдателя)R_DrawWaterSurfaces(переключение в режим GL_BEND/GL_MODULATE для отрисовки воды. Деформация выполняется с помощью таблицы поиска sin и cos изgl_warp.c)R_PolyBlend(смешивание всего экрана с использованием значения, установленного вV_UpdatePaletteпеременнойv_blend. Это используется для демонстрации получения урона (красный цвет), нахождения под водой или применения бонуса)
R_RenderScene
Вызовы:
R_SetupFrame(извлечение листа BSP, в котором находится камера и сохранение его в переменной «r_viewleaf» )R_SetFrustum(установкапирамиды mplane_t[4]. Без ближней и дальней плоскости.R_SetupGL(установка GL_PROJECTION, GL_MODELVIEW, области просмотра и стороны glCullFace, а также поворот осей Y и Z, потому что оси X и Z в Quake имеют другое положение по сравнению с openGL.)R_MarkLeavesR_DrawWorldS_ExtraUpdate(сброс положения мыши, разрешение проблем со звуком)R_DrawEntitiesOnList(отрисовка объектов в списке)GL_DisableMultitexture(отключение мультитекстурирования)R_RenderDlights(световые домены и эффекты освещения)R_DrawParticles(взрывы, огонь, электричество и т.д.)
R_SetupFrame
Интересна строка:
r_viewleaf = Mod_PointInLeaf (r_origin, cl.worldmodel);
В ней движок Quake извлекает лист/узел в BSP, на который направлена камера в текущий момент.
Mod_PointInLeaf расположен в model.c, он выполняется через BSP (корень BSP-дерева находится в model->nodes ).
Для каждого узла:
- Если узел не рассекает пространство далее, то он является листом, поэтому он возвращается как положение текущего узла.
- В противном случае секущая плоскость BSP проверяется для текущего положения (с помощью обычного скалярного произведения, это стандартный способ обхода BSP-дерева) и обходятся соответствующие дочерние элементы.
R_MarkLeaves
Сохраняет в переменную r_viewleaf местоположение камеры в BSP (извлекаемое в R_SetupFrame), выполняет поиск (Mod_LeafPVS) и распаковывает (Mod_DecompressVis) потенциально видимый набор (PVS). Затем итеративно обходит битовый вектор и помечает потенциально видимые узлы BSP: node->visframe = r_visframecount.
R_DrawWorld
Вызовы:
R_RecursiveWorldNode(обход мира BSP спереди назад, пропуск узлов, не помеченных ранее (вR_MarkLeaves), заполнение спискаcl.worldmodel->textures[]->texturechainсоответствующими полигонами.)DrawTextureChains(отрисовка списка полигонов, хранящихся в texturechain: итерация по cl.worldmodel->textures[]. Таким образом получается только одно переключение на материал. Неплохо.)R_BlendLightmaps(второй проход, используемый для смешивания карт освещения в буфере кадров).
Примечание:
В этой части используется печально известный режим openGL «immediate mode», в то время он считался «последним словом техники».
В R_RecursiveWorldNode выполняется бóльшая часть операций отсечения поверхностей. Узел отсекается, если:
- Его содержимое является твёрдым объектом.
- Лист не был помечен в PVS (
node->visframe != r_visframecount) - Лист не проходит отсечение по пирамиде видимости.
Формат MDL
Формат MDL — это набор фиксированных кадров. Движок Quake не интерполирует положение вершин для сглаживания анимации (поэтому высокая частота кадров не приводит улучшению анимации).
Элегантные решения
Элегантная пометка листьев
Наивный подход пометки листьев BSP для рендеринга заключается в использовании булевой переменной isMarkedVisible. Перед каждым кадром нужно:
- Установить значения всех булевых переменных равными false.
- Итеративно обойти PVS и для каждого видимого листа указать значение true.
- Потом протестировать лист с помощью
if (leave.isMarkedVisible)
Вместо этого движок Quake использует целое число для подсчёта номера отрендеренного кадра (
r_visframecount variable). Это позволяет избавиться от первого шага:
- Итеративный обход PVS и для каждого видимого листа установить
leaf.visframe = r_visframecount - Потом протестировать лист с помощью
if (leaf.visframe == r_visframecount)
Избавление от рекурсии
В R_SetupFrame вместо выполнения «быстрой и грязной» рекурсии для обхода BSP и извлечения текущего положения используется цикл while.
node = model->nodes;
while (1)
{
if (node->contents < 0)
return (mleaf_t *)node;
plane = node->plane;
d = DotProduct (p,plane->normal) - plane->dist;
if (d > 0)
node = node->children[0];
else
node = node->children[1];
}
Минимизация количества переключений текстур
В openGL переключение текстур с помощью (glBindTexture(GL_TEXTURE_2D,id)) очень затратно. Для минимизации количества переключений текстур каждый полигон, помеченный для рендеринга, хранится в цепочке массивов, индексированных по материалу текстуры полигона.
cl.worldmodel->textures[textureId]->texturechain[]
После завершения отсечения цепочки текстур отрисовываются по порядку. Таким образом, выполняется всего N переключений текстур, где N — общее количество видимых текстур.
int i;
for ( i = 0; i < cl.worldmodel->textures_num ; i ++)
DrawTextureChains(i);
Комментарии (0)