aft CS7.
302
Basics of Computer Graphics
Module: Rasterization Module
Dr
Avinash Sharma
Spring 2021
CS7.302
(Point) Pipeline in Action
World
Coord
aftModelView
Camera
Coord
Projection
Canonical
Coord
Viewport
Window
Coord
I Points are transformed from Object to World to Canonical to Window
Dr
coordinates.
I Each 3D point maps to a pixel (i, j) in the window space.
I Lines are made out of two points. Triangles and polygons are made out
of 3 or more points.
CS7.302
Lines in Action
I
aft
Lines are rasterized to the pixel
grid of the window.
I Find pixels that lie closest to the
line. Results in aliasing.
Dr
I Each pixel needs to be given a
color and depth.
CS7.302
Clipping Lines
I
aft
End points map to window
coordinates independently.
I World lines needn’t map nicely
Dr
onto points inside the window.
CS7.302
Clipping Lines
I
aft
End points map to window
coordinates independently.
World lines needn’t map nicely
onto points inside the window.
Dr
I Clipping: Finding part of the
line that is inside the window.
I Clip first and then rasterize.
CS7.302
Triangles in Action
I
aft
Un-filled triangles are
uninteresting. Filled ones
represent surfaces.
I Triangles are scan converted or
rasterized to include all pixels
Dr
inside it.
I Each pixel needs to have a
colour and depth.
CS7.302
Clipping Triangles
I
aft
Only parts of the triangle may lie
in the window.
I First clip a triangle to a (planar!)
polygon that lies inside.
Dr
I Scan convert the polygon
subsequently.
CS7.302
Primitive Pipeline
Vertex/Point
aft
Vertex Processing
Primitive Assembly
I
I
From points, lines, triangles/polygons
Vertex stage: process vertices
independently
I Primitive stage: triangle assembly
Dr
I Rasterization: Clip & Determine the
Rasterization pixels inside the primitive
I Pixel stage: process each pixel
independently
Pixel Processing
Frame Buffer
CS7.302
Linear Interpolation of Properties
I
aft
Each pixel needs: colour, depth, and texture coordinate.
Assumption: Properties vary linearly across the plane.
If we know the colour, texture coordinate, and depth at the vertices of
the polygon (or line), these can be interpolated to pixels on the inside
linearly!
Dr
I Colour: 3-vector, texture coord: 2-vector, depth: scalar.
I Rasterization step interpolates these values and gives to each pixel.
I Is the interpolation valid?
CS7.302
Vertex Processing
I
aft
Apply ModelView and Projection matrices to the vertex
Find/send colour: either given or compute from physics!
I Find/send texture coordinates: usually given
I Find/send normals: usually given.
Dr
I Can process vertices of a primitive independently
I Modern GPUs: This stage is programmable! Can write own vertex
shader to replace the standard processing.
CS7.302
Rasterization
I
aft
Apply viewport transformation.
Clip primitive to the window or the viewport.
Evaluate which pixels are part of the primitive.
I Interpolate values for each pixel and queue the pixels or fragments for
Dr
further processing.
I This is computationally quite expensive and is usualy done by a
dedicated hardware unit.
I A queue of fragments with associated data are built by this stage.
CS7.302
Pixel or Fragment Processing
I
aft
The pixels generated by the rasterization stage are processed in
arbitrary order by this stage.
Depth value is available already. Can look up Z-buffer to keep or discard
the fragment.
I Interpolated colour value can be sent to frame buffer.
Dr
I Texture image can be accessed using the texture coordinates. The final
colour can be a combination of interpolated and texture colours.
I Modern GPUs: This stage is programmable! Can write own fragment
shader to replace the standard processing.
CS7.302
Programmable GPUs
I
aft
Graphics Processing Units are programmable today
Novel shading and lighting can be performed by writing appropriate
vetex and pixel shaders, beyond OpenGL
I GPUs used parallel processing with 2-4 vertex and 32-64 pixel
processing units, all working in parallel. Together, considerable
Dr
computing power was in a GPU
I Clever idea: Use the power for other processing: matrix multiplication,
FFT, sorting, image processing, etc.
I GPGPU: General Processing on GPUs
CS7.302
Primitive Pipeline: Summary
Vertex/Point
I
aft
Basic primitives: Points, Lines,
Triangles/Polygons.
Vertex Processing
I Each constructed fundamentally from points. Primitive Assembly
I Points map to pixels on screen. Primitives are
Dr
assembled from points.
Rasterization
I Pipeline of operations on a primitive finds the
pixels that are part of it. And performs a few
operations on each pixel
Pixel Processing
Frame Buffer
CS7.302
Scan Conversion or Rasterization
I
aft
Primitives are defined using points, which have been mapped to the
screen coordinates.
In vector graphics, connect the points using a pen directly.
I In Raster Graphics, we create a discretized image of the whole screen
Dr
onto the frame buffer first. The image is scanned automatically onto the
display periodically.
I This step is called Scan Conversion or Rasterization.
CS7.302
Scan Converting a Point
I
aft
The 3D point has been transformed to its screen coordinates (u, v).
Round the coordinates to frame buffer array indices (i, j).
Current colour is defined/known. Frame buffer array is initialized to the
background colour.
Dr
I Perform: frameBuf[i, j] currentColour
I Function WritePixel(i, j, colour) does the above.
I If PointSize > 1, assign the colour to a number of points in the
neighbourhood!
CS7.302
Scan Converting a Line
I
aft
Identify the grid-points that lie on the line and colour them.
Problem: Given two end-points on the grid, find the pixels on the line
connecting them.
Dr
I Incremental algorithm or Digital Differential Analyzer (DDA) algorithm.
I Mid-Point Algorithm
CS7.302
Line on an Integer Grid
aft
Dr
CS7.302
Incremental Algorithm
x
x
aft
Function DrawLine(x1 , y1 , x2 , y2 , colour)
x2 x1 , y
x1 , y y1
While (x < x2 )
y2 y1 , slope y/ x
WritePixel (x, round(y), colour)
x x + 1, y y + slope
Dr
EndWhile
WritePixel (x2 , y2 , colour)
EndFunction
CS7.302
Incremental Algorithm With Integers
x
aft
Function DrawLine(x1 , y1 , x2 , y2 , colour)
x2 x1 , y
While (x < x2 )
y2 y1 , sl
WritePixel (x, y, colour)
0, x x1 , y y1
x x + 1, sl += y.
if (sl x) {y y + 1, sl -= x}
Dr
EndWhile
WritePixel (x2 , y2 , colour)
EndFunction
CS7.302
Points to Consider
I
aft
If abs(slope) > 1, step through y values, adding inverse slopes to x at
each step.
I Simple algorithm, easy to implement.
I Floating point calculations were expensive once!
Dr
I Can we do with integer arithmetic only?
Yes: Bresenham’s Algorithm, Mid-Point Line Algorithm.
CS7.302
Two Options at Each Step!
aft
NE
Dr
M
E
CS7.302
Mid-Point Line Algorithm
I
aft
Line equation: ax + by + c = 0, a > 0.
Let 0 < slope = y/ x = a/b < 1.0
F(x, y) = ax + by + c > 0 for below the line, < 0 for above.
I NE if d = F(M) > 0; E if d < 0; else any!
I dE = F(ME ) = d + a, dNE = d + a + b
Dr
I Therefore, E = a, NE =a+b
I Initial value: d0 = F(x1 + 1, y1 + 12 ) = a + b /2
I Similar analysis for other slopes. Eight cases in total.
CS7.302
Pseudocode
d
aft
Function DrawLine (x1 , y1 , x2 , y2 , colour)
a (y2 y1 ), b
2a + b, E
While (x < x2 )
(x1 x2 ), x
2a, NE
x1 , y
2(a + b)
y1
WritePixel(x, y, colour)
if (d < 0) // East
d d + E, x x+1
Dr
else // North-East
d d + NE , x x + 1, y y+1
EndWhile
WritePixel(i, j, colour)
EndFunction
CS7.302
Example: (10, 10) to (20, 17)
aft
F(x, y) = 7x 10y + 30, a = 7, b = 10
d0 = 2 ⇤ 7 10 = 4, E = 2 ⇤ 7 = 14, NE =
d > 0 : NE (11, 11), d = 4 + 6 = 2
6
d < 0 : E (12, 11), d = 2 + 14 = 12
d > 0 : NE (13, 12), d = 12 + 6 = 6
Dr
d > 0 : NE (14, 13), d = 6 + 6 = 0
d = 0 : E (15, 13), d = 0 + 14 = 14
d > 0 : NE (16, 14), d = 14 + 6 = 8
Later, NE (17, 15), NE (18, 16), E (19, 16), NE (20, 17).
CS7.302
Patterned Line
I
aft
Represent the pattern as an array of booleans/bits, say, 16 pixels long.
Fill first half with 1 and rest with 0 for dashed lines.
I Perform WritePixel(x, y) only if pattern bit is a 1.
Dr
if (pattern[i]) WritePixel(x, y)
where i is an index variable starting with 0 giving the ordinal number
(modulo 16) of the pixel from starting point.
CS7.302
Shared Points/Edges
I
aft
It is common to have points common between two lines and edges
between two polygons.
I They will be scan converted twice. Not efficient. Sometimes harmful.
I Solution: Treat the intervals closed on the left and open on the right.
Dr
[xm , xM ) & [ym , yM )
I Thus, edges of polygons on the top and right boundaries are not drawn.
CS7.302
aft
Dr
CS7.302
Clipping
I
aft
Often, many points map to outside the range in the normalized 2D
space.
Think of the FB as an infinite canvas, of which a small rectangular
portion is sent to the screen.
Dr
I Let’s get greedy: draw only the portion that is visible. That is, clip the
primitives to a clip-rectangle.
I Scissoring: Doing scan-conversion and clipping together.
CS7.302
Clipping Points
I
aft
Clip rectangle: (xm , ym ) to (xM , yM ).
For (x, y): xm x xM , ym y yM
I Can use this to clip any primitives: Scan convert normally. Check above
condition before writing the pixel.
Dr
I Simple, but perhaps we do more work than necessary.
I Analytically clip to the rectangle, then scan convert.
CS7.302
Clipping Lines
aft
Dr
Popular: Cohen-Sutherland Algorithm
CS7.302
