Line drawing algo.

Line Drawing Algorithms

A line in Computer graphics typically refers to
line segment, which is a portion of straight
line that extends indefinitely in opposite
direction. It is defined by its two end points &
the slope intercept equation for a line:
y = mx + b (1)
where, m = Slope of the line
b = the y intercept of a line

The two endpoints of a line segment are
specified at positions (x1,y1) and (x2,y2).
y
P2(x2,y2)

P1(x1,y1)
b

0
x

We can determine the value for slope m & b
intercept as
m = y2-y1/x2-x1 (2)
And, b = y1 – mx1 (3)
For a given x interval Δx along a line, we can
compute the corresponding y interval Δy from
Δy = m Δx (4)
Similarly, we can obtain x interval Δx by Δy:
Δx = Δy/m (5)

If |m|<1, then for every integer value of x
between and excluding x1 and x2, calculate
the corresponding value of y using
equation Δy = m Δx & scan convert (x,y).
If |m|>1, then for every integer value of y
between and excluding y1 and y2, calculate
the corresponding value of x using
equation Δx = Δy/m & scan convert (x,y).
If |m|=1, Δx = Δy. In each case, a smooth line
with slope m is generated between the
specific endpoints.

Example 1 The endpoints of line are(0,0) &
(6,18). Compute each value of y as x steps
from 0 to 6 and plot the result.
Solution : Equation of line is y= mx +b
m = y2-y1/x2-x1= 18-0/6-0 = 3
Next the y intercept b is found by plugging
y1& x1 into the equation y = 3x + b,
0 = 3(0) + b. Therefore, b=0, so the
equation for the line is y= 3x.

While this approach is mathematically sound,
it involves floating-point computation
(multiplication & addition) in every step
that uses the line equation since m & b are
generally real numbers. The challenge is to
find a way to achieve the same goal as
quickly as possible.

DDA Algorithm
The digital differential analyzer (DDA)
algorithm is an incremental scan-
conversion method. Such an approach is
characterized by performing calculations at
each step using results from the preceding
step. Suppose, at step i we have
calculated(xi, yi) to be a point on the
line.Since the next point (xi+1,yi+1) should
satisfy Δy/Δx= m where Δy= yi+1 – yi &
Δx = xi+1 – xi.

We have, yi+1 = yi + mΔx
yi+1 = yi + Δy (1)
Or xi+1 = xi + Δy/m (2)
Algorithm:
(x1,y1) (x2,y2) are the end points and dx, dy are the
float variables.
(i) If abs(x2-x1) > abs(y2-y1) then
length = abs(x2-x1)
else
length = abs(y2-y1)
endif

(ii) dx = (x2-x1)/length
dy = (y2-y1)/length
(iii) x = x1 + 0.5
y = y1 + 0.5
(iv) i=0
(v) Plot (trunc(x), trunc(y))
(vi) x = x + dx
y = y + dy
(vii) i=i+1

(viii) If i < length then go to step (v)
(ix) Stop
Example 2 Scan convert a line having end
points (3,2) & (4,7) using DDA.
Solution: x2 - x1 = 4-3 = 1
y2 - y1 = 7-2 = 5
As, abs(x2-x1) < abs(y2-y1) then
length = y2-y1 = 5
dx = (x2-x1)/ length = 1/5 = .2
dy = (y2-y1)/ length = 5/5 = 1

x1 y1 x2 y2 L dx dy i x y Result Plot
3 2 4 7 5 .2 1 0 3.5 2.5 3.5, 2.5 3,2
1 3.7 3.5 3.7,3.5 3,3
2 3.9 4.5 3.9,4.5 3,4
3 4.1 5.5 4.1,5.5 4,5
4 4.3 6.5 4.3,6.5 4,6
5 4.5 7.5 4.5,7.5 4,7

Limitations of DDA:
(1) The rounding operation & floating point
arithmetic are time consuming procedures.
(2) The accumulation of round-off error in
successive addition of floating point
increment can cause the calculated pixel
position to drift away from the true line
path for long line segment.

Line drawing algo.

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Viewers also liked

Viewers also liked (20)

Similar to Line drawing algo.

Similar to Line drawing algo. (20)

More from Mohd Arif

More from Mohd Arif (20)

Line drawing algo.