Polygon-based (DOOM-like) 3D Software rendering engine from scratch

Polygon-based (DOOM-like) 3D software rendering engine from scratch

This tutorial will focus on the subject of coding pseudo-3D graphics. I call it pseudo-3D because it will work with 2D maps and transform them to appear as 3D on the screen. It will not support everything that a true 3D offers. A true 3D assumes 3D models, 6 degrees of freedom of movement of rigid bodies in 3D-space, etc. Those kinds of simulations won’t be covered in this tutorial. It is highly debatable whether this is an actual engine or an application. An engine should be coded in a more generic, reusable way, while the example code in this tutorial will be fragmented. It is with demonstrational purposes only.

Also, it will be more focused on practice than theory. You can learn all the theories on the internet. I will, however, explain some fundamental theories to support the code snippets.

It will not be some groundbreaking game engine with jaw-dropping effects, A.I., particle systems, etc. It will only cover the vital parts, the bare minimum, required to create a (pseudo) 3D rendering engine. You can research the rest yourself since there is enough information about it. Or you can always drop by my webpage again to see if I have already explained anything about it in some other tutorial.

What you will learn:

To render 3D graphics the way DOOM did
Basic physics (collision detection and resolution)
Rasterization
To code simple distance-based flat shading
Movement Mechanics

What will not be covered:

Concave polygons which require converting to convex ones by splitting them
Texture mapping
A.I.
Spatial partitioning

This is the bare minimum required to simulate a 3D environment where you can walk around a level and collide with walls.

I mention what will not be covered intentionally because I’d like to give you some directions on what to continue with after finishing this tutorial.

In order to be able to complete this tutorial, I have to put some constraints on myself. These are as follows.

We will code everything in plain C. No C++ or higher-level programming language. If someone wants to translate it to another language and make it more accessible to other people — email me.
The code will not follow any industry (or my own, for that matter) standards of formatting or organization. It will be fragmented and pretty much ugly.

Let me get rid of one detail from the very beginning. Consider it as a disclaimer.

To put a pixel on the screen, you need a graphical context where you can draw. Think of it as a canvas where a painter paints. All modern operating systems have their own way of doing that. Windows has GDI+, macOS has Core Graphics, Linux uses Xlib, etc. OpenGL does that in its own generic way and utilizes considerable amount of acceleration from your graphics card.

In our case, we won’t use GPU acceleration. We will do everything software-based, with CPU horsepower only, just like in the good old days. This will help you learn the nuts and bolts of some of the techniques used in the 3D rendering.

We also need to handle keyboard and mouse input. All OSes have this supported by their APIs differently.

I have two choices here. To explain how to do it with the APIs supported by each graphics subsystem or to explain it only for one of those subsystems and let you translate it yourself for your target OS.

You see, I don’t have all the time in the world. Also, this tutorial will be long enough anyway. And I want to keep it focused on the rendering graphics aspect of the things, not the details of how a specific OS does its drawing. So we will make a small exception and void the “from scratch” part in the title and use a 3^rd party library.

We will use SDL2 to create a graphical context to draw on it and its event-handling system to track keyboard and mouse input.

This way, the final result will be both generic and save me a lot of time. It will be just this single exception from the “from scratch” part. SDL2 will act as a translation layer between our code and the underlying OS graphics and input interfaces. We will do the rest from scratch, including coding a line drawing algorithm. So, you can easily replace SDL2 with anything you want later.

Let’s get started.

What will you need?

SDL2 installed and added to your environment PATH variable (search the internet on how to do it)
C/C++ compiler (we will use GCC or its Windows flavor – MinGW – search on the internet on how to install it and add it to your env PATH)
Make tool (if you’re using MinGW, you may need to install it via its terminal – just type “pacman -S make”)
Some convenient text editor or IDE of your choice

To be in sync, I will use Mingw64, the Make tool that comes with it, the MinGW version of SDL2, and Visual Studio Code because I know many people use it nowadays.

At this point, I will assume that you already have the above prerequisites in place, installed, and working.

Initialize the project

First, let’s create the base skeleton of our main.c file.

#include <SDL2/SDL.h>

#include <math.h>

#include <memory.h>

#include <stdio.h>

#undef main

int main()

{

return 0;

}

Note that there is a line “#undef main”. This is required because SDL2 has its own main called SDL_main, which is supposed to replace the default one that C uses. We don’t want that, so we undefine and ignore it completely.

We also added a few default C headers – math.h, memory.h, stdio.h. We will need them later.

Now let’s make a simple Makefile in the same directory.

INC = D:\coding\libs\SDL2-devel-2.0.22-mingw\SDL2-2.0.22\x86_64-w64-mingw32\include #replace with your SDL2 include dir

LIB = D:\coding\libs\SDL2-devel-2.0.22-mingw\SDL2-2.0.22\x86_64-w64-mingw32\lib #replace with your SDL2 lib dir

SRC = main.c

L = SDL2 #this is the SDL2 lib that you have to link with

all:

gcc -I$(INC) -L$(LIB) $(SRC) -l$(L) -o 3dengine.exe

Note the comments in the first two lines. Replace the paths with the ones of your SDL2 include and lib directories in case they are not in your environment PATH var.

Now open your terminal (CMD or Power Shell on Windows), switch to the project’s directory, and run make. If you did everything right, you should get your source compiled. If not, something is not set up properly. Try to figure out what and fix it before we continue.

Let’s initialize a graphical context with SDL2 so we can start drawing.

Define your window size:

#define screenW 800

#define screenH 600

Create a new global variable called renderer:

SDL_Renderer* renderer;

Add the following code in your main():

SDL_Init(SDL_INIT_VIDEO);

SDL_Window* mainWin = SDL_CreateWindow(

“3D Poly Renderer”,

SDL_WINDOWPOS_CENTERED,

screenW, screenH,

SDL_WINDOW_SHOWN);

renderer = SDL_CreateRenderer(mainWin, 0, SDL_RENDERER_SOFTWARE);

SDL_DestroyRenderer(renderer);

SDL_DestroyWindow(mainWin);

SDL_Quit();

This will create a window with dimensions of 800×600 pixels and initialize a graphical context inside it. The graphical context in SDL is called Renderer. We will use it all around the code so we declare it as a global var. There are way better ways to do that, but for the sake of the example, I will keep most things straightforward. My goal is not to teach you how to code properly. I will talk about that in a separate article.

After initializing the window and the context, we destroy them, shutdown SDL2 and exit.
If you compile and run the app, you should see a window open and immediately closing.

Now what we need is a Game Loop.

The Game Loop

The Game Loop is simply an infinite loop that runs until the user emits an exit request.

Add the following code just after initializing the SDL2 renderer and before the line that is destroying it:

int loop = 1;

while (loop)

{

}

Don’t compile and run the project just yet. We need a way to exit this loop in order to terminate it. Let’s integrate a small event-handling routine with SDL2 to track the pressing of the ESC key.

Create a new function above main() called ShouldQuit:

int ShouldQuit(SDL_Event event)

{

if(event.type == SDL_QUIT || event.key.keysym.sym == SDLK_ESCAPE)

return 1;

return 0;

}

Update the Game Loop fragment as follows:

int loop = 1;

SDL_Event event;

while (loop)

{

SDL_PollEvent(&event);

if (ShouldQuit(event))

break;

}

This will handle an ESC key press or the window’s X button.
We can now start working on the rendering part.

Rendering in Theory

Let me first tell you one fundamental fact. There is no such thing as a true 3D in the field of computer graphics. There is just an orchestration of shapes and colors rendered on a flat surface in a way that fools the human brain into interpreting the image as a scene that has depth in it. So basically, our job is to fool the human eye.

Our scene will be simple. Just vertical walls, a flat floor, and a sky. You can extend it later on your own.

There are three kinds of “spaces” when it comes about 3D graphics.
A Model (or local) Space, a World Space and a Screen Space. We will not work with the model space in this article.

The World Space is our level. Its walls, entities and objects, their shapes and positions on the map, etc.
The Screen Space is everything that is transformed to a shape that will be displayed on your screen.

For example, in our 2D top-down level view we see polygons – this is in the World Space.
The edges of the world space polygons are later transformed to vertical walls that have height and angle when displayed. They also are polygons but in the Screen Space.

Every shape is built by smaller primitives. A polygon is constructed by edges (lines) that are connections between vertices (points), which have two coordinates (X & Y).

To start rendering, we need our vertices in order to build polygons in the world-space that form the wireframe models of our walls in screen-space and later fill them up with color. The process of filling up a polygon with color is called rasterization.

Rendering in Practice

I have created an array of vertices to build our level from them so we don’t lose time. You can create a CAD-style level editor later on if you like to experiment with the level design. It’s what I did in order to build the vertices array. The rendering will be exactly like in DOOM. The levels will be made out of convex polygons with information about their height so later we can render them as 3D objects on the screen space.

First, we need to define several structures that we will work with. We must define what a Vector, Line, and Polygon should mean to our program.

The Vector struct will consists of two elements, X and Y coordinates. A Line (or the proper name – line segment) struct will consists of two vertices – the start and end point of the line segment. A Polygon struct will keep an array of all vertices it’s build-out of, their count, a distance that will hold the distance from the polygon to the camera, and the height of this polygon so we can later render it as a wall with a certain height.

We will need one more structure – ScreenSpacePoly. It will be used to form the surface of the wall that will be rendered on the screen. So far, all polygons I talked about are the level information about the walls: their position, size, and shape. But what we will actually see on the screen will be the 3D transformed edges of those polygons which on their own are polygons rendered in the screen space.

Let’s define those structures. Create a new file called typedefs.h and add the following code:

#define MAX_POLYS 10

#define MAX_VERTS 8

typedef struct Vec2

{

float x, y;

} Vec2;

typedef struct

{

Vec2 p1, p2;

} LineSeg;

typedef struct

{

Vec2 vert[MAX_VERTS];

int vertCnt;

float height;

float curDist;

} Polygon;

typedef struct

{

//a plane has 4 vertices since it’s a quadrilateral

Vec2 vert[4];

float distFromCamera;

int planeIdInPoly;

} ScreenSpacePoly;

Include this file in your main.c

I limited the Polygon structure vertices count to 8 since this is the maximum number of points in a polygon of the level I’ve created. Keep that in mind if you start messing around with the level design later on.

What we need now is something to draw with. To be able to put a pixel on the rendering context. SDL2 supports this, so we will use it. SDL2 also has a line drawing function, but we will use the Point drawing one in order it to draw pixels only so I can explain how to create your own line drawing algorithm later. It’s good to know how to do it, and it’s helpful in cases when you don’t have an OS or 3rd party library to help you out. Also, it could be useful not only for drawing occasions. You can cast rays with it to scan the environment, detect objects, etc.

I faced that scenario when I was participating in VMware’s annual borathon, where we coded a 3D polygon-based renderer that runs on a bare metal with a colleague of mine. We had no OS and APIs to support us. In fact, we even had no standard C library (libc) or all the fancy memory.h, stdio.h, math.h etc. to work with. We had to code almost everything from scratch and work directly with the hardware.

Create a new function above main() called PutPixel():

void PutPixel(int x, int y, Uint8 r, Uint8 g, Uint8 b)

{

if (x > screenW || y > screenH)

return;

if (x < 0 || y < 0)

return;

SDL_SetRenderDrawColor(renderer, r, g, b, 255);

SDL_RenderDrawPoint(renderer, x, y);

}

This function accepts 5 arguments. The first two are the position of the pixel in the rendering context. The last 3 are the RGB color channels intensity. We check if the pixel is outside the boundaries of the rendering context, and then we set the drawing color and draw a pixel.

There is one final thing to do before we can see our dot on the screen. We must tell SDL2 to update the screen with any rendering performed since the last screen update.

Create another function above main() called UpdateScreen():

void UpdateScreen()

{

SDL_RenderPresent(renderer);

}

If you add the following two lines in our game loop and compile and run the project, you should see a red dot on the top left of the screen:

PutPixel(30, 30, 255, 0, 0);

UpdateScreen();

Remove those lines after testing; we won’t need them.

Now we need our line drawing algorithm. It will be pretty short, so I won’t need to get into the details of it. But if you want to understand it in detail, search the internet for either “Bresenham’s line drawing algorithm” or “Digital Differential Analyzer” (DDA). We will stick with DDA.

Put the following function just after your PutPixel() function:

void DrawLine(int x0, int y0, int x1, int y1)

{

int dx;

if (x1 > x0)

dx = x1 – x0;

else

dx = x0 – x1;

int dy;

if (y1 > y0)

dy = y1 – y0;

else

dy = y0 – y1;

int sx = x0<x1 ? 1 : –1;

int sy = y0<y1 ? 1 : –1;

int err = (dx>dy ? dx : –dy)/2, e2;

for(;;)

{

PutPixel(x0, y0, 255, 0, 0);

if (x0==x1 && y0==y1) break;

e2 = err;

if (e2 >-dx) { err -= dy; x0 += sx; }

if (e2 < dy) { err += dx; y0 += sy; }

}

It takes two points – a start (X & Y) and an end (X & Y) and starts interpolating every next pixel X and/or Y coordinate, so at the end, it connects the two dots following the slope between them. At a pixel level zoom, it’s not always possible to have an ideal diagonal straight line. If the start and end points are aligned vertically or horizontally, then you have straight a line, but this is not possible if they are not aligned to one of their axis (X or Y) or with a perfect 45-degree slope.

Here is a drawing I did to illustrate it to you:

The four grids above represent portions of pixels on the screen. The green-filled squares are pixels that are currently lit. On a pixel-level zoom, you work with squares. As you can see, the DDA follows a line and lights up the pixels this line crosses. It calculates the slope between the two points and lights up every pixel at each delta position.

We now have everything we need to start rendering 3D graphics for the most part.

Let’s put the level data I generated for you. It consists of coordinates of vertices that form our polygons (walls) and essentially define our level. It also has a camera start position coordinate.

The camera in our scene is the position and angle from which you look the world. It’s simply another point in the level but it has one extra attribute – an angle.

Define one more structure for the camera in the typedefs.h file:

typedef struct

{

float camAngle;

float stepWave;

Vec2 camPos;

Vec2 oldCamPos;

} Camera;

Now define two more global variables in your main.c:

Camera cam;

Polygon polys[MAX_POLYS];

We need to initialize those variables with data. It will be long; you may prefer to do it in a separate file, but I will keep it in main.c for simplicity.

Create a new function init() and add the level data I have generated for you:

void Init()

{

cam.camAngle = 0.42;

cam.camPos.x = 451.96;

cam.camPos.y = 209.24;

polys[0].vert[0].x = 141.00;

polys[0].vert[0].y = 84.00;

polys[0].vert[1].x = 496.00;

polys[0].vert[1].y = 81.00;

polys[0].vert[2].x = 553.00;

polys[0].vert[2].y = 136.00;

polys[0].vert[3].x = 135.00;

polys[0].vert[3].y = 132.00;

polys[0].vert[4].x = 141.00;

polys[0].vert[4].y = 84.00;

polys[0].height = 50000;

polys[0].vertCnt = 5;

polys[1].vert[0].x = 133.00;

polys[1].vert[0].y = 441.00;

polys[1].vert[1].x = 576.00;

polys[1].vert[1].y = 438.00;

polys[1].vert[2].x = 519.00;

polys[1].vert[2].y = 493.00;

polys[1].vert[3].x = 123.00;

polys[1].vert[3].y = 497.00;

polys[1].vert[4].x = 133.00;

polys[1].vert[4].y = 441.00;

polys[1].height = 50000;

polys[1].vertCnt = 5;

polys[2].vert[0].x = 691.00;

polys[2].vert[0].y = 165.00;

polys[2].vert[1].x = 736.00;

polys[2].vert[1].y = 183.00;

polys[2].vert[2].x = 737.00;

polys[2].vert[2].y = 229.00;

polys[2].vert[3].x = 697.00;

polys[2].vert[3].y = 247.00;

polys[2].vert[4].x = 656.00;

polys[2].vert[4].y = 222.00;

polys[2].vert[5].x = 653.00;

polys[2].vert[5].y = 183.00;

polys[2].vert[6].x = 691.00;

polys[2].vert[6].y = 165.00;

polys[2].height = 10000;

polys[2].vertCnt = 7;

polys[3].vert[0].x = 698.00;

polys[3].vert[0].y = 330.00;

polys[3].vert[1].x = 741.00;

polys[3].vert[1].y = 350.00;

polys[3].vert[2].x = 740.00;

polys[3].vert[2].y = 392.00;

polys[3].vert[3].x = 699.00;

polys[3].vert[3].y = 414.00;

polys[3].vert[4].x = 654.00;

polys[3].vert[4].y = 384.00;

polys[3].vert[5].x = 652.00;

polys[3].vert[5].y = 348.00;

polys[3].vert[6].x = 698.00;

polys[3].vert[6].y = 330.00;

polys[3].height = 10000;

polys[3].vertCnt = 7;

polys[4].vert[0].x = 419.00;

polys[4].vert[0].y = 311.00;

polys[4].vert[1].x = 461.00;

polys[4].vert[1].y = 311.00;

polys[4].vert[2].x = 404.00;

polys[4].vert[2].y = 397.00;

polys[4].vert[3].x = 346.00;

polys[4].vert[3].y = 395.00;

polys[4].vert[4].x = 348.00;

polys[4].vert[4].y = 337.00;

polys[4].vert[5].x = 419.00;

polys[4].vert[5].y = 311.00;

polys[4].height = 50000;

polys[4].vertCnt = 6;

polys[5].vert[0].x = 897.00;

polys[5].vert[0].y = 98.00;

polys[5].vert[1].x = 1079.00;

polys[5].vert[1].y = 294.00;

polys[5].vert[2].x = 1028.00;

polys[5].vert[2].y = 297.00;

polys[5].vert[3].x = 851.00;

polys[5].vert[3].y = 96.00;

polys[5].vert[4].x = 897.00;

polys[5].vert[4].y = 98.00;

polys[5].height = 10000;

polys[5].vertCnt = 5;

polys[6].vert[0].x = 1025.00;

polys[6].vert[0].y = 294.00;

polys[6].vert[1].x = 1080.00;

polys[6].vert[1].y = 292.00;

polys[6].vert[2].x = 1149.00;

polys[6].vert[2].y = 485.00;

polys[6].vert[3].x = 1072.00;

polys[6].vert[3].y = 485.00;

polys[6].vert[4].x = 1025.00;

polys[6].vert[4].y = 294.00;

polys[6].height = 1000;

polys[6].vertCnt = 5;

polys[7].vert[0].x = 1070.00;

polys[7].vert[0].y = 483.00;

polys[7].vert[1].x = 1148.00;

polys[7].vert[1].y = 484.00;

polys[7].vert[2].x = 913.00;

polys[7].vert[2].y = 717.00;

polys[7].vert[3].x = 847.00;

polys[7].vert[3].y = 718.00;

polys[7].vert[4].x = 1070.00;

polys[7].vert[4].y = 483.00;

polys[7].height = 1000;

polys[7].vertCnt = 5;

polys[8].vert[0].x = 690.00;

polys[8].vert[0].y = 658.00;

polys[8].vert[1].x = 807.00;

polys[8].vert[1].y = 789.00;

polys[8].vert[2].x = 564.00;

polys[8].vert[2].y = 789.00;

polys[8].vert[3].x = 690.00;

polys[8].vert[3].y = 658.00;

polys[8].height = 10000;

polys[8].vertCnt = 4;

polys[9].vert[0].x = 1306.00;

polys[9].vert[0].y = 598.00;

polys[9].vert[1].x = 1366.00;

polys[9].vert[1].y = 624.00;

polys[9].vert[2].x = 1369.00;

polys[9].vert[2].y = 678.00;

polys[9].vert[3].x = 1306.00;

polys[9].vert[3].y = 713.00;

polys[9].vert[4].x = 1245.00;

polys[9].vert[4].y = 673.00;

polys[9].vert[5].x = 1242.00;

polys[9].vert[5].y = 623.00;

polys[9].vert[6].x = 1306.00;

polys[9].vert[6].y = 598.00;

polys[9].height = 50000;

polys[9].vertCnt = 7;

}

Now call this function just before entering your Game Loop, so the data can get initialized before we start rendering.

It’s time to code the first version of our rendering routine. It will go through several updates over this tutorial. I want to introduce it to you incrementally, so you don’t get overwhelmed.

Create a function just before main(), called Render():

void Render()

{

for (int polyIdx = 0; polyIdx < MAX_POLYS; polyIdx++)

{

for (int i = 0; i < polys[polyIdx].vertCnt – 1; i++)

{

Vec2 p1 = polys[polyIdx].vert[i];

Vec2 p2 = polys[polyIdx].vert[i + 1];

float height = –polys[polyIdx].height;

float distX1 = p1.x – cam.camPos.x;

float distY1 = p1.y – cam.camPos.y;

float z1 = distX1 * cos(cam.camAngle) +

distY1 * sin(cam.camAngle);

float distX2 = p2.x – cam.camPos.x;

float distY2 = p2.y – cam.camPos.y;

float z2 = distX2 * cos(cam.camAngle) +

distY2 * sin(cam.camAngle);

distX1 = distX1 * sin(cam.camAngle) –

distY1 * cos(cam.camAngle);

distX2 = distX2 * sin(cam.camAngle) –

distY2 * cos(cam.camAngle);

float widthRatio = screenW / 2;

float heightRatio = (screenW * screenH) / 60.0;

float centerScreenH = screenH / 2;

float centerScreenW = screenW / 2;

float x1 = –distX1 * widthRatio / z1;

float x2 = –distX2 * widthRatio / z2;

float y1a = (height – heightRatio) / z1;

float y1b = heightRatio / z1;

float y2a = (height – heightRatio) / z2;

float y2b = heightRatio / z2;

DrawLine(centerScreenW + x1, centerScreenH + y1a,

centerScreenW + x2, centerScreenH + y2a);

DrawLine(centerScreenW + x1, centerScreenH + y1b,

centerScreenW + x2, centerScreenH + y2b);

DrawLine(centerScreenW + x1, centerScreenH + y1a,

centerScreenW + x1, centerScreenH + y1b);

DrawLine(centerScreenW + x2, centerScreenH + y2a,

centerScreenW + x2, centerScreenH + y2b);

}

This function is really slow. If we had some kind of spatial partitioning, we were going to traverse just the polygons that are close to the camera and in front of its field of view. Due to the time constraints, that I’ve already mentioned, we will have to take this raw approach, unfortunately.

Add a call to this function in your game loop, then call the UpdateScreen() function.
Your game loop should look like this at that point:

while (loop)

{

SDL_PollEvent(&event);

if (ShouldQuit(event))

break;

Render();

UpdateScreen();

}

Now let me break down the Render() function and explain it piece by piece.

It starts with two nested for loops:

for (int polyIdx = 0; polyIdx < MAX_POLYS; polyIdx++)

{

for (int i = 0; i < polys[polyIdx].vertCnt – 1; i++)

{

The first loop traverses all polygons we have defined, and the second one traverses the vertices of the polygon currently indexed by the first loop, without the last vertex. We will access the last vertex within the loop by adding 1 to the array index. We need that in order to access two vertices at a time so we can form a line between them.

Vec2 p1 = polys[polyIdx].vert[i];

Vec2 p2 = polys[polyIdx].vert[i + 1];

float height = –polys[polyIdx].height;

We get the current vertex and the next one in the array. These vertices are our start and end points of the line segment that will be rendered later. We also get the height of the polygon, predefined in my level data. Note that we get its negative value. This is because we will subtract it from the vertical resolution of the rendering context.

float distX1 = p1.x – cam.camPos.x;

float distY1 = p1.y – cam.camPos.y;

float z1 = distX1 * cos(cam.camAngle) +

distY1 * sin(cam.camAngle);

We calculate the distance from the camera X & Y coordinates to the first point. I will clarify the purpose of the “z1” variable value and the usage of cos(angle) & sin(angle) shortly.

Now we do the same for the second point of our line segment:

float distX2 = p2.x – cam.camPos.x;

float distY2 = p2.y – cam.camPos.y;

float z2 = distX2 * cos(cam.camAngle) +

distY2 * sin(cam.camAngle);

Now we need to perform the first step of our perspective computation. Here comes the explanation of the z1 & z2 values and cos(angle) & sin(angle) mentioned above.

We need to recalculate the distances to each point based on the angle and distance from the camera. We need that in order to account the position and rotation of our camera within the world, prior to perform any rendering. Note that everything in front of the camera has a positive Z value, and everything behind the camera has a negative Z value.

distX1 = distX1 * sin(cam.camAngle) –

distY1 * cos(cam.camAngle);

distX2 = distX2 * sin(cam.camAngle) –

distY2 * cos(cam.camAngle);

The code block above (including the z1 & z2 initializations) is a representation of what is called world-to-camera transformation (and more specifically rotation in our case). This is often performed by a 4×4 matrix, called View Matrix in the true (non-pseudo) 3D computer graphics. For the sake of simplicity, we will not use matrices in this tutorial and not get into any further details about the View Matrix.

An important concept you need to understand about the idea of “cameras” is that the camera is just an imaginary concept. Whenever we say we “rotate the camera” what actually happens is that we set a bunch of coordinates based on which we will later rotate the world around and not the camera itself. The concept of camera is just an abstract idea, in reality it’s a bunch of raw coordinates that we use to rotate, move or tilt the world around the player’s view. Maybe that’s why many 3D graphics programmers are so self-centric. 😉

However, this is not enough. We need to render our world based on the ratio of the rendering context size so they are scaled accordingly.

float widthRatio = screenW / 2;

float heightRatio = (screenW * screenH) / 60.0;

float centerScreenH = screenH / 2;

float centerScreenW = screenW / 2;

We take both the horizontal and vertical centers of the screen. Also, its vertical aspect ratio which I called heightRatio, and the horizontal ratio, which will be simply half of the screen width.

Now the second part of our perspective algo:

float x1 = –distX1 * widthRatio / z1;

float x2 = –distX2 * widthRatio / z2;

float y1a = (height – heightRatio) / z1;

float y1b = heightRatio / z1;

float y2a = (height – heightRatio) / z2;

float y2b = heightRatio / z2;

What we do here is to transform our polygon line segment into a vertical plane which will be a face of a wall.

This is the so-called screen-space transformation. In true 3D we also use matrices to perform this transformation and also use the concept of field of view. We won’t get into details here also.

Essentially what happens is that we take what is at front of our camera and we transform it in a way such that it appears as 3D on the screen (therefore screen-space).

We take our horizontal distances (distX1 and distX2) and multiply them by the width ratio, and then we divide them by our Z coordinates for each point. This will make them appear closer or further from the camera based on their distance (their Z coordinate). We don’t need other X coordinates as we have only straight, vertical walls – no slopes.

However, to make our world-space line segment appear as a wall face in the screen-space, we must transform it from a line-segment with two points to a quadrilateral with four points. Two bottom points and two top points.

We calculate them by subtracting the vertical aspect ratio from the predefined height of the polygon and dividing the result by the distance Z. We do that for both the left and the right top vertices of the wall face.

Now we render them:

DrawLine(centerScreenW + x1, centerScreenH + y1a,

centerScreenW + x2, centerScreenH + y2a);

DrawLine(centerScreenW + x1, centerScreenH + y1b,

centerScreenW + x2, centerScreenH + y2b);

DrawLine(centerScreenW + x1, centerScreenH + y1a,

centerScreenW + x1, centerScreenH + y1b);

DrawLine(centerScreenW + x2, centerScreenH + y2a,

centerScreenW + x2, centerScreenH + y2b);

We call DrawLine() four times for each edge of the wall. Top, bottom, right, left.

If you compile and run this, you will see a horrible mess of wireframes stretching around.

You can already see walls and things that look like 3D objects but also all those lines going everywhere and nowhere.

This happens because some vertices go behind the camera (their Z coordinates become negative numbers). At that point, when we convert them to perspective correct 3D points in space, they mess up. We fix that with a technique called “clipping.”

The clipping process cuts everything outside the visible field and renders only what’s inside it. This both improves performance and corrects the picture. If any of the polygon points go outside the screen space boundaries, they will be ignored. We need that to make all vertices that are going behind the camera get ignored.

To do that, we need a function that checks for intersections between lines. It will check if the camera is between the start and end points of any line segment that goes in a certain direction on the Z axis. If the line segment goes behind the camera we cut it at the point the camera position is.
To check line intersections, we need two lines. So our camera will be transformed from a point to a small line just to enable this check. For the line intersection check, we need another function to calculate the Cross Product of those lines (check the internet about the Cross Product). In our case, we will modify a bit the cross product, which is meant to work with 3D coordinates, to work for 2D ones.

Put the following function somewhere above the Render() function:

float Cross2dPoints(float x1, float y1, float x2, float y2)

{

return x1 * y2 – y1 * x2;

}

It performs the 2D cross product calculation.

Right after, it put the following function, which will perform the line intersection check.

Vec2 Intersection(

float x1, float y1, float x2, float y2,

float x3, float y3, float x4, float y4)

{

Vec2 p;

p.x = Cross2dPoints(x1, y1, x2, y2);

p.y = Cross2dPoints(x3, y3, x4, y4);

float det = Cross2dPoints(x1 – x2, y1 – y2, x3 – x4, y3 – y4);

p.x = Cross2dPoints(p.x, x1 – x2, p.y, x3 – x4) / det;

p.y = Cross2dPoints(p.x, y1 – y2, p.y, y3 – y4) / det;

return p;

}

I won’t dig into the line intersection function details since I will also have to explain how the modified version of the Cross Product and determinants work. This is beyond the scope of this tutorial. You can find a lot of information in internet about that.

After implementing those two, we can update our Render() function to utilize them and perform clipping.
Now add the following code just before performing the second perspective computation in our Render function:

distX1 = distX1 * sin(cam.camAngle) –

distY1 * cos(cam.camAngle);

distX2 = distX2 * sin(cam.camAngle) –

distY2 * cos(cam.camAngle);

if (z1 > 0 || z2 > 0)

{

Vec2 i1 = Intersection(distX1, z1, distX2, z2,

–0.0001, 0.0001, –20, 5);

Vec2 i2 = Intersection(distX1, z1, distX2, z2,

0.0001, 0.0001, 20, 5);

if (z1 <= 0)

if (i1.y > 0)

{

distX1 = i1.x;

z1 = i1.y;

}

else

{

distX1 = i2.x;

z1 = i2.y;

}

if (z2 <= 0)

if (i1.y > 0)

{

distX2 = i1.x;

z2 = i1.y;

}

else

{

distX2 = i2.x;

z2 = i2.y;

}

else

{

continue;

}

float widthRatio = screenW / 2;

float heightRatio = (screenW * screenH) / 60.0;

float centerScreenH = screenH / 2;

float centerScreenW = screenW / 2;

I left fragments from the code before and after the code snippet we need to add, and grayed them out so you can get a better idea of where exactly to put the clipping code.

Now, if you compile and run the project, you should see something like this:

Now we see a proper wireframe view of the level and its walls.

However, not everything is good enough. We have some performance-critical stuff to implement. At this point, we see both the front and back faces of the walls. We don’t need that. Performance is very critical in computer graphics, and we need to keep it relatively high. We will need it, especially when we start rasterizing.

There is a technique called back-face culling. It performs a check if a polygon’s face is pointing towards the camera or it’s the back of it. When working with 3D models and apply this technique, those faces at the back of the objects will be ignored, and only those at the front will be rendered. This improves the performance and avoids overdrawing.

To implement back-face culling, just add the following function before your main():

int IsFrontFace(Vec2 Camera, Vec2 pointA, Vec2 pointB)

{

const int RIGHT = 1, LEFT = –1, ZERO = 0;

pointA.x -= Camera.x;

pointA.y -= Camera.y;

pointB.x -= Camera.x;

pointB.y -= Camera.y;

int cross_product = pointA.x * pointB.y – pointA.y * pointB.x;

if (cross_product > 0)

return RIGHT;

if (cross_product < 0)

return LEFT;

return ZERO;

}

It performs yet another cross product computation that checks if a particular line segment is at the front or back of the object we are watching at, based on the camera position and angle.

Now add the following lines right after the line we initialize our points and polygon height in the second nested loop in our rendering routine:

for (int i = 0; i < polys[polyIdx].vertCnt – 1; i++)

{

Vec2 p1 = polys[polyIdx].vert[i];

Vec2 p2 = polys[polyIdx].vert[i + 1];

float height = -polys[polyIdx].height;

if (IsFrontFace(cam.camPos , p1, p2) > 0)

continue;

float distX1 = p1.x – cam.camPos.x;

float distY1 = p1.y – cam.camPos.y;

float z1 = distX1 * cos(cam.camAngle) +

distY1 * sin(cam.camAngle);

Again I grayed out the code between which you have to put the new lines.
Now what you see should be back-face culled:

Now we need movement mechanics.
Add two new definitions at the top of your main.c:

#define MOV_SPEED 100

#define ROT_SPEED 3

Those will be our movement and rotation speeds.
Now add a new function called CameraTranslate():

void CameraTranslate(double deltaTime)

{

const Uint8* keyState = SDL_GetKeyboardState(NULL);

if (keyState[SDL_SCANCODE_W])

{

cam.camPos.x += MOV_SPEED * cos(cam.camAngle) * deltaTime;

cam.camPos.y += MOV_SPEED * sin(cam.camAngle) * deltaTime;

}

else if (keyState[SDL_SCANCODE_S])

{

cam.camPos.x -= MOV_SPEED * cos(cam.camAngle) * deltaTime;

cam.camPos.y -= MOV_SPEED * sin(cam.camAngle) * deltaTime;

}

if (keyState[SDL_SCANCODE_A])

{

cam.camAngle -= ROT_SPEED * deltaTime;

}

else if (keyState[SDL_SCANCODE_D])

{

cam.camAngle += ROT_SPEED * deltaTime;

}

In computer graphics, a movement of any point in space is called translation. Therefore CameraTranslate(). The movement is performed by simply translating the position of our camera and changing its angle in the world.
Before we continue, we need to introduce one more thing to our engine – the Delta Time.

Delta time is the time passed since the last Game Loop cycle. We will use that time to make everything run at a consistent speed.

Also, when we render a frame, the previous one will still be in the renderer’s buffer, therefore the new one will be drawn on top of it. The frames will stack on top of each other, causing a mess on the screen. To fix that, we will need to clear the buffer of the renderer each time before rendering the new frame. There are better ways to do that than flushing the buffer each time a new frame is going to be rendered but we will stick with this one in this tutorial.

Let’s update the game loop to do just that – introduce the delta time and clear the screen before rendering each frame.

Add this code to your game loop:

int loop = 1;

SDL_Event event;

double deltaTime;

while (loop)

{

double start = SDL_GetTicks();

SDL_SetRenderDrawColor(renderer, 0, 0, 0, 0);

SDL_RenderClear(renderer);

SDL_PollEvent(&event);

if (ShouldQuit(event))

break;

CameraTranslate(deltaTime);

Render();

UpdateScreen();

double end = SDL_GetTicks();

deltaTime = (end – start) / 1000.0;

}

We also added a call to the CameraTranslate(), passing the deltaTime to it as an argument.

We will multiply every movement increment to the delta time so it can run at a consistent speed, no matter how long the last frame took to render. Consistent speed means that no matter how low or high your frame rate may go – the amount of displacement during movement will be always consistent. It will be relative to the speed the frames are generated and rendered.

SDL_GetTicks() gets the time in milliseconds since SDL2 has been initialized.

We do this twice, at the beginning and the end of the loop. Then we subtract the latter from the first value and receive the time passed during the current loop cycle. We divide that by 1000.0 milliseconds (1 second) to convert our Delta Time to seconds.

If you compile and run the project now, you will have a consistent translation while moving around the level. This does not means consistent frame rate.

It might be quite slow due to the DDA rendering algorithm. If you replace it with the SDL2’s line drawing algorithm, it will jump in performance. I just had to explain the DDA for education purposes.

Rasterization

To make walls appear solid, we must fill them with color. This process is called rasterization. We will implement a scanline rasterizer that will fill the pixels inside each screen-space polygon (wall face) line by line, starting from the top and going to the bottom. Each line will be drawn by putting a pixel at a particular position and interpolating the next one’s X coordinate until the line reaches the edge of the polygon. Then we move to the next row until we fill up the whole polygon. Essentially performing a scanning of the screen, line by line, starting from the top of it and going to the bottom, putting pixels only when they are inside a wall face.

In the beginning, we defined an array called ScreenSpacePoly in our typedefs.h file. We will use it to track which polygons are currently visible to the camera and rasterize only them. Rasterization is slow; we have to do only the minimum computation required whenever possible.

Introduce a few new defs in our main.c:

#define SHOULD_RASTERIZE 1

//decrease for better resolution; increase for performance

#define RASTER_RESOLUTION 4

#define RASTER_NUM_VERTS 4

The first one will act as a flag – to rasterize or not – so we can quickly turn it off or on. The RASTER_RESOLUTION is the resolution we want to use while rasterizing. Or, in other words, the step between the rows of lines. The value of 4 will cause it to draw a line at each 4^th row. The gaps between pixels can be filled up via linear interpolation (also called learp). The bigger the step, the bigger the gaps but also faster rasterization.

RASTER_NUM_VERTS defines the number of vertices the polygon that we rasterize will have. Since it’s a simple plane that acts as a vertical wall, it will have just four (top-left, top-right, bottom-left, and bottom-right).

Add two new global variables:

int screenSpaceVisiblePlanes;

ScreenSpacePoly screenSpacePolys[MAX_POLYS][MAX_VERTS];

The first one will keep track of the number of visible screen-space polygons (walls) in the current frame. The second one will hold the information about those polygons and their vertices so we can traverse them and rasterize them.

Before we start rasterizing, we need to find a way to determine which pixels are inside a given polygon so we can rasterize only the space inside the polygon. We will do that by checking if a point is inside a polygon. If so – we draw pixel.

There is a fairly simple method to do that when you work with convex polygons.

We take the coordinates of the point and draw an infinite (actually just very long) line to one of the edges of the polygon. If the line does not intersects the polygon or it intersects it twice it means the point is outside the polygon. If the line intersects the polygon just once it means it’s inside the polygon.

I can explain that better by illustrating it:

In the image above, you can see that points A and E have no intersections with any of the polygon edges. Points B and D have one intersection – therefore, they live inside the polygon. Point C has two intersections with the polygon, so it’s outside of it.

Let’s implement this algorithm with code.

Put the following function somewhere above the Render() function:

//nvert = vertices count

//vertx = all x vertices coordinates

//verty = all y vertices coordinates

//testx & testy = point to test if inside the polygon

int PointInPoly(int nvert, float *vertx, float *verty, float testx, float testy)

{

int i, j, isPointInside = 0;

for (i = 0, j = nvert–1; i < nvert; j = i++)

{

int isSameCoordinates = 0;

if ((verty[i]>testy) == (verty[j]>testy))

isSameCoordinates = 1;

if (isSameCoordinates == 0 &&

(testx < (vertx[j]-vertx[i]) * (testy–verty[i]) /

(verty[j]-verty[i]) + vertx[i]))

{

isPointInside = !isPointInside;

}

return isPointInside;

}

The function uses a flag isPointInside which flips every time an intersection occurs. In the beginning, it’s zero. If an intersection is detected it flips to 1. If another intersection occurs it flips back to 0. And so on until it exhausts the edges of the polygon.

Next, we need something to flush our screen-space polygons buffer every frame.

Put the following function below the PointInPoly one:

void ClearRasterBuffer()

{

for (int polyIdx = 0; polyIdx < MAX_POLYS; polyIdx++)

{

for (int i = 0; i < polys[polyIdx].vertCnt; i++)

{

for (int vn = 0; vn < RASTER_NUM_VERTS; vn++)

{

screenSpacePolys[polyIdx][i].vert[vn].x = 0;

screenSpacePolys[polyIdx][i].vert[vn].y = 0;

}

We simply traverse the buffer’s indexes and set them to 0 so the rasterizer will not process them.
Now let’s implement our rasterizer function. Put it just below the ClearRasterBuffer():

void Rasterize()

{

float vx[4];

float vy[4];

//the Pixel Buffer restricts draw calls

//at same pixel screen coordinate to 1, so no redraws

Uint8 pixelBuff[screenH][screenW];

memset(pixelBuff, 0, sizeof(pixelBuff));

for (int polyIdx = screenSpaceVisiblePlanes-1; polyIdx >= 0; polyIdx–)

{

for (int nextv = 0; nextv < RASTER_NUM_VERTS; nextv++)

{

int planeId = screenSpacePolys[polyIdx]->planeIdInPoly;

vx[nextv] = screenSpacePolys[polyIdx][planeId].vert[nextv].x;

vy[nextv] = screenSpacePolys[polyIdx][planeId].vert[nextv].y;

}

for (int y = 0; y < screenH; y += RASTER_RESOLUTION)

{

for (int x = 0; x < screenW; x += 1)

{

if (pixelBuff[y][x] == 1)

continue;

if (PointInPoly(RASTER_NUM_VERTS, vx, vy, x, y) == 1)

{

// for (int learp = 0; learp < RASTER_RESOLUTION; learp++)

// PutPixel(x, y + learp, 100, 255, 0);

PutPixel(x, y, 100, 255, 0);

pixelBuff[y][x] = 1;

}

What it does is to traverse the screen-space polygons registered as visible (later in our code we will do the registration) and starts traversing each polygon vertices to check if the current pixel of the screen is inside this polygon with our PointInPoly function above. There is a huge amount of optimization that could be done here. I will not focus on that though. Whenever it detects a pixel inside a polygon it colorizes it in green (RGB: 100, 255, 0).

Inside the IF statement where the PointInPoly is, I left a small loop of code commented. It interpolates the Y coordinate of the rasterizer and fills the gap caused by the RASTER_RESOLUTION. It will be slower so keep that in mind. To use it just comment the PutPixel function and uncomment the FOR loop.

We also have a buffer called pixelBuff which keeps the information about which pixels on the screen have already been colorized in order to avoid overdraw (or drawing the same pixel more than once) and therefore improve performance.

Make the following updates at the top of the Render() function.
Put the code to clear the rasterizer buffer and reset the number of registered visible polygons:

void Render()

{

if (SHOULD_RASTERIZE == 1)

{

ClearRasterBuffer();

screenSpaceVisiblePlanes = 0;

}

for (int polyIdx = 0; polyIdx < MAX_POLYS; polyIdx++)

{

After the code that draws the wireframe of the walls, add the following block of code:

DrawLine(centerScreenW + x1, centerScreenH + y1a,

centerScreenW + x2, centerScreenH + y2a);

DrawLine(centerScreenW + x1, centerScreenH + y1b,

centerScreenW + x2, centerScreenH + y2b);

DrawLine(centerScreenW + x1, centerScreenH + y1a,

centerScreenW + x1, centerScreenH + y1b);

DrawLine(centerScreenW + x2, centerScreenH + y2a,

centerScreenW + x2, centerScreenH + y2b);

//fill the rasterization buffer

if (SHOULD_RASTERIZE == 1)

{

int planeIdx = screenSpaceVisiblePlanes;

screenSpacePolys[planeIdx][i].vert[0].x = centerScreenW + x2;

screenSpacePolys[planeIdx][i].vert[0].y = centerScreenH + y2a;

screenSpacePolys[planeIdx][i].vert[1].x = centerScreenW + x1;

screenSpacePolys[planeIdx][i].vert[1].y = centerScreenH + y1a;

screenSpacePolys[planeIdx][i].vert[2].x = centerScreenW + x1;

screenSpacePolys[planeIdx][i].vert[2].y = centerScreenH + y1b;

screenSpacePolys[planeIdx][i].vert[3].x = centerScreenW + x2;

screenSpacePolys[planeIdx][i].vert[3].y = centerScreenH + y2b;

screenSpacePolys[planeIdx]->planeIdInPoly = i;

screenSpaceVisiblePlanes++;

}

It basically registers each visible polygon, saves its vertices positions, and increments the visible polygons counter (screenspaceVisiblePlanes).

And finally, outside all the FOR loops, at the very end of the Render() function (just before its closing bracket }), put the following code to call the rasterizer when you finish traversing the level data:

if (SHOULD_RASTERIZE == 1)

Rasterize();

Now compile and run the project. What you will see is that all walls are now rasterized.

As you can see each green line is drawn 4 pixels below the one above it, therefore, we have black gaps between them. If you set the rasterizer resolution to 1 – it will become solid but very slow. This is a technique the old arcade machines used back in the day.

What you will notice is that everything now is very slow. That’s the cost of coding a rasterizer that works on a relatively high-resolution pixel by pixel. 800×600 is way too much for this kind of line drawing algorithm that calls a 3^rd party library’s drawing function to put pixels on the screen.

If you replace the method that we use to put pixels on the screen and make it draw lines (see SDL_RenderDrawLine()), you will get way better performance. However, I had to explain how it usually works on a lower level to those new to computer graphics since this tutorial has educational purposes in the first place.

One thing we can do is to use SDL2’s logical resolution feature. We will turn down the rendering resolution from 800×600 to half: 400×300. And set the logical resolution to 800×600.

Update the two defines at the top:

#define screenW 400

#define screenH 300

Now in your main(), where we initialize the window and the rendering context, update the code as follows:

SDL_Window* mainWin = SDL_CreateWindow(

“3D Poly Renderer”,

SDL_WINDOWPOS_CENTERED,

800, 600,

SDL_WINDOW_SHOWN);

renderer = SDL_CreateRenderer(mainWin, 0, SDL_RENDERER_SOFTWARE);

SDL_RenderSetLogicalSize(renderer, screenW, screenH);

We hardcoded the window resolution to 800×600 and set the logical resolution via the SDL2’s SDLRenderSetLogicalSize() API. Now the performance should be considerably better.

We can now also afford to set the Rasterizer resolution to 1 (no gaps), at the top where the definitions are:

#define RASTER_RESOLUTION 1

The picture so far is very flat. There is no visual depth due to the lack of shades of the color we use. Let’s fix that. Let’s implement a flat shading based on the world-space distance of the polygons to the camera. The flat shading is the process of computing the shade of the color based on certain criteria (distance in our case) and utilize it to colorize the whole face of the surface. It works reasonably well for objects with flat faces like our walls. You can search for Gouraud and Phong shading for more advanced techniques.

Define new structure called Color in typedefs.h:

typedef struct

{

Uint8 R, G, B;

} Color;

Implement the following function above the Rasterize() function:

Color GetColorByDistance(float dist)

{

float pixelShader = (0x55 / dist);

if (pixelShader > 1) pixelShader = 1.0;

else if (pixelShader < 0) pixelShader = 0.1;

Color clr;

clr.R = 0x00;

clr.G = 0xFF * pixelShader;

clr.B = 0x00;

return clr;

}

This will generate a color based on the distance of the given wall to the camera.

In our ScreenSpacePoly structure, we have a field called “distFromCamera” we will save the distance from the wall to the camera there so we can use it to generate the appropriate color when rasterizing.

Update the loop where you fill up your screen space polygons buffer in your Render() function as follows: