Scan Conversion Notes | EduRev

Created by: Gurmeet Kaur

: Scan Conversion Notes | EduRev

 Page 1


CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Scan Conversion
CS123
1 of 44 Scan Conversion - 10/15/13
Page 2


CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Scan Conversion
CS123
1 of 44 Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Line Drawing
? First problem statement:  Draw a line on a raster screen between two 
points
? Why is this a difficult problem?
? What is “drawing” on a raster display?
? What is a “line” in raster world?
? Efficiency and appearance are both important
Problem Statement
? Given two points P and Q in XY plane, both with integer coordinates, 
determine which pixels on a raster screen should be on in order to best 
approximate a unit-width line segment starting at P and ending at Q 
2 of 44 
Scan Converting Lines
Scan Conversion - 10/15/13
Page 3


CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Scan Conversion
CS123
1 of 44 Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Line Drawing
? First problem statement:  Draw a line on a raster screen between two 
points
? Why is this a difficult problem?
? What is “drawing” on a raster display?
? What is a “line” in raster world?
? Efficiency and appearance are both important
Problem Statement
? Given two points P and Q in XY plane, both with integer coordinates, 
determine which pixels on a raster screen should be on in order to best 
approximate a unit-width line segment starting at P and ending at Q 
2 of 44 
Scan Converting Lines
Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
? Final step of rasterisation (process of taking geometric shapes and 
converting them into an array of pixels stored in the framebuffer to be 
displayed) – converting from “random scan”/vector specification to a 
raster scan where we specify which pixels are on (and how much) 
based on a stored array of pixels
? Takes place after clipping occurs
? All graphics packages do this at end of the rendering pipeline
? Takes triangles (or higher-order primitives) and maps them to pixels on 
screen
? For 3D rendering also takes into account other processes, like lighting 
and shading, but we’ll focus first on algorithms for line scan conversion
3 of 44 
What is Scan Conversion?
Scan Conversion - 10/15/13
Page 4


CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Scan Conversion
CS123
1 of 44 Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Line Drawing
? First problem statement:  Draw a line on a raster screen between two 
points
? Why is this a difficult problem?
? What is “drawing” on a raster display?
? What is a “line” in raster world?
? Efficiency and appearance are both important
Problem Statement
? Given two points P and Q in XY plane, both with integer coordinates, 
determine which pixels on a raster screen should be on in order to best 
approximate a unit-width line segment starting at P and ending at Q 
2 of 44 
Scan Converting Lines
Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
? Final step of rasterisation (process of taking geometric shapes and 
converting them into an array of pixels stored in the framebuffer to be 
displayed) – converting from “random scan”/vector specification to a 
raster scan where we specify which pixels are on (and how much) 
based on a stored array of pixels
? Takes place after clipping occurs
? All graphics packages do this at end of the rendering pipeline
? Takes triangles (or higher-order primitives) and maps them to pixels on 
screen
? For 3D rendering also takes into account other processes, like lighting 
and shading, but we’ll focus first on algorithms for line scan conversion
3 of 44 
What is Scan Conversion?
Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Special cases:
? Horizontal Line:
? Draw pixel P and increment x coordinate value by 1 to get next pixel.
? Vertical Line:
? Draw pixel P and increment y coordinate value by 1 to get next pixel.
? Diagonal Line:
? Draw pixel P and increment both x and y coordinate by 1 to get next pixel.
? What should we do in general case?
? For slope <= 1, increment x coordinate by 1 and choose pixel on or closest to line. 
Slopes in other octants by reflection (e.g., in second octant, increment Y)
? But how do we measure “closest”?
4 of 44 
Scan-converting a Line:  Finding the next pixel:
Scan Conversion - 10/15/13
Page 5


CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Scan Conversion
CS123
1 of 44 Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Line Drawing
? First problem statement:  Draw a line on a raster screen between two 
points
? Why is this a difficult problem?
? What is “drawing” on a raster display?
? What is a “line” in raster world?
? Efficiency and appearance are both important
Problem Statement
? Given two points P and Q in XY plane, both with integer coordinates, 
determine which pixels on a raster screen should be on in order to best 
approximate a unit-width line segment starting at P and ending at Q 
2 of 44 
Scan Converting Lines
Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
? Final step of rasterisation (process of taking geometric shapes and 
converting them into an array of pixels stored in the framebuffer to be 
displayed) – converting from “random scan”/vector specification to a 
raster scan where we specify which pixels are on (and how much) 
based on a stored array of pixels
? Takes place after clipping occurs
? All graphics packages do this at end of the rendering pipeline
? Takes triangles (or higher-order primitives) and maps them to pixels on 
screen
? For 3D rendering also takes into account other processes, like lighting 
and shading, but we’ll focus first on algorithms for line scan conversion
3 of 44 
What is Scan Conversion?
Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
Special cases:
? Horizontal Line:
? Draw pixel P and increment x coordinate value by 1 to get next pixel.
? Vertical Line:
? Draw pixel P and increment y coordinate value by 1 to get next pixel.
? Diagonal Line:
? Draw pixel P and increment both x and y coordinate by 1 to get next pixel.
? What should we do in general case?
? For slope <= 1, increment x coordinate by 1 and choose pixel on or closest to line. 
Slopes in other octants by reflection (e.g., in second octant, increment Y)
? But how do we measure “closest”?
4 of 44 
Scan-converting a Line:  Finding the next pixel:
Scan Conversion - 10/15/13
CS123 | INTRODUCTION TO COMPUTER GRAPHICS
Andries van Dam
©
? Why can we use vertical distance as 
a measure of which point (pixel 
center) is closer?
? … because vertical distance is 
proportional to actual distance
? Similar triangles show that true 
distances to line (in blue) are 
directly proportional to vertical 
distances to line (in black) for each 
point
? Therefore, point with smaller 
vertical distance to line is closest to 
line
5 of 44 
Vertical Distance
( ?? 1
, ?? 1
)
( ?? 2
, ?? 2
)
Scan Conversion - 10/15/13
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!