Samara University

College of Engineering and Technology

Department of Computer Science

Computer Graphics(CoSc3121)

Chapter Two
Graphics Primitives

1
 Points and Lines
 Point plotting is done by converting a single coordinate position furnished by an
application program into appropriate operations for the output device in use.
 Line drawing is done by calculating intermediate positions along the line path between
two specified endpoint positions.
 The output device is then directed to fill in those positions between the end points with
some color.
 For some device such as a pen plotter or random scan display, a straight line can be
drawn smoothly from one end point to other.
 Digital devices display a straight line segment by plotting discrete points between the
two endpoints.
 Discrete coordinate positions along the line path are calculated from the equation of the
line.
 For a raster video display, the line intensity is loaded in frame buffer at the
corresponding pixel positions.
 Reading from the frame buffer, the video controller then plots the screen pixels.
 Screen locations are referenced with integer values, so plotted positions may only
approximate actual line positions between two specified endpoints.

2
 Points and Lines…
 For example line position of (12.36, 23.87) would be converted to pixel position (12, 24).
 This rounding of coordinate values to integers causes lines to be displayed with a stair
step appearance as represented in fig 2.1.

Fig. 2.1: - Stair step effect produced when line is generated as a series of pixel positions.

 The stair step shape is noticeable in low resolution system, and we can improve their
appearance somewhat by displaying them on high resolution system.
 More effective techniques for smoothing raster lines are based on adjusting pixel
intensities along the line paths.
 For raster graphics device-level algorithms discuss here, object positions are specified
directly in integer device coordinates.
 Pixel position will referenced according to scan-line number and column number
which is illustrated by following figure. 3
 Points and Lines…

Fig. 2.2: - Pixel positions referenced by scan-line number and column number.

 To load the specified color into the frame buffer at a particular position, we will assume
we have available low-level procedure of the form 𝑠𝑒𝑡𝑝𝑖𝑥𝑒𝑙(𝑥, 𝑦).
 Similarly for retrieve the current frame buffer intensity we assume to have procedure
𝑔𝑒𝑡𝑝𝑖𝑥𝑒𝑙(𝑥, 𝑦).

4
 Line Drawing Algorithms
Lines are a very common primitive and will be supported by almost all graphics
packages. In addition, lines form the basis of more complex primitives such as polylines
(a connected sequence of straight-line segments) or polygons (2-D objects formed by
straight-line edges).
Lines are normally represented by the two end-points of the line, and points (x,y) along
the line must satisfy the following slope-intercept equation:

y = mx + c ……………………………………………… (1)

where m is the slope or gradient of the line, and c is the coordinate at which the line
intercepts the y-axis. Given two end-points (x0,y0) and (xend,yend), we can calculate values
for m and c as follows:
 y  y 0  …………………………………… (2)
m  end
xend  x0 
c  y  mx ……………………………………
0 0
(3)
Furthermore, for any given x-interval δx, we can calculate the corresponding y-interval δy:
δy = m.δx …………………………………………….. (4)
δx = (1/m).δy …………………………………………… (5)

 These equations form the basis of the two line-drawing algorithms described below: the
DDA algorithm and Bresenham’s algorithm. 5
 DDA Algorithm
The Digital Differential Analyser (DDA) algorithm operates by starting at one end-point
of the line, and then using Eqs. (4) and (5) to generate successive pixels until the second
end-point is reached. Therefore, first, we need to assign values for δx and δy.

Before we consider the actual DDA algorithm, let us consider a simple first approach to
this problem. Suppose we simply increment the value of x at each iteration (i.e. δx = 1),
and then compute the corresponding value for y using Eqs. (2) and (4). This would
compute correct line points but, as illustrated by Fig 2.3, it would leave gaps in the line.
The reason for this is that the value of δy is greater than one, so the gap between
subsequent points in the line is greater than 1 pixel.

Figure 2.3 – ‘Holes’ in a Line Drawn by Incrementing x and Computing the

Corresponding y-Coordinate
6
 DDA Algorithm…
The solution to this problem is to make sure that both δx and δy have values less than or
equal to one. To ensure this, we must first check the size of the line gradient. The conditions
are:
 If |m| ≤ 1:
o δx = 1
o δy = m
 If |m| > 1:
o δx = 1/m
o δy = 1
Once we have computed values for δx and δy, the basic DDA algorithm is:
 Start with (x0,y0)
 Find successive pixel positions by adding on (δx, δy) and rounding to the nearest integer,
i.e.
o xk+1 = xk + δx
o yk+1 = yk + δy
 For each position (xk,yk) computed, plot a line point at (round(xk),round(yk)), where the
round function will round to the nearest integer.

Note that the actual pixel value used will be calculated by rounding to the nearest integer, but
we keep the real-valued location for calculating the next pixel position.
7
 DDA Algorithm…
Let us consider an example of applying the DDA algorithm for drawing a straight-line
segment. Referring to see Fig 2.4, we first compute a value for the gradient m:
 yend  y 0  (13  10) 3
m    0.6
xend  x0  (15  10) 5
Now, because |m| ≤ 1, we compute δx and δy as follows:

δx = 1
δy = 0.6

Using these values of δx and δy we can now start to plot line points:
 Start with (x0,y0) = (10,10) – colour this pixel
 Next, (x1,y1) = (10+1,10+0.6) = (11,10.6) – so we colour pixel (11,11)
 Next, (x2,y2) = (11+1,10.6+0.6) = (12,11.2) – so we colour pixel (12,11)
 Next, (x3,y3) = (12+1,11.2+0.6) = (13,11.8) – so we colour pixel (13,12)
 Next, (x4,y4) = (13+1,11.8+0.6) = (14,12.4) – so we colour pixel (14,12)
 Next, (x5,y5) = (14+1,12.4+0.6) = (15,13) – so we colour pixel (15,13)
 We have now reached the end-point (xend,yend), so the algorithm terminates

8
 DDA Algorithm…

Figure 2.4 The Operation of the DDA Line-

Drawing Algorithm

The DDA algorithm is simple and easy to implement, but it does involve floating point
operations to calculate each new point. Floating point operations are time-consuming
when compared to integer operations. Since line-drawing is a very common operation in
computer graphics, it would be nice if we could devise a faster algorithm which uses
integer operations only. The next section describes such an algorithm.
Advantages of DDA algorithm
 It is faster algorithm.
 It is simple algorithm.
Disadvantage of DDA algorithm
 Floating point arithmetic is time consuming.
 Poor end point accuracy. 9
 Bresenham’s Line Algorithm
Bresenham’s line-drawing algorithm provides significant improvements in efficiency over
the DDA algorithm. These improvements arise from the observation that for any given line,
if we know the previous pixel location, we only have a choice of 2 locations for the next
pixel. This concept is illustrated in Fig 2.5 given that we know (xk,yk) is a point on the line,
we know the next line point must be either pixel A or pixel B. Therefore we do not need to
compute the actual floating-point location of the ‘true’ line point; we need only make a
decision between pixels A and B.

Figure 2.5- Bresenham's Line-Drawing

Algorithm

Bresenham’s algorithm works as follows. First, we denote by dupper and dlower the
distances between the centres of pixels A and B and the ‘true’ line (see Fig 2.5). Using
Eq. (1) the ‘true’ y-coordinate at xk+1 can be calculated as:

10
 Bresenham’s Line Algorithm…
y  m( xk  1)  c …………………………………………………………… (6)

Therefore we compute dlower and dupper as:

dlower  y  yk  m( xk  1)  c  yk …………………………………………… (7)

dupper  ( yk  1)  y  yk  1  m( xk  1)  c …………………………………(8)

Now, we can decide which of pixels A and B to choose based on comparing the values
of dupper and dlower:
 If dlower > dupper, choose pixel A
 Otherwise choose pixel B

We make this decision by first subtracting dupper from dlower:

d lower  d upper  2mxk  1  2 yk  2c  1 …………………………………… (9)

11
 Bresenham’s Line Algorithm…
If the value of this expression is positive we choose pixel A; otherwise we choose pixel B.
The question now is how we can compute this value efficiently. To do this, we define a
decision variable pk for the kth step in the algorithm and try to formulate pk so that it can
be computed using only integer operations. To achieve this, we substitute m  y / x
(where Δx and Δy are the horizontal and vertical separations of the two line end-
points) and define pk as:

pk  x(d lower  d upper )  2yxk  2xyk  d …………………………… (10)

where d is a constant that has the value 2y  2cx  x

Note that the sign of pk will be the same as the sign of (dlower – dupper), so if pk is positive
we choose pixel A and if it is negative we choose pixel B. In addition, pk can be
computed using only integer calculations, making the algorithm very fast compared to
the DDA algorithm.

An efficient incremental calculation makes Bresenham’s algorithm even faster. (An

incremental calculation means we calculate the next value of pk from the last one.)
Given that we know a value for pk, we can calculate pk+1 from Eq. (10) by observing that

12
 Bresenham’s Line Algorithm…
 Always xk+1 = xk+1
 If pk < 0, then yk+1 = yk, otherwise yk+1 = yk+1

Therefore we can define the incremental calculation as:

p k 1  p k  2y if pk < 0 …………………………………………… (11)

p k 1  p k  2y  2x if pk ≥ 0 …………………………………………… (12)

The initial value for the decision variable, p0, is calculated by substituting xk = x0 and yk =
y0 into Eq. (10), which gives the following simple expression:

p0  2y  x …………………………………………………………… (13)

So we can see that we never need to compute the value of the constant d in Eq. (10).

13
Bresenham’s Line Algorithm…

14
Bresenham’s Line Algorithm…

 We can see that the

algorithm plots exactly
the same points as the
DDA algorithm but it
computes them using
only integer operations.
For this reason,
Bresenham’s algorithm is
the most popular choice
for line-drawing in
computer graphics.
15
 Circle

Fig. 2.7: - Circle with center coordinates (𝑥𝑐, 𝑦𝑐) and radius 𝑟.
 A circle is defined as the set of points that are all at a given distance r from a center
position say (𝑥𝑐, 𝑦𝑐).
Properties of Circle

 The distance relationship is expressed by the Pythagorean theorem in Cartesian

coordinates as:
 (𝑥 − 𝑥𝑐)2 + (𝑦 − 𝑦𝑐)2 = 𝑟2
 We could use this equation to calculate circular boundary points by incrementing
1 in 𝑥 direction in every steps from 𝑥𝑐 – 𝑟 to 𝑥𝑐 + 𝑟 and calculate corresponding 𝑦
values at each position as:

16
 Circle…
(𝑥 − 𝑥𝑐)2 + (𝑦 − 𝑦𝑐)2 = 𝑟2
(𝑦 − 𝑦𝑐)2 = 𝑟2 − (𝑥 − 𝑥𝑐)2
(𝑦 − 𝑦𝑐) = ± 𝑟2 −(𝑥𝑐− 𝑥)2
y = 𝑦𝑐 ± 𝑟2 −(𝑥𝑐− 𝑥)2
 But this is not best method for generating a circle because it requires more
number of calculations which take more time to execute.
 And also spacing between the plotted pixel positions is not uniform as shown
in figure below.

Fig. 2.8: - Positive half of circle showing non uniform spacing bet calculated
pixel positions.

17
 Circle…
 We can adjust spacing by stepping through 𝑦 values and calculating 𝑥 values
whenever the absolute value of the slop of the circle is greater than 1. But it will
increases computation processing requirement.
 Another way to eliminate the non-uniform spacing is to draw circle using polar
coordinates ‘𝑟’ and ‘q ’.
 Calculating circle boundary using polar equation is given by pair of equations which
is as follows.
𝑥 = 𝑥𝑐 + 𝑟 cos q
𝑦 = 𝑦𝑐 + 𝑟 sin q
 When display is produce using these equations using fixed angular step size circle is
plotted with uniform spacing.
 The step size ‘q ’ is chosen according to application and display device.
 For a more continuous boundary on a raster display we can set the step size at 1/𝑟.
This plot pixel position that are approximately one unit apart.
 Computation can be reduced by considering symmetry city property of circles. The
shape of circle is similar in each quadrant.
 We can obtain pixel position in second quadrant from first quadrant using reflection
about 𝑦 axis and similarly for third and fourth quadrant from second and first
respectively using reflection about 𝑥 axis.

18
 Circle…
 We can take one step further and note that there is also symmetry between octants.
Circle sections in adjacent octant within one quadrant are symmetric with respect to
the 450 line dividing the two octants.
 This symmetry condition is shown in figure below where point (𝑥, 𝑦) on one circle
sector is mapped in other seven sector of circle.

Fig. 2.9: - symmetry of circle.

19
 Circle…
 Taking advantage of this symmetry property of circle we can generate all pixel
position on boundary of circle by calculating only one sector from 𝑥 = 0 to 𝑥 = 𝑦.
 Determining pixel position along circumference of circle using any of two equations
shown above still required large computation.
 More efficient circle algorithm are based on incremental calculation of decision
parameters, as in the Bresenham line algorithm.
 Bresenham’s line algorithm can be adapted to circle generation by setting decision
parameter for finding
 closest pixel to the circumference at each sampling step.
 The Cartesian coordinate circle equation is nonlinear so that square root evaluations
would be required to compute pixel distance from circular path.
 Bresenham’s circle algorithm avoids these square root calculation by comparing the
square of the pixel separation distance.
 A method for direct distance comparison to test the midpoint between two pixels to
determine if this midpoint is inside or outside the circle boundary.
 This method is easily applied to other conics also.
 Midpoint approach generates same pixel position as generated by bresenham’s circle
algorithm.
 The error involve in locating pixel positions along any conic section using midpoint
test is limited to one- half the pixel separation.
20
 Midpoint Circle Algorithm
 Taking advantage of this symmetry property of circle we can generate all pixel
position on boundary of circle by calculating only one sector from 𝑥 = 0 to 𝑥 = 𝑦.
 Determining pixel position along circumference of circle using any of two equations
shown above still required large computation.
 More efficient circle algorithm are based on incremental calculation of decision
parameters, as in the Bresenham line algorithm.
 Bresenham’s line algorithm can be adapted to circle generation by setting decision
parameter for finding
 closest pixel to the circumference at each sampling step.
 The Cartesian coordinate circle equation is nonlinear so that square root evaluations
would be required to compute pixel distance from circular path.
 Bresenham’s circle algorithm avoids these square root calculation by comparing the
square of the pixel separation distance.
 A method for direct distance comparison to test the midpoint between two pixels to
determine if this midpoint is inside or outside the circle boundary.
 This method is easily applied to other conics also.
 Midpoint approach generates same pixel position as generated by bresenham’s circle
algorithm.
 The error involve in locating pixel positions along any conic section using midpoint
test is limited to one- half the pixel separation.
21
 Midpoint Circle Algorithm…
 Similar to raster line algorithm we sample at unit interval and determine the
closest pixel position to the specified circle path at each step.
 Given radius ‘𝑟’ and center (𝑥𝑐, 𝑦𝑐)
 We first setup our algorithm to calculate circular path coordinates for center (0, 0).
And then we will transfer calculated pixel position to center (𝑥𝑐, 𝑦𝑐) by adding 𝑥𝑐
to 𝑥 and 𝑦𝑐 to 𝑦.
 Along the circle section from 𝑥 = 0 to 𝑥 = 𝑦 in the first quadrant, the slope of the
curve varies from 0 to -1 so we can step unit step in positive 𝑥 direction over this
octant and use a decision parameter to determine which of the two possible 𝑦
position is closer to the circular path.
 Position in the other seven octants are then obtain by symmetry.
 For the decision parameter we use the circle function which is:
𝑓𝑐𝑖𝑟𝑐𝑙𝑒(𝑥, 𝑦) = 𝑥2 + 𝑦2 − 𝑟2
 Any point which is on the boundary is satisfied 𝑓𝑐𝑖𝑟𝑐𝑙𝑒(𝑥, 𝑦) = 0 if the point is inside
circle function value is negative and if point is outside circle the function value is
positive which can be summarize as below.
𝑓𝑐𝑖𝑟𝑐𝑙𝑒(𝑥, 𝑦) < 0 𝑖𝑓 (𝑥, 𝑦)𝑖𝑠 𝑖𝑛𝑠𝑖𝑑𝑒 𝑡ℎ𝑒 𝑐𝑖𝑟𝑐𝑙𝑒 𝑏𝑜𝑢𝑛𝑑𝑎𝑟𝑦
𝑓𝑐𝑖𝑟𝑐𝑙𝑒(𝑥, 𝑦) = 0 𝑖𝑓 (𝑥, 𝑦)𝑖𝑠 𝑜𝑛 𝑡ℎ𝑒 𝑐𝑖𝑟𝑐𝑙𝑒 𝑏𝑜𝑢𝑛𝑑𝑎𝑟𝑦
𝑓𝑐𝑖𝑟𝑐𝑙𝑒(𝑥, 𝑦) > 0 𝑖𝑓 (𝑥, 𝑦)𝑖𝑠 𝑜𝑢𝑡𝑠𝑖𝑑𝑒 𝑡ℎ𝑒 𝑐𝑖𝑟𝑐𝑙𝑒 𝑏𝑜𝑢𝑛𝑑𝑎𝑟𝑦
22
 Midpoint Circle Algorithm…
 Above equation we calculate for the mid positions between pixels near the circular
path at each sampling step and we setup incremental calculation for this function as
we did in the line algorithm.
 Below figure shows the midpoint between the two candidate pixels at sampling
position 𝑥𝑘 + 1.
𝒙 𝟐 + 𝒚𝟐 − 𝒓 𝟐 = 𝟎

𝒚𝒌 Midpoint

𝒚𝒌 − 𝟏

𝒙𝒌 𝒙𝒌 + 𝟏 𝒙𝒌 + 𝟐
Fig. 2.10: - Midpoint between candidate pixel at sampling position 𝑥𝑘 + 1
along circle path.

23
 Midpoint Circle Algorithm…
 Assuming we have just plotted the pixel at (𝑥𝑘, 𝑦𝑘) and next we need to determine
whether the pixel at
 position ‘(𝑥𝑘 + 1, 𝑦𝑘)’ or the one at position’ (𝑥𝑘 + 1, 𝑦𝑘 − 1)’ is closer to circle
boundary.
 So for finding which pixel is more closer using decision parameter evaluated at
the midpoint between two candidate pixels as below:

1
𝑝𝑘 = 𝑓𝑐𝑖𝑟𝑐𝑙𝑒 𝑥𝑘 + 1, 𝑦𝑘 −
2
2
2
1
𝑝𝑘 = 𝑥𝑘 + 1 + 𝑦𝑘 + − 𝑟2
2
 If 𝑝𝑘 < 0 this midpoint is inside the circle and the pixel on the scan line 𝑦𝑘 is
closer to circle boundary. Otherwise the midpoint is outside or on the boundary
and we select the scan line 𝑦𝑘 − 1.
 Successive decision parameters are obtain using incremental calculations as
follows:

24
 Midpoint Circle Algorithm…
 If 𝑝𝑘 < 0 this midpoint is inside the circle and the pixel on the scan line 𝑦𝑘 is
closer to circle boundary. Otherwise the midpoint is outside or on the boundary
and we select the scan line 𝑦𝑘 − 1.
 Successive decision parameters are obtain using incremental calculations as
follows:
1
𝑝𝑘+1 = 𝑓𝑐𝑖𝑟𝑐𝑙𝑒 𝑥𝑘+1 + 1, 𝑦𝑘+1 −
2 2
1
𝑝𝑘+1 = 𝑥𝑘+1 + 1 + 1 2 + 𝑦𝑘+1 + − 𝑟2
2
 Now we can obtain recursive calculation using equation of 𝑝𝑘+1 and 𝑝𝑘 as follow.
2 2
2
1 2 2
1
𝑝𝑘+1 − 𝑝𝑘 = 𝑥𝑘 + 1 + 𝑦𝑘 + −𝑟 − 𝑥𝑘+1 + 1 + 1 + 𝑦𝑘+1 + − 𝑟2
2 2

2
1 1
𝑝𝑘+1 − 𝑝𝑘 = 𝑥𝑘 + 1 + 2 𝑥𝑘 + 1 + 1 + 𝑦𝑘+1 2 + 𝑦𝑘+1 + − 𝑟 2 − 𝑥𝑘 + 1 2
− 𝑦𝑘 2 + 𝑦𝑘 − + 𝑟 2
4 4

25
 Midpoint Circle Algorithm…
 In above equation 𝑦𝑘+1 is either 𝑦𝑘 or 𝑦𝑘 − 1 depending on the sign of the 𝑝𝑘.
 Now we can put 2𝑥𝑘+1 = 2𝑥𝑘 + 2 and when we select 𝑦𝑘+1 = 𝑦𝑘 − 1
we can obtain 2𝑦𝑘+1 = 2𝑦𝑘 − 2.
 The initial decision parameter is obtained by evaluating the circle function at the start
position

26
 Algorithm for Midpoint Circle Generation

1. Input radius 𝑟 and circle center (𝑥𝑐, 𝑦𝑐), and obtain the first point on the
circumference of a circle centered on the origin as
(𝑥0, 𝑦0) = (0, 𝑟)
2. calculate the initial value of the decision parameter as
3. At each 𝑥𝑘 position, starting at 𝑘 = 0, perform the following test:
If 𝑝𝑘 < 0, the next point along the circle centered on (0, 0) is
(𝑥𝑘 + 1, 𝑦𝑘) & 𝑝𝑘+1 = 𝑝𝑘 + 2𝑥𝑘+1 + 1

Otherwise, the next point along the circle is

(𝑥𝑘 + 1, 𝑦𝑘 − 1) &𝑝𝑘+1 = 𝑝𝑘 + 2𝑥𝑘+1 + 1 − 2𝑦𝑘+1

Where 2𝑥𝑘+1 = 2𝑥𝑘 + 2, & 2𝑦𝑘+1 = 2𝑦𝑘 − 2.

4. Determine symmetry points in the other seven octants.
5. Move each calculated pixel position (𝑥, 𝑦) onto the circular path centered on
(𝑥𝑐, 𝑦𝑐) and plot the coordinate values:
𝑥 = 𝑥 + 𝑥𝑐, 𝑦 = 𝑦 + 𝑦𝑐
6. Repeat steps 3 through 5 until 𝑥 ≥ 𝑦.

27
 Ellipse

Fig. 2.11: - Ellipse generated about foci f1 and f2.

 AN ellipse is defined as the set of points such that the sum of the distances from two
fixed positions (foci) is same for all points.

28
 Properties of Ellipse
 If we labeled distance from two foci to any point on ellipse boundary as 𝑑1 and 𝑑2 then
the general equation of an ellipse can be written as follow.
𝑑1 + 𝑑2 = 𝐶𝑜𝑛𝑠𝑡𝑎𝑛𝑡
 Expressing distance in terms of focal coordinates 𝑓1 = (𝑥1, 𝑦1) and 𝑓2 = (𝑥2, 𝑦2) we have

 An interactive method for specifying an ellipse in an arbitrary orientation is to input

two foci and a point on the ellipse boundary.
 with this three coordinates we can evaluate constant in equation:

29
 Properties of Ellipse…

 We can also write this equation in the form

𝐴𝑥2 + 𝐵𝑦2 + 𝐶𝑥𝑦 + 𝐷𝑥 + 𝐸𝑦 + 𝐹 = 0
 Where the coefficients 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, and 𝐹 are evaluated in terms of the focal
coordinates and the dimensions of the major and minor axes of the ellipse.
 Major axis of an ellipse is straight line segment passing through both foci and
extends up to boundary on both sides.
 The minor axis spans shortest dimension of ellipse, it bisect the major axis at right
angle in two equal half.
 Then coefficient in 𝐴𝑥2 + 𝐵𝑦2 + 𝐶𝑥𝑦 + 𝐷𝑥 + 𝐸𝑦 + 𝐹 = 0 can be evaluated and used
to generate pixels along the elliptical path.
 Ellipse equation are greatly simplified if we align major and minor axis with
coordinate axes i.e. 𝑥 − 𝑎𝑥𝑖𝑠 and 𝑦 − 𝑎𝑥𝑖𝑠.
 We can say ellipse is in standard position if their major and minor axes are parallel
to 𝑥 − 𝑎𝑥𝑖𝑠 and 𝑦 −𝑎𝑥𝑖𝑠 which is shown in below figure

30
 Properties of Ellipse…

Fig. 2.12: - Ellipse centered at (𝑥𝑐, 𝑦𝑐) with semi major axis 𝑟𝑥 and semi minor axis 𝑟𝑦 are
parallel to coordinate axis.

 Equation of ellipse shown in figure 2.12 can be written in terms of the ellipse
center coordinates and parameters 𝑟𝑥 and 𝑟𝑦 as.

 Using the polar coordinates 𝑟 and 𝜃, we can also describe the ellipse in
standard position with the parametric equations:
𝑥 = 𝑥𝑐 + 𝑟𝑥 cos θ
𝑦 = 𝑦𝑐 + 𝑟𝑦 sin θ
31
 Properties of Ellipse…
 Symmetry considerations can be used to further reduced computations.
 An ellipse in standard position is symmetric between quadrants but unlike a circle it
is not symmetric between octant.
 Thus we must calculate boundary point for one quadrant and then other three
quadrants point can be obtained by symmetry as shown in figure below.

Fig. 2.13: - symmetry of an ellipse.

32
 Midpoint Ellipse Algorithm

 Midpoint ellipse algorithm is a method for drawing ellipses in computer graphics. This
method is modified from Bresenham's algorithm.
 The advantage of this modified method is that only addition operations are required in the
program loops.
 This leads to simple and fast implementation in all processors.
 Given parameters 𝑟𝑥, 𝑟𝑦 and (𝑥𝑐, 𝑦𝑐) we determine points (𝑥, 𝑦) for an ellipse in
standard position centered on the origin, and then we shift the points so the ellipse is
centered at (𝑥𝑐, 𝑦𝑐).

33
 Midpoint Ellipse Algorithm…
 If we want to display the ellipse in nonstandard position then we rotate the ellipse about
its center to align with required direction.
 For the present we consider only the standard position.
 In this method we divide first quadrant into two parts according to the slope of an ellipse
as shown in figure below.

Fig. 2.14: - Ellipse processing

regions. Over the region 1 the
magnitude of ellipse slope is < 1
and over the region 2 the
magnitude of ellipse slope > 1.
34
 Midpoint Ellipse Algorithm…

 We take unit step in 𝑥 direction if magnitude of slope is less than 1 in that region
otherwise we take unit step in 𝑦 direction.
 Boundary divides region at 𝑠𝑙𝑜𝑝𝑒 = −1.
 With 𝑟𝑥 < 𝑟𝑦 we process this quadrant by taking unit steps in 𝑥 direction in region 1 and
unit steps in 𝑦 direction in region 2.
 Region 1 and 2 can be processed in various ways.
 We can start from (0, 𝑟𝑦) and step clockwise along the elliptical path in the first
quadrant shifting from unit step in 𝑥 to unit step in 𝑦 when slope becomes less than -1.
 Alternatively, we could start at (𝑟𝑥, 0) and select points in a counterclockwise order,
shifting from unit steps in 𝑦 to unit steps in 𝑥 when the slope becomes greater than -1.
 With parallel processors, we could calculate pixel positions in the two regions
simultaneously.
 Here we consider sequential implementation of midpoint algorithm. We take the start
position at (0, 𝑟𝑦)
 and steps along the elliptical path in clockwise order through the first quadrant.

35
 Midpoint Ellipse Algorithm…

 We define ellipse function for center of ellipse at (0, 0) as follows.

 Which has the following properties:

 Thus the ellipse function serves as the decision parameter in the midpoint ellipse
algorithm.
 At each sampling position we select the next pixel from two candidate pixel.
 Starting at (0, 𝑟𝑦) we take unit step in 𝑥 direction until we reach the boundary between
region 1 and 2 then we switch to unit steps in 𝑦 direction in remaining portion on ellipse
in first quadrant.
 At each step we need to test the value of the slope of the curve for deciding the end point
of the region-1.

36
 Midpoint Ellipse Algorithm…
 The ellipse slope is calculated using following equation.

 The ellipse slope is calculated using following equation.

 At boundary between region 1 and 2 𝑠𝑙𝑜𝑝𝑒 = −1 and equation become.

2𝑟𝑦2𝑥 = 2𝑟𝑥2𝑦
 Therefore we move out of region 1 whenever following equation is false
2𝑟𝑦2𝑥 ≤ 2𝑟𝑥2𝑦
 Following figure shows the midpoint between the two candidate pixels at sampling
position 𝑥𝑘 + 1 in the first region.

Fig. 2.15: - Midpoint between

candidate pixels at sampling
position 𝑥𝑘 + 1 along an elliptical
path.
37
 Midpoint Ellipse Algorithm…
 Assume we are at (𝑥𝑘 , 𝑦𝑘) position and we determine the next position along the
ellipse path by evaluating decision parameter at midpoint between two candidate
pixels.

 If 𝑝1𝑘 < 0, the midpoint is inside the ellipse and the pixel on scan line 𝑦𝑘 is closer to
ellipse boundary otherwise the midpoint is outside or on the ellipse boundary and we
select the pixel 𝑦𝑘 − 1.
 At the next sampling position decision parameter for region 1 is evaluated as.
 Now subtract 𝑝1𝑘 from 𝑝1𝑘+1

38
 Midpoint Ellipse Algorithm…
 Now making 𝑝1𝑘+1 as subject.

 Here 𝑦𝑘+1 is either 𝑦𝑘 or 𝑦𝑘 − 1, depends on the sign of 𝑝1𝑘

 Now we calculate the initial decision parameter 𝑝10 by putting (𝑥0, 𝑦0) = (0, 𝑟𝑦)
as follow.

 Now we similarly calculate over region 2 by unit stepping in negative 𝑦

direction and the midpoint is now taken between horizontal pixels at each
step as shown in figure below.

39
 Midpoint Ellipse Algorithm…

Fig. 2.16: - Midpoint between candidate pixels at sampling position 𝑦𝑘 − 1 along an

elliptical path.

 For this region, the decision parameter is evaluated as follows.

40
 Midpoint Ellipse Algorithm…
 If 𝑝2𝑘 > 0 the midpoint is outside the ellipse boundary, and we select the pixel at 𝑥𝑘.
 If 𝑝2𝑘 ≤ 0 the midpoint is inside or on the ellipse boundary and we select 𝑥𝑘 + 1.
 At the next sampling position decision parameter for region 2 is evaluated as.

 Now subtract 𝑝2𝑘 from 𝑝2𝑘+1

41
 Midpoint Ellipse Algorithm…
 Now making 𝑝2𝑘+1 as subject.
 Here 𝑥𝑘+1 is either 𝑥𝑘 or 𝑥𝑘 + 1, depends on the sign of 𝑝2𝑘.
 In region 2 initial position is selected which is last position of region one and the
initial decision parameter is calculated as follows.

 For simplify calculation of 𝑝20 we could select pixel position in counterclockwise

order starting at (𝑟𝑥, 0).
 In above case we take unit step in the positive 𝑦 direction up to the last point selected
in region 1.

42
 Algorithm for Midpoint Ellipse Generation
1. Input 𝑟𝑥, 𝑟𝑦 and ellipse center (𝑥𝑐, 𝑦𝑐), and obtain the first point on an ellipse centered on
the origin as
(𝑥0, 𝑦0) = (0, 𝑟𝑦)
2.Calculate the initial value of the decision parameter in region 1 as
3. At each 𝑥𝑘 position in region 1, starting at 𝑘 = 0, perform the following test:

If 𝑝1𝑘 < 0, the next point along the ellipse centered on (0, 0) is (𝑥𝑘+1, 𝑦𝑘) and

Otherwise, the next point along the ellipse is (𝑥𝑘+1, 𝑦𝑘 − 1) and

With

And continue until 2𝑟𝑦2𝑥 ≤ 2𝑟𝑥2𝑦

 Calculate the initial value of the decision parameter in region 2 using the last point (𝑥0, 𝑦0)
calculated in region 1 as

43
 Algorithm for Midpoint Ellipse Generation...
 At each 𝑦𝑘 position in region-2, starting at 𝑘 = 0, perform the following test:

 If 𝑝2𝑘 > 0, the next point along the ellipse centered on (0, 0) is (𝑥𝑘, 𝑦𝑘 − 1) and

 Otherwise, the next point along the ellipse is (𝑥𝑘 + 1, 𝑦𝑘 − 1) and

Using the same incremental calculations for 𝑥 and 𝑦 as in region 1.

 Determine symmetry points in the other three quadrants.
 Move each calculated pixel position (𝑥, 𝑦) onto the elliptical path centered on (𝑥𝑐, 𝑦𝑐)
and plot the coordinate values:

 Repeat the steps for region 2 until 𝑦𝑘 ≥ 0.

44
 Filled-Area Primitives
 In practical we often use polygon which are filled with some color or pattern inside it.
 There are two basic approaches to area filling on raster systems.
 One way to fill an area is to determine the overlap intervals for scan line that cross the
area.
 Another method is to fill the area is to start from a given interior position and paint
out wards from this point until we encounter boundary.

Scan-Line Polygon Fill Algorithm

 Figure below shows the procedure for scan-line filling algorithm.

Fig. 2.17: - Interior pixels along a scan line passing through a polygon area.
45
 Scan-Line Polygon Fill Algorithm…
 For each scan-line crossing a polygon, the algorithm locates the intersection points are
of scan line with the polygon edges.
 This intersection points are stored from left to right.
 Frame buffer positions between each pair of intersection point are set to specified fill
color.
 Some scan line intersects at vertex position they are required special handling.
 For vertex we must look at the other endpoints of the two line segments of the polygon
which meet at this vertex.
 If these points lie on the same (up or down) side of the scan line, then that point is
counts as two intersection points.
 If they lie on opposite sides of the scan line, then the point is counted as single
intersection
 This is illustrated in figure below

Fig. 2.18: - Intersection points

along the scan line that
intersect polygon vertices.

46
 Scan-Line Polygon Fill Algorithm…

 As shown in the Fig. 2.18, each scan line intersects the vertex or vertices of the polygon.
For scan line 1, the other end points (B and D) of the two line segments of the polygon lie
on the same side of the scan line, hence there are two intersections resulting two pairs: 1 -
2 and 3 - 4. Intersections points 2 and 3 are actually same Points. For scan line 2 the other
endpoints (D and F) of the two line segments of the Polygon lie on the opposite sides of
the scan line, hence there is a single intersection resulting two pairs: l - 2 and 3 - 4. For
scan line 3, two vertices are the intersection points“

 For vertex F the other end points E and G of the two line segments of the polygon lie on
the same side of the scan line whereas for vertex H, the other endpoints G and I of the
two line segments of the polygon lie on the opposite side of the scan line. Therefore, at
vertex F there are two intersections and at vertex H there is only one intersection. This
results two pairs: 1 - 2 and 3 - 4 and points 2 and 3 are actually same points.

 Coherence methods often involve incremental calculations applied along a single scan
line or between successive scan lines.

 In determining edge intersections, we can set up incremental coordinate calculations

along any edge by exploiting the fact that the slope of the edge is constant from one scan
line to the next.
47
 Flood-Fill Algorithm
 Sometimes it is required to fill in an area that is not defined within a single color
boundary.
 In such cases we can fill areas by replacing a specified interior color instead of searching
for a boundary color.
 This approach is called a flood-fill algorithm. Like boundary fill algorithm, here we start
with some seed and examine the neighbouring pixels.
 However, here pixels are checked for a specified interior color instead of boundary color
and they are replaced by new color.
 Using either a 4-connected or 8-connected approach, we can step through pixel positions
until all interior point have been filled.
 The following procedure illustrates the recursive method for filling 4-connected region
using flood-fill algorithm.
 Procedure :
flood-fill4(x, y, new-color, old-color){
if(getpixel (x,y) = = old-color){
putpixel (x, y, new-color)
flood-fill4 (x + 1, y, new-color, old -color); flood-fill4 (x, y + 1, new -color, old -color);
flood-fill4 (x - 1, y, new -color, old -color); flood-fill4 (x, y - l, new -color, old-color);
}
}
 Note: 'getpixel' function gives the color of .specified pixel and 'putpixel' function draws
the pixel with specified color. 48
 Character Generation
 We can display letters and numbers in variety of size and style.
 The overall design style for the set of character is called typeface.
 Today large numbers of typefaces are available for computer application for example
Helvetica, New York platino etc.
 Originally, the term font referred to a set of cast metal character forms in a particular
size and format, such as 10-point Courier Italic or 12- point Palatino Bold. Now, the
terms font and typeface are often used interchangeably, since printing is no longer
done with cast metal forms.
 Two different representations are used for storing computer fonts.

Bitmap Font/ Bitmapped Font

 A simple method for representing the character shapes in a particular typeface is
to use rectangular grid patterns.
Figure below shows pattern for particular letter.

Fig. 2.25: - Grid pattern for letter B.

49
 Character Generation…
 When the pattern in figure 2.25 is copied to the area of frame buffer, the 1 bits
designate which pixel positions are to be displayed on the monitor.
 Bitmap fonts are the simplest to define and display as character grid only need to be
mapped to a frame- buffer position.
 Bitmap fonts require more space because each variation (size and format) must be
stored in a font cache.
 It is possible to generate different size and other variation from one set but this
usually does not produce good result.

Outline Font
 In this method character is generated using curve section and straight line as combine
assembly.
 Figure below shows how it is generated.

Fig. 2.26: - outline for letter B.

50
 Character Generation…
 To display the character shown in figure 2.26 we need to fill interior region of the
character.
 This method requires less storage since each variation does not required a distinct
font cache.
 We can produce boldface, italic, or different sizes by manipulating the curve
definitions for the character outlines.
 But this will take more time to process the outline fonts, because they must be scan
converted into the frame buffer.

Stroke Method

Fig. 2.27: - Stroke Method for Letter A

 It uses small line segments to generate a character.

 The small series of line segments are drawn like a stroke of a pen to form a
character as shown in figure.
 We can generate our own stroke method by calling line drawing algorithm.
 Here it is necessary to decide which line segments are needs for each character
and then draw that line to display character.
 It support scaling by changing length of line segment. 51
 Character Generation…
Starbust Method

Fig. 2.28: - (a) Starbust

Method. (b) Letter V using
starbust method

 In this method a fix pattern of line segments are used to generate characters.
 As shown in figure 2.28 there are 24 line segments.
 We highlight those lines which are necessary to draw a particular character.
 Pattern for particular character is stored in the form of 24 bit code. In which each bit
represents corresponding line having that number.
 That code contains 0 or 1 based on line segment need to highlight. We put bit value 1 for
highlighted line and 0 for other line.
 Code for letter V is
110011100001001100000000
 This technique is not used now a days because:
1.It requires more memory to store 24 bit code for single character.
2.It requires conversion from code to character.
3.It doesn’t provide curve shapes. 52
Thank you!

53