Quake engine

(Redirected from Surface caching)

Developer(s) id Software, (John Carmack, Michael Abrash, John Cash) 1.09 / December 21, 1999; 21 years ago github.com/id-Software/Quake C, Assembly (for software rendering & optimization) DOS, AmigaOS, Microsoft Windows, macOS, Linux, Amiga, PowerPC, Nintendo 64, RiscPC, Zeebo Doom engine Quake II engine, GoldSrc GNU GPL-2.0-or-later www.idsoftware.com

The Quake engine is the game engine developed by id Software to power their 1996 video game Quake. It featured true 3D real-time rendering and is now licensed under the terms of GNU General Public License v2.0 or later.

After release, it immediately forked, as did the level design. Much of the engine remained in Quake II and Quake III Arena. The Quake engine, like the Doom engine, used binary space partitioning (BSP) to optimise the world rendering. The Quake engine also used Gouraud shading for moving objects, and a static lightmap for nonmoving objects.

Historically, the Quake engine has been treated as a separate engine from its successor, the Quake II engine. However, both engines are now considered variants of id Tech 2. Although, the codebases for Quake and Quake II were separate GPL releases.[1][2]

History

The Quake engine was developed from 1995 for the video game Quake, released on June 22, 1996. John Carmack did most of the programming of the engine, with help from Michael Abrash in algorithms and assembly optimization. The Quake II engine (id Tech 2) was based on it.

John Romero initially conceived of Quake as an action game taking place in a fully 3D polygon world, inspired by Sega AM2's 3D fighting game Virtua Fighter. Quake was also intended to feature Virtua Fighter influenced third-person melee combat. However, id Software considered it to be risky, and it would've taken longer to develop the engine. Because the project was taking too long, the third-person melee was eventually dropped.[3][4]

Engine design and milestones

Reducing 3D complexity to increase speed

Simplified process of reducing map complexity in Quake

Quake was the first true-3D game to use a special map design system that preprocessed and pre-rendered some elements of the 3D environment, so as to reduce the processing required when playing the game on the 50–75 MHz CPUs of the time. The 3D environment in which the game takes place is referred to as a map, even though it is three-dimensional in nature rather than a flat 2D space. The map editor program uses a number of simple convex 3D geometric objects known as brushes that are sized and rotated to build the environment. The brushes are placed and oriented to create an enclosed, empty, volumetric space, and when the design is complete, the map is run through the rendering preprocessor. The preprocessor is used to locate two types of empty space in the map: the empty space enclosed by brushes where the game will be played and the other empty space outside the brushes that the player will never see. The preprocessor then strips away the back faces of the individual brushes, which are outside the game space, leaving only a few polygons that define the outer perimeter of the enclosed game space.

Generally, once a map has been preprocessed, it cannot be re-edited in a normal fashion because the original brushes have been cut into small pieces. Instead, the original map editor data with the brushes is retained and used to create new versions of the map. But it is possible to edit a processed map by opening it in a special vertex editor and editing the raw vertex data, or to add or remove individual triangle faces. Though difficult, this technique was occasionally used by cheaters to create windows in walls, to see normally hidden enemies approaching from behind doors and walls, and resulted in an anti-cheat mechanism used in recent 3D games that calculates a checksum for each file used in the game, to detect players using potentially hacked map files.

A processed map file can have a much lower polygon count than the original unprocessed map, often by 50–80%. On the 50–75 MHz PCs of the time, it was common for this pruning step to take many hours to complete on a map, often running overnight if the map design was extremely complex.

This preprocessing step cannot work if there are any small holes or "leaks" that interconnect the interior game space with the exterior empty space, and it was common for complex map-building projects to be abandoned because the map designer could not locate the leaks in their map. To prevent leaks, the brushes should overlap and slightly interpenetrate each other; attempting to perfectly align along the edges of unusually shaped brushes on a grid can result in very small gaps that are difficult to locate.

The open sky in Quake maps is in fact not open, but is covered over and enclosed with large brushes, and textured with a special skybox texture, which is programmed to use sphere mapping, and thus always looks the same from any viewing position, giving the illusion of a distant sky.

Quake also incorporated the use of lightmaps and 3D light sources, as opposed to the sector-based static lighting used in games of the past. id Software's innovation has been used for many 3D games released since, particularly first-person shooters, though id Software switched to a Unified lighting and shadowing model for Doom 3 (however, they switched back to a lightmapped or semi-lightmapped method starting with RAGE). After a map had been pruned of excess polygons, a second preprocessing system was used to precalculate and bake the lightmaps into the game map to further reduce load on the CPU when playing the game. However, full light processing could take an extremely long time, so for the initial map design process, lesser-quality light processing could be done, but at the cost of creating a jagged stair-step lightcast around lights.

Sectioning the map to increase speed

To further decrease the workload of 3D rendering, a mechanism was developed to section off large regions of the map not currently visible to the player, so the engine would not need to render those unseen spaces. A 3D rendering engine without any such optimizations must draw every part of the world and then attempt to determine which polygons are the closest, then hide all polygons located behind these closest polygons (a technique known as Z-buffering). Just because a polygon is not visible does not mean it is excluded from the scene calculations.

The Quake engine was optimized specifically to obviate this problem. The engine could be told ahead of time to not calculate rendering for all objects in any space out of the player's view, greatly reducing the rendering load on the CPU. This effect is noticeable in the game as small tunnels with sharp 90-degree bends leading from one large space into another. This small tunnel serves to block view into the adjoining unrendered space, and a special type of transparent brush (called a visportal) is placed within it to define the edge of where the engine should stop rendering the adjoining space. It is uncommon in the original Quake to be able to see across the entire length of a map, and outdoor spaces are often very tall and narrow, primarily utilizing distance above into open sky or below into lava to create a low-polygonal illusion of expanse.

How sectioning is performed

A binary space partitioning (BSP) tree is built from the map, simplifying complexity of searching for a given polygon to O(number of polygons). Each leaf creates some area of 3D space (imagine cutting a pie into arbitrary pieces). The leaves of this binary tree have polygons of the original map associated with them, which are then used for computing each area's visibility. For each area, the VSD algorithm finds the parts of the map for which a line of sight exists. This is called the potentially visible set (PVS).[5]

This process uses large amounts of memory, since it should take ${\displaystyle O(n^{2})}$ (where ${\displaystyle n}$ is the number of polygons) bits (only visible/hidden information is needed). John Carmack realized that one area sees just a small fraction of the other areas, so he compressed this information by using run-length encoding (RLE). This is what allowed Quake's complex geometry to be rendered so quickly on the hardware of the time.

Speeding up the rendering, and rendering order

To reduce overdraw (rendering a new pixel that hides a previously rendered point, meaning the previous work was useless and wasted), the environment was displayed first, from front to back. To hide parts of walls hidden by other walls, a Global Edge List was sorting edges of already rendered polygons; new polygons were first clipped against previous edges so that only visible parts would get to the frame buffer.

Also while rendering the environment, a z-buffer was filled but never read while rendering the environment, as the BSP tree and Global Edge List ensured that each pixel was rendered only once. The ZBuffer was later used to render correctly characters and other moving objects that were partially hidden by the environment.

The pixel rendering loop was implemented in assembly. The texture coordinates perspective correction and interpolation was done using the floating-point unit, due to the limited number of integer registers; it also allows to compute expensive division operation (part of perspective correction) on the floating-point unit in parallel with integer interpolation (in other words, at no cost).

The base texture and the lightmap of a wall were rendered at the same time: a "surface cache" was creating new surfaces, which are new pre-lighted textures which combines the base and light map textures baked together. Surfaces not used since a few frames were released, while new required Surfaces were dynamically created. Generating the surfaces was consuming less time than a secondary lighting pass would have. To save memory, smaller surfaces using mipmaps of the original texture were generated first for further walls.

Characters were lit by an ambient light and fixed distant light both dependent on the light level of the spot on the floor where the character was standing. Close-by characters were Gouraud shaded and affinely textured, whereas faraway characters were rendered using triangle subdivision.[6]

Hardware 3D acceleration

Quake was one of the first games to support 3D hardware acceleration. While initially released with only software rendering, John Carmack created a version of the Quake executable that took advantage of Rendition's Vérité 1000 graphics chip (VQuake). OpenGL support was added in the form of the GLQuake executable for Windows 95 and higher. Other cards capable of rendering GLQuake were a professional (and very expensive) Intergraph 3D OpenGL card and later, the PowerVR cards.

To optimize the software rendering engine, lightmaps were shared by polygons that were close in space, and in the same leaf of the BSP tree. This means that quite often polygons using the same main texture could not be rendered at the same time with the 3D acceleration, due to the multi-texturing second unit having to be reconfigured with another lightmap. This architecture decision reduced hardware-accelerated rendering performance.[clarification needed]

Network play

Quake includes cooperative and deathmatch multiplayer modes over LAN or the Internet. Additional multiplayer modes were later added using mods.

Quake uses the client–server model, where a server has control of all game events. All players connect to this server in order to participate, with the server telling the clients what is happening in the game. The server may either be a dedicated server or a Listen Server. Even in the latter situation, Quake still uses the client-server model, as opposed to the peer-to-peer networking used by some other games. Quake thus cannot suffer from de-synchronized network games that could occur from different clients disagreeing with each other, since the server is always the final authority.

Derivative engines

Family tree illustrating derivations of Quake engines (this graph was last updated in 2013)

On December 21, 1999, John Carmack of id Software released the Quake engine source code on the Internet under the terms of GPL-2.0-or-later, allowing programmers to edit the engine and add new features. Programmers were soon releasing new versions of the engine on the net. Some of the most known engines are:

• DarkPlaces – A significantly modified engine used in several standalone games and Quake mods.[7] Although its last stable release was on May 13, 2014, it has received numerous updates through its SVN repository since then.[8] Its home page is hosted on Icculus.org, which also hosted its repository until 2021, when the engine switched to a Git repository hosted on GitHub.[9] Team Xonotic provides mirrors of DarkPlaces source code on various social coding platforms[10][11] since the game is built on and distributed with the development version of the engine.
• GoldSrc – The first engine to be created by Valve. It was used in the Half-Life series, gave rise to the Source engine.
• MarkV – (Derivitave of Fitzquake and Glquake) a pretty barebones Quake sourceport that includes various features from darkplaces and other engines that can be toggled on or off such as improved visual effects, head bobbing, and weapon render styles.
• Quakespasm – a modern, cross-platform Quake 1 engine based on FitzQuake. It includes support for 64 bit CPUs and custom music playback, a new sound driver, some graphical niceities, and numerous bug-fixes and other improvements. Recommended by id Software co-founder, John Romero.[12]
• Telejano – A modification that adds many more features and particle effects.
• Tenebrae – A derivative that was the first to introduce real-time lighting and shadowing to the Quake engine.
• Tomaz Quake – One of the first Quake engine modifications on the net. Tomaz Quake was last updated as version 1.481 on June 8, 2010.
• Twilight Engine – The fastest of the known Quake engines, this modification is based on performance rather than extra features.
• vkQuake – (Derivative of Quakespasm) Uses Vulkan API for rendering programmed by id Software employee Axel Gneiting, released under the GPLv2.[13][14]

Games using the Quake engine

Year Title Developer(s) Publisher(s)
1996 Quake id Software GT Interactive
1997 Quake Mission Pack No. 1: Scourge of Armagon Hipnotic Interactive 3D Realms
Quake Mission Pack No. 2: Dissolution of Eternity Rogue Entertainment 3D Realms
Hexen II Raven Software id Software, Activision
Malice Ratloop Quantum Axcess
X-Men: The Ravages of Apocalypse Zero Gravity Entertainment WizardWorks
1998 Hexen II Mission Pack: Portal of Praevus Raven Software id Software, Activision
2000 Laser Arena Trainwreck Studios ValuSoft
2001 CIA Operative: Solo Missions 2015, Inc., Trainwreck Studios ValuSoft
Urban Mercenary Moshpit Entertainment
2002 Eternal War: Shadows of Light Two Guys Software Two Guys Software
2005 Nexuiz Alientrap Alientrap
2011 Xonotic Team Xonotic Team Xonotic
2021 Wrath: Aeon of Ruin 3D Realms 3D Realms, 1C Entertainment

Quake engine tools

• QuArK – A multipurpose tool for Quake engine-based games.
• Trenchbroom 2.0 – A map editor for Quake engine-based games.
• PakExpl – Used for opening the .pak files that carry Quake's model, sound, and level data, as well as the progs.dat file.
• fteqccgui – Used to open the progs.dat file in order to edit the quakec files that control entity behavior.
• qME 3.1 – The final version of the Quake model editing tool, can be used to convert traditional 3d model files into Quake's .mdl format.
• qPAK – Another tool for opening Quake .pak archives. Comes bundled with qME.

References

1. ^ "Quake engine GPL release". Retrieved May 24, 2020.
2. ^ "id Tech 2 GPL release". Retrieved May 24, 2020.
3. ^ "Does John Romero Still Enjoy Shooting People?". Next Generation. No. 30. June 1997. pp. 9–12.
4. ^ Edge, May 1997, My original idea was to do something like Virtua Fighter in a 3D world, with full-contact fighting, but you'd also be able to run through a world, and do the same stuff you do in Quake, only when you got into these melees, the camera would pull out into a third-person perspective. It would've been great, but nobody else had faith in trying it. The project was taking too long, and everybody just wanted to fall back on the safe thing – the formula.
5. ^ Abrash, Michael. "Quake's 3-D Engine: The Big Picture". Retrieved August 22, 2012.
6. ^ https://bluesnews.com/abrash/chap69.shtml
7. ^ "DarkPlaces Homepage". icculus.org. Retrieved November 6, 2017.
8. ^ "Darkplaces subversion repository". svn.icculus.org. Retrieved August 9, 2019.
9. ^ darkplacesengine/darkplaces, DarkPlaces Engine, June 14, 2021, retrieved June 21, 2021
10. ^ "DarkPlaces Quake Engine on Xonotic GitLab". Retrieved February 3, 2020.
11. ^ "DarkPlaces Quake Engine on Xonotic GitHub". Retrieved November 6, 2017.
12. ^ "If you're planning on playing Quake today, one of the best source ports is QUAKESPASM". Retrieved August 5, 2021.
13. ^ Gneiting, Axel (July 20, 2016). "My Vulkan Quake 1 Port running "In the Shadows" mod. Some stuff still missing. Code is here https://github.com/Novum/vkQuake". Twitter. Retrieved August 6, 2016.
14. ^ "Vulkan Quake port based on QuakeSpasm". github.com/Novum/vkQuake. Retrieved August 6, 2016.