The code for this one is part of a project I’m working on for university so I’m not going to release it just yet, but feel free to email me.

My original 3D renderer used a naive scanline algorithm to rasterise triangles and was pretty slow. Since there was a class coming up where we’d be designing a 3D renderer as part of the final project, I decided to try and make my new renderer as fast as possible. I started up the profiling tools in Visual Studio and immediately noticed that an insane percentage of my total execution time was in one particular method.

That’s nuts. If there was any place to optimise, that would be it. I started researching alternate methods of rasterising triangles. I eventually settled on using half-space equations to determine the area of the triangle, as this method can be computed incrementally and seemed to have a lot of potential for optimisation. Originally I was going to go over the actual rasterisation of the triangles, but since most of what I wrote were techniques I learnt from Nicolas Capen’s article on Advanced Rasterisation (update: link fixed), I’m instead going to recommend that you read his excellent topic yourself.

Interpolation

In order to interpolate values across a triangle linearly, I found that it was easiest to imagine the triangle as three points on a plane with dimensions x, y, and w, the third dimension being our interpolant (I specifically called this w instead of z as it can be any interpolant – colour, z-coordinate, texture coordinates.) I also tried barycentric coordinates, but when working through the mathematics using the plane equation, I realised that they were more or less the same thing.

The Plane Equation

This site gives a brief overview of the plane equation and its various magical constants. Basically, a plane is defined by the following equation with A, B, C, anD D as constants:

Ax + By + Cz + D = 0

We can calculate these constants from three points on a plane, using the following expressions (from the link above):


A = y1 (z2 - z3) + y2 (z3 - z1) + y3 (z1 - z2)
B = z1 (x2 - x3) + z2 (x3 - x1) + z3 (x1 - x2)
C = x1 (y2 - y3) + x2 (y3 - y1) + x3 (y1 - y2)
- D = x1 (y2 z3 - y3 z2) + x2 (y3 z1 - y1 z3) + x3 (y1 z2 - y2 z1)


How convenient! The triangles we’re trying to draw are defined by three points, and although they’re not necessarily in 3D space, z can be any (and any number of) dimensions common to all three points. Notice that C, since its expression contains only X and Y, is common to all interpolants. For example, if we want to interpolate the red component of the colour of each point:


#include <pseudocode>

float x1, y1, r1; // The x, y, and r values of the first vertex
float x2, y2, r2;
float x3, y3, r3;

float A = y1 * (r2 – r3) + y2 * (r3 – r1) + y3 * (r1 – r2);
float B = r1 * (x2 – x3) + r2 * (x3 – x1) + r3 * (x1 – x2);
float C = x1 * (y2 – y3) + x2 * (y3 – y1) + x3 * (y1 – y2);
float D = -(x1 * (y2 * r3 – y3 * r2) + x2 * (y3 * r1 – y1 * r3) + x3 * (y1 * r2 – y2 * r1));

Now we have the four constants from our original plane equation, we can rearrange it to calculate the value of r at any position.


Ax + By + Cr + D = 0
Cr = -Ax - By - D
r = - (Ax + By + D) / C


And using this, we can colour our triangle pretty colours:


#include <pseudocode>

float x; // current x
float y; // current y

// In inner loop
float r = – (A * x + B * y + D) / C;
((char*)&colourBuffer)[0] = r;

 

 

 

 

 

 

 

 

 

 

Since it would be messy doing this for each component, I made a colour class with three floating point components (R, G, B), and added overloads for the arithmetic operators that add the components together (r += other.r; etc) so I could do operations between two Colours or a Colour and a float. C is still going to be a floating point value because its only components are x and y.


#include <pseudocode>

Colour c1;
Colour c2;
Colour c3;

Colour A = y1 * (c2 – c3) + y2 * (c3 – c1) + y3 * (c1 – c2);
Colour B = c1 * (x2 – x3) + c2 * (x3 – x1) + c3 * (x1 – x2);
float C = x1 * (y2 – y3) + x2 * (y3 – y1) + x3 * (y1 – y2);
Colour D = -(x1 * (y2 * c3 – y3 * c2) + x2 * (y3 * c1 – y1 * c3) + x3 * (y1 * c2 – y2 * c1));

for (y = ymin; y < ymax; y++)
{
for (x = xmin; x < xmax; x++)
{
Colour col = (A * -x + B * -y – D) / C;
}
}

((char*)&colourBuffer)[0] = (char)col.r;
((char*)&colourBuffer)[1] = (char)col.g;
((char*)&colourBuffer)[2] = (char)col.b;

Although this works, it isn’t optimal. We’re still doing those *, / and – operations in the middle of the loop, and each one is at least three floating point operations. If you look at the line in the middle of the loop, you can see that the initial value of col would be (A * -xmin + B * -ymin -D) / C. From there, you should also be able to see that as the value of x increases by 1, the value of col increases by -A/C, and as the value of y increases, the value of col increases by -B/C.

We can take these constants out of the loop, and then just calculate the colour incrementally, reducing the logic in the inner loop to simple addition.


#include <pseudocode>

Colour initialCol = (A * -xmin + B * -ymin -D) / C;
Colour dx = -A / C;
Colour dy = -B / C;

for (int y = miny; y < maxy; y++)
{
Colour tempColour = initialCol;

for (int x = minx; x < maxx; y++)
{
// Cast float values from tempColour to chars and put them into the colour buffer here

tempColour += dx;
}

initialColour += dy;
}

This works, but isn’t as fast as it could be. I found that casting the colour components from floats was really slow, and that it was faster to convert them to int with the x86 instruction fistp. There’s also an SSE2 instruction that can convert four floats into four chars in a single instruction, but I’ll leave that until next time.

Update: by enabling SSE optimisation in Visual Studio, I found a large increase in speed for those floating point operations

The full code for my software renderer can be found on GitHub and my Rasteriser class can be found here