Lecture #3

Line Rasterization

Computer Graphics
Winter Term 2019/20

Marc Stamminger / Roberto Grosso

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

• Triangle primitive:

• Line primitive:

Computer Graphics 2019/20 - Line Rasterization 2

Rasterization - Primitives
• Which primitives are of interest ?

• Lines:
• very widely used in CAD (computer aided design) → wireframe models

[Link]

• every curve can be approximated by lines

Computer Graphics 2019/20 - Line Rasterization 3

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/20 - Line Rasterization
𝑝𝑝4 4
Rasterization
• This lecture: Rasterization of lines (+ circles)
• Next Lecture: Rasterization of filled objects (Triangles, Polygons)

Computer Graphics 2019/20 - Line Rasterization 5

Line Drawing
• Line Rasterization
• Given: Segment endpoints (integers (𝑥𝑥0, 𝑦𝑦0), (𝑥𝑥1, 𝑦𝑦1) )
• Identify: Set of pixels (𝑥𝑥, 𝑦𝑦) that represent the line segment

(𝑥𝑥1, 𝑦𝑦1)

(𝑥𝑥0 , 𝑦𝑦0 )

Computer Graphics 2019/20 - Line Rasterization 6

Line Drawing
• An iterative version

• renders x1-x0 pixels for all lines → but length varies by 2

Computer Graphics 2019/20 - Line Rasterization 7

Line Drawing
• Doesn‘t work if slope > 1
• and for x0 > x1, …

• → differentiate cases

Computer Graphics 2019/20 - Line Rasterization 8

Line Drawing
• Incremental version – even simpler

• only one addition within loop

Computer Graphics 2019/20 - Line Rasterization 9

Line Drawing
• A recursive line rasterizer

• → for our purpose: slow, pixels may be set multiple times…

Computer Graphics 2019/20 - Line Rasterization 10

Line Drawing
• Line Rasterization: Problem statement (without anti-aliasing)

Mark all pixels touched blue pixels Better (thinnest)

by the line. Line appears should not be approximation
to be thicker considered of the line

Computer Graphics 2019/20 - Line Rasterization 11

Line Drawing
• Problem Statement
• How to draw a line from 𝑃𝑃0 = (𝑥𝑥0, 𝑦𝑦0) to 𝑃𝑃1 = (𝑥𝑥1, 𝑦𝑦1)
• Examples
• (0,0) to (6,6) Slope = 6/6

• (0,0) to (8,4) Slope = 4/8

Computer Graphics 2019/20 - Line Rasterization 12

Line Drawing
• Simplification
• Slope m: 0 < 𝑚𝑚 < 1 where 𝑚𝑚 = Δ𝑦𝑦/Δ𝑥𝑥 = (𝑦𝑦1 − 𝑦𝑦0 )/(𝑥𝑥1 − 𝑥𝑥0 )
• 𝑥𝑥0 < 𝑥𝑥 < 𝑥𝑥1: 𝑦𝑦 = 𝑦𝑦0 + 𝑚𝑚(𝑥𝑥 – 𝑥𝑥0)
• all other cases can be treated similarly

Computer Graphics 2019/20 - Line Rasterization 13

Line Drawing
Δ𝑦𝑦 𝑦𝑦1 −𝑦𝑦0
• Slope m: 0 < m < 1 where 𝑚𝑚 = =
Δ𝑥𝑥 𝑥𝑥1 −𝑥𝑥0

(𝑥𝑥1, 𝑦𝑦1)

(𝑥𝑥0, 𝑦𝑦0)

Computer Graphics 2019/20 - Line Rasterization 14

Line Drawing
• Brute force algorithm
• 𝑥𝑥0 , 𝑥𝑥1 , 𝑦𝑦0 , 𝑦𝑦1 are integers
• Direct version
float m = (float)(y1 – y0) / (x1 – x0)

for int x = x0 to x1
float y = y0 + m(x – x0)
setPixel (x, round(y))

Computer Graphics 2019/20 - Line Rasterization 15

Line Drawing
• Simple algorithm, incremental version
• Remark:
𝑦𝑦𝑛𝑛 = 𝑦𝑦0 + 𝑚𝑚 𝑥𝑥𝑛𝑛 − 𝑥𝑥0
𝑦𝑦𝑛𝑛+1 = 𝑦𝑦0 + 𝑚𝑚 𝑥𝑥𝑛𝑛 + 1 − 𝑥𝑥0 = 𝑦𝑦𝑛𝑛 + 𝑚𝑚

float m = (float)(y1 – y0)/(x1 – x0)

float y = y0
int x = x0

while (x <= x1)

setPixel(x, round(y))
x = x + 1
y = y + m

Computer Graphics 2019/20 - Line Rasterization 16

Line Drawing: Bresenham
• Bresenham-Algorithm based on // incremental line drawing
incremental version (see right) float m = (float)(y1 – y0)/(x1 – x0)
float y = y0
• goal int x = x0
• avoid float-operations
while (x <= x1)
• use integer only
setPixel(x, round(y))
• if 0 < 𝑚𝑚 < 1 and 𝑥𝑥0 < 𝑥𝑥1 : x = x + 1
• y remains either the same y = y + m
• or is increased by one

• Two cases: // Bresenham line drawing

Case 1: Case 2: int y = y0
int x = x0

while (x <= x1)

setPixel(x,y)
East North-East x = x + 1
if (some condition)
• How to decide between E and NE ? y = y + 1
Computer Graphics 2019/20 - Line Rasterization 17
Line Drawing: Bresenham
• The implicit equation for a line
𝐹𝐹 𝑥𝑥, 𝑦𝑦 = 𝑦𝑦 − 𝑦𝑦0 − 𝑚𝑚(𝑥𝑥 − 𝑥𝑥0 )

• 𝐹𝐹(𝑥𝑥, 𝑦𝑦) = 0: (𝑥𝑥, 𝑦𝑦) is on the line

𝐹𝐹 𝑥𝑥, 𝑦𝑦 > 0
• 𝐹𝐹 𝑥𝑥, 𝑦𝑦 < 0: (𝑥𝑥, 𝑦𝑦) is below the line
• 𝐹𝐹 𝑥𝑥, 𝑦𝑦 > 0: (𝑥𝑥, 𝑦𝑦) is above the line 𝐹𝐹 𝑥𝑥, 𝑦𝑦 < 0

Computer Graphics 2019/20 - Line Rasterization 18

Line Drawing: Bresenham
NE

• Midpoint decider
→ look at midpoint between E and NE pixel E
• if line below midpoint GO EAST
(𝑥𝑥 + 1, 𝑦𝑦 + 0.5)
current
• otherwise, GO NORTH-EAST NE
(𝑥𝑥, 𝑦𝑦)

• That is: // Bresenham line drawing

int y = y0
int x = x0

while (x <= x1)

setPixel(x,y)
x = x + 1
if (F(x,y+0.5) < 0)
y = y + 1

Computer Graphics 2019/20 - Line Rasterization 19

Line Drawing: Bresenham
• Performance considerations:
Making the evaluation of the decider faster
• Incremental
• Integer operation only

• But 𝐹𝐹 is rational value (𝑚𝑚 is rational)…

• But we can multiply 𝐹𝐹 with arbitrary positive value

→ get rid of denominator of 𝑚𝑚
• 𝐹𝐹 𝑥𝑥, 𝑦𝑦 = 𝑦𝑦 𝑥𝑥1 − 𝑥𝑥0 + 𝑥𝑥 𝑦𝑦0 − 𝑦𝑦1 + 𝑦𝑦1 𝑥𝑥0 − 𝑦𝑦0 𝑥𝑥1 =
Δ𝑥𝑥 𝑦𝑦 − 𝑦𝑦0 − Δ𝑦𝑦(𝑥𝑥 − 𝑥𝑥0 )

Computer Graphics 2019/20 - Line Rasterization 20

Line Drawing: Bresenham
• Incremental algorithm: Compute 𝐹𝐹 incrementally in variable 𝑑𝑑
→ First step in loop
𝑑𝑑 = 𝐹𝐹(𝑥𝑥0 + 1, 𝑦𝑦𝑦 + 1�2)
• Within loop, if 𝑑𝑑 < 0
→ NE: 𝑥𝑥0 , 𝑦𝑦0 → (𝑥𝑥0 + 1, 𝑦𝑦0 + 1)
• Next test will be at 𝑥𝑥0 + 2, 𝑦𝑦0 + 1 + 1⁄2
3
• 𝐹𝐹 𝑥𝑥0 + 2, 𝑦𝑦0 + = … = 𝐹𝐹 𝑥𝑥0 + 1, 𝑦𝑦0 + 1⁄2 + Δ𝑥𝑥 − Δ𝑦𝑦
2
• → Incremental update of d: 𝑑𝑑𝑛𝑛𝑛𝑛𝑛𝑛 = 𝑑𝑑𝑜𝑜𝑜𝑜𝑜𝑜 + Δ𝑥𝑥 − Δ𝑦𝑦

• Analog, if 𝑑𝑑 > 0
→ E: 𝑥𝑥0 , 𝑦𝑦0 → (𝑥𝑥0 + 1, 𝑦𝑦0 )
1
• Next test will be at 𝑥𝑥0 + 2, 𝑦𝑦0 +
2
1 1
• 𝐹𝐹 𝑥𝑥0 + 2, 𝑦𝑦0 + = ⋯ = 𝐹𝐹 𝑥𝑥0 + 1, 𝑦𝑦 + + (𝑦𝑦0 − 𝑦𝑦1 )
2 2

• Incremental update of d: 𝑑𝑑𝑛𝑛𝑛𝑛𝑛𝑛 = 𝑑𝑑𝑜𝑜𝑜𝑜𝑜𝑜 − Δ𝑦𝑦

Computer Graphics 2019/20 - Line Rasterization 21
Line Drawing: Bresenham
• Algorithm
int y = y0
int x
float d = F(x0+1,y0+0.5) // decider
for x = x0 to x = x1
draw_pixel(x,y)
if (d < 0) then // go NE
y = y + 1
d = d + (x1 – x0) + (y0 – y1)
else // go E
d = d + (y0 – y1)

Computer Graphics 2019/20 - Line Rasterization 22

Line Drawing: Bresenham
• Initialization of 𝐷𝐷 has a 0.5-parameter → initial value multiple of 0.5
• All other increments are integer
• → multiple with 2 → integer only
int x = x0
int y = y0
int Δx = x1 – x0
int Δy = y1 – y0
int D = Δx – 2Δy , ΔDE = -2Δy , ΔDNE = 2(Δx - Δy)

while (x <= x1)

draw_pixel(x,y)
x = x + 1
if(D < 0) {
y = y + 1
D = D + ΔDNE
}
else
D = D + ΔDE

Computer Graphics 2019/20 - Line Rasterization 23

Line Drawing: Bresenham
• handling multiple slopes: consider eight regions: octants

𝑦𝑦0 < 𝑦𝑦1 𝑦𝑦0 < 𝑦𝑦1

−∞ < 𝑚𝑚 < −1 1 < 𝑚𝑚 < ∞

𝑥𝑥1 < 𝑥𝑥0 𝑥𝑥0 < 𝑥𝑥1

-1 ≤ 𝑚𝑚 ≤ 0 0 ≤ 𝑚𝑚 ≤ 1

𝑥𝑥1 < 𝑥𝑥0 𝑥𝑥0 < 𝑥𝑥1

0 ≤ 𝑚𝑚 ≤ 1 -1 ≤ 𝑚𝑚 ≤ 0

𝑦𝑦1 < 𝑦𝑦0 𝑦𝑦1 < 𝑦𝑦0

1 < 𝑚𝑚 < ∞ −∞ < 𝑚𝑚 < −1

Computer Graphics 2019/20 - Line Rasterization 24

Line Drawing: Bresenham
• Remark: negative slopes
• update on 𝑦𝑦 is different
• if line above midpoint update to (𝑥𝑥 + 1, 𝑦𝑦)
• otherwise update to (𝑥𝑥 + 1, 𝑦𝑦 − 1)
• update on decision variable is subtly different:
1 3
𝐹𝐹 𝑥𝑥 + 1, 𝑦𝑦 + > 0 ⇒ goto (𝑥𝑥 + 1, 𝑦𝑦 − 1) and next test at 𝑥𝑥 + 2, 𝑦𝑦 −
2 2
1 1
𝐹𝐹 𝑥𝑥 + 1, 𝑦𝑦 + ≤ 0 ⇒ goto 𝑥𝑥 + 1, 𝑦𝑦 and next test at (𝑥𝑥 + 2, 𝑦𝑦 − )
2 2

Computer Graphics 2019/20 - Line Rasterization 25

Line Drawing: Bresenham
• One possible strategy
• If 𝑚𝑚 > 1: swap coordinates, i.e. 𝑥𝑥 ↔ 𝑦𝑦
• if 𝑥𝑥0 > 𝑥𝑥1 : swap start and end points
• if 𝑚𝑚 < 0: set step in 𝑦𝑦 to be −1
• use Δ𝑥𝑥 = 𝑥𝑥1 – 𝑥𝑥0 and Δ𝑦𝑦 = |𝑦𝑦1 – 𝑦𝑦0|

Computer Graphics 2019/20 - Line Rasterization 26

Line Drawing
• Problems:
• The length of a line is measured in screen units = pixels
• Ideally: number of pixels of scan-converted line equal length
• If line longer than no. of pixels, it looks fragmented
• Bresenham algorithm generates number of pixels = max(Δ𝑥𝑥, ∆𝑦𝑦)
• Assume 𝑚𝑚 < 1
number of pixels = 𝐿𝐿 cos 𝛼𝛼
where 𝐿𝐿 length of line

𝐿𝐿
Δ𝑦𝑦
𝛼𝛼

Δx

Computer Graphics 2019/20 - Line Rasterization 27

Line Drawing: antialiasing
• Problems
• Line intensity varies with slope

Horizontal line: Diagonal line:

1 pixel / unit length 1/ 2 pixel / unit length

1
→ on grey scale screen: modify intensity by 2 cos 𝛼𝛼

Computer Graphics 2019/20 - Line Rasterization 28

Line Drawing: antialiasing
• “Jaggies” → typical aliasing artifact
• In the original Bresenham, only one pixel is
drawn per incremental step. The desired
intensity (here: black) is entirely assigned to
that pixel.
• Can also result in patterns
→ Moire effect (Wikipedia)

Computer Graphics 2019/20 - Line Rasterization 29

Line Drawing: antialiasing
• Antialiased Bresenham
• With antialiasing, (up to) two pixels are drawn per incremental step (and column).
The intensity of these pixels sums up to the desired intensity.

Computer Graphics 2019/20 - Line Rasterization 30

Line Drawing: antialiasing
• In order to decide which pixels we should draw and how to choose the
weighting factors, we need the signed distance 𝑎𝑎 between the true line and
the midpoint between the E- and the NE-pixel.

The distance can be computed

from the decision variable 𝑑𝑑:
𝑎𝑎
𝑑𝑑
𝑎𝑎 =
2Δ𝑥𝑥

Computer Graphics 2019/20 - Line Rasterization 31

Line Drawing: antialiasing
• Which pixels should be drawn?
• Case 𝑑𝑑 ≥ 0 (choose E)

𝑎𝑎 < 0.5 𝑎𝑎 > 0.5

draw pixels: draw pixels:
(𝑥𝑥 + 1, 𝑦𝑦) with intensity factor 1 − |𝑎𝑎 + 0.5| (𝑥𝑥 + 1, 𝑦𝑦) with intensity factor 1 − |𝑎𝑎 + 0.5|
(𝑥𝑥 + 1, 𝑦𝑦 + 1) with intensity factor |𝑎𝑎 + 0.5| (𝑥𝑥 + 1, 𝑦𝑦 − 1) with intensity factor |𝑎𝑎 + 0.5|

Computer Graphics 2019/20 - Line Rasterization 32

Line Drawing: antialiasing
• Case d < 0 (choose NE)

𝑎𝑎 > −0.5 𝑎𝑎 < −0.5

draw pixels: draw pixels:
(𝑥𝑥 + 1, 𝑦𝑦 + 1) with intensity 1 − |𝑎𝑎 − 0.5| (𝑥𝑥 + 1, 𝑦𝑦 + 1) with intensity 1 − |𝑎𝑎 − 0.5|
(𝑥𝑥 + 1, 𝑦𝑦) with intensity |𝑎𝑎 − 0.5| (𝑥𝑥 + 1, 𝑦𝑦 + 2) with intensity |𝑎𝑎 − 0.5|

Computer Graphics 2019/20 - Line Rasterization 33

Further Reading - Circle Drawing
• Circle
• Center 𝑐𝑐 = (𝑥𝑥𝑐𝑐 , 𝑦𝑦𝑐𝑐 )
• Circle of radius 𝑟𝑟
𝑥𝑥 − 𝑥𝑥𝑐𝑐 2 + 𝑦𝑦 − 𝑦𝑦𝑐𝑐 2 = 𝑟𝑟2
• For now:
• Center at (0,0)

• Eight-fold symmetry
• 1st octant: 0 ≤ 𝑦𝑦 < 𝑥𝑥
• 2nd octant: 0 <= 𝑥𝑥 < 𝑦𝑦
• 3rd octant: 0 <= −𝑥𝑥 < 𝑦𝑦
• 4th octant: 0 <= 𝑦𝑦 < −𝑥𝑥
• 5th octant: 0 <= −𝑦𝑦 < −𝑥𝑥
• 6th octant: 0 <= −𝑥𝑥 < −𝑦𝑦
• 7th octant: 0 <= 𝑥𝑥 < −𝑦𝑦
• 8th octant: 0 <= −𝑦𝑦 < 𝑥𝑥

Computer Graphics 2019/20 - Line Rasterization 34

Further Reading - Circle Drawing
• Draw pixels using the 8-fold symmetry
add offset 𝑐𝑐 = (𝑥𝑥𝑐𝑐 , 𝑦𝑦𝑐𝑐 ) to center circle at (𝑥𝑥𝑐𝑐 , 𝑦𝑦𝑐𝑐 )

// The pixel (x,y) is in the 2nd octant

void draw8pixel(xc,yc,x,y)
{
draw_pixel(xc+x,yc+y); // (x,y) 2nd octant
draw_pixel(xc+y,yc+x); // 1st octant
draw_pixel(xc-x,yc+y); // 3rd octant
draw_pixel(xc-y,yc+x); // 4th octant
...
}

Computer Graphics 2019/20 - Line Rasterization 35

Further Reading - Circle Drawing
• The 2nd octant: 𝑚𝑚 < 0; 𝑚𝑚 < 1; 0 < 𝑥𝑥 < 𝑦𝑦
• The implicit function
𝐹𝐹 𝑥𝑥, 𝑦𝑦 = 𝑥𝑥 − 𝑥𝑥𝑐𝑐 2 + 𝑦𝑦 − 𝑦𝑦𝑐𝑐 2 − 𝑟𝑟 2
• The circle
𝑥𝑥 ∈ ℝ2 : 𝐹𝐹 𝑥𝑥, 𝑦𝑦 = 0
• Properties 2nd octant

• 𝐹𝐹 𝑥𝑥, 𝑦𝑦 > 0 → (𝑥𝑥, 𝑦𝑦) is outside/above the circle

𝐹𝐹 𝑥𝑥, 𝑦𝑦 > 0
• 𝐹𝐹 𝑥𝑥, 𝑦𝑦 ≤ 0 → (𝑥𝑥, 𝑦𝑦) is inside/below the circle

𝐹𝐹(𝑥𝑥, 𝑦𝑦) < 0

Computer Graphics 2019/20 - Line Rasterization 36

Further Reading - Circle Drawing
• The decider variable
• 𝑑𝑑 = 𝐹𝐹(𝑥𝑥 + 1, 𝑦𝑦 − 1/2)
• The increment
• 𝑑𝑑 > 0 ((𝑥𝑥, 𝑦𝑦) outside the circle)
• (𝑥𝑥, 𝑦𝑦) → (𝑥𝑥 + 1, 𝑦𝑦 − 1)
• 𝑑𝑑 < 0 ((𝑥𝑥, 𝑦𝑦) inside the circle)
• (𝑥𝑥, 𝑦𝑦) → (𝑥𝑥 + 1, 𝑦𝑦)

Computer Graphics 2019/20 - Line Rasterization 37

Further Reading - Circle Drawing
• The increment of the decider variable
• Set 𝑑𝑑 = 𝐹𝐹(𝑥𝑥 + 1, 𝑦𝑦 − 1/2)
• Case 𝑑𝑑 < 0; next test at (𝑥𝑥 + 2, 𝑦𝑦 − 1/2)
1 1
• 𝐹𝐹 𝑥𝑥 + 2, 𝑦𝑦 − − 𝐹𝐹 𝑥𝑥 + 1, 𝑦𝑦 − = ⋯ = 2𝑥𝑥 + 3
2 2
• ⇒ 𝑑𝑑 = 𝑑𝑑 + 2𝑥𝑥 + 3
3
• Case 𝑑𝑑 > 0; next test at 𝑥𝑥 + 2, 𝑦𝑦 −
2
3 1
• 𝐹𝐹 𝑥𝑥 + 2, 𝑦𝑦 − − 𝐹𝐹 𝑥𝑥 + 1, 𝑦𝑦 − = ⋯ = 2 𝑥𝑥 − 𝑦𝑦 + 5
2 2
• ⇒ 𝑑𝑑 = 𝑑𝑑 + 2(𝑥𝑥 – 𝑦𝑦) + 5

Computer Graphics 2019/20 - Line Rasterization 38

Further Reading - Circle Drawing
• The increment of the decider variable
• The increment of d depends on the position (𝑥𝑥, 𝑦𝑦)
• Introduce new variables 𝐸𝐸 and 𝑆𝑆𝑆𝑆 (E: east, SE: south east)
𝐸𝐸 = 2𝑥𝑥 + 3; 𝑆𝑆𝑆𝑆 = 2 𝑥𝑥 – 𝑦𝑦 + 5
• 𝐸𝐸 and 𝑆𝑆𝑆𝑆 can be computed incrementally
→ incrementally compute the increment
• If 𝑑𝑑 < 0: 𝑑𝑑 = 𝑑𝑑 + 𝐸𝐸; 𝐸𝐸 = 𝐸𝐸 + 2; 𝑆𝑆𝑆𝑆 = 𝑆𝑆𝑆𝑆 + 2
• If 𝑑𝑑 > 0: 𝑑𝑑 = 𝑑𝑑 + 𝑆𝑆𝑆𝑆; 𝐸𝐸 = 𝐸𝐸 + 2; 𝑆𝑆𝑆𝑆 = 𝑆𝑆𝑆𝑆 + 4

Computer Graphics 2019/20 - Line Rasterization 39

Further Reading - Circle Drawing
• Remarks
• Use 𝑑𝑑 = 𝐹𝐹(𝑥𝑥 + 1, 𝑦𝑦 – ½) – ¼
• Use only integer precision, 𝑥𝑥, 𝑦𝑦 and 𝑟𝑟 are taken to be ints

Computer Graphics 2019/20 - Line Rasterization 40

Further Reading - Circle Drawing
// Bresenham. 77
void Bresenham_Circle(xc,yc,r)
{
x = 0; y = r;
d = 1 – r; e = 3; se = 5 – 2*r;
do {
draw8pixel(xc,yc,x,y);
if d < 0 then
d = d + e;
e = e + 2;
se = se + 2;
x = x + 1;
else
d = d + se;
e = e + 2;
se = se + 4;
x = x + 1;
y = y - 1;
} while (x <= y)
}

Computer Graphics 2019/20 - Line Rasterization 41

Next Lecture
• Polygon Rasterization

Computer Graphics 2019/20 - Line Rasterization 42