CGDC Quake Talk

I took the cgdctalk.doc file as provided by Michael Abrash and converted it for distribution. The wording is his, HTML and possible related errors are mine. There is, with permission, a local copy. Please remember that these are about 30 pages with a only few lines each, and that it is a WORD document. -- b.

This document contains the transparencies for my talk at the Computer Game Developers Conference on 4/2/96. Audio and video tapes of the talk are available from the conference organizers.
Note that the Quake technology described in these transparencies can be licensed from id Software; contact Jay Wilbur (jayw@idsoftware.com), or Mike Wilson (mikew@idsoftware.com).


--Michael Abrash


The Quake Graphics Engine

by Michael Abrash, id Software.

WARNING! - Explicit technical content!!

A highly technical look inside the design of the Quake graphics engine.

1 hour != 12 months

Idea is to give you benefit of our real-world experience to help you up the learning curve.


"Pretty soon, computers will be fast." -Billy Zelsnack

Hardware isn't as fast as we'd like for realtime 3-D, and isn't going to be for a long time.

Hard frame-rate constraints.

Balancing act between visual quality and speed, all with the frame rate limit as a hard constraint--and it all changes every year as hardware moves forward.


Objectives:

For our purposes, that means sampling the right pixel from the polygon that's nearest at that pixel, and doing so at 10-15 frame/second minimum.


Problems

It would be nice to be able to chuck all the polygons at a rasterizer that was so fast that we didn't have to think any further.

Problem: no such rasterizer.

Bigger problem: level designers would just use more polygons.

The number of polygons goes up very fast with larger/more complex worlds, much more than linearly, though the number of visible polygons may not.

Problem of rejecting polygons outside the view pyramid, and frame rate variation.

#2 has been the focus for a long time, but #1 is quickly becoming the real challenge. Both must be done well in order to build a compelling engine.


Two parts to the Quake graphics engine:

These are handled very differently.

The static world.

Big (up to around 10,000 large polygons), with a continuous polygon mesh skin and any number of light sources.

Can be preprocessed very effectively.

Is compiled into a single BSP tree.


Handy facts about BSP trees:


The other part of large-scale culling:

culling polygons that are in the view pyramid but are totally obscured. Some of the techniques that were considered and/or tried:

In every case, some average performance impact, considerable worst-case impact, so frame rate wasn't very level.


Precalculate the PVS!

Precalculated the PVS from each leaf to each leaf.


Frame rate

Frame rate was still not level enough, because of overdraw.

Added another stage, edge sorting, to process the polygons in the PVS.

Add edges to global table, process all edges at once, top to bottom, emit nearest spans. Later, draw the spans for each surface in turn.

Extra sorting work, but reduced overdraw to zero, levelling performance a great deal.

Other benefits:

What key to sort on?

BSP order. BSPs contain more implicit information that you might think.


Rasterization!

Disadvantages of normal Gouraud shaded texture mapping:

Solution: surface caching

Each surface is generated from a combination of a tiled texture and a light map with light values on a 16-pixel grid.

This is cached and used as the source texture for a non-shading texture mapper.

The light map is precalculated with ray casting from lights to each grid point on each surface. Radiosity would be possible.

Per-surface mipmapping helps keep the total cache size down, and also improves appearance at a distance.

Advantages:

Disadvantages:


Time to draw!

There's a span drawer that takes the list of spans for a surface and draws the pixels.

No lighting is performed.

The screen gradients for the texture coordinates and 1/z are used to calculate perspective correct texture coordinates every 8 or 16 pixels, and linear interpolation is used between those points.

100% floating-point down to the 8 or 16 pixel subdivisions.

Hurts on 486, but Pentium floating-point is fast, and floating-point solves all sorts of range and scale problems, and allows both lowering FDIV precision and overlapping FDIV. Also, using FP registers frees up integer registers.

All in all, our inner loop is clearly faster in floating-point on Pentium than it would be in fixed-point.


Everything else--moving entities.

There are several types of entities, stored as BSP trees, polygon meshes, sprites, and particles.

Large-scale culling benefits for entities: Each entity's bounding box is clipped into the world BSP.

Only if it touches a PVS leaf is it flagged for later drawing, after the world has been processed.

Separate BSP models, such as doors, platforms, and health and ammo boxes, are clipped into the world BSP, then added to the global edge table, just like world polygons.

Doors block view past them, reducing overdraw considerably.

BSP models in the same leaf fall back to sorting against each other on 1/z.


More complex objects

More complex objects, such as torches, armor, and players can't be done with BSPs.

Sprites look startlingly non-3D in a Quake level; they're rare now, and may disappear entirely, but are an easy solution for objects like torches.

We had been clipping sprites into the world BSP and drawing the pieces by their leaves' BSP order, drawing back to front.

That approach didn't work so well for polygon models--players and monsters.

Polygon models are meshes of 100-400 polygons, with a single front/back skin stretched over them.

We couldn't clip them to the world BSP, because it would be too expensive, so we just drew each triangle in the nearest leaf it had a vertex in, which caused occasional errors.

Errors sorting polygons within models.

Errors sorting between models in same leaf (and also with other BSP models and sprites).


Z-Buffer

Tried lots of tweaks (such as putting into edge list), but none was satisfactory until John came up with a sweeping solution:

Uh... Z-buffering

We z-buffer sprites, polygon models, and all other non-BSP entities.

How low-tech can you get?

Solved all sorting problems for moving entities with NO sorting errors ever.

Fits beautifully into overall design.

Because of no-overdraw spans, can z-fill world at an adequate speed.

Allows post-processing. At the moment, we're doing particles, scaled NxN colored rectangles, but could do pretty much anything.

Low-tech, high-tech, whatever; the secret's in the mixing and matching until it all fits.


In conclusion:

The more 3-D tricks you know, and the more you experiment, the better.

Yes, I could use a vacation.

Sharing knowledge makes the world a better place.

Further reading:


Author:

Michael Abrash, CGDC talk of April 1996, published as video tape CGDC96-158.


home qdev qdev dread rsc qdev doom license web
home dEr95 r3D dread netrsc quake doom legal web
Author: B., email to bernd@nero.uni-bonn.de, with public PGP key
Copyright (©) 1995, 1996 by author. All rights reserved.
Source: $Id: mikeab-cgdc.html,v 1.2 1996/06/08 20:30:51 b1 Exp $