←Previous Entry | Next Entry→ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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:
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:
and there are no more black pixels! How about the fill routine? Tomorrow. |