Scanline rendering

[Carina]

There should be a gazillion resources on this about.. It's one of the most basic rendering techniques about, and any good introductory graphics book should cover it.

[badsectoracula]

Looking the sources won't teach you much actually :-).

A very simple description of how the scanline rasterization of a triangle works is this: imagine you have a triangle with its vertices sorted like this:

A
oo
o o
o o
o o
B o
o o
o o
o o
o o
o o
oo
C


What you notice from such a triangle (except that its made by o's :-P) is that it is actually made of three lines: A to B, B to C and A to C. I'm saying A to C for the last one because its an important property of a common method for rasterizing (drawing) triangles: the lines go from up to down. But i'm going ahead. Anyway.

Now if all you wanted to draw was the triangle's outline then all you need to do is draw the lines i mentioned. However this isn't what you want to do, usually :-). What you need is to fill the triangle. Back when i was starting with programming my first thought was to use some sort of flood fill, but really that the slowest thing one can think, so don't :-P. The real solution is much much simpler: take a note at the o's there. You'll notice that there are at most two o's in each line (assume that the ABC letter don't exist and are actually o's). So basically each line is made of two o's which represent the leftmost and rightmost position of the triangle. Think these as the leftmost and rightmost pixels - the edges of the scanline which give the name to the algorithm :-). So all you need to do is to fill them. Here is the triangle with dashes added where you should fill:

A
oo
o-o
o--o
o---o
B-----o
o----o
o---o
o--o
o--o
o-o
oo
C


As you can imagine (i used dashes to help your imagination) once you know where each pair of o's is placed, you can draw a line between them. Since the y is always the same all you have to do is very simple. Here is pseydocode:

for x from x1 to x2:
plot_pixel x, y

So simple. Ok, now to the hard part: figuring out where the lines are! There are many methods to find the points of a line, but the two most common are the Brensenham's algorithm and using plain slope-based line math. I'm going to do the second since the first one is a little more involved and the only benefit is speed, something which you shouldn't care about when you're learning stuff (remember: make it work first, make it fast later). The idea is to calculate the slope (or 'how much it changes') of a pair of values of the same thing when used with a different pair of values of the same thing. This is done like:

slope = (Bx-Ax)/(By-Ay)

(thats basically some form of the line formula)

Now in words the above means: break the change from Ax to Bx in the steps required for the change from Ay to By when the latter change is always 1. So when you have a value y which begins from Ay, ends in By and you always change the values in steps of 1 (that is you always add or subtract 1 to y), then you can use the 'slope' to see how much you need to change another value x that begins from Ax and ends in Bx (that is how much you need to add or subtract from x). Why is this needed? Simple because if you see the lines in the triangle above they're pixels which always change in the vertical direction by one (the next pixel is always below the previous) but not in horizontal direction (the next pixel can be at the same horizontal - x - position as the previous). So their 'change' is not always one. However since you know the beginning (Ax and Ay) and ending (Bx and By) values and you know that y (the vertical coordinate) is always changed by one, you can use the above formula to figure out how much you need to change the x value everytime you change y.

So to put this in pseudocode:

slope = (Bx-Ax)/(By-Ay)
x = Ax
for y from Ay to By:
store the edge position x for scanline y
x = x + slope


This calculates the x positions in each scanline for the line that begins from Ax,Ay ('A') and ends in Bx,By ('B'). Doing the same for lines BC and AC will provide you with the positions that are needed to draw the triangle. However notice something: each scanline has the two positions! One to start from and one to end to (the two o's for each line in the "images" above :-P). Soo which position is for which? Well, if you take a look at the triangle's edges you'll notice that the long edge is always at one side (in your example is at the right side but it can be at the left) and the smaller edges are at the other side together. So what you need to is to use two variables for each scanline and store the x position of the long line in one variable and the x position of the the other sides in the other variable. So if you use Pos1 and Pos2 in each scanline, the x position of edges AB and BC will be stored in Pos1 and the x position of edges AC will be stored in Pos2.

Now all you have to do once you have these positions is to use the first code snipped above in order to draw them like

for y from Ay to Cy:
set x1 to scanline[y].Pos1
set x2 to scanline[y].Pos2
for x from x1 to x2:
plot_pixe x, y


Now this was a very very simple explanation and only for plain colored triangles. However having these working is the most important step. Adding texture mapping is only a matter of interpolating (this is what 'finding out the x value' above is actually called) the texture coordinates for each vertex in the Y loop and storing them in the scanline.

This document has a nice description of the methods used (http://tfpsly.free.fr/Docs/3dIca/3dica.htm) and contain a lot more than the triangle rasterization part (and includes tutorials on adding texture mapping, perspective correct texture mapping, gouraud shading, and other stuff). Also the articles of Chris Hecker are considered some of the best on the topic (search Chris Hecker texture mapping on google). While working at id, Michael Abrash also wrote some series of articles about the development of Quake's engine although they're mostly random thoughts than tutorials. They might give you some ideas though :-)

[sundialsvc4]

I finally grokked "slope," back in high school, when I was told: "slope equals rise over (divided-by...) run."

A purely vertical line has "no slope" because it would constitute division-by-zero.

[badsectoracula]

I gave the generic idea behind it. Checking for division by zero is the details which i don't believe i have to write about :-)

Btw in the above rasterizer's case a totally vertical line won't be a problem since the division is done by (By-Ay). A totally horizontal line however... :-)

[Galo]

wow man thanks for the effort, very good explenation, im onto that one t'night thanks again

[CGTalk Moderation]

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.