|Previous||Table of Contents||Next|
Okay, I admit it: Im sick and tired of classic rock. Admittedly, its been a while, about 20 years, since I was last excited to hear anything by the Cars or Boston, and I was never particularly excited in the first place about Bob Seger or Queen, to say nothing of Elvis, so some things havent changed. But I knew something was up when I found myself changing the station on the Allman Brothers and Steely Dan and Pink Floyd and, God help me, the Beatles (just stuff like Hello Goodbye and Ill Cry Instead, though, not Ticket to Ride or A Day in the Life; Im not that far gone). It didnt take long to figure out what the problem was; Id been hearing the same songs for a quarter-century, and I was bored.
I tell you this by way of explaining why it was that when my daughter and I drove back from dinner the other night, the radio in my car was tuned, for the first time ever, to a station whose slogan is There is no alternative.
Now, were talking here about a 10-year-old who worships the Beatles and has been raised on a steady diet of oldies. She loves melodies, catchy songs, and good singers, none of which youre likely to find on an alternative rock station. So its no surprise that when I turned on the radio, the first word out of her mouth was Yuck!
What did surprise me was that after listening for a while, she said, You know, Dad, its actually kind of interesting.
Apart from giving me a clue as to what sort of music I can expect to hear blasting through our house when shes a teenager, her quick uptake on alternative rock (versus my decades-long devotion to the music of my youth) reminded me of something that its easy to forget as we become older and more set in our ways. It reminded me that its essential to keep an open mind, and to be willing, better yet, eager, to try new things. Programmers tend to become attached to familiar approaches, and are inclined to stick with whatever is currently doing the job adequately well, but in programming there are always alternatives, and Ive found that theyre often worth considering.
Not that I should have needed any reminding, considering the ever-evolving nature of Quake.
Back in Chapter 64, I described the creative flux that led to John Carmacks decision to use a precalculated potentially visible set (PVS) of polygons for each possible viewpoint in Quake, the game were developing here at id Software. The precalculated PVS meant that instead of having to spend a lot of time searching through the world database to find out which polygons were visible from the current viewpoint, we could simply draw all the polygons in the PVS from back-to-front (getting the ordering courtesy of the world BSP tree) and get the correct scene drawn with no searching at all; letting the back-to-front drawing perform the final stage of hidden-surface removal (HSR). This was a terrific idea, but it was far from the end of the road for Quakes design.
For one thing, there was still the question of how to sort and draw moving objects properly; in fact, this is the single technical question Ive been asked most often in recent months, so Ill take a moment to address it here. The primary problem is that a moving model can span multiple BSP leaves, with the leaves that are touched varying as the model moves; that, together with the possibility of multiple models in one leaf, means theres no easy way to use BSP order to draw the models in correctly sorted order. When I wrote Chapter 64, we were drawing sprites (such as explosions), moveable BSP models (such as doors), and polygon models (such as monsters) by clipping each into all the leaves it touched, then drawing the appropriate parts as each BSP leaf was reached in back-to-front traversal. However, this didnt solve the issue of sorting multiple moving models in a single leaf against each other, and also left some ugly sorting problems with complex polygon models.
John solved the sorting issue for sprites and polygon models in a startlingly low-tech way: We now z-buffer them. (That is, before we draw each pixel, we compare its distance, or z, value with the z value of the pixel currently on the screen, drawing only if the new pixel is nearer than the current one.) First, we draw the basic world, walls, ceilings, and the like. No z-buffer testing is involved at this point (the world visible surface determination is done in a different way, as well see soon); however, we do fill the z-buffer with the z values (actually, 1/z values, as discussed below) for all the world pixels. Z-filling is a much faster process than z-buffering the entire world would be, because no reads or compares are involved, just writes of z values. Once the drawing and z-filling of the world is done, we can simply draw the sprites and polygon models with z-buffering and get perfect sorting all around.
Whenever a z-buffer is involved, the questions inevitably are: Whats the memory footprint and whats the performance impact? Well, the memory footprint at 320×200 is 128K, not trivial but not a big deal for a game that requires 8 MB to run. The performance impact is about 10 percent for z-filling the world, and roughly 20 percent (with lots of variation) for drawing sprites and polygon models. In return, we get a perfectly sorted world, and also the ability to do additional effects, such as particle explosions and smoke, because the z-buffer lets us flawlessly sort such effects into the world. All in all, the use of the z-buffer vastly improved the visual quality and flexibility of the Quake engine, and also simplified the code quite a bit, at an acceptable memory and performance cost.
As I said above, in the Quake architecture, the world itself is drawn first, without z-buffer reads or compares, but filling the z-buffer with the world polygons z values, and then the moving objects are drawn atop the world, using full z-buffering. Thus far, Ive discussed how to draw moving objects. For the rest of this chapter, Im going to talk about the other part of the drawing equation; that is, how to draw the world itself, where the entire world is stored as a single BSP tree and never moves.
|Previous||Table of Contents||Next|