Home » Computer Graphics

Scan Converting a Straight Line in Computer Graphics

Computer Graphics | Scan Converting a Straight Line: In this tutorial, we are going to learn about the Scan Converting a Straight Line, and algorithms which are used in that. By Monika Sharma Last updated : April 05, 2024

Scan Converting a Straight Line

For the scan conversion of a straight line, we need the two endpoints. In normal life, if we want to draw a line we simply draw it by using a scale or ruler. But we can't draw a line on the computer by using a ruler. We have to do some programming for it. The computer draws a line by finding the intermediate points between the two endpoints of a line. The line is drawn on the screen when the computer has endpoints and then the computer fills the pixel of the intermediate point's value.

The computer can't take the intermediate points in fraction value. For example, after using any of the algorithms if the intermediate point was found (5.1, 7.8) then the computer will round off the point values which are (5,8). The computer takes the nearest integer from that fraction value. This happens because the computer fills the pixels in the screen and pixels are present at the integer values. Either the pixel will be filled or it will not be filled. A pixel can't be partially filled. That is why the line is drawn in the computer is not always a straight line.

Algorithms for Scan Converting a Straight Line

There are several algorithms available which are used for this process:

1. Direct Method
2. Bresenham's Algorithm
3. DDA (Digital Differential Analyzer)

1. Direct Method

It is the simplest method of this. In this algorithm, we have two endpoints. We find the slope of the line by using both the points and we put the slope in the line equation Y = MX + C. Then we find the value of C by putting X and Y is equal to 0. After this, we have a relation between X and Y. Now we increase the value of X and find the corresponding value of Y. These values will be the intermediate points of the line. After finding the intermediate points we'll plot those points and draw the line.

2. Bresenham's Algorithm

This method of line drawing is very effective because it includes integer addition, subtraction, and multiplication. The calculation is very fast in this method that's why the line is drawn very quickly in this. We'll need the two endpoints in this and then we have to find the decision parameters. Let assume that (x1,y1) and (x2,y2) are the two points. So, dx = x2-x1 and dy = y2-y1.

The formula for the decision parameter is: di = 2dy - dx

1. If di > 0 (Above true line)

       di +1 = di + 2dy - 2dx
   

   Plotted points are,

       xN = x1 + 1
       yN = y1 + 1
   

2. If di < 0: (Below True Line)

       di + 1 = di + 2dy
   

   Plotted points are,

       xN = x1 + 1
       yN = y1
   

   This is the way we can find the intermediate point and after finding these points we can plot all the points on the screen using programming.

Advantages

• This algorithm involves integer arithmetic operations.
• Duplicate points can’t be generated in this.
• This algorithm can be implemented using the software as well as the hardware.

Disadvantages

• This algorithm is for basic line drawing.
• You have to prefer some other algorithm for drawing smooth lines

3. DDA (Digital Differential Analyzer)

This algorithm works on the incremental approach. It means that by taking the help of previous coordinates, we find the next coordinates. In this method, the difference of pixel point is analyzed and according to the analysis, the line can be drawn. We'll start with the starting point and we'll try to find the intermediate points between the starting point and the ending point. The slope of the line will be the ratio of difference of y-coordinates and the difference of x-coordinates.

Δy = ( y2 - y1 )
Δx = ( x2 - x1 )

Where, (x1, y1) and (x2, y2) are the endpoints.

The Digital Differential Analyzer algorithm is based on the values of Δx and Δy.

Δy = m * Δx 
Δx = Δy / m

The value of the slope will be either positive or negative. If the value of the slope is positive then the values of Δx and Δy are increased otherwise their values are decreased.

1)  If (m < 1):
    xN = x1 + 1
    yN = y1 + m

2)	If (m > 1):
    xN = x1 + 1 / m
    yN = y1 +1

3)	If (m = 1):
    xN = x1 + 1
    yN = y1 + 1