Why do I think VSD is the toughest 3-D challenge? Although rasterization issues such as texture mapping are fascinating and important, they are tasks of relatively finite scope, and are being moved into hardware as 3-D accelerators appear also, they only scale with increases in screen resolution, which are relatively modest. In the interests of brevity, I’ll use the abbreviation VSD to mean both visible surface determination and culling from now on. I want to talk about what is, in my opinion, the toughest 3-D problem of all: visible surface determination (drawing the proper surface at each pixel), and its close relative, culling (discarding non-visible polygons as quickly as possible, a way of accelerating visible surface determination). Michael Abrash, a programmer who worked with Carmack on Quake (id Software’s follow-up to Doom), wrote about the VSD problem in his famous Graphics Programming Black Book: Advertisement This problem is sometimes called the problem of visible surface determination. This is not especially challenging if you have lots of time, but a respectable real-time game engine needs to figure out what can be seen and what cannot be seen at least 30 times a second. In order to render a three-dimensional scene, a renderer has to figure out, given a particular viewpoint, what can be seen and what cannot be seen. The BSP tree is a solution to one of the thorniest problems in computer graphics. That’s right: E1M1, the first level of Doom, was brought to you by the US Air Force.
It turns out that the BSP tree, rather interestingly, and like so many things in computer science, has its origins in research conducted for the military. So this post is about John Carmack and Doom, but it is also about the history of a data structure: the binary space partitioning tree (or BSP tree). I’ve also wondered where binary space partitioning first came from and how the idea found its way to Carmack. On a spectrum from Homer Simpson to Albert Einstein, how much of a genius-level move was it really for Carmack to add binary space partitioning to Doom? I’ve long assumed that what Carmack did was a clever intellectual leap, but because I’ve never understood what binary space partitioning is or how novel a technique it was when Carmack decided to use it, I’ve never known for sure. Obviously, the story is impressive because “binary space partitioning” sounds like it would be a difficult thing to just read about and implement yourself. He deserves to be known as the archetypal genius video game programmer for all sorts of reasons, but this episode with the academic papers and the binary space partitioning is the justification I think of first.įurther Reading The original Doom, one of 64 Objects that shaped video game history It is my explanation for why Carmack has become such a legendary figure. That story about Carmack applying cutting-edge academic research to video games has always impressed me. He eventually implemented a technique called “binary space partitioning,” never before used in a video game, that dramatically sped up the Doom engine. So Carmack, realizing the problem with his renderer was fundamental enough that he would need to find a better rendering algorithm, starting reading research papers. This was unacceptable, because Doom was supposed to be action-packed and frenetic.
WOLFENSTEIN 3D MAPS E1M1 FULL
This is a loose gloss of the story (see below for the full details), but essentially, early in the development of Doom, Carmack realized that the 3D renderer he had written for the game slowed to a crawl when trying to render certain levels. I read Masters of Doom a few years ago and don’t remember much of it now, but there was one story in the book about lead programmer John Carmack that has stuck with me.
WOLFENSTEIN 3D MAPS E1M1 SOFTWARE
The game is now considered one of the most influential games of all time.Ī decade after Doom’s release, in 2003, journalist David Kushner published a book about id Software called Masters of Doom, which has since become the canonical account of Doom’s creation. In 1993, id Software released the first-person shooter Doom, which quickly became a phenomenon.
0 kommentar(er)
