CA 301: Computer Graphics and Multimedia
Systems
Dr. Aparna Shukla
Department of Computer Science and Engineering
BIT, Mesra (Lalpur Campus)
Lecture 2
Output Primitives in Computer Graphics
Line
Outline of the Lecture
• Scan Conversion /Rasterization
• Scan Conversion Operation
• Line
• Scan Converting of Line
• Line Drawing Algorithm
Scan Conversion (Rasterization)
Convert high-level geometry description to pixel colors in the frame buffer
Example: Given vertex x, y coordinates determine pixel colors to draw line
Two ways to create an image:
Scan existing photograph
Procedurally compute values (rendering)
Viewport
Rasterization
Transformation
Scan Conversion (Rasterization)
A fundamental computer graphics function
Determine the pixels’ colors, illuminations, textures, etc.
Implemented by graphics hardware
Rasterization algorithms
Lines
Circles
Triangles
Polygons
Rasterization Operations
Drawing lines on the screen
Manipulating pixel maps (pixmaps): copying, scaling, rotating, etc
Compositing images, defining and modifying regions
Drawing and filling polygons
Previously glBegin(GL_POLYGON), etc
Aliasing and antialiasing methods
Line
A straight line is specified by two endpoint
positions. A line segment is thus defined as :
𝑳𝑳𝑳𝑳𝑳𝑳𝑳𝑳𝑳𝑳𝑳𝑳𝑳𝑳 = 𝒙𝒙𝟏𝟏 , 𝒚𝒚𝟏𝟏 , 𝒙𝒙𝟐𝟐 , 𝒚𝒚𝟐𝟐
A line is produced by means of illuminating a set
of intermediary pixels between the two end points
Line drawing is done by-
Calculating intermediate positions between the
endpoints.
Directing the output device to fill in the calculated
positions as in the case of plotting single points.
Line
Plotted positions may be only approximations
to the actual line positions between endpoints.
A computed positions (10.48,20.51) is
converted to pixel (10, 21)
• This rounding causes the lines to be
displayed with as stair step appearance.
• Stair steps appearance are noticeable in low
resolution systems, it can be improved by;
Displaying lines on high resolution systems
Adjusting intensities along line path
Line
• To load an intensity value into the frame buffer at a position corresponding to
column x along scan line y
setpixel (x, y)
• To retrieve the current frame buffer intensity setting for a specified location we
use a low level function;
getpixel (x, y)
Line Drawing
Problem: Given two end-points on the grid, find the pixels on the line connecting
them
Description: Given the specification for a straight line, find the collection of
addressable pixels which most closely approximates this line.
Goals: (not all of them are achievable with the discrete space of a raster device):
Straight line should appear as a straight line.
Primitives should start and end accurately
Primitives should have a consistent brightness along their length
They should be drawn rapidly.
Quality of the line drawn depends on the location of the pixels and their
brightness
Line Drawing
8
7 Line: (3,2) -> (9,6)
6
5
4
3 ? Which intermediate
2
pixels to turn on?
1
0 1 2 3 4 5 6 7 8 9 10 11 12
Line Drawing Algorithm
We are going to analyze how this process is achieved
Line Drawing Algorithm
Line Drawing Algorithm
Line Drawing Algorithm
Direct use of line equation
DDA (Digital Differential Analyzer)
Bresenham's Algorithm
Line Drawing Algorithm 1- Direct Method
It is the simplest form of conversion.
First of all scan P1 and P2 points. P1 has co-ordinates.
Slope-intercept line equation
y = mx + b
Given two end points (x0,y0), (x1, y1), how to compute m and b?
dy y1 − y 0
m= = b = y 0 − m * x0
dx x1 − x0
(x1,y1)
dy
(x0,y0)
dx
Line Drawing Algorithm 1- Direct Method
Example -Numerical example of finding slope m:
(x0, y0) = (23, 41), (x1, y1) = (125, 96)
y1 − y 0 96 − 41 55
m= = = = 0.5392
x1 − x0 125 − 23 102
x1,y1)
dy
(x0,y0)
dx
Line Drawing Algorithm 1- Direct Method
1. Start Algorithm
2. Input two end points 𝑥𝑥0 , 𝑦𝑦0 and 𝑥𝑥1 , 𝑦𝑦1
𝑦𝑦1 −𝑦𝑦0
3. Compute the slope of line, 𝑚𝑚 =
𝑥𝑥1− 𝑥𝑥0
4. Compute y-intercept of the line, 𝑐𝑐 = 𝑦𝑦0 -m*𝑥𝑥0
5. Set initial values of x and y as 𝑥𝑥 = 𝑥𝑥0 and 𝑦𝑦 = 𝑦𝑦0
6. Plot the first end point, plotpixel (x, y)
Line Drawing Algorithm 1- Direct Method
7. If 𝑚𝑚 ≤ 1 then
while 𝑥𝑥 ≤ 𝑥𝑥1
increment x coordinate, 𝑥𝑥 = 𝑥𝑥 + 1
compute y coordinate, 𝑦𝑦 = 𝑚𝑚𝑥𝑥 + 𝑐𝑐
Round off the y-value and plotpixel (x, y)
End while
8. else
while 𝑦𝑦 ≤ 𝑦𝑦1
increment x coordinate, 𝑦𝑦 = 𝑦𝑦 + 1
𝑦𝑦−𝑐𝑐
compute y coordinate, 𝑥𝑥 =
𝑚𝑚
Round off the x-value and plotpixel (x, y)
End while
End if
9. stop
Line Drawing Algorithm 1- Direct Method
This algorithm sounds well mathematically, it involves floating point computation
(multiplication and addition) in every step that uses line equation
y=mx + c.
Find a way to achieve the same goal as quickly as possible.
Direct Method Line Algorithm-Example
Question- Scan convert a line by direct method whose end points are (3, 4) and
ending point (9, 5) is given. Find the points to be plotted
Step Step Description Computation Result
No
1 Input two end points 𝑥𝑥0 , 𝑦𝑦0 and 𝑥𝑥0 , 𝑦𝑦0 =(3,4) and
𝑥𝑥1 , 𝑦𝑦1 𝑥𝑥1 , 𝑦𝑦1 =(9, 5)
𝑦𝑦1 −𝑦𝑦0 5−4
2 Compute the slope of line, 𝑚𝑚 = m=1/6
𝑥𝑥1− 𝑥𝑥0 𝑚𝑚 = = 1/6
9−3
3 Compute y-intercept of the line, 𝑐𝑐 = 𝑦𝑦0 - c= 4-(1/6*3)=4- c= 7/2
m*𝑥𝑥0 1/2=7/2
4 Set initial values of x and y as 𝑥𝑥 = 𝑥𝑥0 and 𝑦𝑦 = 𝑦𝑦0 𝑥𝑥 = 3 and 𝑦𝑦 =
4
Direct Method Line Algorithm-Example
Step Step Description Computation Result
No
5 Plotting very first pixel; plotpixel (3,4)
plotpixel (x, y)
6 Check the value of m, if (m<=1) 𝑚𝑚 = 1/6 <=1 If condition is
True
7 while 𝑥𝑥 ≤ 𝑥𝑥1 while 3≤9 plotpixel
increment x coordinate, x = 𝑥𝑥 + 1 increment x, x = 3 + 1 (3, 4)
compute y coordinate, 𝑦𝑦 = 𝑚𝑚𝑥𝑥 + 𝑐𝑐 compute y coordinate, 𝑦𝑦 =
Round off the y-value and 1 7
𝑚𝑚𝑥𝑥 + 𝑐𝑐 = ∗ 4 + =
6 2
plotpixel (x, y)
4.166 …
End while
Round off the y-value and
End while
Direct Method Line Algorithm-Example
X Y=mx+c Plot Pixel
3 4 (3,4)
4 4.17 (4,4)
5 4.33 (5,4)
6 4.50 (6,4)
7 4.66 (7,4)
8 4.83 (8,4)
9 5.00 (9,5)
Line Drawing Algorithm 1- Direct Method
Question-A line with starting point as (0, 0) and ending point (6, 18) is given.
Calculate value of intermediate points and slope of line
Next Lecture Agendas
DDA Line Algorithm
Bresenham's Algorithm
Thanks
