Scan Conversion on Line Generation Algorithm
Scan Conversion defer is a process of representing graphics objects a collection of pixels that is 1(on set) or 0 (offset). In general, a line consist of connecting two points. It is a basic in computer graphics. In order to draw a line, you need two points between which you can draw a line.
Scan Converting a Straight Line
A straight line may be defined by two endpoints & an equation. In fig the two endpoints are described by (x1,y1) and (x2,y2). The equation of the line is used to determine the x, y coordinates of all the points that lie between these two endpoints.
Using the equation of a straight line, y = mx + b where m = 
& b = the y interrupt, we can find values of y by incrementing x from x =x1, to x = x2. By scan-converting these calculated x, y values, we represent the line as a sequence of pixels.
Properties of Good Line Drawing Algorithm:
1. Line should appear Straight: We must appropriate the line by choosing addressable points close to it. If we choose well, the line will appear straight, if not, we shall produce crossed lines.
The lines must be generated parallel or at 45° to the x and y-axes. Other lines cause a problem: a line segment through it starts and finishes at addressable points, may happen to pass through no another addressable points in between.
2. Lines should terminate accurately: Unless lines are plotted accurately, they may terminate at the wrong place.
3. Lines should have constant density: Line density is proportional to the no. of dots displayed divided by the length of the line. In order to maintain constant density, dots should be equally spaced.
4. Line density should be independent of line length and angle: This can be done by computing an approximating line-length estimate and to use a line-generation algorithm that keeps line density constant to within the accuracy of this estimate.
5. Line should be drawn rapidly: This computation should be performed by special-purpose hardware.
Algorithm for line Drawing:
- Direct use of line equation
- DDA (Digital Differential Analyzer)
- Bresenham’s Algorithm
Direct use of line equation:
It is the simplest form of conversion. First of all scan P1 and P2 points. P1 has co-ordinates (x1‘,y1‘) and (x2‘ y2‘ ).
Then m = (y2‘,y1‘)/( x2‘,x1‘) and b = 
If value of |m|≤1 for each integer value of x. But do not consider 
If value of |m|>1 for each integer value of y. But do not consider 
Example: A line with starting point as (0, 0) and ending point (6, 18) is given. Calculate value of intermediate points and slope of line.
Solution: P1 (0,0) P7 (6,18)
x1=0
y1=0
x2=6
y2=18
We know equation of line is
y =m x + b
y = 3x + b…………..equation (1)
put value of x from initial point in equation (1), i.e., (0, 0) x =0, y=0
0 = 3 x 0 + b
0 = b ⟹ b=0
put b = 0 in equation (1)
y = 3x + 0
y = 3x
Now calculate intermediate points
Let x = 1 ⟹ y = 3 x 1 ⟹ y = 3
Let x = 2 ⟹ y = 3 x 2 ⟹ y = 6
Let x = 3 ⟹ y = 3 x 3 ⟹ y = 9
Let x = 4 ⟹ y = 3 x 4 ⟹ y = 12
Let x = 5 ⟹ y = 3 x 5 ⟹ y = 15
Let x = 6 ⟹ y = 3 x 6 ⟹ y = 18
So points are
P1 (0,0); P2 (1,3) ; P3 (2,6); P4 (3,9); P5 (4,12); P6 (5,15); P7 (6,18)
Algorithm for drawing line using equation:
Step1: Start Algorithm
Step2: Declare variables x1,x2,y1,y2,dx,dy,m,b,
Step3: Enter values of x1,x2,y1,y2.
The (x1,y1) are co-ordinates of a starting point of the line.
The (x2,y2) are co-ordinates of a ending point of the line.
Step4: Calculate dx = x2– x1
Step5: Calculate dy = y2-y1
Step6: Calculate m = 
Step7: Calculate b = y1-m* x1
Step8: Set (x, y) equal to starting point, i.e., lowest point and xendequal to largest value of x.
If dx < 0
then x = x2
y = y2
xend= x1
If dx > 0
then x = x1
y = y1
xend= x2
Step9: Check whether the complete line has been drawn if x=xend, stop
Step10: Plot a point at current (x, y) coordinates
Step11: Increment value of x, i.e., x = x+1
Step12: Compute next value of y from equation y = mx + b
Step13: Go to Step9.
Program to draw a line using Line Slope Method
#include <graphics.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;
class bresen
{
float x, y, x1, y1, x2, y2, dx, dy, m, c, xend;
public:
void get ();
void cal ();
};
int main ()
{
bresen b;
b.get ();
b.cal ();
getch ();
}
void bresen :: get ()
{
printf (“Enter start & end points”);
printf (“enter x1, y1, x2, y2\n”);
scanf (“%f%f%f%f”,&x1, &y1, &x2, &y2);
}
void bresen ::cal ()
{
/* request auto detection */
int gdriver = DETECT,gmode, errorcode;
/* initialize graphics and local variables */
initgraph (&gdriver, &gmode, ” “);
/* read result of initialization */
errorcode = graphresult();
if (errorcode != grOk) /* an error occurred */ /*an error occurred */
{
printf(“Graphics error: %s\n”, grapherrormsg(errorcode));
printf(“Press any key to halt:”);
getch ();
exit (1); /* terminate with an error code */
}
dx = x2-x1;
dy=y2-2*y1;
m = dy/dx;
c = y1 – (m * x1);
if (dx<0)
{
x=x2;
y=y2;
xend=x1;
}
else
{
x=x1;
y=y1;
xend=x2;
}
while (x<=xend)
{
putpixel (x, y, RED);
y++;
y=(x*x) +c;
}
}
OUTPUT:
Enter Starting and End Points Enter (X1, Y1, X2, Y2) 200 100 300 200
In general, a line consist of connecting two points. It is a basic in computer graphics. In order to draw a line, you need two points between which you can draw a line.
In the following three algorithms, we refer the one point of line as X0,Y0X0,Y0 and the second point of line as X1,Y1X1,Y1.
DDA Algorithm(Digital Differential Analyzer )
DDA algorithm is the simple line generation algorithm which is detailed step by step here.
Step 1 − Get the input of two end points (X0,Y0)(X0,Y0) and (X1,Y1)(X1,Y1).
Step 2 − Calculate the difference between two end points.
dx = X1 - X0 dy = Y1 - Y0
Step 3 − Based on the calculated difference in step-2, you need to identify the number of steps to put pixel. If dx > dy, then you need more steps in x coordinate; otherwise in y coordinate.
if (absolute(dx) > absolute(dy)) Steps = absolute(dx); else Steps = absolute(dy);
Step 4 − Calculate the increment in x coordinate and y coordinate.
Xincrement = dx / (float) steps; Yincrement = dy / (float) steps;
Step 5 − Put the pixel by successfully incrementing x and y coordinates accordingly and complete the drawing of the line.
for(int v=0; v < Steps; v++) { x = x + Xincrement; y = y + Yincrement; putpixel(Round(x), Round(y)); }
Bresenham’s Line Generation
Bresenham’s Line Algorithm is used for scan converting a line. It was developed by Bresenham. It is an incremental scan conversion algorithm. The big advantage of this algorithm is that, it uses only integer calculations. Moving across the x axis in unit intervals and at each step choose between two different y coordinates. 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. In this method, next pixel selected is that one who has the least distance from true line.
The method works as follows:
Assume a pixel P1′(x1′,y1′),then select subsequent pixels as we work our may to the night, one pixel position at a time in the horizontal direction toward P2′(x2′,y2′). Once a pixel in choose at any step. The next pixel is 
Either the one to its right (lower-bound for the line). One top its right and up (upper-bound for the line) The line is best approximated by those pixels that fall the least distance from the path between P1′,P2′.
Bresenham’s Line Algorithm
When (s-t) <0 ⟹ s < t
The closest pixel is S
When (s-t) ≥0 ⟹ s < t
The closest pixel is T
This difference is
s-t = (y-yi)-[(yi+1)-y]
= 2y – 2yi -1
Advantage:
1. It involves only integer arithmetic, so it is simple.
2. It avoids the generation of duplicate points.
3. It can be implemented using hardware because it does not use multiplication and division.
4. It is faster as compared to DDA (Digital Differential Analyzer) because it does not involve floating point calculations like DDA Algorithm.
Disadvantage:
1. This algorithm is meant for basic line drawing only Initializing is not a part of Bresenham’s line algorithm. So to draw smooth lines, you should want to look into a different algorithm.
Bresenham’s Line Algorithm:
Step1: Start Algorithm
Step2: Declare variable x1,x2,y1,y2,d,i1,i2,dx,dy
Step3: Enter value of x1,y1,x2,y2
Where x1,y1are coordinates of starting point
And x2,y2 are coordinates of Ending point
Step4: Calculate dx = x2-x1
Calculate dy = y2-y1
Calculate i1=2*dy
Calculate i2=2*(dy-dx)
Calculate d=i1-dx
Step5: Consider (x, y) as starting point and xendas maximum possible value of x.
If dx < 0
Then x = x2
y = y2
xend=x1
If dx > 0
Then x = x1
y = y1
xend=x2
Step6: Generate point at (x,y)coordinates.
Step7: Check if whole line is generated.
If x > = xend
Stop.
Step8: Calculate co-ordinates of the next pixel
If d < 0
Then d = d + i1
If d ≥ 0
Then d = d + i2
Increment y = y + 1
Step9: Increment x = x + 1
Step10: Draw a point of latest (x, y) coordinates
Step11: Go to step 7
Step12: End of Algorithm
Example: Starting and Ending position of the line are (1, 1) and (8, 5). Find intermediate points.
Solution: x1=1
y1=1
x2=8
y2=5
dx= x2-x1=8-1=7
dy=y2-y1=5-1=4
I1=2* ∆y=2*4=8
I2=2*(∆y-∆x)=2*(4-7)=-6
d = I1-∆x=8-7=1
| x | y | d=d+I1 or I2 |
| 1 | 1 | d+I2=1+(-6)=-5 |
| 2 | 2 | d+I1=-5+8=3 |
| 3 | 2 | d+I2=3+(-6)=-3 |
| 4 | 3 | d+I1=-3+8=5 |
| 5 | 3 | d+I2=5+(-6)=-1 |
| 6 | 4 | d+I1=-1+8=7 |
| 7 | 4 | d+I2=7+(-6)=1 |
| 8 | 5 |
Bresenham’s Line Algorithm
Program to implement Bresenham’s Line Drawing Algorithm:
#include<stdio.h>
#include<graphics.h>
void drawline(int x0, int y0, int x1, int y1)
{
int dx, dy, p, x, y;
dx=x1-x0;
dy=y1-y0;
x=x0;
y=y0;
p=2*dy-dx;
while(x<x1)
{
if(p>=0)
{
putpixel(x,y,7);
y=y+1;
p=p+2*dy-2*dx;
}
else
{
putpixel(x,y,7);
p=p+2*dy;}
x=x+1;
}
}
int main()
{
int gdriver=DETECT, gmode, error, x0, y0, x1, y1;
initgraph(&gdriver, &gmode, "c:\\turboc3\\bgi");
printf("Enter co-ordinates of first point: ");
scanf("%d%d", &x0, &y0);
printf("Enter co-ordinates of second point: ");
scanf("%d%d", &x1, &y1);
drawline(x0, y0, x1, y1);
return 0;
}
Output:
Bresenham’s Line Algorithm
Differentiate between DDA Algorithm and Bresenham’s Line Algorithm:
DDA Algorithm Bresenham’s Line Algorithm
1. DDA Algorithm use floating point, i.e., Real Arithmetic. 1. Bresenham’s Line Algorithm use fixed point, i.e., Integer Arithmetic
2. DDA Algorithms uses multiplication & division its operation 2.Bresenham’s Line Algorithm uses only subtraction and addition its operation
3. DDA Algorithm is slowly than Bresenham’s Line Algorithm in line drawing because it uses real arithmetic (Floating Point operation) 3. Bresenham’s Algorithm is faster than DDA Algorithm in line because it involves only addition & subtraction in its calculation and uses only integer arithmetic.
4. DDA Algorithm is not accurate and efficient as Bresenham’s Line Algorithm. 4. Bresenham’s Line Algorithm is more accurate and efficient at DDA Algorithm.
5.DDA Algorithm can draw circle and curves but are not accurate as Bresenham’s Line Algorithm, it can draw circle and curves with more accurate.
Mid-Point Algorithm
Mid-point algorithm is due to Bresenham which was modified by Pitteway and Van Aken. Assume that you have already put the point P at x,yx,y coordinate and the slope of the line is 0 ≤ k ≤ 1 as shown in the following illustration. Now you need to decide whether to put the next point at E or N. This can be chosen by identifying the intersection point Q closest to the point N or E. If the intersection point Q is closest to the point N then N is considered as the next point; otherwise E.
To determine that, first calculate the mid-point Mx+1,y+½x+1,y+½. If the intersection point Q of the line with the vertical line connecting E and N is below M, then take E as the next point; otherwise take N as the next point. In order to check this, we need to consider the implicit equation:
Fx,yx,y = mx + b – y
For positive m at any given X,
- If y is on the line, then Fx,yx,y = 0
- If y is above the line, then Fx,yx,y < 0
- If y is below the line, then Fx,yx,y > 0
