Michael Abrash is the author of Zen of Graphics Programming and Zen of Code Optimization. He is currently pushing the envelope of real-time 3-D on Quake at id Software. He can be reached at mikeab@idsoftware.com.
The answer is: Wendy Tucker. The question that goes with that answer isn't particularly interesting to anyone but me--but the manner in which I came up with the answer might be.
I spent many of my childhood summers at Camp Chingacook, on Lake George in New York. It was a great place to have fun and do some growing up, with swimming and sailing and hiking and lots more.
When I was 14, Camp Chingacook had a mixer with a nearby girl's camp. As best I can recall, I had never had any interest in girls before, but after the older kids had paired up, I noticed a pretty girl looking at me, and, with considerable trepidation, crossed the room to talk to her. To my amazement, we hit it off terrifically. We talked nonstop for the rest of the evening, and I walked back to my cabin floating on air. I had taken a first, tentative step into adulthood, and my world would never be quite the same.
That was the only time I ever saw her, although I would occasionally remember that warm glow and call up an image of her smiling face. That happened less frequently as the years passed and I had real girlfriends. By the time I got married, that particular memory was stashed in some back storeroom of my mind. I didn't think of her again for more than a decade.
A few days ago, for some reason, that mixer popped into my mind as I was trying to fall asleep, and I wondered, for the first time in 20 years, what that girl's name was. The name was there in my mind, somewhere; I could feel the shape of it, in that same back storeroom, if only I could figure out how to retrieve it.
I poked and worried at that memory, trying to get it to come to the surface. I concentrated on it as hard as I could and even started going through the alphabet one letter at a time, trying to remember if her name started with each letter. After 15 minutes, I was wide awake and totally frustrated. I was also farther than ever from answering the question; all the focusing on the memory was beginning to blur the original imprint.
At this point, I consciously relaxed and made myself think about something completely different. Every time my mind returned to the mystery girl, I gently shifted it to something else. After a while, I began to drift off to sleep, and as I did, a connection was made, and a name popped, unbidden, into my mind.
Wendy Tucker.
There are many problems that are amenable to the straight-ahead, purely conscious sort of approach that I first tried to use to retrieve Wendy's name. Writing code (once it's designed) is often like that, as are some sorts of debugging, and technical writing, and balancing your checkbook. I find these left-brain activities very appealing because they're finite and controllable; when I start one, I know I'll be able to deal with whatever comes up and make good progress, just by plowing along. Inspiration and intuitive leaps are sometimes useful, but not required.
The problem is, though, that neither you nor I will ever do anything great without inspiration and intuitive leaps, and especially not without stepping away from what's known and venturing into territories beyond. The way to do that is not by trying harder but, paradoxically, by trying less hard, stepping back and giving your right brain room to work, then listening for and nurturing whatever comes of that. On a small scale, that's how I remembered Wendy's name, and on a larger scale, that's how programmers come up with products that are more than me-too, checklist-oriented software.
Which, for a couple of reasons, brings us neatly to today's topic, binary space partitioning (BSP) trees. First, games are probably the sort of software in which the right-brain element is most important--blockbuster games are almost always breakthroughs in one way or another--and some very successful games use BSP trees, most notably the megahit DOOM. Second, BSP trees aren't intuitively easy to grasp, and considerable ingenuity and inventiveness is required to get the most from them.
First, I'd like to thank John Carmack, technical wizard of DOOM, for generously sharing his knowledge of BSP trees.
A BSP tree is, at heart, nothing more than a tree that subdivides space in order to isolate features of interest. Each node of a BSP tree splits an area or a volume (in two dimensions or three dimensions, respectively) into two parts along a line or a plane; thus the name "binary space partitioning." The subdivision is hierarchical; the root node splits the world into two subspaces, then each of the root's two children splits one of those two subspaces into two more parts. This continues, with each subspace being further subdivided, until each component of interest (each line segment or polygon, for example) has been assigned its own unique subspace. This is, admittedly, a pretty abstract description, but the workings of BSP trees will become clearer shortly; it may help to glance ahead to Figures 2 through 6.
Building a tree that subdivides space doesn't sound particularly profound, but there's a lot that can be done with such a structure. BSP trees can be used to represent shapes, and operating on those shapes is a simple matter of combining trees as needed; this makes BSP trees a powerful way to implement constructive solid geometry (CSG). BSP trees can also be used for hit testing, line-of-sight determination, and collision detection.
I'm going to discuss only one of the many uses of BSP trees: their ability to allow you to traverse a set of line segments or polygons in back-to-front or front-to-back order as seen from any arbitrary viewpoint. This sort of traversal can be very helpful in determining which parts of each line segment or polygon are visible and which are occluded from the current viewpoint in a 3-D scene. Thus, a BSP tree makes possible an efficient implementation of the painter's algorithm, whereby polygons are drawn in back-to-front order, with closer polygons overwriting more distant ones that overlap, as shown in Figures 1(b--d). (The line segments in Figure 1(a) represent vertical walls viewed directly from above.) Alternatively, visibility determination can be performed by front-to-back traversal working in conjunction with some method for remembering which pixels have already been drawn. The latter approach is more complex, but has the potential benefit of allowing you to early-out from traversal of the scene database when all the pixels on the screen have been drawn.
Back-to-front or front-to-back traversal in itself wouldn't be so impressive--there are many ways to do that--were it not for one additional detail: The traversal can always be performed in linear time, as we'll see later on. In other words, you can traverse, say, a polygon list back-to-front from any viewpoint simply by walking through the corresponding BSP tree once, visiting each node once and only once, and performing only one relatively inexpensive test at each node.
It's hard to get cheaper sorting than linear, and BSP-based rendering stacks up well against alternatives such as z-buffering, octrees, z-scan sorting, and polygon sorting. Better yet, a scene database represented as a BSP tree can be clipped to the view pyramid very efficiently; huge chunks of a BSP tree can be lopped off when clipping to the view pyramid, because if a splitting line or plane lies entirely outside the view volume, then all surfaces on one or the other side of the splitting surface must likewise be outside the view volume, for reasons that will become clear as we delve into the workings of BSP trees.
Powerful as they are, BSP trees aren't perfect. By far the greatest limitation of BSP trees is that they're time-consuming to build, enough so that, for all practical purposes, BSP trees must be precalculated and cannot be built dynamically at run time. In fact, a BSP-tree compiler that attempts to perform some optimization (limiting the number of surfaces that need to be split, for example) can easily take minutes or even hours to process large world databases.
A fixed world database is fine for walkthrough or flythrough applications, but not much use for games or virtual reality, where objects constantly move relative to one another. Consequently, various workarounds have been developed to allow moving objects to appear in BSP tree-based scenes. DOOM, for example, uses 2-D sprites mixed into BSP-based, 3-D scenes; note, though, that this approach requires maintaining z information so that sprites can be drawn and occluded properly. Alternatively, movable objects could be represented as separate BSP trees and merged into the BSPtree describing the static world anew with each move. Dynamic merging may or may not be fast enough, depending on the scene, but merging BSP trees tends to be quicker than building them, because the BSP trees being merged are already spatially sorted.
Another possibility would be to generate a per-pixel z-buffer for each frame as it's rendered, to allow dynamically changing objects to be drawn into the BSP-based world. In this scheme, the BSP tree would allow fast traversal and clipping of the complex, static world, and the z-buffer would handle the relatively localized visibility determination involving moving objects. The drawback of this is the need for a memory-hungry z-buffer; a typical 640x480 z-buffer requires a fairly appalling 600K, with equally appalling cache-miss implications for performance.
Yet another possibility would be to build the world so that each dynamic object falls entirely within a single subspace of the static BSP tree, rather than straddling splitting lines or planes. In this case, dynamic objects can be treated as points, which are then just sorted into the BSP tree on the fly as they move.
The only other drawbacks of BSP trees that I know of are the memory required to store the tree, which amounts to a few pointers per node, and the relative complexity of debugging BSP-tree compilation and usage; debugging a large data set being processed by recursive code (which BSP code tends to be) can be quite a challenge. Visual tools which, like the BSP compiler that I'll present next time, depict the process of spatial subdivision as a BSP tree is constructed can help a great deal with BSP debugging.
Now that we know a good bit about what a BSP tree is, how it helps in visible surface determination, and what its strengths and weaknesses are, let's take a look at how a BSP tree actually works to provide front-to-back or back-to-front ordering. This month's discussion will be at a conceptual level, with plenty of figures; next time we'll get into mechanisms and implementation details.
I'm going to discuss only 2-D BSP trees from here on out, because they're much easier to draw and to grasp than their 3-D counterparts. Don't worry, though; the principles of 2-D BSP trees using line segments generalize directly to 3-D BSP trees using polygons. Also, 2-D BSP trees are quite powerful in their own right, as evidenced by DOOM, which is built around 2-D BSP trees.
First, let's construct a simple BSP tree. Figure 2 shows a set of four lines that will constitute our sample world. I'll refer to these as walls viewed from directly above, because that's an easily visualized context in which 2-D BSP trees would be useful in a game. Note that each wall has a front side, denoted by a normal (perpendicular) vector, and a back side. To make a BSP tree for this sample set, we need to split the world in two, then each part into two again, and so on, until each wall resides in its own unique subspace. An obvious question, then, is how we should carve up the world of Figure 2.
There are many valid ways to carve up Figure 2, but the simplest is just to carve along the lines of the walls themselves, with each node containing one wall. This is not necessarily optimal in the sense of producing the smallest tree, but it has the virtue of generating the splitting lines without expensive analysis. It also saves on data storage, because the data for the walls can do double duty in describing the splitting lines as well. (Putting one wall on each splitting line doesn't actually create a unique subspace for each wall, but it does create a unique subspace boundary for each wall; as we'll see, this spatial organization provides for the same unambiguous visibility ordering as unique subspaces would.)
Creating a BSP tree is a recursive process, so we'll perform the first split and go from there. Figure 3 shows the world carved along the line of wall C, into two parts: walls that are in front of wall C, and walls that are behind. (Any of the walls would have been an equally valid choice for the initial split; we'll return to the issue of choosing splitting walls next time.) This splitting into front and back is the essential dualism of BSP trees. Next, in Figure 4, the front subspace of wall C is split by wall D. This is the only wall in that subspace, so we're done with wall C's front subspace.
Figure 5 shows the back subspace of wall C being split by wall B. There's a difference here, though: Wall A straddles the splitting line generated from wall B. Does wall A belong in the front or back subspace of wall B?
Both, actually. Wall A gets split into two pieces, which I'll call wall A and wall E; each piece is assigned to the appropriate subspace and treated as a separate wall. As shown in Figure 6, each of the split pieces then has a subspace to itself, and each becomes a leaf of the tree. The BSP tree is now complete.
Now that we've successfully built a BSP tree, you might justifiably be a little puzzled as to how any of this helps with visibility ordering. The answer is that each BSP node can definitively determine which of its child trees is nearer and which is farther from any and all viewpoints; applied throughout the tree, this principle makes it possible to establish visibility ordering for all the line segments or planes in a BSP tree, no matter what the viewing angle.
Consider the world of Figure 2 viewed from an arbitrary angle, as in Figure 7. The viewpoint is in front of wall C; this tells us that all walls belonging to the front tree that descends from wall C are nearer along every ray from the viewpoint than wall C is (that is, they can't be occluded by wall C). All the walls in wall C's back tree are likewise farther away than wall C along any ray. Thus, for this viewpoint, we know for sure that if we're using the painter's algorithm, we want to draw all the walls in the back tree first, then wall C, and then the walls in the front tree. If the viewpoint had been on the back side of wall C, this order would have been reversed.
Of course, we need more ordering information than wall C alone can give us, but we get that by traversing the tree recursively, making the same far/near decision at each node. Figure 8 shows the painter's algorithm (back-to-front) traversal order of the tree for the viewpoint of Figure 7. At each node, we decide whether we're seeing the front or back side of that node's wall, then visit whichever of the wall's children is on the far side from the viewpoint, draw the wall, and visit the node's nearer child, in that order. Visiting a child is recursive, involving the same far-near visiting order.
The key is that each BSP splitting line separates all the walls in the current subspace into two groups relative to the viewpoint, and every single member of the farther group is guaranteed not to occlude every single member of the nearer. By applying this ordering recursively, the BSP tree can be traversed to provide back-to-front or front-to-back ordering, with each node being visited only once.
The type of tree walk used to produce front-to-back or back-to-front BSP traversal is known as "inorder." (See my article, "Good Causes, Good Code," PC Techniques, October 1994, or any book on data structures for a discussion of inorder walking.) The only special aspect of BSP walks is that a decision has to be made at each node about which way the node's wall is facing relative to the viewpoint, so we know which child tree is nearer and which is farther.
Example 1 shows a function that draws a BSP tree back-to-front. The decision whether a node's wall is facing forward, made by WallFacingForward() in Listing One, can, in general, be made by generating a normal to the node's wall in screenspace (perspective-corrected space as seen from the viewpoint) and checking whether the z component of the normal is positive or negative, or by checking the sign of the dot product of a viewspace (nonperspective-corrected space as seen from the viewpoint) normal and a ray from the viewpoint to the wall. In 2-D, the decision can be made by enforcing the convention that when a wall is viewed from the front, the start vertex is leftmost; then a simple screenspace comparison of the x-coordinates of the left and right vertices indicates which way the wall is facing.
Finally, be aware that BSP trees can often be made smaller and more efficient by detecting collinear surfaces (like aligned wall segments) and generating only one BSP node for each collinear set, with the collinear surfaces stored in, say, a linked list attached to that node. Collinear surfaces partition space identically and can't occlude one another, so it suffices to generate one splitting node for each collinear set.
Next time, I'll build a BSP-tree compiler, then put together a rendering system built around the BSP trees the compiler generates. In the meantime, there's a World Wide Web page on BSP trees under construction at http://www.graphics.cornell.edu/bspfaq; as I write this, the page contains little more than an outline of things to come, but if the contents live up to the promise of the outline, it could be worth checking out by the time you read this.
Short on space though I am, I'd be remiss if I didn't point out one of the most valuable articles you're likely to come across this year. Chris Hecker's column in the April 1995 issue of Game Developer magazine is by far the best discussion of perspective texture mapping I've seen. Check it out; you won't be sorry.
Foley, J., A. van Dam, S. Feiner, and J. Hughes. Computer Graphics: Principles and Practice, Second Edition. Reading, MA: Addison-Wesley, 1990.
Fuchs, H., Z. Kedem, and B. Naylor. "On Visible Surface Generation by A Priori Tree Structures." Computer Graphics (June 1980).
Gordon, D. and S. Chen. "Front-to-Back Display of BSP Trees." IEEE Computer Graphics and Applications (September 1991).
Naylor, B. "Binary Space Partitioning Trees as an Alternative Representation of Polytopes." Computer Aided Design (May 1990).
void WalkBSPTree(NODE *pNode)
{
if (WallFacingForward(pNode) {
if (pNode->BackChild) {
WalkBSPTree(pNode->BackChild);
}
Draw(pNode);
if (pNode->FrontChild) {
WalkBSPTree(pNode->FrontChild);
}
} else {
if (pNode->FrontChild) {
WalkBSPTree(pNode->FrontChild);
}
Draw(pNode);
if (pNode->BackChild) {
WalkBSPTree(pNode->BackChild);
}
}
}
Copyright © 1995, Dr. Dobb's Journal