Doom Rendering

[MaxWindiff]

I am not quite sure where to post this... so I wish to put it here. Please correct me if I am wrong.

I have been reading some Doom 3D engine articles, and most of them tells me that the engine is able to achieve 0% overdraw and relatively efficient visibility calculation. I also see in one thread that Gherkin said that building a BSP is the only efficient way to display the map in the 3D editing mode of DB.

Can anybody tell me a brief description of the technique used by the Doom engine and DB (or simply the name of the technique used)?

[Gherkin]

Go down the BSP tree and with each split you test on which side of the split line you are. Then you continue processing that side of the tree (or the other side first if you want everything in back-tofront order) and then the other side. So you need a recursive routine.

When you reach a subsector (leaf in the tree), you test if its segs are visible. Here a one dimensional clipping buffer is perfect since Doom's map is actually only 2D. Take the angles of the wall towards the viewer and project them on the clipping buffer to test if any column (read: pixels) are visible. If so, add the subsector to a list. If non of the segs are visible, skip the subsector.

Now you have a front-to-back or back-to-front list of subsectors that you will see from your current position. I believe Doom not only keeps subsectors in this list, but also inserts other stuff like Things and maybe segs.

Im not sure how Doom renders since I wrote the rendering for DirectX, so that works very different than software rendering, but from studying its graphics it looks like this;

It takes the farthest subsector and renders each of its segs. With each seg it renders the floor and draws that in columns all the way to the bottom of the screen. Same for the ceiling, it draws from the seg all the way up to the screen. Sounds like a mess, but because it starts with the farthest, the ones closer will overdraw the 'mess' that segs in the back made.

For hardware rendering (DirectX/OpenGL) its works very different. You have to make a polygon for the ceiling and floor of each subsector and 'quad' polygones for the upper, middle and lower textures of each seg (I do this per sidedef instead of per seg, because its much faster to draw a whole sidedef at once). Because you have a Z buffer, the order of drawing doesnt matter. I draw from front to back on purpose to reduce overdraw, but transparent middle texture must still be drawn at last from back to front to keep correct transparency.

pfew, i think thats about all the basics. Im sure someone can add something to this.

[MaxWindiff]

Woo! Thanks for your detailed explanation... I think I got it now. You are really a genius!

[Gherkin]

Eh ok...

And dont forget to project your segs onto the clipping buffer once you chose to show the subsector (after visibility testing). In Doom Builder I also made a test which checks if the clipping buffer is fully drawn on, in which case it terminates BSP walking immediately (you wont see anything else anyway).

[Quasar]

Gherkin said:

I draw from front to back on purpose to reduce overdraw, but transparent middle texture must still be drawn at last from back to front to keep correct transparency.

Isn't it possible to draw translucencies front to back if you invert the alpha values?

EDIT: Oops I guess you mean transparencies as in 2S textures with holes in them, not translucent 2S textures like in BOOM. Sorry ^_^

[Vile1011]

Speaking of which, I've always wondered why Duke Nukem 3D maps don't need a nodesbuilder, unless it's hidden and really really fast. I figured a BSP tree was required for any 3D environment.

[MaxWindiff]

Gherkin said:
Eh ok...

And dont forget to project your segs onto the clipping buffer once you chose to show the subsector (after visibility testing). In Doom Builder I also made a test which checks if the clipping buffer is fully drawn on, in which case it terminates BSP walking immediately (you wont see anything else anyway).

For the clipping buffer... how do you implement it? I think there have to be two parallel 1D arrays of integers to indicate the undrawned "top" and "bottom"... am I correct?

[CodeImp]

nevermind my post, heh

[Gherkin]

No, one does the job. Segs on a single-sided linedef always block the view, Segs on double-sided linedefs only block the view when one of the sides ceiling <= one of the sides floor. The rest you do not count as blocking the view.

You can get the Doom Builder source code from my site. The builder.dll is c++ source and you can find the BSP and Clipping code in bsp.cpp. It uses a 360 degree clipping buffer (when looking forward your back is already marked as clipped before walking the bsp) and some fancy trick takes care of the 0/360 point and does drawing and testing with entire memory block writes.

What are you making anyway?

[fraggle]

I wrote this a few months ago.

[Ultraviolet]

fraggle said:

I wrote this a few months ago.

And did you simplify the definition of a sector so much intentionally? I hope you'll revisit that... *reads on*

[fraggle]

Ultraviolet said:

And did you simplify the definition of a sector so much intentionally? I hope you'll revisit that... *reads on*

?

I left out some of the stuff like the special sector types and sector tags because its not really relevant to the rendering engine.

[Ultraviolet]

fraggle said:

I left out some of the stuff like the special sector types and sector tags because its not really relevant to the rendering engine.

I was really referring to how you referred to the polygonal area as a sector, not a sector as a set of properties that you apply to a group of linedefs (EDIT: since I'm being nitpicky anyway, I should probably say "sidedef area" or something)forming a polygonal area. It is relevant because you can apply a sector number to any linedefs you want and have several polygonal areas share the same sector. It's something I used to do often when I messed with mapping... just so I could see right away in the editor when I had areas that are exactly the same and all that. I'm rather frugal with my sector use, even though I like to use a lot MORE sectors for detail. I recycle sectors as much as possible. I'm told that can cause monster line-of-sight and hearing issues, so I never did recycle sectors across big areas that would be occupied, just for little detail sectors and such.

Got a little off-topic, oops. :P I'm just saying you used a very "n00b-compatible" definition of sectors. Was it intentionally written that way so more people would understand what a sector is commonly used for? I know it took me a while before it just clicked in my head that a sector isn't really an area, but a set of properties used for an area, so it's probably best to leave sectors explained the way you did, at least for introduction to the engine.

[MaxWindiff]

Gherkin said:
What are you making anyway?

You mean me? Not writing anything... just interested in 3D rendering algorithms (especially older games like Doom/Quake, since I want to know the difference between them and today's games).

[MaxWindiff]

fraggle said:

I wrote this a few months ago.

Um?? I cannot load it...

[fraggle]

Ultraviolet said:

I was really referring to how you referred to the polygonal area as a sector, not a sector as a set of properties that you apply to a group of linedefs (EDIT: since I'm being nitpicky anyway, I should probably say "sidedef area" or something)forming a polygonal area. It is relevant because you can apply a sector number to any linedefs you want and have several polygonal areas share the same sector. It's something I used to do often when I messed with mapping... just so I could see right away in the editor when I had areas that are exactly the same and all that. I'm rather frugal with my sector use, even though I like to use a lot MORE sectors for detail. I recycle sectors as much as possible. I'm told that can cause monster line-of-sight and hearing issues, so I never did recycle sectors across big areas that would be occupied, just for little detail sectors and such.

Got a little off-topic, oops. :P I'm just saying you used a very "n00b-compatible" definition of sectors. Was it intentionally written that way so more people would understand what a sector is commonly used for? I know it took me a while before it just clicked in my head that a sector isn't really an area, but a set of properties used for an area, so it's probably best to leave sectors explained the way you did, at least for introduction to the engine.

Yeah I know. I think it gives a clearer explanation this way, though.

MaxWindiff said:

Um?? I cannot load it...

e2 is slow sometimes. Try again later.

[sidav]

Can someone give detailed explanation about rendering of SEGS (in Vanilla Doom, of course)? I looked at the sources, but didn't understood so much.

[Kappes Buur]

sidav said:

...explanation about rendering of SEGS (in Vanilla Doom, of course)?....

Would that help?

http://fabiensanglard.net/doomIphone/doomClassicRenderer.php

[sidav]

Kappes Buur said:

Would that help?

http://fabiensanglard.net/doomIphone/doomClassicRenderer.php

Thanks, but it didn't helped a much. "After clipping, space remaining was interpolated and drawn as column of pixels: The height and Y coordinate of the column of pixel were based respectively on the SEGS's sector height and its distance from player POV.". But there is nothing about those interpolating and SEGS distance calculation process.