Back to July Calendar 

August 23, 2005

It's the simplest things that make for the richest complexity. 

Let's compare the DDA and Bresenham algorithms for line rasterization.  Here's a magnification of one triangle drawn with yesterdays code:

Each of the triangle's edges are first drawn in black with the DDA algorithm and then over drawn with either red (if not a steep line) or blue (if steep.)  So, here's how this came to be: from the lower left vertex to the right vertex, a black rasterization of the line using DDA is drawn, then it is (sort of) duplicated with the red Bresenham rasterization.  Similarly for the next two edges proceeding counterclockwise around the triangle.  By outputting data to the console window (for some strange reason, I'm using "printf" instead of "cout") we can numerically analyze the results of this experiment and try to make sense of these in terms of the pixels plotted, as evidenced in the picture.

What this means is that the black pixels may or may not be overwritten by the red/blue pixels. 

The vertices (by happenstance) turn out to have coordinates (5,5), (23,9) and (9,14). 

Thus, for the first (bottom) edge, we have Δy=4 and Δx=18.  The diagram is cropped so it doesn't look like it, but the big black pixel on the lower left, would have been at (5,5).  Then it would have been painted red, then black again, and then...blue?  Why isn't it blue?  Hmmm....

As for the black pixels, that's the DDA algorithm, so let's look at it, too.  The slope is 2/9 = 0.22222... So, as the table below indicates, you should get exactly the same values with the rounding that you got with Bresenham.  This causes me to realize that I have a mistake: the (int)x expression doesn't round x, it truncates it!  

So I add a round function:

int round(float x) {
  if (x-(int)x < 0.5) return (int)x;
  else return (int)(x+1);
}

and there are no more black pixels!

How about the fill routine?  Tomorrow.