Анализ исходного кода Quake

Я с удовольствием погрузился в изучение исходного кода 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 ASM
• qwcl — клиентская часть Quake
• QWFwd — прокси, расположенный перед серверами Quake
• qwsv — серверная часть 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 размером примерно 5МБ. Это было слишком много для ПК в 1996 году. Поэтому PVS сжимался с помощью компрессии разности длин.

Сжатый 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

Вызовы:

1. GL_BeginRendering (устанавливает значения переменных (glx,gly,glwidth,glheight), позже используемых в R_SetupGL для установки области просмотра и матрицы проецирования)
2. SCR_SetUpToDrawConsole (Определяет высоту консоли: почему это находится здесь, а не в части, относящейся к 2D?!)
3. V_RenderView (рендеринг 3D-сцены)
4. GL_Set2D (переключение к ортогональной проекции (2D))
5. SCR_TileClear (Дополнительная отрисовка множества 2D-объектов, консоли, метрик FPS и т.д.)
6. V_UpdatePalette (название соответствует программному рендереру, в openGL метод устанавливает режим смешивания соответственно полученному урону или активному бонусу, делая экран красным, ярким и т.д.). Значение хранится в v_blend
7. GL_EndRendering (переключение буфера (двойная буферизация)!)

V_RenderView
Вызовы:

1. V_CalcRefdef (простите, в этой части не разобрался)
2. R_PushDlights Пометка полигонов каждым источником освещения для наложения эффекта (см. примечание)
3. R_RenderView

Примечание: R_PushDlights вызывает рекурсивный метод (R_MarkLights). Он использует BSP для пометки полигонов (с помощью целочисленного битового вектора), на которые воздействуют источники освещения. BSP обходится с ближних точек до дальних (с точки обзора источников освещения). Метод проверяет, активен ли источник освещения и находится ли он в пределах доступности. Метод R_MarkLights особенно примечателен, потому что здесь мы видим прямую реализацию статьи Майкла Абраша о расстоянии между точкой и плоскостью «Frames of Reference» (dist = DotProduct (light->origin, splitplane->normal) - splitplane->dist;)).

R_RenderView

Вызовы:

1. R_Clear (очистка при необходимости GL_COLOR_BUFFER_BIT и/или GL_DEPTH_BUFFER_BIT)
2. R_RenderScene
3. R_DrawViewModel (рендеринг модели игрока в режиме наблюдателя)
4. R_DrawWaterSurfaces (переключение в режим GL_BEND/GL_MODULATE для отрисовки воды. Деформация выполняется с помощью таблицы поиска sin и cos из gl_warp.c)
5. R_PolyBlend (смешивание всего экрана с использованием значения, установленного в V_UpdatePalette переменной v_blend. Это используется для демонстрации получения урона (красный цвет), нахождения под водой или применения бонуса)

R_RenderScene

Вызовы:

1. R_SetupFrame(извлечение листа BSP, в котором находится камера и сохранение его в переменной «r_viewleaf» )
2. R_SetFrustum (установка пирамиды mplane_t[4]. Без ближней и дальней плоскости.
3. R_SetupGL (установка GL_PROJECTION, GL_MODELVIEW, области просмотра и стороны glCullFace, а также поворот осей Y и Z, потому что оси X и Z в Quake имеют другое положение по сравнению с openGL.)
4. R_MarkLeaves
5. R_DrawWorld
6. S_ExtraUpdate (сброс положения мыши, разрешение проблем со звуком)
7. R_DrawEntitiesOnList (отрисовка объектов в списке)
8. GL_DisableMultitexture (отключение мультитекстурирования)
9. R_RenderDlights (световые домены и эффекты освещения)
10. 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

Вызовы:

1. R_RecursiveWorldNode (обход мира BSP спереди назад, пропуск узлов, не помеченных ранее (в R_MarkLeaves), заполнение списка cl.worldmodel->textures[]->texturechain соответствующими полигонами.)
2. DrawTextureChains (отрисовка списка полигонов, хранящихся в texturechain: итерация по cl.worldmodel->textures[]. Таким образом получается только одно переключение на материал. Неплохо.)
3. R_BlendLightmaps (второй проход, используемый для смешивания карт освещения в буфере кадров).

Примечание:

В этой части используется печально известный режим openGL «immediate mode», в то время он считался «последним словом техники».

В R_RecursiveWorldNode выполняется бóльшая часть операций отсечения поверхностей. Узел отсекается, если:

• Его содержимое является твёрдым объектом.
• Лист не был помечен в PVS (node->visframe != r_visframecount)
• Лист не проходит отсечение по пирамиде видимости.

Формат MDL

Формат MDL — это набор фиксированных кадров. Движок Quake не интерполирует положение вершин для сглаживания анимации (поэтому высокая частота кадров не приводит улучшению анимации).

Элегантные решения

Элегантная пометка листьев

Наивный подход пометки листьев BSP для рендеринга заключается в использовании булевой переменной isMarkedVisible. Перед каждым кадром нужно:

1. Установить значения всех булевых переменных равными false.
2. Итеративно обойти PVS и для каждого видимого листа указать значение true.
3. Потом протестировать лист с помощью if (leave.isMarkedVisible)

Вместо этого движок Quake использует целое число для подсчёта номера отрендеренного кадра (r_visframecount variable). Это позволяет избавиться от первого шага:

1. Итеративный обход PVS и для каждого видимого листа установить leaf.visframe = r_visframecount
2. Потом протестировать лист с помощью 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);