Sign in to follow this  

Doom 1 and 2 Raycasting

This topic is 4096 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Quote:
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.


Okay, for starters, Doom's engine was a raycasting engine that happened to use BSPs to accelerate. That's like saying "Unreal didn't use 3dfx Glide to render the scene, it used portals." It used the BSP to figure out which walls to DRAW, but it still used the old Wolf3d ray casting to do the actual draw of the walls, because it was damn fast.

Walls were, in fact, drawn front to back. Drawing the environment back to front would have been retarded; first, because that would have eliminated the main advantage of a BSP-based overdraw reduction system, and most importantly, that much extra memory access on the framebuffer would have been KILLER back then (hell, we STILL try to avoid excessive overdraw...but back then, no overdraw was particularly acceptable).

Entities in the world, however, were drawn back to front. They were clipped against the walls that were drawn before getting their spans drawn in much the same way that the raycaster drew the walls.

Back-to-front on the entities was more acceptable because entities were smaller and generally non-occluding, and because it was easier than doing any sort of hellish transparency-masking to determine visibility.

Just trying to sort out a few misconceptions that have been strewn about. For more information, please check out the wiki:

http://en.wikipedia.org/wiki/Doom_engine.

~fin~

Share this post


Link to post
Share on other sites

This topic is 4096 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this