Visplane Rendering - What's the general overview as to how it is done?

[CacophonousChorus]

I've come to the point where I now need to add the rendering of visplanes to my engine.  How does DOOM exactly handle them?  What type of math (equations) is involved?  Are they computed one at a time, or by scanline at a time?  If it's a scanline at a time, then is it done vertically or horizontally for each visplane?  How are the offsets into each texture computed?  

 

Any insights into the overall process would be immensely appreciated as I'm having a difficult time wrapping my head around the general process.

 

Thanks!

[scifista42]

See this page:

 

https://doomwiki.org/wiki/Doom_rendering_engine#Rendering

 

And these two files in the source code:

 

https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/r_plane.c

https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/r_draw.c

 

And this video:

 

 

[fraggle]

Simply put, a visplane is a contiguous area of the screen that is all the same texture, z position (height) and light level. For example, suppose you can see an area of the screen where there are 10 different sectors, but all those sectors have the same floor texture, floor height and light level; those might all be effectively "joined together" and drawn as a single visplane.

 

It gets slightly complicated because a visplane has to be vertically contiguous. For example suppose you're looking at a donut-shaped area of floor where the inside of the donut is a different texture; the outside would be split into two visplanes because there's a hole in the middle; you can't have one visplane for the whole outside area.

 

You can visualize it as being like a strip of texture across the screen; at each X position of the strip there's a column of texture drawn, and it extends across a certain Y range. But you can't have a gap in the middle of that range; to do that you have to split it into two visplanes instead.

 

If you want to generate lots of visplanes in a way that will cause a visplane overflow, a good example is to draw a checkerboard pattern (eg. with varying textures; light levels will also work). Even though there may be only two sectors, the pattern necessitates generating many different visplanes, one for each square.

[CacophonousChorus]

@scifista42

 

Quote

Floors and ceilings are drawn as "visplanes", which represent horizontal runs of texture, given a floor or ceiling at a particular height, light level and texture (if two adjacent sectors have the exact same floor, these can be merged into one visplane). Each X position in the visplane has a particular vertical line of texture which is to be drawn.

Because of the requirement to draw only one vertical line at each X position, it is sometimes necessary to split one visplane into multiple visplanes. For example, consider looking at a floor with two concentric squares. The inner square will vertically divide the surrounding floor, and within the horizontal range of the inner square, two visplanes are needed for the surrounding floor.

 

The first link states that the visplanes represent a horizontal list of columns to draw, but your video shows the visplanes being rendered as horizontal lines rendered sequentially as they move toward the center of the screen.  Which is it?  Is it possible that the columns are rendered first to a buffer and then all rows are drawn to the screen one at a time, or is the link incorrect, or am I incorrectly reading it?

 

I'd look at the source, but I'm really trying not to as it feels kind of like cheating, if that makes sense. 

[CacophonousChorus]

@fraggle

 

Quote

You can visualize it as being like a strip of texture across the screen; at each X position of the strip there's a column of texture drawn, and it extends across a certain Y range

 

So, each visplane is just a vertical strip using a texture and neighboring strips with the same texture and z height are merged?

 

How are the UV calculations done?  I.e., how is the first UV offset picked at the bottom of a visplane given a particular x coordinate?  Would you have to store the world space coordinates for the bottom of each column of each wall and then interpolate from the player's position to that point to get the first UV (then just interpolate UV/Z until you hit the top of that visplane column)?

[dpJudas]

The visplanes are stored initially as a list of columns to draw, but when drawing them it finds the row spans covered by those columns. It is done this way because everything in Doom is drawn in directions where the depth (Z) is constant. For walls that is columns, and for floor/ceilings that is rows.

 

The constant depth part is important for performance as you'd otherwise have to do a division for every pixel drawn. As long as the depth is constant, you can calculate the UV coordinates at each end of the span and then do a linear interpolation between them.

[Quasar]

5 hours ago, dpJudas said:

The visplanes are stored initially as a list of columns to draw, but when drawing them it finds the row spans covered by those columns. It is done this way because everything in Doom is drawn in directions where the depth (Z) is constant. For walls that is columns, and for floor/ceilings that is rows.

 

The constant depth part is important for performance as you'd otherwise have to do a division for every pixel drawn. As long as the depth is constant, you can calculate the UV coordinates at each end of the span and then do a linear interpolation between them.

I am curious if the division is amortized in the face of cache misses on modern computers, and if we shouldn't think about drawing walls as horizontal strips of non-constant Z depth using a full perspective-correct texture mapping operation. I'd be interesting at the least to see a port that attempts it :)

[dpJudas]

4 hours ago, Quasar said:

I am curious if the division is amortized in the face of cache misses on modern computers, and if we shouldn't think about drawing walls as horizontal strips of non-constant Z depth using a full perspective-correct texture mapping operation. I'd be interesting at the least to see a port that attempts it :)

It is a good question. A drawer that doesn't use constant-Z also has to calculate the diminishing light for every pixel though. Calculating the shade is a linear interpolation, I think, but there are some clamps in place to prevent it from going out of bounds.

[kb1]

10 hours ago, Quasar said:

I am curious if the division is amortized in the face of cache misses on modern computers, and if we shouldn't think about drawing walls as horizontal strips of non-constant Z depth using a full perspective-correct texture mapping operation. I'd be interesting at the least to see a port that attempts it :)

I think, as a first step, you'd have to parse the textures at load time, and store them differently to allow them to be traversed in any direction other than top-to-bottom. A single pass could calculate the light levels via interpolation and cache them before drawing the wall. There's a chance that all of the extra work required to draw horizontally will regardless be faster than the standard vertical draw. Cache misses can be REALLY slow :(  If only DoomGuy looked up and down vs. left and right...

[scifista42]

22 hours ago, CacophonousChorus said:

The first link states that the visplanes represent a horizontal list of columns to draw,

No, it doesn't. The text you quoted is followed by this text:

Quote

While visplanes are constructed essentially from vertical "strips", the actual low-level rendering is performed in the form of horizontal "spans" of texture. After all visplanes have been constructed, they are converted into spans which are then rendered to the screen. This appears to be a tradeoff: computation time is saved by constructing visplanes as vertical strips, but in order to decrease the number of perspective calculations made, it is easier to draw them as horizontal strips. Just as a single vertical strip of wall is at a constant distance from the camera, a single horizontal strip of a floor or ceiling is at a constant distance, and so some rendering calculations can be done once and used for an entire span.

Note that a single visplane is generally neither a single column nor a single row - a single visplane is a whole 2D area on the screen, therefore coverable either by columns or by rows.

22 hours ago, CacophonousChorus said:

I'd look at the source, but I'm really trying not to as it feels kind of like cheating, if that makes sense. 

I'd understand if you found it bothersome to read through it, but "feels like cheating" shouldn't be a problem if your goal is just to learn.

Edited September 28, 2017 by scifista42

[Maes]

[Jon]

22 hours ago, CacophonousChorus said:

I'd look at the source, but I'm really trying not to as it feels kind of like cheating, if that makes sense. 

 

That really doesn't make sense. The source is the canonical truth as to what is happening. Everything else is derivative, necessarily simplified, and possibly wrong.

[Maes]

23 hours ago, CacophonousChorus said:

I'd look at the source, but I'm really trying not to as it feels kind of like cheating, if that makes sense. 

What Jon said. Plus, if you really feel like going "blind date" on your project, why don't you just implement the first, naive algorithm that comes to mind and works, and work it up from there?

[Linguica]

On 9/27/2017 at 4:38 AM, CacophonousChorus said:

I'd look at the source, but I'm really trying not to as it feels kind of like cheating, if that makes sense. 

I assure you that even looking at the Doom source does not make everything obvious.

[fraggle]

Just wanted to point out that Fabien Sanglard's review of the Doom engine has a really nice illustration of visplanes, in particular it shows the donut thing that I mentioned in my previous comment:

 

[Optimus]

I was curious historically why the original game did just throw you back in DOS? Why not just stop at it's 128 visplanes limit and abandon the rendering for the rest? Maybe there would be artifacts or hall of mirrors on floor/ceilings, but it would be mostly far away as I think they are drawn from front to back. Or would there be crashing issues if you skip drawing some visplanes?

 

Of course just letting the game on, could possibly lead to careless mappers not caring about reducing detail, but the worse would be that there would be artifacts and that's only at specific viewpoints but the game would go on, and not just throwing the gamer back to DOS, which would be the absolute unfriendly thing. You'd say it was done so, so that it punishes the mapper to really take care, but the mapper could also forget textures, add too much items (that make some of them dissapear on the view iirc), but those don't throw you back to DOS, you continue playing with horrible artifacts but doesn't abruptly stop your gameplay.

[Maes]

1 hour ago, Optimus said:

I was curious historically why the original game did just throw you back in DOS? Why not just stop at it's 128 visplanes limit and abandon the rendering for the rest? Maybe there would be artifacts or hall of mirrors on floor/ceilings, but it would be mostly far away as I think they are drawn from front to back. Or would there be crashing issues if you skip drawing some visplanes?

Well, the Classic Doom port in Doom 3: BFG Edition does something like that: beyond raising the visplane limit to 384, if there are no more available visplanes, it simply "reuses" the last one: I can imagine the effect being only the last excess visplane being rendered correctly, and the rest would just become HOMs. Of course, since it cannot load PWADs, that's quite a chore to verify.

[Jon]

1 hour ago, Optimus said:

I was curious historically why the original game did just throw you back in DOS? Why not just stop at it's 128 visplanes limit and abandon the rendering for the rest? Maybe there would be artifacts or hall of mirrors on floor/ceilings, but it would be mostly far away as I think they are drawn from front to back. Or would there be crashing issues if you skip drawing some visplanes?

 

One reason might be quality control. If it's a non-fatal error, then one of the vanilla maps under development might have triggered it by accident in some circumstances, but it get overlooked. Carmack in particular was very keen that the renderer was rock-solid (something he said about wolf3d too). So, by making it a fatal error, they were damn sure that no vanilla maps went past the limit. As for setting the limit to 128, that might have been a performance decision too.

 

 

[kb1]

It is obvious (to me) that Carmack struggled to make the game fit in the memory of the computers of the day. The game is strictly balanced for the IWADs.