Rendering Visplanes by Column - GooberMan/rum-and-raisin-doom GitHub Wiki

But first, a bit of theory

Everyone knows what a polygon is, yeah? You learn about these in school. It's just an N-sided shape. In real-time computer graphics, triangles are the most commonly used form of polygon. Here's a polygon we prepared earlier, texture mapped with some perspective to give you the impression of depth.

But let's expand our understanding of a polygon. If you were to pick any point on the polygon and draw a line directly out from it in 3D space, this is what is known as a normal. Another mathematical construct that uses a normal is a plane. A plane is a two-dimensional surface that expands infinitely far. Just as Doomguy would see if he were standing in infinity.

A plane in 3D space is defined as a normal and a distance from the origin. In Doomguy's world, the floor plane there is the sector floor height and a normal pointing directly up in to the sky.

Remember how we started off talking about a polygon? With this in mind about a plane, you can thus define a polygon as a set of constraints on a plane. Or, in other words, extend your polygon edges out to infinity and you have a plane.

So how does a polygon get processed by a rendering engine? Simple. It constructs scanlines from your polygon. For each row of pixels on your screen, it works out the beginning and ending pixels that a polygon overlaps and fills it in with whatever you choose. In our case, perspective-corrected texture data.

This is essentially what a visplane is. Short for visible planes, it is simply the Doom engine's way of providing constraints on floor and ceiling planes for rendering purposes.

Visplanes, and how they're rendered in the original code.

If you're in the Doom community, chances are you know all about visplane limits. But why is that limit even there? This is thanks to memory limitations of the time. As the renderer traverses the BSP tree, it will work out where floors begin and end on the screen in a top-to-bottom manner. For each floor that matches height, texture, and light they will be collapsed in to a single visplane structure where possible.

But what is a visplane? Simply put, it's an array of pixel coordinates for each screen column. The topmost and bottom-most pixel is recorded along with the previously mentioned data. Here's a few example visplane columns highlighted for the floor plane directly in front of the player's viewpoint.

After all walls are rendered, the next step is to go back to all these recorded visplanes. From here, the engine will construct spans. What is a span? Well, remember how we illustrated a rasterline for a polygon above? That's basically all it is - a visplane translated in to rasterlines. Row by row, it will move the start and end column of a span to match the furthest extents of a visplane column found. A couple of spans are highlighted in green in the following image.

It does this transformation to scanlines like this for a number of reasons. The Doom renderer treats each scanline as the same 3D height, thus meaning it only need to perform one multiply to get a perspective-correct transformation for the texture (there is in fact a separate buffer of height values generated for each row that a visplane covers). As it marches along the texture, it linearly interpolates the data to get the correct pixel. If the rotation of the object says it needs to move two texels left and one texel up to get the next sample for the output pixel, then that's just done with a very efficient addition operation. Lighting is also constant along a scanline, meaning it only needs to fetch a single colormap instead of potentially changing colormaps every output pixel.

For a thorough mechanical explanation of visplanes, be sure to check out Fabien Sanglard's Doom engine book.

Visplanes with a transposed buffer

Now that our buffer is transposed, we don't want to render across the screen for the same reason the column renderer doesn't - cache concerns. Which means we need to convert our visplanes to not render by row, but to render by column.

Alright, first port of call. so let's start with visplane columns.

Hey, hold on. They already look like scanlines!

Now that our buffer is transposed, we do not need to generate spans. There is no point in generating horizontal data any more. We already know the exact region of the screen we want to render to, but without spans we just need to work out how.

So. Remember how I said that a scanline is just a clipped line from a polygon, which itself is a clipped plane? Rather than try and translate Carmack's original code, we're going to do something wild. We're going to look in to how to create a perspective-correct texture mapper ourselves from scratch.

This is not easy knowledge to find on Google these days. But I had no tomes on the subject handy, so I went looking. And I came across an educational article from 1997. The takeaway? There was actually a decent chunk of code that can be recycled from Carmack's orginal code - specifically, the sampling code for any given point on a plane. So if you already know the code to look up a texture coordinate, that's your start. From there, it's all about efficient interpolation.

The method described in there suggests that a fairly efficient way to speed up your operations if you don't want generate new look-up coordinates from scratch every frame is to calculate sample points N pixels apart, divide the difference by N - or, if you're using integers and N is a power of two, use log2(N) as a right shift value for the same result - and just do exactly what Carmack did. Sample, add the fractional data to your texture coordinates, and repeat until you hit N pixels. Then sample N pixels ahead and repeat.

The only question left was lighting. At the same time the Y height values are calculated, we work out the light level and cache that value. While diminished lighting is linear based on distance, I have not yet determined if it is linear in screenspace. There may be a similar interpolation win to be had there.

This particular method was important to get back speed in to the renderer. If you were to sample the texture accurately at every output pixel, you end up doing a ton of multiplications and run much slower than the original code. Which means you want to bring everything down to additions as much as possible. Unfortunately, you can't make the same assumptions Carmack made about rendering a plane in to the screen as rendering across the screen. With this method, performance gets better the higher your screen resolution goes. Below 640x400, this method is slower than the original code. But above and beyond, I have functions for log2(4), log2(8), log2(16), and log2(32). This is necessary because the lower your resolution, the lower your N needs to be to avoid really weird errors as illustrated in this video.

But what you do get at the end of the day is very efficient flat rendering at high resolutions. On my test i7 from the E1M1 starting room, flats using the log2(32) path go from ~13 milliseconds to ~5 milliseconds per frame with a target resolution of 2560x1200 - a widescreen resolution so that I can draw more flats, and ~50% more pixels than a 1080p render buffer.

Also notice the errors that crop up with the original code when using widescreen. Similarly, the more pixels away you get from the start of a span the more inaccuracies get introduced with the original, non-self-corrective interpolation method.

There are several ways to solve these if you keep spans, and source ports since the code release have explored a few of these options, but I'm not keeping spans and this method is fast and fairly accurate.

This method may work well without a transposed buffer

The speed gains I got just from an algorithmic perspective at a high resolution indicates that it should also work efficiently with a non-transposed buffer.

The real implication though?

Every piece of data the engine generates is now a rasterline. Walls, floors, ceilings. It doesn't matter, they all now render in a cacheline.

This changes things. Quite a bit. I've basically redefined visplanes here and deleted spans. To take it further, I would also put wall rendering through the new functions. At that point, there will be nothing at all stopping the renderer from becoming a full 3D renderer. You can even keep slime trails, since supporting view rotations won't change at a fundamental level how seg edges are projected towards the player along their floor/ceiling plane.