1- DDA Algorithm
The Digital differential analyzer (DDA) algorithm is an
incremental scan-conversion method.
Such an approach is characterized by performing
calculations at each step using results from the
preceding step.
Computer Graphics
Lecture 03
Circle Drawing Technique
What is Circle
A circle is the set of
points in a plane
that are equidistant
from a given point
O. The distance r
from the center is
called the radius,
and the point O is
called the center.
Reduction in Calculations
Symmetry in octants
Upper half circle symmetric to lower half
circle
Left half circle symmetric to right half
circle
Finally two halves of the same quarters are
symmetric to each other
Eight Octants Symmetry
Circle Drawing Technique
- Input for circle drawing
. one center point (xc, yc)
and
. radius r
Now, using these two inputs to draw a circle.
Midpoint Circle Algorithm
Circle function tests are
performed for the midpoints
between pixels near the circle
path at each sampling step.
Consider only the first octant of a
circle of radius r centered on
the origin.
We begin by plotting point (0,
r) and end when x = y.
Midpoint Circle Algorithm
X2- Y2 - r2 =0 X=Y
The decision at each step is whether to choose :
the pixel to the right of the current pixel
or
the pixel which is to the right and below the current pixel
(8-way stepping)
Assume:
P = (xk, yk) is the current pixel.
Q = (xk+1, yk) is the pixel to the right. E
R = (xk+1, yk -1) is the pixel to the right and below .SE
Midpoint Circle Algorithm
To apply the midpoint method, we define a circle function:
fcircle(x, y) = x2 + y2 – r2
The following relations can be observed:
f circle (x, y) < 0,if (x, y) is inside the circle boundary
f circle (x, y) = 0,if (x, y) is on the circle boundary
f circle (x, y) > 0,if (x, y) is outside the circle boundary
Midpoint Circle Algorithm
the midpoint between the two candidate
pixels at sampling position xk+1.
Our decision parameter is the circle
function evaluated at the midpoint
between these two pixels:
Where yk+1 is either yk or yk-1, depending on
the sign of Pk.
Decision Parameter
If pk < 0,
this midpoint is inside the circle and the pixel on
scan line yk is closer to the circle boundary.
Otherwise, the mid position is outside or on the
circle boundary, and we select the pixel on scan-
line yk-1.
Pk = f circle ( xk + 1, yk - ½ )
P = ( x + 1 ) 2 + ( y - ½ ) 2 – r 2 ……...(1)
Decision Parameter
Therefore, if Pk < 0 or negative then
yk+1 will be yk
and the formula to calculate Pk+1 will be:
Pk+1 = Pk + 2( xk + 1 ) + ( y2k - y2k ) – ( yk - yk ) + 1
Pk+1 = Pk + 2( xk + 1 ) + 1
Decision Parameter
Otherwise, if Pk > 0 or positive
then yk+1 will be yk-1
and the formula to calculate Pk+1 will be:
Pk+1 = Pk + 2( xk + 1 ) + [ (y k -1)2 - y2k ] – (yk -1- yk ) + 1
Pk+1 = Pk + 2(xk + 1) + (y2 k - 2 y k +1 - y2k )
– ( yk -1- yk ) + 1
Pk+1 = Pk + 2( xk + 1 ) - 2 y k + 1 + 1 +1
Pk+1 = Pk + 2( xk + 1 ) - 2 y k + 2 +1
Pk+1 = Pk + 2( xk + 1 ) - 2 ( y k – 1 ) + 1
Decision Parameter
Now a similar case that we observed in line
algorithm is that how would starting Pk be
calculated.
For this, the starting pixel position will be (0, r).
Therefore, putting this value in equation, we get
Decision Parameter
P0 = ( 0 + 1 ) 2 + ( r - ½ ) 2 – r 2
P0 = 1 + r2 - r + ¼ – r 2
P0 = 5/4 – r
If radius r is specified as an integer, we can simply round p0
to:
P0 = 1 – r
Since all increments are integer.
Finally the algorithm can be summed up as :
Algorithm
MidpointCircle (xcenter, ycenter, radius)
x = 0;
y = r;
p = 1 - r;
do
DrawSymmetricPoints (xcenter, ycenter, x, y)
x=x+1
If p < 0 Then
p=p+2*(x+1)+1
else
y=y-1
p = p + 2 * ( x+ 1) –2 ( y – 1 ) + 1
while ( x < y )
Example
Example to calculate first octant of the circle using
midpoint algorithm
p point
Example Cont…
Behaviour of
calculated points
around the circle is
observable
calculate first octant of the circle using midpoint
algorithm
R=9
Center=(2,1)
calculate first octant of the circle using midpoint
algorithm
R=5
Center=(3,2)