|Previous||Table of Contents||Next|
As long-time readers of my columns know, I tend to move my family around the country quite a bit. Change doesnt come out of the blue, so theres some interesting history to every move, but the roots of the latest move go back even farther than usual. To wit:
In 1986, just after we moved from Pennsylvania to California, I started writing a column for Programmers Journal. I was paid peanuts for writing it, and I doubt if even 5,000 people saw some of the first issues the columns appeared in, but I had a lot of fun exploring fast graphics for the EGA and VGA.
By 1991, we were in Vermont, and I was writing the Graphics Programming column for Dr. Dobbs Journal (and having a great time doing it, even though it took all my spare nights and weekends to stay ahead of the deadlines). In those days I received a lot of unsolicited evaluation software, including a PC shareware game called Commander Keen, a side-scrolling game that was every bit as good as the hot Nintendo games of the day. I loved the way the game looked, and actually drafted a column opening about how for years Id been claiming that the PC could be a great game machine in the hands of great programmers, and here, finally, was the proof, in the form of Commander Keen. In the end, though, I decided that would be too close to a product review, an area that Ive observed inflames passions in nonconstructive ways, so I went with a different opening.
In 1992, I did a series of columns about my X-Sharp 3-D library, and hung out on DDJs bulletin board. There was another guy who hung out there who knew a lot about 3-D, a fellow named John Carmack who was surely the only game programmer Id ever heard of who developed under NEXTSTEP. When we moved to Redmond, I didnt have time for BBSs anymore, though.
In early 1993, I hired Chris Hecker. Later that year, Chris showed me an alpha copy of DOOM, and I nearly fell out of my chair. About a year later, Chris forwarded me a newsgroup post about NEXTSTEP, and said, Isnt this the guy you used to know on the DDJ bulletin board? Indeed it was John Carmack; whats more, it turned out that John was the guy who had written DOOM. I sent him a congratulatory piece of mail, and he sent back some thoughts about what he was working on, and somewhere in there I asked if he ever came up my way. It turned out he had family in Seattle, so he stopped in and visited, and we had a great time.
Over the next year, we exchanged some fascinating mail, and I became steadily more impressed with Johns company, id Software. Eventually, John asked if Id be interested in joining id, and after a good bit of consideration I couldnt think of anything else that would be as much fun or teach me as much. The upshot is that here we all are in Dallas, our fourth move of 2,000 miles or more since Ive starting writing in the computer field, and now Im writing some seriously cool 3-D software.
Now that Im here, its an eye-opener to look back and see how events fit together over the last decade. You see, when John started doing PC game programming he learned fast graphics programming from those early Programmers Journal articles of mine. The copy of Commander Keen that validated my faith in the PC as a game machine was the fruit of those articles, for that was an id game (although I didnt know that then). When John was hanging out on the DDJ BBS, he had just done Castle Wolfenstein 3-D, the first great indoor 3-D game, and was thinking about how to do DOOM. (If only Id known that then!) And had I not hired Chris, or had he not somehow remembered me talking about that guy who used NEXTSTEP, Id never have gotten back in touch with John, and things would surely be different. (At the very least, I wouldnt be hearing jokes about how my daughters going to grow up saying yall.)
I think theres a worthwhile lesson to be learned from all this, a lesson that Ive seen hold true for many other people, as well. If you do what you love, and do it as well as you can, good things will eventually come of it. Not necessarily quickly or easily, but if you stick with it, they will come. There are threads that run through our lives, and by the time weve been adults for a while, practically everything that happens has roots that run far back in time. The implication should be clear: If you want good things to happen in your future, stretch yourself and put in the extra effort now at whatever you care passionately about, so those roots will have plenty to work with down the road.
All this is surprisingly closely related to this chapters topic, BSP trees, because John is the fellow who brought BSP trees into the spotlight by building DOOM around them. He also got me started with BSP trees by explaining how DOOM worked and getting me interested enough to want to experiment; the BSP compiler in this article is the direct result. Finally, John has been an invaluable help to me as Ive learned about BSP trees, as will become evident when we discuss BSP optimization.
Onward to compiling BSP trees.
As youll recall from the previous chapter, a BSP tree is nothing more than a series of binary subdivisions that partion space into ever-smaller pieces. Thats a simple data structure, and a BSP compiler is a correspondingly simple tool. First, it groups all the surfaces (lines in 2-D, or polygons in 3-D) together into a single subspace that encompasses the entire world of the database. Then, it chooses one of the surfaces as the root node, and uses its line or plane to divide the remaining surfaces into two subspaces, splitting surfaces into two parts if they cross the line or plane of the root. Each of the two resultant subspaces is then processed in the same fashion, and so on, recursively, until the point is reached where all surfaces have been assigned to nodes, and each leaf surface subdivides a subspace that is empty except for that surface. Put another way, the root node carves space into two parts, and the roots children carve each of those parts into two more parts, and so on, with each surface carving ever smaller subspaces, until all surfaces have been used. (Actually, there are many other lines or planes that a BSP tree can use to carve up space, but this is the approach well use in the current discussion.)
|Previous||Table of Contents||Next|