Computer Aided Design (3161903) LAB Manual

EXPERIMENT – 1

Aim: To prepare a program for drawing lines and circle using algorithm.
Objectives: Identify the Line Drawing algorithms of computer graphics.
Outcomes: Implement computer graphics programs in C++ using the line drawing algorithms.
Introduction:
DDA (Digital Differential Analyzer) is a line drawing algorithm used in computer graphics to generate
a line segment between two specified endpoints. It is a simple and efficient algorithm that works by
using the incremental difference between the x-coordinates and y-coordinates of the two endpoints to
plot the line.

The steps involved in DDA line generation algorithm are:

 Input the two endpoints of the line segment, (x1,y1) and (x2,y2).
 Calculate the difference between the x-coordinates and y-coordinates of the endpoints as dx
and dy respectively.
 Calculate the slope of the line as m = dy/dx.
 Set the initial point of the line as (x1,y1).
 Loop through the x-coordinates of the line, incrementing by one each time, and calculate the
corresponding y-coordinate using the equation y = y1 + m(x – x1).
 Plot the pixel at the calculated (x,y) coordinate.
 Repeat steps 5 and 6 until the endpoint (x2,y2) is reached.
DDA algorithm is relatively easy to implement and is computationally efficient, making it suitable for
real-time applications. However, it has some limitations, such as the inability to handle vertical lines
and the need for floating-point arithmetic, which can be slow on some systems. Nonetheless, it remains
a popular choice for generating lines in computer graphics.
In any 2-Dimensional plane, if we connect two points (x0, y0) and (x1, y1), we get a line segment. But
in the case of computer graphics, we cannot directly join any two coordinate points, for that, we should
calculate intermediate points’ coordinates and put a pixel for each intermediate point, of the desired
color with the help of functions like putpixel(x, y, K) in C, where (x,y) is our co-ordinate and K denotes
some color.
Examples:

Input: For line segment between (2, 2) and (6, 6) :

Output: we need (3, 3) (4, 4) and (5, 5) as our intermediate points.

Input: For line segment between (0, 2) and (0, 6) :

Output: we need (0, 3) (0, 4) and (0, 5) as our intermediate points.

S. N. Patel Ins tute of Technology & Research Centre, Umrakh.

Asst. Prof. Nilesh Rana (Mechanical Department)
Computer Aided Design (3161903) LAB Manual
For using graphics functions, our system output screen is treated as a coordinate system where the
coordinate of the top-left corner is (0, 0) and as we move down our y-ordinate increases, and as we
move right our x-ordinate increases for any point (x, y). Now, for generating any line segment we need
intermediate points and for calculating them we can use a basic algorithm called DDA(Digital
differential analyzer) line generating algorithm.
DDA Algorithm:
Consider one point of the line as (X0, Y0) and the second point of the line as (X1, Y1).
// calculate dx , dy
dx = X1 – X0;
dy = Y1 – Y0;

// Depending upon absolute value of dx & dy

// choose number of steps to put pixel as

// steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy)

steps = abs(dx) > abs(dy) ? abs(dx) : abs(dy);

// calculate increment in x & y for each steps

Xinc = dx / (float) steps;

Yinc = dy / (float) steps;

// Put pixel for each step

X = X0;
Y = Y0;

for (int i = 0; i <= steps; i++)

{
putpixel (round(X),round(Y),WHITE);
X += Xinc;
Y += Yinc;
}

S. N. Patel Ins tute of Technology & Research Centre, Umrakh.

Asst. Prof. Nilesh Rana (Mechanical Department)
Computer Aided Design (3161903) LAB Manual

Flowchart for DDA Line Drawing Algorithm:

Advantages of DDA Algorithm:

 It is a simple and easy-to-implement algorithm.

 It avoids using multiple operations which have high time complexities.
 It is faster than the direct use of the line equation because it does not use any floating point
multiplication and it calculates points on the line.
Disadvantages of DDA Algorithm:

 It deals with the rounding off operation and floating point arithmetic so it has high time
complexity.
 As it is orientation-dependent, so it has poor endpoint accuracy.
 Due to the limited precision in the floating point representation, it produces a cumulative error.

Bresenham’s Line Generation Algorithm

Given the coordinate of two points A(x1, y1) and B(x2, y2). The task is to find all the intermediate
points required for drawing line AB on the computer screen of pixels. Note that every pixel has integer
coordinates.

Below are some assumptions to keep the algorithm simple.

 We draw lines from left to right.

 x1 < x2 and y1< y2
 Slope of the line is between 0 and 1. We draw a line from lower left to upper right.

S. N. Patel Ins tute of Technology & Research Centre, Umrakh.

Asst. Prof. Nilesh Rana (Mechanical Department)
Computer Aided Design (3161903) LAB Manual
The idea of Bresenham’s algorithm is to avoid floating point multiplication and addition to compute mx
+ c, and then compute the round value of (mx + c) in every step. In Bresenham’s algorithm, we move
across the x-axis in unit intervals.
We always increase x by 1, and we choose about next y, whether we need to go to y+1 or remain on y.
In other words, from any position (Xk, Yk) we need to choose between (Xk + 1, Yk) and (Xk + 1, Yk
+ 1).

We would like to pick the y value (among Yk + 1 and Yk) corresponding to a point that is closer to the
original line.
We need a decision parameter to decide whether to pick Yk + 1 or Yk as the next point. The idea is to
keep track of slope error from the previous increment to y. If the slope error becomes greater than 0.5,
we know that the line has moved upwards one pixel and that we must increment our y coordinate and
readjust the error to represent the distance from the top of the new pixel – which is done by subtracting
one from the error.

Flowchart for Bresenhams’s Line Drawing Algorithm:

S. N. Patel Ins tute of Technology & Research Centre, Umrakh.

Asst. Prof. Nilesh Rana (Mechanical Department)
Computer Aided Design (3161903) LAB Manual
How to avoid floating point arithmetic
The above algorithm still includes floating point arithmetic. To avoid floating point arithmetic, consider
the value below value m.
m = (y2 – y1)/(x2 – x1)
We multiply both sides by (x2 – x1)
We also change slope_error to slope_error * (x2 – x1). To avoid comparison with 0.5, we further change
it to slope_error * (x2 – x1) * 2.
Also, it is generally preferred to compare with 0 than 1.

Advantages of Bresenham Line Drawing Algorithm-

 It is easy to implement.
 It is fast and incremental.
 It executes fast but less faster than DDA Algorithm.
 The points generated by this algorithm are more accurate than DDA Algorithm.
 It uses fixed points only.

Bresenham’s circle drawing algorithm

It is not easy to display a continuous smooth arc on the computer screen as our computer screen is made
of pixels organized in matrix form. So, to draw a circle on a computer screen we should always choose
the nearest pixels from a printed pixel so as they could form an arc.
Bresenham’s circle drawing algorithm

This algorithm uses the key feature of circle that it is highly symmetric. So, for whole 360 degree of
circle we will divide it in 8-parts each octant of 45 degree. In order to do that we will use Bresenham’s
Circle Algorithm for calculation of the locations of the pixels in the first octant of 45 degrees. It assumes
that the circle is centered on the origin. So for every pixel (x, y) it calculates, we draw a pixel in each
of the 8 octants of the circle as shown below :

S. N. Patel Ins tute of Technology & Research Centre, Umrakh.

Asst. Prof. Nilesh Rana (Mechanical Department)
Computer Aided Design (3161903) LAB Manual
For a pixel (x,y), all possible pixels in 8 octants
For a pixel (x,y), all possible pixels in 8 octants
Now, we will see how to calculate the next pixel location from a previously known pixel location (x,
y). In Bresenham’s algorithm at any point (x, y) we have two option either to choose the next pixel in
the east i.e. (x+1, y) or in the south east i.e. (x+1, y-1).

And this can be decided by using the decision parameter d as:

If d > 0, then (x+1, y-1) is to be chosen as the next pixel as it will be closer to the arc.
else (x+1, y) is to be chosen as next pixel.
Now to draw the circle for a given radius ‘r’ and centre (xc, yc) We will start from (0, r) and move in
first quadrant till x=y (i.e. 45 degree). We should start from listed initial condition:
d = 3 - (2 * r)
x=0
y=r
Now for each pixel, we will do the following operations:
1. Set initial values of (xc, yc) and (x, y)
2. Set decision parameter d to d = 3 – (2 * r).
3. call drawCircle(int xc, int yc, int x, int y) function.
4. Repeat steps 5 to 8 until x < = y
5. Increment value of x.
6. If d < 0, set d = d + (4*x) + 6
7. Else, set d = d + 4 * (x – y) + 10 and decrement y by 1.
8. call drawCircle(int xc, int yc, int x, int y) function

Computer Program for the above algorithm:

// C-program for circle drawing
// using Bresenham’s Algorithm
S. N. Patel Ins tute of Technology & Research Centre, Umrakh.
Asst. Prof. Nilesh Rana (Mechanical Department)
Computer Aided Design (3161903) LAB Manual
// in computer-graphics
#include <stdio.h>
#include <dos.h>
#include <graphics.h>

// Function to put pixels

// at subsequence points
void drawCircle(int xc, int yc, int x, int y)
{
putpixel(xc+x, yc+y, RED);
putpixel(xc-x, yc+y, RED);
putpixel(xc+x, yc-y, RED);
putpixel(xc-x, yc-y, RED);
putpixel(xc+y, yc+x, RED);
putpixel(xc-y, yc+x, RED);
putpixel(xc+y, yc-x, RED);
putpixel(xc-y, yc-x, RED);
}

// Function for circle-generation

// using Bresenham's algorithm
void circleBres(int xc, int yc, int r)
{
int x = 0, y = r;
int d = 3 - 2 * r;
drawCircle(xc, yc, x, y);
while (y >= x)
{
// for each pixel we will
// draw all eight pixels

x++;

S. N. Patel Ins tute of Technology & Research Centre, Umrakh.

Asst. Prof. Nilesh Rana (Mechanical Department)
Computer Aided Design (3161903) LAB Manual

// check for decision parameter

// and correspondingly
// update d, x, y
if (d > 0)
{
y--;
d = d + 4 * (x - y) + 10;
}
else
d = d + 4 * x + 6;
drawCircle(xc, yc, x, y);
delay(50);
}
}
// Driver code
int main()
{
int xc = 50, yc = 50, r = 30;
int gd = DETECT, gm;
initgraph(&gd, &gm, ""); // initialize graph
circleBres(xc, yc, r); // function call
return 0;
}
Advantages:

 It is a simple algorithm.
 It can be implemented easily
 It is totally based on the equation of circle i.e. x2 +y2 =r2
Disadvantages:

 There is a problem of accuracy while generating points.

 This algorithm is not suitable for complex and high graphic images.

S. N. Patel Ins tute of Technology & Research Centre, Umrakh.

Asst. Prof. Nilesh Rana (Mechanical Department)
Computer Aided Design (3161903) LAB Manual
Exercises:
1. Write a computer program to draw a line with any start and end points coordinates using DDA line
algorithm.

2. Write a computer program to draw a line using Bresenham’s line algorithm.

3. Write a computer program to plot a circle using Bresenham’s circle algorithm.

S. N. Patel Ins tute of Technology & Research Centre, Umrakh.

Asst. Prof. Nilesh Rana (Mechanical Department)