Courses

# 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
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!