The Definitive Guide to Visplanes

[Anarkavre]

Visplanes have always seemed mysterious, so I planned to write an article explaining them that was simple to understand. I went through all the related code and everything can be categorized into three stages: Generation, Mapping, and Rendering. I will explain the code for these three stages with simple explanations and visuals. Just a warning, parts of this require knowledge of algebra, geometry, and trigonometry, so brush up on those for a full understanding. So with that, let’s delve into the mysterious visplanes.

 

Generation

 

Each frame R_ClearPlanes is called in R_RenderPlayerView to reset data related to clipping, visplane generation, and texture mapping. I will come back to the part related to texture mapping in a later section. R_FindPlane is called in R_Subsector for both the floor and the ceiling. This checks to see if a visplane already exists with the same height, pic, (different for floor and ceiling) and light level of the subsector. If it cannot find one, it creates a new one with the height, pic, and light level of the subsector. R_CheckPlane is called in R_StoreWallRange for both the floor and the ceiling if they are visible. This checks if the plane selected earlier can be merged with the area it wants to render. If there is no vertical divide, the area is merged with the visplane. If it cannot be merged, a new visplane is created. As the linesegs are rendered in R_RenderSegLoop, the top and bottom of the visplane are marked for both the floor and the ceiling if they are visible.

 

Mapping

 

R_DrawPlanes is called in R_RenderPlayerView to draw all visplanes that were generated. If the visplane is for a sky, it will draw the sky as columns like the walls and the sprites since it does not have to be projected the same way as floors and ceilings. If the visplane is for a floor or ceiling, it will convert the columns into spans of pixels to be drawn.

 

Figure 1 - Floor as columns

 

 

Figure 2 - Floor as spans

 

 

It does it this way because the strip of the floor or ceiling is at a constant depth and it helps save on perspective calculations that can be done once and used for the entire span. R_MakeSpans is called in R_DrawPlanes for each visplane drawn. It performs the conversion from columns to spans. When a span is ready to be drawn, R_MapPlane is called in R_MakeSpans. It performs the necessary perspective calculations for the span and caches them so they can be reused. The mathematics behind this is simple algebra, geometry, and trigonometry. We can find the distance to the strip of floor or ceiling using similar triangles and some known variables. We know the distance of the floor or ceiling from the player's view, the distance of the projection plane y the span is on from the center y of the projection plane, and the distance from the player to the projection plane.

 

The distance from the player to the projection plane can be easily calculated. The player field of view is 90° which makes it a 45°–45°–90° triangle. The projection plane would be along the hypotenuse of this triangle.

 

Figure 3 - Field of view and projection plane

 

 

We can find the distance from the player to the projection plane using trigonometry.

 

projectionplanedistance = (viewwidth / 2) / tan(90 / 2) = viewwidth / 2

 

The distance can then be calculated.

 

distance = planeheight * projectionplanedistance / dy

 

The step used for texture mapping can also be calculated. We know that the distance to the projection plane is equal to half of the width of the projection plane. This also applies for the distance to the strip of floor or ceiling.

 

step =  distance / projectionplanedistance

 

We need to know the step in the x and y directions of world space. We can find these using trigonometry.

 

xstep = step * cos(viewangle - 90)

ystep = -step * sin(viewangle - 90)

 

The last thing we need before rendering can happen is the point in world space where the strip of floor or ceiling begins. This can be found using trigonometry and some known variables. We know the player view x, the player view y, the player view angle, the view angle of the projection plane x where the span starts, and the distance to the strip of floor or ceiling.

 

x = viewx + (distance / cos(xviewangle) * cos(viewangle + xviewangle)

y = -viewy - (distance / cos(xviewangle) * sin(viewangle + xviewangle)

 

Rendering

 

R_DrawSpan or R_DrawSpanLow is called in R_MapPlane depending on the graphic detail mode set. It draws the span by stepping over the strip of floor or ceiling in texture space and sampling the texture at each discrete point.

 

Figure 4 - Sampling points

 

 

Figure 5 - Sampling points zoomed

 

 

That is all there is to visplanes. They aren't very mysterious after all. I wrote a little demo that lets you watch a floor be drawn. You can also turn, move, and strafe. You can think of it as being a room with walls infinitely far away, so the visplane starts at the horizon which is the center y of the projection plane. The demo isn't exactly how Doom works, but it uses all the same mathematics that I explained.

 

I hope you enjoyed this article and learned something from it. If I made any mistakes or errors, please let me know so that I may make corrections.

Edited December 19, 2018 by Anarkavre

[Linguica]

Have you seen this thread @anotak made last week?

 

[Anarkavre]

I have not seen it, but I will read it. I was curious how they worked for use in my ray-casting engine. Once I learned everything, I thought the knowledge may benefit others. I was planning on writing this article for a few months. I had the figures, notes, and a rough draft, but I only wrote the full article today. I wasn't aware of anything that went in depth and I wanted to try to explain it as simple as possible.

Edited September 15, 2018 by Anarkavre

[kb1]

@Anarkavre Nice, straight-forward description, and interesting post! Thanks for taking the time to write this.

[Tango]

this is awesome, thanks so much for posting :D

[Felix420]

Hello there,

I've been trying to implement said algorithm, however I found myself struggling at implementing slopes, as in Duke Nukem' 3D, into it.
 

@njit(fastmath=True)
def render_visplane(TEXTURE_Width, TEXTURE_Height, TEXTURE_Data, isFloor, zfloor, zceil, cpos, cpos_z, cangle):
    visplane = np.random.uniform(0,1, (s.SCREEN_WIDTH, s.SCREEN_HEIGHT_2, 3))

    for y in range(0, s.SCREEN_HEIGHT_2):
                    
        if not (y - s.SCREEN_HEIGHT_2) * 0.5 * s.SCREEN_WIDTH == 0:
            distance = (cpos_z - zfloor + (s.SCREEN_RATIO_WIDTH*(cpos_z-zfloor))) / (y - s.SCREEN_HEIGHT_2) * 0.5 * s.SCREEN_WIDTH if isFloor else (zceil - cpos_z + (s.SCREEN_RATIO_WIDTH*(zceil - cpos_z))) / (y - s.SCREEN_HEIGHT_2) * 0.5 * s.SCREEN_WIDTH
        
        else: distance = m.inf

        length = distance / m.cos(s.HFOV_2)
        x1 = -cpos.x + length * m.cos((cangle + (s.HFOV_2)))
        y1 = cpos.y - length * m.sin((cangle + (s.HFOV_2)))
        stepX = distance * m.cos(cangle - s.HFOV) / (s.SCREEN_WIDTH_2)
        stepY = -distance * m.sin(cangle - s.HFOV) / (s.SCREEN_WIDTH_2)

        for x in range(0, s.SCREEN_WIDTH):
            tx = int(((100) * x1) % TEXTURE_Width)
            ty = int(((100) * y1) % TEXTURE_Height)

            if (tx < 0): tx = 0

            if (ty < 0): ty = 0

            color = TEXTURE_Data[tx][ty]

            if not tx > s.SCREEN_WIDTH and not ty > s.SCREEN_HEIGHT and check_keyColor(color):
                if isFloor: visplane[x][y] = TEXTURE_Data[tx][ty]

                else: visplane[x][-y] = TEXTURE_Data[tx][ty]

            x1 += stepX
            y1 += stepY

    return visplane

That's basically the same code as in the JavaScript Demo, however fitted to my needs and in Python (Numpy, Pygame libraries used).

Since x1 and y1, or however you want to call them, are literal positions in World Space I could utilize them to get a value between 0 and 1, to measure at which height of the slope they are. This works since I span the slope between two points, virtually creating a gradient.

 

@njit(fastmath=True) 
def get_gradient(v1, v2, vt):
    t = closest_point_on_line_segment(vt, v1, v2)

    d1 = distance(v1, v2)
    d2 = distance(t, v2)
    
    return d2/d1 if d1 != 0 else 0

However since a height input is already demanded at the beginning of the calculus, before x1 and y1 are calculated, I have no clue how to implement that.

So I'd be glad if someone could help.

[Felix420]

Ok, so after observing the rendering footage posted on Fabian Sanglards Website I found out that sloped floors i.e. sloped ceils in Duke Nukem' 3D must use another algorithm, as they are drawn in Vertical Spans not Horizontal ones.