How can I rasterize 3D triangles in software?

Question

I am creating a 3D software renderer, and I have a wire frame cube rendering. Now I am working on solid color rendering and I am wondering what an efficient algorithm for shading the contents of the triangles would be?

Answer 1

Let's call the vertices of a single triangle v1, v2, v3, and the colours of those vertices c1, c2, c3.

The general start to filling in your polygons is as follows:

1. iterate over every pixel of your screen
2. for every x/y coordinate calculate the barycentric coordinates b1, b2, b3 with respect to the triangle you are trying to draw. You can find formulas on how to calculate these on the wikipedia page: https://en.wikipedia.org/wiki/Barycentric_coordinate_system

(If you want you can derive these formulas yourself, it's good practice and not that hard.)

The thing about barycentric coordinates is that whenever all of the coordinates are between 0 and 1, the x/y point that corresponds with it lies in the triangle. Whenever some of the barycentric coordinates are 1 or 0, and the others are between 0 and 1, the x/y point lies on the edge or corner of the triangle.

3. So now you simply check if the barycentric coordinates are between 0 and 1 inclusive, and if they are you draw a pixel there. If you want colour then you simply multiply b1 * c1 + b2 * c2 + b3 * c3, which will result in a Gouraud shaded triangle interpolation.

=========================================================================

There are many optimisations to be made to this algorithm, as well as some problems to be solved. I'll briefly describe the problems and solutions here:

Edge pixels:

If two triangles are drawn on each other, to which triangle does the edge between them belong?

You need a homogeneous way to solve this for all triangles. A solution would be to pick an off-screen point and assign the edge to the triangle that is closest to the off-screen point.

Incremental calculation:

The barycentric coordinates currently are being calculated freshly every new iteration, this is slow. We really want to do this incrementally, so we take every calculation out of the loop that we can, and we calculate the delta changes in the barycentric coordinates. We then add those to the starting coordinates every iteration to get the final barycentric coordinates.

Early return:

If we step through the whole screen and while iterating a row we find a section of triangle.
X
0 - 472 = no triangle
472 - 582 = triangle
582 - 640 = no triangle

Then after we found the triangle we know there is not going to be anything after that in the same row, so we simply go to the next row.

X
0 - 472 = no triangle
472 - 582 = triangle... STOP

End notes By now you should be getting well over a 100,000 triangles drawn per second on a modern computer. There are multiple different ways to determine in which order to draw these triangles. The easiest is the painters algorithm where you simply draw them from back to front. A z-buffer is another option you can employ.