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.

Fun thing #1: hardware is fast enough to do interesting things, but not fast enough to do what we really want.
Fun thing #2: a ton of techniques and approaches, all of which are good for something, none of which are good for everything.

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:

Quake:
- True, arbitrary 6 DOF 3-D.
- Highest possible graphics quality, both lighting and rasterizing.
- True 3-D for players, monsters, and as many objects as possible.
Any 3-D engine:
- Correct color at each pixel.
- Adequate, reasonably level framerate.

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.

Principle #1:
we need to reduce the polygon set quickly to only those that matter, or at least those that have a pretty good chance of mattering.
Principle #2:
we need to get the right colors on the right pixels for those polygons we do draw; this means perspective correction, z-ordering, shading, subpixel and subtexel placement, and so on.

#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:

Static world.
Everything else (moving objects, including players, monsters, doors, platforms, health, ammo, armor, and so on).

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:

Nodes are splitting planes, with polygons stored on them, that carve up space.
Leaves are the convex volumes that nodes carve the world into.
A BSP tree can be walked front-to-back or back-to-front in linear time for any viewpoint.
A BSP tree performs a convex, hierarchical partitioning of space, with each node defining a subspace that contains all of the node's children.
Hierarchical partitioning helps greatly in large-scale culling. Node bounding boxes can be clipped to the view pyramid.
If a node's bounding box is trivially rejected, all its children can be rejected with no further testing.
If a node is trivially accepted, all its children can be accepted with no further testing.

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:

Z-buffering
Painters algorithm
Beam tree
Subdividing raycasting
Edge or span sorting
Portals
Direct visibility extraction from BSP

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.

Virtually free at runtime.
Very expensive to precalculate - but that's what preprocessing is for.
Speeds up culling to the view pyramid and determination of moving objects that have to be drawn, because only nodes and leaves in the PVS matter.

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:

Shared edges
Concave polygons
Culling of polygons for 3-D hw

What key to sort on?

BSP order.
1/z.

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

Rasterization!

Disadvantages of normal Gouraud shaded texture mapping:

Rotational lighting variance if triangles aren't used.
Lighting detail is added by adding more polygons.
Lighting is not perspective correct.

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:

No rotational variance.
Perspective correct lighting.
Fewer polgyons.
Lighting separated from polygons.
Ability to post-process.

Disadvantages:

More memory.
More cache misses.
Slow for constantly changing lighting (fine for switching lighting on/off).
Slowdown when turning corners.
Not a perfect fit for hardware.

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.