Quake Source Code Analysis

I was delighted to plunge into the study of Quake World source code and set out in the article everything that I understood. I hope this helps those who wish to sort it out. This article is divided into four parts:

• Architecture
• Network
• Forecasting
• Visualization

Architecture

Quake Client

Learning Quake is worth starting with a project qwcl(client). The entry point WinMainis at sys_win.c . In short, the code looks like this:

	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;
		}
	}

Here we can highlight three main elements of Quake World:

• NetworkCL_ReadPackets andCL_SendCmd
• ForecastingCL_SetUpPlayerPrediction , CL_PredictMoveandCL_EmitEntities
• VisualizationSCR_UpdateScreen

The network layer (also called Net Channel) displays information about the world in a variable frames(array frame_t). They are transferred to the forecasting layer , in which collisions are processed, and the data is displayed in the form of visibility instructions ( cl_visedicts) with the definition of the visibility area (POV). VisEdicts are used in the visualization layer along with POV ( cl.sim*) variables to render the scene.



setjmp:

Setting the intermediate point of the code, if something bad happens, the program returns here.

Sys_SendKeyEvents:

Receive Windows OS messages, minimize windows, etc. Corresponding update of the engine variable (for example, if the window is minimized, the world will not be rendered).

IN_Commands:

Retrieving joystick entry information.

Cbuf_Execute:

In each cycle of the game, commands are executed in the buffer. Commands are generated mainly through the console, but can come from the server or even from a keystroke.

The game begins with the exec quake.rccommand buffer.

CL_ReadPacketsand CL_SendCmd:

Processing the network part of the engine.

CL_SendCmdintercepts mouse and keyboard input, generates a command, which is then sent.

Because Quake World used UDP, transmission reliability was guaranteed by the sequence / sequenceACK set in the netChannel packet headers. In addition, the last command was systematically resent. There were no restrictions on the transfer of packets from the client, updates were sent as often as possible. From the server side, a message was sent to the client only if the packet was received and the sending speed was lower than the processing speed. This limit was set by the client and sent to the server.

The entire "Network" section is dedicated to this topic.

CL_SetUpPlayerPrediction, CL_PredictMoveand CL_EmitEntities:

Carried out forecasting in the engine and calculation of collisions. They are mainly designed to combat the latency of transmission over the network.

This topic is devoted to the entire section "Forecasting".

SCR_UpdateScreen:

Visualization in the engine. In this part, BSP / PVS is actively used. Here the code branches based on include/ define. The Quake engine can render the world either software or hardware accelerated.

The section “Visualization” is entirely devoted to this.

Opening a zip archive and compiling

Opening zip:

There are two folders / two Visual Studio: QWand projects in the q1sources.zip archive WinQuake.

• WinQuake- this is code with the combined client and server code, working as a single process (ideally, these should be two separate processes, if DOS supported them). Network play was only possible on the LAN.
• QW- this is the Quake World project, in which the server and client must be run on separate machines (note that the client entry point is WinMain(in sys_win.c), and the server entry point is main(also in sys_win.c)).

I studied Quake World with openGL rendering. There are four subprojects in this project:

• gas2asm - utility for porting assembler code from GNU ASM to x86 ASM
• qwcl - client part of Quake
• QWFwd - proxy located in front of Quake servers
• qwsv - Quake backend

Compilation:

After installing Windows and the DirectX SDK, compiling in Visual Studio 2008 reveals one error:

.\net_wins.c(178) : error C2072: '_errno' : initialization of a function

This is currently _errnoa Microsoft macro used for something else. You can fix these errors by replacing the variable name with _errnosuch as 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));
	}

The linker complains about LIBC.lib in the qwcl project. Just add it to the list of ignored libraries "Ignored Library" and the assembly of four projects will be completed.

Instruments

Visual Studio Express (freeware) was great as an IDE. I recommend reading a few books if you want to get a deeper understanding of the engine based on BSP / PVS, Id Software and Quake:



My bookshelf during the week of working with Quake source code looked like this:

Network

The network architecture of QuakeWorld was once considered a terrific innovation. All subsequent network games used the same approach.

Network stack

The basic unit of information exchange in Quake was команда. They are used to update the position, orientation, health, damage to the player, etc. TCP / IP has many great features that could be useful in real-time simulations (transmission control, reliable delivery, packet order preservation), but this protocol could not be used in the Quake World engine (it was used in the original Quake). In first-person shooters, information not received on time is not worth resending. Therefore, UDP / IP was selected. To ensure reliable delivery and preserve the order of packages, we created a network layer of abstraction " NetChannel".

In terms of OSI, NetChannelit’s conveniently located on top of UDP:



So, to summarize: the engine basically works withкомандами. When you need to send or receive data, he entrusts this task to Netchan_Transmitand Netchan_Processfrom netchan.c methods (these methods are the same for the client and server).

NetChannel Header

The NetChannel header has the following structure:

Bit offset	Bits 0-15	16-31
0	Sequence
32	ACK Sequence
64	Qport	Teams
94	...

• Sequence is a number intinitialized by the sender and incremented by one each time a packet is sent. Sequenceused for many purposes, but the most important task is to provide the recipient with the ability to recognize lost / duplicated / extraordinary UDP packets. The most significant bit of this integer is not part of the sequence, but a flag indicating whether ( команда) contains reliable data (more on this later).
• ACK Sequence is also int, it is equal to the last sequence number received. Thanks to him, the other side of NetChannel can understand that the packet was lost.
• QPort is a workaround for NAT router errors (see the end of this section for more details). Its value is a random number that is set when the client starts.
• Commands: significant data transmitted.

Reliable messages

Unreliable commands are grouped into a UDP packet, it is marked with the last outgoing sequence number and sent: it does not matter to the sender whether it will be lost. Trusted commands are handled differently. The main thing is to understand that there can be only one unconfirmed reliable UDP packet between the sender and the receiver.

In each game cycle, when a new reliable command is generated, it is added to the array message_buf(controlled via a variable message) ( 1 ). The set of reliable commands is then moved from messageto the array reliable_buf( 2 ). This only happens if it is reliable_bufempty (if it is not empty, it means that another set of commands has been sent earlier and its receipt has not yet been confirmed).

Then the final UDP packet is formed: the NetChannel ( 3 ) header is added , then the contents reliable_bufand the current unreliable commands (if there is enough space).

On the receiving side, the UDP message is parsed, the incoming number is sequencesent to the outgoing sequence ACK( 4 ) (along with a bit flag indicating that the packet contains reliable data).

The next message you receive:

• If the reliability bit flag is true, this means that the UDP packet has been delivered to the recipient. NetChannel can clear reliable_buf( 5 ) and is ready to send a new set of commands.
• If the reliability bit flag is false, then the UDP packet did not reach the receiver. NetChannel retries sending content reliable_buf. New teams accumulate in message_buf. If the array overflows, then the client is reset.

Transmission control

As I understand it, transmission control is performed only on the server side. The client sends updates to its status as often as possible.

The first rule of transmission control, active only on the server: send a packet only if the packet was received from the client. The second type of transfer control is “choke,” a parameter that the client sets with the console command rate. It allows the server to skip update messages, reducing the amount of data sent to the client.

Important Commands

Commands contain type code stored in байтеfollowed by useful command information. Probably the most important are the teams that give information about the state of the game ( frame_t):

• svc_packetentitiesand svc_deltapacketentities: update objects such as traces of missiles, explosions, particles, etc.
• svc_playerinfo: Sends updates on the player’s position, last team and team duration in milliseconds.

Read more about qport

Qport has been added to the NetChannel header to fix the error. Prior to qport, the Quake server identified the client using the combination “remote IP address, remote UDP port”. Most often, this worked well, but some NAT routers can arbitrarily change their port translation scheme (remote UDP port). The UDP port becomes unreliable, and John Carmack explained that he decided to identify the client by the “remote IP address, Qport in the NetChannel header”. This fixed the error and allowed the server to change the destination UDP response port on the fly.

Latency Calculation

The Quake engine stores the 64 most recently sent commands (in the array frame_t:) framesalong with senttime. They can be accessed directly by the sequence number used to transmit them ( outgoing_sequence).

	frame = &cl.frames[cls.netchan.outgoing_sequence & UPDATE_MASK];
	frame->senttime = realtime;
	//Отправка пакета серверу

After receiving confirmation from the server, the time for sending the command is obtained from sequenceACK. Latency is calculated as follows:

	//Получение ответа от сервера
	frame = &cl.frames[cls.netchan.incoming_acknowledged & UPDATE_MASK];
	frame->receivedtime = realtime;
	latency = frame->receivedtime - frame->senttime;

Elegant solutions

Looping index array The
network part of the engine stores 64 of the last received UDP packets. A naive solution to loop through an array would be to use the remainder operator of integer division:

arrayIndex = (oldArrayIndex+1) % 64;

Instead, a new value is calculated with the binary AND operation for UPDATE_MASK. UPDATE_MASK is 64-1.

arrayIndex = (oldArrayIndex+1) & UPDATE_MASK;

The real code looks like this:

		frame_t *newpacket; 
		newpacket = &frames[cls.netchan.incoming_sequence&UPDATE_MASK];

Update: here is a comment received from Dietrich Epp regarding optimization of the remainder division operation:

Есть проблема с последней частью, где использование оператора деления с остатком называется "наивным". 
Вот пример разницы между остатком целочисленного деления и оператором И:
Создаём файл 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

Forecasting

We looked at the NetChannel abstraction for network communication. Now we will find out how latency is offset by prediction. Here is the material to study:

• Статья самого Джона Кармака.
• Другая статья (архив) компании Valve с описанием движка Half-life (в Half-life используется движок Quake).

Прогнозирование

Forecasting is probably the hardest, least documented, and most important part of the Quake World engine. The purpose of forecasting is to defeat latency, namely, to compensate for the delay needed by the medium to transmit information. Prediction is performed on the client side. This process is called “Client Side Prediction.” On the server side, lag compensation techniques are not applied.

Problem:



As you can see, the state of the game is "older" by half the value of latency. If we add time to send the command, we need to wait for the full cycle (latency) to see the results of our actions:



To understand the Quake forecasting system, we need to understand how NetChannel fills the variable frames(array frame_t).



Each command sent to the server is stored in framesalong with senttimean index netchannel.outgoingsequence.

When the server confirms receipt of the command with sequenceACK, you can accept the sent command and calculate the latency:

latency = senttime-receivedtime;

At this stage, we know the world as it was latency / 2 ago. In NAT, latency is quite low (<50 ms), but on the Internet it is huge (> 200ms), and forecasting is necessary to simulate the current state of the world. This process is performed differently for the local player and other players.

Local player

For a local player, latency is reduced to almost 0 due to extrapolation of what will be the state of the server. This is done using the last status received from the server and “playing” all the commands sent from that moment.



Therefore, the client predicts what its position on the server will be at time t + latency / 2.

From a code point of view, this is done using a method CL_PredictMove. First, the Quake engine selects the sentime limit for "playable" commands:

cl.time = realtime - cls.latency - cl_pushlatency.value*0.001;

Note:cl_pushlatency is a console variable (cvar), the value of which is set on the client side. It is equal to the negative latency of the client in milliseconds. From this it is easy to conclude that: cl.time = realtime.

Then all other players are defined CL_SetSolidPlayers (cl.playernum);as solid objects (in order to be able to test the collisions) and the teams “sent” from the last state received to the moment are “lost” cl.time <= to->senttime(the collisions are tested at each iteration using CL_PredictUsercmd).

Other players

For other players, the Quake engine does not have “sent, but not yet confirmed teams,” so interpolation is used instead. Starting from the last known position, cmdinterpolated to predict the resulting position. Only position is predicted, without angular rotation.

Quake World also takes into account the latency of other players. The latency of each player is sent along with the update of the world.

The code

The collision prediction and calculation code can be summarized as follows:

		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

This part is complicated because Quake World not only performs prediction for players, but also recognizes collisions based on forecasts. The first call does not perform forecasting, it only places players in positions received from the server (that is, with a delay of t-latency / 2). This is where the local player moves:

CL_SetUpPlayerPrediction(false)



CL_PredictMove()

• Orientation is not interpolated and is performed in full in real time.
• Position and speed: all commands sent up to the current moment ( cl.time <= to->senttime) are applied to the last position / speed received from the server.

More about updating position and speed:

• First, other players turn into solid objects (in their last known position set in CL_SetUpPlayerPrediction(false)) using CL_SetSolidPlayers.
• Движок циклически проходит по всем отправленным командам, проверяя коллизии и прогнозируя положение с помощью CL_PredictUsercmd. Также тестируются коллизии для других игроков.
• Полученные положение и скорость сохраняются в cl.sim*. Они будут использованы позже для настройки точки обзора.

CL_SetUpPlayerPrediction(true)

In the second server-side call, the position of other players at the current moment is predicted (but the move has not yet been performed). The position is extrapolated based on the last known teams and the last known position.

Note: A small problem arises here: Valve recommends (for cl_pushlatency) predicting the status of a local player on the server side at time t + latency / 2. However, the position of other players is predicted on the server side at time t. Perhaps the best value for cl_pushlatencyin QW was -latency / 2? Visibility guidelines are generated here. Then they are passed to the renderer.

CL_EmitEntities

• CL_LinkPlayers: Other players are moving, other players are turning into solid objects and collision detection is performed for their predicted position.
• CL_LinkPacketEntitiesPacket: objects from the last state received from the server are predicted and associated with visibility guidelines. That is why there is a lag for the launched rocket.
• CL_LinkProjectiles: processing nails and other shells.
• CL_UpdateTEnts: A standard update for light rays and objects.

Visualization

When developing the original game, most of the effort was spent on the Quake renderer module. This is described in detail in the book by Michael Abrash and in the .plan files of John Carmack.

Visualization

The scene visualization process is inextricably linked to the BSP card. I recommend reading more on Binary Space Partitioning ( binary space partitioning ) in Wikipedia. In short, Quake cards went through a lot of pre-processing. Their volume was recursively cut as follows:



This process created a BSP with leaves (the creation rules are as follows: select an existing polygon as a cutting plane and select a separator that cuts fewer polygons). After creating a BSP, a PVS (Potentially Visible Set, potentially visible set) was calculated for each sheet. Example: sheet 4 can potentially see leaves 7 and 9: The



final PVS for this sheet was saved as a bit vector:

Id leaf	1	2	3	4	5	6	7	8	9	10	eleven	12	thirteen	14	fifteen	16
PVS for sheet 4	0	0	0	1	0	0	1	0	1	0	0	0	0	0	0	0

The result is a global PVS of approximately 5MB in size. That was too much for a PC in 1996. Therefore, the PVS was compressed by compression of the length difference.

Compressed PVS for sheet 4	3	2	1	7

Encoded PVS contained only the number of zeros between units. Although this does not look like a very effective compression technique, a large number of leaves (32767) combined with a very limited set of visible leaves reduced the size of the entire PVS to 20KB.

Preprocessing in action

Thanks to the presence of pre-calculated BPS and PVS, the procedure for visualizing the map with the engine was simple:

• Bypass the BSP to determine which sheet the camera is pointing at.
• Extract and unpack the PVS for this sheet, iterate through the PVS and mark the leaves in the BSP.
• Bypass BSP, from near to far.
• If the node (Node) is not marked, then it is skipped.
• Testing the overall border of the nodes for the presence in the pyramid of camera visibility.
• Adding the current sheet to the visualization list.

Note: BSP is used several times. For example, to bypass the map from the nearest points into the distance for each active light source and mark polygons on the map.

Note 2: In software rendering, the BSP tree was traversed from far points to nearest ones.

Code analysis

In short, the visualization code can be represented as follows:

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

Calls:

1. GL_BeginRendering(sets the values ​​of the variables ( glx,gly,glwidth,glheight) later used in R_SetupGLto set the viewport and the projection matrix)
2. SCR_SetUpToDrawConsole (Determines the height of the console: why is it here, and not in the part related to 2D ?!)
3. V_RenderView (3D scene rendering)
4. GL_Set2D (switch to orthogonal projection (2D))
5. SCR_TileClear (Additional rendering of many 2D objects, console, FPS metrics, etc.)
6. V_UpdatePalette(the name corresponds to the software renderer; in openGL, the method sets the mixing mode according to the received damage or active bonus, making the screen red, bright, etc.). Value is stored inv_blend
7. GL_EndRendering (buffer switching (double buffering)!)

V_RenderView
Calls:

1. V_CalcRefdef (sorry, I didn’t understand this part)
2. R_PushDlights Mark polygons with each light source to apply an effect (see note)
3. R_RenderView

Note: R_PushDlights calls the recursive method ( R_MarkLights). It uses BSP to mark polygons (using an integer bit vector) that are affected by light sources. BSP goes from near points to far points (from the point of view of light sources). The method checks if the light source is active and within reach. The method is R_MarkLightsespecially noteworthy because here we see a direct implementation of the article by Michael Abrash about the distance between a point and a plane “Frames of Reference” ( dist = DotProduct (light->origin, splitplane->normal) - splitplane->dist;)).

R_RenderView

Calls:

1. R_Clear (cleaning if necessary GL_COLOR_BUFFER_BIT and / or GL_DEPTH_BUFFER_BIT)
2. R_RenderScene
3. R_DrawViewModel (rendering the player model in observer mode)
4. R_DrawWaterSurfaces(switching to GL_BEND / GL_MODULATE mode to draw water. Deformation is performed using the lookup table sin and cos from gl_warp.c)
5. R_PolyBlend(mixing the entire screen using the value set in the V_UpdatePalettevariable v_blend. This is used to demonstrate taking damage (red), being under water, or applying a bonus)

R_RenderScene

Calls:

1. R_SetupFrame(extracting the BSP sheet in which the camera is located and saving it in the variable "r_viewleaf")
2. R_SetFrustum(installation пирамиды mplane_t[4]. Without near and far plane.
3. R_SetupGL (setting GL_PROJECTION, GL_MODELVIEW, viewports and sides of glCullFace, as well as rotating the Y and Z axes, because the X and Z axes in Quake have a different position than openGL.)
4. R_MarkLeaves
5. R_DrawWorld
6. S_ExtraUpdate (reset mouse position, resolving audio problems)
7. R_DrawEntitiesOnList (drawing objects in a list)
8. GL_DisableMultitexture (disable multitexturing)
9. R_RenderDlights (light domains and lighting effects)
10. R_DrawParticles (explosions, fire, electricity, etc.)

R_SetupFrame

Interesting line:

r_viewleaf = Mod_PointInLeaf (r_origin, cl.worldmodel);

In it, the Quake engine retrieves the sheet / node in the BSP that the camera is currently pointing at.

Mod_PointInLeaf is located in model.c, it is executed through BSP (the root of the BSP tree is in model-> nodes).

For each node:

• If the node does not dissect the space further, then it is a sheet, so it returns as the position of the current node.
• Otherwise, the secant plane of the BSP is checked for the current position (using the usual scalar product, this is the standard way of traversing the BSP tree) and the corresponding child elements are bypassed.

R_MarkLeaves

Stores the r_viewleafcamera location in the BSP (retrieved to R_SetupFrame) into a variable , performs a search ( Mod_LeafPVS), and decompresses ( Mod_DecompressVis) a potentially visible set (PVS). Then iteratively traverses the bit vector and marks the potentially visible BSP nodes: node-> visframe = r_visframecount.

R_DrawWorld

Challenges:

1. R_RecursiveWorldNode(traversing the BSP world from front to back, skipping nodes not previously marked (c R_MarkLeaves), filling out the list cl.worldmodel->textures[]->texturechainwith appropriate polygons.)
2. DrawTextureChains (drawing a list of polygons stored in texturechain: iterating over cl.worldmodel-> textures []. This way you get only one switch to the material. Not bad.)
3. R_BlendLightmaps (second pass used to mix the lightmaps in the frame buffer).

Note:

In this part, the infamous openGL “immediate mode” mode is used, at that time it was considered the “last word of technology”.

In R_RecursiveWorldNoderuns most of the operations of clipping surfaces. A node is cut off if:

• Its contents are a solid object.
• The sheet was not marked in PVS ( node->visframe != r_visframecount)
• The leaf does not undergo clipping along the pyramid of visibility.

MDL format

The MDL format is a set of fixed frames. The Quake engine does not interpolate the position of the vertices to smooth the animation (therefore, a high frame rate does not improve the animation).

Elegant solutions

Elegant leaf

tagging The naive approach of BSP leaf tagging for rendering is to use a boolean variable isMarkedVisible. Before each frame you need:

1. Set the values ​​of all Boolean variables to false.
2. Iteratively bypass PVS and specify true for each visible sheet.
3. Then test the sheet with if (leave.isMarkedVisible)

Instead, the Quake engine uses an integer to calculate the number of the rendered frame ( r_visframecountvariable). This allows you to get rid of the first step:

1. Iterative PVS traversal and for each visible sheet set leaf.visframe = r_visframecount
2. Then test the sheet with if (leaf.visframe == r_visframecount)

Getting rid of recursion

In, R_SetupFrameinstead of performing a “quick and dirty” recursion, a while loop is used to bypass the BSP and retrieve the current position.

	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];
	}

Minimizing Texture Switching

In openGL, switching textures with ( glBindTexture(GL_TEXTURE_2D,id)) is very expensive. To minimize the number of texture switching, each polygon marked for rendering is stored in a chain of arrays indexed by the polygon texture material.

cl.worldmodel->textures[textureId]->texturechain[]

After clipping is complete, texture chains are drawn in order. Thus, a total of N texture switches are performed, where N is the total number of visible textures.

	int i;
	for ( i = 0; i < cl.worldmodel->textures_num ; i ++)
		DrawTextureChains(i);