Computer Graphics (CoSc3121)

COMPUTER SCIENCE DEPARTMENT

DEBARK U N I V E R S I T Y

CHAPTER TWO-GRAPHICS PRIMITIVES

 Computer Graphics Chapter Two
2

 Drawing Primitives

 Line Drawing

 Polygon Drawing

 Interaction with mouse/keyboard in OpenGL

 Computer Graphics Chapter Two
3

Point Drawing in
OpenGL

Line Drawing
Algorithms

Circle Drawing
Algorithms

Fill-Area Primitives
 OpenGL Drawing Primitives
4

1. Point Drawing in OpenGL

 Basic type of primitive we use

 The pair of functions glBegin … glEnd

 Symbolic constant GL_POINTS

 to specify how the vertices in between should be interpreted

 glPointSize can be used

 to set the size of the points in pixels
 default point size is 1 pixel.

 Ex. code draws three 2-D points with a size of 2 pixels.

 5
Point Drawing in OpenGL

Point Drawing in  glPointSize(2.0);

OpenGL  glBegin(GL_POINTS);
Line Drawing  glVertex2f(100.0, 200.0);
Algorithms
 glVertex2f(150.0, 200.0);
Circle Drawing  glVertex2f(150.0, 250.0);
Algorithms
 glEnd();
Fill-Area Primitives  GL_POINTS : specify how the
vertices in between should be
interpreted
 There is only 3D in OpenGL.
 2D + constant Z coordinate
 6
2. Line Drawing algorithms

Point Drawing in
OpenGL  Are represented by the two end-points

Line Drawing of the line.

Algorithms
 Line must satisfy the following slope-
Circle Drawing intercept equation:
Algorithms  y = mx + c
 m is the slope and c is the coordinate
Fill-Area Primitives
at which the line intercepts y-axis.
 7
Lines

Point Drawing in
OpenGL

Line Drawing
Algorithms

Circle Drawing
Algorithms

Fill-Area Primitives

 y end  y 0  c  y  mx
m 0 0
x end  x0 
 8
2. Line Drawing algorithms

Point Drawing in
OpenGL  For any given x-interval δx, we can

Line Drawing calculate the corresponding y-interval

Algorithms
δy:
Circle Drawing
 δy = m.δx
Algorithms
 δx = (1/m).δy

Fill-Area Primitives  These equations are a basis for the two

types of line-drawing algorithms.
 9
Digital Differential Analyzer Algorithm
 Given (x0,y0) and (xend,yend)
Point Drawing in  Compute m
OpenGL  If |m| ≤ 1:
 δx = 1

Line Drawing  δy = m

Algorithms  If |m| > 1:

 δx = 1/m

DDA Algorithm  δy = 1

 Paint (x0,y0)
 Find successive pixel positions
Bresenham’s
 xk+1 = (xk + δx)
Algorithm
 yk+1 = (yk + δy)

 For each position (xk,yk) plot a

Circle Drawing
line point at
Algorithms
 (round(xk),round(yk))

Fill-Area Primitives
 10
Digital Differential Analyzer Algorithm
Example
 Given (x0,y0) = (10,10)  yend  y0  (13 10) 3
Point Drawing in m    0.6
 and (xend,yend) = (15,13)
OpenGL 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)

 11
Digital Differential Analyzer Algorithm
Example
 Given (x0,y0) = (10,10)  yend  y0  (13 10) 3
Point Drawing in m    0.6
 and (xend,yend) = (15,13)
OpenGL 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)

 12
Digital Differential Analyzer Algorithm
Example
 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)

 13
Digital Differential Analyzer Algorithm
Example
 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)

 14
Digital Differential Analyzer Algorithm
Example
 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)

 15
Digital Differential Analyzer Algorithm
Example
 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)

 16
Digital Differential Analyzer Algorithm
Example
 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

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

 17
Bresenham’s Line-Drawing Algorithm

 |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
 18
Bresenham’s Line-Drawing Algorithm

 |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+1,yk)

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
 19
Bresenham’s Line-Drawing Algorithm
Example
 |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)

 20
Bresenham’s Line-Drawing Algorithm
Example
 |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)

 21
Bresenham’s Line-Drawing Algorithm
Example
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 p0 ≥ 0, so
Line Drawing k=0: Plot (x1,y1) = (x0+1,y0+1) =
Algorithms (11,11)
 If pk < 0:

 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)

 22
Bresenham’s Line-Drawing Algorithm
Example
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 < 0,
Line Drawing k=0: Plot (x2,y2) = (x1+1,y1) =
Algorithms  If pk < 0: (12,11)
 Plot (xk+1,yk)
p 2  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)

 23
Bresenham’s Line-Drawing Algorithm
Example
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 p2 ≥ 0,
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)

 24
Bresenham’s Line-Drawing Algorithm
Example
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 p3 < 0,
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)

 25
Bresenham’s Line-Drawing Algorithm
Example
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 ≥ 0,
Line Drawing k=0: Plot (x5,y5) = (x4+1,y4+1)
Algorithms  If pk < 0: = (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)

 26
Bresenham’s vs. DDA

Point Drawing in  They plot the same pixels

OpenGL
 DDA is simple and easy to implement.
Line Drawing
Algorithms  It involves floating point operations to

DDA Algorithm calculate each new point.

 Time-consuming
Bresenham’s
Algorithm

Circle Drawing
Algorithms

Fill-Area Primitives
 27
Bresenham’s vs. DDA…

Point Drawing in  Bresenham’s algorithm is more

OpenGL
efficient than DDA
Line Drawing
Algorithms  Bresenham’s algorithm use only

DDA Algorithm integer operations

 Bresenham’s algorithm preferable for

Bresenham’s
Algorithm line drawing than DDA in computer
Circle Drawing Graphics.
Algorithms

Fill-Area Primitives
 28

OpenGL Line Drawing

Point Drawing in
OpenGL  We can draw straight-lines in OpenGL

Line Drawing using glBegin … glEnd functions.

Algorithms
 We can draw different types of straight-
DDA Algorithm
line using different symbolic constant.
Bresenham’s  Examples:
Algorithm
 GL_LINES
Circle Drawing
 GL_LINE_STRIP
Algorithms
 GL_LINE_LOOP
Fill-Area Primitives
 29

OpenGL Line Drawing…

Point Drawing in For example:

OpenGL Glint p1[] = {200,100}; Glint p2[] = {50,0}
Glint p3[] = {100,200}; Glint p4[] = {150,0};
Glint p5[] = {0,100};
Line Drawing
 They will draw separate line segments
Algorithms
glBegin(GL_LINES);
DDA Algorithm glVertex2iv(p1);
glVertex2iv(p2);
glVertex2iv(p3);
glVertex2iv(p4);
Bresenham’s glVertex2iv(p5); (GL_LINE_STRIP)
Algorithm glEnd();

Suffix 2i: number

Circle Drawing and type of
Algorithms arguments

Fill-Area Primitives
(GL_LINE_LOOP)
Questions

30
 31
Circle Drawing Algorithms
Circle
Point Drawing in
OpenGL

Line Drawing
Algorithms

Circle Drawing
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives
 32
Circle Drawing Algorithms
1. Plotting Points Using Cartesian Coordinates
Point Drawing in  Incrimenting x and computing y
OpenGL
2
y  yc  r 2  xc  x
Line Drawing
Algorithms

Circle Drawing  Like DDA we can calculate & check gradient at

Algorithms once
o If |m| ≤ 1, increment x, calculate y

Basic Algorithms o If |m| > 1, increment y, calculate x

• For circles the gradient changes with each point
Midpoint
plotted and
Algorithms • Square root calculation
o Quite inefficient
Fill-Area Primitives
 33
Circle Drawing Algorithms
2. Plotting Points Using Polar Coordinates
Point Drawing in
 We express a position in the coordinate system as
OpenGL
an angle θ and a distance r
Line Drawing  r will be constant and only changing θ
Algorithms Compute x and y

Circle Drawing x  x c  r cos  y  y c  r sin 

Algorithms
• By increasing the size of the steps in the value of θ and
• Joining the computed points by straight-line segments
Basic Algorithms

 More efficient than

Midpoint
Algorithms
Cartesian one
 Even more efficient
Fill-Area Primitives with a little cost in
quality
 34
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

 We can generate the point reflected in the y-

Midpoint
Algorithms
axis by negating x-coordinate.
 We can generate the point reflected in the x-
Fill-Area Primitives axis by negating y-coordinate.
 35
Circle Drawing Algorithms
 For each point computed
Point Drawing in o Generates extra 7 points by re-
OpenGL arrangment
Line Drawing o Than computing each point separately.
Algorithms
 Need only compition for one octant of the
Circle Drawing circle
Algorithms

 Still have square root operations and

Basic Algorithms
trigonometric calculations

Midpoint
Algorithms o A need of another int based algorithm

Fill-Area Primitives
 36
Midpoint Algorithm
 Given the center and r
Point Drawing in  Plot the start-point of the
OpenGL circle (x0,y0) = (xc,r)
 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  2xk 1  1
Otherwise:
Midpoint Plot (xk+1,yk-1)
Algorithms
pk1  pk  2xk1 1 2yk1
Fill-Area Primitives
 37
Midpoint Algorithm Example
 Given the center (0,0) and 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 P = -9
Algorithms

Basic Algorithms

Midpoint
Algorithms

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

Circle Drawing p0 = -9
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives
(0,0)
 39
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)
 40
Midpoint Algorithm Example
p2 < 0,
Plot (x3,y3) = (x2+1,y2) = (3,10)
Point Drawing in
OpenGL p3  p2  2x3  1  1  7  6
Line Drawing
Algorithms (10,10)

Circle Drawing p2 = -1
Algorithms

Basic Algorithms

Midpoint
Algorithms

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

Circle Drawing p3 = 6
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives
(0,0)
 42
Midpoint Algorithm Example
p4 < 0,
Plot (x5,y5) = (x4+1,y4) = (5,9)
Point Drawing in
OpenGL p 5  p 4  2 x 5  1  3  11  8
Line Drawing
Algorithms (10,10)

Circle Drawing p4 = -3
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives
(0,0)
 43
Midpoint Algorithm Example
p5 ≥ 0,
Plot (x6,y6) = (x5+1,y5-1) = (6,8)
Point Drawing in
OpenGL p6  p5 2x6 12y6 83 5
Line Drawing
Algorithms (10,10)

Circle Drawing p5 = 8
Algorithms

Basic Algorithms

Midpoint
Algorithms

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

Circle Drawing p6 = 5
Algorithms

Basic Algorithms

Midpoint
Algorithms

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

Circle Drawing p7 = 6
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives
(0,0)
 46
Midpoint Algorithm Example
p8 ≥ 0,
Plot (x9,y9) = (x8+1,y8-1) = (9,5)
Point Drawing in
OpenGL

Line Drawing
Algorithms (10,10)

Circle Drawing p8 = 11
Algorithms

Basic Algorithms

Midpoint
Algorithms

Fill-Area Primitives
(0,0)
Any Question?

47