Source code analysis Doom 3


On November 23, 2011 id Software supported its own tradition and published the source code of its previous engine.

This time, it's time idTech4 , which was used in Prey, in Quake 4 and, of course, in Doom 3. In just a few hours more than 400 forks of the repository on GitHub were created, people began to explore the internal mechanisms of the game or port it to other platforms. I also decided to participate and created a Intel version for Mac OS X , which John Carmack kindly advertised .

From the point of view of cleanliness and comments, this is the best release of the id Software code since the code base Doom iPhone (which was released later, and therefore commented better). I highly recommend that everyone learn this engine, collect it and experiment.

Here are my notes about what I understood. As usual, I cleaned them, I hope they save someone a couple of hours and encourage someone to study the code to improve their programming skills.
Part 1: Overview of
I noticed that I use more and more illustrations and less text to explain the code base. Previously, I used gliffy for this, but it has annoying restrictions (for example, lack of an alpha channel). I'm thinking of creating my own tool based on SVG and Javascript specifically for illustrations on 3D-engines. I wonder if there is already something like that? Well, okay, back to code ...
It's very nice to get access to the source code of such an amazing engine. At the time of release in 2004, Doom III set new graphics and sound standards for real-time engines, the most notable being Unified Lighting and Shadows. For the first time technology allowed artists to express themselves with Hollywood scope. Even eight years later, the first meeting with HellKnight in Delta-Labs-4 still looks incredibly spectacular:
The first contact
The source code is now distributed through Github and this is good, because the FTP server id Software almost always lay or was overloaded.


Original release TTimo is compiled normally using Visual Studio 2010 Professional. Unfortunately, in Visual Studio 2010 "Express" there is no MFC and therefore it can not be used. After the release, it was somewhat disappointing, but since dependencies have been deleted .

Windows 7 :

git clone https://github.com/TTimo/doom3.gpl.git


For reading and researching code, I prefer to use XCode 4.0 on Mac OS X: the speed of searching from SpotLight, highlighting variables, and "Command-Click" to navigate to the right place make work more convenient than in Visual Studio. The XCode project for the release was broken, but its it's very simple to fix , and now there is a Github repository of the user "bad sector" that works well on Mac OS X Lion.

MacOS X :

git clone https://github.com/badsector/Doom3-for-MacOSX-

Notes: it turned out that the highlighting of variables and the "Control-Click" transition are also available in Visual Studio 2010 after installing Visual Studio 2010 Productivity Power Tools . I do not understand why this is not in the "vanilla" package installation.

Both codebases are now in the best condition: one click is enough to build the executable! <Tgsrb>

Download the code.
Press F8 / Command-B.
You can run!

<b> Interesting fact:
to start the game you will need a folder with the Doom 3 resource. I did not want to waste time extracting them from the Doom 3 CDs and updating, so I downloaded the Steam version. It seems that the guys from id Software did the same because in the debugging settings of the published Visual Studio project there is still "+ set fs_basepath C: \ Program Files (x86) \ Steam \ steamapps \ common \ doom 3 "!

Interesting fact: The engine was developed in Visual Studio .NET ( the sources ). But in the code there is not a single line in C #, and the published version for compilation requires Visual Studio 2010 Professional.

Interesting fact: It seems that the Id Software team are fans of the "Matrix" franchise: the working title Quake III was "Trinity", and the Doom III work title was "Neo". This explains why all of the source code is in the neo subfolder.
The game is divided into projects that reflect the overall architecture of the engine:
Projects Assemblies Notes
Windows Mac OS X
Game gamex86.dll gamex86.so Gameplay Doom3
Game-d3xp gamex86.dll gamex86.so Gameplay Doom3 eXPension (Ressurection)
MayaImport MayaImport.dll - Part of the resource creation tool: loaded at run time to open Maya files and import monsters, camera routes and maps.
Doom3 Doom3.exe Doom3.app Doom 3 engine
TypeInfo TypeInfo.exe - Internal auxiliary RTTI file: generatesGameTypeInfo.h, a map of all types of Doom3 classes with the size of each element. This allows you to debug memory using the TypeInfo class.
CurlLib CurlLib.lib - An HTTP client used to download files (statically linked to gamex86.dll and doom3.exe)
idLib idLib.lib idLib.a Library id Software. Includes parser, lexical analyzer, dictionary ... (statically linked to gamex86.dll and doom3.exe).
As in all other engines, starting with idTech2, we see one binary file with closed sources (doom.exe) and one dynamic library with open source code (gamex86.dll):


Most of the code base was available from October 2004 in the Doom3 SDK , only the source code for the Doom3 executable was missing. Modders could collect idlib.a and gamex86.dll, but the kernel of the engine was still closed.

Note: The engine does not use the standard C ++ library: all containers (map, list with pointers ...) are implemented again, but actively using libc.

Note: In the Game module, each class inherits idClass. This allows the engine to perform internal RTTI and create instances of classes by class name.

Interesting fact: If you look at the illustration, you will notice that some necessary frameworks (such as FileSystem) are in the Doom3.exe project. This presents a problem, because gamex86.dll must also load resources. These subsystems are dynamically loaded with the gamex86.dll from doom3.exe (this is what the arrow in the illustration means). If you open the DLL in PE explorer, you can see that gamex86.dll exports one method: GetGameAPI:


Everything works just like Quake2 loaded the renderer and gaming ddl , passing pointers to objects:

When Doom3.exe is loaded, it:

Loads the DLL into the process memory space using the LoadLibrary.
Gets the GetGameAPI address in the dll using GetProcAddress win32.
Calls GetGameAPI.

gameExport_t * GetGameAPI_t( gameImport_t *import ); At the end of this "communication setup" Doom3.exe there is a pointer to the object "idGame", and in Game.dll there is a pointer to the object gameImport_t, which contains additional references to all missing subsystems, for example, idFileSystem.

How Gamex86 sees the objects of the executable Doom 3:

typedef struct {

            int version; // API version
            idSys * sys; // non-portable system services
            idCommon * common; // common
            idCmdSystem * cmdSystem // console command system
            idCVarSystem * cvarSystem; // system of console variables
            idFileSystem * fileSystem; // file system
            idNetworkSystem * networkSystem; // network system
            idRenderSystem * renderSystem; // rendering system
            idSoundSystem * soundSystem; // sound system
            idRenderModelManager * renderModelManager; // rendering model dispatcher
            idUserInterfaceManager * uiManager; // User interface manager
            idDeclManager * declManager; // Ad Manager
            idAASFileManager * AASFileManager; // AAS file manager
            idCollisionModelManager * collisionModelManager; // collision model manager

} gameImport_t;
How Doom 3 sees the Game / Modd objects:

typedef struct

        int version; // API version
        idGame * game; // interface for playing the game
        idGameEdit * gameEdit; // interface for in-game editing

} gameExport_t;
Notes: an excellent resource for better understanding each subsystem - Doom3 SDK documentation page : it looks like it was written in 2004 by a person with a deep understanding of the code (that is, most likely one of the development team).
Before parsing, here are some statistics fromcloc:

./cloc-1.56.pl neo

2180 text files.
2002 unique files.
626 files ignored.

http://cloc.sourceforge.net v 1.56 T=19.0 s (77.9 files/s, 47576.6 lines/s)

Language files blank comment code
C++ 517 87078 113107 366433
C/C++ Header 617 29833 27176 111105
C 171 11408 15566 53540
Bourne Shell 29 5399 6516 39966
make 43 1196 874 9121
m4 10 1079 232 9025
HTML 55 391 76 4142
Objective C++ 6 709 656 2606
Perl 10 523 411 2380
yacc 1 95 97 912
Python 10 108 182 895
Objective C 1 145 20 768
DOS Batch 5 0 0 61
Teamcenter def 4 3 0 51
Lisp 1 5 20 25
awk 1 2 1 17
SUM: 1481 137974 164934 601047
By the number of lines of code, it's usually impossible to say anything definite, but here it will be very useful for evaluating the work necessary to understand the engine. In the code 601 047 lines, that is, the engine is twice as difficult to understand than Quake III. A few statistics about the history of id Software engines in the number of lines of code:
The lines of code Doom idTech1 idTech2 idTech3 idTech4
The 39079 143855 135788 239398 601032
Tools 341 11155 28140 128417 -
Total 39420 155010 163928 367815 601032

Note: A significant increase in the volume in idTech3 was due to tools from the code base lcc (the C compiler was used to generate the QVM bytecode).

Note: For Doom3 tools are not taken into account, because they are included in the code base of the engine.

At a high level, you can see a couple of funny facts:

For the first time in the history of id Software, the code is written in C ++, not C. John Carmack explained this in an interview.

The code actively uses abstraction and polymorphism. But an interesting trick allows you to avoid reducing the performance of vtable on some objects.
All resources are stored in human readable text format. No more binary files. The code actively uses the lexical analyzer / parser. John Carmack told about it in an interview.
Templates are used in low-level helper classes (mostly in idLib), but they are never applied on higher layers, so the code, unlike Google V8, does not cause the eyes to bleed.
From the point of view of commenting, this is the second-most-quality code base id software, it's better only Doom iPhone , perhaps because it came out later Doom3. 30% of comments - still an outstanding result, it is very rare to find a well documented project! In some parts of the code (see the section on dmap) there are more comments than the code.
OOP encapsulation made the code cleaner and simplified its reading.
Days of low-level assembler optimization have passed. Some tricks, for example, idMath :: InvSqrt and optimization of spatial localization are preserved, but basically the code simply uses the available tools (GPU shaders, OpenGL VBO, SIMD, Altivec, SMP, optimization L2 R_AddModelSurfaces for model processing ...).

It's also interesting to look at The standard for writing idTech4 code ( mirror ), written by John Carmack (in particular I'm grateful for the comment about the location of the const).
Expand the loop
Here is the analysis of the main loop with the most important parts of the engine:

idCommonLocal commonLocal; // specialized object of OS
    idCommon * common = & commonLocal; // The interface pointer (since Init is dependent on the OS, this is an abstract method)

int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow )

Sys_SetPhysicalWorkMemory( 192 << 20, 1024 << 20 ); //Min = 201,326,592 Max = 1,073,741,824

        // Because the engine is multithreaded, mutexes are initialized here: one mutex per "critical" (concurrently executable) part of the code.
for (int i = 0; i < MAX_CRITICAL_SECTIONS; i++ ) {
InitializeCriticalSection( &win32.criticalSections[i] );

        common-> Init (0, NULL, lpCmdLine); // Estimate the amount of available VRAM (it's not done through OpenGL, but by calling the OS)

        Sys_StartAsyncThread () {// The next one is executed in a separate thread.
while ( 1 ){
                usleep (16666); // Performed at 60 Hz
                common-> Async (); // Completing of the work
                Sys_TriggerEvent (TRIGGER_EVENT_ONE); // Unlock other threads waiting to be entered
                pthread_testcancel (); // Check if the task was canceled by the main thread (when the game is closed).


while( 1 ){
            Win_Frame (); // Displays / hides the console
                session-> Frame () // Game logic
for (int i = 0 ; i < gameTicsToRun ; i++ )
                            game-> RunFrame (& cmd); // From this point, execution passes to the GameX86.dll address space.
for( ent = activeEntities.Next(); ent != NULL; ent = ent->activeNode.Next() )
                                ent-> GetPhysics () -> UpdateTime (time); // let the elements think

                session-> UpdateScreen (false); // the usual serial update of the screen
                        idGame :: Draw // Frontend renderer. Does not exchange data with the video processor!
                        R_IssueRenderCommands // Backend renderer. Transmits optimized video processor commands to the video processor.

More information about the completely disassembled cycle can be here . When I read the code, I used it as a map.

The standard cycle for the id Software engines is main. Except for the Sys_StartAsyncThread, which means that Doom3 is multithreaded. The task of this thread is to control the time-critical functions that the engine should not limit the frame rate:

Mixing sound.
Generating user input.

Interesting fact: all high-level idTech4 objects are abstract classes with virtual methods. Typically, this reduces performance, because the address of each virtual method before calling it at runtime must be found in the vtable. But there is a "trick" that allows this to be avoided. Instances of all objects are statically created as follows:

idCommonLocal commonLocal; // Implementation
    idCommon * common = & commonLocal; // Pointer to gamex86.dll
Since an object statically placed in a data segment has a known type, the compiler can optimize the search in the vtable when calling thecommonLocal methods. When the connection is established (handshake), the interface pointer is used, so doom3.exe can exchange links to objects with gamex86.dll, but in this case the search costs in vtable are not optimized.

Interesting fact: having studied most of the id Software engines, I find it remarkable that one method name has NEVER changed since the doom1 engine: the method that reads the data entered from the mouse and the joystick called the IN_frame ().
Two important parts:

Since Doom3 uses a portal system, the preprocessing tooldmap is completely different from the traditional bsp linker. I reviewed it below in the appropriate section.

The run-time renderer has a very interesting architecture. It is divided into two parts with a frontend and a backend (for more details, see the section "Renderer" below).

I used the Instruments from Xcode to check what the loops are doing CPU. For results and analysis, see "Profiling" below.
Scripting and virtual machine
In each product, idTech VM and the scripting language completely changed ... and id did it again (for more details see the "Script VM" section)
While reading the code, I was puzzled by some innovations, so I wrote to John Carmack and he was so polite that he answered and explained in detail the following features:

Splitting the renderer into two parts.
Text resources.
Interpreted bytecode.

In addition, I collected on one page all the videos and interviews with the press about idTech4. All of them are collected on the interview page .
Part 2: Dmap
Like in all id Software engines, the team of map designers undergoes a powerful pre-processing of the utility to increase performance at runtime.

In idTech4 this utility is called dmap and its purpose is to read the soup from polyhedra from the.map file, identify the areas connected by the portals and save them in the .proc file.

The purpose of this tool is to use the runtime portal system in doom3.exe. There is an amazing article by Seth Teller in 1992: Visibility Computations in the Densely Occluded Polyhedral Environment . It describes in detail and with many illustrations how the idTech4 engine works.
Designers create level maps using CSG (Constructive Solid Geometry): they use polyhedrons, usually having six faces, and place them on the map.

These blocks are called "brushes" (brush). The figure below uses eight brushes (I will use the same card to explain each step of the dmap).

The designer can well understand what is "inside" (the first figure), but the dimm receives only soup from the brushes, in which there is nothing internal and external (the second figure).
What the designer sees What does Dmap see when reading brushes from a.map file.

The brush is defined not through faces, but through planes. Setting planes instead of faces may seem ineffective, but it will be very useful later, when checking whether two surfaces are on the same plane. There are no internal and external parts, because the planes are not oriented "identically". The orientation of the planes can be different inside or outside the volume.
Code overview
The source code for Dmap is very well commented out, just look at this number: more comments than code!

bool ProcessModel( uEntity_t *e, bool floodFill ) {

bspface_t *faces;

     // build a bsp tree using all sides
     // all structural brushes
faces = MakeStructuralBspFaceList ( e->primitives );
e->tree = FaceBSP( faces );

     // create portals at each intersection of leaves,
     // to enable the ability to fill
MakeTreePortals( e->tree );

     // classify the leaves as opaque or domain portals
FilterBrushesIntoTree( e );

     // check if bsp is closed completely
if ( floodFill && !dmapGlobals.noFlood ) {
if ( FloodEntities( e->tree ) ) {
         // make the leaves outside opaque
FillOutside( e );
} else {
common->Printf ( "**********************\n" );
common->Warning( "******* leaked *******" );
common->Printf ( "**********************\n" );
LeakFile( e->tree );
         // If you really need to process
         // "leaking" map, then the parameter
// -noFlood
return false;

     // get the minimal convex hull for each visible side
     // this must be done before creating portals between areas,
     // because the visible shell is used as a portal
ClipSidesByTree( e );

     // define the areas before trimming the triangles
     // in a tree so that the triangles never intersect the boundaries of the regions
FloodAreas( e );

     // Now we have a BSP tree with opaque and transparent leaves labeled with areas
     // all primitives are now truncated to them, discarded
     // fragments in opaque areas
PutPrimitivesInAreas( e );

     // now we build volumes of shadows for illumination and we cut
     // optimization lists for trees of light rays,
     // so that there is no unnecessary redrawing in the case
     // immobility
Prelight( e );

     // optimization is a superset of correcting T-shaped connections
if ( !dmapGlobals.noOptimize ) {
OptimizeEntity( e );
} else if ( !dmapGlobals.noTJunc ) {
FixEntityTjunctions( e );

     // now we correct T-shaped connections in areas
FixGlobalTjunctions( e );

return true;
0. Loading geometry level
The file.map is a list of entities. The level is the first entity in the file that has the worldspawn class. The entity contains a list of primitives, which are almost always brushes. The remaining entities are light sources, monsters, spawn points of the player, weapons, etc.

Version 2

    // entity 0
"classname" "worldspawn"
        // primitive 0
( 0 0 -1 -272 ) ( ( 0.0078125 0 -8.5 ) ( 0 0.03125 -16 ) ) "textures/base_wall/stelabwafer1" 0 0 0
( 0 0 1 -56 ) ( ( 0.0078125 0 -8.5 ) ( 0 0.03125 16 ) ) "textures/base_wall/stelabwafer1" 0 0 0
( 0 -1 0 -3776) ( ( 0.0078125 0 4 ) ( 0 0.03125 0 ) ) "textures/base_wall/stelabwafer1" 0 0 0
( -1 0 0 192 ) ( ( 0.0078125 0 8.5 ) ( 0 0.03125 0 ) ) "textures/base_wall/stelabwafer1" 0 0 0
( 0 1 0 3712 ) ( ( 0.006944 0 4.7 ) ( 0 0.034 1.90) ) "textures/base_wall/stelabwafer1" 0 0 0
( 1 0 0 -560 ) ( ( 0.0078125 0 -4 ) ( 0 0.03125 0 ) ) "textures/base_wall/stelabwafer1" 0 0 0
        // primitive 1
        // primitive 2
   // entity 37
"classname" "light"
"name" "light_51585"
"origin" "48 1972 -52"
"texture" "lights/round_sin"
"_color" "0.55 0.06 0.01"
"light_radius" "32 32 32"
"light_center" "1 3 -1"
Each brush is described as a set of planes. The sides of the brush are called faces (or bends), each of which is obtained by pruning the plane with all other planes of the brush.

Note: a very interesting and fast system of hashing of planes (Plane Hashing System) is used at the stage of loading: topidHashIndex createdPlaneSet, which is worth seeing.
1. MakeStructuralBspFaceList and FaceBSP
The first step is to cut the map in the manner of a binary space partition (Binary Space Partition). Each opaque face of the map is used as a separation plane.

The following delimiter heuristic is used:

1: if there are more than 5000 units in the map: cut it with the axis-oriented plane (Axis Aligned Plane) in the middle of the space. In the figure below, the space 6000x6000 is cut three times.


2: When there are no more than 5,000 units left: use faces labeled as "portals" (they have the textures / editor / visportal material). In the figure below, the brushes of the portals are marked in blue.


3: We use the remaining faces. We choose the face, the most collinear with the majority of the other AND cut the smallest faces. Also preference is given to the axial separators. The separation planes are marked in red.



The process ends when there are no available faces: the entire sheet of the BSP tree is a convex subspace:

2. MakeTreePortals
Now the map is divided into convex subspaces, but these subspaces know nothing about each other. The goal of this stage is to connect each of the leaves with its neighbors by automatically creating portals. The idea is to start with the six portals that limit the map: connect the "external" to the "internal" (with the BSP root). Then for each node in the BSP we separate each portal in the node, add the separation plane as a portal and recursively repeat.



The six original portals will be divided and spread down to the leaves. This is not as trivial as it seems, because each time a node is divided: each portal connected to it must also be divided.

In the figure on the left, one portal connects two nodes-the "brother" in the BSP tree. When following the left child sheet, its dividing plane divides the portal into two. We see that the portals of other nodes also need to be updated so that they no longer connect with the "brothers" and their "nephews".

At the end of the process, the six source portals are divided into hundreds of portals, and new portals are created on the separation planes:

Every sheet in the BSP now knows about its neighbors thanks to a linked list of portals connecting them to leaves that have a common edge:

3. FilterBrushesIntoTree

This stage is similar to a children's game with the selection of shapes of figures, where BSP is a board, and brushes are figures. Each brush is sent down the BSP to detect opaque leaves.

The method works thanks to a well-described heuristic: if the brush crosses the dividing plane a little, but not more than on EPSILON, then instead it goes completely to the side of the plane on which all other elements of the brush are.

Now the "internal" and "outer" parts begin to be visible.

The sheet touched by the brush is considered opaque (solid) and is marked accordingly.

4. FloodEntities and FillOutside
With the essence of the player's spawn, a fill algorithm is implemented for each sheet. He marks the leaves as achievable by entities.


The last stage of FillOutside passes through each sheet and if it is unreachable, it marks it as opaque .


We've got a level in which each subspace is either reachable or opaque: now navigating through leaf portals is uniform and is done by checking the target sheet for opacity.
5. ClipSidesByTree
It's time to discard the unnecessary parts of the brushes: each source side of the brush is sent down the BSP. If the side is inside an opaque space, then it is discarded. Otherwise, it is added to the visibleHull side list.

As a result, we get the "skin" of the level, only the visible parts are preserved.


From now on, for the remaining operations, only the visibleHull side list is considered.
6. FloodAreas
Now, dmap groups the leaves with area identifiers: a fill algorithm is implemented for each sheet. He tries to fill in all the portals associated with the sheet.

Here, the designer has great importance : the areas can be identified only if visportals (the brushes of the portals mentioned in step 1) were manually located on the map. Without them, the dmap identifies only one area and each frame in the video processor will be sent the entire map.

The recursive algorithm of pouring is stopped only by domain portals and opaque nodes. In the image below, the automatically generated portal (red) allows you to continue the fill, but the designer-placed visportal (blue, also called areaportal) will stop it, creating two areas:



At the end of the process, each non-continuous sheet belongs to the region and inter-regional portals (blue) are defined.

7. PutPrimitivesInAreas
At this stage, in another "Find a shape" game, the areas defined in step 6 and visibleHull, computed in step 5, are combined: this time the board is the areas, and the shapes are visibleHull.

An array of areas is selected and each visibleHull of each brush is sent down the BSP: the surfaces are added to the array of areas by the index areaID.

Note: is a pretty clever move - at this stage, the spawning of entities is also optimized. If some entities are labeled as "func_static", their instances are created now and are bound to the region. In this way, you can "glue" boxes, barrels and chairs to the area (also by performing a preliminary generation of their shadows).
8. Prelight
For each static light source, dimmap pre-calculates the geometry of shadow volumes. These volumes are later saved as .proc. The only trick is that the shadow volume is saved with the name "_prelight_light" connected to the light source ID so that the engine can match the light source from the.map file and the amount of shadows from the file.proc:

shadowModel { /* name = */ "_prelight_light_2900"

/* numVerts = */ 24 /* noCaps = */ 72 /* noFrontCaps = */ 84 /* numIndexes = */ 96 /* planeBits = */ 5

( -1008 976 183.125 ) ( -1008 976 183.125 ) ( -1013.34375 976 184 ) ( -1013.34375 976 184 ) ( -1010 978 184 )
( -1008 976 184 ) ( -1013.34375 976 168 ) ( -1013.34375 976 168 ) ( -1008 976 168.875 ) ( -1008 976 168.875 )
( -1010 978 168 ) ( -1008 976 167.3043518066 ) ( -1008 976 183.125 ) ( -1008 976 183.125 ) ( -1010 978 184 )
( -1008 976 184 ) ( -1008 981.34375 184 ) ( -1008 981.34375 184 ) ( -1008 981.34375 168 ) ( -1008 981.34375 168 )
( -1010 978 168 ) ( -1008 976 167.3043518066 ) ( -1008 976 168.875 ) ( -1008 976 168.875 )

4 0 1 4 1 5 2 4 3 4 5 3 0 2 1 2 3 1
8 10 11 8 11 9 6 8 7 8 9 7 10 6 7 10 7 11
14 13 12 14 15 13 16 12 13 16 13 17 14 16 15 16 17 15
22 21 20 22 23 21 22 18 19 22 19 23 18 20 21 18 21 19
1 3 5 7 9 11 13 15 17 19 21 23 4 2 0 10 8 6
16 14 12 22 20 18
9. FixGlobalTjunctions
Correction of T-junctions is usually important for getting rid of visual artifacts, but in idTech4 it is even more important: geometry is also used to generate shadows while writing to the template buffer. T-joints are twice problematic.
10. Data output
At the end, all pre-processed data is saved to a file. Proc:

For each region, a number of facets of surfaces are grouped by material.
BSP-tree with areaID for leaves.
Bends of inter-regional portals.
The amount of shadows.
Many code segments fromdmap are similar to code used in preprocessing tools Quake qbsp.exe), Quake 2 q2bsp.exe), and Quake 3 q3bsp.exe). The reason for this is that the potentially visible set (PVS) is generated using a temporary portal system:

qbsp.exe read.map and generated a .prt file containing information about the links between the leaves in the BSP portals (exactly as in step 2 of "MakeTreePortals").
vis.exe was used in .prt as an input. For each sheet:

filling with portals into bound leaves was performed.
before pouring into a sheet: the visibility was checked by cutting off the next portal with the two previous portals relative to the visibility pyramid (many believed that visibility is determined by the emission of thousands of rays, but this is a myth many believe in now).

The illustration is always better: let's say qbsp.exe found six leaves connected by portals and now is executedvis.exe to generate PVS. This process will be performed for each sheet, but in this example, we'll only cover sheet 1.


Since the sheet is always visible from itself, the original PVS for sheet 1 will be as follows:
The sheet identifier 1 2 3 4 5 6
Bit Vector (PVS for Sheet 1) 1 ? ? ? ? ?
The filling algorithm begins: the rule is that while there are no two portals in the path, the sheet is considered visible from the starting point. This means that we will reach sheet 3 with the following PVS:
The sheet identifier 1 2 3 4 5 6
Bit Vector (PVS for Sheet 1) 1 1 1 ? ? ?

In sheet 3, we can actually check visibility: taking two points from the n-2 portal and n-1 portal, we can generate clipping planes and test the following portals for potential visibility.

From the figure we see that the portals leading to leaves 4 and 6 will not pass the test, and the portal to sheet 5 will pass. Then the fill algorithm for sheet 6 will be recursively executed. At the end of PVS, for sheet 1, it will be as follows:
The sheet identifier 1 2 3 4 5 6
Bit Vector (PVS for Sheet 1) 1 1 1 0 1 0
In idTech4, PVS is not generated, instead, portal data is stored. The visibility of each area is calculated at runtime by projecting the bends of the portals into the screen space and trimming them relative to each other.

Interesting fact: Michael Abrash explained the whole process in 10 seconds with the help of a marker in this excellent video from GDC Vault (the picture is clickable):

Part 3: Renderer
The renderer idTech4 made three important innovations:

"Unified Lighting and Shadows": the faces of the level and facets of entities pass through the same pipeline and shaders.
"Visible Surface Determination": The portal system allows you to execute VSD at runtime - no more PVS.
"Multi-pass Rendering".

The most important in idTech4 was a multi-pass renderer. The effect of each light source in the scope is accumulated in the frame buffer of the video processor using additive mixing. Doom 3 fully exploits the fact that the frame buffer color registers perform saturation, not transfer.

CPU register (transfer):

1111 1111
+ 0000 0100
= 0000 0011

Video processor register (saturation):

1111 1111
+ 0000 0100
= 1111 1111

I created my own level to illustrate the additive blending. In the screenshot below, three light sources are shown in the room for which three passes are performed. The result of each pass is accumulated in the frame buffer. Note the white light in the center of the screen, where all light sources are mixed.


I changed the engine to isolate every pass:

Passage 1: blue light source

Passage 2: a source of green light

Passage 3: red light source

I made other changes to the engine to see the state of the frame buffer AFTER each pass of the light source:

The video processor buffer after the first pass

The frame buffer of the video processor after the second pass

The buffer of the video processor frame after the third pass

Interesting fact: You can take the result of each pass of the light source, mix them manually in Photoshop (Linear Dodge to simulate additive mixing of OpenGL) and get expecially the same result .

Additive blending combined with support for shadows and relief texturing (bumpmapping) create a very good picture in the engine even according to the 2012 standards:

Unlike previous engines idTech, the renderer is not monolithic, but it is divided into two parts (frontend and backend):


Analyzes the database and determines what affects the scope.
Saves the result to the intermediate view def_view_t) and loads / uses the cached geometry in the VBO of the video processor.
Gives the command RC_DRAW_VIEW.


The RC_DRAW_VIEW command activates the backend.
Uses an intermediate representation as input and passes commands to the video processor using VBO.


The renderer architecture is very similar to the LCC cross-compiler used to generate the bytecode of the Quake3 virtual machine:


I initially thought that the design of the renderer was influenced by the design of LCC, but the renderer was divided into two parts, because it was supposed to become multithreaded in SMP-systems. The frontend should have been performed in one core, and the backend in the other. Unfortunately, due to instability with some drivers, one more thread had to be disconnected and both parts are executed in one thread.

An interesting fact about the origin: With the code, you can also perform archaeological research - if you look closely at the expanded renderer code, it is clearly seen that the engine moves from C ++ to C (from objects to static methods ):

It happened because of the history of the code. The idTech4 renderer was written by John Carmack on the basis of the Quake3 engine (code base in C), until he became a C ++ specialist. Ren
xially 5 october 2017, 14:04
Vote for this post
Bring it to the Main Page


Leave a Reply

Avaible tags
  • <b>...</b>highlighting important text on the page in bold
  • <i>..</i>highlighting important text on the page in italic
  • <u>...</u>allocated with tag <u> text shownas underlined
  • <s>...</s>allocated with tag <s> text shown as strikethrough
  • <sup>...</sup>, <sub>...</sub>text in the tag <sup> appears as a superscript, <sub> - subscript
  • <blockquote>...</blockquote>For  highlight citation, use the tag <blockquote>
  • <code lang="lang">...</code>highlighting the program code (supported by bash, cpp, cs, css, xml, html, java, javascript, lisp, lua, php, perl, python, ruby, sql, scala, text)
  • <a href="http://...">...</a>link, specify the desired Internet address in the href attribute
  • <img src="http://..." alt="text" />specify the full path of image in the src attribute