Computer Graphics

(CoSc3121)
1

EAST AFRICA COLLAGE

DEPARTMENT OF COMPUTER SCIENCE

CHAPTER TWO- PART ONE

GRAPHICS PRIMITIVES
 Chapter Two- Graphics Primitives
2

Point Drawing in
OpenGL

Line Drawing
Algorithms

Circle Drawing
Algorithms

Fill-Area Primitives

Computer Graphics- CoSc3121

 3
Point Drawing in OpenGL
Points are the most basic type of primitive.
Point Drawing in  glPointSize(2.0); //set the size of the points in pixels
OpenGL  The default point size is 1 pixel.
 Points that have a size greater than one pixel are
Line Drawing drawn as squares .
Algorithms
 glBegin(GL_POINTS); // draw 3 points
Circle Drawing glVertex2f(100.0, 200.0);
Algorithms
glVertex2f(150.0, 200.0);
Fill-Area Primitives glVertex2f(150.0, 250.0);
glEnd();
 GL_POINTS : specify how the vertices in
between should be interpreted.
 There is only 3D in OpenGL.
 2D + constant Z coordinate (equal to zero)

Computer Graphics- CoSc3121

 4
Lines
 Lines are a very common primitive and will
be supported by almost all graphics packages.
Point Drawing in  Lines are normally represented by the two
OpenGL
end-points.
Line Drawing
Algorithms

Circle Drawing
Algorithms

Fill-Area Primitives

 yend  y0  c  y0  mx0
m
xend  x0  δy = m.δx
δx = (1/m).δy
Computer Graphics- CoSc3121
 5
Digital Differential Analyzer Algorithm
•The Digital Differential Analyser (DDA) algorithm operates by starting at one end-point of the
line, and to generate successive pixels until the second end-point is reached.

Point Drawing in  Given (x0,y0) and (xend,yend)

OpenGL  Compute m
 If |m| ≤ 1:
Line Drawing
 δx = 1
Algorithms
 δy = m

 If |m| > 1:
DDA Algorithm
 δx = 1/m

 δy = 1
Bresenham’s  Paint (x0,y0)
Algorithm  Find successive pixel positions
 xk+1 = (xk + δx)
Circle Drawing  yk+1 = (yk + δy)
Algorithms  For each position (xk,yk) plot a
line point at
The gap between subsequent
 (round(xk),round(yk))
Fill-Area Primitives points in the line is greater than 1
 The round function will round to pixel.
the nearest integer.
Computer Graphics- CoSc3121
 6
Digital Differential Analyzer Algorithm
Example1

Point Drawing in
 Given (x0,y0) = (10,10)  yend  y0  (13  10) 3
m    0.6
OpenGL
 and (xend,yend) = (15,13)
xend  x0  (15  10) 5
 Compute m
Line Drawing  If |m| ≤ 1:
Algorithms  δx = 1
δx = 1
 δy = m δy = 0.6
 If |m| > 1:
DDA Algorithm
 δx = 1/m

 δy = 1
Bresenham’s  Paint (x0,y0) (xend,yend) = (15,13)
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 7
Digital Differential Analyzer Algorithm
Example1

Point Drawing in
 Given (x0,y0) = (10,10)  yend  y0  (13  10) 3
m    0.6
OpenGL
 and (xend,yend) = (15,13)
xend  x0  (15  10) 5
 Compute m
Line Drawing  If |m| ≤ 1:
Algorithms  δx = 1
δx = 1
 δy = m δy = 0.6
 If |m| > 1:
DDA Algorithm
 δx = 1/m

 δy = 1
Bresenham’s  Paint (x0,y0) (xend,yend) = (15,13)
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 8
Digital Differential Analyzer Algorithm
Example1
 Paint (x0,y0) δx = 1
Point Drawing in  Find successive pixel δy = 0.6
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x1,y1) = (10+1,10+0.6)
Algorithms = (11,10.6)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (11,11)
DDA Algorithm

Bresenham’s (xend,yend) = (15,13)

Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 9
Digital Differential Analyzer Algorithm
Example1
 Paint (x0,y0) δx = 1
Point Drawing in  Find successive pixel δy = 0.6
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x2,y2) = (11+1,10.6+0.6)
Algorithms = (12,11.2)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (12,11)
DDA Algorithm

Bresenham’s (xend,yend) = (15,13)

Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 10
Digital Differential Analyzer Algorithm
Example1
 Paint (x0,y0) δx = 1
Point Drawing in  Find successive pixel δy = 0.6
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x3,y3) = (12+1,11.2+0.6)
Algorithms = (13,11.8)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (13,12)
DDA Algorithm

Bresenham’s (xend,yend) = (15,13)

Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 11
Digital Differential Analyzer Algorithm
Example1
 Paint (x0,y0) δx = 1
Point Drawing in  Find successive pixel δy = 0.6
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x4,y4) = (13+1,11.8+0.6)
Algorithms = (14,12.4)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (14,12)
DDA Algorithm

Bresenham’s (xend,yend) = (15,13)

Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 12
Digital Differential Analyzer Algorithm
Example1
 Paint (x0,y0) δx = 1
Point Drawing in  Find successive pixel δy = 0.6
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x5,y5) = (14+1,12.4+0.6)
Algorithms = (15,13)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (15,13)
DDA Algorithm

Bresenham’s (xend,yend) = (15,13)

Algorithm

Circle Drawing
Algorithms
Figure - The Operation of the DDA Line-
Draiwng Algorithm

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 13
Digital Differential Analyzer Algorithm
Example2

Point Drawing in
 Given (x0,y0) = (10,10)
m
 yend  y0   (15  10)  5  1.25
OpenGL
 and (xend,yend) = (14,15) xend  x0  (14  10) 4
 Compute m
Line Drawing  If |m| ≤ 1:
δx = 0.8
Algorithms  δx = 1
δy = 1
 δy = m

 If |m| > 1: (xend,yend) = (14,15)

DDA Algorithm
 δx = 1/m

 δy = 1
Bresenham’s  Paint (x0,y0)
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 14
Digital Differential Analyzer Algorithm
Example2

Point Drawing in
 Given (x0,y0) = (10,10)
m
 yend  y0   (15  10)  5
OpenGL
 and (xend,yend) = (14,15) xend  x0  (14  10) 4
 Compute m
Line Drawing  If |m| ≤ 1:
δx = 0.8
Algorithms  δx = 1
δy = 1
 δy = m

 If |m| > 1: (xend,yend) = (14,15)

DDA Algorithm
 δx = 1/m

 δy = 1
Bresenham’s  Paint (x0,y0)
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 15
Digital Differential Analyzer Algorithm
Example2
 Paint (x0,y0) δx = 0.8
Point Drawing in  Find successive pixel δy = 1
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x1,y1) = (10+0.8,10+1)
Algorithms = (10.8,11)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (11,11)
DDA Algorithm
(xend,yend) = (14,15)

Bresenham’s
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 16
Digital Differential Analyzer Algorithm
Example2
 Paint (x0,y0) δx = 0.8
Point Drawing in  Find successive pixel δy = 1
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x2,y2) = (10.8+0.8,11+1)
Algorithms = (11.6,12)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (12,12)
DDA Algorithm
(xend,yend) = (14,15)

Bresenham’s
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 17
Digital Differential Analyzer Algorithm
Example2
 Paint (x0,y0) δx = 0.8
Point Drawing in  Find successive pixel δy = 1
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x3,y3) = (11.6+0.8,12+1)
Algorithms = (12.4,13)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (12,13)
DDA Algorithm
(xend,yend) = (14,15)

Bresenham’s
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 18
Digital Differential Analyzer Algorithm
Example2
 Paint (x0,y0) δx = 0.8
Point Drawing in  Find successive pixel δy = 1
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x4,y4) = (12.4+0.8,13+1)
Algorithms = (13.2,14)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (13,14)
DDA Algorithm
(xend,yend) = (14,15)

Bresenham’s
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 19
Digital Differential Analyzer Algorithm
Example2
 Paint (x0,y0) δx = 0.8
Point Drawing in  Find successive pixel δy = 1
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x5,y5) = (13.2+0.8,14+1)
Algorithms = (14,15)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (14,15)
DDA Algorithm
(xend,yend) = (14,15)

Bresenham’s
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives
(x0,y0) = (10,10)
Computer Graphics- CoSc3121
 20
Digital Differential Analyzer Algorithm
Example2
 Paint (x0,y0) δx = 0.8
Point Drawing in  Find successive pixel δy = 1
OpenGL positions
 xk+1 = (xk + δx)
Line Drawing  yk+1 = (yk + δy)
(x5,y5) = (13.2+0.8,14+1)
Algorithms = (14,15)
 For each position (xk,yk)
plot a line point at
 (round(xk),round(yk))
colour pixel (14,15)
DDA Algorithm
(xend,yend) = (14,15)

Bresenham’s
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 21

Digital Differential Analyzer Algorithm

Exercise1
Point Drawing in
 Consider the above examples and
OpenGL plotting the line using DDA algorithm:
 Given (x0,y0) = (5,5) and (xend,yend) = (10,9)
Line Drawing
Algorithms

Exercise2
DDA Algorithm
 Consider the above examples and
plotting the line using DDA algorithm:
Bresenham’s  Given (x0,y0) = (2,2) and (xend,yend) = (6,12)
Algorithm

Circle Drawing Exercise3

Algorithms  Write a fragment of OpenGL code to
draw three points in GLUT window?
Fill-Area Primitives  Given P1(50.0,100.0), P2(100.0,200.0) and
P3(200.0,100.0)

Computer Graphics- CoSc3121

 22
Bresenham’s Line-Drawing Algorithm
•Given (x0,y0) and (xend,yend)
•Compute m
 |m| < 1
Point Drawing in
OpenGL  Plot (x0,y0)
 Compute the first
Line Drawing decision variable:
Algorithms p0  2y  x
 For each k, starting with
DDA Algorithm k=0:
 If pk < 0:

Bresenham’s  Plot (xk+1,yk)

Algorithm
pk 1  pk  2y
Circle Drawing
 Otherwise:
Algorithms
 Plot (xk+1,yk+1)
pk 1  pk  2y  2x
Fill-Area Primitives

Computer Graphics- CoSc3121

 23
Bresenham’s Line-Drawing Algorithm
•Given (x0,y0) and (xend,yend)
•Compute m
 |m| < 1  |m| ≥ 1
Point Drawing in
OpenGL  Plot (x0,y0)  Plot (x0,y0)
 Compute the first  Compute the first
Line Drawing decision variable: decision variable:
Algorithms p0  2y  x p0  2x  y
 For each k, starting with  For each k, starting with
DDA Algorithm k=0: k=0:
 If pk < 0:  If pk < 0:

Bresenham’s  Plot (xk+1,yk)  Plot (xk,yk+1)

Algorithm
pk 1  pk  2y pk 1  pk  2x
Circle Drawing
 Otherwise:  Otherwise:
Algorithms
 Plot (xk+1,yk+1)  Plot (xk+1,yk+1)
pk 1  pk  2y  2x pk 1  pk  2x  2y
Fill-Area Primitives

Computer Graphics- CoSc3121

 24
Bresenham’s Line-Drawing Algorithm
•Example Given (x0,y0) = (10,10) and (xend,yend) = (15,13)
Compute m
 |m| < 1 m = 0.6 < 1
Point Drawing in
OpenGL  Plot (x0,y0)
 Compute the first
Line Drawing decision variable:
Algorithms p0  2y  x

DDA Algorithm

Bresenham’s (xend,yend) = (15,13)

Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 25
Bresenham’s Line-Drawing Algorithm
•Given (x0,y0) = (10,10) and (xend,yend) = (15,13)
•Compute m
 |m| < 1 m = 0.6 < 1
Point Drawing in
OpenGL  Plot (x0,y0) Δx = 5
 Compute the first Δy = 3
Line Drawing decision variable: 2Δy = 6
Algorithms p0  2y  x 2Δy - 2Δx = -4

DDA Algorithm p0  2y  x  2  3  5  1

Bresenham’s (xend,yend) = (15,13)
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 26
Bresenham’s Line-Drawing Algorithm
m = 0.6 < 1
 |m| < 1 Δx = 5 Δy = 3 2Δy = 6
Point Drawing in
 Plot (x0,y0) 2Δy - 2Δx = -4
OpenGL p0 =1
 For each k, starting with
p0 ≥ 0, so
Line Drawing k=0: Plot (x1,y1) = (x0+1,y0+1) =
Algorithms  If pk < 0: (11,11)
 Plot (xk+1,yk) p1  p0  2y  2x
DDA Algorithm
 1  4  3
pk 1  pk  2y
Bresenham’s  Otherwise: (xend,yend) = (15,13)
Algorithm  Plot (xk+1,yk+1)

Circle Drawing pk 1  pk  2y  2x

Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 27
Bresenham’s Line-Drawing Algorithm
m = 0.6 < 1
 |m| < 1 Δx = 5 Δy = 3 2Δy = 6
Point Drawing in
 Plot (x0,y0) 2Δy - 2Δx = -4
OpenGL
 For each k, starting with p1 = -3
Line Drawing k=0: p1 < 0, so
Algorithms  If pk < 0:
Plot (x2,y2) = (x1+1,y1) =
(12,11)
 Plot (xk+1,yk)
p2  p1  2y
DDA Algorithm
pk 1  pk  2y  3  6  3
Bresenham’s  Otherwise: (xend,yend) = (15,13)
Algorithm  Plot (xk+1,yk+1)

Circle Drawing pk 1  pk  2y  2x

Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 28
Bresenham’s Line-Drawing Algorithm
m = 0.6 < 1
 |m| < 1 Δx = 5 Δy = 3 2Δy = 6
Point Drawing in
 Plot (x0,y0) 2Δy - 2Δx = -4
OpenGL
p2 =3
 For each k, starting with
p2 ≥ 0, so
Line Drawing k=0:
Plot (x3,y3) = (x2+1,y2+1)
Algorithms  If pk < 0:
= (13,12)
 Plot (xk+1,yk)
p3  p2  2y  2x
DDA Algorithm
pk 1  pk  2y  3  4  1

Bresenham’s  Otherwise: (xend,yend) = (15,13)

Algorithm  Plot (xk+1,yk+1)

Circle Drawing pk 1  pk  2y  2x

Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 29
Bresenham’s Line-Drawing Algorithm
m = 0.6 < 1
 |m| < 1 Δx = 5 Δy = 3 2Δy = 6
Point Drawing in
 Plot (x0,y0) 2Δy - 2Δx = -4
OpenGL
p3 = -1
 For each k, starting with
p3 < 0, so
Line Drawing k=0:
Plot (x4,y4) = (x3+1,y3) =
Algorithms  If pk < 0:
(14,12)
 Plot (xk+1,yk)
DDA Algorithm p4  p3  2y
pk 1  pk  2y  1  6  5
Bresenham’s  Otherwise: (xend,yend) = (15,13)
Algorithm  Plot (xk+1,yk+1)

Circle Drawing pk 1  pk  2y  2x

Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 30
Bresenham’s Line-Drawing Algorithm
m = 0.6 < 1
 |m| < 1 Δx = 5 Δy = 3 2Δy = 6
Point Drawing in
 Plot (x0,y0) 2Δy - 2Δx = -4
OpenGL
 For each k, starting with p4 =5,
Line Drawing k=0: p4 ≥ 0, so
Algorithms  If pk < 0:
Plot (x5,y5) = (x4+1,y4+1)
= (15,13)
 Plot (xk+1,yk)
DDA Algorithm
pk 1  pk  2y
Bresenham’s  Otherwise: (xend,yend) = (15,13)
Algorithm  Plot (xk+1,yk+1)

Circle Drawing pk 1  pk  2y  2x

Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 31
Bresenham’s Line-Drawing Algorithm
m = 0.6 < 1
 |m| < 1 Δx = 5 Δy = 3 2Δy = 6
Point Drawing in
 Plot (x0,y0) 2Δy - 2Δx = -4
OpenGL
 For each k, starting with p4 =5,
Line Drawing k=0: p4 ≥ 0, so
Algorithms  If pk < 0:
Plot (x5,y5) = (x4+1,y4+1)
= (15,13)
 Plot (xk+1,yk)
DDA Algorithm
pk 1  pk  2y
Bresenham’s  Otherwise: (xend,yend) = (15,13)
Algorithm  Plot (xk+1,yk+1)

Circle Drawing pk 1  pk  2y  2x

Algorithms

Fill-Area Primitives (x0,y0) = (10,10)

Computer Graphics- CoSc3121

 32
Bresenham’s vs. DDA
Line Drawing Algorithms
Point Drawing in
OpenGL  They plot the same pixels.
Line Drawing  Bresenham’s algorithm use only
Algorithms integer operations.
 Bresenham’s algorithm is more
DDA Algorithm
efficient than DDA.
Bresenham’s  Bresenham’s algorithm preferable
Algorithm for line drawing than DDA in
Circle Drawing
computer Graphics.
Algorithms

Fill-Area Primitives

Computer Graphics- CoSc3121

 33
OpenGL Line Drawing
•GL_LINES : specify that vertices should be
Point Drawing in interpreted as line end-points.
OpenGL •glLineWidth(3.0); //set the width of the line

Line Drawing •For example, the following code will draw two
Algorithms separate line segments:
•One line from (100,200) to (150,200)
DDA Algorithm •Another line from (150,250) to (200,250)
glLineWidth(3.0);
Bresenham’s glBegin(GL_LINES);
Algorithm glVertex2f(100.0, 200.0);
glVertex2f(150.0, 200.0);
Circle Drawing glVertex2f(150.0, 250.0);
Algorithms glVertex2f(200.0, 250.0);
glEnd();
Fill-Area Primitives

Computer Graphics- CoSc3121

 OpenGL Data Types
34

Computer Graphics- CoSc3121

 Points, Lines and Polygons
35

Computer Graphics- CoSc3121

 Points, Lines and Polygons
36

Computer Graphics- CoSc3121

 37
OpenGL Line Drawing
Example
•GL_LINES : specify that vertices should be interpreted as line end-points.
Point Drawing in •glLineWidth(3.0); //set the width of the line
OpenGL GLint p1[] = {200,100}; GLint p2[] = {50,0};
GLint p3[] = {100,200}; GLint p4[] = {150,0};
GLint p5[] = {0,100};
Line Drawing
Algorithms glBegin(GL_LINES);
glVertex2iv(p1);
glVertex2iv(p2);
DDA Algorithm glVertex2iv(p3);
glVertex2iv(p4);
glVertex2iv(p5);
Bresenham’s glEnd(); (GL_LINES)
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives (GL_LINE_STRIP) (GL_LINE_LOOP)

Computer Graphics- CoSc3121

 38
Circle Drawing Algorithms
Circle
Point Drawing in
OpenGL

Line Drawing
Algorithms

Circle Drawing
Algorithms

Basic Algorithms

Midpoint
Algorithms
 We will examine a number of approaches to
plotting points on a circle, culminating in the most
Fill-Area Primitives
efficient algorithm: the midpoint algorithm.
Computer Graphics- CoSc3121
 39
Circle Drawing Algorithms
1. Plotting Points Using Cartesian Coordinates
Point Drawing in  Incrimenting x and computing y
OpenGL
y  yc  r 2  x  xc 
2
Line Drawing
Algorithms 2. Plotting Points Using Polar Coordinates
 The radius r will be constant and only changing θ
Circle Drawing
Algorithms  Compute x and y

x  xc  r cos y  yc  r sin 
Basic Algorithms
 More efficient than
Midpoint Cartesian one.
Algorithms  Even more efficient
with a little cost in
Fill-Area Primitives quality.

Computer Graphics- CoSc3121

 40
Circle Drawing Algorithms
3. Plotting Points Using Cartesian Coordinates
and Symmetry of Circles
Point Drawing in
OpenGL

Line Drawing
Algorithms

Circle Drawing
Algorithms

Basic Algorithms

 Generates extra points by re-arrangment

Midpoint
Algorithms  Need only compition for one octant of the
circle
Fill-Area Primitives  Still have square root operations and
trigonometric calculations
Computer Graphics- CoSc3121
 41
4. Midpoint Circle Drawing Algorithm
 Given the center and radius r
 Plot the start-point of the
Point Drawing in
circle (x0,y0) = (xc,r)
OpenGL
 Compute the first decision
Line Drawing variable:
Algorithms p0  1  r
 For each k, starting with
Circle Drawing k=0:
Algorithms If pk < 0:
Plot (xk+1,yk)
Basic Algorithms pk 1  pk  2 xk 1  1
Otherwise:
Midpoint Plot (xk+1,yk-1)
Algorithms
pk 1  pk  2 xk 1  1  2 yk 1
Fill-Area Primitives

Computer Graphics- CoSc3121

 42
Midpoint Algorithm Example
 Given the center (0,0) and radius r = 10
 Plot the start-point of the circle (x0,y0) = (xc,r) = (0,10)
Point Drawing in
 Compute the first decision variable:
OpenGL
p0  1  r
Line Drawing
Algorithms (10,10)

Circle Drawing p0 = -9
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 43
Midpoint Algorithm Example
p0 < 0,
Point Drawing in Plot (x1,y1) = (x0+1,y0) = (1,10)
OpenGL
p1  p0  2 x1  1  9  3  6
Line Drawing
Algorithms (10,10)

Circle Drawing p0 = -9
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 44
Midpoint Algorithm Example
p1 < 0,
Plot (x2,y2) = (x1+1,y1) = (2,10)
Point Drawing in
OpenGL p2  p1  2x2  1  6  5  1
Line Drawing
Algorithms (10,10)

Circle Drawing p1 = -6
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 45
Midpoint Algorithm Example
p2 < 0,
Plot (x3,y3) = (x2+1,y2) = (3,10)
Point Drawing in
OpenGL p3  p2  2 x3  1  1  7  6
Line Drawing
Algorithms (10,10)

Circle Drawing p2 = -1
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 46
Midpoint Algorithm Example
p3 ≥ 0
Plot (x4,y4) = (x3+1,y3-1) = (4,9)
Point Drawing in
OpenGL p4  p3  2 x4  1  2 y4  6  9  3
Line Drawing
Algorithms (10,10)

Circle Drawing p3 = 6
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 47
Midpoint Algorithm Example
p4 < 0,
Plot (x5,y5) = (x4+1,y4) = (5,9)
Point Drawing in
OpenGL p5  p4  2 x5  1  3  11  8
Line Drawing
Algorithms (10,10)

Circle Drawing p4 = -3
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 48
Midpoint Algorithm Example
p5 ≥ 0,
Plot (x6,y6) = (x5+1,y5-1) = (6,8)
Point Drawing in
OpenGL p 6  p5  2 x6  1  2 y 6  8  3  5
Line Drawing
Algorithms (10,10)

Circle Drawing p5 = 8
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 49
Midpoint Algorithm Example
p6 ≥ 0,
Plot (x7,y7) = (x6+1,y6-1) = (7,7)
Point Drawing in
OpenGL p7  p6  2 x7  1  2 y7  19 13  6
Line Drawing
Algorithms (10,10)

Circle Drawing p6 = 5
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 50
Midpoint Algorithm Example
p7 ≥ 0,
Plot (x8,y8) = (x7+1,y7-1) = (8,6)
Point Drawing in
OpenGL p8  p7  2 x8  1  2 y8  22 11  11
Line Drawing
Algorithms (10,10)

Circle Drawing p7 = 6
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 51
Midpoint Algorithm Example
p8 ≥ 0,
Plot (x9,y9) = (x8+1,y8-1) = (9,5)
Point Drawing in
OpenGL p9  p8  2 x9  1  2 y9  29  9  20
Line Drawing
Algorithms (10,10)

Circle Drawing p8 = 11
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 52
Midpoint Algorithm Example
p9 ≥ 0,
Plot (x10,y10) = (x9+1,y9-1) = (10,4)
Point Drawing in
OpenGL

Line Drawing
Algorithms (10,10)

Circle Drawing p9 = 20
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives

(0,0)
Computer Graphics- CoSc3121
 53
Bresenham’s Line-Drawing Algorithm
Exercise Given (x0,y0) = (10,10) and (xend,yend) = (14,15)
Compute m
 |m| ≥ 1 m = 1.25 ≥ 1
Point Drawing in
OpenGL  Plot (x0,y0)
 Compute the first
Line Drawing decision variable:
Algorithms p0  2x  y

DDA Algorithm
(xend,yend) = (14,15)
Exercise4
Bresenham’s
 Consider the above
Algorithm
examples and plotting the
line using Bresenham’s
Circle Drawing
algorithm:
Algorithms
 Given (x0,y0) = (10,10) and
(xend,yend) = (14,15)
Fill-Area Primitives
(x0,y0) = (10,10)
Computer Graphics- CoSc3121
 54
Midpoint Algorithm Example
 Given the center (0,0) and radius r = 5
 Plot the start-point of the circle (x0,y0) = (xc,r) = (0,5)
Point Drawing in
 Compute the first decision variable:
OpenGL
p0  1  r
Line Drawing
Algorithms (5,5)

Circle Drawing P = -4
Algorithms Exercise5
 Consider the above
Basic Algorithms example and express the
midpoint circle-drawing
algorithm for a circle
Midpoint centred at the origin.
Algorithms
(0,0)  Given the center (0,0)
and radius r = 5
Fill-Area Primitives

Computer Graphics- CoSc3121

 55
OpenGL Circle Drawing
1. Routine for Wireframe Rendering
Point Drawing in glutWireSphere(GLdouble radius,GLint nSlices, GLint nStacks);
2. Routine for Solid Rendering
OpenGL
glutSolidSphere(GLdouble radius, GLint nSlices, GLint nStacks);
ARGUMENTS
Line Drawing
 radius - The radius of the Sphere / Circle.
Algorithms
 nSlices – Number of Slices (Similar to lines of longitude).
 nStacks – Number of Stacks (Similar to lines of latitude).
Circle Drawing Example1:
Algorithms glutWireSphere(0.5, 50, 50); //draw Wire Sphere / Circle

Basic Algorithms
Exercise6
Midpoint  Consider the above
Algorithms example and create a
OpenGL Circle solid sphere / circle with a
Drawing radius of 1 units.
Fill-Area Primitives
Computer Graphics- CoSc3121
Any Question?