Jump to content
  • Advertisement
Sign in to follow this  
eviltwigflipper

Doom 1 and 2 Raycasting

This topic is 4307 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!