![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/toomed_variable_z4.gif\")
<\/figure>\n<\/div>\n\n\n<\/p>\n\n\n\n
Here we’re adjusting the floor and ceiling height of our corridor. When we raise the floor, we need to render a wall texture between our floor and the raised corridor floor. When we lower the floor, we need to render a wall texture between the lowered floor and the normal floor on the other end.<\/p>\n\n\n
![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image.png\")
<\/figure>\n<\/div>\n\n\n<\/p>\n\n\n\n
Changing the ceiling height can also expose a bit of wall texture:<\/p>\n\n\n
![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-1.png\")
<\/figure>\n<\/div>\n\n\n<\/p>\n\n\n\n
Our renderer has to be able to model these floor sections in order to keep track which of piece of floor has which floor and ceiling height, and we have to keep track of the textures to draw when they are exposed.<\/p>\n\n\n\n
Like DOOM<\/a>, I will denote regions of the map with a particular floor and ceiling height (and later, floor and ceiling textures) to be called a sector.<\/em> Sectors will naturally be closed polygons in our top-down 2D map. <\/p>\n\n\n\n Here you can see a top-down view of the TOOM level editor, showing the same region as rendered above. The red triangle is the camera, which looks toward the right. <\/p>\n\n\n <\/p>\n\n\n\n Here is the same shot, filled in a bit to make it easier to interpret:<\/p>\n\n\n <\/p>\n\n\n\n As covered in the last post, the world is defined using a triangle mesh. Our corridor, for example, is comprised of two triangles. The sector for that corridor must be referenced by the lines along the corridor’s boundary:<\/p>\n\n\n <\/p>\n\n\n\n The sector itself just stores the z heights right now. It doesn’t know which edges it corresponds to. Instead, we have the side geometry refer to the sector it should correspond to. This approach is again, very much like DOOM<\/a>.<\/p>\n\n\n\n We are using a Doubly Connected Edge List (DCEL) to represent our triangle mesh. Edges in a DCEL are bi-directional . If we think of edges as right-handed, and an edge A->B as being on the right-hand side of AB, then we can just have every directed edge at the boundary of a sector keep track of which sector it helps enclose.<\/p>\n\n\n The sides that refer to the corridor are yellow, whereas the sides that refer to the primary sector are orange. When we raycast from the camera down the corridor, we can check for z changes when we traverse over edges where the sector changes. Here we see a raycast with two locations where the sector heights might change:<\/p>\n\n\n <\/p>\n\n\n\n The data structures for this are pretty simple. A directed edge may have a SideInfo:<\/p>\n\n\n\n A SideInfo is simply a struct that contains a lower, middle, and upper texture, the index of the sector to refer to, and some flags. Right now, the only flag I use is one to determine whether a wall is passable, and if so, we can avoid rendering the middle texture.<\/p>\n\n\n\n The TextureInfo entry is pretty simple as well:<\/p>\n\n\n\n And Sectors are just basic data as well:<\/p>\n\n\n\n With these data structures in-hand, rendering becomes a little more complicated. We continue to cast our ray out, as before. Now, however, we need to keep track of how much we’ve already drawn.<\/p>\n\n\n\n To illustrate, let’s look at a horizontal cross-section of geometry:<\/p>\n\n\n Here I have drawn the area swept out as we cast a single ray to the right, down a single pixel-column. The light purple boxes show all of the regions in our field-of-view where we need to render ceiling pixels, the dark purple boxes show where we need to render floor pixels, and the green boxes show where we need to render wall pixels.<\/p>\n\n\n\n When we start raycasting, we start having not drawn any pixels. The bounds on where we can draw contains the whole vertical pixel column, between zero and the number of pixels:<\/p>\n\n\n\n \\[y_\\text{lo} = 0 \\qquad y_\\text{hi} = \\text{SCREEN_SIZE_Y}\\]\n\n\n\n We start to traverse the mesh, and hit our first sector change:<\/p>\n\n\n At this point we calculate the y-location (i.e., location in the vertical pixel column) of the ends of the floor and ceiling. We render the floor and ceiling into our pixel column. We’re already pretty used to this trigonometry by now.<\/p>\n\n\n\n \\[\\begin{aligned} y_\\text{ceil} & = \\frac{\\text{SCREEN_SIZE_Y}}{2} + \\gamma \\left( z_\\text{ceil} – z_\\text{camera} \\right) \\\\ y_\\text{floor} & = \\frac{\\text{SCREEN_SIZE_Y}}{2} + \\gamma \\left( z_\\text{floor} – z_\\text{camera} \\right)\\end{aligned}\\]\n\n\n\n where<\/p>\n\n\n\n \\[\\gamma = \\frac{\\text{SCREEN_SIZE_Y}}{\\text{y field of view}} \\cdot \\frac{\\text{cam length}}{\\text{ray length}}\\]\n\n\n\n The y yield of view is how many units up the camera views for every unit we raycast outward. I’m using about 0.84. The camera length is close to 1, and adjusts for the fact that our screen is flat and not curved, so rays travelling left or right of center have to have the length adjusted. Other than that, its just a function of the heights and how far our ray has traveled.<\/p>\n\n\n\n In this case, the next sector has an increase in the ceiling height and a decrease in the floor height. That means we do not have any local wall textures to render. We set \\(y_\\text{lo} = y_\\text{floor}\\) and \\(y_\\text{hi} = y_\\text{ceil}\\) and keep on raycasting:<\/p>\n\n\n At the next sector transition, we once again compute \\(y_\\text{floor}\\) and \\(y_\\text{ceil}\\). This time, however, the ceiling drops and the floor rises, so we also have wall segments to render. We compute their pixel extents in the same way:<\/p>\n\n\n\n \\[\\begin{aligned} y_\\text{upper} & = \\frac{\\text{SCREEN_SIZE_Y}}{2} + \\gamma \\left( z_\\text{upper} – z_\\text{camera} \\right) \\\\ y_\\text{lower} & = \\frac{\\text{SCREEN_SIZE_Y}}{2} + \\gamma \\left( z_\\text{lower} – z_\\text{camera} \\right)\\end{aligned}\\]\n\n\n\n where \\(z_\\text{upper}\\) and \\(z_\\text{lower}\\) are the new sector ceiling and floor heights, respectively.<\/p>\n\n\n\n When we continue our raycast, we find that the next sector transition only increases the ceiling height. The new \\(y_\\text{floor}\\) is greater than \\(y_\\text{lo}\\), so we render the patch of floor. The new \\(y_\\text{ceil}\\) is not any lower than our current \\(y_\\text{hi}\\), due to the ceiling being parallel to our camera view, so we don’t need to render anything there. <\/p>\n\n\n <\/p>\n\n\n\n We finally proceed and hit a closed sector. We render the last bit of floor and then render its center texture:<\/p>\n\n\n <\/p>\n\n\n\n So that’s how the renderer works when you have variable z heights and upper, middle, and lower textures. Each raycast has to do more work to determine what to draw, and it keeps track of where it is within its y pixel bounds to make sure we don’t mistakenly draw something on top of what we’ve already rendered.<\/p>\n\n\n\n In this previous blog post<\/a>, I covered sprites, and how they use the DOOM picture format<\/a>. In short, sprites like monsters are stored in vertical pixel strips. Why? Because when we render the vertical portions of the world, we’re rendering convenient vertical sections of these sprites. The vertical orientation forms a right-triangle, which makes the math of figuring out which pixel to draw more efficient. DOOM uses the same format for wall textures (both upper and lower). I ended up doing the same thing.<\/p>\n\n\n\n So, wall textures are the same as sprites. What about horizontal textures? We’d like to draw textures on our ceilings and floors too:<\/p>\n\n\n (Yeah, these don’t fit thematically. I haven’t loaded my own floor and ceiling textures yet. These just come from DOOM.)<\/p>\n\n\n\n We can again leverage our previous work<\/a> to figure out how to draw floor and ceiling textures. Unlike the vertically-oriented wall textures, these “flat” textures are most efficiently drawn horizontally across the screen. As such, in DOOM they are called flats<\/a><\/em>. <\/p>\n\n\n\n Our render is most adept at rendering things vertically. It works on one pixel column at a time. So how do we hope to render anything horizontally?<\/p>\n\n\n\n Well, the raycasts start with the leftmost pixel column and then work their way to the right. I keep track of active spans<\/em>, which are horizontal sections of the screen that need to eventually be rendered with a single flat at a single floor height. Whenever we need to start a new span, we close out the previous one and render it. <\/p>\n\n\n <\/p>\n\n\n\n The gif above shows how the renderer produces a scene. We draw vertical sections as we raycast, but start\/maintain horizontal spans that only get rendered (1) when another span in the same y-coordinate starts or (2) we are done raycasting.<\/p>\n\n\n\n Each active span contains all of the information needed to render it efficienctly, once it needs to be rendered:<\/p>\n\n\n\n We can do the computation work of calculating the hit and step values when we first create the span. We set x_start at that time, and initially set x_end to the same value. If we go to render the same sector in the same location in the next column, we increment x_end.<\/p>\n\n\n\n You may have noticed that these images get darker the further we’re looking. This is an intentional effect from DOOM that enhances the sense of depth.<\/p>\n\n\n\n This is easiest to see without the floor textures:<\/p>\n\n\n\n <\/p>\n\n\n\n Conceptually, this is really simple. Render pixels darker when they are further away. <\/p>\n\n\n\n The light level<\/em> of a pixel column drops off as the raycast distance increases. Or rather, the darkness level increases with the raycast distance.<\/p>\n\n\n\n Pixel values are written to the screen as RGB values. How does one take an RGB value and make it darker? Well, white is 0xFFFFFF and black is 0x000000, so the simplest way is to decrease each channel by some percentage. To do it “more correctly”, you can convert your RGB color into the Lab colorspace<\/a>, reduce its lightness, and then convert it back. That is an expensive operation.<\/p>\n\n\n\n The original DOOM didn’t have access to RGB values. Or rather, it didn’t have access to all of them. According to the DOOM Black Book<\/a>, PC video games of the 90s had 320×200 resolution with 1 byte per pixel drawn from a 256-color palette<\/a>. This meant that programmers could set the 256 colors in the palette, and drawing a pixel to the screen effectively meant indexing into this palette by setting a 1-byte pixel index rather than a full RGB value.<\/p>\n\n\n\n So how does one change a pixel’s brightness?<\/p>\n\n\n\n The DOOM developers precomputed mappings from pixel values at full brightness to pixel values at reduced brightness. There were many such colormaps<\/a>, 32 that were computed for all light levels from 100% brightness all the way down to 0%. There were even some additional colormaps, such as an inverted colormap used when the player becomes invulnerable:<\/p>\n\n\n <\/p>\n\n\n\n All wall textures and flats store pixel indices rather than RGB values. These pixel indices pass through the chosen colormap and then index into the palette to get the RGB value. In the original DOOM system, indexing into the palette was done for you by the video card. I’ll be doing it myself here.<\/p>\n\n\n\n The palette stores sequential BGR values, so we just grab the section we need and then overwrite the FF for the alpha channel.<\/p>\n\n\n\n As a final note, there is one additional lighting effect that helps make the map more legible. Like the trick used in Wolfenstein<\/a>, walls closer to being x-aligned are drawn 1 point brighter than normal, and walls closer to being y-aligned are drawn 1 point darker than normal. Furthermore, each sector has its own baseline light level. This lets the map creator make some areas naturally darker, and allows for some nice floor shadow effects:<\/p>\n\n\n <\/p>\n\n\n\n Ah, that last image gave it away. The geometry changes and lighting changes now bring us more-or-less to parity with the original DOOM. We can load and traverse the original DOOM levels!<\/p>\n\n\n <\/p>\n\n\n\n This rendering is done using the raycasting method, via our DCEL, rather than using DOOM’s BSP. This means we can totally avoid loading SEGS<\/a>, SSECTORS<\/a>, NODES<\/a>, and the BLOCKMAP<\/a>. <\/p>\n\n\n E1M1 loaded into the TOOM editor.<\/p>\n\n\n\n <\/p>\n\n\n\n Work was required to be able to load the geometry into our DCEL correctly. Mainly in being able to properly flip mesh edges in order to be able to produce edges that match the map geometry, and then constrain them. I might cover that in a future post.<\/p>\n\n\n\n Okay, we’ve reached geometric parity with DOOM. Is there something this DCEL approach can do that DOOM cannot?<\/p>\n\n\n So how does that work?<\/p>\n\n\n\n When we raycast or when the player walks around, we traverse between faces in our triangle mesh. We can create a portal by linking two edges in the triangle mesh and adding the necessary logic such that, when traversed, we come out the linked edge instead.<\/p>\n\n\n\n Below we see the top-down view of the portal setup playing out. The red triangle shows the player camera and its approximate view cone. <\/p>\n\n\n <\/p>\n\n\n\n The player movement for when we traverse a portal is:<\/p>\n\n\n\n Geometrically, we are figuring out the rotation angle between our portals (which could be precomputed) and then rotating our movement direction and speed when we traverse. <\/p>\n\n\n\n Note that the +pi term compensates for the fact that the destination portal side is oriented 180 degrees with respect to the source portal side.<\/p>\n\n\n <\/p>\n\n\n\n When we raycast through portals, we have properly account for any height changes on the receiving sector. We want to view the other side as if we were the appropriate height:<\/p>\n\n\n\n <\/p>\n\n\n\n There is a bit of extra bookkeeping we have to do with portals – namely that for flats to render correctly we have to update the camera position to the place it would be as if the portal did not exist and we were peering toward our destination:<\/p>\n\n\n We then have to recompute some of the vectors used to create spans. This is all because flats are rendered on a fixed grid, and we compute where we are in that grid based on the camera location. We have to fake the camera being in the proper location “behind” where the portal surface is. Please take a look at the source code for the nitty-gritty.<\/p>\n\n\n\n <\/p>\n\n\n\n There is a lot of neat gamemap stuff that one can do with portals and the non-Euclidean geometry they unlock. Some of it is more blatant, like the first portal, and some of it can be quite subtle, like a hallways that is shorter or longer than expected. <\/p>\n\n\n\n This blog post covered adding variable z heights for floors and ceilings, which then required being able to render wall sections revealed at floor or ceiling height changes. We rendered those vertically, because that is most efficient. We then figured out a way to render horizontal textures too, which were most efficient to render in horizontal strips. We added some lighting effects. We then had everything we needed to represent the original DOOM level geometry. We concluded with an overview of portals – sides in our mesh that are linked together such that crossing one results in you exiting out the other.<\/p>\n\n\n\n I made the code for TOOM<\/a> and TOOMED<\/a> available in separate repos. TOOM is the “game”, written in pure C without graphics libraries. TOOMED is the TOOM Editor, written in C++. It basically doesn’t use graphics libraries either, but it does use Dear ImGui with an accelerated backend, as well as have more liberal data structures for easier manipulation of game data and assets.<\/p>\n\n\n\n That’s more or less it for TOOM, for now. There are a few things the renderer doesn’t support that DOOM has, such as animated nukage<\/a>, pickups, or proper handling for partially-transparent walls. There obviously isn’t any gameplay. No shooting or doors or anything like that. Those things are neat, of course, but I feel like I already understand how they work, and it’d just be pretty tedious work for me to get TOOM running with all that. Maybe I’ll do it, but for now I’m thinking I’ll be turning to other interests. Thanks for reading!<\/p>\n\n\n\n One of the reasons that this TOOM project interested me in the first place was the promise that I might learn how to program something “for real” and really have to care about performance. I admire folks like Casey Muratori<\/a> and Jonathan Blow<\/a> who ardently advocate for efficient programming, and that software engineers should understand what goes on under modern abstractions.<\/p>\n\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-2.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-3.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-4.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-5.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-6.png\")
<\/figure>\n<\/div>\n\n\nstruct SideInfo {\n u16 flags;\n u16 sector_id;\n TextureInfo texture_info_lower;\n TextureInfo texture_info_middle;\n TextureInfo texture_info_upper;\n};<\/code><\/pre>\n\n\n\nstruct TextureInfo {\n u16 texture_id; \/\/ Index in the texture atlas\n i16 x_offset; \/\/ Texture x offset\n i16 y_offset; \/\/ Texture y offset\n};<\/code><\/pre>\n\n\n\nstruct Sector\n{\n u16 flags;\n f32 z_floor;\n f32 z_ceil;\n};<\/code><\/pre>\n\n\n\nRaycasting with Varying Heights<\/h2>\n\n\n\n
![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-7.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/Selection_661.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/Selection_663.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/Selection_665.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-11.png\")
<\/figure>\n<\/div>\n\n\nRendering Textures<\/h2>\n\n\n\n
![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-12.png\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/toom_active_spans.gif\")
<\/figure>\n<\/div>\n\n\nstruct ActiveSpanData {\n \/\/ Location of ray_dir_lo's intersection with the ground.\n common::Vec2f hit;\n \/\/ Shift 'hit' by one pix column moved toward hi's intersection.\n common::Vec2f step;\n u16 sector_id;\n u16 flat_id;\n bool is_active;\n \/\/ The camera x pixel index where this span starts.\n int x_start;\n \/\/ The most recent camera x pixel where this span currently ends.\n int x_end;\n};<\/code><\/pre>\n\n\n\nColors and Light Levels<\/h2>\n\n\n\n
![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-13.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-14.png\")
<\/figure>\n<\/div>\n\n\nu8 palette_index = patch.post_data[column_offset];\npalette_index = colormap.map[palette_index];\nu32 abgr = *(u32*)(palette.colors + 3 * palette_index) | 0xFF000000;<\/code><\/pre>\n\n\n\nstruct Palette {\n u8 rgbs[768];\n};\n\nstruct Colormap {\n u8 map[256];\n};<\/code><\/pre>\n\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-15.png\")
<\/figure>\n<\/div>\n\n\nDOOM Levels<\/h2>\n\n\n\n
![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/toom_e1m1_walkthrough_4.gif\")
<\/figure>\n<\/div>\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/toom_e1m1_walkthrough_5.gif\")
<\/figure>\n<\/div>\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/toom_e1m1_walkthrough_6.gif\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-16-1024x650.png\")
<\/figure>\n<\/div>\n\n\nPortals<\/h2>\n\n\n\n
![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/toom_portal8.gif\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/toom_portal6.gif\")
<\/figure>\n<\/div>\n\n\n\/\/ Suppose we are crossing the line segment AB from pos to pos_next,\n\/\/ where pos_next now lies on AB.\nVec2f v_face = b - a;\n\n\/\/ Calculate where along the segment we intersected.\nf32 v_face_len = Norm(v_face);\nf32 x_along_texture = v_face_len - Norm(pos_next - a);\n\n\/\/ Update our quarter edge using the destination quarter edge\n\/\/ stored in the side info.\ncamera_state->qe = mesh.Tor(side_info->qe_portal);\n\n\/\/ The vector along the new face is\nVec2f c = mesh.GetVertex(side_info->qe_portal);\nVec2f d = mesh.GetVertex(mesh.Sym(side_info->qe_portal));\nVec2f cd = d - c;\ncd = Normalize(cd);\n\n\/\/ Our new position is:\ncamera_state->pos = c + x_along_texture * cd;\n\nf32 angle_ab = std::atan2(v_face.y, v_face.x);\nf32 angle_cd = std::atan2(cd.y, cd.x);\nf32 angle_rot = CounterClockwiseAngleDistance(angle_ab, angle_cd) + M_PI;\nf32 cos_rot = std::cos(angle_rot);\nf32 sin_rot = std::sin(angle_rot);\n\n\/\/ Now to get the new direction, we need to rotate out of the new face\ndir = {cos_rot * dir.x - sin_rot * dir.y,\n sin_rot * dir.x + cos_rot * dir.y};\n\n\/\/ We also need to rotate our speed\nvel = {cos_rot * vel.x - sin_rot * vel.y,\n sin_rot * vel.x + cos_rot * vel.y};<\/code><\/pre>\n\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/Selection_681.png\")
<\/figure>\n<\/div>\n\n\ncamera_z += (sector_dst->z_floor - sector_src->z_floor);<\/code><\/pre>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/toom_portal7.gif\")
<\/figure>\n<\/div>\n\n\n![\"\"](\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2023\/08\/image-18.png\")
<\/figure>\n<\/div>\n\n\nConclusion<\/h2>\n\n\n\n
A Note on Efficiency<\/h2>\n\n\n\n