Raster Conversion Algorithms
DDA line algorithm
Bresenham line algorithm
Pixel Addressing in Raster Graphics
Theoretical length
Pixel
address
y+1
Pixel
y+2
y+3
x x+1 x+2 x+3 x+4
Actual length
Raster conversion Algorithms:
Requirements
visual accuracy
spatial accuracy
speed
Line – Raster Representation
Basis for Line Drawing Algorithms
The Cartesian slope-intercept for a straight line is
y= m.x + b 1
--------------------
m= Slope of the line
b= y intercept
The slope of the line is defined as
m=(y2-y1)/(x2-x1) ---------------- 2
The y intercept b is defined as
b=y1- m . x1-----------------------3
Algorithms for displaying straight lines are based on the above 3 eqns.
For any given x interval ∆x along a line, we compute the y-interval ∆y.
∆y=m . ∆x ------------------------------4
• Similarly we can obtain ∆x .
∆x= ∆y/m ------------------------------------5
• The eqns 4 and 5 form the basis for determining the deflection voltage in
analog devices.
Cases to handle
Case 1:Slope |m| < 1
∆x=small horizontal deflection voltage
∆y is calculated proportional to slope.(∆y =m. ∆x)
Case 2:Slope |m| >1
∆y=small vertical deflection voltage
∆x is calculated proportional to slope.(∆x =∆y/m)
Case 3:Slope m = 1
∆x=∆y (Both the voltages are same)
Line drawing – DDA algorithm
(DDA) is a scan-conversion line algorithm based on calculating
either ∆y or ∆x.
∆y = m * ∆x
∆x = ∆y / m
we have many cases based on sign of the slope, value of the
slope, and the direction of drawing.
Slope sign: positive or negative.
Slope value: <= 1 or >1.
Direction: (left – right) or (right – left)
DDA – case 1
Positive slope and left to right:
If slope <= 1 then:
xk+1 = xk + 1
yk+1 = yk + m
If slope > 1 then:
xk+1 = xk + 1/m
yk+1 = yk + 1
DDA – case 2
Positive slope and right to left:
If slope <= 1 then:
xk+1 = xk – 1
yk+1 = yk – m
If slope > 1 then:
xk+1 = xk – 1/m
yk+1 = yk – 1
DDA – case 3
Negative slope and left to right:
If |m | <= 1 then:
xk+1 = xk + 1
yk+1 = yk – m
If |m | > 1 then:
xk+1 = xk + 1/m
yk+1 = yk – 1
DDA – case 4
Negative slope and right to left:
If |m | <= 1 then:
xk+1 = xk – 1
yk+1 = yk + m
If |m | > 1 then:
xk+1 = xk – 1/m
yk+1 = yk + 1
Digital Differential Algorithm
Input line endpoints, (x1,y1) and (x2, y2)
set pixel at position (x1,y1)
calculate slope m=(y2-y1)/(x2-x1)
For +ve slope (left to right)
Case |m|≤1: Sample at unit x intervals and compute each successive y.
Repeat the following steps until (x2, y2) is reached:
yk+1 = yk + m where(m=∆y/ ∆x)
xk+1 = xk + 1
set pixel at position (xk+1,Round(yk+1))
Case |m|>1: Sample at unit y intervals and compute each successive
x.
Repeat the following steps until (x2, y2) is reached:
xk+1 = xk+ 1/m
yk+1 = yk + 1
set pixel at position (Round(xk+1), yk+1)
Digital Differential Algorithm
For +ve slope (right endpoint to left endpoint)
Case |m|≤1: Sample at unit x intervals and compute each successive y.
Repeat the following steps until (x2, y2) is reached:
yk+1 = yk - m where(m=∆y/ ∆x)
xk+1 = xk - 1
set pixel at position (xk-1,Round(yk-1))
Case |m|>1: Sample at unit y intervals and compute each successive x.
Repeat the following steps until (x2, y2) is reached:
xk+1 = xk -1/m
yk+1 = yk - 1
set pixel at position (Round(xk-1), yk-1)
Scan Conversion Process
DDA ( Digital Differential Algorithm )
m<1
•∆x=small horizontal
deflection voltage
(∆x=1)
•∆y proportional to
slope m (∆y= ∆x . m)
DDA ( Digital Differential Algorithm )
m>1
•∆y=small horizontal
deflection voltage
(∆y=1)
•∆x proportional to
slope m (∆x= ∆y/m)
DDA ( Digital Differential Algorithm )
m>1
DDA Line algorithm - Procedure
Procedure lineDDA(xa,xb,ya,yb:integer);
Var
dx,dy,steps,k : integer;
xIncrement, yIncrement, x , y: real;
Begin
dx:=xb-xa;
dy:=yb-ya;
if abs(dx) >abs(dy) then steps:=abs(dx)
else steps:=abs(dy)
xIncrement :=dx/steps;
yIncrement :=dy/steps;
x:=xa;
y:=ya;
DDA Line algorithm – Procedure
contd.
setPixel(round(x),round(y),1);
for k:=1 to steps do
Begin
x:=x+xIncrement;
y:=y+yIncrement;
setPixel(round(x), round(y),1);
End
End {lineDDA}
Example
Consider endpoints: P1 (0,0) P2 (7,3)
m = (3 – 0)/(7 - 0)
= 0.429 (m<1)(+ve slope)
dx = 1
x0 = 0, y0 = 0
x1 = x0 + 1 = 1
y1 = y0 + 0.429 •3
= 0.429 ≈ 0 •2
•1
x1 = 1, y1 = 0.429
•0
x2 = x1 + 1 = 2 •0 •1 •2 •3 •4 •5 •6 •7
y2 = y1 + 0.429
= 0.859 ≈ 1
Example contd.
x2 = 2, y2 = 0.858
x3 = x2 + 1 = 3
y3 = y2 + 0.429
= 1.287 ≈ 1
x3 = 3, y3 = 1.287
x4 = x3 + 1 = 4
y4 = y3 + 0.429
= 1.716 ≈ 2
x4 = 4, y4 = 2
x5 = x4 + 1 = 5
y5 = y4 + 0.429
= 2.145 ≈ 2
Example contd.
x5 = 5, y5 = 2
x6 = x5 + 1 = 6
y6 = y5 + 0.429
= 2.574 ≈ 3
x6 = 6, y6 = 3
x7 = x6 + 1 = 7
y7 = y6 + 0.429
= 3.003 ≈ 3
x7=7,y7=3
Disadvantages of DDA algorithm
DDA works with floating point arithmetic
Rounding to integers necessary
Bresenham's Line Algorithm
An accurate and efficient raster line generating-algorithms developed by Bresenham.
Scan converts lines using only incremental integer calculations.
y = mx + b
d2
y = m(x+1) + b
y d1
x x+1
Bresenham's line algorithm (slope ≤ 1)
Input line endpoints, (x0,y0) and (xn, yn)
calculate ∆x = xn - x0 and ∆y = yn - y0
Assuming the pixel (xk , yk ) is to displayed
Determine the positions whether at (xk+1 , yk ) and (xk+1 , yk+1 )
From xk+1 we label vertical pixel separations from line as d1 and d2
The y coordinate at pixel column position xk+1 is calculated as
y=m(xk+1)+b.
Then
d1=y-yk=m(xk+1)+b-yk
and
d2=yk+1-y=yk+1- m(xk+1)-b.
Bresenham's line algorithm (slope ≤ 1)
d1-d2=2 m(xk+1)-2yk+2b-1
Decision parameter pk for the kth step in line algorithm obtained by rearranging the
above equations.
Substitute m=∆y/ ∆x, where ∆y, ∆x are horizontal and vertical seperations.
Pk= ∆x(d1-d2)== 2 ∆y. xk – 2 ∆x . yk +c------------------- 1
C is constant has the value 2 ∆y+ ∆x(2b-1)
When Pk is negative plot the lower pixel else plot the upper pixel.
Coordinate changes along the line occur in unit steps in x and y directions.
The values of successive decision parameter can be evaluated from
2
Pk+1=2 ∆y. xk+1 – 2 ∆x . yk+1 +c-------------------------------
Subtracting 1 & 2 we get
Pk+1=Pk+ 2 ∆y- 2 ∆x (yk+1- yk) (since xk+1=xk+1)
The term (yk+1- yk) is either 1 or 0 depending on the sign of parameter pk
The recursive calculation of decision parameters is performed at each integer
x position.
The parameter p0 is evaluated from eq1 p0=2 ∆y- ∆x
Bresenham's Line Algorithm
Input line endpoints, (x0,y0) and (xn, yn)
Load (x0,y0) into the frame buffer that is first point
Calculate the constants ∆x, ∆y,2∆y and 2∆y - 2∆x
calculate parameter p0 = 2 ∆y - ∆x
Set pixel at position (x0,y0)
repeat the following steps until (xn, yn) is reached:
if pk < 0
set the next pixel at position (xk +1, yk )
calculate new pk+1 = pk + 2 ∆y
if pk ≥ 0
set the next pixel at position (xk +1, yk + 1 )
calculate new pk+1 = pk + 2(∆y - ∆x)
Repeat last step ∆x times.
Advantages of Bresenham's Line Algorithm
Bresenham’s algorithm uses integer arithmetic
Constants need to be computed only once
Bresenham’s algorithm generally faster than DDA
Bresenham’s line drawing Procedure
procedure lineBres (xa, ya, xb, yb : integer)
var
dx, dy, x, y, xEnd, p: integer;
begin
dx :=abs(xa-xb);
dy :=abs(ya-yb);
p:=2 * dy – dx;
if xa > xb then
begin
x:= xb;
y:= yb;
xEnd := xa;
else
begin
x:=xa;
y:=ya;
Contd…
xEnd := xb;
end;
setPixel (x,y,1);
while x < xEnd do
begin
x:= x+1;
if p < 0 then p:= p+2 * dy
else
begin
y:=y+1;
p:=p+2 * (dy-dx)
end;
setPixel (x,y,1);
end
end; {lineBres}
Thank you
