## The Rasterization Algorithm – part 2 Scanline

So it turns out that there’s a much better rasterization algorithm. After being appalled at how slow my algorithm was (okay it’s not that slow, but it’s pretty much unworkable), I researched better algorithms on the internet. Turns out, the way modern GPU’s do their rasterization is with the Scanline Rasterization Algorithm. Basically what this does is go line by line through the triangle, figure out the leftmost and rightmost points that are within the triangle, and then renders them and all the pixels in between. This is pretty great because it means that for every line that the polygon operates on, we really only have to do two calculations. However, before we can do that, we need to rearrange our triangle first.

The real genius behind this, is that rasterization is dead simple for aligned rectangles. We just figure out four points and render everything in between. It’s also pretty easy for triangle that have a horizontal axis. Luckily, we can turn every triangle into one with a horizontal axis, or rather, two triangles that both have horizontal axis. Visually what we do is take this triangle:

And turn it into these triangles:

We don’t actually colour them differently. This is purely for illustrative purposes.

At this point, it’s trivially easy to find out the minimum x value for each line, and the maximum x value for each line, and render everything in between. I don’t have any way of getting specific framerate measurements, but what I can do is render something in the background, to measure the difference between the two algorithms.

I put a random pattern that scrolls up the page. There is no framerate limiter, so the faster the background scrolls, the faster each frame must be getting executed. Admittedly eyballing it, but it looks like the program is running at more than an order of magnitude faster, and the code behind it is shorter and simpler to boot.

UPDATE:

I ran Visual Studio’s performance profiler on the code. I just rendered the polygon both ways, and it turns out that the RenderPolygon function takes 926ms of CPU time (over the entire program running time), but the RenderPolygonFast takes a grand total of 28ms of CPU time. It’s not just 10x faster, it’s actually 33x faster. Actually, the function I have that just renders the squares in the background actually takes about 10x longer to execute then rendering this polygon, which is very slightly worrying for the future, as the CPU seems to be fairly slow at simply putting pixels on the screen.

## 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…

## Blitting part 4

After an absurd amount of extremely frustrating exceptions and bugs, I’ve finally gotten software blitting working perfectly (I hope) on my chess project. As of right now every time I run the program it creates a png for me to use. The images can be of arbitrary size, and can blit to an arbitrary part of the other image. Anyway, here’s one of the PNG’s:

Notice, no borders.

There’s no doubt that it looks quite janky. Since I’m using a sub-optimal (from a perfect image quality POV), nearest-pixel algorithm, I decided to pre-downscale my images. I was lazy, and instead of creating a small program to do this for me, I instead just resized the images in Microsoft Paint, which ruined all my alpha values (transparency). As a result, to get this image I set pure white to transparent (similar to green-screening), and we have what you see before you.

Nevertheless I’m quite proud of myself, mostly on the programming side, since these images can easily be replaced with higher quality images.

## Software Blitting Part 3

If we have a typical PNG of size, say, 100×100, then we can easily refer to a specific pixel as 44, 02, if we want the forty fourth pixel from the right, on the second line. Unfortunately it’s not quite that simple, since the raw pixel data is linear, so pixel 44,02, is actually just pixel #244. A visual representation might make this easier.

Imagine a very simple image consisting of four pixels:

Of course, I have added the black lines.

The way this image is stored in memory is like this:

So if we want to access the pink pixel, we can’t simply go for the pixel at 2, 2, we need to specify the #4 pixel. All this seems quite simple, but it makes blitting one image to another a bit harder.

## Software Blitting part 2

Computer graphics are made up of pixels, and pixels are made up of colour channels, specifically Red, Green, and Blue (and Alpha, but we’re not worried about that). You combine all three of those channels to form the colour that you want. As it turns out, if you have a gradation of 0-255 for each of these channels, you can create colours of small enough granularity that the human eye cannot tell the difference between the two most like each other. Since it takes a computer 8 bytes to store 256 values, and we need one byte for each colour channel, we have each of our pixels requiring 24 bits of information, giving us 24 bit colour, giving us over 16.7 million colours.

But we have a bit of a problem. Raw pixel data can be quite large. Consider this, and image at 1920×1080, or 1080p, contains 1920*1080 pixels, or over 2 million pixels. If each pixel takes 3 bytes of information, that image takes 47.46 MB’s of space on the user’s hard drive. And yet, if you find an image of this size on your hard drive odds are that it does not take up anywhere near that amount of space. This is due to compression. There are many types of compression algorithms (such as JPEG, DXT, PNG, GIFF, etc), and therefore formats, but I was dealing simply with PNG. What compression does is take the raw image data, and reduce the data required to store that image. You then need a program to read the PNG (or other format) image file, and decompress the file.

## Software Blitting Part 1

About a week ago my trusty Microsoft Ergonomic Keyboard broke, and I was forced to use my laptops native keyboard. I somehow managed to be productive during this time, but today my new keyboard came in the mail. So I decided to take it out for a spin, and get to work on a problem that’s starting to irritate me to no end.

My workflow to create the pictures that you see here consists of the following:
1) Run Program
2) Hit ‘Print Screen’ key
3) Open Microsoft Paint
4) CTRL+V the entire screen into Paint
5) Crop out everything but the running window.
6) Upload PNG to WordPress

Uncropped image.

Posted in Programming | Tagged , | Leave a comment

## Chess 3030

As a brief refresher, the entire purpose of Chess 60 was to reduce the benefit of opening preparation to effectively zero. Top level players, and frankly even >2000 ELO players (fairly highly rated) have played so many games and remembered so many openings, that the game begins much later than move one. For the best players in the world, it begins much, much later than move one. Since that’s not particularly fun to me, I created a version that would hit the sweet spot between Fischer Random Chess, (chess 960) and classical chess. Unfortunately, as it turn out, Chess 60 is really Chess 30, which leaves me with two problems. The first being that Chess 60 is a stupid name, which can easily be solved by calling it something else, like Chess 30.

More seriously, my concern is that, with only thirty starting positions it leaves the door quite open to players memorizing openings again. They may not memorize openings for all thirty positions, but there is a clear advantage to memorizing openings for a few positions, and hoping that you get to play those positions in tournament. Even with the original sixty positions there was a small part of that, and it makes for a very unfortunate meta-game, where the outcome of a game is determined in large part due to luck, if one of the players prepared for the position more than the other did.

My solution to this is probably going to be much more controversial than my original proposal, but frankly I feel it is much more exciting.

Posted in Chess, Chess 900, Game Design | Tagged , | Leave a comment