The Rasterization Algorithm

I recently got it into my head to make a software renderer. No particular reason, just for the love of an interesting programming challenge, and as a way to keep my programming skills sharp in advance of my VFS course starting in January. Anyway, the very first step of rendering things is to rasterize the points of the triangle onto the screen.

Backing up a second, an overview of computer graphics is required here. A good overview of 3D graphics from Wikipedia

Anyway, I was starting at the very beginning, which is to render a triangle. I suppose the very beginning is just getting a working framebuffer up and running in Windows, but that’s tedious. I had no idea how to actually write the rasterization algorithm, so I decided to create my own.

What we want to do is to create a triangle such as this one: 

The rasterization stage is the very last stage, where we have already “mapped” the triangle to the screen, so we know where the triangle’s points are on the screen. If you don’t understand this, just think in a real 3D environment we might be looking at the triangle at an angle (well almost certainly we will be), and we want to “snap” or mathematically transform the triangle from it’s place in the world, to it’s place relative to where the camera is. Rasterization assumes we have already done so, I just needed to create an algorithm that took the three points of a triangle and rendered all the pixels inside of them.

My idea was that we can make three lines from the triangle, such as this:

Apologies for the poorly cropped image.

For each line, if we extend it to the edge of the screen, the pixel will either be on the right or wrong side of the line. We know which side is the right side, because it’s the side that the third vertice (point) is on. Just follow one line and “look” towards the third point for the correct side. The math for actually figuring this out is somewhat hard to explain, and very messy in (my) code, but fundamentally what I’m doing is this:
1) Find the angle of the pixel to the nearest point in the line. This can only be one of two angles, but floating point errors creep in.
2) If the angle matches the angle from the third vertice to the line, then the pixel is on the correct side of the line.

If we do this for all 3 lines, then if the pixel is on the correct side of all the lines, the pixel is inside of the triangle.

Unfortunately this is tediously slow. I probably could optimize my poor code here, but the algorithm itself is just fundamentally worse than the alternative.

To be continued…

This entry was posted in software renderer and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s