Element 61

Tuesday, September 20, 2005

Looking at the Quake 3 Source -- Part 3

Alright then, it's finally time to look at Q3's rendering. Everything that's rendered in Quake 3 can be categorized as follows:

Those of you who are familiar with Q3 BSPs will notice I skipped curved surfaces entirely here. I don't even want to go near those things right now.
  • BSP -- Specifically, brush models. These convex hulls form the majority of the static level geometry.
  • Models -- Pretty much anything that's loaded from an MD3 file. These can either come as part of the map or as entities (players, weapon pickups, etc).
  • Other -- This is kind of a cop-out, I know. This would include stuff that's generated at runtime for effects (flares, lightning) and just miscellaneous stuff that isn't either from the BSP map or MD3 files.
Originally I wasn't going to discuss the BSP system at all. But since there was such a huge delay in getting this part of the blog up, I figured it better be good. If you're not familiar with the basic concept of BSP (binary spatial partition), then go read up -- there are a ton of resources on the net (The BSP FAQ is the canonical reference on the subject in amateur circles). Now, it's important to realize that Quake 3 does NOT the BSP tree for visibility determination, which is what BSP was originally meant to do. Instead, the map compiler slices the map up into the BSP tree. Then, for every single leaf, it determines whether or not every other leaf could ever be visible from that leaf. This is called the Potentially Visible Set (PVS). So all of the necessary visibility data is completely precompiled and stored into the map (it's compressed into an RLE bit set). Then, when the engine needs to determine what to render, it has a very simple job. First, it uses the BSP tree to figure out what leaf the view point is in. Then it goes through that bitset, finds every other leaf that could ever possibly be visible from that one, and frustum culls the potentially visible ones to come up with a final set of visible leaves. The resultant set is nearly completely optimal on indoor environments, making newer techniques like occlusion culling unnecessary.

Lighting on the Q3 map is also precalculated, and then baked into light maps. These lightmaps are stored back into the BSP file itself. They're fairly low detail, at 16x16 per poly in the map. Although the Quake 2 lighting engine did radiosity, Quake 3 did not. (The story, I gather, is that Carmack didn't like the bleeding and indirect lighting that radiosity created.) Rendering the lighting is a simple task of drawing another pass which is modulated against the lightmaps. Again, these can be collapsed into a single multitexture pass. Everything that isn't baked into the map, which mainly means all the movable junk, misc models, players, etc, is dynamically lit at runtime. Quake 3 maps have light entities that are used during the precomputation process, but those light entities are also stored back into the final BSP, so that they can be used at runtime.

Lastly, BSPs are used for all of the collisions in Quake. The actual BSP data is constructed entirely from convex hulls. During compilation, overlapping hulls are merged together using constructive solid geometry (CSG). Then, the BSP splits apart everything so that no face spans any of the splits. These properties can all be used for collision detection. I won't go into more detail about that; it is a post about rendering architecture, after all.

Let's move on to Models and Other. Rendering of these things in Q3 is controlled by shader files. These aren't shaders like the GPU programs that we're used to, but rather simply descriptions of how things ought to be rendered. Nowadays they'd probably be referred to as material scripts. Let's look at an example:
textures/base_button/shootme2
{
 qer_editorimage textures/base_button/metal3_3_shootme.tga
 q3map_lightimage textures/base_button/shootme_glow.tga
 q3map_surfacelight 1000
 {
  map $lightmap
  rgbGen identity
 }
 {
  map textures/base_support/metal3_3.tga
  blendFunc GL_DST_COLOR GL_ZERO
  rgbGen identity
 }
 {
  map textures/base_button/shootme_glow.tga
  rgbGen wave sin 0.5 1.0 0 .3
  blendFunc GL_ONE GL_ONE
 }
}
So this is a shader for some kind of glowing button thing. We can see it has 3 layers. The first one is the lightmap (this would actually be applied to a brush in the map). The second is a base texture that isn't blended against anything. The third is an additive blend that comes from a base texture. It's also modified by a sine wave, which will have the end result of giving it a pulsating glow. I'm not going to go into great depth about everything a shader can have, because we'll be here all day if I do. However, I did happen to find a great manual. Shaders are dealt with in code/renderer/tr_shader.c. All of the parser code is here, and don't expect any clever stuff in there -- the parser code is about as brute force as it gets. There are also a ton of misc. operations to work with and manage shaders, but most of them are not particularly interesting. You'll notice that each and every texture layer is specified seperately. Q3 assumes that any effect can be done with a single texture per pass and alpha blending. (And this was quite true until the advent of pixel shaders.) The engine does detect certain blending modes as collapsible into a single multitextured pass, and will attempt to do so. It's hard coded to only ever use two textures per multitexture pass though, so hardware with more texture units doesn't benefit.

I think it's time to take a brief look at the model rendering in Q3. Q3 models are keyframe animated, just like Q2. The difference, though, is that the models can be sliced into multiple parts and then controlled seperately. Each player has 3 models associated with it: head, torso, and legs. These are attached by "tags" embedded in the model. Each tag is a single triangle which is used to correct orient the attached models in the correct pose. By rotating the tag of the torso to the head, you can make the player turn his head without having to do anything else. So the legs, torso, and head all have their own animations, and they're combined at runtime. It isn't dynamic blending of multiple skeletal animations (arguably the holy grail today), but it's pretty damn clever nonetheless.

That more or less covers the external behavior of the rendering subsystem. Most (all?) of this information has been public for years, but it's necessary to make sure we're on the same page before digging into the code, otherwise we'll lose people along the way, and that's never good. It sounds very simple, and externally it is. But there's a lot of code backing this stuff, particularly in processing shaders. There's stuff for processing mirrors and portals, which carry their own complications. Additionally, there's a complete command queueing backend to sort and render things in optimal order. The things in the Other category that I mentioned are usually dynamically generated geometry, and there's plenty of code for that. The list goes on and on. It's not a simple engine internally.

I hope that helps everybody. Sorry about the huge delay in writing this part. As I said earlier, I needed to get copies of both Q3 and Visual Studio. Also, there were some major technical problems that have left my main system a corpse until a few RMAs come back. Not to mention school started again, and that carries a whole load of stuff with it. Anyway, if you have any questions, please post in the comments and I promise I will answer them. The BSP section seemed a little brief, since I only covered rendering and not compilation; the latter is where the real complexity lies (and I don't quite understand it besides). The shaders are for the most part self explanatory.

5 Comments:

  • Sweet.

    Network! Network! Network! :)

    By Anonymous Anonymous, at 9/20/2005 1:36 PM  

  • MOOOOORE!!! I want MORE!

    - BradDaBug

    By Anonymous Anonymous, at 11/09/2005 4:23 PM  

  • PART 4 PLEASE:)

    By Anonymous Anonymous, at 1/26/2006 3:32 AM  

  • Good job! hope to read more about the Quake 3 Rendering Engine. There's not too many good articles on Engine design in general.

    By Anonymous Anonymous, at 4/13/2006 10:12 AM  

  • For networking model overview (with pseudocode snips) have a look at the book of hook: http://trac.bookofhook.com/bookofhook/trac.cgi/wiki/Quake3Networking

    By Blogger Robbb, at 5/05/2008 12:29 PM  

Post a Comment

<< Home