On 20/08/2011 11:19 AM, Warp wrote:
> Orchid XP v8<voi### [at] devnull>  wrote:
>> I can still remember everybody laughing when he said that our assignment
>> was to write a program to draw a straight line. But *you* try doing that
>> with only integer arithmetic. It's surprisingly nontrivial.
>
>    Drawing a line with integer arithmetic is quite easy. Drawing it
> accurately is slightly more involved. Drawing it *fast* is non-trivial.
>
>    And that's assuming the line has a width of 1 pixel and the drawing is
> done without antialiasing.

The assignment was basically to implement Bresenham's Algorithm, 
optionally *with* antialiasing for extra marks.

I'm sure Wikipedia can probably provide the details, but essentially the 
derivation is this:

1. Start with the equation of a line: P(t) = Vt + U

2. By computing each successive point from the previous one, we can 
avoid the expensive multiplication step: P[0] = U, P[n+1] = P[n] + V.

3. We want to ensure that no pixels are missed, and yet no pixel is hit 
more than once. Determine whether the line is longer along the X or Y 
axies, and then iterate over that axis in 1-pixel incriments.

(This step radically increases the difficulty of implementing your code 
correctly "in all eight octants". It's trivial in theory, and damned 
fiddly in practise.)

4. If you incriment in one-pixel steps on one axis, the other axis 
incriments in steps of dx/dy or dy/dx, which is the ratio of two 
integers. If you multiply /the entire algorithm/ through the appropriate 
integer variable, all the arithmetic comes into the integral domain. 
Welcome to Bresenham's algorithm. Yes, I still remember this 10 years later.

The irony is that the lecture notes explain how to use C++ and OpenGL to 
generate the graphical display of your giant "pixels"...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message