Line Drawing algorithm

Line Drawing algorithm

Slope-intersept equation for a straight line is

Y=mx+b

m- slope of the line. b-constant

Two end points of the line segment are (x1,y1) , (x2,y2) Slope m = y2-y1 / x2-x1 -- > Δy/Δx

Δx- x interval – x2-x1 Δy – y interval – y2-y1

Δy = m. Δx Δx=Δy/m

If the interval is known, we can find the next point. xi+1= x i+ Δx -- >  xi+ Δy/m

yi+1= y i+ Δy -- >  yi+ m. Δx

we sample at unit x interval and y interval then this equation becomes xi+1= x i+ Δx -- >  xi+ (1/m)

yi+1= y i+ Δy -- >  yi+ m.1

The above equations are for the lines which are processed from left to right.

The equations are for the lines which are processed from right to left is xi+1= x i+ Δx -- > xi- (1/m)

yi+1= y i+ Δy -- >  yi- m.1

Since m can be any real number between 0 and 1 the y value must be rounded to the nearest integer.

DDA Algorithm (Digital differential analyze)

1. Get the two end points

2. Calculate the Horizontal and vertical difference between two end points (dx,dy)

3. The greatest difference value is taken as the length value.

4. Calculate the step value dx=dx/length, dy=dy / length

5. Start plotting the line from the first point.

6. Repeat through 9 step up to length value times

7. if dx>dy and xa<xb then increment x by 1 and increment y by m

8. if dx>dy and xa>xb then decrement x by 1 and decrement y by m

9. if dx<dy ya<yb then increment y by 1 and increment x by 1/m

10.            if dx<dy and ya>yb then decrement y by 1 and decrement x by 1/m

DDA Line Algorithm

It generates lines from their differencial equations.

Advantages

1. It is the faster method for calculating pixel positions.

2. It is simplest algorithm.It does not require special skills for implementation.

Disadvantages

Floating point arithmetic in DDA algorithm is still time consuming

The algorithm is orientation dependent.Hence end point accuracy is poor.

Bresenham’s Line Algorithm

This algorithm uses only integer addition, subtraction, and multiplication by 2. So it is efficient for scan converting algorithms. This algorithm increments either x or y by one unit depending on the slope of the line. The increment in the other variable is determined by examine the distance between the actual line location and the nearest pixel. This distance is called decision variable or the error.

In matemetical terms the error or decision variable is defined as e = Db – Da

If e>0 then the pixel above the line is closer to the true line.

Else the pixel below the line is closer to the true line.

Assume the current pixel is (xk,yk)

We have to find the next pixel position either ((xk+1,yk) and (xk+1,yk+1) The y coordinate on the line at the pixel position xk+1 Is y = m (xk+1 ) + c Then the distance d1= y - yk = m (xk+1 ) + c-yk

d2= (yk+1-y)= yk+1-m (xk+1 ) + c

d1-d2 = m (xk+1) + c-yk -yk--1-(yk+1)+m (xk+1 ) + c = 2m (xk+1)-2 yk +2c-1

The error term is initially set as e = 2Δy-Δx where Δy=y2-y1 , Δx=x2-x1

Bresenhams algorithm

1. Get the two end points

2. Calculate the values dx,dy,2dy and 2dy-2dx where dx=X2-X1 and dy=Y2-Y1

3. Calculate the starting decision parameter d=2dy-dx

4. plot the first point

5. At each Xk along the line, starting at k=0, perform the following test

If pk<0 , the next point to plot is (Xk+1,Yk) and Pk+1=pk+2dy Otherwise the next point to plot is (Xk+1,Yk+1) Pk+1=pk+2dy-2dx 6. Repeat step 5 for dx times.

The following program is used to for generalized bresenham algorithm, which will work for all the four coordinates.

Parallel Line algorithm

We can calculate the pixel position along the path simultaneously by partitioning the computations among the various processors available. One approach to the partitioning problem is to adapt an exsisting sequential algorithm to take advantage of multiple processors. Alternatively, we can look for other ways to set up the processing so that pixel positions can be calculated efficiently in parallel.