# Part 2: Scan Conversion on Line Generation Algorithm.

## 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:

1. Direct use of line equation
2. DDA (Digital Differential Analyzer)
3. 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

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.

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

Cambridge IELTS 12 is the latest IELTS exam preparation.https://draftsbook.com/ will help you to answer all questions in cambridge ielts 12 reading test 4 with detail explanations. 1. obsidian Question: Early humans used a material called 1…………. to make the sharp...

Cambridge IELTS 12 is the latest IELTS exam preparation.https://draftsbook.com/ will help you to answer all questions in cambridge ielts 12 reading test 3 with detail explanations. 1. v Paragraph A The first paragraph is about the inhospitable environment of the...

Cambridge IELTS 12 is the latest IELTS exam preparation.https://draftsbook.com/ will help you to answer all questions in cambridge ielts 12 reading test 2 with detail explanations. 1. A Question: a reference to characteristics that only apply to food production...

Cambridge IELTS 12 is the latest IELTS exam preparation.https://draftsbook.com/ will help you to answer all questions in cambridge ielts 12 reading test 1 with detail explanations. 1. NOT GIVEN Question: The cork oak has the thickest bark of any living tree. Key...

Cambridge IELTS 11 is the latest IELTS exam preparation. https://draftsbook.com/ will help you to answer all questions in cambridge ielts 11 reading test 4 with detail explanations. PASSAGE 1: RESEARCH USING TWINS QUESTIONS 1-4: DO THE FOLLOWING STATEMENTS AGREE...

Cambridge IELTS 11 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 11 reading test 3 with detail explanations. PASSAGE 1: THE STORY OF SILK QUESTIONS 1-9: COMPLETE THE NOTES BELOW....

# You may find interest following article

Cambridge IELTS 12 is the latest IELTS exam preparation.https://draftsbook.com/ will help you to answer all questions in cambridge ielts 12 reading test 4 with detail explanations. 1. obsidian Question: Early humans used a material called 1…………. to make the sharp points of their 2…………… Key words: early humans, sharp points In the first paragraph, the author...

Cambridge IELTS 12 is the latest IELTS exam preparation.https://draftsbook.com/ will help you to answer all questions in cambridge ielts 12 reading test 3 with detail explanations. 1. v Paragraph A The first paragraph is about the inhospitable environment of the Galapagos Islands and explains that “the islands were colonised by one or more tortoises from mainland...

Cambridge IELTS 12 is the latest IELTS exam preparation.https://draftsbook.com/ will help you to answer all questions in cambridge ielts 12 reading test 2 with detail explanations. 1. A Question: a reference to characteristics that only apply to food production Keywords: characteristics, only, food production We have to find paragraphs which contain information...

Cambridge IELTS 12 is the latest IELTS exam preparation.https://draftsbook.com/ will help you to answer all questions in cambridge ielts 12 reading test 1 with detail explanations. 1. NOT GIVEN Question: The cork oak has the thickest bark of any living tree. Key words: thickest bark In paragraph 1 and paragraph 2, the author mentioned the thick bark of the cork oak...

Cambridge IELTS 11 is the latest IELTS exam preparation. https://draftsbook.com/ will help you to answer all questions in cambridge ielts 11 reading test 4 with detail explanations. PASSAGE 1: RESEARCH USING TWINS QUESTIONS 1-4: DO THE FOLLOWING STATEMENTS AGREE WITH THE INFORMATION GIVEN IN READING PASSAGE? Please note that the answer given at the end of the...

Cambridge IELTS 11 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 11 reading test 3 with detail explanations. PASSAGE 1: THE STORY OF SILK QUESTIONS 1-9: COMPLETE THE NOTES BELOW. Paragraph 1:  Silk is a fine…. Paragraph 2:  Originally, silkworm farming…. Paragraph...

Cambridge IELTS 11 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 11 reading test 2 with detail explanations. PASSAGE 1: RAISING THE MARY ROSE QUESTIONS 1-4: DO THE FOLLOWING STATEMENTS AGREE WITH THE INFORMATION GIVEN IN READING PASSAGE 1? Paragraph 1:  On 19 July,...

Cambridge IELTS 11 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 11 reading test 1 with detail explanations. PASSAGE 1: CROP-GROWING SKYSCRAPERS QUESTIONS 1-7: COMPLETE THE SENTENCES BELOW. 1. SOME FOOD PLANTS, INCLUDING…., ARE ALREADY GROWN INDOORS => Answer: tomatoes...

Cambridge IELTS 10 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 10 reading test 4 with detail explanations. PASSAGE 1: THE MEGAFIRES OF CALIFORNIA QUESTIONS 1-6: COMPLETE THE NOTES BELOW. 1-2. CHARACTERISTICS OF WILDFIRES AND WILDFIRE CONDITIONS TODAY COMPARED TO THE PAST: –...

Cambridge IELTS 10 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 10 reading test 3 with detail explanations. PASSAGE 1: THE CONTEXT, MEANING AND SCOPE OF TOURISM QUESTIONS 1-4: READING PASSAGE HAS FIVE PARAGRAPHS, A-E. 1.PARAGRAPH B: In  this  paragraph, ...

Cambridge IELTS 10 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 10 reading test 2 with detail explanations. PASSAGE 1: TEA AND THE INDUSTRIAL REVOLUTION QUESTIONS 1-7: READING PASSAGE HAS SEVEN PARAGRAPHS, A-G. 1. PARAGRAPH A. In  paragraph  A,  the ...

Cambridge IELTS 10 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 10 reading test 1 with detail explanations. PASSAGE 1: STEPWELLS Paragraph 1: During the sixth and seventh… Paragraph 2: Unique to this region… Paragraph 3: As their name suggests… Paragraph 4: Some wells…. Paragraph...

Cambridge IELTS 9 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 9 reading test 4 with detail explanations. PASSAGE 1: THE LIFE AND WORK OF MARIE CURIE QUESTIONS 1-6: DO THE FOLLOWING STATEMENTS AGREE WITH THE INFORMATION GIVEN IN READING PASSAGE 1 ? 1. MARIE CURIE’S HUSBAND WAS A...

Cambridge IELTS 9 is the latest IELTS exam preparation. READINGIELTS.COM will help you to answer all questions in cambridge ielts 9 reading test 3 with detail explanations. PASSAGE 1: ATTITUDES TO LANGUAGE QUESTIONS 1-8: DO THE FOLLOWING STATEMENTS AGREE WITH THE CLAIMS OF THE WRITER IN READING PASSAGE 1 ? 1. THERE ARE UNDERSTANDABLE REASONS...

Cambridge IELTS 9 is the latest IELTS exam preparation. https://draftsbook.com/ will help you to answer all questions in cambridge ielts 9 reading test 2 with detail explanations. PASSAGE 1: CHILDREN WITH AUDITORY PROBLEMS 1-6. WHICH SECTION CONTAINS THE FOLLOWING INFORMATION? 1. AN ACCOUNT OF A NATIONAL POLICY INITIATIVE. Keywords: national policy initiative...

Cambridge IELTS 9 is the latest IELTS exam preparation.https://draftsbook.com/ will help you to answer all questions in cambridge ielts 9 reading test 1 with detail explanations. PASSAGE 1: WILLIAM HENRY PERKIN QUESTIONS 1-7: DO THE FOLLOWING STATEMENTS AGREE WITH THE INFORMATION GIVEN IN READING PASSAGE 1 ? 1. MICHAEL FARADAY WAS THE FIRST PERSON TO RECOGNISE...

Cambridge IELTS 8 is the latest IELTS exam preparation. https://draftsbook.com/ will help you to answer all questions in cambridge ielts 8 reading test 4 with detail explanations. PASSAGE 1: LAND OF THE RISING SUN QUESTIONS 1 – 5, CHOOSE THE CORRECT HEADING FOR SECTIONS B – F 1.   SECTION B In paragraph B, the writer gives us an overview about lower...