Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

RegularKid

BSP Doom Style Rendering

This topic is 5478 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

I''m confused on how Doom uses the BSP trees to do it''s rendering. I downloaded the source code, but it is very cryptic to try to figure out. However, I have figured out that although it uses BSP trees to figure out which walls are visible, it still uses Wolfenstien-like wall strip rendering techniques. This is where I get confused. I understand how a BSP tree would work if you were to figure out which walls are visible and then draw those whole polygons, however how would this work for just drawing wall strips instead of the whole wall polygon? It doesn''t seem to make sense to me. Could someone explain to me Carmack is doing there? Thanks!

Share this post


Link to post
Share on other sites
Advertisement
I don't know how the source code works (haven't even looked at it), but I'm pretty sure he used a front to back rendering technique. The BSP tree lends itself well to this purpose, because you can to a front-back parse.

I tried this once with a simple maze game. I kept track of which horizontal ranges where taken up by the walls I just drew. If the next wall I tried to draw didn't intersect with any of the not-yet-rendered ranges, I didn't bother to draw it. When the entire horizontal range of the screen was rendered, I stopped drawing. It worked well. I'm guessing DOOM used a similar rendering style.

I know the .wad files for DOOM contain visibility values, such that if you knew which subsector you were in, you could quickly determine which subsectors could even possibly be seen from where you are. This was one way of eliminating a subsector from the rendering.

In addition, each node of the tree had a rectangular region that encased all the walls within it, and you could do a quick check on that to see if is crosses any of the not-yet-rendered regions, or even any part of the screen. If it didn't cross, you ignore that part of the tree.

Of course, see-through walls like opening doors, cage bars, etc. would need to be pushed on the stack and drawn last.

Also, the graphics for the wall are stored as vertical strips, making it fast for the renderer to decide where it needs to start drawing, and use as little processing as possible once the rendering of that wall begins. Just calculate the beginning X and the ending X, and render a vertical line at a time until you render that many pixel columns. Something like that.

Hope some of this helps. I wasn't sure what you meant by "wall strips".


[edited by - Waverider on June 19, 2003 3:08:28 PM]

Share this post


Link to post
Share on other sites
both wolfenstien and doom, while giving the appearence of true 3d, were actually 2d with a few perspective shape drawing techniques that made them appear 3d.

if you''ll notice, on no map will you find that there are ever rooms on top of other rooms, or even walls on top of walls. that is because all this data is in a 2d map defining the walls, and extra data for the height of those walls.

Doom made this into a 2d BSP, considering the floor & ceiling were always there, and always solid (there was nothing on the under/over side of them). when rendering the level, it divides the screen up into columns of pixels, so if you have a 320x240 screen, thats 320 columns. then a ray was traced in the 2d map for each column of pixels, sending it down the bsp tree. that way it could easily and recursivly draw the walls, however im sure there was some optimization to remove the overdraw generated, probably some form of z buffer for a single column.

the important thing to keep in mind was that although you saw doom in 3d, it was 90% 2d.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The reason doom only uses vertical strips to render the walls is that you get a perspective correct render when texture mapping, a line across the polygon that has a constant Z value follows a straight line in the texture. For vertical surfaces, with no possible texture rotation, that is a vertical line.

The floors and ceilings have a slightly trickier task, because the line can be at any orientation (though it is still straight).

IIRC, doom renders everything front to back using the BSP, using the upper/mid/lower sectioning of walls to eliminate overdraw. If a mid section is 2-sided, it is stuffed onto a stack to render as a second pass. If the upper or lower portion of a sidedef is visible, they are rendered, and the extents of the mid section are stored. More distant walls are clipped against the mid extents, and a 1-sided line will cease all wall rendering for that column of the screen.

After that, the floors and ceilings are rendered with a floodfill-esque algorithm. Then the stack of 2-sided lines is rendered, along with sprites IIRC.

Share this post


Link to post
Share on other sites
Hmmm. I understand how BSP tree''s help to quickly find out what walls are possibly visible and the order in which to draw the walls. But, combinded with raycasting, I just don''t see how it helps speed that up. You still have to send out rays from the player''s view like wolfenstein and check each step for an intersection, right? How is DOOM''s BSP tree speeding up the raycasting part of the engine? Any ideas? I will also keep looking through the code for hints, but Carmacks code is kind of hard to follow sometimes

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
One could raycast through a BSP instead of the wolfenstein grid


Doom uses two steps:

step 1: draw bsp front to back
But instead of performing the innerloop with texturing, they just store the parameters{ y_min,y_max,u_start,u_end,v,ve}[x]


step 2:
for each x
texture(parameter[x''])

Share this post


Link to post
Share on other sites
quote:
Original post by RegularKid
Hmmm. I understand how BSP tree''s help to quickly find out what walls are possibly visible and the order in which to draw the walls. But, combinded with raycasting, I just don''t see how it helps speed that up. You still have to send out rays from the player''s view like wolfenstein and check each step for an intersection, right? How is DOOM''s BSP tree speeding up the raycasting part of the engine? Any ideas? I will also keep looking through the code for hints, but Carmacks code is kind of hard to follow sometimes


Well.. it should be simple.

With the BSP tree you know which walls are infront of you and with are futher away. So you just do some line intersection-math beginning with the wall most closly to you. If the ray (from the eye) hits that wall, then draw one slice. Simple! Else go to the one futher away in the BSP tree.

/MindWipe

Share this post


Link to post
Share on other sites
Whoa. Why didn''t I think of that? That makes total sense. Instead of checking every step for the intersections, just do a line intersection check with the lines. Thanks!

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!