Quake engine
Encyclopedia
The Quake engine is the game engine
Game engine
A game engine is a system designed for the creation and development of video games. There are many game engines that are designed to work on video game consoles and personal computers...

 that was written to power 1996's Quake, written by id Software
Id Software
Id Software is an American video game development company with its headquarters in Richardson, Texas. The company was founded in 1991 by four members of the computer company Softdisk: programmers John Carmack and John Romero, game designer Tom Hall, and artist Adrian Carmack...

. It featured true 3D real-time rendering and is now licensed under the terms of the GNU General Public License
GNU General Public License
The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....

 (GPL).

After release it immediately fork
Fork (software development)
In software engineering, a project fork happens when developers take a legal copy of source code from one software package and start independent development on it, creating a distinct piece of software...

ed, as did the level design. Much of the engine remained in Quake II
Quake II
Quake II, released on December 9, 1997, is a first-person shooter computer game developed by Id Software and distributed by Activision. It is not a sequel to Quake; it merely uses the name of the former game due to Id's difficulties in coming up with alternative names.The soundtrack for Quake II...

and Quake III Arena
Quake III Arena
Quake III Arena , is a multiplayer first-person shooter video game released on December 2, 1999. The game was developed by id Software and featured music composed by Sonic Mayhem and Front Line Assembly...

. The Quake engine, like the Doom engine
Doom engine
The Doom engine is the game engine that powers the id Software games Doom and Doom II. It is also used by HeXen, Heretic, Strife, Freedoom, and HacX, and other games produced by licensees. It was created by John Carmack, with auxiliary functions written by Mike Abrash, John Romero, Dave Taylor and...

, used binary space partitioning
Binary space partitioning
In computer science, binary space partitioning is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.Originally, this approach was proposed in 3D computer...

 (BSP). The Quake engine also used Gouraud shading
Gouraud shading
Gouraud shading, named after Henri Gouraud, is an interpolation method used in computer graphics to produce continuous shading of surfaces represented by polygon meshes...

 for moving objects, and a static lightmap
Lightmap
A lightmap is a data structure which contains the brightness of surfaces in 3d graphics applications such as video games. Lightmaps are precomputed and used for static objects. Quake was the first computer game to use lightmaps to augment rendering. Before lightmaps were invented, realtime...

 for nonmoving objects.

History

The Quake engine was created in 1996 for Quake. John Carmack did most of the programming of the engine, with help from Michael Abrash
Michael Abrash
Michael Abrash is a technical writer specializing in optimization and 80x86 assembly language programming, a reputation cemented by his 1990 book Zen of Assembly Language Volume 1: Knowledge. The original 8086 processor, the focus of the book, was several generations behind the state of the art by...

 in algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s and assembly
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...

 optimization
Optimization (computer science)
In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...

. It was later upgraded to id Tech 2 and id Tech 3.

Reducing 3D complexity to increase speed

Quake was the first true-3D game to use a special map design system that preprocessed and pre-rendered 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
Brush (video game)
Brushes are used in some 3D video games such as games based on the Source engine, its predecessor the Goldsrc engine, Unreal Engine's tool Unreal Editor, etc. to construct levels. Brushes can be primitive shapes , pre-defined shapes , or custom shapes...

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 the 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
Vertex (computer graphics)
A vertex in computer graphics is a data structure that describes a point in 2D or 3D space. Display objects are composed of arrays of flat surfaces and vertices define the location and other attributes of the corners of the surfaces.-Application to object models:In computer graphics, objects are...

 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 to 80 percent. 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 cloudy sky in Quake maps is in fact not open, but is covered over and enclosed with large brushes, and textured with a special skybox
Skybox (video games)
A skybox is a method of creating backgrounds to make a computer and video games level look bigger than it really is. When a skybox is used, the level is enclosed in a cuboid; and the sky, distant mountains, distant buildings, and other unreachable objects are projected onto the cube's faces , thus...

 texture that always looks the same from any viewing position, giving the illusion of a distant sky.

Precalculating lighting and shadows

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
Unified lighting and shadowing
Unified shadow and lighting is the lighting model used in the Doom 3 game developed by id Software.Previous 3D games like Quake III Arena, used separate lighting models for determining how a light would illuminate a character or a map...

 model for Doom 3
Doom 3
Doom 3 is a science fiction horror video game developed by id Software and published by Activision. An example of the first-person shooter genre, Doom 3 was first released for Microsoft Windows on August 3, 2004. The game was later adapted for Linux, as well as being ported by Aspyr Media for Mac...

. 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 3D rendering, a mechanism was developed to section off large regions of the map that are currently not visible to the player, and to not render those unseen spaces. A 3D rendering engine without any such optimizations would draw every part of the world and then attempt to determine which polygons are the closest; then hide all the other polygons behind the closest polygons (a technique known as Z-buffering
Z-buffering
In computer graphics, z-buffering is the management of image depth coordinates in three-dimensional graphics, usually done in hardware, sometimes in software. It is one solution to the visibility problem, which is the problem of deciding which elements of a rendered scene are visible, and which...

); just because a polygon is not visible does not mean it is not part of the scene calculations. With this Quake 3D engine optimization, if the player could not see into a nearby region, the 3D engine could be told ahead of time to not include any of the objects in that space in the rendering calculations, greatly reducing the rendering load on the CPU. This effect can be noticed in the game as small tunnels with sharp 90-degree bends leading from one large space into the next large space. The small tunnel is used to block view into the adjoining unrendered space, and a special type of transparent brush (called a visportal) is used 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 and below into open sky or lava, to create a low-polygonal illusion of expanse.

How sectioning is performed

A Binary Space Partitioning
Binary space partitioning
In computer science, binary space partitioning is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree.Originally, this approach was proposed in 3D computer...

 (BSP) tree is built from the map, simplifying searching for a 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
Binary tree
In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...

 have polygons of the original map associated with them, which are then used for computing each area's visibility. For each area, the VSD
Hidden surface determination
In 3D computer graphics, hidden surface determination is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint...

 algorithm finds the parts of the map for which a line of sight exists. This is called the potentially visible set
Potentially visible set
Potentially Visible Sets are used to accelerate the rendering of 3D environments. This is a form of occlusion culling, whereby a candidate set of potentially visible polygons are pre-computed, then indexed at run-time in order to quickly obtain an estimate of the visible geometry...

 (PVS).

This process uses large amounts of memory, since it should take (where 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
Run-length encoding
Run-length encoding is a very simple form of data compression in which runs of data are stored as a single data value and count, rather than as the original run...

 (RLE). This is what allowed Quake's sophisticated graphics to run 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 framebuffer.

Also while rendering the environment, a ZBuffer 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
Image scaling
In computer graphics, image scaling is the process of resizing a digital image. Scaling is a non-trivial process that involves a trade-off between efficiency, smoothness and sharpness. As the size of an image is increased, so the pixels which comprise the image become increasingly visible, making...

 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
Surface caching
Surface caching is a computer graphics technique pioneered by John Carmack, first used in the computer game Quake to apply lightmaps to level geometry. Carmack's technique was to combine lighting information with surface textures in texture-space when primitives became visible , exploiting...

 was creating new Surfaces, which are new pre-lighted textures which combines the base and lightmap textures. 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 mipmap
Mipmap
In 3D computer graphics texture filtering, MIP maps are pre-calculated, optimized collections of images that accompany a main texture, intended to increase rendering speed and reduce aliasing artifacts. They are widely used in 3D computer games, flight simulators and other 3D imaging systems. The...

s of the original texture were generated first for further walls.

The characters were lit using a constant ambient light, which value came from a structure storing ambient colors in 3D, depending on the character's position.
Characters and objects very far from the camera were not rendered in 3D: they were instead rendered as voxel
Voxel
A voxel is a volume element, representing a value on a regular grid in three dimensional space. This is analogous to a pixel, which represents 2D image data in a bitmap...

s: 3d big square points of a single color (which came from the object texture).

Hardware 3D acceleration

Quake was also one of the first games to support 3D hardware acceleration. While initially released with only software rendering
Software rendering
In the context of rendering , software rendering refers to a rendering process that is unaided by any specialized graphics hardware, such as a graphics card. The rendering takes place entirely in the CPU...

, John Carmack created a version of the Quake executable that took advantage of Rendition
Rendition (company)
Rendition was a maker of 3D graphics chipsets in the mid- to late-90's. They were known for products such as the Vérité 1000 and Vérité 2x00 and for being one of the first 3D chipset makers to directly work with Quake developer John Carmack to make a hardware-accelerated version of the game ....

's Vérité 1000 graphics chip (VQuake). OpenGL
OpenGL
OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...

 support was soon added in the form of the GLQuake executable for Windows 95 and higher. Many believe that this kick-started the independent 3D graphics card revolution, GLQuake being the first application to truly demonstrate the capabilities of the 3dfx
3dfx
3dfx Interactive was a company that specialized in the manufacturing of 3D graphics processing units and, later, graphics cards. It was a pioneer in the field for several years in the late 1990s until 2000 when it underwent one of the most high-profile demises in the history of the PC industry...

 "Voodoo" chipset at the time. The only other cards capable of rendering GLQuake were a professional (and very expensive) Intergraph
Intergraph
Intergraph Corporation is an American software development and services company. It provides enterprise engineering and geospatially powered software to businesses, governments, and organizations around the world. Intergraph operates through two divisions: Process, Power & Marine and Security,...

 3D OpenGL card and later, the PowerVR
PowerVR
PowerVR is a division of Imagination Technologies that develops hardware and software for 2D and 3D rendering, and for video encoding, decoding, associated image processing and Direct X, OpenGL ES, OpenVG, and OpenCL acceleration....

 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 multitexturing second unit having to be reconfigured with another lightmap. This architecture decision reduced hardware-accelerated rendering performance.

Player movement

Quake by default used the keyboard to turn left and right and move forward and backward, using the mouse, like Doom, to do the same movements. This produced awkward movements, and required settings like "auto-level" that would move the viewpoint back to straight forward as the player moved and "auto vertical aim" that would automatically shoot things above and below the player. Probably because of this, the level design in Quake was more suited to the 2.5D
2.5D
2.5D , 3/4 perspective and pseudo-3D are terms used to describe either:* 2D graphical projections and techniques which cause a series of images or scenes to fake or appear to be three-dimensional when in fact they are not, or* gameplay in an otherwise three-dimensional video game that is...

 environment of Doom. Only in a few spots in the game was the attacking monster far above or below the player. Quake did have the option of using the mouse to look/aim/orient ("mouselook
Free look
Free look describes the ability to move the mouse to rotate the player character's view in video games. It is almost always used for 3D game engines, and has been included on role-playing games, real-time strategy games, third-person shooters, first-person shooters, racing games, and flight...

") and the keyboard to move forward, backward and sideways, but it was not the default until Quake III Arena was released.

Network play

Quake includes cooperative
Cooperative gameplay
Cooperative gameplay is a feature in video games that allows players to work together as teammates. It is distinct from other multiplayer modes, such as competitive multiplayer modes like player versus player or deathmatch...

 and deathmatch
Deathmatch (gaming)
Deathmatch or Player vs All is a widely-used gameplay mode integrated into many shooter and real-time strategy computer games...

 multiplayer modes over LAN
Local area network
A local area network is a computer network that interconnects computers in a limited area such as a home, school, computer laboratory, or office building...

 or the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...

. Additional multi-player modes were later added using mods
Mod (computer gaming)
Mod or modification is a term generally applied to personal computer games , especially first-person shooters, role-playing games and real-time strategy games. Mods are made by the general public or a developer, and can be entirely new games in themselves, but mods are not standalone software and...

.

Quake uses the client–server model, where a server
Game server
A game server is a remotely or locally run server used by game clients to play multiplayer video games. Most video games played over the Internet operate via a connection to a game 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
Peer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...

 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

On December 21, 1999, John Carmack of id Software released the Quake engine source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...

 on the Internet under the terms of the GPL, allowing programmers to edit the engine and add new features. Soon programmers were releasing new versions of the engine on the net. A few of the most known engines are:
  • DarkPlaces – An engine modification that adds real-time lighting and shadowing, Quake III BSP support, ogg
    Ogg
    Ogg is a free, open container format maintained by the Xiph.Org Foundation. The creators of the Ogg format state that it is unrestricted by software patents and is designed to provide for efficient streaming and manipulation of high quality digital multimedia.The Ogg container format can multiplex...

    -support, a completely new renderer, and many other features. Currently the most advanced engine modification.
  • GoldSource Engine
    GoldSrc
    GoldSrc, or Goldsource, is the retronym used internally by Valve Software to refer to the heavily modified Quake engine that powers their science fiction first-person shooter Half-Life ....

     – First engine to be created by Valve Corporation
    Valve Corporation
    Valve Corporation is an American video game development and digital distribution company based in Bellevue, Washington, United States...

    , and was used on the Half-Life series, gave rise to the Source engine
    Source engine
    Source is a 3D game engine developed by Valve Corporation. It debuted in June 2004 with Counter-Strike: Source and shortly thereafter Half-Life 2, and has been in active development ever since...

    .
  • Tenebrae – A derivative that was the first to introduce realtime lighting and shadowing to the Quake engine.
  • Telejano – A modification that adds many more features and particle effects.
  • Tomaz Quake – One of the first Quake engine modifications on the net.
  • Twilight Engine – Fastest of the known Quake engines, this modification is based on performance rather than extra features.

Games using the Quake engine

  • Quake (1996) – id Software
  • HeXen II
    Hexen II
    Hexen II is a first-person shooter developed by Raven Software from 1996 to 1997, published by id Software and distributed by Activision. It was the third game in the Hexen/Heretic series, and the last in the Serpent Riders trilogy. It was made available on Steam on August 3, 2007...

    (1997) – Raven Software
    Raven Software
    Raven Software is an American video game developer. The company was founded in 1990 by brothers Brian and Steve Raffel. In 1997, Raven made an exclusive publishing deal with Activision and was subsequently acquired by them...

  • Half-Life (1998) - Valve Corporation
    Valve Corporation
    Valve Corporation is an American video game development and digital distribution company based in Bellevue, Washington, United States...

     (Half-Life uses the Quake-based GoldSrc
    GoldSrc
    GoldSrc, or Goldsource, is the retronym used internally by Valve Software to refer to the heavily modified Quake engine that powers their science fiction first-person shooter Half-Life ....

     engine)
  • Laser Arena
    Laser Arena
    Laser Arena is a FPS PC game designed to simulate laser tag. Play modes include Free for All , Team Match, Duel, Domination and Mega Target. Players have 3 "health canisters", and every hit diminishes one of them...

    (2000) – Trainwreck Studios
  • CIA Operative: Solo Missions (2001) – Trainwreck Studios
  • Urban Mercenary (2001) – Moshpit Entertainment
  • Silver Wings (2005) – Bampusht! (Silver Wings uses a heavily modified version of Telejano v7)

Quake engine tools

  • QuArK
    Quake Army Knife
    QuArK , is a free and open source program for developing 3D assets for a large variety of video games, mostly first-person shooters using engines similar to or based on the Quake engine by id Software...

    – a multi-purpose tool for Quake engine-based games.

See also

  • List of game engines
  • First person shooter engine
  • id Tech
    Id Tech
    id Tech is the family of game engines designed and developed by id Software. Prior to the presentation of the id Tech 5-based game Rage, the engines lacked official designation and as such were referred to as the Doom and Quake engines, from the name of the main game series the engines have been...


External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK