View
5
Download
1
Category
Preview:
Citation preview
Recorte
Edward Angel, Cap. 7
Apontamentos CG
1
Pergunta (teste) Considere o triângulo ABC ilustrado na figura abaixo e definido
pelos pontos A = [5 5]T, B = [20 10] T e C = [5 15]T. Para efeitos
do cálculo do sombreamento de Phong, sabe que as normais nos
três vértices do triângulo ABC são dadas pelos vectores𝑛𝐴 = −0.2 −0.4 0.3 𝑇, 𝑛𝐵 = 0.2 0.0 0.6 𝑇e 𝑛𝐶 = 0.0 0.4 0.3 𝑇 .
a) Indique o valor da normal no ponto P = [10 10]T. Note que este
vector deve estar normalizado. 2
Pergunta (teste) 𝑛𝐴 = −0.2 −0.4 0.3 𝑇, 𝑛𝐵 = 0.2 0.0 0.6 𝑇e 𝑛𝐶 = 0.0 0.4 0.3 𝑇 .
b) Sabendo que existe apenas uma fonte de luz, calcule a valor
do halfway vector nesse ponto, tendo em conta que
𝑙 = 02
2
2
2
𝑇
e 𝑣 = 0 −2
2
2
2
𝑇
.
3
Pergunta (teste) 𝑛𝐴 = −0.2 −0.4 0.3 𝑇, 𝑛𝐵 = 0.2 0.0 0.6 𝑇e 𝑛𝐶 = 0.0 0.4 0.3 𝑇 .
c) Calcule a componente azul da cor desse ponto P, tendo em
conta que existe apenas uma fonte de luz direccional, não
existe luz ambiente global nem atenuação atmosférica, e que o
material e as componentes da fonte de luz são definidos
conforme indicado na pergunta anterior.4
Back-Face CullingRemoção de Faces Traseiras e Recorte
5
Faces Traseiras
Requisitos
Objecto é um poliedro sólido
• faces poligonais envolvem o volume
O interior não é exposto pelo recorte
Conclusão
Faces traseiras não são visíveis
Solução
Identificar faces traseiras
• Remover da cena
Faces Traseiras?
6
Faces Traseiras
Requisitos
Objecto é um poliedro sólido
• faces poligonais envolvem o volume
O interior não é exposto pelo recorte
Conclusão
Faces traseiras não são visíveis
Solução
Identificar faces traseiras
• Remover da cena
Faces Traseiras?
7
Identificar Faces Traseiras
Como identificar faces traseiras?
Calcular o ângulo entre a normal e a VPN?
V
N N
> 90o < 90o
Front-Face Back-Face
8
Identificar Faces Traseiras
Como identificar faces traseiras?
Usar produto interno
• Normal ao polígono (N)
• Vector de visualização (V)
< 0 Polígono visível
= 0 Arestas visíveis
> 0 Polígono invisível (back-face)
Cálculos em coordenadas de visualização (VRC)
V
N N
> 90o < 90o
Front-Face Back-Face
9
Identificar Faces Traseiras
Como identificar faces traseiras?
Usar produto interno ( N V > 0 back-face)
Cálculos em coordenadas da câmara (VRC)
É mesmo necessário calcular o produto interno?
Não!
• Basta verificar a componente Z da normal!! NZ > 0 back-face
V
N N
> 90o < 90o
Front-Face Back-Face
Z
10
Remover Faces Traseiras
Cena com um poliedro convexo
RSO fica completa com back-face culling
Em poliedros côncavos
Algumas front-faces podem estar
• totalmente ocultas (E)
• parcialmente ocultas (C)
x
z
A
B
C
D
E
F
G
H
11
Back-Face Culling
Remoção de faces traseiras
Remove (aprox.) metade dos polígonos
Limitações
Apenas funciona em • Modelos sólidos
Definidos com malhas poligonais
Para volumes não convexos• Apenas serve como passo de pré-processamento
É necessário usar outro algoritmo
Objectos definidos com outra representação:
• Convertidos em malhas poligonais
12
Pipeline de Visualização 3D
13
Pipeline de Visualização 3D
14
RecorteRemoção de Faces Traseiras e Recorte
15
Volume de Visualização
Sobre que volume de visualização é feito o recorte?
Volume Perspectivo (Frustum)?
Volume Ortogonal?
Volume Canónico Perspectivo?
Volume Canónico Ortogonal?
Onde estamos no pipeline 3D?
2º Andar, 3º Passo
• Recorte de Polígonos
Qual o volume de visualização
Que temos neste ponto?16
Recorte (1/3)
Usa volume canónico ortogonal
Paralelepípedo x,y,z [-1..1]
y
z
x
(-1, 1, 1)
(1, -1, 1)(1, -1, -1)
(-1, -1, -1)
(-1, 1, -1)
(-1, -1, 1)
(1, 1, 1)plano de recorte
anterior (z = -1)
plano de recorte
posterior (z = 1)
17
Recorte (2/3)
Elimina primitivas fora do volume canónico
Objectos, vértices, arestas e faces
18
Recorte (3/3)
Vértices:
Comparar
• x, y e z com +/- 1
Conservar se dentro dos limites, eliminar se fora
Arestas
Calcular intersecção com planos de recorte
Determinar valores x, y, z na intersecção
Conservar parte da aresta dentro do volume
Recorte 3D extensão “trivial” de recorte 2D
19
Recorte 2DRemoção de Faces Traseiras e Recorte
20
Recorte de Linhas
(xmin ≤ X ≤ Xmax) e (Ymin ≤Y ≤Ymax) ponto dentro
Extremos dentro [AB]: segmento dentro
Um fora outro dentro [CD]
Determinar ponto de intersecção [D’]
• Rejeitar exterior
Ambos fora [GH ou IJ]:
Determinar pontos de intersecção
• se houver [GH], usá-los
• rejeitar se não [IJ]
Rectângulo
de Recorte
A
B C
D
E
F
G
H
I
J
G´
D´F´
H´
I´
J´
Recorte
A
B C
G´
D´
H´
21
Recorte de Linhas: Força Bruta
Testar extremos contra rectângulo de recorte
Tratar os casos triviais de inclusão total
Casos não triviais:
• usar equação paramétrica da recta
Resolver equações simultâneas
• segmento de recta (tline)
• 4 lados do rectângulo (tedge)
Existe intersecção se:
X = X0 + t (X1 - X0)
Y = Y0 + t (Y1 - Y0)
0 tline 1 e 0 tedge 1
22
Algoritmo de Cohen-SutherlandRemoção de Faces Traseiras e Recorte
23
Algoritmo de Cohen-Sutherland (1/5)
Usa Outcodes
divide plano em 9 regiões
Casos triviais:
OC1= OC0 = 0000 => aceita
OC1 & OC0 0000 => rejeita (semiplano ext.)
0000
1000 10101001
0010
0100
0001
0101 0110
1º Bit: Acima do lado superior (Y > Ymax)
2º Bit: Abaixo do lado inferior (Y < Ymin)
3º Bit: À direita do lado direito (X > Xmax)
4º Bit: À esquerda do lado esquerdo (X < Xmin)
24
Algoritmo de Cohen-Sutherland (2/5)
Restantes Casos (OC1 & OC0 = 0)
Subdividir segmento inicial:
• Corte através de um lado da janela atravessado
• Partir de um extremo exterior
• Testar outcode para escolher próximo lado de recorte (bit a 1)
Descartar o fragmento exterior
Se fragmento interior
• trivialmente tratável
• o processo termina.
Caso contrário,
• subdividi-lo
• repetir o processo.
25
Exemplo
Algoritmo de Cohen-Sutherland (3/5)
Recorte de [AD]
Subdividir pelo lado superior [AB] e [BD].
Descartar fragmento exterior [BD].
Aceitar trivialmente [AB] (OCA = OCB = 0)
Rectangulo de Recorte
A
B
D
0000
0100
1001
0010
1000 1010
26
Algoritmo de Cohen-Sutherland (4/5)
Partir de E e subdividir por baixo [EF] e [FI]
Descartar [EF] [FI] não trivial
Subdividir [FI] pelo lado superior [FH] e [HI].
Descartar [HI] [FH] não trivial (OCH = 0010).
Subdividir [FH] pelo lado direito [FG] e [GH].
Descartar [GH] Aceitar [FG] (OCF = OCG = 0).
Exemplo
I
E
H
F
G
0000
0100
1001
0010
1000 1010
Rectangulo de Recorte
27
Recorte de PolígonosRecorte 2D
28
Recorte de Polígonos
29
Recorte de Polígonos
Lados do Polígono testados com arestas de recorte
Lados iniciais podem ser:
• trivialmente aceites, rejeitados ou subdivididos
Podem surgir novos lados
• colineares com arestas de recorte
O resultado final pode ser um ou mais polígonos
30
Recorte de Polígonos
31
Algoritmo de
Sutherland-Hodgman (1/4)
Abordagem “Dividir para Reinar”
Recortes sucessivos do polígono por aresta infinita
Quatro passos (um para cada aresta)
32
Algoritmo de
Sutherland-Hodgman (2/4)
Passo 1: Left Clip
Quatro passos (um para cada aresta)
Em cada passo:
Entrada = cadeia de vértices (V1, V2, …, Vn)
Resultado = nova cadeia de vértices (polígono recortado)
Resultado do passo N = Entrada do N+1
33
Algoritmo de
Sutherland-Hodgman (2/4)
Quatro passos (um para cada aresta)
Em cada passo:
Entrada = cadeia de vértices (V1, V2, …, Vn)
Resultado = nova cadeia de vértices (polígono recortado)
Resultado do passo N = Entrada do N+1
Passo 2: Top Clip
34
Algoritmo de
Sutherland-Hodgman (2/4)
Quatro passos (um para cada aresta)
Em cada passo:
Entrada = cadeia de vértices (V1, V2, …, Vn)
Resultado = nova cadeia de vértices (polígono recortado)
Resultado do passo N = Entrada do N+1
Passo 3: Right Clip
35
Algoritmo de
Sutherland-Hodgman (2/4)
Quatro passos (um para cada aresta)
Em cada passo:
Entrada = cadeia de vértices (V1, V2, …, Vn)
Resultado = nova cadeia de vértices (polígono recortado)
Resultado do passo N = Entrada do N+1
Passo 4 : Bottom Clip
36
Algoritmo de
Sutherland-Hodgman (3/4)
Executa o chamado “pipeline clipping”
Quatro andares de clipping
• Um para cada aresta
Pode-se aplicar o Cohen-Sutherland
• Aresta a aresta
Left
Clip Top Clip
Right
Clip
Bottom
Clip
37
Inserção de pontos
Algoritmo de
Sutherland-Hodgman (4/4)
Interior Exterior
S
P
Interior Exterior
S
P
Interior Exterior
S
PI
Interior Exterior
S
PI
Caso 1: Caso 2: Caso 3: Caso 4:
Inserir ponto P Inserir ponto I Não insere pontos Insere primeiro I
Insere depois P
Pode gerar falsos lados
(remover a posteriori)
38
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
39
P0
P1
P2
P3
P4
P5
P6
P7
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P0
P1P2
P4
P5
P6
P7
P3
Left
Clip
40
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P0
P1P2
P4
P5
P6
P7
Left Clip
[P0 P1] Não insere ponto
P3
P0
P1
P2
P3
P4
P5
P6
P7
41
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P0
P1P2
P4
P5
P6
P7
Left Clip
[P1 P2] Insere pontos I0 P2
P2I0
P3
P0
P1
P2
P3
P4
P5
P6
P7
I0
P2
42
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P0
P1P2
P4
P5
P6
P7
Left Clip
[P2 P3] Insere ponto P3
P2I0
P3 P3
P0
P1
P2
P3
P4
P5
P6
P7
I0
P2
P3
43
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P0
P1P2
P4
P5
P6
P7
Left Clip
[P3 P4] Insere ponto I1
P2I0
P3 P3
I1
P0
P1
P2
P3
P4
P5
P6
P7
I0
P2
P3
I1
44
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P0
P1P2
P4
P5
P6
P7
Left Clip
[P4 P5] Não insere ponto
P2I0
I2P3 P3
I1
P0
P1
P2
P3
P4
P5
P6
P7
I0
P2
P3
I1
45
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P0
P1P2
P4
P5
P6
P7
Left Clip
[P5 P6] Insere pontos I2 e P6
P2I0
P3 P3
I1
P0
P1
P2
P3
P4
P5
P6
P7
I0
P2
P3
I1
I2
P6
I2
P6
46
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P0
P1P2
P4
P5
P6
P7
Left Clip
[P6 P7] Insere ponto P7
P2I0
P3 P3
I1
P0
P1
P2
P3
P4
P5
P6
P7
I0
P2
P3
I1
I2
P6
P7
I2
P6
P7
47
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P0
P1P2
P4
P5
P6
P7
Left Clip
[P7 P0] Insere ponto I3
P2I0
P3 P3
I1
P0
P1
P2
P3
P4
P5
P6
P7
I0
P2
P3
I1
I2
P6
P7
I3
I2
P6
P7
I3
48
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P5
P6
P7
I1 P3
I0
P2
P3
I1
I2
P6
P7
I3
I2
I3
I0
Resultado
após
Left Clip
Top Clip
49
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P5
P6
P7
Top Clip
[I0 P2] Insere ponto P2
P2
I1 P3
I0
P2
P3
I1
I2
P6
P7
I3
P2
I2
I3
I0
50
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P5
P6
P7
Top Clip
[P2 P3] Insere ponto P3
P2
I1 P3
I0
P2
P3
I1
I2
P6
P7
I3
P2
P3I2
I3
I0
P3
51
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P5
P6
P7
Top Clip
[P3 I1] Insere ponto I1
P2
I1 P3
I0
P2
P3
I1
I2
P6
P7
I3
P2
P3
I1
I2
I3
I0
P3
I1
52
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P5
P6
P7
Top Clip
[I1 I2] Insere ponto I4
P2
I1 P3
I0
P2
P3
I1
I2
P6
P7
I3
P2
P3
I1
I4
I2
I3
I0
P3
I1
I4
53
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P5
P6
P7
Top Clip
[I2 P6] Insere pontos I5 e P6
P2
I1 P3
I0
P2
P3
I1
I2
P6
P7
I3
P2
P3
I1
I4
I5
P6
I2
I3
I0
P3
I1
I4
I5
P6
54
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P5
P6
P7
Top Clip
[P6 P7] Insere ponto I6
P2
I1 P3
I0
P2
P3
I1
I2
P6
P7
I3
P2
P3
I1
I4
I5
P6
I6
I2
I3
I0
P3
I1
I4
I5
P6
I6
55
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P5
P6
P7
Top Clip
[P7 I3] Não insere pontos
P2
I1 P3
I0
P2
P3
I1
I2
P6
P7
I3
P2
P3
I1
I4
I5
P6
I6
I2
I3
I0
P3
I1
I4
I5
P6
I6
56
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P5
P6
P7
Top Clip
[I3 I0] Insere pontos I7 e I0
P2
I1 P3
I0
P2
P3
I1
I2
P6
P7
I3
P2
P3
I1
I4
I5
P6
I6
I7
I0
I2
I3
I0
P3
I1
I4 = I7I5
P6
I6
I0
57
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P6I1 P3
I0
I4 = I7I5 I6
P2
P3
I1
I4
I5
P6
I6
I7
I0
Resultado
após
Top Clip
Right
Clip
P2
P6I1 P3
I0
I4 = I7I5 I6
P3
I1
I4
I5
P6
I6
I7
I0
P2
58
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
P2
P6I1 P3
I0
I4 = I7I5 I6
P3
I1
I4
I5
P6
I6
I7
I0
P2
Resultado
após
Right Clip
Bottom
Clip
P2
P6I1 P3
I0
I4 = I7I5 I6
I1
I4
I5
P6
I6
I7
I0
P2
P3
59
Algoritmo de
Sutherland-Hodgman (EXEMPLO)
60
Recorte 3DRecorte
61
Recorte em 3D (1/3)
Extensão do algoritmo de Cohen-Sutherland
Usar Outcode de 6 bits:
bit 1: ponto em frente VV (z < -1)
bit 2: ponto atrás VV (z > 1)
bit 3: ponto acima Volume de Visualização (y > 1)
bit 4: ponto abaixo VV (y < -1)
bit 5: ponto à direita VV (x > 1)
bit 6: ponto à esquerda VV (x < -1)
62
Recorte em 3D (3/3)
Quando Necessário, recorta segmentos em relação a
planos
64
Recorte em 3D (3/3)
Extensão algortimo de Cohen-Sutherland:
Aceitação trivial: OC1 = OC2 = 0
Rejeição trivial: OC1 & OC2 0
Calcular 6 intersecções recta-plano VV
x = x0 + t(x1 - x0)
y = y0 + t(y1 - y0)
z = z0 + t(z1 - z0), 0 ≤ t ≤ 1
Idêntico para recorte de polígonos
Sutherland-Hodgman
66
Pipeline de Visualização 3D
67
Pipeline de Visualização 3D
68
Pipeline de Visualização 3D
69
Pipeline de Visualização 3D
70
Pipeline de Visualização 3D
71
Pipeline de Visualização 3D
72
Próxima Aula
Discretização
Z-Buffer
Edward Angel, Cap. 6
Apontamentos CG
73
Recommended