Today's lecture is about an algorithm for drawing lines with these "pixels". The colour doesn't matter for the algorithm; we'll draw a line in black on a white background today; the algorithm gives us the series of coordinates for the pixels.
How do we refer to these pixels? We use 'x' and 'y' coordinates, like on a graph in mathematics. The horizontal direction is 'x' and the vertical direction is 'y'. However, unlike in the usual scheme in mathematics, we will have the coordinate (0,0) in the top-left corner. In mathematics we write coordinates just like that, in parentheses: the x coordinate, a comma, and the y coordinate.
So the coordinate (0,0) is the top-left corner; the coordinate (1,0) is one pixel to the right of the top-left corner; and the coordinate (0,1) is one pixel below the top-left corner.
Suppose we want to draw a line from coordinate (1,1) to coordinate (8,5). This is how the mathematically-perfect line goes:
But we can't draw it that finely. We only have these pixels. The smaller each pixel is, the better-looking a line we can draw, but sooner or later, if you look closely enough, you'll get to the level of the individual pixels and have to make some decisions. (This seven-pixel range is less than 1% of the way across a modern monitor, but the same issues arise for longer lines.)
If we are drawing a line from coordinate (1,1) to coordinate (8,5), obviously we will first plot the point (1,1).
But then, which point should we plot next? The algorithm we will be using will say to plot (2,2) next.
We don't also plot (2,1) -- that would make it look too chunky. The algorithm we present below won't plot (2,1), just (2,2).
The next point is (3,2). Compare this to the mathematically-ideal line.
And so on. Of course we want to end exactly on (8,5), the square we're trying to draw the line to.
Note that each point has a new 'x' coordinate. In our line from (1,1) to (8,5), the x coordinates are 1,2,3,4,5,6,7,8. (So you could use range(1,9).) The 'y' coordinate advances more slowly -- sometimes the y coordinate advances, sometimes it doesn't.
How do we figure out when to advance the 'y' coordinate? We compute what we call the "error" at any given time.
Let's go through this again, with calculations.
After we plot the first point (1,1), we know we're going to add 1 to x. But to make the true mathematical line, we should add 4/7 to y when adding 1 to x. Why 4/7? The difference in the two x coordinates is 7, computed as 8 minus 1; we call this "dx", the difference in x. The difference in the two y coordinates is 4, computed as 5 minus 1; we call this "dy". To make a perfect line, we should add to the x and y coordinates in this ratio, so when adding 1 to x, we add 1*4/7 to y. (Remember to use real arithmetic instead of integer arithmetic to do this division!)
But we can't plot the point (2, 1.5714...), because pixel coordinates are integers.
So we plot the point (2,2), but we remember that we have this error of 2 minus 1.5714... . Which is about 0.43. (Let's do this to two decimal places for the purpose of this example. In this very short line, two decimal places will be accurate enough.)
Since the y coordinate is 2 but should be 1.57, we'll call the error "-0.43". The error is the difference between what y coordinate we're actually on, which is necessarily an integer, and where the mathematically-perfect line would be, which is usually not an integer. And since the mathematically-perfect line could be either above or below the pixel we're plotting, the error number can be either positive or negative. So the error will be the number you would add to the pixel coordinate to get to the actual ideal line. (Adding -0.43 is the same as subtracting 0.43.)
So we have plotted (2,2) and our error value is -0.43. Next, we're going to add another one to x, so x will become 3. And again we'd like to add 4/7, or 0.57, to y. Let's add that to the error instead. -0.43 + 0.57 is 0.14. This value shows that we're pretty close to the ideal line if we just leave y as being 2. So we'll leave y at 2.
That means we next plot (3,2).
And then again we'll add 0.57 to the error. 0.57 + 0.14 is 0.71. This suggests that it would be a good time to add one to y for the next point.
So what's the exact rule, i.e. the algorithm, for when we add one to y? It will be when the error is greater than or equal to 0.5. It's the same as rounding -- this is the situation in which we'll be closer to the ideal line by adding one to y, rather than leaving it as it is.
When we add one to y, we simultaneously subtract one from the error. That is to say, right now y is 2 and the error is 0.71. If we change y to 3, then the error is now -0.29 (computed as 0.71 minus 1), representing the fact that our plotted pixel is 0.29 higher than the ideal line. If we hadn't added one to y or subtracted one from the error, it would have stayed at 0.71, representing the fact that our plotted pixel (were we to plot (4,2), which we aren't going to do because we did add one to y, but this is about if we hadn't) would be 0.71 less than where the ideal line is. Since "0.29 more" is more accurate than "0.71 less", we choose to do the adding one to y and subtracting one from the error.
So where are we now? We plotted (3,2) before, and now when we add one to x (yielding 4), we've decided to add one to y (yielding 3). So we're next plotting the point (4,3). And in addition to these variables "x" and "y", we have a variable named "error" which is now equal to -0.29.
To follow the calculation the rest of the way, please see http://course.dgp.toronto.edu/cgi-bin/bres?x1=1&y1=1&x2=8&y2=5
Do the calculation for your choice of x1, y1, x2, and y2 at: http://course.dgp.toronto.edu/cgi-bin/bres
Ok, does x always increase by 1 each time around the loop?
No. Consider the line from (1,1) to (5,8):
The previous line was above the diagonal, which is why x increased each time. Since this line is below the diagonal, in this case y will increase each time, and it's x which will increase some times and not others, depending on the value of the error.
How do you determine whether the line is above or below the diagonal?
By comparing dx and dy! If dx > dy, we have the earlier case (the one which most of this web page is about), where x increases each time through the loop.
If dx < dy, we have the latter case, where y increases each time through the loop.
If dx is exactly equal to dy, you can consider it to be either case (that is to say, you don't have to worry about dx==dy as a special case).
Are these the only two cases?
No. Consider a line from (1,6) to (8,3), for example:
In this case, y has to decrease as x increases.
But the previous two cases are enough for today. In lab 5, you will write the Bresenham line algorithm always starting from the point (1,1) and always going down to the right. You still have to compare dx and dy to decide which of the first two cases you have, although in grading, the case where dx > dy (where you always increase x each time through the loop, and sometimes increase y) will be worth most of the marks, so get that going first.
Detailed implementation notes for lab 5:
Then you can fill in the 'else'. But make sure you submit a program which still works when dx>dy.