Bresenham's Line Drawing Derivation

Bresenham's Line Drawing Algorithm Derivation

Bresenham Line drawing algorithm is used to determine closest points to be illuminated on the screen to form a line.

As we know a line is made by joining 2 points, but in a computer screen, a line is drawn by illuminating the pixels on the screen.

(Here pixel (1,2), (3,1) and (5,5) are illuminated and others are non-illuminated)

A line from pixel (2,2) to (7,5) will be shown like this on the screen.

The slope of a line plays a major role in the line equation that's why Bresenham line drawing algorithm calculates the equation according to the slope of the line.

The slope of the line can be greater than 1 (m>1) or less than or equal to 1 (m<=1).
Now enough talking let's derive the equations.

Derivation:

Let's say we want to draw a line on the screen.
so, to draw a line we have to calculate the points or pixels to be illuminated on the screen.

Now while drawing a line a sometimes it passes through 2 pixels at the same time then we have to choose 1 pixel from the 2 to illuminate it.

so, the bresenham algorithm calculates the distance from the intersection point y to both the pixels and whichever is smaller we choose that pixel.

The equation of Line is:

                   Y=mx+c           ....(1)

Here m is the slope of Line and

C is y-Intercept of line

The slope can also be written as 

.....(2)

First we calculate the slope of the line if slope is less than 1, then X will always be incremented.
so at (m<=1)
we calculate the d₁ which is distance between intersection point y to the pixel y_k 

So, d₁ = y-y_k
  d₁ = mx_k+1 +c -y_k         By using ....(1)
 Similarly d₂ is the distance between pixel y_k+1 and intersection point y.
d₂ = y_k+1-y
d₂ = y_k+1-(mx_k+1+c)       By using ....(1)
Note: here x is always incrementing so we can write x_k+1 as x_k +1 and here y_k+1 is next pixel so we can write it as y_k+1.
subtracting d₂ from d₁
d₁-d₂ = m(x_k+1) +c -y_k – [y_k+1-(mx_k+1+c)]
       = m(x_k+1)+c -y_k – y_k-1+m(x_k+1)+c
d₁-d₂ = 2m(x_k+1)-2y_k+2c-1           .....(3)

Multiplying both side by (dx)

dx(d₁-d₂) = 2dy(x_k+1)-2dx(y_k)+2dx(c)-dx

Now ­we need to find decision parameter P_K

P_K= dx(d₁-d₂) and,

C = 2dy+2dx(c)-dx which is constant

So new equation is.

P_K =2dy(x_k)-2dx(y_k) +C      .......(4)

Now our next parameter will be

P_K+1 =2dy(x_k+1)-2dx(y_k+1) +C .....(5)

Subtracting P_k from PK₊₁  

P_k+1-P_k= 2dy(x_k+1­-x_k)-2dx(y_k+1­-y_k) +C-C

Note: here x is always incrementing so we can write x_k+1 as x_k +1

P_k+1-P_k= 2dy(x_k­-x_k+1)-2dx(y_k+1­-y_k)

P_k+1 = P_k+2dy-2dx(y_k+1­-y_k)........(6)

when P_k<0 then (d₁-d₂)<0

So d₁<d₂ then we will write y_k+1 as y_k­ because current pixel’s distance from intersection point y is smaller.so, we will have to choose current pixel.

Then our formula will be:

P_k+1 = P_k+2dy-2dx(y_k­-y_k)

P_k+1 = P_k+2dy

And when P_k>0 then (d₁-d₂)>0

So d₁>d₂ then we will write y_k+1 as y_k+1_­ because current pixel’s distance from intersection point y is larger.so, we will have to choose upper pixel.

At that time our formula will be:

P_k+1 = P_k+2dy-2dx(y_k+1_­-y_k)

P_k+1 = P_k+2dy-2dx

We can say that (y_k+1­-y_k) value can either be 0 or 1.

For Initial decision parameter

From 4^th equation

P_K = 2dy(x_k)-2dx(y_k) +C

P_K = 2dy(x_k)-2dx(y_k)+2dx(c)-dx+2dy

By using 1^st equation

y_k=m(x_k)+c 

c=y_k-m(x_k)             

 P₀ = 2dy(x_k)-2dx(y_k)+2dx(y_k-m(x_k)-dx (By using 2)

    ₌ 2dy(x_k)-2dx(y_k)+2dxy_k-2dyx_k+2dy-dx 

P₀ =2dy-dx

But if the slope of line is greater then 1 (m>1).
then our Y coordinate will always be incremented and we have to choose between x_k or x_k+1.

So, our Line equation will be:

Y_k+1 = m(x)+c

Now, In this case our d₁ will be the distance between intersection point x and pixel x_k   
d₁= x-x_k                By using ....(7)
d₁= 1/m(y_k+1-c)-x_k
And similarly our d₂ will be the distance between intersection point x and pixel x_k+1
d₂ = x_k+1-x             By using ....(7)
d₂ = x_k+1-1/m(y_k+1-c)
 
Note: here y is always incrementing so we can write y_k+1 as y_k+1 and here x_k+1 is next pixel so we can write it as x_k+1.
subtracting d₂ from d₁
d₁-d₂ =1/m(y_k+1-c)-x_k – [x_k+1-1/m(y_k+1-c)]
       = 1/m(y_k+1-c)-x_k – x_k-1+1/m(y_k+1-c)
d₁-d₂ = 2/m(y_k+1-c)-2x_k-1
d₁-d₂ = 2dx(y_k+1-c)-2dyx_k-dy
 
Multiplying both side by (dy)

dy(d₁-d₂) = 2dxy_k+2dx-2dxc-2dyx_k-dy
 
Now ­we need to find decision parameter P_K
P_K = dy(d₁-d₂)
C = 2dx-2dxc-dy which is constant
So new equation is 
P_K = 2dxy_k-2dyx_k +C   ......(8)

Now our next parameter will be
P_k+1 = 2dx(y_k+1)-2dy(x_k+1)+C
Substracting P_k from P_k+1
P_k+1-P_k = 2dx(y_k+1-y_k)-2dy(x_k+1-x_k)+C-C
Note: here x is always incrementing so we can write y_k+1 as y_k +1
P_k+1-P_k = 2dx(y_k +1-y_k)-2dy(x_k+1-x_k)
P_k+1=P_k+2dx-2dy(x_k+1-x_k)

when P_k<0 then (d₁-d₂)<0

So d₁<d₂ then we will write x_k+1 as x_k­ because current pixel’s distance from intersection point x is smaller.so, we will have to choose current pixel.

Then our formula will be:

P_k+1 = P_k+2dx-2dy(x_k-x_k)
P_k+1 = P_k+2dx

And when P_k>0 then (d₁-d₂)>0

So d₁>d₂ then we will write x_k+1 as x_k­+1 because current pixel’s distance from intersection point x is Larger.so, we will have to choose next pixel.

At that time our formula will be:
P_k+1= P_k+2dx-2dy(x_k+1-x_k)
P_k+1= P_k+2dx-2dy


For Initial decision parameter
From 8^th equation 
P_K = 2dxy_k-2dyx_k +C
P₀ = 2dxy₀+2dx-2dxc-2dyx₀-dy

By using 1^st equation 
y_k=m(x_k)+c 

c=y_k-m(x_k)P₀ = 2dxy₀-2dyx₀+2dx-2dx(y₀-m(x₀))-dy
P₀ = 2dxy₀-2dyx₀+2dx-2dxy₀+2dyx₀-dy (By using 2)
P₀ = 2dx-dy

hence formulas for bresenham is derived.

More>>
Bresenhams Line drawing program in C
Bresenham circle drawing algorithm 
Bresenhams Circle drawing program in C
Mid point circle drawing algorithm's derivation 
What is computer graphics