Aula_13_Clipping_and_Culling

Prévia do material em texto

Clipping and Culling
Prof. Eduardo Gastal
eslgastal@inf.ufrgs.br
INF01047 – 2017/1
Culling
2
Frustum 
culling
Backface
culling
Occlusion
culling
 Objetos que a câmera virtual não vê 
devem ser descartados
 Objetos que a câmera virtual não vê 
devem ser descartados
Culling
3
Fora do 
frustum
“Lado de trás” 
do objeto
Objeto 
escondido 
por outro em 
sua frente
Clipping
 Clipping é o processo 
de “recortar” um 
objeto, preservando 
somente as partes de 
interesse
4
Normalized Device
Coordinates (NDC)
Clipping
 Clipping é o processo 
de “recortar” um 
objeto, preservando 
somente as partes de 
interesse
5
Normalized Device
Coordinates (NDC)
Fora do volume visível
Clipping
 Clipping é o processo 
de “recortar” um 
objeto, preservando 
somente as partes de 
interesse
6
Normalized Device
Coordinates (NDC)
Fora do volume visível
Clipping
 Clipping é o processo 
de “recortar” um 
objeto, preservando 
somente as partes de 
interesse
7
Normalized Device
Coordinates (NDC)
Fora do volume visível
Clipping
 Clipping é o processo 
de “recortar” um 
objeto, preservando 
somente as partes de 
interesse
8
Normalized Device
Coordinates (NDC)
Fora do volume visível
Culling vs Clipping
 Culling comumente visa evitar 
processamento desnecessário
 Descartamos o que não será visto
 Ocorre tanto no nivel da aplicação como 
dentro do pipeline gráfico (OpenGL)
9
Culling: Aplicação vs Pipeline
10
Culling: Aplicação vs Pipeline
11
Culling: Aplicação vs Pipeline
12
1. Aplicação descarta geometria que
é obviamente não visível.
Culling: Aplicação vs Pipeline
13
1. Aplicação descarta geometria que
é obviamente não visível.
2. GPU faz o descarte final
Culling vs Clipping
14
Culling vs Clipping
 Clipping comumente visa evitar erros de 
rendering e limitações técnicas
 Por exemplo: tentar desenhar um pixel fora da 
tela irá gerar um erro de acesso à memória do 
framebuffer, ou pode acabar sobrescrevendo 
um pixel errado.
 Portanto, “recortamos” regiões problemáticas
 Normalmente ocorre somente no nível do 
pipeline gráfico (OpenGL)
15
Culling vs Clipping
 Clipping comumente visa evitar erros de 
rendering e limitações técnicas
 Por exemplo: tentar desenhar um pixel fora da 
tela irá gerar um erro de acesso à memória do 
framebuffer, ou pode acabar sobrescrevendo 
um pixel errado.
 Portanto, “recortamos” regiões problemáticas
 Normalmente ocorre somente no nível do 
pipeline gráfico (OpenGL)
16
Pipeline Gráfico (Rasterização)
17
Aplicação
Rendering
Imagem
(framebuffer)
Transform.
Geometria
Rasterização
Model & View
Vertex Shading
Projection
Clipping
Screen Mapping
(Viewport)
Rendering
 Culling e Clipping ocorrem durante 
renderização de primitivas
18
Rendering
 Culling e Clipping ocorrem durante 
renderização de primitivas
19
Culling: Fora da 
região visível. 
Descartado por 
inteiro.
Rendering
 Culling e Clipping ocorrem durante 
renderização de primitivas
20
Culling: Fora da 
região visível. 
Descartado por 
inteiro.
Clipping: 
Intersecta a 
região visível. 
Necessário 
recorte.
Perguntas?
21
Backface Culling
22
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Backface Culling
23
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Backface Culling
24
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Como detectar triângulos que 
estão “de costas” para a câmera?
Backface Culling
25
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Como detectar triângulos que 
estão “de costas” para a câmera?
𝑛
Backface Culling
26
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Como detectar triângulos que 
estão “de costas” para a câmera?
Descartar (cull) triângulos quando 𝑐 ⋅ 𝑛
𝑛
 𝑐
Backface Culling
27
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Como detectar triângulos que 
estão “de costas” para a câmera?
Descartar (cull) triângulos quando 𝑐 ⋅ 𝑛
𝑛
< 0
 𝑐
Backface Culling
28
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Como detectar triângulos que 
estão “de costas” para a câmera?
Descartar (cull) triângulos quando 𝑐 ⋅ 𝑛
𝑛
< 0
 𝑐
 𝑐
Backface Culling em OpenGL
29
Backface Culling em OpenGL
glEnable(GL_CULL_FACE)
glCullFace(GL_BACK)
glFrontFace(GL_CCW)
30
Backface Culling em OpenGL
glEnable(GL_CULL_FACE)
glCullFace(GL_BACK)
glFrontFace(GL_CCW)
31
GL_BACK
GL_FRONT
GL_FRONT_AND_BACK
Backface Culling em OpenGL
glEnable(GL_CULL_FACE)
glCullFace(GL_BACK)
glFrontFace(GL_CCW)
32
GL_BACK
GL_FRONT
GL_FRONT_AND_BACK
Backface Culling em OpenGL
glEnable(GL_CULL_FACE)
glCullFace(GL_BACK)
glFrontFace(GL_CCW)
33
GL_BACK
GL_FRONT
GL_FRONT_AND_BACK
GL_CW
GL_CCW
Perguntas?
34
Occlusion Culling (Visibility)
35
Occlusion Culling (Visibility)
36
 Como renderizar corretamente objetos 
escondidos por outros?
 Algoritmo do Pintor
 Algoritmo Z-buffer (ou depth buffer)
Algoritmo do Pintor
37
Algoritmo do Pintor
38
Algoritmo do Pintor
39
Algoritmo do Pintor
40
Algoritmo do Pintor
 Desenhar primeiro objetos mais distantes 
da câmera
 Necessário ordenação dos polígonos
 Necessário reordenar ao movimentar a câmera!
 Ordenação nem sempre é possível...
41
Algoritmo do Pintor
 Desenhar primeiro objetos mais distantes 
da câmera
 Necessário ordenação dos polígonos
 Necessário reordenar ao movimentar a câmera!
 Ordenação nem sempre é possível...
42
Algoritmo do Pintor
 Desenhar primeiro objetos mais distantes 
da câmera
 Necessário ordenação dos polígonos
 Necessário reordenar ao movimentar a câmera!
 Ordenação nem sempre é possível...
43
Algoritmo do Pintor
44
A
B
Algoritmo do Pintor
45
A
B
C
Z-buffer (depth buffer)
46
Z-buffer (depth buffer)
47
Posição em profundidade
do primeiro triângulo
Z-buffer (depth buffer)
48
Posição em profundidade
do primeiro triângulo
Z-buffer (depth buffer)
49
Posição em profundidade
do primeiro triângulo
Z-buffer (depth buffer)
50
Posição em profundidade
do primeiro triângulo
Posição em profundidade
do segundo triângulo
Z-buffer (depth buffer)
51
Posição em profundidade
do primeiro triângulo
Posição em profundidade
do segundo triângulo
Z-buffer (depth buffer)
52
Posição em profundidade
do primeiro triângulo
Posição em profundidade
do segundo triângulo
 Somente o fragmento mais próximo da 
câmera se torna um pixel!
Z-buffer (depth buffer) - 1974
Disney, Pixar 
Edwin Catmull
Z-buffer (depth buffer) - 1974
 Algumas vantagens e desvantagens:
 Fácil implementação (software e hardware)
 Funciona para qualquer tipo de objeto
 Utiliza muita memória (#pixels × bitsperpixel)
 Depende da precisão desejada para z (bitsperpixel)
 𝑝𝑧 = 0.12 vs 𝑞𝑧 = 0.11
Disney, Pixar 
Edwin Catmull
Z-buffer (depth buffer) - 1974
 Algumas vantagens e desvantagens:
 Fácil implementação (software e hardware)
 Funciona para qualquer tipo de objeto
 Utiliza muita memória (#pixels × bitsperpixel)
 Depende da precisão desejada para z (bitsperpixel)
 𝑝𝑧 = 0.12 vs 𝑞𝑧 = 0.11
Disney, Pixar 
Edwin Catmull
Z-buffer (depth buffer) - 1974
 Algumas vantagens e desvantagens:
 Fácil implementação (software e hardware)
 Funciona para qualquer tipo de objeto
 Utiliza muita memória (#pixels × bitsperpixel)
 Depende da precisão desejada para z (bitsperpixel)
 𝑝𝑧 = 0.12 vs 𝑞𝑧 = 0.11
Disney, Pixar 
Edwin Catmull
Z-buffer Precision: Z-fighting
57
Z-buffer (depth buffer) - 1974
 Algumas vantagens e desvantagens:
 Fácil implementação (software e hardware)
 Funciona para qualquer tipo de objeto
 Utiliza muita memória (#pixels × bitsperpixel)
 Depende da precisão desejada para z (bitsperpixel)
 𝑝𝑧 = 0.12 vs 𝑞𝑧 = 0.11
 Rasterização: precisa interpolar z de 
cada vértice para cada pixel
Disney, Pixar 
Edwin Catmull
Z-buffer Algorithm
59
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
Z-buffer Algorithm
60
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥 , 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥 , 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
𝐩z = 𝛼𝐚z + 𝛽𝐛z + 𝛾𝐜z
if 𝐩z < zbuffer[x,y]
draw pixel at (x,y) with color 𝐩color
zbuffer[x,y] = 𝐩z
c
b
a
Z-buffer Algorithm
61
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥 , 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥 , 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
𝐩z = 𝛼𝐚z + 𝛽𝐛z + 𝛾𝐜z
if 𝐩z < zbuffer[x,y]
draw pixel at (x,y) with color 𝐩color
zbuffer[x,y] = 𝐩z
c
b
a
for all (x,y)
zbuffer[x,y] = ∞
Z-buffer (depth buffer) - 1974
 Algumas vantagens e desvantagens:
 Fácil implementação (software e hardware)
 Funciona para qualquer tipo de objeto
 Utiliza muita memória (#pixels × bitsperpixel)
 Depende da precisão desejada para z (bitsperpixel)
 𝑝𝑧 = 0.12 vs 𝑞𝑧 = 0.11
 Rasterização: precisa interpolar z de 
cada vértice para cada pixel
 Não funciona diretamente para 
renderizar objetos transparentes
Disney, Pixar 
Edwin Catmull
Z-buffer em OpenGL
63
Z-buffer em OpenGL
64
glEnable(GL_DEPTH_TEST)
glDepthFunc(GL_LESS)
glClear(GL_DEPTH_BUFFER_BIT)
Z-buffer em OpenGL
65
glEnable(GL_DEPTH_TEST)
glDepthFunc(GL_LESS)
glClear(GL_DEPTH_BUFFER_BIT)
GL_LESS
GL_GREATER
GL_LEQUAL
GL_GEQUAL
GL_EQUAL
GL_NOTEQUAL
GL_ALWAYS
GL_NEVER
Z-buffer em OpenGL
66
glEnable(GL_DEPTH_TEST)
glDepthFunc(GL_LESS)
glClear(GL_DEPTH_BUFFER_BIT)
GL_LESS
GL_GREATER
GL_LEQUAL
GL_GEQUAL
GL_EQUAL
GL_NOTEQUAL
GL_ALWAYS
GL_NEVER
Importante resetar (“limpar”) o z-buffer sempre que a 
cena virtual for renderizada novamente:
Perguntas?
67
Frustum Culling
68
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Frustum
Frustum Culling
69
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Frustum
Frustum Culling
70
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Frustum
Frustum Culling
71
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Frustum
Frustum Culling
72
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Frustum
O que acontece com 
este triângulo se ele for 
transformado por nossas 
projeções?
Frustum Culling
73
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Frustum
O que acontece com 
este triângulo se ele for 
transformado por nossas 
projeções?
Frustum Culling
74
𝑢
𝑤
 𝑣
Camera
(Eye) Coord.
Frustum
Precisamos descartar objetos fora do 
frustum da câmera, caso contrário estes 
poderão ser projetados no plano de 
imagem pelas matrizes de projeção!
O que acontece com 
este triângulo se ele for 
transformado por nossas 
projeções?
Frustum Culling
75
 𝑧
 𝑦
Frustum
Frustum Culling
76
 𝑧
 𝑦
Frustum
✘
✘
✘
✘
Frustum Culling
77
 𝑧
 𝑦
Frustum
✘ ✔
✘
✘
✘
?
Frustum Culling
78
 𝑧
 𝑦
Frustum
✘ ✔
✘
✘
✘
?
Frustum Culling
79
 𝑧
 𝑦
Frustum
✘ ✔
✘
✘
✘
Precisa ser recortado!
(clipping)
Frustum Culling: Pontos
80
 𝑧
 𝑦
Frustum
✘
✔
✘
✘
✘ ✔
✘
✘
Frustum Culling: Pontos
81
 𝑧
 𝑦
Frustum
✘
✔
✘
✘
✘
Pontos nunca precisam 
de recorte!
✔
✘
✘
Frustum Culling: Pontos
82
 𝑧
 𝑦
Frustum
✘
✔
✘
✘
✘
Pontos nunca precisam 
de recorte!
Mas: como testar se um ponto 
está dentro ou fora do frustum?
✔
✘
✘
Frustum Culling: Pontos
83
p
Frustum Culling: Pontos
84
p
Frustum Culling: Pontos
85
p
Frustum Culling: Pontos
86
p
Frustum Culling: Pontos
 Ponto p está dentro do frustum?
 Mais fácil testar após transformação para NDC!
87
p
Frustum Culling: Pontos
 Ponto p está dentro do frustum?
 Mais fácil testar após transformação para NDC!
88
p
−1
−1
−1
1
1
1
Normalized Device
Coordinates (NDC)
𝑀𝑃
(+div.w)
p
Frustum Culling: Pontos
 Ponto p está dentro do frustum?
 Mais fácil testar após transformação para NDC!
89
p
−1
−1
−1
1
1
1
Normalized Device
Coordinates (NDC)
𝑀𝑃
(+div.w)
p
−1 ≤ 𝑝𝑥 ≤ 1
−1 ≤ 𝑝𝑦 ≤ 1
−1 ≤ 𝑝𝑧 ≤ 1
Frustum Culling: Pontos
90
−1 ≤ 𝑝𝑥 ≤ 1
−1 ≤ 𝑝𝑦 ≤ 1
−1 ≤ 𝑝𝑧 ≤ 1
Frustum Culling: Pontos
 Ponto p em NDC está dentro do frustum:
 Note que o ponto só está em NDC após 
multiplicação por 𝑀𝑃 e divisão por w:
91
−1 ≤ 𝑝𝑥 ≤ 1
−1 ≤ 𝑝𝑦 ≤ 1
−1 ≤ 𝑝𝑧 ≤ 1
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
Frustum Culling: Pontos
 Ponto p em NDC está dentro do frustum:
 Note que o ponto só está em NDC após 
multiplicação por 𝑀𝑃 e divisão por w:
92
−1 ≤ 𝑝𝑥 ≤ 1
−1 ≤ 𝑝𝑦 ≤ 1
−1 ≤ 𝑝𝑧 ≤ 1
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
≡
Frustum Culling: Pontos
 Ponto p em NDC está dentro do frustum:
 Note que o ponto só está em NDC após 
multiplicação por 𝑀𝑃 e divisão por w:
93
−1 ≤ 𝑝𝑥 ≤ 1
−1 ≤ 𝑝𝑦 ≤ 1
−1 ≤ 𝑝𝑧 ≤ 1
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
≡
OpenGL faz 
este teste. 
Economiza 
divisões.
Frustum Culling: Pontos
 Ponto p em NDC está dentro do frustum:
 Note que o ponto só está em NDC após 
multiplicação por 𝑀𝑃 e divisão por w:
94
−1 ≤ 𝑝𝑥 ≤ 1
−1 ≤ 𝑝𝑦 ≤ 1
−1 ≤ 𝑝𝑧 ≤ 1
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
≡
OpenGL faz 
este teste. 
Economiza 
divisões.
Frustum Culling: Pontos
 Ponto p em NDC está dentro do frustum:
 Note que o ponto só está em NDC após 
multiplicação por 𝑀𝑃 e divisão por w:
95
−1 ≤ 𝑝𝑥 ≤ 1
−1 ≤ 𝑝𝑦 ≤ 1
−1 ≤ 𝑝𝑧 ≤ 1
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
≡
OpenGL faz 
este teste. 
Economiza 
divisões.
Teste do OpenGL 
é válido somente 
se 𝑤 > 0!
Frustum Culling: Pontos
96
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
≡
OpenGL faz 
este teste. 
Economiza 
divisões.
Teste sempre 
válido.
Teste do OpenGL 
é válido somente 
se 𝑤 > 0!
Frustum Culling: Pontos
97
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
≡
OpenGL faz 
este teste. 
Economiza 
divisões.
Teste sempre 
válido.
Para obter w > 0, usamos −𝑀𝑃 para 
projeção perspectiva em nosso Lab 2.
Teste do OpenGL 
é válido somente 
se 𝑤 > 0!
Divisão por w
98
𝑀𝑃𝐩 =
𝑥
𝑦
𝑧
𝑤
Divisão por w
99
𝑀𝑃𝐩 =
𝑥
𝑦
𝑧
𝑤
div. w
𝑥/𝑤
𝑦/𝑤
𝑧/𝑤
1
Divisão por w
100
𝑀𝑃𝐩 =
𝑥
𝑦
𝑧
𝑤
div. w
−𝑀𝑃𝐩 =
−𝑥
−𝑦
−𝑧
−𝑤
𝑥/𝑤
𝑦/𝑤
𝑧/𝑤
1
Divisão por w
101
𝑀𝑃𝐩 =
𝑥
𝑦
𝑧
𝑤
div. w
−𝑀𝑃𝐩 =
−𝑥
−𝑦
−𝑧
−𝑤
div. w
−𝑥/−𝑤
−𝑦/−𝑤
−𝑧/−𝑤
1
𝑥/𝑤
𝑦/𝑤
𝑧/𝑤
1
Divisão por w
102
𝑀𝑃𝐩 =
𝑥
𝑦
𝑧
𝑤
div. w
−𝑀𝑃𝐩 =
−𝑥
−𝑦
−𝑧
−𝑤
div. w
−𝑥/−𝑤
−𝑦/−𝑤
−𝑧/−𝑤
1
=
𝑥/𝑤
𝑦/𝑤
𝑧/𝑤
1
𝑥/𝑤
𝑦/𝑤
𝑧/𝑤
1
Divisão por w
103
𝑀𝑃𝐩 =
𝑥
𝑦
𝑧
𝑤
div. w
−𝑀𝑃𝐩 =
−𝑥
−𝑦
−𝑧
−𝑤
div. w
−𝑥/−𝑤
−𝑦/−𝑤
−𝑧/−𝑤
1
=
𝑥/𝑤
𝑦/𝑤
𝑧/𝑤
1
𝑥/𝑤
𝑦/𝑤
𝑧/𝑤
1
Frustum Culling: Pontos
104
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
≡
OpenGL faz 
este teste. 
Economiza 
divisões.
Teste sempre 
válido.
Para obter w > 0, usamos −𝑀𝑃 para 
projeção perspectiva em nosso Lab 2.
Teste do OpenGL 
é válido somente 
se 𝑤 > 0!
From the OpenGL 4.5 spec.
105
Perguntas?
106
Frustum Culling: Linhas
107
 𝑧
 𝑦
Frustum
✘ ✔
✘
✘
✘
Frustum Culling: Linhas
108
 𝑧
 𝑦
Frustum
✘ ✔
✘
✘
✘
Linhas precisam de 
recorte!
Frustum Culling: Linhas
109
 𝑧
 𝑦
Frustum
✘ ✔
✘
✘
✘
Linhas precisam de 
recorte!
Clipping: Linhas
110
Clipping: Linhas
 Também pode ser feito em NDC
 Mas: normalmente feito após
multiplicação pela matriz de projeção 
perspectiva e antes da divisão por w.
 Espaço chamado de “clip space.”
 Por quê?
 Divisão porw gera uma singularidade 
para primitivas que cruzam o plano 𝑧 = 0.
111
Clipping: Linhas
 Também pode ser feito em NDC
 Mas: normalmente feito após
multiplicação pela matriz de projeção 
perspectiva e antes da divisão por w.
 Espaço chamado de “clip space.”
 Por quê?
 Divisão por w gera uma singularidade 
para primitivas que cruzam o plano 𝑧 = 0.
112
Clipping: Linhas
 Também pode ser feito em NDC
 Mas: normalmente feito após
multiplicação pela matriz de projeção 
perspectiva e antes da divisão por w.
 Espaço chamado de “clip space.”
 Por quê?
 Divisão por w gera uma singularidade 
para primitivas que cruzam o plano 𝑧 = 0.
113
Cruzando o plano 𝒛 = 𝟎
114
 𝑧
 𝑦
𝑧 = 0
Cruzando o plano 𝒛 = 𝟎
115
 𝑧
 𝑦
𝑧 = 0
Cruzando o plano 𝒛 = 𝟎
116
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
117
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
118
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
119
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
120
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
121
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
122
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
123
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
124
 𝑧
 𝑦
Divisão por 
zero!
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
125
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
126
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
127
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
128
 𝑧
 𝑦
(𝑤 = 0)
Wrap-around no 
infinito!
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
129
 𝑧
 𝑦
(𝑤 = 0)
𝑧 = 0 plano de 
projeção
Cruzando o plano 𝒛 = 𝟎
130
 𝑧
 𝑦
O recorte (clipping) desta 
linha deve ser feito antes da 
divisão por w, para evitar a 
singularidade do plano 𝑧 = 0.
(𝑤 = 0)
Clipping antes da divisão por w
131
Clipping antes da divisão por w
132
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
Após div.w
Clipping antes da divisão por w
133
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
Após div.w Antes div.w
Clipping antes da divisão por w
 Note que, para pontos, também fazemos 
teste do frustum antes da divisão por w
 A situação é análoga para clipping de 
linhas e triângulos: feito antes da div.w.
134
−1 ≤ 𝑥/𝑤 ≤ 1
−1 ≤ 𝑦/𝑤 ≤ 1
−1 ≤ 𝑧/𝑤 ≤ 1
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
Após div.w Antes div.w
Perguntas?
135
Clipping: Linhas
136
D
a
n
n
y
 C
o
h
e
n
Iv
a
n
 S
u
th
e
rl
a
n
d
Clipping: Linhas
 Algoritmo de Cohen e Sutherland (1967)
 Descreve uma maneira eficiente 
para determinar quando uma 
linha precisará de clipping
 Descrição extendida para uso 
deste algoritmo antes da divisão 
por w por Jim Blinn
137
D
a
n
n
y
 C
o
h
e
n
Iv
a
n
 S
u
th
e
rl
a
n
d
Clipping: Linhas
 Algoritmo de Cohen e Sutherland (1967)
 Descreve uma maneira eficiente 
para determinar quando uma 
linha precisará de clipping
 Descrição extendida para uso 
deste algoritmo antes da divisão 
por w por Jim Blinn
138
D
a
n
n
y
 C
o
h
e
n
Iv
a
n
 S
u
th
e
rl
a
n
d
Blinn, J. F. “A Trip down the Graphics Pipeline: 
Line Clipping.” IEEE CG&A. 1991.
Cohen-Sutherland (1967)
139
Quais destas linhas precisam de recorte?
Cohen-Sutherland (1967)
140
Cohen-Sutherland (1967)
141
XXXX XXXX XXXX
XXXX XXXX XXXX
XXXX XXXX XXXX
Cohen-Sutherland (1967)
142
XXX1 XXX0 XXX0
XXX1 XXX0 XXX0
XXX1 XXX0 XXX0
Cohen-Sutherland (1967)
143
XX01 XX00 XX10
XX01 XX00 XX10
XX01 XX00 XX10
Cohen-Sutherland (1967)
144
X101 X100 X110
X001 X000 X010
X001 X000 X010
Cohen-Sutherland (1967)
145
0101 0100 0110
0001 0000 0010
1001 1000 1010
Cohen-Sutherland (1967)
146
0101 0100 0110
0001 0000 0010
1001 1000 1010
Cohen-Sutherland (1967)
147
0101 0100 0110
0001 0000 0010
1001 1000 1010
10001001 
Cohen-Sutherland (1967)
148
0101 0100 0110
0001 0000 0010
1001 1000 1010
10001001 
1000
0001
Cohen-Sutherland (1967)
149
0101 0100 0110
0001 0000 0010
1001 1000 1010
10001001 
1000
0001
0001 0000
Cohen-Sutherland (1967)
150
0101 0100 0110
0001 0000 0010
1001 1000 1010
10001001 
1000
0001
0001 0000
0000 0000
Cohen-Sutherland (1967)
151
0101 0100 0110
0001 0000 0010
1001 1000 1010
10001001 
1000
0001
0001 0000
0000 0000
1000
0010
Cohen-Sutherland (1967)
152
10001001 
1000
0001
0001 0000
0000 0000
“outcodes”
1000
0010
Cohen-Sutherland (1967)
153
10001001 
1000
0001
0001 0000
0000 0000
“outcodes”
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
1000
0010
Cohen-Sutherland (1967)
154
10001001 
1000
0001
0001 0000
0000 0000
“outcodes”
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
0000 
1000
0010
Cohen-Sutherland (1967)
155
10001001 
1000
0001
0001 0000
0000 0000
“outcodes”
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
0000 
0000 
1000
0010
Cohen-Sutherland (1967)
156
10001001 
1000
0001
0001 0000
0000 0000
“outcodes”
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
0000 
0000 
1000
0010
0000 
Cohen-Sutherland (1967)
157
10001001 
1000
0001
0001 0000
0000 0000
“outcodes”
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
0000 
0000 
0000 
1000
0010
0000 
Cohen-Sutherland (1967)
158
10001001 
1000
0001
0001 0000
0000 0000
“outcodes”
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
1000 
0000 
0000 
0000 
1000
0010
0000 
Cohen-Sutherland (1967)
159
1000
0001
0001 0000
0000 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
1000
0010
Cohen-Sutherland (1967)
160
1000
0001
0001 0000
0000 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
Bitwise OR of outcodes is = 0000 ⇒ Linha está 100% dentro
1000
0010
Cohen-Sutherland (1967)
161
1000
0001
0001 0000
0000 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
0001 
Bitwise OR of outcodes is = 0000 ⇒ Linha está 100% dentro
1000
0010
Cohen-Sutherland (1967)
162
1000
0001
0001 0000
0000 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
0000 
0001 
Bitwise OR of outcodes is = 0000 ⇒ Linha está 100% dentro
1000
0010
Cohen-Sutherland (1967)
163
1000
0001
0001 0000
0000 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
1001 
0000 
0001 
Bitwise OR of outcodes is = 0000 ⇒ Linha está 100% dentro
1000
0010
Cohen-Sutherland (1967)
164
1000
0001
0001 0000
0000 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
1001 
0000 
0001 
Bitwise OR of outcodes is = 0000 ⇒ Linha está 100% dentro
1000
0010
1010 
Cohen-Sutherland (1967)
165
1000
0001
0001 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
1001 
0001 
Bitwise OR of outcodes is = 0000 ⇒ Linha está 100% dentro
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
Cohen-Sutherland (1967)
166
1000
0001
0001 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
1001 
0001 
Bitwise OR of outcodes is = 0000 ⇒ Linha está 100% dentro
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
Cohen-Sutherland (1967)
167
1000
0001
0001 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
1001 
0001 
Bitwise OR of outcodes is = 0000 ⇒ Linha está 100% dentro
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
Qual a vantagem deste algoritmose nem todas as linhas que não
precisam de recorte são 
detectadas?
Cohen-Sutherland (1967)
168
1000
0001
0001 0000
Bitwise AND of outcodes is ≠ 0000 ⇒ Linha está fora (descarta)
1001 
0001 
Bitwise OR of outcodes is = 0000 ⇒ Linha está 100% dentro
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
A grande maioria das linhas 
normalmente não precisa de recorte, 
e a grande maioria destas são 
rapidamente tratadas pelo algoritmo.
Perguntas?
169
Recorte de Linhas
170
1000
0001
0001 0000
1001 
0001 
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
Recorte de Linhas
171
1000
0001
0001 0000
1001 
0001 
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
Bitwise OR dos 
outcodes dizem contra 
quais planos as linhas 
devem ser recortadas.
Recorte de Linhas
172
1000
0001
0001 0000
1001 
0001 
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
Bitwise OR dos 
outcodes dizem contra 
quais planos as linhas 
devem ser recortadas.
Planos?
Recorte de Linhas
173
1000
0001
0001 0000
1001 
0001 
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
Bitwise OR dos 
outcodes dizem contra 
quais planos as linhas 
devem ser recortadas.
Recorte de Linhas
174
1000
0001
0001 0000
1001 
0001 
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
Bitwise OR dos 
outcodes dizem contra 
quais planos as linhas 
devem ser recortadas.
Recorte de Linhas
175
1000
0001
0001 0000
0001 
1000
0010
1010 
Caso contrário, linha tem chance de necessitar recorte
Bitwise OR dos 
outcodes dizem contra 
quais planos as linhas 
devem ser recortadas.
1001 
Recorte de Linhas
176
1000
0001
0001 0000
0001 
1000
0010
Caso contrário, linha tem chance de necessitar recorte
1001 
1010 
Recorte é executado 
contra todos os planos 
cujo bit está não zero.
Recorte de Linhas
177
Recorte de Linhas
178
Recorte de Linhas
179
a b
Recorte de Linhas
180
a b
𝑛
p
Recorte de Linhas
181
a b
𝑛
p
𝐪 ∈ plano ⇔
Recorte de Linhas
182
a b
𝑛
p
(𝐪 − 𝐩) ⋅ 𝑛 = 0𝐪 ∈ plano ⇔
Recorte de Linhas
183
a b
𝑛
p
(𝐪 − 𝐩) ⋅ 𝑛 = 0𝐪 ∈ plano ⇔
𝐪 ∈ linha ⇔
Recorte de Linhas
184
a b
𝑛
p
(𝐪 − 𝐩) ⋅ 𝑛 = 0𝐪 ∈ plano ⇔
𝐪 ∈ linha ⇔ 𝐪 = 𝐚 + 𝑡 𝐛 − 𝐚
Recorte de Linhas
185
a b
𝑛
p
(𝐪 − 𝐩) ⋅ 𝑛 = 0𝐪 ∈ plano ⇔
𝐪 ∈ linha ⇔ 𝐪 = 𝐚 + 𝑡 𝐛 − 𝐚
𝑡 =
𝐩 − 𝐚 ⋅ 𝑛
𝐛 − 𝐚 ⋅ 𝑛
Recorte de Linhas
186
a b
𝑛
p
(𝐪 − 𝐩) ⋅ 𝑛 = 0𝐪 ∈ plano ⇔
𝐪 ∈ linha ⇔ 𝐪 = 𝐚 + 𝑡 𝐛 − 𝐚
𝑡 =
𝐩 − 𝐚 ⋅ 𝑛
𝐛 − 𝐚 ⋅ 𝑛
𝐪 = 𝐚 + 𝑡 𝐛 − 𝐚
Recorte de Linhas
187
1000
0001
0000
0001 
1000
0010
Caso contrário, linha tem chance de necessitar recorte
1001 
1010 
Recorte é executado 
contra todos os planos 
cujo bit está não zero.
Recorte de Linhas
188
1000
0001
a
b
1001 
Recorte de Linhas
189
1000
0001
a
b
𝐪
1001 
Recorte de Linhas
190
1000
0001
S1
S2a
b
𝐪
1001 
Recorte de Linhas
191
1000
0001
S1
S2
Qual segmento devemos 
preservar, S1 ou S2?
a
b
𝐪
1001 
Recorte de Linhas
192
1000
0001
S1
S2
Qual segmento devemos 
preservar, S1 ou S2?
a
b
S2!
𝐪
1001 
Recorte de Linhas
193
1000
0001
S1
S2
Qual segmento devemos 
preservar, S1 ou S2?
a
b
S2!
𝐪
Logo devemos substituir o 
ponto extremo a por q.
1001 
Recorte de Linhas
194
1000
0001
S1
S2
Qual segmento devemos 
preservar, S1 ou S2?
a
b
S2!
𝐪
Logo devemos substituir o 
ponto extremo a por q.
Como determinar isso 
algoritmicamente?
1001 
Recorte de Linhas
195
1000
0001
S1
S2
Qual segmento devemos 
preservar, S1 ou S2?
a
b
S2!
𝐪
Logo devemos substituir o 
ponto extremo a por q.
Como determinar isso 
algoritmicamente?
Olhamos para o outcode
dos pontos extremos!
1001 
1XXX
XXX1
Recorte de Linhas
196
1000
a
b
1001 
Recorte de Linhas
197
a
b
Recorte de Linhas
198
0000
0001 
1000
0010
Caso contrário, linha tem chance de necessitar recorte
1010 
Recorte é executado 
contra todos os planos 
cujo bit está não zero.
Recorte de Linhas
199
1000
0010
1010 
1XXX
XX1X
a
b
Recorte de Linhas
200
1000
0010
1010 
𝐪1XXX
XX1X
a
b
Recorte de Linhas
201
00101XXX
XX1X
a
b
Recorte de Linhas
202
0010
XX1X
a
b
Recorte de Linhas
203
0010
XX1X
a
b
Não existe mais intersecção 
com o segundo plano!?
Recorte de Linhas
204
0010
XX1X
a
b
Não existe mais intersecção 
com o segundo plano!?
Isso significa que a linha está 
fora do volume desejado e 
pode ser descartada!
Recorte de Linhas
205
Linhas recortadas 
e prontas para 
rasterização!
Recorte de Linhas
 Na prática, temos 6 planos de recorte
206
a
b
Recorte de Linhas
 Na prática, temos 6 planos de recorte
207
a
Clip Space
𝑀𝑃
(sem div.w)
b
Recorte de Linhas
 Na prática, temos 6 planos de recorte
208
a
Clip Space
𝑀𝑃
(sem div.w)
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
b
Recorte de Linhas
 Na prática, temos 6 planos de recorte
209
a
Clip Space
𝑀𝑃
(sem div.w)
−𝑤 ≤ 𝑥 ≤ 𝑤
−𝑤 ≤ 𝑦 ≤ 𝑤
−𝑤 ≤ 𝑧 ≤ 𝑤
b
?
Renderizando Linhas
210
a
b
Renderizando Linhas
1. Aplicar matriz de projeção nos pontos 
extremos a e b
2. Recortar com algoritmo de Cohen-
Sutherland
3. Fazer divisão por w
4. Rasterizar (e.g. Bresenham)
211
a
b
Renderizando Linhas
1. Aplicar matriz de projeção nos pontos 
extremos a e b
2. Recortar com algoritmo de Cohen-
Sutherland
3. Fazer divisão por w
4. Rasterizar (e.g. Bresenham)
212
a
b
Renderizando Linhas
1. Aplicar matriz de projeção nos pontos 
extremos a e b
2. Recortar com algoritmo de Cohen-
Sutherland
3. Fazer divisão por w
4. Rasterizar (e.g. Bresenham)
213
a
b
Perguntas?
214
Recorte de Triângulos
215
Recorte de Triângulos
216
Recorte de Triângulos
217
Recorte de Triângulos
218
Recorte de Triângulos
219
Recorte de Triângulos
220
Recorte de Triângulos
221
Recorte de 
triângulos é uma 
operação 
complexa.
Recorte de Triângulos
222
Recorte de Triângulos
 Na prática, podemos recortar os 
triângulos somente contra o near plane!
 Para evitar a singularidade de 𝑧 = 0.
 Os outro 5 planos podem ser tratados 
durante a rasterização
223
Recorte de Triângulos
224
 𝑧
 𝑦
Frustum
Recorte de Triângulos
225
 𝑧
 𝑦
Frustum
Recorte contra near plane
Recorte de Triângulos
226
 𝑧
 𝑦
Frustum
Recorte contra near plane
Sem recorte! Serão tratados 
pelo rasterizador.
Recorte de Triângulos
227
 𝑧
 𝑦
Frustum
Recorte contra near plane
Sem recorte! Serão tratados 
pelo rasterizador.
Descartado (100% do lado 
errado do near plane)
Recorte de Triângulos
228
Recorte de Triângulos
 Na prática, podemos recortar os 
triângulos somente contra o near plane!
 Para evitar a singularidade de 𝑧 = 0.
 Os outro 5 planos podem ser tratados 
durante a rasterização
 Como?
 Loop de rasterização somente por pixels 
válidos
 Com o z-buffer, descartar pixels com z fora 
do range válido 229
Rasterizando Triângulo
230
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥 , 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥 , 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
𝐩z = 𝛼𝐚z + 𝛽𝐛z + 𝛾𝐜z
if 𝐩z < zbuffer[x,y] and 𝐩z < far_plane
draw pixel at (x,y) with color 𝐩color
zbuffer[x,y] = 𝐩z
for all (x,y)
zbuffer[x,y] = ∞
c
b
a
Rasterizando Triângulo
231
for (x,y) in region
𝛼 = 𝑓𝐛𝐜 𝑥, 𝑦 /𝑓𝐛𝐜(𝑎𝑥 , 𝑎𝑦)
𝛽 = 𝑓𝐜𝐚 𝑥, 𝑦 /𝑓𝐜𝐚(𝑏𝑥 , 𝑏𝑦)
𝛾 = 𝑓𝐚𝐛 𝑥, 𝑦 /𝑓𝐚𝐛(𝑐𝑥 , 𝑐𝑦)
if 𝛼 > 0 and 𝛽 > 0 and 𝛾 > 0
𝐩color = 𝛼𝐚color + 𝛽𝐛color + 𝛾𝐜color
𝐩z = 𝛼𝐚z + 𝛽𝐛z + 𝛾𝐜z
if 𝐩z < zbuffer[x,y] and 𝐩z < far_plane
draw pixel at (x,y) with color 𝐩color
zbuffer[x,y] = 𝐩z
for all (x,y)
zbuffer[x,y] = ∞
c
b
a
Perguntas?232