1

Points and Lines, Antialiasing

Line Drawing algorithms
DDA line drawing algorithm
Bresenhams drawing algorithm
Circle generating algorithms
Mid-point Circle algorithm
Parametric Cubic Curves
Bezier curves
B-Spline curves


2
What is Scan conversion ?
What is rasterization ?

3
Point is defined by its coordinates. P(x,y)
Where x- horizontal distance
y-vertical distance.

4

5
0 1 2 3 4 5 6 7 8 9 10 11 12
8
7
6
5
4
3
2
1
?
Line: (3,2) -> (9,6)
Which intermediate
pixels to turn on?
6
Slope-intercept line equation
y = mx + b
Given two end points (x0,y0), (x1, y1), how to
compute m and b?

0 1
0 1
x x
y y
dx
dy
m

= =
(x0,y0)
(x1,y1)
dx
dy 0 * 0 x m y b =
7
Digital Differential Analyzer (DDA) algorithm

1. Read the line end points (x1,y1) & (x2,y2) such that they
are not equal .[If equal then plot that points & exit]
2. [Calculate dx & dy]
dx = x2-x1 & dy = y2-y1
3. [Calculate the length ]
If (dx>= dy) then
length = dx
else
length = dy



8
4. [Calculate increment factor]
x= (x2-x1)/ length
y= (y2-y1)/ length

5. [initialize the initial point on the line ]
x= x1+0.5
y= y1+0.5
Plot (Integer (x), integer (y))

(note : 0.5 is added to round off values instead of truncating values.)







9
6. [obtain the new pixel on the line and plot initial &
new points]
i=1
while (i<= length)
{
x = x + x
y = y + y
Plot (Integer (x), integer (y))
i = i+1
}
7. Stop.

10
i X Y plot
0.5 0.5 (0,0)
1 1.5 1.0 (1,1)
2 2.5 1.5 (2,1)
3 3.5 2.0 (3,2)
4 4.5 2.5 (4,2)
5 5.5 3.0 (5,3)
6 6.6 3.5 (6,3)
7 7.5 4.0 (7,4)
8 8.5 4.5 (8,4)
11
i X Y plot
0.5 0.5 (0,0)
1 -0.5 -0.5 (-1, -1)
2 -1.5 -1.5 (-2,-2)
3 -2.5 -2.5 (-3,-3)
4 -3.5 -3.5 (-4,-4)
5 -4.5 -4.5 (-5,-5)
12
Advantages of DDA Algorithm:
1. It is the simplest algorithm
2. It is faster method for calculating pixel positions
than the direct use of equation.

Disadvantages of DDA Algorithm:
1. Floating point algorithm in DDA algorithm is time
consuming.
2. Because of round off, errors are introduced . Hence
end point accuracy is poor.
13
Bresenhams line drawing algorithm

Bresenhams line drawing algorithm uses only integer
addition , subtraction & multiplication by 2.

This algorithm is used to select optimum raster
locations to represent straight line. To accomplish this
the algorithm always increments either x or y by one
unit depending on the slope of the line. The increment
in other variable is determined by examining the
distance between actual line location & nearest pixel.


14
The distance between actual line location & nearest
pixel is called Decision variable or error.

The error is represented as e= 2y x
Where y=y2-y1 & x =x2-x1

While(e>=0)
{
y=y+1
e=e - 2* x
}
x=x+1
e=e+2* y

15
1. [Initialize the line end points(x1,y1) & (x2,y2) such that
they are not equal. [ If equal then plot that points & exit]]
2. [Calculate x & y]
x = x2-x1 & y = y2-y1
3. [Initialize starting point & decision variable or error term]
x=x1
y=y1
e=2* y x


16
4. [Determine the next pixel on the line & update the error term]
for i=0 to x
Plot (int(x), int(y))
While(e>=0)
{
y=y+1
e=e-2* x
}
x=x+1
e=e+2* y
i=i+1
End for loop
5. Stop.
17
A circle is a set of points that are all at a given distance r
from a center position ( x c , y c ).
The equation for a circle is:


where r is the radius of the circle.
There are circle drawing algorithms, which are based on
either of the following 2 methods :
(1) Polynomial (Cartesian coordinates) method
(2) Trigonometric (polar coordinates) method
2 2 2
r y x = +
18
Method 1:
So, a simple circle drawing algorithm can be written
by solving the equation for y at unit x intervals using:

19
20 0 20
2 2
0
~ = y
20 1 20
2 2
1
~ = y
20 2 20
2 2
2
~ = y
6 19 20
2 2
19
~ = y
0 20 20
2 2
20
~ = y
20
But this is not a best solution!
Firstly, the resulting circle has large gaps
where the slope approaches the vertical
Secondly, the calculations are not very
efficient
The square (multiply) operations
The square root operation
There is a need of more efficient, more
accurate solution.

21
Another way to eliminate the unequal spacing
shown in Fig. is to calculate points along the
circular boundary using polar coordinates r and
Theta.
Expressing the circle equation in parametric polar
form yields the pair of equations

22
When a display is generated with these equations using a
fixed angular step size, a circle is plotted with equally
spaced points along the circumference.
To reduce calculations, large angular separation can be
taken.
For a more continuous boundary on a raster display, set the
angular step size at 1/r .
This plots pixel positions that are approximately one unit
apart.
Although polar coordinates provide equal point spacing,
the trigonometric calculations are still time consuming.

23
The first thing we can notice to make our circle
drawing algorithm more efficient is that circles
centred at (0, 0) have eight-way symmetry

(x, y)
(y, x)
(y, -x)
(x, -y) (-x, -y)
(-y, -x)
(-y, x)
(-x, y)
2
R
24
In the mid-point circle algorithm we use eight-
way symmetry so only calculate the points for
the top right eighth of a circle, and then use
symmetry to get the rest of the points

25

(x
k
+1, y
k
)
(x
k
+1, y
k
-1)
(x
k
, y
k
)
Assume that we have
just plotted point (x
k
, y
k
)
The next point is a
choice between (x
k
+1, y
k
)
and (x
k
+1, y
k
-1)
We would like to choose
the point that is nearest to
the actual circle
So how do we make this
choice?
26
The equation of the circle slightly to give us:

The equation evaluates as follows:





By evaluating this function at the midpoint between the
candidate pixels we can make our decision

>
=
<

, 0
, 0
, 0
) , ( y x f
circ
boundary circle the inside is ) , ( if y x
boundary circle on the is ) , ( if y x
boundary circle the outside is ) , ( if y x
2 2 2
) , ( r y x y x f
circ
+ =
27
Assuming we have just plotted the pixel at (x
k
, y
k
) so
we need to choose between (x
k
+1,y
k
) and (x
k
+1,y
k
-1)
Our decision variable can be defined as:




If p
i
< 0 the midpoint is inside the circle and the pixel
at y
k
is closer to the circle
Otherwise the midpoint is outside and y
k
-1 is closer

28
2 2 2
)
2
1
( ) 1 (
)
2
1
, 1 (
r y x
y x f p
k k
k k circ k
+ + =
+ =
To ensure things are as efficient as possible we can
do all of our calculations incrementally
First consider:



or:


where y
k+1
is either y
k
or y
k
-1 depending on the sign
of p
k

( )
( )
2
2
1
2
1 1 1
2
1
] 1 ) 1 [(
2
1
, 1
r y x
y x f p
k k
k k circ k
+ + + =
+ =
+
+ + +
1 ) ( ) ( ) 1 ( 2
1
2 2
1 1
+ + + + =
+ + + k k k k k k k
y y y y x p p
29
The first decision variable is given as:




Then if p
k
< 0 then the next decision variable is
given as:

If p
k
> 0 then the decision variable is:

r
r r
r f p
circ
=
+ =
=
4
5
)
2
1
( 1
)
2
1
, 1 (
2 2
0
1 2
1 1
+ + =
+ + k k k
x p p
1 2 1 2
1 1
+ + + =
+ + k k k k
y x p p
30
Input radius r and circle centre (x
c
, y
c
), then set the
coordinates for the first point on the circumference of a
circle centred on the origin as:


Calculate the initial value of the decision parameter as:


Starting with k = 0 at each position x
k
, perform the following
test. If p
k
< 0, the next point along the circle centred on
(0, 0) is (x
k
+1, y
k
) and:

) , 0 ( ) , (
0 0
r y x =
r p =
4
5
0
1 2
1 1
+ + =
+ + k k k
x p p
31
Otherwise the next point along the circle is (x
k
+1, y
k
-1)
and:

4. Determine symmetry points in the other seven octants
5. Move each calculated pixel position (x, y) onto the
circular path centred at (x
c
, y
c
) to plot the coordinate
values:

6. Repeat steps 3 to 5 until x >= y
1 1 1
2 1 2
+ + +
+ + =
k k k k
y x p p
c
x x x + =
c
y y y + =
32
To see the mid-point circle algorithm in action lets
use it to draw a circle centred at (0,0) with radius 10

33


9
7
6
5
4
3
2
1
0
8
9 7 6 5 4 3 2 1 0 8 10
10
k p
k

(x
k+1
,y
k+1
)
2x
k+1
2y
k+1
0
1
2
3
4
5
6
34
Use the mid-point circle algorithm to draw the circle
centred at (0,0) with radius 15

35
9
7
6
5
4
3
2
1
0
8
9 7 6 5 4 3 2 1 0 8 10
10
13 12 11 14
15
13
12
14
11
16
15 16
k p
k
(x
k+1
,y
k+1
)
2x
k+1

2y
k+1
0
1
2
3
4
5
6
7
8
9
10
11
12
36