A raster scan display is the most common type of display used in modern screens,

such as TVs, computer monitors, and smartphones. This display technology works by
scanning the screen from top to bottom, left to right, in a grid-like pattern (called a
raster). The screen is made up of rows and columns of pixels, and the image is formed by
illuminating specific pixels at specific times.

Here’s how it works:

1. Scanlines: The screen is divided into rows (scanlines), and the electron beam (or
similar technology) starts at the top-left corner and moves horizontally, illuminating
each pixel in the row.

2. Frame: After completing one row, the beam moves down to the next row,
continuing until the entire screen is filled from top to bottom. This process is
repeated many times per second to refresh the image, which is why you often hear
terms like refresh rate and frame rate.

3. Resolution: The sharpness of the image is determined by the number of pixels in

the screen’s resolution, such as 1920x1080 for HD screens, where there are 1920
pixels across and 1080 down.
A vector scan display is a type of display technology that creates images by drawing
lines directly onto the screen with an electron beam or similar technique, as opposed to
raster scanning, which paints the screen pixel by pixel. This method is often associated
with older computer graphics, oscilloscopes, and certain types of video games and
arcade machines.

In a vector scan display:

 The electron beam is directed to specific points in a frame to form the desired
shape, such as lines, curves, and polygons.

 It is different from raster displays, where the entire screen is filled with pixel grids.

 It creates smoother and sharper lines since there are no pixel-based constraints,
often producing vector-like, precise designs.

Scan conversion of Line and Line Drawing algorithms

SCAN Conversion of Line :

 A line connects two points.

 It is a basic element in graphics.

 You’ll need two spots between which to draw a line to draw a line .

A line, or line segment, can be uniquely described by two points, according to geometry.
We also know from algebra that a line can be defined by a slope, commonly denoted by
the letter m, and a y-axis intercept, denoted by the letter b. A line in computer graphics
is usually defined by two endpoints. However, most line-drawing algorithms calculate the
slope and y- intercept as intermediate outputs.

Line Drawing algorithms :

Given the inherent restrictions of a raster display, the purpose of every line drawing
method is to produce the best feasible approximation of an ideal line. Before getting into
specific line drawing algorithms, it’s a good idea to think about the needs for such
algorithms in general.

The primary design criteria are as follows.

 Straight lines appear as straight lines.

 Straight lines start and end accurately.

 Displayed lines should have constant brightness along their length, independent of
the line length and orientation.

 Lines should be drawn rapidly.

Method-1 : Direct Method :

In this algorithm, we have two endpoints. We find the slope of the line by using both the
points, and we put the slope in the line equation y = mx + b.

Then we find the value of b by putting x and y equal to 0. After this, we have a relation
between x and y. Now we increase the value of x and find the corresponding value of y.
These values will be the intermediate points of the line. After finding the intermediate
points we’ll plot those points and draw the line.

FIG – Direct method

Method-2 : DDA (Digital Differential Analyzer) Algorithm :

The incremental technique is used in this algorithm. It means that we can find the next
coordinates by using past coordinates as a guide. In this method, the difference of pixel
point is analyzed and according to the analysis, the line can be drawn.

We’ll start with the initial position and work our way to the ending position by looking for
intermediate places. The slope of the line will be the ratio of difference of y-coordinates
and the difference of x-coordinates.

Δy = ( y2 -y1 ), Δx = (x2 - x1)

where, (x1, y1) and (x2, y2) are the endpoints.

The Digital Differential Analyzer algorithm is based on the values of Δx and Δy.

Δy = m * Δx , Δx = Δy / m

The value of the slope will be either positive or negative. If the value of the slope is
positive then the values of Δx and Δy are increased otherwise their values are decreased.
 (i). If (m < 1): xN = x1 + 1 , yN = y1 + m

(ii). If (m > 1): xN = x1 + 1 / m , yN = y1 +1

(iii). If (m = 1): xN = x1 + 1 , yN = y1 + 1

FIG = DDA algo

Method-3 : Bresenham’s Line Generation :

Another incremental scan conversion procedure is the Bresenham’s algorithm. The big
advantage of this algorithm is that, it uses only integer calculations.

This method’s calculation is incredibly quick, which is why the line is drawn swiftly. We’ll
need the two endpoints in this and then we have to find the decision parameters.

Let assume that (x1,y1) and (x2,y2) are the two points.

So, dx = x2-x1 and dy = y2-y1

The formula for the decision parameter is: di = 2dy – dx.

-> If di >= 0:

Plotted points are,

di +1 = di + 2dy - 2dx ( i+1 is in base of d )

xN = x1 + 1 , yN = y1 + 1

-> If di < 0:

Plotted points are,

di +1 = di + 2dy ( i+1 is in base of d )

xN = x1 + 1 , yN = y1

Fig = Bresenham’s line algorithm

Scan conversion methods of circle and circle generation algorithms

Last Updated : 17 Jun, 2021

Scan conversion of circle :

 A circle is defined as a set of points that all are the same distance from a common
point.

 The Centre of the circle is known as the Centre, and the radius is the distance from
the Centre of the circle to any point on its circumference.

 It’s an eight-sided symmetrical figure divided into four quadrants. By knowing only
one point and reflecting it via every 45 degree axis, this symmetry aids in
constructing a circle on a computer.

fig = scan conversion of circle

METHODS :
Method I – Direct or Polynomial Method :

 In this method, a circle is defined with the help of a polynomial equation.

Method II – Polar Coordinates Method :

 In this method, the coordinates are converted into polar coordinates.

FIG = polar form

Circle generation algorithms :

1) Mid-Point Circle Algorithm :

 The mid-point circle drawing algorithm is used to calculate all the perimeter points
of a circle.

 In this algorithm, the mid-point between the two pixels is calculated which helps in
calculating the decision parameter.

 The value of the decision parameter will decide which pixel should be chosen for
drawing the circle.

 This algorithm only calculates the points for one octant and the points for other
octants are generated using the eight-way symmetry for the circle.

Algorithm :

 Step 1: Plot the initial point such that x = 0 and y = r.

 Step 2: Find initial decision parameter: P=5/4 – r.

 Step 3: if (P< 0): Set P= P+ 2x + 3 and yN = y , xN = x + 1 else if (P>= 0): Set P=

P+ 2(x-y) + 5 and yN = y – 1 , xN = x + 1.

 Step 4: Plot the complete circle by using 8-way symmetry.

FIG = Mid-point circle algorithm

2) Bresenham’s Circle Drawing Algorithm :

 The Bresenham’s circle drawing algorithm is a circle drawing algorithm which

calculates all the nearest points nearest to the circle boundary.
  It is an incremental method. •

 It only uses integer arithmetic which makes it’s working faster as well as less
complex.

 The strategy that is followed in this algorithm is to select the pixel which has the
least distance with the true circle boundary and with then keep calculating the
successive points on the circle.

 As we know that the circle follows 8 symmetry property, i.e. if we know the
boundary coordinates of the first octant, the rest 7 octants’ value can be easily
calculated by changing their magnitudes or by interchanging the coordinate values
according to the respective octants.

 This algorithm calculates the location of the pixels similarly.

 Here, we calculate the values only for the first octant and the values for the rest
octants can be calculated by extending these values to the other 7 octants, using
the eight-way symmetry property of the circle.

Algorithm :

 Step 1: Initialize x = 0 , y = r.

 Step 2: Calculate the decision parameter as follows: D = 3 – 2r.

 Step 3: if D < 0: then D = D + 4x + 6 xN = x + 1 yN = y if D ≥ 0: then D = D + 4

(x – y) + 10 xN = x + 1 yN = y – 1

 Step 4: Plot the complete circle by using 8-way symmetry .

fig = Bresenham’s circle algorithm

UNIT- 1
 Overview of Computer Graphics

Application of Computer Graphics

Computer-Aided Design for engineering and architectural systems etc.

Objects maybe displayed in a wireframe outline form. Multi-window environment is also
favored for producing various zooming scales and views.
Animations are useful for testing performance.

Presentation Graphics
To produce illustrations which summarize various kinds of data. Except 2D, 3D graphics
are good tools for reporting more complex data.

Computer Art
Painting packages are available. With cordless, pressure-sensitive stylus, artists can
produce electronic paintings which simulate different brush strokes, brush widths, and
colors. Photorealistic techniques, morphing and animations are very useful in commercial
art. For films, 24 frames per second are required. For video monitor, 30 frames per
second are required.

Entertainment
Motion pictures, Music videos, and TV shows, Computer games

Education and Training

Training with computer-generated models of specialized systems such as the training of
ship captains and aircraft pilots.

Visualization
For analyzing scientific, engineering, medical and business data or behavior. Converting
data to visual form can help to understand mass volume of data very efficiently.

Image Processing
Image processing is to apply techniques to modify or interpret existing pictures. It is
widely used in medical applications.

Graphical User Interface

Multiple window, icons, menus allow a computer setup to be utilized more efficiently.

Video Display devices

Cathode-Ray Tubes (CRT) - still the most common video display device
presently

1
 Electrostatic deflection of the electron beam in a CRT

An electron gun emits a beam of electrons, which passes through focusing and deflection
systems and hits on the phosphor-coated screen. The number of points displayed on a CRT is
referred to as resolutions (eg. 1024x768). Different phosphors emit small light spots of
different colors, which can combine to form a range of colors. A common methodology for
color CRT display is the Shadow-mask meth

Illustration of a shadow-mask CRT

The light emitted by phosphor fades very rapidly, so it needs to redraw the picture repeatedly.
There are 2 kinds of redrawing mechanisms: Raster-Scan and Random-Scan

Raster-Scan
The electron beam is swept across the screen one row at a time from top to bottom. As it
moves across each row, the beam intensity is turned on and off to create a pattern of
illuminated spots. This scanning process is called refreshing. Each complete scanning of a
screen is normally called a frame.

The refreshing rate, called the frame rate, is normally 60 to 80 frames per second, or
described as 60 Hz to 80 Hz.

Picture definition is stored in a memory area called the frame buffer. This frame buffer
stores the intensity values for all the screen points. Each screen point is called a pixel (picture
element).

On black and white systems, the frame buffer storing the values of the pixels is called a
bitmap. Each entry in the bitmap is a 1-bit data which determine the on (1) and off (0) of the
intensity of the pixel.

On color systems, the frame buffer storing the values of the pixels is called a pixmap
 nowadays many graphics libraries name it as bitmap too). Each entry in the pixmap
(Though 2
 occupies a number of bits to represent the color of the pixel. For a true color display, the
number of bits for each entry is 24 (8 bits per red/green/blue channel, each channel 2 8=256
levels of intensity value, ie. 256 voltage settings for each of the red/green/blue electron guns).
Random-Scan (Vector Display)

The CRT's electron beam is directed only to the parts of the screen where a picture is to be
drawn. The picture definition is stored as a set of line-drawing commands in a refresh display
file or a refresh buffer in memory.

Random-scan generally have higher resolution than raster systems and can produce smooth
line drawings, however it cannot display realistic shaded scenes.

Display Controller

For a raster display device reads the frame buffer and generates the control signals for the
screen, ie. the signals for horizontal scanning and vertical scanning. Most display controllers
include a color map (or video look-up table). The major function of a color map is to provide
a mapping between the input pixel value to the output color.

Anti-Aliasing

On dealing with integer pixel positions, jagged or stair step appearances happen very
usually. This distortion of information due to under sampling is called aliasing. A number
of ant aliasing methods have been developed to compensate this problem.

One way is to display objects at higher resolution. However there is a limit to how big we
can make the frame buffer and still maintaining acceptable refresh rate.

Drawing a Line in Raster Devices

DDA 3
 In computer graphics, a hardware or software implementation of a digital differential analyzer
(DDA) is used for linear interpolation of variables over an interval between start and end point.
DDAs are used for rasterization of lines, triangles and polygons. In its simplest implementation
the DDA Line drawing algorithm interpolates values in interval [(xstart, ystart), (xend, yend)] by
computing for each xi the equations xi = xi−1+1/m, yi = yi−1 + m, where Δx = xend − xstart and
Δy = yend − ystart and m = Δy/Δx.

The dda is a scan conversion line algorithm based on calculating either dy or dx. A line is
sampled at unit intervals in one coordinate and corresponding integer values nearest the line path
are determined for other coordinates.
Considering a line with positive slope, if the slope is less than or equal to 1, we sample at unit x
intervals (dx=1) and compute successive y values as

Subscript k takes integer values starting from 0, for the 1st point and increases by until endpoint
is reached. y value is rounded off to nearest integer to correspond to a screen pixel.
For lines with slope greater than 1, we reverse the role of x and y i.e. we sample at dy=1 and
calculate consecutive x values as

Similar calculations are carried out to determine pixel positions along a line with negative slope.
Thus, if the absolute value of the slope is less than 1, we set dx=1 if i.e. the starting extreme
point is at the left.

The basic concept is:

- A line can be specified in the form:
y = mx + c
- Let m be between 0 to 1, then the slope of the line is between 0 and 45 degrees.
- For the x-coordinate of the left end point of the line, compute the
corresponding y value according to the line equation. Thus we get the
left end point as (x1,y1), where y1 may not be an integer.
- Calculate the distance of (x1,y1) from the center of the pixel immediately
above it and call it D1
- Calculate the distance of (x1,y1) from the center of the pixel immediately
below it and call it D2
- If D1 is smaller than D2, it means that the line is closer to the upper
pixel than the lower pixel, then, we set the upper pixel to on;
otherwise we set the lower pixel to on.
- Then increatement x by 1 and repeat the same process until x
reaches the right end point of the line.
- This method assumes the width of the line to be zero

Bresenham's Line 4
Algorithm
This algorithm is very efficient since it use only incremental integer calculations. Instead of
calculating the non-integral values of D1 and D2 for decision of pixel location, it computes a
value, p, which is defined as:

p = (D2-D1)* horizontal length of the line

if p>0, it means D1 is smaller than D2, and we can determine the pixel location accordingly

However, the computation of p is very easy:

The initial value of p is 2 * vertical height of the line - horizontal length of the line.
At succeeding x locations, if p has been smaller than 0, then, we increment p by 2 * vertical
height of the line, otherwise we increment p by 2 * (vertical height of the line - horizontal
length of the line)

All the computations are on integers. The incremental method is applied to

void BresenhamLine(int x1, int y1, int x2, int y2)

{ int x, y, p, const1, const2; /* initialize
variables */ p=2*(y2-y1)-(x2-x1);
const1=2*(y2-y1); const2=2*((y2-
y1)-(x2-x1));

x=x1;
y=y1;
SetPixel(x,y);
while (x<xend) { x+
+;
if (p<0)
{ p=p+const1;
}
else
{ y++;
p=p+const2;
}
SetPixel(x,y);
}
}

Bitmap

- A graphics pattern such as an icon or a character may be needed

frequently, or may need to be re-used.
- Generating the pattern every time when needed may waste a lot of processing
 time.
- A bitmap can be used to store a pattern and duplicate it to many places on the
image
on the screen with simple copying operations.
or 5
Mid Point circle Algorithm

However, unsurprisingly this is not a brilliant 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 – try really hard to avoid these!
We need a more efficient, more accurate solution.
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

Similarly to the case with lines, there is an incremental algorithm for

drawing circles – the mid- point circle algorithm
In the mid-point circle algorithm we use eight-way symmetry so only ever calculate the points
for the top right eighth of a circle, and then use symmetry to get the rest of the points

Assume that we have

just plotted point (xk, yk)
The next point is a
choice between
(xk+1, yk) and
(xk+1, yk-1)

6
We would like to choose

the point that is nearest to

the actual circle
So how do we make this choice?

Let’s re-jig the equation of the circle slightly to give us:

The equation evaluates as follows:

f (x, y) 2 2
circ
x2 y r

0,
fcirc (x, y)

0
,
0
,

<0 if (x, y) is outside thecircleboundary

=0 (x, y) is on thecircleboundary
if (x, y) is inside thecircleboundary
>0
if

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

Assuming we have just plotted the pixel at (xk,yk) so we need to choose between (xk+1,yk) and
7
(xk+1,yk-1)
Our decision variable can be defined as:

pk 1, yk 2 1 )
fcirc (xk

k
1
1)2 ( 22 2
(xk ) r
y

If pk < 0 the midpoint is inside the circle and and the pixel at yk is closer to the circle
Otherwise the midpoint is outside and yk-1 is closer

8
To ensure things are as efficient as possible we can do all of our calculations incrementally
First consider:

pk 1 fcirc xk 1 1, yk 1 1
2

[( xk 1] yk 1 2
1) 1 2 r
2 1) ( y2
p p 2 y2) y )1
2(x (y
k 1 k k k1 k k 1 k

where yk+1 is either yk or yk-1 depending on the sign of pk

The first decision variable is given as:

p0 fcirc (1,r 12 )

1 (r 1 )2 r 2
2
5 r
4

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

pk 1 pk 2xk 1 1

If pk > 0 then the decision variable is:

pk 1 pk 2xk 1 1 2 yk 1

Input radius r and circle centre (xc, yc), then set the coordinates for the first point on the
circumference of a circle centred on the origin as:

(x0 , y0 ) (0, r)
• Calculate the initial value of the decision parameter as:

p0 5 r
4
• Starting with k = 0 at each position xk, perform the following test. If pk
< 0, the next point along the circle centred on (0, 0) is (xk+1, yk) and:

9
 pk 1 pk 2xk 1 1

Otherwise the next point along the circle is (xk+1, yk-1) and:

pk 1 pk 2xk 1 1 2 yk 1

Determine symmetry points in the other seven octants

Move each calculated pixel position (x, y) onto the circular path centred at (xc, yc) to plot the
coordinate values:

10
 x x xc y y yc

Repeat steps 3 to 5 until x >= y

To see the mid-point circle algorithm in action lets use it to draw a circle centred at (0,0) with
radius 10.
Scan-Line Polygon Fill Algorithm

- Basic idea: For each scan line crossing a polygon, this algorithm locates
the intersection points of the scan line with the polygon edges. These
intersection points are shorted from left to right. Then, we fill the pixels
between each intersection pair.

- Some scan-line intersection at polygon vertices require special

handling. A scan line passing through a vertex as intersecting the
polygon twice. In this case we may or may not add 2 points to the list
of intersections, instead of adding 1 points. This decision depends on
whether the 2 edges at both sides of the vertex are both above, both
below, or one is above and one is below the scan line. Only for the case
if both are above or both are below the scan line, then we will add 2
points.

Inside-Outside Tests:

- The above algorithm only works for standard polygon shapes. However,
for the cases which the edge of the polygon intersects, we need to
identify whether a point is an interior or exterior point. Students may
find interesting descriptions of 2 methods to solve this problem in many
text books: odd-even rule and nonzero winding number rule.

11
Boundary-Fill Algorithm

- This algorithm starts at a point inside a region and paint the interior
outward towards the boundary.
- This is a simple method but not efficient: 1. It is recursive method
which may occupy a large stack size in the main memory.

void BoundaryFill(int x, int y, COLOR fill, COLOR boundary)

{ COLOR current;
current=GetPixel(x,y);
if (current<>boundary) and (current<>fill) then {
SetPixel(x,y,fill);
BoundaryFill(x+1,y,fill,boundary);
BoundaryFill(x-1,y,fill,boundary);
BoundaryFill(x,y+1,fill,boundary);
BoundaryFill(x,y-1,fill,boundary);
}
}

- More efficient methods fill horizontal pixel spands across scan

lines, instead of proceeding to neighboring points.

12
Flood-Fill Algorithm

- Flood-Fill is similar to Boundary-Fill. The difference is

that Flood-Fill is to fill an area which I not defined by a
single boundary color.

void BoundaryFill(int x, int y, COLOR fill, COLOR old_color)

{ if
(GetPixel(x,y)== old_color) { SetPixel(x,y,fill);
BoundaryFill(x
+1,y,fill,bounda
ry);
BoundaryFill(x-
1,y,fill,boundary
);
BoundaryFill(x,
y+1,fill,boundar
y);
BoundaryFill(x,
y-
1,fill,boundary);
}

13