Lecture #3

Polygon Rasterization

Computer Graphics
Winter Term 2018/19

Marc Stamminger / Roberto Grosso

What is Rasterization ?
• Given a primitive, find the pixels that cover this primitive

• Line primitive:

• Triangle primitive:

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 2

Rasterization - Primitives
• mostly, we want to fill objects → polygons

[Link]
• A polygon is defined by an ordered set of
points (for now in 2D)
𝑝𝑝1
𝑝𝑝2
𝑝𝑝5

𝑝𝑝3
𝑝𝑝4

• Every shape can be approximated by a polygon

[Link]
• Every polygon can be split into triangles
𝑝𝑝1
= Triangulation
𝑝𝑝2
𝑝𝑝5

𝑝𝑝3
Computer Graphics 2019/2020 - Rasterization of Lines and Polygons
𝑝𝑝4 3
Rasterization – Aliasing and Antialiasing
• Simple rasterization rule: set pixel if its center is inside the shape
→ strong jaggies, well visible
→ this is one form of Aliasing
→ we will come back to aliasing later

• Other rules:

average over some sample

look at pixel’s center positions within pixel compute coverage

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 4

Polygon Rasterization
• Problem statement
• Given a 2D-polygon with 𝑛𝑛 vertices 𝑃𝑃1 , … , 𝑃𝑃𝑛𝑛
• Color all pixels inside the polygon

• Idea: rasterize boundery, fill interior → seed fill algorithm

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 5

Seed-Fill Algorithm
• Start at one point (seed)
• Set it to fill color
• look at neighbor pixels:
if not set, call seed fill for these pixels recursively

• Recursive algorithm → BAD 

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 6

Seed-Fill Algorithm
• Recursive algorithm
seedfill (x,y,fillcolor)
if (color(x,y) == fillcolor)
return; //boundary reached or fillcolor already set
color(x,y) = fillcolor;
seedfill(x+1,y); //right
seedfill(x-1,y); //left
seedfill(x,y+1); //up
seedfill(x,y-1); //down

• Cons: Very deep recursion possible (requires large stack), rather inefficient

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 7

Seed-Fill Algorithm
• Example
• 1: seed point
• Recursion tree
10 9 8 7 6 5
11 12 1 2 3 4
18 13 14 15 16 17

x
x
4 x
5 x
3 6 x
7 x x
8 x x
2 9 x
10
1 11 ……

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 8

Seed-Fill Algorithm
• Apply for Polygon Rasterization:
• Draw boundary of polygon using Bresenham in unique color
• Pick a point inside
• Do seed fill from this point
• Replace unique color by desired one

• Evaluation for rasterization of polygons

• Unique color only (no shading, see later)
• How to correctly define boundary…
• and not interfere with previously drawn objects
• How to find seed position?
• Not very efficient !

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 9

Polygon Rasterization
• Better: 2D Scan Conversion
• We directly find the pixels within a polygon

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 10

Polygon Rasterization
• Brute force solution for triangles

foreach pixel (x,y)

Foreach edge E
if (x,y) on wrong side of E
continue with next pixel
set pixel (x,y)

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 11

Polygon Rasterization
• Brute force solution for triangles
• If the triangle is small, a lot of useless computation

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 12

Polygon Rasterization
• Brute force solution for triangles
• Improvement: Compute only for the screen bounding box of the triangle
foreach pixel (x,y) in bounding box
Foreach edge E
if (x,y) on wrong side of E
continue with next pixel
set pixel (x,y)

𝑋𝑋𝑚𝑚𝑚𝑚𝑚𝑚, 𝑋𝑋𝑚𝑚𝑚𝑚𝑚𝑚 , 𝑌𝑌𝑚𝑚𝑚𝑚𝑚𝑚, 𝑌𝑌𝑚𝑚𝑚𝑚𝑚𝑚 of the triangle vertices

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 13
Polygon Rasterization
• Alternative idea: scanline rasterization

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 14

Scanline Algorithm
• Idea Scanline Algorithm
• Proceed scanline by scanline from bottom to top
• Find intersections of scanline with polygon
• Fill these intersections

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 15

Scanline Algorithm
• Data Structures
• Edge table (ET)
• List of all polygon edges (upwards only!) 𝑃𝑃𝑖𝑖+1
• Content per edge 𝑦𝑦𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢
• Linked list
• Sorted by ylower Δ𝑦𝑦
𝑃𝑃𝑖𝑖
𝑦𝑦𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 Δ𝑥𝑥
• Note that 1/m is the x-increment 𝑥𝑥𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙
when stepping to above scanline

𝑦𝑦𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑥𝑥𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑦𝑦𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢 1/𝑚𝑚 = Δ𝑥𝑥/Δ𝑦𝑦 next

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 16

Scanline Algorithm
• Active Edge table (AET)
• All edges from ET that intersect current scanline
• Data per edge
• Current scanline of 𝑦𝑦𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
• Current intersection of edge with scanline: 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 , 𝑦𝑦𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
• Sorted by 𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖

𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 𝑦𝑦𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢 1/𝑚𝑚 = Δ𝑥𝑥/Δ𝑦𝑦 next

𝑃𝑃𝑖𝑖+1
𝑦𝑦𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢
𝑦𝑦𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠

𝑃𝑃𝑖𝑖
𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 17

Scanline Algorithm
• Example
• Edge table x4 − x3
y3 x3 y4 P3P4
y 4 − y3

P1 x2 − x3
y3 x3 y2 P3P2
y 2 − y3

P2 P4 x1 − x4
y4 x4 y1 P4P1
y1 − y4
yscan

P3 x1 − x2
y2 x2 y1 P2P1
x’ x’’ y1 − y2

NIL

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 18

Scanline Algorithm
• Current scanline 𝑦𝑦𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 ⇒ AET

𝑃𝑃2 𝑃𝑃4

𝑦𝑦𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠

𝑃𝑃3
𝑥𝑥𝑥 𝑥𝑥𝑥𝑥

𝑥𝑥2 − 𝑥𝑥3 𝑥𝑥3 − 𝑥𝑥4

𝑥𝑥𝑥 𝑦𝑦2 𝑥𝑥𝑥𝑥 𝑦𝑦4 NIL
𝑦𝑦2 − 𝑦𝑦3 𝑦𝑦3 − 𝑦𝑦4

𝑃𝑃3𝑃𝑃2 𝑃𝑃3𝑃𝑃4

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 19

Scanline Algorithm
• Remark on incrementing 𝑥𝑥
1
• 𝑥𝑥𝑜𝑜𝑜𝑜𝑜𝑜 = yscan − ylower + xlower
𝑚𝑚
1 1
• 𝑥𝑥𝑛𝑛𝑛𝑛𝑛𝑛 = 𝑦𝑦𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 + 1 − 𝑦𝑦𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 + 𝑥𝑥𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 = 𝑥𝑥𝑜𝑜𝑜𝑜𝑜𝑜 +
𝑚𝑚 𝑚𝑚
𝑦𝑦𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢 −𝑦𝑦𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙
• Where 𝑚𝑚 = 𝑥𝑥𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢 −𝑥𝑥𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙

1
• So the update is 𝑦𝑦 → 𝑦𝑦 + 1, 𝑥𝑥 → 𝑥𝑥 +
𝑚𝑚

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 20

Scanline Algorithm

initialize ET
set AET to empty
set yscan to ylower of first entry in ET
move all edges from ET with yscan == ylower to AET

while ET not empty or AET not empty

sort AET for x
draw lines from (AET[0].x,yscan) to (AET[1].x,yscan),
from (AET[2].x,yscan) to (AET[3].x,yscan), ……
remove all edges from AET with yscan >= yupper
for all edges in AET
x:= x + 1/m
yscan += 1
move all edges from ET with yscan == ylower to AET

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 21

Scanline Algorithm

edge ylower xlower yupper 1/m

e1 1 1 3 3

e2 1 1 7 1/2
e3
e3 4 4 7 0 e5
e4 3 7 5 -3 e2 e4

e5 4 4 5 2

e1

(0,0) x

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 22

Scanline Algorithm

y
ET: edge table, sorted on ylower

edge ylower xlower yupper 1/m Next

e1 1 1 3 3 e2

e2 1 1 7 1/2 e4 e3
e4 3 7 5 -3 e3 e5

e2 e4
e3 4 4 7 0 e5

e5 4 4 5 2 NULL
e1

(0,0) x

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 23

Scanline Algorithm
First scanline yscan = 1
AET: edge table, sorted on xintersect y

edge xinters yupper 1/m Next

e1 1 3 3 e2

e2 1 7 1/2 NULL

e3
ET: edge table, sorted on ylower e5

e2 e4
edge ylower xlower yupper 1/m Next
e4 3 7 5 -3 e3

e3 4 4 7 0 e5 e1

e5 4 4 5 2 NULL yscan

(0,0) x

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 24

Scanline Algorithm
Scanline yscan = 2
AET: edge table, sorted on xintersect y

edge xinters yupper 1/m Next

e2 3/2 7 1/2 e1

e1 4 3 3 NULL

e3
ET: edge table, sorted on ylower e5

e2 e4
edge ylower xlower yupper 1/m Next
e4 3 7 5 -3 e3

e3 4 4 7 0 e5 e1 yscan
e5 4 4 5 2 NULL

(0,0) x

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 25

Scanline Algorithm
Scanline yscan = 3
AET: edge table, sorted on xintersect y

edge xinters yupper 1/m Next

e2 2 7 1/2 e1

e4 7 5 -3 NULL

e3
ET: edge table, sorted on ylower e5

e2 e4
edge ylower xlower yupper 1/m Next
e3 4 4 7 0 e5 yscan
e5 4 4 5 2 NULL e1

(0,0) x

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 26

Scanline Algorithm
• Set pixels inside polygon to which color? → “Shading”

• We could define color gradients

US/docs/Web/SVG/Tutorial/Gradients
[Link]
• e.g. SVG linear gradients

• e.g. SVG radial gradients

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 27

Scanline Algorithm
• for our purpose, we want to define color values at the vertices of the
polygon and interpolate these
→ Gouraud Shading

• Later on, we want to interpolate

also other attributes (normals,
texture coordinates, …)

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 28

Gouraud Shading
• Interpolating intensities (or other attributes)

𝑎𝑎
• Any point 𝑝𝑝 inside the triangle 𝑎𝑎𝑎𝑎𝑎𝑎
is an affine combination of the vertices
𝛾𝛾
𝑝𝑝 = 𝛼𝛼𝛼𝛼 + 𝛽𝛽𝛽𝛽 + 𝛾𝛾𝛾𝛾
𝛽𝛽 𝑝𝑝
𝑏𝑏
with 𝛼𝛼 + 𝛽𝛽 + 𝛾𝛾 = 1 𝛼𝛼
and 0 < 𝛼𝛼, 𝛽𝛽, 𝛾𝛾 < 1
𝑐𝑐
• 𝛼𝛼, 𝛽𝛽, 𝛾𝛾 are the Barycentric Coordinates of
𝑝𝑝 with respect to triangle 𝑎𝑎𝑎𝑎𝑎𝑎

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 29

Gouraud Shading
• We can shade a point 𝑝𝑝 using its barycentric coordinates:
𝑝𝑝 = 𝛼𝛼𝛼𝛼 + 𝛽𝛽𝛽𝛽 + 𝛾𝛾𝛾𝛾

• We interpolate colors with the same weights:

𝑐𝑐𝑐𝑐𝑙𝑙𝑝𝑝 = 𝛼𝛼𝛼𝛼𝛼𝛼𝑙𝑙𝑎𝑎 + 𝛽𝛽𝛽𝛽𝛽𝛽𝑙𝑙𝑏𝑏 + 𝛾𝛾𝛾𝛾𝛾𝛾𝑙𝑙𝑐𝑐
𝑏𝑏
𝑐𝑐𝑐𝑐𝑐𝑐𝑏𝑏
→ linear interpolation

𝑝𝑝
𝑎𝑎
𝑐𝑐𝑐𝑐𝑐𝑐𝑎𝑎 𝑐𝑐𝑐𝑐𝑐𝑐𝑝𝑝 =?

𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑐𝑐
Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 30
Gouraud Shading
• Algorithmically:
• do linear interpolation of the attributes along the edges
• within a span, interpolate linearily

• This is not bilinear, but linear ! 𝑐𝑐𝑐𝑐𝑐𝑐𝑏𝑏

𝑐𝑐𝑐𝑐𝑐𝑐𝑎𝑎
𝑐𝑐𝑐𝑐𝑐𝑐1 𝑐𝑐𝑐𝑐𝑐𝑐 𝑐𝑐𝑐𝑐𝑐𝑐2
scanline

𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 31

Gouraud Shading
• Can be well combined with scanline rasterization
• with each edge, store increment of attribute when going one scanline up
• do not only update 𝑥𝑥 by 1/𝑚𝑚, but also attributes
• when rasterizing a span, compute attribute updates for 𝑥𝑥 → 𝑥𝑥 + 1
𝑐𝑐𝑐𝑐𝑐𝑐𝑏𝑏

𝑐𝑐𝑐𝑐𝑐𝑐𝑎𝑎
𝑐𝑐𝑐𝑐𝑐𝑐1 𝑐𝑐𝑐𝑐𝑐𝑐 𝑐𝑐𝑐𝑐𝑐𝑐2
scanline

𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 32

Polygon Shading
• Problems
• Shading only rotation invariant for triangles
• for more than 3 vertices: color inside polygon changes with rotation → BAD !
• Example: A
D
scanline
scanline
B C A
D

B
C

color depends on color depends on

A,B,D A,C,D

→ triangulate and rasterize triangles

→ but then the color depends on the triangulation…
Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 33
Polygon Shading
• Problem: Vertex inconsistencies
• Polygon 1 a
2
• Interpolation between a and b → c
• Polygons 2 and 3 1 c
• c is separate vertex
3

• Solution: avoid hanging nodes b

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 34

Next Lecture
• An intro to GPU rendering

Computer Graphics 2019/2020 - Rasterization of Lines and Polygons 35