Unit I

Graphics Primitives and Scan

Conversion Algorithms
--Prof. Priyanka Yeotikar Bhore
AI&DS Department
(Assistant Professor)
Ajeenkya DY Patil SOE, Lohgoan
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Mapping of Course Outcomes for Unit I

• CO1: Identify the basic terminologies of Computer Graphics and interpret

the mathematical foundation of the concepts of computer graphics.
• CO2: Apply mathematics to develop Computer programs for elementary
graphic operations

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Syllabus
• Introduction, graphics primitives - pixel, resolution, aspect ratio, frame buffer.
Display devices, applications of computer graphics.
• Introduction to OpenGL - OpenGL architecture, primitives and attributes, simple
modelling and rendering of two- and three-dimensional geometric objects, GLUT,
interaction, events and call-backs picking. (Simple Interaction with the Mouse
and Keyboard)
• Scan conversion: Line drawing algorithms: Digital Differential Analyzer (DDA),
Bresenham. Circle drawing algorithms: DDA, Bresenham, and Midpoint.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Introduction

• Graphics Primitives:- Graphics primitives are basic

geometric elements used to create computer-generated images.
They include fundamental shapes and objects that serve as
building blocks for more complex graphics. Some common
graphics primitives include points, lines, curves, polygons, and
text.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Graphics Primitives
• Pixel: Pixel, short for "picture element," is the smallest unit of a digital
image or display. The pixel is the smallest addressable screen element
which we can control. It represents a single point in a rasterized image and
is typically represented by a combination of red, green, and blue color
values (RGB) or other color models. Pixels collectively form the basis for
creating digital graphics and images. Each pixel has a name or address. The
name which identify pixels correspond to the coordinates which of the
pixel. We can think of the display screen as a grid , or array , of pixels.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Graphics Primitives

• Resolution: Resolution refers to the number of pixels

contained in an image or displayed on a screen. It determines the
level of detail and clarity of the image. Resolution is commonly
specified by the number of pixels horizontally and vertically, such
as 1920x1080 for Full HD (1080p) resolution. Higher resolutions
result in sharper and more detailed images.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Graphics Primitives

• Aspect Ratio: Aspect ratio defines the proportional

relationship between the width and height of an image or display.
It represents the ratio of the horizontal pixels to the vertical
pixels. Common aspect ratios include 4:3 (standard definition),
16:9 (widescreen), and 21:9 (ultrawide). The aspect ratio affects
the shape and visual perception of the displayed content.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Graphics Primitives

• Frame Buffer: A frame buffer, also known as a framebuffer, is

a region of computer memory used to store the pixel values of an
image or frame temporarily. It holds the necessary information to
generate a complete frame for display. The frame buffer acts as a
buffer between the CPU and the display device, allowing for
efficient rendering and manipulation of images before they are
sent to the screen.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Graphics Primitives

• Display Devices: Display devices are hardware components

used to present visual output generated by computers or other
electronic devices. They include monitors, projectors, televisions,
virtual reality headsets, and various other screens. Display devices
come in different sizes, resolutions, and technologies (e.g., LCD,
LED, OLED), providing visual feedback and enabling users to
interact with graphical applications.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Applications of Computer Graphics
Computer graphics has a wide range of applications across various industries
and fields, including:
• Entertainment: Computer graphics are extensively used in video games,
movies, and animations to create immersive virtual worlds, lifelike
characters, and stunning visual effects.
• Design and Visualization: Graphics software is employed in architecture,
industrial design, automotive design, and fashion to create 3D models,
renderings, and simulations, enabling visualization of concepts and designs.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Applications of Computer Graphics

• Computer-Aided Design (CAD): CAD software utilizes computer

graphics to assist in the creation, modification, and analysis of designs,
such as architectural blueprints, mechanical parts, and electronic
circuits.
• Scientific Visualization: Computer graphics techniques are employed to
represent complex scientific data and simulations visually. This aids in
understanding and analyzing data in fields such as medicine, physics,
and meteorology.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Applications of Computer Graphics
• Virtual Reality (VR) : Graphics play a vital role in creating immersive virtual
environments and overlaying digital information onto the real world,
enabling applications in gaming, education, training, and other interactive
experiences.
• Data Visualization: Graphics help in representing large and complex datasets
visually, making it easier to interpret and analyze information in fields like
business intelligence, analytics, and data science.
• User Interfaces (UI) and User Experience (UX): Graphics are used in
designing visually appealing and intuitive interfaces for software applications,
websites, and mobile apps, enhancing the user experience and interaction.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Introduction to OpenGL
• OpenGL (Open Graphics Library) is a cross-platform API (Application
Programming Interface) for rendering 2D and 3D graphics. It provides a set
of functions that allows developers to interact with the graphics hardware
to create interactive graphics applications. OpenGL is a hardware-
independent, operating system independent, vendor neutral graphics API
specification. OpenGL is window system independent, and therefore
contains no windowing operations or mechanisms for user input. Also,
OpenGL does not provide direct support for complex geometrical shapes,
such as cubes or spheres. These must be built up from supported primitives.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Introduction to OpenGL
• Cross language – we can implement it in any language like
c, c++ , java
• Cross platform – it can be implemented in an platform like
ios, android, mac os , windows
• It is already defined in the kernel of an operating system,
use to process graphics.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Architecture of OpenGL
• OpenGL follows a client-server architecture.
• The client is the application that uses OpenGL to render graphics,
and the server is the OpenGL implementation provided by the
graphics driver.
• The client sends drawing commands and data to the server, which
then processes these commands and interacts with the graphics
hardware to render the scene. OpenGL has been designed using a
client/server paradigm, allowing the client application and the
graphics server controlling the display hardware to exist on the same
or separate machines. The network is transparent to the application.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Architecture of OpenGL

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Architecture of OpenGL
• The first stage in the pipeline is the evaluator. This stage effectively takes any
polynomial evaluator commands and evaluates them into their corresponding
vertex and attribute commands.
• The second stage is the per-vertex operations, including transformations, lighting,
primitive assembly, clipping, projection, and viewport mapping.
• The third stage is rasterization. This stage produces fragments, which are series of
framebuffer addresses and values, from the viewport-mapped primitives.
• The fourth stage is the per-fragment operations. Before fragments go to the
framebuffer, they may be subjected to a series of conditional tests and
modifications, such as blending or z-buffering.
• Parts of the framebuffer may be fed back into the pipeline as pixel rectangles.
Texture memory may be used in the rasterization process when texture
mapping(2D image & mapping ) is enabled.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Primitives and Attributes
• OpenGL supports several primitive types that serve as the
building blocks for creating graphics. Common primitives include
points, lines, and triangles. These primitives can be used to
construct more complex shapes and objects. For each primitive,
various attributes can be specified, such as position, color, texture
coordinates, normals, etc. These attributes define how the
primitive will appear on the screen.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Primitives and Attributes
• Most objects (with the exception of pixel rectangles and
bitmaps), use Begin/End primitives. Each Begin/End
primitive contains a series of vertex data, and may
optionally contain normals, texture coordinates, colors, edge
flags, and material properties.
• There are ten primitive types, as follows:

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

Sub. Teacher :- Prof. Priyanka Shreyas Bhore
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Simple Modeling and Rendering
• An OpenGL® display can be an entire screen, which is known as
full-screen mode, or it can be only the area inside a window within
a graphical user interface (GUI) or a small panel embedded in a
larger layout, when the larger layout is not managed by OpenGL.
Some operating systems and computer configurations use
OpenGL as the default method for drawing to a screen, meaning
that, technically, everything shown on the monitor is contained in
an OpenGL display.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Simple Modeling and Rendering
• From a computer graphics programming perspective, however, an
OpenGL® display needs to be a known quantity that is created with
specific attributes such as dimensions, color depth and other
properties. The display itself is basically a rectangular Cartesian grid
that relates to the rectangular area of the physical screen on which it
will appear. The graphics hardware and OpenGL drivers both use the
attributes of the OpenGL display during the process of rasterization,
which involves turning three-dimensional (3D) objects that are
defined mathematically into two-dimensional (2D) pixels that are
placed on the display surface.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Simple Modeling and Rendering
• To model and render 2D or 3D geometric objects, you typically perform the
following steps:
• Initialize OpenGL: Set up the OpenGL context and specify its properties, such as
the display mode and buffer(for visual output).
• Define Geometric Objects: Specify the vertex data for the geometric objects you
want to create. This includes defining the vertices' positions and other attributes.
• Shading: Choose shading models, such as flat shading, smooth shading, or using
materials and lighting.
• Transformations: Apply transformation matrices (e.g., translation, rotation,
scaling) to position and orient objects in the 3D world.
• Rendering: Issue OpenGL commands to render the geometric objects to the
screen.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 GLUT
• GLUT(OpenGL Utility Toolkit): GLUT is a library that
simplifies the process of creating windows and handling
events in OpenGL applications. It provides functions for
creating windows, handling input from the keyboard and
mouse, and managing timers for animations.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Interaction and Events:
• To enable interaction with an OpenGL application, you can use GLUT's
callback mechanism. Callback functions are functions you define that get
called by GLUT when specific events occur, such as mouse clicks or
keyboard presses. Examples of common callback functions include:
• a. Display Callback: Called when the window needs to be redrawn (e.g.,
after resizing or other updates).
• b. Keyboard Callback: Called when a key on the keyboard is pressed or
released.
• c. Mouse Callback: Called when a mouse button is pressed or released.
• d. Motion Callback: Called when the mouse moves.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Picking:

• Picking is a technique to determine which object or

primitive the user has selected with the mouse.
When the user clicks on the screen, the application
performs a picking algorithm to identify the object
or primitive at the clicked location.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

To implement simple interaction with the mouse and
keyboard in an OpenGL application using GLUT,
you need to:
• Register the appropriate callback functions to handle keyboard and mouse
events.
• In the callback functions, implement the necessary logic to respond to the
user's input.
• For picking, use ray casting (Ray casting is a rendering technique used in
computer graphics and computational geometry) or other techniques to
identify the objects or primitives at the mouse click position.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Scan conversion:
• Line drawing algorithms
1. Digital Differential Analyzer Algorithm
2. Bresenham
• Circle drawing algorithms
1. DDA
2. Bresenham
3. Midpoint.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Digital Differential Analyzer Algorithm

• DDA for Line

• It stands for digital differential analyzer. it is an
incremental method of scan conversion of line. In this
method calculation is performed at each step but by using
result of previous step.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Digital Differential Analyzer Algorithm
• Example : - Explanation with values
• Consider p1(5,5) p2(10,9)
• X1 =5 , y1 =5
X= 5 y=5 //starting point (5,5)
• X2= 10 , y2= 9
• For next point
• Dx= 10-5 =5 X= 5+1=6
Y= 5+0.8 =5.8
• Dy = 9-5 =4 Next point (6,6)
• If (5>4) step = 5 Repeat until x= 10
• Xinc = 5/5 =1
• Yinc= 4/5 =0.8
Sub. Teacher :- Prof. Priyanka Shreyas Bhore

•
 Digital Differential Analyzer Algorithm

X1 Y1 Xp+1 Yp+1 Round(Xp+1, Yp+1)

5 5 6 5.8 (6,6)
6 5.8 7 6.6 (7,7)
7 6.6 8 7.4 (8,7)
8 7.4 9 8.2 (9,8)
9 8.2 10 9 (10,9)

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Digital Differential Analyzer Algorithm
Y-Values
10
9
8
7
6
5
4
3
2
1
0
0 2 4 6 8 10 12
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham Line Algorithm
• Bresenham's Line Algorithm is a rasterization algorithm used to draw a
straight line between two points in a discrete coordinate system, such as a
computer screen.
• It is used for scan converting a line.
• It involves only integer addition, subtraction and multiplication operations.
• Next pixel selected is that one who has the least distance from true line.
• The main advantage of Bresenham's algorithm is that it uses only integer
arithmetic, which makes it faster than other line-drawing algorithms that
involve floating-point calculations. It is particularly useful in environments
where floating-point operations are costly or not available.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham's Line Algorithm
• Here is the basic idea of Bresenham's Line Algorithm:
• Input two endpoints: (x0, y0) and (x1, y1), where (x0, y0) is the starting point and
(x1, y1) is the ending point of the line.
• Determine the differences between the endpoint coordinates: dx = x1 - x0 and dy
= y1 - y0.
• Calculate the decision parameter, also known as the decision variable: d = 2 * dy -
dx
• Start at the initial point (x0, y0), and for each x-coordinate from x0 to x1:
• Plot the pixel at the current position (x, y).
• If d > 0, increment y by 1 (go up).
• Update d based on the current value of d.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham's Line Algorithm

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

• Explanation with example:
• P1(5,5) p2(13,9)
• X0= 5
• Y0= 5
• dx= 13-5 =8 dy = 9-5 = 4
• P0 = 2*4-8= 0
• Here p0 = 0
• P1 = 0+ 2*4 -2*8 =-8 and (6,6)
• Now at (6,6) pk<0
• (7,6) p1= -8 +2 *4=0
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham's Line Algorithm
Sr. No. Plot x Y p
5 5 0
1 (5,5) 6 6 -8
2 (6,6) 7 6 0
3 (7,6) 8 7 -8
4 (8,7) 9 7 0
5 (9,7) 10 8 -8
6 (10,8) 11 8 0
7 (11,8) 12 9 -8
8 (12,9) 13 9 0
(13,9)
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham's Line Algorithm

Y-Values
10

0
0 2 4 6 8 10 12 14

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Circle drawing algorithms
• DDA,
• Bresenham, and
• Midpoint
• Drawing a circle on the screen is a little
complex than drawing a line.
• The equation of circle is x2 + y2 = r2
,where r is radius.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 DDA Circle drawing algorithms
• This is an incremental mechanism algorithm.
• The equation at origin (0,0) is x2 + y2 = r2
• DDA differential equation for circle drawing for circle drawing is =0
2xdx +2ydy = 0
xdx+ydy =0
ydy = -xdx or dy/dx =-x/y
This algorithm starts drawing the circle from the initial point and compute
ε (epsilon) by which the x and y co- ordinates should be increased or
decreased.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 DDA Circle drawing algorithms
• Now we can construct the circle by using incremental x value ∆x=εy and
incremental y value ∆y= -εx , where ε is calculated by radius of circle.
• The increment ε is derived as follow. First find the n such that
2n-1 <= R <= 2n (2*2*2*2*2*2) where 25 =32 & 26 =64
2n-1 <= 50 <= 2n
32<=50<=64 now n= 6
ε = 1/26 = 0.0156
Now Appling these incremental steps we have
𝒙𝒏+𝟏 = 𝒙 𝒏 + ε𝒚 𝒏 and 𝒚𝒏+𝟏 = 𝒚 𝒏 - ε𝒙 𝒏
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 DDA Circle drawing algorithms
𝒙𝒏+𝟏 = 𝒙 𝒏 + ε𝒚 𝒏 and 𝒚𝒏+𝟏 = 𝒚 𝒏 - ε𝒙 𝒏

The Points plotted using above equation gives the spiral instead of
the circle
To get the circle we have to make correction in the equation
Replace 𝒙 𝒏 by 𝒙𝒏+𝟏 in the equation of 𝒚𝒏+𝟏

𝒚𝒏+𝟏 = 𝒚 𝒏 - ε 𝒙𝒏+𝟏

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 DDA Circle drawing algorithms
• DDA_Circle(r) //r : radius of circle
• Find the value of n such that 2n-1 <= r <= 2n
• Compute value of ε : ε = 1/ 2n
• 𝒔𝒕𝒂𝒓𝒕_𝒙 =0 and start_𝒚 = r
• Set initial points of circle : 𝒙𝟏 = 𝒔𝒕𝒂𝒓𝒕_𝒙 , 𝒚𝟏 = start_𝒚
• Do { 𝒙𝟐 = 𝒙𝟏 + ε . 𝒚𝟏
• 𝒚𝟐 = 𝒚𝟏 - ε . 𝒙𝟐 (here 𝒙𝟐 represents 𝒙𝒏+𝟏 and 𝒙 𝟏 represents 𝒙 𝒏 )

• Plot ( int (𝒙𝟐 ) , int (𝒚𝟐 ))

• Set 𝒙𝟏 = 𝒙𝟐 and 𝒚𝟏 = 𝒚𝟐
• Reinitialize the current point
• } While ((𝒚𝟏 − start_y) < ε OR (𝒔𝒕𝒂𝒓𝒕 _𝒙 − 𝒙𝟏 )> ε )
• ( check if the current point is the starting point or not. If current point is not starting point repeat
step 4; otherwise stop)
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
• End
 Bresenham's Circle drawing Algorithm
• Bresenham’s circle drawing algorithm considers
the eight way symmetry of the circle to generate.
It plots 1/8th part of the circle.
• As we want to generate circle points from 90° to
45°, X moves in positive direction and y moves
in negative direction.
• Let us assume we have a point p (x, y) on the
boundary of the circle and with r radius
satisfying the equation fc (x, y) = 0

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Bresenham's Circle drawing Algorithm
• as we know the equation of the circle is –
• fc (x, y) = x2 + y2 = r2
• If
• fc (x, y) < 0
• then
• The point is inside the circle boundary.
• If
• fc (x, y) = 0
• then
• The point is on the circle boundary.
• If
• fc (x, y) > 0
• then
• The point is outside the circle boundary.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham's Circle drawing Algorithm
• We assume,
• The distance between point P3 and circle
boundary = d1
• The distance between point P2 and circle
boundary = d2
• Now, if we select point P3 then circle
equation will be-
• d1 = (xk +1)2 + (yk)2 – r2 {Value is
+ve, because the point is outside the
circle}
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham's Circle drawing Algorithm

• if we select point P2 then circle equation will be-

• d2 = (xk +1)2 + (yk -1)2 – r2 {Value is -ve,
because the point is inside the circle}
• Now, we will calculate the decision
parameter (dk) = d1 + d2
• dk =(xk +1)2 + (yk)2 – r2 + (xk +1)2 + (yk -1)2 –
r2
• = 2(xk +1)2 + (yk)2+ (yk -1)2 –
2r2 …………………… (1)
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham's Circle drawing Algorithm
• If
• dk < 0
• then
• Point P3 is closer to circle boundary, and the final coordinates are-
• (xk +1, yk) = (xk +1, yk)
• If
• dk >= 0
• then
• Point P2 is closer to circle boundary, and the final coordinates are-
• (xk +1, yk) = (xk +1, yk -1)
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham's Circle drawing Algorithm
• Now, we will find the next decision parameter (dk+1)
• (dk+1) = 2(xk+1 +1)2 + (yk+1)2+ (yk+1 -1)2 – 2r2 ……………… (2)
• Now, we find the difference between decision parameter equation (2) - equation (1)
• (dk+1) – (dk) = 2(xk+1+1)2 + (yk+1)2+ (yk+1 –1)2 – 2r2 – 2(xk +1)2 + (yk)2+ (yk– 1)2 –
2r2
• (dk+1) = dk + 4xk + 2(yk+12– yk2) – (yk+1 – yk) + 6
• Now, we check two conditions for decision parameter-
• Condition 1: If
• dk < 0
• then
• yk+1 = yk (We select point P3)
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Bresenham's Circle drawing Algorithm
• Condition 2: If
• dk >= 0
• then
• yk+1 = yk-1 (We select point P3)
• Now, we calculate initial decision parameter (d0)
• d0 = d1 + d2
• d0 = {12 +r2– r2} + {12 +(r – 1)2 – r2}
• d0 = 3 – 2r

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Bresenham's Circle drawing Algorithm
• Read the radius(r) of the circle
• d= 3-2r (initialize the decision parameter)
• x =0, y= r (initialize starting point)
• do{ plot(x, y)
• if (d<0) then { d = d+4x+6 }
• else { d= d+4(x-y ) +10
• y=y-1 }
• x= x+1
• } while ( x<y)
• stop
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Mid-Point Circle Drawing Algorithm
• The mid-point circle drawing algorithm is
an algorithm used to determine the points
needed for rasterizing a circle.
• The midpoint circle drawing
algorithm helps us to calculate the complete
perimeter points of a circle for the first
octant.
• We can quickly find and calculate the points
of other octants with the help of the first
octant points. The remaining points are the
mirror reflection of the first octant points.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Mid-Point Circle Drawing Algorithm
• In the algorithm, we will use the 8-way
symmetry property.
• In this algorithm, we define the unit
interval and consider the nearest point
of the circle boundary in each step.
• Let us assume we have a point a (p,
q) on the boundary of the circle and
with r radius satisfying the
equation fc (p, q) = 0
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Mid-Point Circle Drawing Algorithm
• As we know the equation of the circle is –
• fc (p, q) = p2 + q2 = r2 …………………………… (1)
• If fc (p, q) < 0
• then The point is inside the circle boundary.
• If fc (p, q) = 0
• Then The point is on the circle boundary.
• If fc (p, q) > 0
• Then The point is outside the circle boundary.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Mid-Point Circle Drawing Algorithm
• In the figure, we calculate the mid-
point (m). The midpoint appears
between qk and qk -1.
• The current position of the pixel
= pk +1
• The next position of the pixel
• = (pk +1, qk) (outside of boundary)
and (pk +1,qk - 1) (inside of boundary)
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Mid-Point Circle Drawing Algorithm
Derivation :-
Midpoint M : (pm , qm ) Now, we will calculate the decision
parameter (dk)
( (pk +1 + pk +1)/2 , (qk + qk - 1)/2 )
Now, we replace all the values with
• = ( 2(pk +1)/2 , 2(qk - ½) /2 ) equation (1)
d = (p +1)2 + (q – 1/2)2 –
• = (pk +1 , qk – ½) k k k
r2 ………………… (2)

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Mid-Point Circle Drawing Algorithm
• Now, there should be two conditions.
• Condition 1: If
• dk is negative
• then
• The midpoint (m) is inside the circle boundary
• Condition 2: If
• dk is positive
• then
• The midpoint (m) is outside the circle boundary
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Mid-Point Circle Drawing Algorithm
• Now, we find the next point of x coordinates. Then,
• Pk+1 +1 = Pk+2
• Now, we replace all the value of equation (2) with (k+1). We get-
• dk+1 = (pk+1 +1)2 + (qk+1 – 1/2)2 – r2 ……………………………. (3)
• Now, we will find the difference between
• dk+1 – dk = {(pk+1 +1)2 + (qk+1 – 1/2)2 – r2} – {(pk +1)2 + (qk – 1/2)2 – r2}
• = dk +(2pk +1) + (qk+12 – qk2) – (qk+1 – qk) +1 …………………… (4)

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Mid-Point Circle Drawing Algorithm
• Here, If dk is negative then dk+1
• then
• 2pk+1 +1
• Otherwise
• 2pk+1 +1 – 2qk+1
• Now, the next coordinate for x and y points
• 2pk+1 = 2pk +2
• 2qk+1 = 2qk –2
Sub. Teacher :- Prof. Priyanka Shreyas Bhore
 Mid-Point Circle Drawing Algorithm
• Now, the initial decision parameter (d0) at the position (p, q) =
(0, r)
• We put (0, r) in circle equation and we get-
• d0 = (1, r – 1/2)
• = (1 + (r –1/2)2 –r2)
• = 5/4 –r
• We only take integer value = 1 – r

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Mid-Point Circle Drawing Algorithm
1. Plot The initial point (xi , yi ) such that xi = 0, yi = r
2. Find initial decision parameter
Pi = 5/4 –r = 1.25 – r = 1- r
3. If Pi < 0 then xi+1 = xi + 1 and yi+1 = yi
Pi +1 = Pi + 2 xi + 3
4. If Pi >= 0 then xi+1 = xi + 1 and yi+1 = yi - 1
Pi +1 = Pi + 2( xi – yi )+ 5
5. Repeat step 3 and 4 until x becomes greater than or equal to y.

Sub. Teacher :- Prof. Priyanka Shreyas Bhore

 Mid-Point Circle Drawing Algorithm
Advantages of Midpoint circle drawing algorithm
• It is a powerful and efficient algorithm.
• The midpoint circle drawing algorithm is easy to implement.
• It is also an algorithm based on a simple circle equation (x2 + y2 = r2).
• This algorithm helps to create curves on a raster display.
Disadvantages of Midpoint circle drawing algorithm
• It is a time-consuming algorithm.
• Sometimes the points of the circle are not accurate.
Sub. Teacher :- Prof. Priyanka Shreyas Bhore