04 - Polygon Rasterization
04 - Polygon Rasterization
04 - Polygon Rasterization
Polygon Rasterization
Computer Graphics
Winter Term 2018/19
• Line primitive:
• Triangle primitive:
autodesk.com
• A polygon is defined by an ordered set of
points (for now in 2D)
𝑝𝑝1
𝑝𝑝2
𝑝𝑝5
𝑝𝑝3
𝑝𝑝4
autodesk.com
• 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:
• Cons: Very deep recursion possible (requires large stack), rather inefficient
x
x
4 x
5 x
3 6 x
7 x x
8 x x
2 9 x
10
1 11 ……
𝑃𝑃𝑖𝑖+1
𝑦𝑦𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢𝑢
𝑦𝑦𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
𝑃𝑃𝑖𝑖
𝑥𝑥𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖
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
𝑃𝑃2 𝑃𝑃4
𝑦𝑦𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠
𝑃𝑃3
𝑥𝑥𝑥 𝑥𝑥𝑥𝑥
𝑃𝑃3𝑃𝑃2 𝑃𝑃3𝑃𝑃4
1
• So the update is 𝑦𝑦 → 𝑦𝑦 + 1, 𝑥𝑥 → 𝑥𝑥 +
𝑚𝑚
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
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
y
ET: edge table, sorted on ylower
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
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
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
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
US/docs/Web/SVG/Tutorial/Gradients
https://developer.mozilla.org/en-
• e.g. SVG linear gradients
𝑎𝑎
• 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 30
Gouraud Shading
• Algorithmically:
• do linear interpolation of the attributes along the edges
• within a span, interpolate linearily
𝑐𝑐𝑐𝑐𝑐𝑐𝑎𝑎
𝑐𝑐𝑐𝑐𝑐𝑐1 𝑐𝑐𝑐𝑐𝑐𝑐 𝑐𝑐𝑐𝑐𝑐𝑐2
scanline
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
𝑐𝑐𝑐𝑐𝑐𝑐𝑎𝑎
𝑐𝑐𝑐𝑐𝑐𝑐1 𝑐𝑐𝑐𝑐𝑐𝑐 𝑐𝑐𝑐𝑐𝑐𝑐2
scanline
𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐
B
C