Doom 1 and 2 Raycasting
Author
http://student.kuleuven.be/~m0216922/CG/raycasting.html#Untextured_Raycaster_ btw best tutorial in the world if you want to learn raycasting. I was wondering if anyone knew of a similar tutorial but for Doom 1 and 2 style games where there sized walls, based on a Z-Axis.
It's a very common misconception that Doom used a raycasting system. It didn't. It used a system called Binary Space Partitioning (BSP). It used a simple 2D implementation of the algorithm (Quake used a 3D version together with a system called Potentially Visible Sets or PVS). I don't have exact details to hand but I'm sure googling for "Binary Space Partitioning" or "BSP" would yield some useful information. Interestingly, the method used in the original Doom games was not the most efficent way of doing it. The walls were drawn back to front resulting in overdraw (where you draw to the same pixel twice). It is possible, though a bit more complex, to create a front to back rendering system that eliminates overdraw. I don't know if Doom did this, but the version I came up with used self-generating code to do the texture scaling for the walls and sprited.
Skizz
Skizz
Quote:Original post by eviltwigflipper
http://student.kuleuven.be/~m0216922/CG/raycasting.html#Untextured_Raycaster_ btw best tutorial in the world if you want to learn raycasting. I was wondering if anyone knew of a similar tutorial but for Doom 1 and 2 style games where there sized walls, based on a Z-Axis.
The tutorial contains a small mistake, a raycaster described there is the special case of a backprojecting raytracer with a single iteration and without lighting.
The doom engine uses geometry based rendering and only employs tricks so walls are always vertical and floors are horizontal. Using vertical only walls and two infinite sized surfaces (floor and ceiling), means the vertex transformations don't need a full matrix (2x2 instead of the full 4x4). The result of this simplification is that the player can't look around freely.
You can find more here:
http://everything2.com/index.pl?node_id=1494609
AFAIK the reason why Doom1 drew back to front was because it used a software rasterizer, and they couldn't afford the overhead of a Z-test for every polygon in the scene. So instead, they simply drew back to front (painter's algorithm). In fact, I'm not even sure that the original Doom did any Z-buffering at all (though quake certainly did)
JB
JB
No, you don't need a Z test to draw the walls front to back, merely vertical span information. A Z buffer was used for rendering the sprites, the contents of the buffer created when the walls were rendered. The Z buffer doesn't need to be a z value per pixel, clever use of the vertical span buffer is enough. Remember that in Doom everything was render using vertical segments, not horizontal.
Skizz
Skizz
I own one of Andre LaMothe's really old game development books, Tricks of the Game Programming Gurus, and I'm pretty sure that it covers a Doom-style rasterizer using the vertical strip technique. It's actually more Wolfenstein-style since there aren't any variations in ceiling or floor height, but the basic techniques are there. It's either this book, or one that's related to it, but either way they're over a decade old and really really cheap to pick up.
I don't think Doom used the painter's algorithm except for sprites. I vaguely recall Carmack talking about turning the map vertices (end points of walls) into polar coordinates which were used to determine occlusion (and what an inelegant hack that was). The "alpha tested" surfaces had to be drawn back to front though, which made some areas of the game run very slowly on a <16MHz machine...
Quote:Original post by Zipster
I own one of Andre LaMothe's really old game development books, Tricks of the Game Programming Gurus, and I'm pretty sure that it covers a Doom-style rasterizer using the vertical strip technique. It's actually more Wolfenstein-style since there aren't any variations in ceiling or floor height, but the basic techniques are there. It's either this book, or one that's related to it, but either way they're over a decade old and really really cheap to pick up.
I have that book. I'm holding in my lap at the moment. It does indeed cover the verticle strip technique. Code for the technique can also be found here: winray.cpp. Imo, fun to play with, but quite limited.
Quote:Original post by jbarcz1
AFAIK the reason why Doom1 drew back to front..
I'm pretty sure that this engine used angle tricks for occlusion culling.
Doom is 2.5D, yes, but it is one stage too. This allow polygons culling using a kind of 1D array of 1D occluded FOV. And it allow front to back rendering using painter algorithm.
Quote:Original post by Skizz
It's a very common misconception that Doom used a raycasting system. It didn't. It used a system called Binary Space Partitioning (BSP). It used a simple 2D implementation of the algorithm (Quake used a 3D version together with a system called Potentially Visible Sets or PVS). I don't have exact details to hand but I'm sure googling for "Binary Space Partitioning" or "BSP" would yield some useful information. Interestingly, the method used in the original Doom games was not the most efficent way of doing it. The walls were drawn back to front resulting in overdraw (where you draw to the same pixel twice). It is possible, though a bit more complex, to create a front to back rendering system that eliminates overdraw. I don't know if Doom did this, but the version I came up with used self-generating code to do the texture scaling for the walls and sprited.
Skizz
Didn't it use a BSP accelerated ray-caster?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
