Aula_12_Rasterizacao_Triangulos

Prévia do material em texto

Rasterização
Triângulos
Prof. Eduardo Gastal
eslgastal@inf.ufrgs.br
INF01047 – 2017/1
Pipeline Gráfico (Rasterização)
2
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Model & View
Vertex Shading
Projection
Clipping
Screen Mapping
(Viewport)
Pipeline Gráfico (Rasterização)
3
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Model & View
Vertex Shading
Projection
Clipping
Screen Mapping
(Viewport)
Pipeline Gráfico (Rasterização)
4
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Fragment
Generation
Fragment
Shading
Visibility
Pipeline Gráfico (Rasterização)
5
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Fragment
Generation
Fragment
Shading
Visibility
Pipeline Gráfico (Rasterização)
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Fragment
Generation
Fragment
Shading
Visibility
Pipeline Gráfico (Rasterização)
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Fragment
Generation
Fragment
Shading
Visibility
Pipeline Gráfico (Rasterização)
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Fragment
Generation
Fragment
Shading
Visibility
Nem todos fragmentos 
virarão pixels: alguns 
serão descartados!
Atributos numéricos dos 
vértices são interpolados 
para todos fragmentos
Por quê?
Pipeline Gráfico (Rasterização)
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Fragment
Generation
Fragment
Shading
Visibility
Nem todos fragmentos 
virarão pixels: alguns 
serão descartados!
Atributos numéricos dos 
vértices são interpolados 
para todos fragmentos
Pipeline Gráfico (Rasterização)
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Fragment
Generation
Fragment
Shading
Visibility
Nem todos fragmentos 
virarão pixels: alguns 
serão descartados!
Atributos numéricos dos 
vértices são interpolados 
para todos fragmentos
Pipeline Gráfico (Rasterização)
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Fragment
Generation
Fragment
Shading
Visibility
Nem todos fragmentos 
virarão pixels: alguns 
serão descartados!
Atributos numéricos dos 
vértices são interpolados 
para todos fragmentos
Pipeline Gráfico (Rasterização)
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Fragment
Generation
Fragment
Shading
Visibility
Nem todos fragmentos 
virarão pixels: alguns 
serão descartados!
Atributos numéricos dos 
vértices são interpolados 
para todos fragmentos
Rasterizando Triângulos
13
Rasterizando Triângulos
 Novamente, dois passos:
1. Encontrar pixels ∈ triângulo
2. Interpolar atributos
 Várias opções de algoritmos
 Escolha depende de alguns fatores:
 Tamanho esperado dos triângulos (cobrem 
muitos ou poucos pixels?)
 Implementação em hardware ou software?
 Implementação paralela ou serial?
14
Rasterizando Triângulos
 Novamente, dois passos:
1. Encontrar pixels ∈ triângulo
2. Interpolar atributos
 Várias opções de algoritmos
 Escolha depende de alguns fatores:
 Tamanho esperado dos triângulos (cobrem 
muitos ou poucos pixels?)
 Implementação em hardware ou software?
 Implementação paralela ou serial?
15
Edge Walking
16
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
17
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
18
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
19
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
20
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
21
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
22
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
23
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
24
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
25
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
26
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
27
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
28
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
29
Bom para triângulos grandes
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
30
Bom para triângulos grandes
Pouco paralelizável
Alguns casos para tratar:
Edge Walking
1. Rasterizar arestas do triângulo com o algoritmo 
de Bresenham
2. Preencher os intervalos horizontais (spans) 
para cada linha (scanline) 
 Interpolar cores linearmente
31
Bom para triângulos grandes
Pouco paralelizável
Alguns casos para tratar:
Brute-Force Triangle Coverage
Brute-Force Triangle Coverage
for each pixel
if pixel inside triangle
interpolate vertex colors to pixel
Brute-Force Triangle Coverage
for each pixel
if pixel inside triangle
interpolate vertex colors to pixel
Paralelizável em hardware!
Brute-Force Triangle Coverage
for each pixel
if pixel inside triangle
interpolate vertex colors to pixel
Problema?
Muita computação 
desnecessária se o 
triângulo for pequeno!
Paralelizável em hardware!
Brute-Force Triangle Coverage
for each pixel
if pixel inside triangle
interpolate vertex colors to pixel
Problema?
Muita computação 
desnecessária se o 
triângulo for pequeno!
Paralelizável em hardware!
Brute-Force Triangle Coverage
for each pixel
if pixel inside triangle
interpolate vertex colors to pixel
Problema?
Muita computação 
desnecessária se o 
triângulo for pequeno!
Paralelizável em hardware!
BBOX Triangle Coverage
for each pixel in BBOX
if pixel inside triangle
interpolate vertex colors to pixel
Problema?
Muita computação 
desnecessária se o 
triângulo for pequeno!
Solução:
Percorrer somente os 
pixels dentro do Triangle 
Bounding Box (BBOX)
BBOX Triangle Coverage
for each pixel in BBOX
if pixel inside triangle
interpolate vertex colors to pixel
Problema?
Muita computação 
desnecessária se o 
triângulo for pequeno!
Solução:
Percorrer somente ospixels dentro do Triangle 
Bounding Box (BBOX)
Como computar
a BBOX?
Axis Aligned Bounding Box (AABB)
40
a b
c
p
q
Axis Aligned Bounding Box (AABB)
𝑝𝑥 = floor(min(𝑎𝑥 , 𝑏𝑥 , 𝑐𝑥))
𝑝𝑦 = floor(min(𝑎𝑦 , 𝑏𝑦 , 𝑐𝑦))
𝑞𝑥 = ceil(max(𝑎𝑥 , 𝑏𝑥 , 𝑐𝑥))
𝑞𝑦 = ceil(max(𝑎𝑦 , 𝑏𝑦 , 𝑐𝑦))
41
a b
c
p
q
Axis Aligned Bounding Box (AABB)
𝑝𝑥 = floor(min(𝑎𝑥 , 𝑏𝑥 , 𝑐𝑥))
𝑝𝑦 = floor(min(𝑎𝑦 , 𝑏𝑦 , 𝑐𝑦))
𝑞𝑥 = ceil(max(𝑎𝑥 , 𝑏𝑥 , 𝑐𝑥))
𝑞𝑦 = ceil(max(𝑎𝑦 , 𝑏𝑦 , 𝑐𝑦))
42
a b
c
p
q
Hierarchical Triangle Coverage
for each pixel in BBOX
if pixel inside triangle
interpolate vertex colors to pixel
Hierarchical Triangle Coverage
for each pixel in BBOX
if pixel inside triangle
interpolate vertex colors to pixel
Hierarchical Triangle Coverage
for each pixel in BBOX
if pixel inside triangle
interpolate vertex colors to pixel
Novamente
computação 
desnecessária!
Hierarchical Triangle Coverage
for each block in BBOX
if block inside triangle
interpolate colors to pixels ∈ triang
Testar blocos de pixels
(hierarchical rasteriz.)
Pixel Walk (Pineda 1988)
for each pixel in walk
if pixel inside triangle
interpolate vertex colors to pixel
Pineda, Juan. “A Parallel Algorithm for Polygon Rasterization.” 
SIGGRAPH ’88. 1988
Pixel Walk (Pineda 1988)
for each pixel in walk
if pixel inside triangle
interpolate vertex colors to pixel
Pineda, Juan. “A Parallel Algorithm for Polygon Rasterization.” 
SIGGRAPH ’88. 1988
Conservativamente
visitar um 
superconjunto dos 
pixels do triângulo
Perguntas?
49
Rasterizando Triângulos
50
for each pixel in region
if pixel inside triangle
interpolate vertex colors to pixel
Rasterizando Triângulos
 Vimos como definir regiões de busca
 Força bruta, BBOX, hierárquica, pixel walk
 Precisamos ainda:
 Determinar se o pixel está dentro do triângulo
 Interpolar atributos dos vértices para pixels
 Abordagem comum: edge equations
51
for each pixel in region
if pixel inside triangle
interpolate vertex colors to pixel
Rasterizando Triângulos
 Vimos como definir regiões de busca
 Força bruta, BBOX, hierárquica, pixel walk
 Precisamos ainda:
 Determinar se o pixel está dentro do triângulo
 Interpolar atributos dos vértices para pixels
 Abordagem comum: edge equations
52
for each pixel in region
if pixel inside triangle
interpolate vertex colors to pixel
Rasterizando Triângulos
 Vimos como definir regiões de busca
 Força bruta, BBOX, hierárquica, pixel walk
 Precisamos ainda:
 Determinar se o pixel está dentro do triângulo
 Interpolar atributos dos vértices para pixels
 Abordagem comum: edge equations
53
for each pixel in region
if pixel inside triangle
interpolate vertex colors to pixel
Rasterizando Triângulos
 Vimos como definir regiões de busca
 Força bruta, BBOX, hierárquica, pixel walk
 Precisamos ainda:
 Determinar se o pixel está dentro do triângulo
 Interpolar atributos dos vértices para pixels
 Abordagem comum: edge equations
54
for each pixel in region
if pixel inside triangle
interpolate vertex colors to pixel
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
55
b
p
q
a
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
56
b
p
 𝑣
q
a
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
57
b
p
 𝑣
q
a
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
58
b
p
 𝑣
q
a
?
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
59
b
p
 𝑣
q
a
?
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
60
b
p
 𝑣
q
a 𝑣
′ ⋅ 𝐩 − 𝐚
?
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
61
b
p
 𝑣
q
a 𝑣
′ ⋅ 𝐩 − 𝐚
?
> 0
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
62
b
p
 𝑣
q
a 𝑣
′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
?
> 0
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
63
b
p
 𝑣
q
a 𝑣
′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
?
> 0
< 0
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
64
b
p
 𝑣
q
a
r
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
?
> 0
< 0
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
65
b
p
 𝑣
q
a
r
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
?
> 0
< 0
= 0
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
66
b
p
 𝑣
q
a ≡
𝑣𝑥
𝑣𝑦
r
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
?
> 0
< 0
= 0
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
67
b
p
 𝑣
q
a ≡
𝑣𝑥
𝑣𝑦
≡
?
?
r
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
?
> 0
< 0
= 0
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
68
b
p
 𝑣
q
a ≡
𝑣𝑥
𝑣𝑦
≡
?
?
r
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
?
> 0
< 0
= 0
Exercício!
 𝑣′
Edge Equations
Como determinar se pontos estão à direita, 
à esquerda, ou em cima de uma reta infinita 
bidimensional?
69
b
p
 𝑣
q
a ≡
𝑣𝑥
𝑣𝑦
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
?
> 0
< 0
= 0
Exercício!
Edge Equations
70
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
≡
𝑣𝑥
𝑣𝑦
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
Edge Equations
71
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚
≡
𝑣𝑥
𝑣𝑦
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
Edge Equations
72
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚
≡
𝑣𝑥
𝑣𝑦
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
73
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚 = 𝑣𝑦 𝑥 − 𝑎𝑥 − 𝑣𝑥(𝑦 − 𝑎𝑦)
≡
𝑣𝑥
𝑣𝑦
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
74
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚 = 𝑣𝑦 𝑥 − 𝑎𝑥 − 𝑣𝑥(𝑦 − 𝑎𝑦)
= 𝑣𝑦𝑥 − 𝑣𝑥𝑦 − 𝑣𝑦𝑎𝑥 + 𝑣𝑥𝑎𝑦
≡
𝑣𝑥
𝑣𝑦
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
75
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚 = 𝑣𝑦 𝑥 − 𝑎𝑥 − 𝑣𝑥(𝑦 − 𝑎𝑦)
= 𝑣𝑦𝑥 − 𝑣𝑥𝑦 − 𝑣𝑦𝑎𝑥 + 𝑣𝑥𝑎𝑦
≡
𝑣𝑥
𝑣𝑦
= 𝐴𝑥 + 𝐵𝑦 + 𝐶
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
76
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚 = 𝑣𝑦 𝑥 − 𝑎𝑥 − 𝑣𝑥(𝑦 − 𝑎𝑦)
= 𝑣𝑦𝑥 − 𝑣𝑥𝑦 − 𝑣𝑦𝑎𝑥 + 𝑣𝑥𝑎𝑦
≡
𝑣𝑥
𝑣𝑦
= 𝐴𝑥 + 𝐵𝑦 + 𝐶
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
77
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚 = 𝑣𝑦 𝑥 − 𝑎𝑥 − 𝑣𝑥(𝑦 − 𝑎𝑦)
= 𝑣𝑦𝑥 − 𝑣𝑥𝑦 − 𝑣𝑦𝑎𝑥 + 𝑣𝑥𝑎𝑦
≡
𝑣𝑥
𝑣𝑦
= 𝐴𝑥 + 𝐵𝑦 + 𝐶
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
78
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚 = 𝑣𝑦 𝑥 − 𝑎𝑥 − 𝑣𝑥(𝑦 − 𝑎𝑦)
= 𝑣𝑦𝑥 − 𝑣𝑥𝑦 − 𝑣𝑦𝑎𝑥 + 𝑣𝑥𝑎𝑦
≡
𝑣𝑥
𝑣𝑦
= 𝐴𝑥 + 𝐵𝑦 + 𝐶
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
79
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚 = 𝑣𝑦𝑥 − 𝑎𝑥 − 𝑣𝑥(𝑦 − 𝑎𝑦)
= 𝑣𝑦𝑥 − 𝑣𝑥𝑦 − 𝑣𝑦𝑎𝑥 + 𝑣𝑥𝑎𝑦
≡
𝑣𝑥
𝑣𝑦
= 𝐴𝑥 + 𝐵𝑦 + 𝐶𝑓𝐚𝐛(𝑥, 𝑦)
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
80
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚 = 𝑣𝑦 𝑥 − 𝑎𝑥 − 𝑣𝑥(𝑦 − 𝑎𝑦)
= 𝑣𝑦𝑥 − 𝑣𝑥𝑦 − 𝑣𝑦𝑎𝑥 + 𝑣𝑥𝑎𝑦
≡
𝑣𝑥
𝑣𝑦
= 𝐴𝑥 + 𝐵𝑦 + 𝐶𝑓𝐚𝐛(𝑥, 𝑦)
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
81
b
p
 𝑣
q
a
 𝑣′
r
≡
𝑣𝑦
−𝑣𝑥
 𝑣′ ⋅ 𝐩 − 𝐚 = 𝑣𝑦 𝑥 − 𝑎𝑥 − 𝑣𝑥(𝑦 − 𝑎𝑦)
= 𝑣𝑦𝑥 − 𝑣𝑥𝑦 − 𝑣𝑦𝑎𝑥 + 𝑣𝑥𝑎𝑦
≡
𝑣𝑥
𝑣𝑦
= 𝐴𝑥 + 𝐵𝑦 + 𝐶𝑓𝐚𝐛(𝑥, 𝑦)
 𝑣′ ⋅ 𝐩 − 𝐚
 𝑣′ ⋅ 𝐪 − 𝐚
 𝑣′ ⋅ 𝐫 − 𝐚
> 0
< 0
= 0
=
𝑥
𝑦
Edge Equations
82
b
a
Edge Equations
83
b
a
+
Edge Equations
84
b
a
+
-
Edge Equations
Para um ponto com coord. cartesianas 𝑥 e 𝑦, 
e uma reta no sentido a→b:
85
b
a
+
-
Edge Equations
86
a
+
-
Para um ponto com coord. cartesianas 𝑥 e 𝑦, 
e retas nos sentidos a→b e b→c:
-
c
b
Edge Equations
87
a
+
-
Para um ponto com coord. cartesianas 𝑥 e 𝑦, 
e retas nos sentidos a→b e b→c:
-
c
b
Direita?
Edge Equations
88
+
- b
Para um ponto com coord. cartesianas 𝑥 e 𝑦, 
e retas nos sentidos a→b, b→c e c→a:
-
a
- c
Edge Equations
89
+
- b
Para um ponto com coord. cartesianas 𝑥 e 𝑦, 
e retas nos sentidos a→b, b→c e c→a:
-
a
- c
Todas funções são 
positivas dentro 
do triângulo
Logo, um pixel com coordenadas 𝑥 e 𝑦 está 
dentro do triângulo abc quando as três 
funções das arestas dão resultado positivo.
Edge Equations
90
c
b
a
𝑥
𝑦 +
Rasterizando Triângulo
91
c
b
a
𝑥
𝑦 +
for each pixel in region
if 𝑓𝐚𝐛 𝑥, 𝑦 > 0 & 𝑓𝐛𝐜 𝑥, 𝑦 > 0 & 𝑓𝐜𝐚 𝑥, 𝑦 > 0
interpolate vertex colors to pixel
Rasterizando Triângulo
92
c
b
a
𝑥
𝑦 +
for each pixel in region
if 𝑓𝐚𝐛 𝑥, 𝑦 > 0 & 𝑓𝐛𝐜 𝑥, 𝑦 > 0 & 𝑓𝐜𝐚 𝑥, 𝑦 > 0
interpolate vertex colors to pixel
Perguntas?
Rasterizando Triângulo
93
c
b
a
𝑥
𝑦 +
for each pixel in region
if 𝑓𝐚𝐛 𝑥, 𝑦 > 0 & 𝑓𝐛𝐜 𝑥, 𝑦 > 0 & 𝑓𝐜𝐚 𝑥, 𝑦 > 0
interpolate vertex colors to pixel
Perguntas?
Interpolando Atributos
94
c
b
a
𝑥
𝑦 +
Interpolando Atributos
95
c
b
a
𝑥
𝑦 +
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Logo: 𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
Interpolando Atributos
96
c
b
a
𝑥
𝑦 +
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Logo: 𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
Interpolando Atributos
97
c
b
a
𝑥
𝑦 +
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Logo: 𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
Coordenadas
baricêntricas
Interpolando Atributos
98
c
b
a
𝑥
𝑦 +
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Logo: 𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
Coordenadas
baricêntricas
Interpolando Atributos
99
c
b
a
𝑥
𝑦 +
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Logo: 𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
Coordenadas
baricêntricas
Cor de cada 
pixel é uma 
combinação 
linear das 
cores dos 
vértices!
Coordenadas Baricêntricas
100
c
b
a p
Coordenadas Baricêntricas
101
c
b
a
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Como encontrar 𝛼, 𝛽, e 𝛾 para um certo ponto p?
 Interpretação geométrica:
p
Coordenadas Baricêntricas
102
c
b
a
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Como encontrar 𝛼, 𝛽, e 𝛾 para um certo ponto p?
 Interpretação geométrica:
p
𝐷
Coordenadas Baricêntricas
103
c
b
a
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Como encontrar 𝛼, 𝛽, e 𝛾 para um certo ponto p?
 Interpretação geométrica:
p
𝐷
𝐿
Coordenadas Baricêntricas
104
c
b
a
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Como encontrar 𝛼, 𝛽, e 𝛾 para um certo ponto p?
 Interpretação geométrica:
p
𝛼 =
𝐷
𝐿
𝐷
𝐿
Coordenadas Baricêntricas
105
c
b
a
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Como encontrar 𝛼, 𝛽, e 𝛾 para um certo ponto p?
 Interpretação geométrica:
p
𝛼 =
𝐷
𝐿
𝐷
𝐿
Coordenadas Baricêntricas
106
c
b
a
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Como encontrar 𝛼, 𝛽, e 𝛾 para um certo ponto p?
 Interpretação geométrica:
p
𝛼 =
𝐷
𝐿
𝐷
𝐿
1𝐚 + 0𝐛 + 0𝐜 =
Coordenadas Baricêntricas
107
c
b
a
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Como encontrar 𝛼, 𝛽, e 𝛾 para um certo ponto p?
 Interpretação geométrica:
p
𝛼 =
𝐷
𝐿
𝐷
𝐿
=
𝑓𝐛𝐜(𝑝𝑥 , 𝑝𝑦)
𝑓𝐛𝐜(𝑎𝑥 , 𝑎𝑦)
1𝐚 + 0𝐛 + 0𝐜 =
Coordenadas Baricêntricas
108
c
b
a
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Como encontrar 𝛼, 𝛽, e 𝛾 para um certo ponto p?
 Interpretação geométrica:
p
𝛼 =
𝐷
𝐿
𝐷
𝐿
=
𝑓𝐛𝐜(𝑝𝑥 , 𝑝𝑦)
𝑓𝐛𝐜(𝑎𝑥 , 𝑎𝑦)
1𝐚 + 0𝐛 + 0𝐜 =
𝛽 =
𝑓𝐜𝐚(𝑝𝑥 , 𝑝𝑦)
𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
Coordenadas Baricêntricas
109
c
b
a
 Se p ∈ triângulo então 𝐩 = 𝛼𝐚 + 𝛽𝐛 + 𝛾𝐜
onde 𝛼 + 𝛽 + 𝛾 = 1 e 0 ≤ 𝛼, 𝛽, 𝛾 ≤ 1.
 Como encontrar 𝛼, 𝛽, e 𝛾 para um certo ponto p?
 Interpretação geométrica:
p
𝛼 =
𝐷
𝐿
𝐷
𝐿
=
𝑓𝐛𝐜(𝑝𝑥 , 𝑝𝑦)
𝑓𝐛𝐜(𝑎𝑥 , 𝑎𝑦)
1𝐚 + 0𝐛 + 0𝐜 =
𝛽 =
𝑓𝐜𝐚(𝑝𝑥 , 𝑝𝑦)
𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 =
𝑓𝐚𝐛(𝑝𝑥 , 𝑝𝑦)
𝑓𝐚𝐛(𝑐𝑥 , 𝑐𝑦)
Rasterizando Triângulo
110
c
b
a
Rasterizando Triângulo
111
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Rasterizando Triângulo
112
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Rasterizando Triângulo
113
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Rasterizando Triângulo
114
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Rasterizando Triângulo
115
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 =𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Rasterizando Triângulo
116
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Rasterizando Triângulo
117
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Mesma interpolação para qualquer outro atributo numérico!
Exemplo de Interpolação de Cor
118
a
c
b
Exemplo de Interpolação de Cor
119
a
c
b
Exemplo de Interpolação de Cor
120
a
c
b
(pixels 
exageradamente 
grandes para 
visualização)
Ordem dos Vértices
121
a
b
c
Ordem dos Vértices
122
a
b
c
Problema?
Ordem dos Vértices
123
a
b
c
Problema?
Ordem dos Vértices
124
a
b
c
Problema?
Ponto c esta à esquerda da 
reta no sentido a→b!
Ordem dos Vértices
125
a
b
c
Problema?
Ponto c esta à esquerda da 
reta no sentido a→b!
Solução:
Ordem dos Vértices
126
a
b
c
Problema?
Ponto c esta à esquerda da 
reta no sentido a→b!
Solução:
Reordenar os vértices 
ou trocar o sentido da 
aresta (ie, trocar 𝑓𝐚𝐛
por 𝑓𝐛𝐚).
Otimizando o Loop
127
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Otimizando o Loop
128
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Otimizando o Loop
129
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Otimizando o Loop
130
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
c
b
a
Digital Differential Analyzer pode ser utilizado para diminuir o 
número de instruções dentro do loop.
Otimizando o Loop
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
𝐴2 = 𝐴2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦); 𝐵2 = 𝐵2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦); 𝐶2 = 𝐶2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦);
𝐴1 = 𝐴1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦); 𝐵1 = 𝐵1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦); 𝐶1 = 𝐶1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦);
𝐴3 = 𝐴3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦); 𝐵3 = 𝐵3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦); 𝐶3 = 𝐶3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦);
𝛼 = 𝐴2x0+ 𝐵2y0 + 𝐶2
𝛽 = 𝐴3x0+ 𝐵3y0 + 𝐶3
𝛾 = 𝐴1x0+ 𝐵1y0 + 𝐶1
for x = x0 to xN
for y = y0 to yN
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
𝛼 = 𝛼 + 𝐵2; 𝛽 = 𝛽 + 𝐵3; 𝛾 = 𝛾 + 𝐵1;
𝛼 = 𝛼 + 𝐴2 − (yN-y0+1)𝐵2;
𝛽 = 𝛽 + 𝐴3 − (yN-y0+1)𝐵3;
𝛾 = 𝛾 + 𝐴1 − (yN-y0+1)𝐵1; 
Otimizando o Loop
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
𝐴2 = 𝐴2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦); 𝐵2 = 𝐵2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦); 𝐶2 = 𝐶2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦);
𝐴1 = 𝐴1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦); 𝐵1 = 𝐵1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦); 𝐶1 = 𝐶1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦);
𝐴3 = 𝐴3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦); 𝐵3 = 𝐵3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦); 𝐶3 = 𝐶3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦);
𝛼 = 𝐴2x0+ 𝐵2y0 + 𝐶2
𝛽 = 𝐴3x0+ 𝐵3y0 + 𝐶3
𝛾 = 𝐴1x0+ 𝐵1y0 + 𝐶1
for x = x0 to xN
for y = y0 to yN
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
𝛼 = 𝛼 + 𝐵2; 𝛽 = 𝛽 + 𝐵3; 𝛾 = 𝛾 + 𝐵1;
𝛼 = 𝛼 + 𝐴2 − (yN-y0+1)𝐵2;
𝛽 = 𝛽 + 𝐴3 − (yN-y0+1)𝐵3;
𝛾 = 𝛾 + 𝐴1 − (yN-y0+1)𝐵1; 
Inicialização fora do loop
Otimizando o Loop
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
𝐴2 = 𝐴2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦); 𝐵2 = 𝐵2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦); 𝐶2 = 𝐶2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦);
𝐴1 = 𝐴1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦); 𝐵1 = 𝐵1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦); 𝐶1 = 𝐶1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦);
𝐴3 = 𝐴3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦); 𝐵3 = 𝐵3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦); 𝐶3 = 𝐶3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦);
𝛼 = 𝐴2x0+ 𝐵2y0 + 𝐶2
𝛽 = 𝐴3x0+ 𝐵3y0 + 𝐶3
𝛾 = 𝐴1x0+ 𝐵1y0 + 𝐶1
for x = x0 to xN
for y = y0 to yN
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
𝛼 = 𝛼 + 𝐵2; 𝛽 = 𝛽 + 𝐵3; 𝛾 = 𝛾 + 𝐵1;
𝛼 = 𝛼 + 𝐴2 − (yN-y0+1)𝐵2;
𝛽 = 𝛽 + 𝐴3 − (yN-y0+1)𝐵3;
𝛾 = 𝛾 + 𝐴1 − (yN-y0+1)𝐵1; 
Inicialização fora do loop
Atualização dentro do loop 
somente com somas 
(instruções eficientes).
Otimizando o Loop
compute 𝐴1, 𝐵1, 𝐶1 for 𝑓𝐚𝐛 𝑥, 𝑦 = 𝐴1𝑥 + 𝐵1𝑦 + 𝐶1
compute 𝐴2, 𝐵2, 𝐶2 for 𝑓𝐛𝐜 𝑥, 𝑦 = 𝐴2𝑥 + 𝐵2𝑦 + 𝐶2
compute 𝐴3, 𝐵3, 𝐶3 for 𝑓𝐜𝐚 𝑥, 𝑦 = 𝐴3𝑥 + 𝐵3𝑦 + 𝐶3
𝐴2 = 𝐴2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦); 𝐵2 = 𝐵2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦); 𝐶2 = 𝐶2/𝑓𝐛𝐜(𝑎𝑥, 𝑎𝑦);
𝐴1 = 𝐴1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦); 𝐵1 = 𝐵1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦); 𝐶1 = 𝐶1/𝑓𝐚𝐛(𝑐𝑥, 𝑐𝑦);
𝐴3 = 𝐴3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦); 𝐵3 = 𝐵3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦); 𝐶3 = 𝐶3/𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦);
𝛼 = 𝐴2x0+ 𝐵2y0 + 𝐶2
𝛽 = 𝐴3x0+ 𝐵3y0 + 𝐶3
𝛾 = 𝐴1x0+ 𝐵1y0 + 𝐶1
for x = x0 to xN
for y = y0 to yN
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
draw pixel at (x,y) with color 𝐩color
𝛼 = 𝛼 + 𝐵2; 𝛽 = 𝛽 + 𝐵3; 𝛾 = 𝛾 + 𝐵1;
𝛼 = 𝛼 + inc_𝛼;
𝛽 = 𝛽 + inc_𝛽;
𝛾 = 𝛾 + inc_𝛾; 
Inicialização fora do loop
Atualização dentro do loop 
somente com somas 
(instruções eficientes).
inc_𝛼 = 𝐴2 − (yN-y0+1)𝐵2
inc_𝛽 = 𝐴3 − (yN-y0+1)𝐵3
inc_𝛾 = 𝐴1 − (yN-y0+1)𝐵1
Pré-computar fora do loop:
Perguntas?
135
Detalhes: pixels sobre arestas
Detalhes: pixels sobre arestas
Detalhes: pixels sobre arestas
Detalhes: pixels sobre arestas
Problema?
Detalhes: pixels sobre arestas
Problema?
Detalhes: pixels sobrearestas
Problema?
Detalhes: pixels sobre arestas
Como evitar “buracos”?Problema?
Detalhes: pixels sobre arestas
 Ordem de rasterização não deve importar
 Utilizar uma regra para manter consistência
 Exemplo:
Detalhes: pixels sobre arestas
 Ordem de rasterização não deve importar
 Utilizar uma regra para manter consistência
 Exemplo:
Detalhes: pixels sobre arestas
 Ordem de rasterização não deve importar
 Utilizar uma regra para manter consistência
 Exemplo:
Para cada triângulo, 
desenhar pixels sobre 
aresta da esquerda, 
mas não desenhar
pixels sobre aresta da 
direita.
Detalhes: pixels sobre arestas
 Ordem de rasterização não deve importar
 Utilizar uma regra para manter consistência
 Exemplo:
Para cada triângulo, 
desenhar pixels sobre 
aresta da esquerda, 
mas não desenhar
pixels sobre aresta da 
direita.
Detalhes: pixels sobre arestas
 Ordem de rasterização não deve importar
 Utilizar uma regra para manter consistência
 Exemplo:
Para cada triângulo, 
desenhar pixels sobre 
aresta da esquerda, 
mas não desenhar
pixels sobre aresta da 
direita.
Detalhes: pixels sobre arestas
 Ordem de rasterização não deve importar
 Utilizar uma regra para manter consistência
 Exemplo:
Para cada triângulo, 
desenhar pixels sobre 
aresta da esquerda, 
mas não desenhar
pixels sobre aresta da 
direita.
?
Detalhes: “buracos”
149
Detalhes: “buracos”
 Buracos ainda podem ocorrer!
 Exemplo ao lado foi rasterizado 
pelo hardware (OpenGL)
 Ocorre em triângulos “finos”
 “Buraco” visível somente com 
magnificação dos pixels
 Tamanho original:
150
Detalhes: “buracos”
 Buracos ainda podem ocorrer!
 Exemplo ao lado foi rasterizado 
pelo hardware (OpenGL)
 Ocorre em triângulos “finos”
 “Buraco” visível somente com 
magnificação dos pixels
 Tamanho original:
151
Perguntas?
152
Interpolação Perspectiva
153
Interpolação Perspectiva
 Nossos modelos geométricos são em 
três dimensões
 Rasterização ocorre após projeção e
após viewport mapping (mapeamento 
para coordenadas de tela)
 Isto é, estamos interpolando atributos 
(cores, normais, etc) em duas 
dimensões (sobre a tela)
 Isso está correto? 
154
Interpolação Perspectiva
 Nossos modelos geométricos são em 
três dimensões
 Rasterização ocorre após projeção e
após viewport mapping (mapeamento 
para coordenadas de tela)
 Isto é, estamos interpolando atributos 
(cores, normais, etc) em duas 
dimensões (sobre a tela)
 Isso está correto? 
155
Interpolação Perspectiva
 Nossos modelos geométricos são em 
três dimensões
 Rasterização ocorre após projeção e
após viewport mapping (mapeamento 
para coordenadas de tela)
 Isto é, estamos interpolando atributos 
(cores, normais, etc) em duas 
dimensões (sobre a tela)
 Isso está correto? 
156
Interpolação Perspectiva
 Nossos modelos geométricos são em 
três dimensões
 Rasterização ocorre após projeção e
após viewport mapping (mapeamento 
para coordenadas de tela)
 Isto é, estamos interpolando atributos 
(cores, normais, etc) em duas 
dimensões (sobre a tela)
 Isso está correto? 
157
Não para proj. perspectiva!
Interpolação Perspectiva
158
 𝑥
 𝑧
 𝑦
Camera
(Eye) Coord.
Frustum
Interpolação Perspectiva
159
 𝑥
 𝑧
 𝑦
Camera
(Eye) Coord.
Frustum
Interpolação Perspectiva
160
 𝑥
 𝑧
 𝑦
Camera
(Eye) Coord.
Frustum
 𝑧
 𝑦
Interpolação Perspectiva
161
Frustum
b
a
 𝑧
 𝑦
Interpolação Perspectiva
162
Frustum
b
a
a'
 𝑧
 𝑦
Interpolação Perspectiva
163
Frustum
b
a
a'
b'
 𝑧
 𝑦
Interpolação Perspectiva
164
Frustum
b
a
c
a'
b'
 𝑧
 𝑦
Interpolação Perspectiva
165
Frustum
b
a
c
a'
b'
c'
 𝑧
 𝑦
Interpolação Perspectiva
166
Frustum
b
a
c
a'
b'
c'
𝐜 = (𝐚 + 𝐛)/𝟐Antes da projeção:
 𝑧
 𝑦
Interpolação Perspectiva
167
Frustum
b
a
c
a'
b'
c'
𝐜 = (𝐚 + 𝐛)/𝟐Antes da projeção:
Depois da projeção: 𝐜′ ≠ (𝐚′ + 𝐛′)/2
 𝑧
 𝑦
Interpolação Perspectiva
168
Frustum
b
a
c
a'
b'
c'
𝐜 = (𝐚 + 𝐛)/𝟐Antes da projeção:
Depois da projeção: 𝐜′ ≠ (𝐚′ + 𝐛′)/2
Problema?
Interpolação Perspectiva
169
Interpolação Perspectiva
 Para obter uma interpolação de atributos 
dos vértices perspectivamente correta
é necessário o uso de interpolação 
hiperbólica (ou racional)
 A interpolação linear que vimos nesta 
aula é uma parte da interpolação 
hiperbólica
 Mais detalhes: INF01009 (Computação Gráfica)
170
Interpolação Perspectiva
 Para obter uma interpolação de atributos 
dos vértices perspectivamente correta
é necessário o uso de interpolação 
hiperbólica (ou racional)
 A interpolação linear que vimos nesta 
aula é uma parte da interpolação 
hiperbólica
 Mais detalhes: INF01009 (Computação Gráfica)
171
Interpolação Perspectiva
172
Interpolação Perspectiva
173
(fragment shader)
Interpolação Perspectiva
 Em OpenGL, a GPU faz automaticamente 
interpolação perspectivamente correta:
 Mas, podemos desabilitar:
174
(fragment shader)
Interpolação Perspectiva
 Em OpenGL, a GPU faz automaticamente 
interpolação perspectivamente correta:
 Mas, podemos desabilitar:
175
(fragment shader)
(fragment shader)
Interpolação Perspectiva
176
“Parede” quadriculada 
vista de frente
“Parede” quadriculada 
vista de lado com 
projeção perspectiva e 
interpolação linear dos 
atributos dos vértices 
para cada pixel
“Parede” quadriculada 
vista de lado com 
projeção perspectiva e 
interpolação hiperbólica 
dos atributos dos 
vértices para cada pixel
Interpolação Perspectiva
177
“Parede” quadriculada 
vista de frente
“Parede” quadriculada 
vista de lado com 
projeção perspectiva e 
interpolação linear dos 
atributos dos vértices 
para cada pixel
“Parede” quadriculada 
vista de lado com 
projeção perspectiva e 
interpolação hiperbólica 
dos atributos dos 
vértices para cada pixel
Perguntas?
178
Outras Geometrias
179
Outras Geometrias
180
Seu visualizador de slides está rasterizando 
este polígono neste exato momento.
Outras Geometrias
 Rasterização de polígonos quaisquer
 Operação comum em computação gráfica 2D
 Triangulação ou rasterizados diretamente
 Rasterização de círculos, elipses, etc.
 Extensões do método de Bresenham
181
Outras Geometrias
 Rasterização de polígonos quaisquer
 Operação comum em computação gráfica 2D
 Triangulação ou rasterizados diretamente
 Rasterização de círculos, elipses, etc.
 Extensões do método de Bresenham
182
Perguntas?
183