|Previous||Table of Contents||Next|
Why did not any of the children in the first group think of this faster method of going across the room? It is simple. They looked at what they were given to use for materials and, they are like all of us, they wanted to use everything. But they did not need everything. They could do better with less, in a different way.
Frederik Pohl, The Gold at the Starbows End
Eleven years ago, I started the first serious graphics article I ever wrote with the above quote. The point I was making at the time was that programming assumptions based on high-level languages or other processors had to be discarded in the quest for maximum x86 performance. While thats certainly still true, time and the microcomputer world have moved on, and today theres a more important lesson 3-D game programmers can draw from Frederik Pohls words. Nowadays, CPUs, 3-D hardware, 3-D algorithms, and 3-D data structures are evolving so rapidly that the enemy is now often the assumptions and techniques from the last productand sometimes the assumptions and techniques in the current product. We all feel most comfortable with techniques weve already mastered, but leading-edge 3-D game technology is such a delicate balancing act between performance, features (particularly with game designers always wanting to add more), and workflow (as well see, preprocessing that improves performance often hurts designer productivity) that its never safe to stop looking for a better approach until the game has actually shipped. Change is the rule, and we must always be looking to do better with less, in a different way.
Ive talked about Quakes technology elsewhere in this book, However, those chapters focused on specific areas, not overall structure. Moreover, Quake changed in significant ways between the writing of those chapters and the final shipping. Then, after shipping, Quake was ported to 3-D hardware. And the post-Quake engine, code-named Trinity, is already in development at this writing (Spring 1997), with some promising results. So in wrapping up this book, Ill recap Quakes overall structure relatively quickly, then bring you up to date on the latest developments. And in the spirit of Frederik Pohls quote, Ill point out that we implemented and discarded at least half a dozen 3-D engines in the course of developing Quake (and all of Quakes code was written from scratch, rather than using Doom code), and almost switched to another one in the final month, as Ill describe later. And even at this early stage, Trinity uses almost no Quake technology.
In fact, Ill take this opportunity to coin Carmacks Law, as follows: Fight code entropy. If you have a new fundamental assumption, throw away your old code and rewrite it from scratch. Incremental patching and modifying seems easier at first, and is the normal course of things in software development, but ends up being much harder and producing bulkier, markedly inferior code in the long run, as well see when we discuss the net code for QuakeWorld. It may seem safer to modify working code, but the nastiest bugs arise from unexpected side effects and incorrect assumptions, which almost always arise in patched-over code, not in code designed from the ground up. Do the hard work up front to make your code simple, elegant, greatand just plain rightand itll pay off many times over in the long run.
Before I begin, Id like to remind you that all of the Doom and Quake material Im presenting in this book is presented in the spirit of sharing information to make our corner of the world a better place for everyone. Id like to thank John Carmack, Quakes architect and lead programmer, and id Software for allowing me to share this technology with you, and I encourage you to share your own insights by posting on the Internet and writing books and articles whenever you have the opportunity and the right to do so. (Of course, check with your employer first!) Weve all benefited greatly from the shared wisdom of people like Knuth, Foley and van Dam, Jim Blinn, Jim Kajiya, and hundreds of othersare you ready to take a shot at making your own contribution to the future?
For the most part, Ill discuss Quakes 3-D engine in this chapter, although Ill touch on other areas of interest. For 3-D rendering purposes, Quake consists of two basic sorts of objects: the world, which is stored as a single BSP model and never changes shape or position; and potentially moving objects, called entities, which are drawn in several different ways. Ill discuss each separately.
The world is constructed from a set of brushes, which are n-sided convex polyhedra placed in a level by a designer using a map editor, with a selectable texture on each face. When a level is completed, a preprocessing program combines all brushes to form a skin around the solid areas of the world, so there is no interpenetration of polygons, just a continuous mesh delineating solid and empty areas. Once this is done, the next step is generating a BSP tree for the level.
The BSP consists of splitting planes aligned with polygons, called nodes, and of leaves, which are the convex subspaces into which all the nodes carve space. The top node carves the world into two subspaces, and divides the remaining polygons into two sets, splitting any polygon that spans the node into two pieces. Each subspace is then similarly split by one node each, and so on until all polygons have been used to create nodes. A nodes subspace is the total space occupied by all its children: the subspace that the node splits into two parts, and that its children continue to subdivide. When the only polygon in a nodes subspace is the polygon that splits the subspacethe polygon whose plane defines the nodethen the two child subspaces are called leaves, and are not divided any further.
The BSP tree is built using the polygon that splits the fewest of the polygons in the current nodes subspace as the heuristic for choosing splitters, which is not an optimal solutionbut an optimal solution is NP-complete, and our heuristic adds only 10% to 15% more polygons to the level as a result of BSP splits. Polygons are not split all the way into leaves; rather, they are placed on the nodes with which they are coplanar (one set on the front and one on the back, which has the advantage of letting us reuse the BSP-walking dot product for backface culling as well), thereby reducing splitting considerably, because polygons are split only by parent nodes, not by child nodes (as would be necessary if polygons were split into leaves). Eliminating polygon splits, thus reducing the total number of polygons per level, not only shrinks Quakes memory footprint, but also reduces the number of polygons that need to be processed by the 3-D pipeline, producing a speedup of about 10% in Quakes overall performance.
|Previous||Table of Contents||Next|