TEXT BOOK

2
What is Computer Graphics??

- term computer graphics was coined in 1960 by William Fetter

“Perhaps the best way to define computer graphics is to find

out what it is not. It is not a machine. It is not a computer, nor a
group of computer programs. It is not the know-how of a
graphic designer, a programmer, a writer, a motion picture
CHAPTERspecialist,
1- PURPOSE OF COMPUTER
or a reproduction GRAPHICS
specialist.

Computer graphics is all these – a consciously managed and

documented technology directed toward communicating
information accurately and descriptively.”
Computer Graphics, by William A. Fetter, 1966

6
 COMPUTER GRAPHICS ? Contd..
A field related to the generation of graphics using
computer
Includes the creation ,storage and manipulation of
images of objects
Objects Entertainment and Advertisement, Medicine,
Physical, Mathematical, Engineering, Architecture
Computer graphics- generating 2D images of a 3D
world represented in a computer

7
 MAIN TASKS
Imaging : formation of an image
: representation of 2D images

Modeling: representing 3D images

- creating and representing the geometry of
objects in the 3D world

Rendering : constructing 2d images from 3D models

- generating 2D images of the objects

Animation : simulating changes over time

- describing how objects change in time

8
 BASIC CONCEPTS
RASTER : A rectangular array of points or dots.
PIXEL (picture element) :One dot or picture element of the raster
SCAN LINE : A row of pixels
BITMAP :ones and zeros representation of the rectangular array
points on screen
Black and white  bitmap
pixmap color (colored raster image)

n–1
Scan Line
We don’t have any pixel
like (1.2, 5.8). In raster
device co-ordinates can
take integer values
Pixel only.
0
0 m–1
m X n Raster
 DEVELOPMENT OF COMPUTER GRAPHICS
1951- whirlwind computer developed in MIT had computer driven
CRT displays for output
Mid 1950’s- SAGE air defense system uses commands and control
CRT on which operator targets with light pens. Light pens sense
light emitted by objects on the screen.
1962- sketchpad, by Ivan Sutherland
Keyboard and light pen were used for drawing and making
choices
Modern interactive graphics
1964- CAD and CAM-shows graphical interaction and
graphical activities
General Motor DAC, Itek, Digitek for Lens Design
1968- Evans and Sutherland
Commercial company- flight simulators
High cost of graphics hardware

10
DEVELOPMENT OF COMPUTER GRAPHICS contd..

1971-Gouraud Shading- rendering method and is faster then

phong shading

1974-1977 : Phong Shading

Computer graphics at NYIT –Computer animation raster
graphics

1982- Ray Tracing ( illumination based rendering method)

1993-Open GL- Open Graphics Library

1995- Microsoft, game playing API

11
 APPLICATIONS OF COMPUTER GRAPHICS
Entertainment
Films-Jurasic Park
Video games, Formula 1 etc
Computer-aided design
Design components and system of mechanical,
Medical Image
electrical, electronics, buildings, automobile etc
aeroplane
Scientific Visualization and Business Visualization
Scientific visualization-generating computer graphics for
scientific, engineering ,medical data
E.g. airflow inside a thunderstorm
Visible human
Business visualization- non scientific data
obtained in economics
AutoCAD 2002
12
APPLICATIONS OF COMPUTER GRAPHICS contd…
Training
Driving Simulation
Flight Simulation
Desk Assembly
Education
Human skeleton
3D MAX Flight Simulator
E-commerce
Virtual phone store
Interactive kitchen planner
charts

The Visible Human Project

Computer Art
maps
Office automation and Electronics Publishing
Desktop publishing

13
CHAPTER 2- HARDWARE CONCEPTS
Basic Graphics System
 VIDEO DISPLAY DEVICE
• capable of performing a high-speed switching process and preventing
of video flicker form occurring.

• comprises a plurality of display unit including numbers of unit cells.

• unit cell comprises of numerous dots arrange vertically and

horizontally in orderly manner.

• Each dot is comprised of numerous display elements.

TERMINOLOGIES
1.Florescence/ phosphorescence
2.Persistence
3.Refresh Rate
4.Horizontal Scan Rate
5.Resolution
6.Aspect Ratio
FLUORESCENCE / PHOSPHORESCENCE
When the beam of electrons emitted by electron gun is strikes phosphor-coated screen of the
CRT and then phosphor emits a small spot of light at each position contacted by the electron
beam, such phenomenon is known as Fluorescence / Phosphorescence which last just a
fraction of microseconds.
PERSISTENCE
-defined as the time from the removal of excitation to the moment when phosphorescence
has decayed to 10 percent of the initial light output .
-The phosphor used for graphics display device usually have persistence of 10 to 60
microseconds.
RESOLUTION
Resolution is defined as the maximum member of points that can be displayed horizontally
and vertically without overlap on a display device.
ASPECT RATIO
Aspect Ratio gives that ratio of vertical point to horizontal points necessary to produce equal
length lines in both directions on the screen an aspect ratio of 3/4 means that a vertical line
plotted with 3 points has the same length as a horizontal line plotted with 4 points.
HORIZONTAL SCAN RATE
The horizontal Scan Rate is the number of scan lines per seconds.
The rate is approximately the product of the refresh rate and number of scan lines.
 REFRESH RATE
The number of times the screen is redrawn each second.
Higher refresh rates mean less flicker on the screen, which translates into less
eyestrain.
As refresh rate decreases , flicker develops because eye can no longer
integrate the individual light impulses coming from pixel.
The refresh rate above which a picture stops flickering and fuses into a steady
image is called the critical fusion frequency.

FACTORS AFFECTING CRITICAL FUSION FREQUENCY

The longer the persistence, the lower the CFF.
Increasing the image intensity increases the CFF
Decreasing the room light increases the CFF
Wavelengths of emitted light
Observer

6
 Video display device types

(i) Cathode Ray tube Display (CRT)

(ii) Liquid Crystal Display (LCD)
(iii) Raster Scan Display
(iv) Random Scan Display (Vector Scan Display)
REFRESH CATHODE-RAY TUBES

8 8
 Refresh Cathode-Ray Tube

o Focusing system
o Electrostatic focusing
o Positively charged metal cylinder
o Deflection of electron beam
o Persistence
o How long phosphors continue to emit light
o Low persistence is useful for animation
o Resolution
o Number of points per centimeter can be
plotted horizontally and vertically
 Refresh Cathode-Ray Tube

o Intensity distribution of a phosphor spot

o Adjacent spots appear distinct: 60%
o Spot size also depends on intensity
o Deflection of electron beam
o Resolution of a CRT depends
o Type of phosphor
o Intensity to be displayed
o Focusing and deflection system
o Aspect ratio
o The ratio of vertical points to horizontal points
necessary to produce equal-length lines
 Raster-Scan Display

The electron beam is swept

across the screen, one row at a
time from top to bottom
 Raster-Scan Display

o Frame buffer (refresh buffer)

Picture definition is stored in the memory area
o Pixel Picture each screen point is referred as pixel or pel
o Scan line
o Pixmap (bitmap) Picture for black-and-white system with
one bit per pixel, the frame buffer is called a bitmap. For
systems with multiple bits per pixel the frame buffer is called a
pixmap
o Refreshing (60 - 80 frames/sec)
o Horizontal retrace
o Vertical retrace
o Interlacing each frame is displayed in two pass
o Scan conversion
Interlaced refresh
 Random-Scan Display

A CRT has the electron beam

directed only to the parts of the
screen where the picture is to be
drawn
draw a picture one line.
 Random-Scan Display

o Random-scan (vector, stroke-writing, calligraphic)

displays
o Draw a picture one line at a time
o Refresh rate
o Depends on the number of lines to be displayed
o Picture definition
o A set of line-drawing commands
o Refresh display file
o Designed for line drawing applications
o Can not display realistic shaded scenes
 Color CRT Monitors

o Beam-penetration method
o Used with random-scan monitors
o Two layers of phosphor: red and green
o The displayed color depends on how far the electron beam
penetrates into the phosphor layers.
o Only four colors are possible: red, green, orange, and yellow.

ADVANTAGE:
• Economical way to produce colors

LIMITATIONS:
• Generation of only four colors is possible
• Poor picture quality
 Color CRT Monitors

o Shadow-mask method
o Three phosphor color dots at each pixel position
o Three electron guns
o Color variations: Varying the intensity levels of the three
electron beams
o Full-color (true-color) system: 24 bits of storage per pixel
 Direct-View Storage Tubes

o Store the picture information inside the CRT

o A charge distribution just behind the phosphor-coated
screen
o Two electron guns: primary gun and flood gun
o Advantage
o Very complex pictures can be displayed at very high
resolutions
o Disadvantages
o Do not display color
o Selected parts of a picture cannot be erased
 Flat-Panel Displays

o Video devices have reduced

o volume,
o weight, and
o power requirements
o compared to a CRT.
o A significant feature - thinner than CRT
o Classified into two categories:
o Emissive displays
o Nonemissive displays
 LIQUID CRYSTAL DISPLAY (LCD)
Commonly found on laptops
Advantage
 Desktop versions exist - Physical Size
 Fluorescent lights provide illumination - Display size
- Power Consumption
- Radiation Emission
TYPES
Passive matrix LCD
Pixels arranged in a grid
Disadvantage
- Viewing angle
Pixels are activated indirectly
- price
– Row and column are activated
Animation can be blurry

Active matrix LCD

Each pixel is activated directly
Pixels have 4 transistors
One each for red, green, blue
One for opaqueness
Transistors arranged in a thin film
Animation is crisp and clean
Raster-Scan Systems
Raster-Scan Systems
 Frame Buffer
The information in the buffer typically
consists of color values for every pixel .
A frame buffer may be thought of as computer
memory organized as a two dimensional array .
with each (x , y) addressable location corresponding to one pixel.
Bit planes or bit depth is the number of bit corresponding to
each pixel.
 Video Controller

o Coordinate system
o Frame-buffer locations are referenced in
Cartesian coordinates.
o Coordinate origin
o Lower left screen corner
o Upper left screen corner
o Refresh operations of video controller
o Top-to-bottom, left-to right
o x register ( initial value = 0)
o y register (initial value = ymax)
Video Controller

Basic video controller refresh operations

 Raster-Scan Display Processor

o Display processor (graphics controller, display

coprocessor)
o To free the CPU from the graphics chores
o Digitize a picture definition into a set of pixel-
intensity values
o Scan conversion: digitization process
o Straight-line segments
o Curved lines and polygon outlines
o Characters
 Raster-Scan Display Processor

Display Processor Frame Video Monitor

Memory buffer Controller

Display System
CPU Memory
Processor

System Bus

I/O Devices
 Raster-Scan Display Processor

o Display processor functions

o Generating various line styles
o Displaying color areas
o Performing certain transformations
o Manipulations on display objects
o Run-length encoding
o Reduce memory requirements
o Organizing the frame buffer as a linked list
o Store a scan line as a set of integer pairs
o An intensity value
o The number of adjacent pixels with the same intensity
 Random-Scan Systems
Graphics commands are translated into a display file stored
in the system memory

System Display Monitor

CPU
Memory Processor

System Bus

I/O Devices
Advanced 3D Graphics Architecture

Object Geometric
Geometric
Object Transformation
Database
Database Transformation
Engine
Engine

Clipping
Clipping
perspective
perspective
scaling
scaling
Video
Video
Controler
Controler
Lighting
Lighting
Model
Model
Calculator
Calculator

Shading
Shading Frame
Rasterizer
Rasterizer buffer
 INPUT DEVICES
- piece of hardware used to enter and manipulate information on a computer

KEYBOARD MOUSE
 TABLET

1.No keyboard, no mouse. Instead, you have an LCD screen and a stylus.

2.You don't need to convert handwriting to text

Tablets are gaining popularity as a replacement for the computer mouse as a pointing device
 TOUCH PANELS
Allow displayed objects or screen positions i.e. graphical icons to be selected
with the touch of a finger.

The key goals are to recognize one or more fingers touching a display, to
interpret the command that this represents, and to communicate the command to
the appropriate application.

When a user touches the surface, the system records the change in the electrical
current that flows through the display

Optical touch panel – employ LED’s along

horizontal and vertical edge of the frame, the
interruption in the beam is recorded by the
detectors
Electrical touch panel – the voltage drop across
the resistive plate to the conductive plate gives
coordinate value
Acoustical touch panel – sound waves generated
across the glass if gets reflected by the touch of
finger position and time is detected
LIGHT PEN JOYSTICK
a computer input device in the form of a light- consists of a stick that pivots on a
sensitive wand used in conjunction with a computer's base and reports its angle or
CRT TV set or monitor direction to the device it is
controlling
works by sensing the sudden small change in
brightness of a point on the screen when the electron
gun refreshes that spot

Light pens have the advantage of 'drawing' directly

onto the screen, but this can become uncomfortable,
and they are not as accurate as digitizing tablets
CHAPTER 3-
3- TWO
TWO-- DIMENSIONAL ALGORITHMS

2
 Points and Lines
Points
Plotted by converting co-ordinate position to appropriate
operations for the output device (e.g.: in CRT monitor, the
electron beam is turned on to illuminate the screen phosphor at
the selected location.)
Line
Plotted by calculating intermediate positions along the line
path between two specified endpoint positions.
Screen locations are referenced with integer values, so
plotted positions may only approximate actual line
positions between two specified endpoints  “the
jaggies”. E.g.: position (10.48,20.51)  (10,21).

3
 Pixel Position

Pixel position: referenced by scan line number and

column number

4
 LINE DRAWING ALGORITHM
DDA Algorithm- (Digital Differential Analyzer)
Bresenham’s Line Algorithm
Note:
Pixel- picture element smallest piece of information in an
image represented using dots, squares and rectangle
Components-
RGB
or
4 components
Y Scan Line
(cyan ,magenta,
yellow & black)

Pixel
0
0
Column number X

5
RASTER and RANDOM SCAN
Raster Scan Random or vector Scan
Electron beam Electron beam
swept across the directed only to
screen ,one row at a parts of the screen
time from top to where a picture is
bottom. e.g. drawn. e.g. pen
television plotter

6
 Straight Line Equation

Slope-Intercept Equation

y m. x 
b
Slope
y2 y1 rise
m 
x2 x1 run
Intercept

b y1 m.x1

Interval Calculation
y
y m.x x 
m
7
Digital System

Sample a line at discrete positions and determine

nearest pixel to the line at each sampled position

8
 DDA Algorithm
 Digital Differential Analyzer
Scan-conversion line – algorithm based on calculating either

Sample the line at unit intervals in one coordinate

Determine the corresponding integer values nearest the line
path in another co-ordinate

9
 CASES
Cases 1 positive slope
LEFT END TO RIGHT END POINT
a. m ≤1  sampling in x-direction

b.m>1 Sampling in y- direction (Reverse the role of x and y)

10
 RIGHT END TO LEFT END POINT
a. m ≤1  sampling in x-direction

b. m>1 Sampling in y- direction

11
 Case
Case 2 Negative slope
LEFT END TO RIGHT END POINT
a. |m| ≤1  sampling in x-direction

b.|m|>1 Sampling in y- direction (Reverse the role of x and y)

12
 Case 2

RIGHT END TO LEFT END POINT

a. |m |≤1  sampling in x-direction

b. |m|>1 Sampling in y- direction

13
 DDA ALGORITHM
1. Input points (x1 ,y1) and (x2,y2)
2. Compute dx = x2- x1 & dy= y2 - y1
3. If |dx|>|dy| then steps=|dx|
otherwise steps =|dy|
4. xinc = dx/ steps
yinc = dy/ steps

5. x= x1 , y= y1 , k=0
6. do:

 plot(round (x), round (y));

 x=x+ xinc y=y+ xinc
 K ++
while ( k<=steps)
14
 Code
Void lineDDA(int xa, int ya, int xb, int yb)
{
int dx = xb – xa, dy = yb – ya, steps, k;
float xIncrement, yIncrement, x = xa, y = ya;

if( abs (dx) > abs (dy) ) steps = abs (dx);

else steps = abs (dy);
xIncrement = dx / (float) steps;
yIncrement = dy / (float) steps;
setPixel (ROUND (x), ROUND (y));
for (k=0; k<steps; k++){
x += xIncrement;
y += yIncrement;
setPixel (ROUND(x), ROUND(y));
}
}

15
DDA
DDA PROBLEMS & IMPROVEMENT
PROBLEMS
Accumulations of round off error in successive
additions of the floating point increment– this
causes the calculated pixel drift away from the
true line path for long line segments
ALIASING EFFECT
Rounding operations and floating-point
arithmetic operations are still time consuming

IMPROVEMENT
Can be removed by making increments m and
1/m into integer and fractional parts so that all
calculations are reduced to integer operations

16
 Bresenham’s Line Algorithm
Another incremental scan conversion algorithm
Uses only incremental integer calculations
Accurate and efficient line generating
algorithm
IDEA : move across the x-axis in unit
intervals and at each step choose
between two y coordinates
E.g.
Which pixel to draw ?
(11,11) or (11,12) ?
(51,50) or (51,49) ?
Solution choice is that which is
closer to the original line
17
 Bresenham’s Line Algorithm contd…
For |m|<1
i.e.

Start from left end point (x0,y0) step to each

successive column (x samples) and plot the pixel
whose scan line y value is closest to the line path.

After (xk, yk) the choice could be (xk+1,yk ) or

(xk+1,yk+1)

18
 Bresenham’s Line Algorithm contd…
y- coordinate on the mathematical line at
is
y m ( xk 1) b
Then
d1 y yk
m( xk 1) b yk
And
d 2 ( yk 1) y
yk 1 m( xk 1) b
Difference between separations

d1 d 2 2m( xk 1) 2 yk 2b 1

19
 Bresenham’s Line Algorithm contd…
Defining decision parameter Constant=2Δy + Δx(2b-1) Which
is independent of pixel position
p k x(d 1 d 2 )
2y. xk 2x. yk c m = Δy/Δx
Sign of pk is same as that of d1-d2 for Δx>0 (left to right sampling)

p k 1 2y.xk 1 2x. yk 1 c c eliminated here

pk 1 pk 2 y ( xk 1 xk ) 2x( yk 1 yk )

because xk+1 = xk + 1
p k 1 p k 2y 2 x ( yk 1 y k )
yk+1-yk = 0 if pk < 0
For Recursive calculation, initially yk+1-yk = 1 if pk ≥0

p0 2y x Substitute b = y0 – m.x0

and m = Δy/Δx in [1]
20
 ALGORITHM
1. Input two points (x1,y1) and (x2,y2)
2. Compute Δx = | x2 - x1 | & Δy= |y2- y1 |
3. If (x2 > x1 ) lx=1 else lx= - 1
4. If (y2 > y1) ly=1 else ly= - 1
5. Plot first point (x1,y 1)
6. If (Δx > Δy) { /* i.e. when |m|<1 */
 calculate p0 = 2Δy – Δx
 Starting at k =0 to Δx times , repeat
If p k<0 /* next point (x k+1,yk) */
xk+1 = xk+lx , yk+1= yk
Pk+1 = pk + 2Δy
else /* next point (xk + 1, yk+1) */
xk+1 = xk+lx , yk+1 = yk +ly
Pk+1 = pk + 2Δy - 2Δx
}ENDIF 21
 ALGORITHM contd…
7. Else /* i.e. when |m|>1 */
{
 calculate p0 = 2Δx – Δy
 Starting at k =0 to Δy times , repeat

If p k<0 /* next point (x k,yk+1) */

xk+1 = xk
yk+1 = yk+ly
Pk+1 = pk + 2Δx

else /* next point (xk + 1, yk+1) */

xk+1 = xk+lx
yk+1 = y k +ly
Pk+1 = pk + 2Δx – 2Δy
}
22
 Example
Digitize the line with endpoints (20,10) and (30,18)
Slope m = 0.8 Δx = 10, Δy = 8
P0 = 2Δy - Δx = 6
2Δy = 16, 2Δy-2Δx = -4
Plot (x0,y 0) = (20,10)
Plot ?

k pk (xk+1,yk+1) k pk (xk+1,yk+1)

0 6 (21,11) 5 6 (26,15)
1 2 (22,12) 6 2 (27,16)
2 -2 (23,12) 7 -2 (28,16)
3 14 (24,13) 8 14 (29,17)
4 10 (25,14) 9 10 (30,18) 23
 Circle

Circle Equation:

( x xc ) ( y yc ) r
2 2 2

Points along circumference could be

calculated by stepping along x-axis:

y yc  r 2 ( xc x) 2

24
 Example

E.g. x c = y c =0 and r Problem ????

1. Computational complexity
y  r x 2 2
Square root and multiply
operation
r=20
2. Non-uniform spacing:
When x=0 then y=20
 Large gaps occurs when the
x=1 then y ≈20 slope approaches vertical
x=2 then y ≈20

x=19 then y ≈6
x=20 then y =0
25
 Adjustments (To fix problems)
1. Spacing problem (2 ways):
Interchange the role of x and y whenever the absolute value of the
slope of the circle tangent > 1
Use polar co-ordinate: x xc r cos 
y yc r sin 
Equally spaced points are plotted along the circumference with fixed
angular step size.

step size chosen for θdepends on the application and display device.
For more continuous boundary on a raster display, set step
size at 1/r; i.e. pixel positions are approximately 1 unit apart.

2. Computation Problem:
Use symmetry of circle; i.e. calculate for one octant and use
symmetry for others.

26
Eight way Symmetry of circle

27
 Mid--Point Circle Algorithm
Mid

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
The mid-point circle
symmetry to get the rest of the points algorithm was
developed by Jack
Bresenham, who we
heard about earlier.
 Mid--Point Circle Algorithm (cont…)
Mid

Assume that we have

just plotted point (xk, yk)
The next point is a
choice between (xk+1, yk)
and (xk+1, yk-1)
We would like to choose
the point that is nearest to
the actual circle
So how do we make this choice?
30
31
32
 Midpoint Circle Algorithm

Circle function defined as:

f circle ( x, y) x y r
2 2 2

Any point (x , y) satisfies following conditions

0 , if ( x , y ) is inside the circle boundary


f circle ( x , y )0 , if ( x , y ) is on the circle boundary
0 ,
 if ( x , y ) is outside the circle boundary

By evaluating this function at the midpoint between

the candidate pixels we can make our decision
33
 Midpoint Circle Algorithm contd….

Decision parameter is the circle function;

evaluated as:
1
p k  f circle ( x k 1, y k  )
2
1
( x k 1) 2 ( y k  ) 2 r 2
2

1 ---- 2
pk 1 f circle ( xk 1 1, y k 1  )
2
1
[( xk 1) 1]2 ( y k 1  )2 r 2
2
pk 1 pk 2 ( xk 1) ( y k 1 y k ) ( y k 1 y k ) 1
2 2

34
 Midpoint Circle Algorithm contd….

if pk < 0
yk+1 = y k
Pk+1 = Pk + 2xk+1+1

if pk > 0

yk+1 = yk-1
Pk+1 = Pk + 2xk+1+1-2yk+1
Note:
Incremental evaluation of 2xk+1 and 2yk+1
2xk+1 = 2xk + 2
2yk+1 = 2yk – 2 if pk >0
At start position (x0,y0) = (0,r)
2x0 = 0 and 2y0 = 2r
35
 Midpoint Circle Algorithm contd….

Initial decision parameter

1
p 0  f circle (1 , r  )
1 22 2
1 ( r  ) r
5 2
 r
4
For r specified as an integer, round p0 to
P0 = 1-r
(because all increments are integers)

36
 Algorithm
1. Input radius r and circle center (xc , yc ) and obtain the first point on the
circumference of a circle centered on the origin as
(x0,y 0) = (0,r)
2. Calculate the initial value of the decision parameter as
P0 = 5/4 – r
3. At each xk position, starting at k = 0, perform the following test:
If pk < 0 /* next point (x k+1,yK)*/
xk+1 = xk + 1
yk+1 = yk
Pk+1 = pk + 2x k+1 + 1

else /*next point (xk+1,yK -1) */

xk+1 = xk + 1
yk+1 = yk - 1
Pk+1 = pk + 2xk+1 + 1 -2yk+1
Where 2xk+1 = 2x k + 2 and 2 yk+1 = 2yk-2
4. Determine the symmetry points in the other seven octants.
5. Move each calculated pixel position (x,y) onto the circular path
centered on (x c,yc) and plot the co-ordinate values:
x = x + xc, y = y+yc
6. Repeat steps 3 through 5 until x ≥y

37
Numerical
Numerical
Complete Plot

40
 Example
Digitize the circle with r=10 and center located at origin
Initial point (x0,y0)=(0,10) 2x0 =0 2y0 =20
P0 = 1- r = 1-10 = -9

k pk (xk+1,yk+1) 2xk+1 2yk+1

0 -9 (1,10) 2 20
1 -6 (2,10) 4 20
2 -1 (3,10) 6 20
3 6 (4,9) 8 18
4 -3 (5,9) 10 18
5 8 (6,8) 12 16
6 5 (7,7) 14 14 41
 Ellipse

Elongated circle
Equation of ellipse:
d 1 d 2 constant
F1(x1 ,y1), F2(x2 ,y2)
( x x1 ) 2 ( y y1 )2  ( x x 2 ) 2 ( y y 2 ) 2 constant
General Equation
Ax 2 By 2 Cxy Dx Ey F 0
In terms of ellipse center coordinates
2
x xc  y yc 
2

  
r   r  1
 x   y 
In polar co-ordinate
x x c rx cos 
y y c r y sin 
42
 Mid Point Ellipse Algorithm

Ellipse function

f ellipse ( x , y ) r y x r x y r x r y
2 2 2 2 2 2

0,

 if ( x, y ) is inside the ellipse boundary
0,
fellipse ( x, y )  if ( x, y) is on the ellipse boundary

0,
 if ( x, y) is outside the ellipse boundary

43
 Mid Point Ellipse Algorithm contd…

From ellipse tangent slope:

2
dy 2r x
 y2
dx 2 rx y
At boundary region (dy/dx= -1)

2ry 2 x 2rx 2 y
Start from (0,ry), take x samples to
boundary between 1 and 2
Switch to sample y from boundary
between 1 and 2
(i.e whenever 2 r y x 2 r x y )
2 2

44
 Mid Point Ellipse Algorithm contd…

•For increment
In the region 1 calculation; Initially:
1
p1k f ellipse ( xk 1, y k  )
2 2r x 0
2
y
1
ry ( xk 1)2 rx ( yk  ) 2 rx ry
2r y 2r r
2 2 2 2
2 2
2 x x y
For next sample •Incrementally:
1
p1k 1 f ellipse ( xk 1 1, yk 1  ) Update x by adding
2 2ry2 to first equation
ry  ( xk 1) 1rx2 ( yk 1  ) 2 rx ry
2 2 1 2 2
and update y by
2

2  1   1 
2 2 subtracting 2rx 2 to
p1k 1 p1k 2ry ( xk 1) ry rx 
2 2
yk 1  yk   second equation

 2   2  
Thus increment

2 ry xk 1 ry2 ,
2
if p1k 0
increment  2
2
 ry xk 
1 ry
2
 2 rx
2
yk 1 , if p1k 0
45
 Mid Point Ellipse Algorithm contd…

Initial value

 1
p10 f ellipse 1, ry  
 2
2
 1 
ry2 rx2 ry  rx2 ry2
 2
1 2
p10 ry rx ry  rx
2 2

46
 Mid Point Ellipse Algorithm contd…

In the region 2
1
p2 k f ellipse ( xk  , yk 1)
2
1
ry ( xk  ) 2 rx ( yk 1) 2 rx ry
2 2 2 2

For next sample

p2 f 1 , y
(x 1)
k 1 k 1 2 k 1
ellipse
 2 2 For simplification calculation
2 1 2  
r y 
x
 k1  


r x

 y k 11  r x 2 r y 2 of p20 can be done by
 2  
  

selecting pixel positions in
 1 2  12

p2 p 2 2 r ( y 1) r r 
2 2 2 
x  

x   
counter clockwise order
k 1 k x k x y 

k 1 2 



 k


2

 starting at (rx,0) and unit

 

Initially samples to positive y direction
until the boundary between
 1 
p 2 0 f ellipse x0  , y0 1  two regions
 22 
 1
p 2 0 ry2 x0  rx2 ( y0 1) 2 rx2 ry2
 2
47
 Algorithm
1. Input rx,ry, and the ellipse center (xc, yc) and obtain the first point on an ellipse
centered on the origin as
(x0,y0) = (0,ry)
2. Calculate the initial value of the decision parameter in region 1 as
1
p 1 0 r y2 rx2 r y  r x2
4
3. At each x k position in region 1, starting at k = 0, perform the following test:
If p1k < 0 /* next point (xk+1,yk)
xk+1 = xk+1, yk+1 = y k
p1k 1  p1k 2 r y2 x k 1 r y2

Else /* next point (xk+1,yk -1) */

xk+1 = xk+1, yk+1 = yk -1

p1k 1 p1k 2ry2 xk 1 2rx2 y k 1 ry2

With
2ry2 x k 1 2ry2 xk 2ry2 , 2rx2 y k 1 2rx2 y k 2rx2
and continue until 2ry2 x 2rx2 y
48
 Algorithm contd…
4. Calculate the initial value of decision parameter in region 2 using the last point (x0,y0)
calculated in region 1 as 2
 1
p 20 ry2 x 0  rx2 (y0 1)2 rx2 ry2
 2
5. At each yk position in region 2, starting at k = 0, perform the following test:

If p2k≤0 /* next point (xk+1,yk-1 )*/

xk+1 = xk+1
yk+1 = yk-1
p2 p 2 2 r 2 x 2 r 2 y r 2
k 1 k y k 1 x k 1 x

Else /*next point (xk,yk-1)*/

xk+1 = xk
yk+1 = yk-1
2 2
p 2 p 2 2 r y r
k 1 k x k 1 x

4. Using the same incremental calculations for x and y as in region 1.

continue until y=0.
6. Determine the symmetry points in the other three quadrants.
7. Move each calculated pixel position (x,y) onto the elliptical path centered on (xc,yc)
and plot the co-ordinate values:
x = x + xc, y = y+ yc 49
Numerical
Numerical
 Numerical
rx= 8 ry=6 and center ( 0,0)
Numerical Contd…
TWO-- DIMENSIONAL GEOMETRIC TRANSFORMATION
TWO

54
 TRANSFORMATION

process of changing orientation, shape or size

Translation
Rotation
Scaling
Reflection
shearing

55
 HOMOGENOUS FORM

 Expressing position in homogeneous coordinates

allows us to represent all geometric transformations
equation as matrix multiplications.

( x, y) -------------------- (xh, yh,h)

x= xh /h y= yh /h
where h is any non zero value
For convenient h=1
(x,y)-------------------------(x, y, 1).

56
 TRANSLATION
Every point on the object is
translated by the same amount Translation
x' x tx, y' y ty vector


x1  
x1'  
tx 
P  , p' ' , T  
1 
y 
y1 
  ty 


P' P T
In homogeneous representation if
position P = (x, y) is translated to new
position P’= (x’, y’) then:

x'  
 1 0 tx  x
y'
 0 1 t .y  P' T (tx , ty ).P
  y 
1
 0 0 1 
1

57
 ROTATION

Two- dimensional rotation is applied to an object by

repositioning it along a circular path in xy plane
REQUIREMENT:
Rotation angle θ
&
pivot point

Clockwise rotation
(Negative)

Anticlockwise rotation
( positive )
58
 ROTATION contd…
Coordinates of point ( x,y ) in polar form
x r cos , y r sin 
x' r cos() r cos. cosr sin.sin
y' r sin() r cos.sinr sin.cos
x' x cos y sin  If Co-ordinates represented as row vector, Then:
y' x sin y cos 
P 'T
( R .P ) T
P 'R.P  P T .R T

cos sin 

R  

sin  cos  In homogeneous co-ordinate

x '  cos  sin  0 x 

y ' sin  cos  0  . y  P ' R (). P
    
1  0 
 
1
 0 1
59
 ROTATION OF A POINT (X,Y) ABOUT ANY POINT (Xr
(Xr,, Yr)
x ' x r ( x x r ) cos ( y y r ) sin 
y ' y r ( x x r ) sin ( y y r ) cos 
Steps
1. Translate object so as to coincide pivot to origin
2. Rotate object about the origin
3. Translate object back so as to return pivot to original
position

Composite Transformations


1 0 x r  cos  sin  0  1 0 x r 

0 1 yr  . 
sin  cos  0 .0 1  y 
   r 


0 0 1  0 0 10 0 1  
cos  sin  x r (1 cos ) y r sin 


sin  cos  y r (1 cos ) x r sin 
 

0 0 1 


T ( x r , yr ). R().T (x r ,y r ) R( x r , y r , )

T (x r ,y r ) T 1 ( x r , y r )
60
 SCALING

- alters the size of an object

x ' x.s x , y ' y.s y

x '  s x 0 x 
  . 
y ' 0 s y y 

P'S.P
In homogeneous co-ordinate

x'  sx 0 0 x

y '0 sy 0.y  P ' S ( s x , s y ). P
     
1  0 1
 
1
 0
61
FIXED POINT SCALING

For a given fixed point (xf,yf)

1. Shift the scaling point to origin
2. Scale
3. Restore
62
 FIXED POINT SCALING contd…

x ' x f ( x x f ).s x ,
j
y ' y f ( y y f ).s y
x ' x. s x x f (1 s x )
y ' y .s y y f (1 s y )

Additive terms xf(1-sx) and yf(1-sy) are constant for

all points in the object

x'  
 sx 0  x x f (1 s x ) 
 . 

 
y ' 0 y f (1 s y ) 
s y y   

P ' S . P C 63
Fixed Point Scaling contd...
 GENERAL SCALING DIRECTIONS

Rotate the object so that x and y axes coincide with

s1 and s 2
Apply scaling transformation in s1 and s2 direction

Rotate the object in opposite direction to return

points to the original orientations

Example: square converted to parallelogram with

s1 =1 and s 2 = 2 and θ= 450 as shown in figure

R 1 ().S ( s1 , s2 ).R ()


s1 cos2 s 2 sin 2  ( s 2 s1 ) cos . sin  0
 
( s2 s1 ) cos . sin  s1 sin 2 s 2 cos 2  0

 0 0 1
 

65
 REFLECTION

A transformation that produces a mirror image of an

object.
Equivalent to rotation of an object about the
reflection axis.
Reflection about
x-axis (y=0)

x ' 
1 0 0 x 
y'0 1 0 .y 
   

1  
0 0 1
 1

66
 REFLECTION contd…
Reflection about y-axis (x=0)

x'  1 0 0x 
y '0 1 0 . y 
   

1  
0 0 1 
 1

67
 REFLECTION contd…

Reflection about y = x

x' 0 1 0x 
y '
1 0 0 . y 
   

1  
0 0 1
  1

Equivalent to:
Reflection about x-axis
Rotate anticlockwise 90˚
OR
Clockwise rotation 45 ˚
Reflection with x-axis
anticlockwise rotation 45 ˚ 68
 REFLECTION contd…

Reflection about y = - x

x' 0 1 0 x
y '1 0 0 . y 
   

1  
0 0 1 1

Equivalent to:
Clockwise rotation 45 ˚
Reflection with y-axis
anticlockwise rotation 45 ˚
69
REFLECTION ABOUT y=m*x+c

ASSIGNMENT 70
 REFLECTION ABOUT y=mx+c
y= mx+c
Combination of translate-rotate-reflect transformation
1. First translate the line so that it passes through the
origin

1 0 0 
0 1 c 
 

0 0 1  
translatio n

2. Rotate the line onto one of the coordinate axes(say x-

axis) and reflect about that
axis (x-axis)
cos  sin  0
sin  cos  0rotation
 

 0 0 1
 71
 REFLECTION ABOUT y=mx+c
y= mx+c contd…
1 0 0
0  1 0 
 

0 0 1 
reflection

3. Finally, restore the line to its

original position with the inverse rotation and
translation transformation.

cos  sin  0
sin  cos  0 
 

0 0 1
rotation
72
 REFLECTION ABOUT y=m*x+c contd…
1 0 0
0 1 c
 

0 0 1 
translatio n

Thus the composite transformation matrix for reflection

about y=m*x+c is

73
 REFLECTION ABOUT y=m*x+c contd…
Substituting value of tanθ, sinθ& cosθyou will get the
reflection matrix

1 m 2
2m  2 cm 
 2 
1 m 2
1 m 2
1 m 
 
 2m m 2 1 2c 
 2 
1 m 2
1 m 2
1 m 
 

 0 0 1 


74
 SHEARING
Transformation that distorts the shape of an object
Transformed object appears as if it were composed of
internal layers that had been caused to slide over each
other.
Shearing factor (Shx, Shy)

75
 SHEARING contd…

x- direction shear relative to x-axis

x’=x+y*Shx
y’=y x '  1 Shx 0 x 
y '  0 1 0 . y 
    

1   0 0 1 1

y- direction shear relative to y-axis

x’=x
y’=y +x *Shy
x '   1 0 0 x 
y '  Shy 1 0 . y 
    

1   0 0 1 1

76
 SHEARING contd…
x- direction shear relative to other reference line y= yref
x’=x +Shx(y-yref)
y’=y x '  1 Shx  Shx . y ref  x 
y '  0 1 0
 
   . y 

1   0 0 1 
 1 


y- direction shear relative to other reference line x=x ref

x’=x
y’=y+Shy(x-xref)
x '   1 0 0 x 
y '  Shy 1  Shy . . y 
   X ref
 

1   0 0 1 
 1 


77
 COMPOSITE TRANSFORMATIONS

Successive Translations are additive

For Successive Translation 

1 0 t x2  1 0 t x1 t x2 
1 0 t x1  
vectors (tx1,ty1) and (tx2,ty2) 
0 1 t .0 1 t 
0 1 t t 
 y 2  y1  y1 y 2 
P ' T ( t x 2 , t y 2 ).{T (t x1 , t y1 ). P} 
0 0 1
 0 0 1 
0 0 1  
{ T (t x 2 , t y 2 ).T ( t x1 , t y 1 )}. P T (t x2 , t y2 ).T (tx1 , t y1 ) T (t x1 t x2 , t y1 t y2 )

For Successive Rotations θ1

and θ2 Successive Rotations are additive.

P '  R ( 2 ).{ R ( 1 ). P } R (2 ). R ( 1 )  R ( 1 2 )

 { R ( 2 ). R ( 1 )}. P
!!!!!!! PROVE YOURSELF !!!!!!!!!

78
 COMPOSITE TRANSFORMATIONS

Successive Scaling are multiplicative Fixed Point Scaling


1 0 x f sx 0 0 1 0 x f  sx 0 x f (1 sx ) 
S ( sx 2 , s y2 ).S ( sx1 , s y1 ) S ( s x1. sx 2 , s y1 .s y 2 )     
0 1 yf . 0 sy 0 . 0 1 y f  0 sy y f (1 s y )
     


0 0 1 

0 0 1 
0 0 1 
 
0 0 1 

sx2 0 0 s x1 0 0  s x1 .sx 2 0 0
0 sy2 0.0 s y1 0 0 S y1 .s y 2 0
    

0 0 1
0 0 1  
0 0 1
 T ( x f , y f ).S (sx , s y ).T (x f ,y f ) S ( x f , y f , sx , sy )

Concatenation Properties

Matrix multiplication is associative, so

A.B.C = (A.B).C = A.(B.C)

Transformation product is not commutative, so
79
A.B ≠B.A
 TRANSFORMATION BETWEEN COORDINATE AXES
1. Translate so that the origin (x0, y0) of the x’y’ system is moved to
the origin of the xy system
2. Rotate the x’-axis onto the x-axis
1 0 x 0 

T( x0 , y 0 ) 
0
 1 y 0



0 0 1  

 cos θ sin θ 0 
R( θ) 

 sin θ cos θ 0 


 0 0 1

So , the composite matrix

 cosθ sinθ 01 0 x0 
T.R 

 sinθ cosθ 0 


0 1 y 
0


 0 0 1

0 0 1   80
2-D VIEWING

81
 2-D VIEWING
Window
- a world coordinate area selected for display
define what is to be viewed
View-port
An area on a display device to which a window is mapped
Define where it is to be displayed
Windows and view-port
Rectangle in standard positions, with rectangle edges
parallel to coordinate axes
Other geometric takes longer to proceed
Viewing transformation- the mapping of a world coordinate
scene to device coordinates
Transformation pipeline-
takes the object coordinates through several intermediate
coordinates systems before finishing with device
coordinates
82
 VIEWING TRANSFORMATION
Transformation from world to viewport

 For Fixed sized viewport, zooming in effect is attained if window size

is decreased and zooming out effect if window size is increased.
 Panning effect is attained by successively changing the position of
viewing window
The normalized device coordinates maps the world co-ordinate to
the viewport of maximum size = unit square as shown in figure. The
advantage is the mapping is display device independent 83
 2-D VIEWING TRANSFORMATION PIPELINE
Procedures for displaying views of a two-dimensional picture on an output
device:
Specify which parts of the object to display (clipping window, or world
window, or viewing window)
Where on the screen to display these parts (viewport).
Clipping window is the selected section of a scene that is displayed on a
display window.
Viewport is the window where the object is viewed on the output device.

84
VIEWING REFERENCE FRAME

Setting up viewing Reference Frame

The matrix is obtained in two steps:
1. Translate Viewing reference frame
origin to world origin
2. Rotate Viewing reference frame to
coincide with world coordinate axes

Thus we get the matrix as

Mwc,vc = R.T 85
 Windows To Viewport Co-
Co-ordinate Transformation
window to viewport coordinate transformation maintains the same relative
placement of objects in normalized space as in viewing cordinates

xv xvmin xw xwmin yv yv min ywywmin

 and yv  yw
xv maxxv min xwmaxxwmin max  yv min max ywmin
Solving we get,
xv  xv min ( xw  xw min ) sx
yv  yv min ( yw  yw min ) sy
where scaling factors
xv max  xv min
sx 
xw max  xw min
yv max  yv min
sy 
yw max  yw min
If sx = sy, the proportion is maintained
otherwise the scene is stretched 86
CLIPPING

87
 CLIPPING
Any procedure that identifies those portions of a picture that are either
inside or outside of a specified region of a space
A clip window can be polygon or curved boundaries
World- coordinate clipping removes the primitives outside the window
from further consideration; thus eliminating the processing necessary
to transform these primitives to device space.
Clipping type- point ,line, area, curve and text clipping

APPLICATIONS
Extracting part of a defined scene for viewing
Identifying visible surfaces in 3-dimensional views
Antialiasing line segments or object boundaries
Creating objects using solid modeling procedures
Displaying a multiwindow environment
Drawing and painting operations that allow parts of a picture to
be selected for copying, moving erasing or duplication.

88
 POINT CLIPPING

Assume clipping window is

Rectangle, point P=(x,y) is saved
ywmax
for display if following
inequalities are satisfied

xwmin x xwmax ywmin

ywmin y ywmax xwmin xwmax

(xwmin , xwmax ,ywmin ,ywmax) can be either world coordinate

window boundaries or viewport boundaries

If all the four inequalities are satisfied for a

point with co-ordinate (x,y), the point is
accepted; i.e not clipped 89
 LINE CLIPPING
“INSIDE – OUTSIDE” TESTS

What are the methods (algorithms) to perform clipping operations ?

90
 LINE CLIPPING

For a line segment with endpoints (x1,y1) and (x2,y2)

and one or both endpoints outside the clipping
rectangle, the parametric representation
x=x1 + u(x2- x1)
y=y1 + u(y2- y1) 0≤u ≤1

 If value of u for an intersection with a rectangle

boundary edge is outside the range 01, the line does
not enter the interior of the window at that boundary
 If value of u is within the range 01, the line segment
does indeed enter into the clipping area

91
 COHEN--SUTHERLAND LINE CLIPPING
COHEN
advantage of the algorithm is that it vastly reduces the number of
line intersections that must be calculated
World space is divided into regions based on the window
boundaries
Each region has a unique four bit region code
Region codes indicate the position of the regions with respect to
the window 4 3 2 1
Top Below Right Left TBRL
Region Code Legend

bit 4 : y  yw
1001 1000 1010
max
bit 3 : y  yw 0000
min 0001 0010
Window
bit 2 : x xw
max
bit 1 : x xw 0101 0100 0110
min
 Cohen--Sutherland line clipping
Cohen

Top
op--Left Top Top
op--Right

Left Inside Right

Bottom
ottom--Left Bottom Bottom
ottom-- Right

1001 1000 1010

TBRL
0000
0001 0010
Window

0101 0100 0110

 Cohen--Sutherland line clipping
Cohen
Region coding
How would you decide which region an endpoint is in?
e.g
if (x<xwmin) && (y>ymax)  the point is at the Top-Left

Are there cases we can trivially accept or reject?

How would you test for those?

 A1=0000,A2=0000
both (0000)  accept trivially

1001 B1  B1=1001,B2=1010
1000 1010
D1
both NOT (0000)
B2 AND Operation
C1 B1  1001
A2
0000 0010 B2  1010
0001 A1 Result 1000
C2
0110 Result = NOT (0000)  reject trivially
0101 0100
D2

94
 ALGORITHM
1. Assign a region code for each endpoints.
2. If both endpoints have a region code 0000 trivially
accept these line.
3. Else, perform the logical AND operation for both region
codes.
3.1 if the result is NOT 0000  trivially reject the line.
3.2 else (i.e. result = 0000, need clipping)
3.2.1. Choose an endpoint of the line that is outside the
window.

3.2.2. Find the intersection point at the window boundary

(based on region code).

3.2.3. Replace endpoint with the intersection point and

update the region code.

3.2.4. Repeat step 2 until we find a clipped line either trivially

accepted or trivially rejected.
4. Repeat step 1 for other lines.
95
 Cohen--Sutherland line clipping
Cohen
Intersection calculations:

Intersection with vertical boundary

y = y1 + m(x-x1)
Where
x = xwmin or xw max
Intersection with horizontal boundary
x = x1 + (y-y 1)/m
Where
y = ywmin or ywmax

96
 COHEN--SUTHERLAND LINE CLIPPING
COHEN contd…
Obtain the endpoints of line P1P 2 after cohen-sutherland
clipping

ASSIGNMENT
97
A COHEN--SUTHERLAND LINE CLIPPING Numerical
COHEN
1. P1=1001 P 2=0100
2. Both (0000)NO
3. And Operation
1001
0100
Result0000
3.1 not(0000)NO
3.2 0000 yes
3.2.1 choose P1
3.2.2 Intersection with LEFT boundary
m=(5-120)/(130-0)= -0.8846
y = y 1 + m(x-x1) where x=10
y=120-0.8846(10-0)=111.15≈111
P1’= (10, 111)
3.2.3 Update region code P1’= 1000 (TOP)
3.2.4 Repeat step 2.
98
B COHEN--SUTHERLAND LINE CLIPPING Numerical
COHEN
1. P1 ’=1000 P2 =0100
2. Both (0000)NO
And Operation
1000
0100
Result0000
3.1 not(0000)NO
3.2 0000 yes
3.2.1 choose P1’
3.2.2 Intersection with TOP boundary
m=(5-120)/(130-0)= -0.8846
x = x1 + (y-y 1)/m where y= 100
x=10+ (100-111)/(-0.8846)=22.44 ≈22
P1’’= (22, 100)
3.2.3 Update region code P1’’= 0000
3.2.4 Repeat step 2.
99
c COHEN--SUTHERLAND LINE CLIPPING Numerical
COHEN
1. P1”=0000 P2=0100
2. Both (0000)NO
And Operation
0000
0100
Result0000
3.1 not(0000)NO
3.2 0000 yes
3.2.1 choose P2
3.2.2 Intersection with BOTTOM boundary
m=(5-120)/(130-0)= -0.8846
x = x1 + (y-y1)/m where y= 10
x=130+ (10-5)/(-0.8846)=124.35 ≈124
P2’= (124, 10)
3.2.3 Update region code P2’= 0000
3.2.4 Repeat step 2.
100
D COHEN--SUTHERLAND LINE CLIPPING Numerical
COHEN

Both (0000)YES
ACCEPT & DRAW

Thus endpoints after clipping

P1 ’’= (22, 100)

P2 ’= (124, 10)

101
 Liang--Barsky Line Clipping
Liang
Based on parametric equation of a line:
x = x1 + u.
u.
x
y = y 1 + u.
u.y
Similarly,, the clipping window is represented by:
Similarly
xwmin x1 + u. x xwmax
u.
0 u 1
ywmin y1 + u. y ywmax
u.
… or, (x 1,y1)
u. p k qk k = 1, 2, 3, 4

where::
where
(x 2 ,y2 )

k = 1 ( is the line inside left boundary ?) p1 = - x , q1 = x1 – xwmin

k = 2 (is the line inside right boundary ?) p2 = x , q2 = xwmax- x1
k = 3 (is the line inside bottom boundary ?) p3 = - y , q3 = y1 – ywmin
k = 4 (is the line inside top boundary ?) p4 = y , q4 = yw max - y1

Pk<0  infinite extension of the line proceeds from outside to inside the infinitely
extended boundary
Pk>0  infinite extension of the line proceeds from inside to outside of the infinitely
102
extended boundary
 Liang--Barsky Line Clipping
Liang contd…
Trivial rejection :
Reject line with pk = 0 for some k and one qk < 0 for these k.

clipped line will be

x1’ = x1 + u1 .x u1 ≥0
y1’ = y1 + u1.y

x2’ = x1 + u2 .x u2 ≤1
y2’ = y1 + u2.y

Calculate

qk
uk 
pk

u1 --(For intersection with the boundaries to which line enters the boundary)
maximum value between 0 and u (for p k < 0), where starting value of u 1=0
u2 --(For intersection with the boundaries to which line leaves the boundary)
minimum value between u and 1 (for pk > 0), where starting value of u2 =1
103
COMPUTER GRAPHICS
EG678EX

Deel Mani Baral

[email protected]
Institute of Engineering
Pulchowk Campus

1
CHAPTER 6- THREE DIMENSIONAL TRANSFORMATIONS

2
 “The art of 3D graphics is the art of fooling the

brain into thinking

that it sees a 3D object painted on a flat screen.”

 3D Translation
Translation of a Point

x' x t , y ' y t , z ' z t

x y z

y x '  
1 0 0 tx 
x 
y ' 0 1 0 ty 
y 
  

z '  
0 0 1 tz 
z 
  

1   0 0 0 1 1
x
z
P ' T . P
 3D Rotation
y' y cos z sin  z' z cos x sin 
x ' x cosy sin 
z ' y sin z cos  x ' z sin x cos 
y' x sin y cos 
x' x y ' y
z ' z
x' cos  sin 0 0x x' 
1 0 0 0x x' cos 0 sin 0 x
 y'  0 0y
 
y' sin cos 0 0 y
 y' 
0 cos sin 0 y  
1 0

  .    . .
z'   0 0 1 0z  z' 
0 sin cos 0 z z ' 
sin 0 cos 0 z
        
1   0 0 0 11 1  
0 0 0 11 1   0 0 0 1 1

P ' Rz ().P P '  R x (). P P '  R y (). P

 Z-Axis Rotation  X-Axis Rotation  Y-Axis Rotation cyclic order

x yz x

5
 Rotation about axis parallel to co-ordinate axis
E.g. x-axis
STEPS

1. Translate the
object so as to
Step 1 coincide rotation
axis to parallel co-
ordinate axis

2. Perform the
rotation about x-
axis

Step 2 Step 3
3. Translate back
the object so as to
move rotation axis
to original position
6
 General 3D Rotations
Rotation about an Arbitrary Axis

Basic
BasicIdea
Idea

1.
1. Translate
Translatethe
theobject
objectso
sothat
thatthe
therotation
rotationaxis
axispasses
passesthrough
throughthe
thecoordinate
coordinate
origin
origin

2.
2. Rotate
Rotatethe
theobject
objectso
sothat
thatthe
theaxis
axisof
ofrotation
rotation coincides
coincideswith
withone
oneof
ofthe
the
coordinate
coordinateaxes
axes

3.
3. Perform
Performthe
thespecified
specifiedrotation
rotationabout
aboutthe
thecoordinate
coordinateaxis
axis

4.
4. Apply
Applyinverse
inverserotations
rotationsto
tobring
bringthe
therotation
rotationaxis
axisback
backto
toits
itsoriginal
original
orientation
orientation

5.
5. Apply
Applythe
theinverse
inversetranslation
translationto
tobring
bringthe
therotation
rotationaxis
axisback
backto
toits
itsoriginal
original
position.
position.
Arbitrary Axis Rotation
Arbitrary Axis Rotation
Arbitrary Axis Rotation
Arbitrary Axis Rotation
Arbitrary Axis Rotation
Arbitrary Axis Rotation
 Example

Find
Findthe
thenew
newcoordinates
coordinatesof
ofaaunit
unitcube
cube90º-rotated
90º-rotatedabout
about
an
anaxis
axisdefined
definedby
byits
itsendpoints
endpointsA(2,1,0)
A(2,1,0)and
andB(3,3,1).
B(3,3,1).

N T
M E
G N
SI
A Unit Cube AS
 Example
Step1. Translate point A to the origin

y
1 0 0 2
B’(1,2,1) 0 1 0 1
T 
0 0 1 0
A’(0,0,0)
x  
0 0 0 1
z
 Example
Step 2. Rotate axis A’B’ about the x axis by and angle ,
until it lies on the xz plane.

2 2 2 5
sin   
22 12 5 5
1 5
cos  
y 5 5
Projected point
(0,2,1) B’(1,2,1)
l  12 2 2 12  6

 l

1 0 0 0
x  5 2 5 
z 0
  0
B”(1,0,5)   5
R x  5 
 2 5 5
0 0
 5 5 

0
 0 0 1

 Example
Step 3. Rotate axis A’B’’ about the y axis by and angle 
until it coincides with the z axis.

1 6
sin  
y 6 6
5 30
cos  
6 6

l  30 6 
 x  0  0
(0,0,6)
6 6 
B”(1,0, 5)
  0
R y  1 0 0
z  6 0
30
0
6 6 
0 0 0 1
 
 Example
Step 4. Rotate the cube 90° about the z axis

0 1 0 0


1 0 0 0 
Rz  
90 

0 0 1 0
 
0
 0 0 1 

Finally, the concatenated rotation matrix about the arbitrary

axis AB becomes,

R 
 T 1R 
x
1

 R y 
1
R z  
90R y 
R x 
T
 Example

1 0 0 0 30 6 

1 0 02
 5 2 5  0 
00 1 0 0 

0 1 01
0 06 6 
1 0 0 0 
R
  
 5 5 0 1 0 0
 

0 0 10
 2 5 5  6 30 0 0 1 0
 0  0  0 0
 
0 0 0 
1 5 5  6 6 0 0 0 1
   
0 0 0 1

0 0 0 1

 30 6  1 0 0 0
 0  0  5 2 5 
1 0 0 2 
6 6  0  
00 1 0 1 
 0 1 0 0  5 5 
 
6 0 30 2 5 5 0 0 1 0
0 0 0
 
6 6   5 5 0 0 0 1
   

0 0 0 1 0 0 0 1
0 .166 0.075 0. 983 1. 742 
0 .742 0 .667 0. 075 1.151 
 
0 .650 0 .741 0.167 0.560 
 
 0 0 0 1 
 Example
Multiplying R(θ) by the point matrix of the original cube


P  
 R  P

0.166 0.075 0.983 1.742 

0 0 1 1 0 0 1 1
0.742 0.667 0.075 1.1511 1 1 1 0 0 0 0

P 
 
0.650 0.741 0.167 0.560 1 0 0 1 1 0 0 1
 
 
 0 0 0 1  1 1 1 1 1 1 1 1
2.650 1.667 1.834 2.816 2.725 1.742 1.909 2.891 
0.558 0.484 0.258 0.184 1.225 1.151 0.409 0.483
 
1.467 1.301 0.650 0.817 0.726 0.560 0.091 0.076 
 
 1 1 1 1 1 1 1 1 
 3-D SCALING
Scaling about origin

x '  s x 0 0 0 x  s x 0 0 0
y '  0    0 sy 0 0
sy 0 0 y S ( s , s , s )  
   .
0 0
x y z
z '  0 0 sz 0 z  0 sz
      
1  0 0 0 1 1  0 0 0 1
Fixed Point Scaling

x '  sx 0 0 (1 s x ) x f x 
y'  0 sy 0 ( 1 s y ) y f y 
  . 
z '  0 0 sz (1 sz ) z f z 
   
1  0 0 0 1 1 

S( x f , y f , z f , sx , s y , sz ) T ( x f , y f , z f ).S( sx , s y , sz ).T ( x f ,y f ,z f )

21
 3-D REFLECTION
Performed relative to a reflection axis or reflection plane
Axis reflection equivalent to 180º rotation about the axis in 3-D space
Plane reflection  equivalent to 180º rotation in 4-D space

Reflection in xy plane
x’ = x
y’ = y
z’ = -z Note :
yz plane
Matrix is as x -x
&
zx plane
y -y
1 0 0
0
0 1 0 0
RFz  
0 0 1 0 
 
0 0 0 1 22
 3-D SHEAR

x ' 
1 0 a 0x
Z-axis shear y' 
  0 1 b 0


y 
x’ = x + a.z .
z ' 
0 0 1 0z
y’ = y + b.z   
z’ = z 1  0 0 0 11

Parameter a and b can be assigned any

1 0 a 0 values
0 1 b 0
SH z  
 alters x and y coordinate values by an
0 0 1 0
  amount that is proportional to the z-value;
0 0 0 1 while leaving the z-coordinate unchanged.

23
3-D OBJECT REPRESENTATION

24
 3-D OBJECT REPRESENTATION
Most commonly used representation for 3-d object
Speeds up the surface rendering
wired frame applications can be displayed quickly to
give a general indication of surface structure.
Greater the number of smaller surfaces, better the
approximations

Polygon Surface
Approximation of
Cylinder
3-D OBJECT REPRESENTATION
Data Requirements for Polygon Surface Representation

Polygon data tables– to store information

Polygon Data Tables consists of

Geometric Tables- Consist of parameters that specify

polygon vertices and spatial orientation of polygons

Vertex Table-stores the coordinates of vertices

Edge Table-contains the pointer back to the vertex table to

identify the vertices for each polygon edge.

Polygon Table-contains pointer back into the edge table to

identify the edges for each polygon

Attributes Tables- Consist of parameters that specify

transparency, surface texture, color etc.
26
 3-D Object Representation

Convenient Organizations for

storing geometric data is to
create three lists

Vertex Table
Edge Table
Polygon Surface Table

27
 Guidelines to Generate Error Free Table

1. Every vertices listed as an end point for at least two edges

2. Every edge is part of at least one polygon

3. Every polygon is closed.

4. Every polygon has at least one shared edge

5. If edge table contains pointers to polygons, every edge

referenced by a polygon pointer has a reciprocal pointer
back to polygon
 3-D Object Representation
Spatial Orientation of Surface
Orientation of surface normal
How to find surface normal if surface vertices (x1,y1,z1), (x2,y2,z2) and (x3,y 3,z3) are given ?
Plane equation:
Ax By Cz D 0
Put the vertex coordinates (x1,y1,z1 ), (x2 ,y2,z2 ) and (x3,y3,z3 ) in plane equation to get

Solution obtained from cramer' s rule N = (A,B,C)

1 y1 z1 x1 1 z1 y
A 1 y2 z2 B  x2 1 z2
1 y3 z3 x3 1 z3
x1 y1 1 x1 y1 z1 x
C  x2 y2 1 D x 2 y2 z2
x3 y3 1 x3 y3 z3 z

Surface Normal N to the plane Ax+By+Cz+D=0 has the Cartesian components (A,B,C)

29
 3-D Object Representation
Two sides of a surface (Inside or Outside the Plane Surface)
For right handed cartesian system (i.e. if vertices are taken in
Counter-Clockwise order to evaluate A,B,C and D)

z
30
Projections
Transformation that changes a point in n-dimensional coordinate system
into a point in a coordinate system that has dimension less than n.

Converts 3-D viewing co-ordinates to 2-D projection co-ordinates

TYPES OF PROJECTION
Parallel Projection
Perspective Projection

PARALLEL PROJECTION
Orthographic
Oblique

31
 PARALLEL PROJECTION
1. Parallel Projection
- Coordinate positions are transformed to view plane along parallel
lines (projection lines)
- Preserves relative proportions of objects
- Accurate views of various sides of an object are obtained.
- Doesn’t give realistic representation of the appearance of the 3-D
object
- Types
- Orthographic- when the projection is perpendicular to the view
plane. Used to produce Front, Side and Top view of an object
- Oblique – when the projection is not perpendicular to the view plane

p2 View Plane

p1 P2 ’

P1’ Orthographic Projection Oblique Projection

Parallel Projection
 PERSPECTIVE PROJECTION
- Coordinate positions are transformed to view plane along lines
(projection lines) that converges to a point called projection
reference point (center of projection)
- Produce realistic view
- Does not preserve relative proportions
- Equal sized object appears in different size according as distance from
view plane

P2 View Plane

P1
P 2’ View Plane

P1’
Projection Projection
Reference Point
Reference Point
 ORTHOGRAPHIC PROJECTION OF A POINT ON TO A VIEW PLANE
x p=x
yp=y
Note: Z value is preserved for the depth information needed in depth culling and
visible surface determination procedure

yv

(x,y,z)
(x,y)
xv

zv
 Oblique Projection
Oblique projection vectors are specified by two angles
(x,y) are also the orthographic co-ordinates on view plane
and Ø 
Projection Matrix Calculation yv
(xp,y p)
xp = x + L.cosØ
yp = y + L.sinØ α L
Z Z (x,y,z)
tanα ,L  , L ZL1 Ø xv
L tan 
Coordinates
1 (x,y)
L1  (x,y,z) are
tan  viewing
coordinates View
xp = x + z(L1cosØ) Plane
yp = y + z(L1sinØ)
Final projection matrix for producing parallel projection will be zv

1
 0 L1 cos  0

0 1 L1 sin  0 Orthographic projection: When L 1 = 0
M parallel   xp = x

0 0 0 0 yp = y
 
0
 0 0 1

35
 Perspective Projection
P = (x,y,z)
Projection vectors meet at
projection reference point zprp
along the zv axis (xp,yp,zvp)
x’ = x – xu
y’ = y – yu zv
z’ = z – (z-zprp)u
u takes value between 0 and 1
zvp zprp
P’(x’,y’,z’) represents any point View
along the projection line
Plane
On view plane
z’ = zvp ; therefore
u = (zvp - z)/(zprp – z)
thus projection transformation
equations are
z prp zvp   d p  xh  
1 0 0 0 
x p x
z z  x
z z 

 x
 prp   prp  y 0 1 0 0 
y
z prp zvp   d p  h  .
y p y
z z  y
z z 
 zh  
0 0 zvp / d p zvp ( z prp / d p )  z
 prp   prp   
h  0
 0 1 / d p z prp / d p   1
Where, h = (zprp –z)/dp
and xp= xh/h, yp = yh/h
36
 Perspective projection

Vanishing Point: a set of parallel lines that are not parallel to view
plane are projected as converging lines that appear to converge at a
point called vanishing point y
•a set of parallel lines that are parallel to view plane are projected as
parallel lines
x
•More than one set of parallel lines form more than one vanishing
z
points in the scene

Principal Vanishing point: Vanishing point for a set of parallel lines

parallel to one of the principal axis of object

•We can control the number of principal vanishing point to one, two or Vanishing
Point
three with the orientation of projection plane and classify as one, two
or three point perspective projection

z-axis
X-axis
vanishing
vanishing
Point
Point
37
 3-D Viewing Pipeline

3-D scene generation

process analogous to
taking photographs with camera

38
VISIBLE SURFACE DETECTION

39
 Visible Surface Detection Method
Also called hidden surface elimination method
Considerations
Memory
Time
Object Type

Two approaches
Depends upon object definition or projected image
Object-space
Deals with object definition directly
Compares objects and parts of them to each other to
determine the visible object or its parts.
E.g. Line Display algorithms in wire-frame display

Image Space Method

deals with projected image of an object
Visibility is decided point by point at each pixel position on
projected plane
Can be adapted to determine visible-line detection.

40
 Back Face Detection Method (Plane Equation Method)
Fast and simple object-space method
Based on “inside” or “outside” test
Test whether view point is inside or outside the polygon surface
Point (x’,y’,z’) is “inside” a polygon surface with plane parameters A,B,C,D if
Ax+By+Cz+D<0 i.e. the polygon surface must be a back face.

Alternatively
1. Make the center of object at origin
2. Calculate the value of D of the plane by taking three points in anticlockwise
direction.
3. If D<=0 the surface is visible
D>0 the surface in invisible. N
Consider Normal Vector N = (A,B,C) to
polygon surface and Vector V in viewing direction
The polygon is back face if: V.N>0
If V.N<0 Visible Surface
V
If object description is converted to viewing
co-ordinates then, V is along zv axis i.e V = (0,0,Vz),
then:
V.N = VzC
Fig: Vector V in the Viewing
i.e V.N > 0  VzC
Direction and a back face normal
So we need to consider only sign of C Vector N of a polyhedron
41
 Back Face Detection Method (Plane Equation Method)

For right handed viewing system

with viewing direction along
negative zv axis, if c<0  back
face
What if C = 0 ??
viewing direction is
perpendicular to
surface normal also Fig: A polygon surface with C < 0 in a right-handed
back face viewing coordinate system is identified as a back face
So, back face if C≤0 when the viewing direction is along the negative Zv axis

• Doesn't works well for

1. Overlapping front
faces due to
- Multiple objects
- Concave objects
2. Non Closed Objects
3. Non-polygonal models
 Depth Buffer (Z-Buffer) method
Commonly used Image-space method to detect visible surface
Surface depth is compared at each pixel position on the projection plane
Object depth is usually measured from the view plane along the z-axis of the
viewing system

For each pixel position (x,y) on projection plane, object depths can be compared
by comparing z-values as each (x,y,z) position on a polygon surface corresponds to
the orthographic projection point (x,y) on projection plane

Usually applied to scene containing only polygon surfaces; but possible to apply for
non-planar surfaces

Two buffers required

Depth buffer: to store depth value for each position as surfaces are processed
Initially all positions are set to 0 (minimum depth)
Refresh buffer: to store intensity values of each position
Initially refresh buffer is initialized to background intensity

DRAWBACK: Deals only with opaque surface but not with transparent surface
i.e. it can only find one visible surface at each pixel position

43
 Depth Buffer Method- Algorithm
1. Initialize the depth buffer and refresh buffer so that for
all buffer positions (x,y),
depth(x,y) = 0, refresh(x,y) = Ibackgrnd

2. For each position on each polygon surface, compare

A
depth values to previously stored values in the depth
buffer to determine visibility B
Calculate the depth z for each (x,y) position on
the polygon y
If z>depth(x,y), then set
depth(x,y)=z, refresh(x,y)=Isurf(x,y)
z2 z1
Ibackgrnd = background intensity
Isurf(x,y) = projected intensity value
for the surface at pixel x
position (x,y)
z
3. After all pixels and surfaces are compared, draw object
using x,y,z from depth and intensity refresh buffer.
44
 Depth Buffer (Depth Computation)
From plane equation, depth is
Ax By D
z y
C
y-1
For the next adjacent pixel (x+1,y) in a scan
line, depth is
A( x 1) By D
z'  or z ' z A x x+1
C C
Start from top scan line to bottom scan line top scan line’
Starting from top vertex, calculate x position
down the left edge of the polygon recursively
y scan line
as
left edge intersection
x’ = x – 1/m
Thus depth value for the next pixel in left edge bottom scan line
is obtained as
A B
put x’ = x-1/m and y’ = y-1
z ' z m y scan line’
C y-1 scan line’
For vertical edge m = infinity, so:

z' z B
C x X’
45
 A-Buffer Method
Extension of depth buffer method
represents Antialiased, area-average, accumulation-buffer
The depth buffer is expanded so that
each position in the buffer can reference
a linked list of surfaces foreground
background
thus enabling more than one opaque
transparent
surface
surface intensity consideration surface

Each pixel position in the A-Buffer has two fields

Depth Field  stores a positive or negative real number
Positive single surface contributes to pixel intensity
Negative  multiple surfaces contribute to pixel intensity
Intensity Field  stores surface-intensity information or a pointer value
Surface intensity if single surface  stores the RGB components of the
surface color at that point and percent of pixel coverage
Pointer value if multiple surfaces

d>0 I d<0 Surf1 Surf2

depth intensity depth intensity
field field field field
46
 A- Buffer Method
Data for each surface in the linked list includes
RGB intensity components
Opacity parameter (percent of transparency)
Depth
Percent of area coverage
Surface identifier
Other surface-rendering parameters
Pointer to next surface

Scan lines are processed to determine surface overlaps of

pixels across the individual scan lines.
Surfaces are subdivided into a polygon mesh and clipped
against the pixel boundaries
The opacity factors and percent of surface overlaps are used
to determine the pixel intensity as an average of the
contribution from the overlapping surfaces
 Scan-Line Method
Extension of scan line algorithm for filling polygon interiors
Instead of filling just one surface, we deal with multiple surfaces
As each scan line is processed, all polygon surfaces intersecting that line are examined
to determine which are visible.
Across each scan line , depth calculations are made for each overlapping surface to
determine, which is nearest to view plane.
When the visible surface has been determined , the intensity value for that position is
entered into the refresh buffer.

DATA STRUCTURE
A. Edge table containing
Coordinate endpoints for each line in a scene
Inverse slope of each line
Pointers into polygon table to identify the surfaces bounded by each line
B. Surface table containing
Coefficients of the plane equation for each surface
Intensity information for each surface
Pointers to edge table

C. Active Edge List

To keep a trace of which edges are intersected by the given scan line

Note :
The edges are sorted in order of increasing x
Define flags for each surface to indicate whether a position is inside or outside the surface
48
 SCAN LINE ALGORITHM
I. Initialize the necessary data structure
1. Edge table containing end point coordinates, inverse slope
and polygon pointer.
2. Surface table containing plane coefficients and surface
intensity
3. Active Edge List
4. Flag for each surface

II. For each scan line repeat

1. update active edge list
2. determine point of intersection and set surface on or off.
3. If flag is on, store its value in the refresh buffer
4. If more than one surface is on, do depth sorting and store the
intensity of surface nearest to view plane in the refresh buffer
 Scan-Line Method (contd…)
For scan line 1
The active edge list contains edges AB,BC,EH, FG
Between edges AB and BC, only flags for s1 == on and
between edges EH and FG, only flags for s2==on
no depth calculation needed and corresponding
surface intensities are entered in refresh buffer E
B
For scan line 2 yv
F
The active edge list contains edges AD,EH,BC and FG Scan Line 1
Between edges AD and EH, only the flag for surface s1 A
== on S1 S2
Between edges EH and BC flags for both surfaces == on Scan Line 2
Depth calculation (using plane coefficients) is Scan Line 3
needed. H C
In this example ,say s2 is nearer to the view plane
than s1, so intensities for surface s2 are loaded into D
G
the refresh buffer until boundary BC is encountered
Between edges BC and FG flag for s1==off and flag for xv
s2 == on
Intensities for s2 are loaded on refresh buffer
For scan line 3
Same coherent property as scan line 2 as noticed from
active list, so no depth calculation needed between
edges BC and EH

50
 Scan-Line Method (contd…)

Problem: Subdividing line

Dealing with cut through surfaces and
cyclic overlap is problematic when used
coherent properties
Solution: Divide the surface to eliminate the
overlap or cut through
Subdividing line

yv
E
B F

Scan Line 1
A Subdividing line
Scan Line 2
S1 S2
Scan Line 3
Scan Line 4
H C

D
G

xv
51
Illumination Models & Surface Rendering Methods

52
 Illumination and Rendering

An illumination model in computer graphics

also called a lighting model or a shading model
used to calculate the color of an illuminated position on the
surface of an object
Approximations of the physical laws

A surface-rendering method determine the pixel

colors for all projected positions in a scene
 Photorealism in Computer Graphics
Photorealism in computer graphics involves
Accurate representations of surface properties, and
Good physical descriptions of the lighting effects

Modeling the lighting effects that we see on an object is a

complex process, involving principles of both physics
and psychology

Physical illumination models involve

Material properties, object position relative to light
sources and other objects, the features of the light
sources, and so on
 Light Sources
Total Reflected Light = Contribution from light sources
+ contribution from reflecting surfaces
Point Source: when light source model is a reasonable
approximation for sources whose dimensions are small
compared to the size of objects in a scene. e.g. Sun

Distributed Light Source: area of source is not small

compared to the surfaces in the scene
e.g. Fluorescent lamp

55
 Ambient Light

Also called background light

Multiple reflection of nearby (light-reflecting) objects
yields a uniform illumination
A form of diffuse reflection independent of the viewing
direction and the spatial orientation of a surface
Ambient illumination is constant for an object
I amb kaIa
Ia : the incident ambient intensity
ka : ambient reflection coefficient, the proportion
reflected away from the surface
 Diffuse Reflection
Surfaces are rough
Incident light is scattered with equal intensity in all
directions
Surfaces appear equally bright from all direction.
Such surfaces are called ideal diffuse reflectors (also
referred to as Lambertian reflectors)
Lambert’s Cosine Law

N
 Diffuse Reflection

Light intensity is independent of angle of reflection

Light intensity depends on angle of incidence

When cosƟis
+ve surface is illuminated
-ve light source is behind the surface
 Diffuse Reflection

I diff kdIl cos kdIl ( N 

L)

Il : the intensity of the light source

kd : diffuse reflection coefficient,

N : the surface normal (unit vector)

L : the direction of light source,

(unit vector)

When cosƟis
+ve surface is illuminated
-ve light source is behind the surface
Ambient + Diffuse

ka I a kd Il ( N 
 L) if N 
L 0
I 
 ka Ia if N 
L 0

Fig: sphere illuminated with different intensity ambient light

Illuminated with varying direction light source
 Specular Reflection
Perfect reflector (mirror) reflects all lights to the direction where angle of
reflection is identical to the angle of incidence

It accounts for the highlight

Near total reflector reflects most of light over a range of positions close to
the direction

E.g. illumination on shiny surface such as polished metal, an apple or a

person’s forehead

Shiny surface have a narrow specular-reflection range, and dull surfaces

have a wider reflection range.
N
L R N
L R
 Phong Specular Reflection Model
Sets Intensity of specular reflection proportional to cos n s 
ns  specular reflection parameter (depends on surface)
Ø ranges from 0 to 900 (cos Ø varies from 0 to 1)

Intensity of specular reflection depends on:

Material properties of surface
Angle of incidence θ
Other factors such as polarization and color of the incident light

Monochromatic specular intensity variations can be approximated using

specular-reflection coefficient, W(θ) for each surface

I spec  w () I l cos ns


N
L R
At θ= 900 , w(θ) = 1  all incident light is reflected
θ θØ V

63
Specular Reflection

cosns 
 Specular Reflection

I spec ksIl cos ksIl ( R 

ns
V) ns

N unit normal Vector

L unit vector towards light source
R unit vector to specular reflection
direction
V unit vector towards viewer
angle between R and V

Il : intensity of the incident light

ks : color-independent specular coefficient

ns : specular reflection parameter (depends upon surface)

 Specular Reflection
Specular-reflection coefficient ks is a material property
For some material, ks varies depending on 
ks =1 if =90°

Calculating the reflection vector R

R L (2N 
L)N
R (2N.L)N L
 Specular Reflection
Simplified Phong model using halfway vector

Replacing V.R with N.H where H is halfway vector between L and V

(i.e. H is unit bisector vector of angle between L and V)

H is constant if both viewer and the light source are sufficiently far
from the surface

L V
H 
| L V |
 Combined Diffuse and Specular Reflection

Point Light Source

I I diff I spec
k a I a k d I l ( N . L ) k s I l ( N . H ) n s
Multiple light sources (n light sources)

 
n
I k a I a I li k d ( N .Li ) k s ( N .H i ) ns

i 1

68
 Intensity Attenuation
Intensity attenuation must be considered for producing realistic lighting
effects.
Intensity of radiant energy at a point d distance far from source is attenuated
by 1/d2
attenuation factor 1/d2 produces too much intensity variation

Using inverse linear quadratic function of d for intensity attenuation as:

f (d )  1
a 0 a 1 d a 2 d 2
a0 can be adjusted to prevent f(d) from becoming too large when d is
very small
Magnitude of attenuation function is limited to 1 as
 1 
f ( d ) min 
1,
 a a d a d 2 

 0 1 2 
The Phong illumination model considering attenuation is:

 
n
I k a I a  f ( d i ) I li k d ( N . L i ) k s ( N . H i ) n s
i 1
69
 Color Consideration in Phong Illumination model
For RGB description, each color in a scene is expressed in terms of R,G and B
components
Various methods:
Described by considering the RGB components for e.g. (k dR,kdG ,kdB) of
diffuse reflection coefficient vector
e.g. For blue light (kdR=k dG=0)

 
n
I B k aB I aB f ( d i ) I lBi k dB ( N . Li ) k sB ( N . H i ) n s
i 1

Described by specifying components of diffuse and specular color vectors

for each surface and retaining the reflectivity (k) as a single valued
constants

 
n
I B k a S dB I aB f ( d i ) I lBi k d S dB ( N . Li ) k s S sB ( N . H i ) ns
i 1
Described by specifying wavelength for a color specification. This
specification is useful to specify color as more than three components

 
n
I B ka S dI a f (d i ) I li kd S d( N .Li ) ks S s( N .H i )ns
i
1
70
 Transparency
Transparent surface produces both reflected and transmitted
light

Light intensity depends on relative transparency and position

of light source or illuminated object behind or in front of the incident
transparent surface light

To model transparent surface, intensity contribution of light

from various sources (illuminated objects) that are transmitted
from the surface must be considered in the intensity equation transparent
object

Both diffuse and specular reflection take place on transparent

surface
Diffuse effects are important for partially transparent surfaces
air glass air
such as frosted glass
Incident
The Snell’s law is used to calculate the light
refracted ray direction
i
sin r  sin i
r
71
 Transparency (contd…)
Transmitted intensity Itrans through a transparent surface from a
background object and Reflected intensity Irefl from the transparent
surface with transparency coefficient kt is given by

I = (1-kt)Irefl + ktItrans
where (1-k t) is opacity factor

Transparency effects Implementation:

1. Process opaque objects first to determine depths for visible opaque

surfaces.
2. Depth positions of the transparent objects are compared to the values
previously stored in the depth buffer.
3. If any transparent surface is visible, its reflected intensity is calculated and
combined with the opaque-surface intensity previously stored in the
frame buffer.
4. Visible transparent surfaces are then rendered by combining their
surface intensities with those of the visible and opaque surfaces behind
them.
72
 Shadow
Hidden surface method with light source at the view position
can be used

The shadow area for all light sources are determined and
these shadows could be treated as a surface pattern arrays

Light
direction

73
 Assigning Intensity Level
The intensity calculated by illumination model must be converted to the
allowable intensity of a particular graphics system

The difference between intensities 0.20 and 0.22 should be perceived same as
that of 0.80 and 0.88

The intensity level in a monitor should be spaced so that the ratio of successive
intensities is constant
for n+1 successive intensity levels
I1/I0=I2/I1=……..In/In-1 = r
Ik = r kI0
also In = 1  r = (1/I0)1/n
so, Ik = I0(n-k)/n

Lowest intensity value I0 depends on the characteristics of the monitor

( I0 ranges from 0.005 to around 0.025)
the black level displayed on monitor will have some intensity

The highest intensity value is 1

For color system (blue color for example)
IBk = rBkIB0
74
 Polygon Rendering Methods
Objects usually polygon-mesh approximation

Illumination model is applied to fill the interior of polygons

Curved surfaces are approximated with polygon meshes

But polyhedra that are not curved surfaces are also modeled
with polygon meshes

Two ways of polygon surface rendering:

1. Single intensity for all points in a polygon
2. Interpolation of intensities for each point in a polygon

Methods:
1. Constant Intensity Shading
2. Gouraud Shading
3. Phong Shading

75
 Constant Intensity Shading or Flat Shading
-Fast and simple method for rendering an object
with polygon surface
-Each polygon shaded with single intensity
calculated for the polygon

PROCEDURE
1. Take a point on the object surface and
calculate the intensity
2. Render the surface with same intensity
throughout the surface
3. Repeat above procedure for each polygon
surface

ASSUMPTIONS
1. Object is a polyhedron
2. light sources should be sufficiently
(i.e. N.L and attenuation function are constant)
3. Viewing position is sufficiently far
(i.e. V.R is constant over the surface)

DRAWBACK: intensity discontinuity at the

edges of polygons
76
Credit goes to the students
 Gouraud Shading
Intensity interpolation method
Renders a polygon surface by linearly interpolating intensity
values across the surface.
Intensity discontinuity at the edges of polygons is eliminated by
matching intensity values of each polygon with adjacent
polygons

PROCEDURE
1. Determine the average unit normal vector at each polygon
vertex
2. Calculate each of the vertex intensities by applying an
illumination model
3. Linearly interpolate the vertex intensities over the polygon
surface

77
 Gouraud Shading (contd…)
N2 N3
Average Unit Normal: Obtained by averaging the
surface normals of all polygons sharing the vertex
n N1
N k
N v  k 1
n
N4 V

N
k 1
k y 3

Intensity interpolation: 1
P scan line
Along the polygon edges are obtained by 4 5
interpolating intensities at the edge ends
2
Recursive calculation along the edge
y 4 y 2 y y 4 I ' I  2
I I 1
I4  I1  1 I2 y 1 y 2 x
y 1 y 2 y 1 y 2

Along the scan line between the polygon edges I1

I
are obtained by interpolating intensities at the y
scan lines
intersection of scan line and polygon edges y-1
I’ I2
x 5 x p x p x 4 Recursive Calculation
Ip  I4  I5 along the scan line ??
x 5 x 4 x 5 x 4 x x+1 78
Surface Rendering
 Gouraud Shading Problems
Lighting in the polygon interior is inaccurate
Mach band effect
Optical illusion
“Mach Bands” are not physically there. Instead, they are illusions due
to excitation and inhibition in our neural processing
bright and dark intensity streaks caused by linear interpolation of
intensities

Solution: Could be reduced by dividing the surface into large number of

polygons or by using other methods, such as Phong shading

The bright bands at

45 degrees (and 135
degrees) are illusory.
The intensity of each
square is the same.
 Phong Shading
More accurate method for rendering
(x 3,y3) N3
N1
Interpolate normal vectors and apply y
illumination model to each surface point
N
PROCEDURE (x 1,y1) Scan line

1. Determine average unit normal vectors at (x2 ,y2 ) N2

each polygon vertex
x
2. Linearly interpolate the vertex normals
over the surface of the polygon

3. Apply an illumination model along each

scan line to calculate projected pixel y y2 y1 y
intensities for the surface points N N1  N2
y1 y 2 y1 y2
Trade-off: requires considerably more Note: Students are encouraged to read
calculations Fast Phong Shading which could be useful
for project works
81
 Gouraud versus Phong Shading
Gouraud shading is faster than Phong shading
Phong shading is more accurate
THANKS ~!!!~
MID POINT ALGORITHM PARAMETERS FOR SOME CURVES
 Rectangular Hyperbola (x.y=a)

At boundary of two regions

dy y

dx x

dy
 1
dx
 x  a


x0 , y 0 
 a, a  
|m| <1 for R2 so sample to x
Since curve is symmetric about the point
(x0,y0) we may take this point as starting point
and calculate the pixels in R2 and find
symmetric points in R1 by interchanging x and y
The conjugate curve can be drawn by taking
changing x to –x and y to -y
 x.y = a

f ( x , y )  x . y a

0 ,
 if ( x , y ) is below the curve
f ( x , y ) 0 , if ( x , y ) is on the curve

0 , if ( x , y ) is above the curve
 x. y = a

1
pk f ( x k 1, y k  )
2
( xk 1).( y k 1 ) a
2
1
pk 1 f ( xk 1 1, yk 1  )
2
1
[( xk 1) 1].( yk 1  ) a p 0  f ( x 0 1 , y 0  1 )
2 2
pk 1 pk ( xk 1)( y k 1 yk ) ( y k 1 1 ) ( x 0 1 ).( y 0  2 ) a
1
2  ( a  1 ).( a  1 ) a
pk ( y k 1 ) if pk 0 2
2  a 1
pk xk yk  5 otherwise
2 2
2
 Straight line (y = m.x + b)
For |m|<1

f ( x, y) m.x y b

0, if ( x, y ) is above the line


f ( x, y ) 0 , if ( x, y ) is on the line
0 , if ( x, y ) is below the line

 y = m.x + b

(x0,y0) be starting point

pk f ( xk 1, y k 1 )
2
1
m.( xk 1) ( y k  ) b
2
pk 1 f ( xk 1 1, yk 1 1 )
2
1
m.[( xk 1) 1] ( yk 1  ) b
2
1
pk 1 pk m ( yk 1 yk ) p 0  f ( x 0 1 , y 0  )
2
 pk m if pk 0
m .( x 0 1 ) ( y 0  1 ) b
 pk m 1 otherwise 2
m 1
2
For the curve

x
y Ae
 At boundary

dy
 A . e  . x
dx
dy
 1
dx
ln( A . )
 x 

Two regions
Region 1 |m|>1
Region 2  |m|<1

f ( x, y) Ae x y
0, if ( x, y) is above the curve

f ( x, y) 0, if ( x, y ) is on the curve

0, if ( x, y ) is below the curve
 Region 1
ln(A.)
x

1
p1k  f ( x k  , y k 1 )
1
2
 ( x k  )
 Ae  ( y k 1 )
2
 / 2  . x k
 Ae .e  y k 1 1
1 p10  f ( x0  , y 0 1 )
p1k 1  f ( x k 1  , y k 1 1 ) 1
2
1
2  Ae
 ( 0 
2
)
 ( A 1 )
 ( x 
 ( y k 1 ) 1 
k 1 )  / 2
 Ae 2 A (e 1 )  1
 / 2
 Ae . e  . x k 1  y k  2

p1k 1 p1k Ae/ 2 (e .xk 1 e.xk ) 1

p1k 1 if p1k 0
p1k Ae/ 2 (e .( xk 1) e .xk ) 1 otherwise
 Region 2
ln( A . )
x 
1
p 2k f ( xk 1, yk  ) 
2
( x k  1
Ae ( yk  )
1)

2
 . x k 1
Ae .e yk 
2
1
p 2 k 1  f ( x k 1 1 , y k 1  1 ) p 2 0  f ( x 0 1, y 0  )
2 2
Ae  ( x k 2 ) ( y k 1  1 ) 1
2 Ae .e . x 0 y 0 
Ae 2  .e  . x k  y k 1  1 2
2
p 2k 1 p 2k A(e  1).e .( xk 1) ( yk 1 yk )
 .( x k 
p 2k A(e 1).e 1)
if p2 k 0
p 2k A(e  1).e .( xk 1) 1 otherwise