Description

Department of Computer Science and Engineering
Course Code: CSE 423 Credits: 1.5
Course Name: Computer Graphics Semester: Fall 18

Lab 03
Midpoint Circle Drawing Algorithm
I. Topic Overview:
The students were introduced to the Midpoint line drawing algorithm in the previous class. Given, the coordinates of any two points on the line: (x1, y1) & (x2, y2), the student’s task was to find all the intermediate points required for drawing the line on the computer screen of pixels where every pixel has integer coordinates.

Today, we would be introducing a similar approach to draw a circle. This algorithm tries to find the best approximation of the next point on the circle using a decision parameter. As we will only choose one between two pixels as we did previously in the midpoint line drawing algorithm it will be a quite fast approach.

We would be drawing a part of the circle let’s say only the zone 0. The students might think that they might have to generate 8 different equations for eight different zones. However, we will be applying the 8-way symmetry approach to draw the portion of the circle for the rest of the zones.

II. Lesson Fit:
a. Implementation of Midpoint circle drawing algorithm using 8-way symmetry.
b. The students should have a clear understanding of the 8-way symmetry approach.
c. They should also have a clear idea about all the different zones.

III. Learning Outcome:
After this lecture, the students will be able to:
a. Learn how to use a decision parameter to determine the next pixel on the circle.
b. Learn how 8-way symmetry approach naturally helps to draw a circle.

2
IV. Anticipated Challenges and Possible Solutions
Students might get confused about why and how we are using the 8-way symmetry approach.
Solutions:
Students should understand why and how we are drawing a point of a particular point to another zone and in which zone the calculation are being done for drawing the circle.

V. Acceptance and Evaluation
Students will start implementing the algorithm after we finish our lecture. If a student fails to complete the implementation he/she will have to complete by that night and show it to the class teacher on his/her consultation period. If a student also fails to do that then instead of 10 we will evaluate the student on 7.
1. Lab evaluation marks: out of 10
2. Late Lab evaluation marks: out of 7

VI. Activity Detail
a. Hour 1:
Discussion:

A circle is defined as a set of points that are all at a given distance r from a center positioned at (xc,y c).

So, the equation of circle according to the center (xc,y c) is,
(x − xc)2 + (y − yc)2 = r2 ………………. 1
from equation 1 we get the value of y as below,

(y = yc ± √r2 − (x − xc)2 ……………….. 2
As f(x,y) = 0represents a circle, Let,
f(x,y) = (x − xc)2 + (y − yc)2 − r2 …….. 3
3
Now, for any point, f(x,y) = 0, the point is on the circle f(x,y) > 0, the point is outside the circle f(x,y) < 0, the point is inside the circle

In midpoint circle drawing algorithm at each of the ith step we will be evaluating the circle function to come to a decision. Let us assume that we are giving unit increments to x in the plotting process and determining the y position using this algorithm. Assuming we have just plotted the ith pixel at (xi,y i) , we next need to determine whether the pixel at the position (xi+1 ,yi) or the one at (xi,y i+1) is closer to the circle.

4

Our decision parameter di at the ith step is the circle function evaluated at the midpoint of these two pixels. The coordinates of the midpoint of these two pixels is (xi − 12,yi + 1).

Hence, di = f(xi − 12,yi + 1) = (xi − 12)2 + (yi + 1)2 − r2 …………….. 4

Successive decision parameters are obtained using incremental calculations, thus avoiding a lot of computation at each step. We obtain a recursive expression for the next decision parameter.
Therefore, di+1 = f(xi+1 − 12,yi+1 + 1) = (xi+1 − 12)2 + (yi + 1 + 1)2 − r2 di+1 = (xi+1 − 12)2 + (yi + 2)2 − r2 ……………………….. 5
Now we get by subtracting eqn (4) from eqn (5)
Δd = di+1 − di
Δd = (xi+1 − 12)2 − (xi − 12)2 + (yi + 2)2 − (yi + 1)2 − r2 + r2
Δd = (xi+1 + xi − 1).(xi+1 − xi) + 2yi + 3 ……………………. 6
Now if di <= 0, then the midpoint of the two possible pixels lies within the circle, thus north pixel is nearer to the theoretical circle.
Hence, xi+1 = xi . Substituting this value of in eqn (6), we get,
Δd = di+1 − di = (xi + xi − 1).(xi − xi) + 2yi + 3 di+1 − di = (xi + xi − 1).0 + 2yi + 3 di+1 = di + 2yi + 3
And if we consider di > 0 then, the midpoint of the two possible pixels lies outside the circle, so the north west pixel is nearer to the theoretical circle.
Therefore, xi+1 = xi − 1 . Substituting this value of in eqn (6), we get,
Δd = di+1 − di = (xi − 1 + xi − 1).(xi − 1 − xi) + 2yi + 3 di+1 − di = (2xi − 2).(− 1) + 2yi + 3 di+1 = di − 2xi + 2 + 2yi + 3 di+1 = di − 2xi + 2yi + 5
For the initial decision parameter x = r, y = 0. So, from eqn (4) we get,
d0 = (r − 12)2 + (0 + 1)2 − r2 d0 = 54 − r
To get the integer value of pixel coordinates, we approximate,
d0 = 1 − r …………………………………………………. 7

b. Hour: 2
Discussion: 8-way Symmetry
Today we will go through the 8-way symmetry approach and we will discuss how we can apply this approach to draw a circle easily.

c. Hour: 3
Discussion: Implementation
Now we will be implementing the midpoint circle algorithm in the lab.

VII. Home tasks