02 Rasterization

Prévia do material em texto

Universidade Federal da Paraíba
Centro de Informática
Rasterization
Lecture 2
1107190 - Introdução à Computação Gráfica – Turma 01
Prof. Christian Azambuja Pagot
CI / UFPB
2Universidade Federal da Paraíba
Centro de Informática
Vector Display
Søren Peo Pedersen (Wikipedia)
1. Deflection voltage eletrode.
2. Electron gun.
3. Electron beam.
4. Focusing coil.
5. Phosphor-coated inner side of the screen.
3Universidade Federal da Paraíba
Centro de Informática
Vector Graphics
Vectrex video game (video)
Blakespot (Flickr)
4Universidade Federal da Paraíba
Centro de Informática
Raster Displays
Gabelstaplerfahrer 
(Wikipedia)
LCD Display Plasma Display
Jari Laamanen
(Wikipedia)
Søren Peo Pedersen (Wikipedia)
CRT Display
1. Three Electron guns.
2. Electron beams.
3. Focusing coils.
4. Deflection coils.
5. Anode connection.
6. Mask for separating beams.
7. Phosphor layer.
8. Close-up of the phosphor-coated inner side of the screen.
5Universidade Federal da Paraíba
Centro de Informática
Raster Display
Gona.eu (Wikipedia)
6Universidade Federal da Paraíba
Centro de Informática
Raster Graphics
Jet 2 (1987) (video)
Sublogic
Video by oldclassicgame (youtube.com)
7Universidade Federal da Paraíba
Centro de Informática
Video Memory
RAM
... ...
0 1 2 nn-1
...
Vídeo Memory (VRAM)
Vídeo Onboard
byte / word
8Universidade Federal da Paraíba
Centro de Informática
Video Memory
... ...
0 1 2 nn-1
...
Vídeo Memory (VRAM)
Vídeo Offboard
Vídeo Card
byte / word
How about 
colors?
9Universidade Federal da Paraíba
Centro de Informática
Colors (Quick view)
● Electromagnetic spectrum
Visible spectrum
Image by penubag (Wikipedia)
10Universidade Federal da Paraíba
Centro de Informática
Colors (Quick view)
● CIE Color Space (1931)
● CIE RGB Color Space
Normally used
in computers!
Image by BenRG (Wikipedia)
11Universidade Federal da Paraíba
Centro de Informática
RGB Representation
● The intensity of each component is represented by a 
number.
● Usually, 8 bits are reserved for each component 
(channel). Thus, each component can present up to 
256 levels of intensity (2563 = ~16 millions of colors).
● An additional channel (alpha) can be used for 
transparency (RGBA).
● It's not uncommon to have different number of bits 
per channel.
12Universidade Federal da Paraíba
Centro de Informática
Screen
Image Storage
0 1 2 3 4 5 6 7
Pixel (0,0)
(4 bytes)
Pixel (0,1)
(4 bytes)
Color buffer
R G B R G B A R G B A...A
i * 4+3
Pixel (0,i)
(4 bytes)i * 4+2
i * 4+1
i * 4+0
Line 0
13Universidade Federal da Paraíba
Centro de Informática
Image Storage
Line 0
Line 1
Line 2
Line 3
Line 4
Line h-2
Line h-1
h lines
(height)
w columns
(width)
C
ol
um
n 
0
C
ol
um
n 
1
C
ol
um
n 
2
C
ol
um
n 
3
C
ol
um
n 
4
C
ol
um
n 
w
-1
C
ol
um
n 
w
-2 # pixels = w * h
14Universidade Federal da Paraíba
Centro de Informática
Image Storage
Color buffer
Line 1 Line 2 Line 3 Line n
Line 0
Line 1
Line 2
Line 3
Line 4
Line h-2
Line h-1
Pixel = (x,y)
Offset = x*4 + y*w*4
W ( # columns)
15Universidade Federal da Paraíba
Centro de Informática
Image Storage
● Vídeo memory screen image footprint:
Color buffer
Depth buffer
Auxiliar buffer 1
Auxiliar buffer 2
Auxiliar buffer n
...Fra
m
e 
bu
ffe
r
Ví
de
o 
M
em
or
y
Screen Image
16Universidade Federal da Paraíba
Centro de Informática
Rasterization
● “Approximation of mathematical ('ideal') 
primitives, described in terms of vertices on a 
Cartesian grid, by sets of pixels of the 
appropriate intensity of gray or color.” 
- Foley et. al
17Universidade Federal da Paraíba
Centro de Informática
Rasterization
Pixel
ScreenX
Y
18Universidade Federal da Paraíba
Centro de Informática
Rasterization
Pixel center
Screen
Pixel
X
Y
19Universidade Federal da Paraíba
Centro de Informática
Rasterizing Lines
∆y
∆x
X
Y
1st point: (x
0
, mx
0
+ b))
2nd point: (x
1
, mx
1
+ b))
3rd point: (x
2
, mx
2
+ b))
. 
. 
.
nth point: (x
n
, mx
n
+ b))
m= Δ y
Δ x
y i=mx i+b
Since ∆x is greater ∆y:
By incrementing x by 1, we can 
compute the corresponding y:
20Universidade Federal da Paraíba
Centro de Informática
Rasterizing Lines
∆y
∆x
X
Y
1st point: (x
0
, Round(mx
0
+ b))
2nd point: (x
1
, Round(mx
1
+ b))
3rd point: (x
2
, Round(mx
2
+ b))
. 
. 
.
nth point: (x
n
, Round(mx
n
+ b))
m= Δ y
Δ x
y i=mx i+b
Since ∆x is greater ∆y:
By incrementing x by 1, we can 
compute the corresponding y:
21Universidade Federal da Paraíba
Centro de Informática
Rasterizing Lines
● Problems with this approach: 
– At each iteration: 
● A floating point multiplication.
● A floating point addition.
● A Round operation.
nth point: (x
n
, Round(mx
n
+ b))
22Universidade Federal da Paraíba
Centro de Informática
Rasterizing Lines
● Solution:
– Multiplication can be eliminated:
– If ∆x = 1:
y i+1=m(x i+Δ x)+b
y i+1=m x i+1+b
y i+1= y i+mΔ x
y i+1= y i+m
This is an incremental 
algorithm.
Usually referred as the DDA 
(digital differential analyzer) 
algorithm.
23Universidade Federal da Paraíba
Centro de Informática
● Incremental.
● Avoids multiplications and roundings.
● Can be generalized for circles.
Bresenham Line Algorithm
24Universidade Federal da Paraíba
Centro de Informática
Variation of Bresenham's Algor.
line
X
Y
25Universidade Federal da Paraíba
Centro de Informática
+ + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + +
+ + + + + + + + + + + + + + +
+ + + + + + + + + ­ ­ ­ ­ ­ ­
+ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
Variation of Bresenham's Algor.
X
Y
m (midpoint)
line
ne
e
Φ(x , y )=α x+β y+γ=0
y=(Δ yΔ x ) x+b
y=mx+b
Φ(x , y )=Δ y⋅x−Δ x⋅y+b⋅Δ x=0
d=Φ(m )→Decision variable
e=(xc+1, yc)
ne=(xc+1, yc+1)
m=( xc+1, yc+
1
2 )
if (d < 0)
next pixel = ne
else
next pixel = e
Assuming that 0 ≤ m ≤ 1:
c
Will we have 
to evaluate
a polynomial 
every pixel?
α = Δ y
β = −Δ x
γ = b⋅Δ x
c=(xc , y c)
x
c
y
c
1
e
26Universidade Federal da Paraíba
Centro de Informática
Variation of Bresenham's Algor.
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
+ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
X
Y
line
c e ?
?
If E is choosen:
dnew=α(xc+2)+β( yc+
1
2 )+γ
dold=α(xc+1)+β( yc+
1
2 )+γ
dnew−dold→dnew=dold+α
Φ(x , y )=α x+β y+γ
α = Δ y
β = −Δ x
γ = b⋅Δ x
Remembering...
m
old
m
new
dold=Φ(m old)=Φ((xc+1, yc+
1
2 ))
dnew=Φ(mnew)=Φ((xc+2, yc+
1
2 ))
27Universidade Federal da Paraíba
Centro de Informática
Variation of Bresenham's Algor.
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + + + + 
+ + + + + + + + + + + + + + + + + + + + ­ ­ ­
+ + + + + + + + + + + + + + + + + ­ ­ ­ ­ ­ ­
+ + + + + + + + + + + + + + + ­ ­ ­ ­ ­ ­ ­ ­
+ + + + + + + + + + + + ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
+ + + + + + + + + + ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
+ + + + + + + ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
+ + + + + ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
+ + ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­ ­
X
Y
line
c
ne
If NE is choosen:
dnew=α(xc+2)+β( yc+
3
2 )+γ
dold=α(xc+1)+β( yc+
1
2 )+γ
dnew−dold→dnew=dold+α+β
?
?
Φ(x , y )=α x+β y+γ
α = Δ y
β = −Δ x
γ = b⋅Δ x
Remembering...
dold=Φ(m old)=Φ((xc+1, yc+
1
2 ))
dnew=Φ(mnew)=Φ((xc+2, yc+
3
2 ))
m
old
m
new
28Universidade Federal da Paraíba
Centro de Informática
Variation of Bresenham's Algor.
● How about the 1st pixel (there is no D
old
!)?
line
X
Y
x
0
y
0
d=Φ(m )=α( x0+1)+β( y0+
1
2 )+γ
d=Φ(c)+α+ β
2
d=Δ y−Δ x2
Φ(x , y )=0=2⋅0=2Φ( x , y )=2(α x+β y+γ)
Φ(c)=0
d=α+β
2
α = Δ y
β = −Δ x
γ = b⋅Δ x
d=2Δ y−Δ x
m
d=Φ(m)
=Φ((x0+1, y0+
1
2 ))
29Universidade Federal da Paraíba
Centro de Informática
Variation of Bresenham's Algor.
● The entire algoritm for 0 < m < 1:
MidPointLine() {
int dx = x1 – x0;
int dy = y1 – x0;
int d = 2 * dy – dx;
int incr_e = 2 * dy;
int incr_ne = 2 * (dy – dx);
int x = x0;
int y = y0;
PutPixel(x, y, color) 
while (x < x1) {
if (d <= 0) {
d += incr_e;
x++;
} else {
d += incr_ne;
x++;
y++;
}
PutPixel(x, y, color);
}
}
Computer Graphics: Principles and Practice. Foley et al.
The computation of d, now, 
involves only addition!
Slopes outside the range [0,1]
can be handled by symmetry!
30Universidade Federal da Paraíba
Centro de Informática
Other Rasterization Issues
● How about?
– Other primitives:
● Circles.
● Ellipses.
● Triangles.
– Thick lines.
– Shape of the endpoints.
– Antialiasing.
– Line stile.
– Filling.
– Etc.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30