Disadvantages of DDA
● Floating Point Addition
● Rounding Off Function
Bresenham Algorithm
● Incremental Algorithm as DDA
● No floating point usage
● No rounding function used
● It is an efficient method because it involves only integer addition,
subtractions, and multiplication operations. These operations can be
performed very rapidly so lines can be generated quickly.
Bresenham Line Generation
Image Source: [Link]
Bresenham Line Generation
Y = m (Xk + 1 ) + c -------
Image Source: [Link]
What to choose
● Xnext = Xk + 1
● Ynext = Yk + 1 (OR) Yk
● Y = m (Xk + 1 ) + c ---- will be floating value but we
need an integer value
Let’s start the derivation
● dlower = Y - Yk = [ m(Xk + 1) + c ] - Yk = m(Xk + 1) + c - Yk
● dupper = Yk+ 1 - Y = Yk+ 1 - [ m(Xk + 1) + c ] = Yk+ 1 - m(Xk + 1) - c
● To understand which one to choose from Yk and Yk+ 1 , we can verify by
○ If (dlower - dupper) < 0 then, Ynext = Yk
○ If (dlower - dupper) > 0 then, Ynext = Yk + 1
● So, (dlower - dupper) can act as a decision parameter
Derivation Continued…...
● dlower - dupper= [m(Xk + 1) + c - Yk] - [Yk+ 1 - m(Xk + 1) - c]
● dlower - dupper= m(Xk + 1) + c - Yk - Yk- 1 + m(Xk + 1) + c
● dlower - dupper= 2m(Xk + 1) - 2Yk + 2c - 1
● Substituting m = �y / �x, but this might give a float.
● So how to get rid of it. We can get rid of the denominator �x altogether
● dlower - dupper= 2(�y / �x)(Xk + 1) - 2Yk + 2c - 1
● �x(dlower - dupper) = �x[2(�y / �x)(Xk + 1) - 2Yk + 2c - 1]
● �x(dlower - dupper) = 2�y(Xk + 1) - 2�xYk + 2�xc - �x
Derivation Continued…...
● �x(dlower - dupper) = 2�y(Xk + 1) - 2�xYk + 2�xc - �x
● �x(dlower - dupper) = 2�yXk - 2�xYk + 2�y + 2�xc - �x
● So we can now form our decision variable that is Pk
● Pk = �x(dlower - dupper) = 2�yXk - 2�xYk + 2�y + 2�xc - �x----Constant
● Pk = �x(dlower - dupper) = 2�yXk - 2�xYk
● Pnext = 2�yXnext - 2�xYnext
● Pnext - Pk = [2�yXnext - 2�xYnext] - [2�yXk - 2�xYk]
● Pnext - Pk = 2�yXnext - 2�xYnext - 2�yXk + 2�xYk
Derivation Continued…...
● Pnext - Pk = 2�y( Xnext - Xk ) - 2�x ( Ynext - Yk )
● If Pnext - Pk < 0, then remain on the same size for Ynext that is Yk
○ Pnext = Pk + 2�y( Xk +1 - Xk ) - 2�x ( Yk - Yk )
○ Pnext = Pk + 2�y
● If Pnext - Pk >= 0, then Ynext is Yk + 1
○ Pnext = Pk + 2�y( Xk +1 - Xk ) - 2�x ( Yk + 1 - Yk )
○ Pnext = Pk + 2�y - 2�x
Derivation Continued…...
● If Pk+1 - Pk < 0, then remain on the same size for Ynext that is Yk
○ Pk+1 = Pk + 2�y( Xk +1 - Xk ) - 2�x ( Yk - Yk )
○ Pk+1 = Pk + 2�y
● If Pk+1 - Pk >= 0, then Ynext is Yk + 1
○ Pk+1 = Pk + 2�y( Xk +1 - Xk ) - 2�x ( Yk + 1 - Yk )
○ Pk+1 = Pk + 2�y - 2�x
Derivation Continued…...
● Now let’s find out the initial value of Pk
● P1 = 2�yX1 - 2�xY1 + 2�y + 2�xc - �x
● As y1 = mx1 + c, we can substitute ‘c’ as c = y1 - mx1 = y1 - [�y / �x] x1
● P1 = 2�yX1 - 2�xY1 + 2�y + 2�x[y1 - (�y / �x) x1] - �x
● P1 = 2�yX1 - 2�xY1 + 2�y + 2�xy1 - 2�yx1 - �x
● P1 = 2�y - �x
Algo_Bresenham(x1, y1, x2, y2)
{
dx = x2 – x1
dy = y2 – y1
P = 2dy - dx
for(i = 0 to dx)
{
put_pixel ( x, y )
x++
Bresenham Algo If (P < 0)
{
P = P + 2dy
}
else
{
P = P + 2dy - 2dx
y++
}
}
}
Examples for Practice
● Indicate which raster locations would be chosen by Bresenham’s algorithm
when scan-converting a line from pixel coordinate (1,1) to pixel coordinate
(8,5).
● Write and explain bresenham’s line drawing alogrithm and find out which
pixel would be turned on for the line with end points (3,2) to (7,4) using
the same.
● What are the steps involved in Bresenham line drawing algorithm for line
(0,0) to (-8,-5)?
● Explain Bresenham line drawing algorithm with proper mathematical
analysis and identify the pixel positions along a line between A(10,10) and
B(18,16). (May-18/10 Marks)
Summary
References
● Hearn & Baker, “Computer Graphics C version”, 2nd
Edition, Pearson Publication
● [Link]
[Link]