Upload
internet
View
136
Download
0
Embed Size (px)
Citation preview
Linha de produção de imagens com o OpenGL™
(OpenGL Rendering Pipeline)
Cena Virtual
objetos geométricosluzescâmeras
xe
ye
ze
xo
yo
zo
Complexidade do Algoritmo de Rastreamento de Raios
Para cada pixel da telaDefina um raio
Para cada objeto da cenaCalcule o objeto visível
Para cada luz da cenaLance um raioPara cada objeto da cena
Teste se o objeto faz sombraCalcule sua iluminação
Complexidade maior que O(num. de pixels num. de objetos2)
Uma outra forma de menor complexidade
Calcule a cor de cada vertice Projete cada vertice
Preencha o triângulo dos vértices projetados
ze
xe
ye
Macro passos da linha de produção de imagens
Aplicação Geometria Rastreio
Transformações do modelo e de câmera
Iluminação
Projeção
Recorte
Mapeamento para tela
Conversão vetorial matricial
Operações de fragmentos
Mapas de cor e profundidade
Extração da posição, forma e aparência dos objetos na resolução
adequada
Descarte dos objetos fora do campo de
visão
Cinemática dos objetos e testes de
colisão
Um objeto em vários níveis de detalhe
Multi-resolução num mesmo objeto
Descarte de objetos fora do campo de visão
Descarte por planos oclusores
Instanciação de objetos na cena
- OpenGL Model View -
Instânciação de objetos
Instânciação de objetos- vários sistemas de coordendas -
x2y
z2
xz
y2x4
y4
z4
x6
x1
y1
z1
x3
y3
z3
x5 z5
y5d1
d2
Objetos posicionados diretamente
x
zy
Objetos posicionados diretamente
Tipos de primitivas gráficas do OpenGL
GL_POINTS
01
2
GL_LINES
0
1
2
3 5
4
GL_LINE_STRIP
0
1
2
3
GL_LINE_LOOP0 1
234
GL_POLYGON
04
3
21
GL_QUADS
03
21
4 7
65
GL_QUAD_STRIP
0
31
2 4
5
GL_TRIANGLES
0
1
2
34
5
GL_TRIANGLE_STRIP
1
02
3
4
5
GL_TRIANGLE_FAN
0
1
4
23
Projeção Cônica (Perspective)
aspect = w/h
void gluPerspective( GLdouble fovy, GLdouble aspect, GLdouble near_, GLdouble far_ );
xe
ye
ze
near
far
w
h
ye
ze
fovy
Projeção Cônica (Frustum)
near
ye
zefar
top
botton
xeze
near
left right
far
void glFrustum(GLdouble left,GLdouble right,GLdouble bottom, GLdouble top, GLdouble near_, GLdouble far_ );
Obs.: near e far são distâncias( > 0)
view frustum
zexe
ye
eye
Glu Look At
Dados: eye, center, up (definem o sistema de coordenadas do olho)
Determine a matriz que leva do sistema de Coordenadas dos Objetospara o sistema de Coordenadas do Olho
void gluLookAt(GLdouble eyex, GLdouble eyey, GLdouble eyez, GLdouble centerx, GLdouble centery, GLdouble centerz, GLdouble upx, GLdouble upy, GLdouble upz);
up eye
center
Coordenadas dosobjetos
Coordenadas doolho
eye
Calculo do sistema - xe ye ze
ye
center
eye
zo
yo
xo
zexe
up
centereyecentereye
z
1
e
ee
e zupzup
x
1
eee xzy
dados:eye, center, up
Translada o eye para origem
center
eye
zo
yo
xo
zexe
ye
zo
yo
xo
center
eye
zexe
ye
1000
100
010
001
z
y
x
eye
eye
eye
T
Roda xe ye ze para xw yw zw
xe , xo
ye , yo
ze , zo
1000
0
0
0
ezeyex
ezeyex
ezeyex
zzz
yyy
xxx
R
zo
yo
xo
center
eye
ze
xe
ye
Matriz LookAt do OpenGL
11 0
eyeI
0
0R
1000
100
010
001
1000
0
0
0
z
y
x
exexex
eyeyex
ezeyex
at eye
eye
eye
zzz
yyy
xxx
RTL
1000
100
010
001
z
y
x
eye
eye
eye
T
centereyecentereye
z
1
e
ee
e zupzup
x
1
eee xzy
1000
0
0
0
exexex
eyeyex
ezeyex
zzz
yyy
xxx
R
10
eyeRR
Cor dos vértices
luzes
n
sb
sg
sr
b
g
r
db
dg
dr
b
g
r
db
dg
dr
ab
ag
ar
b
g
r
k
k
k
l
l
l
k
k
k
l
l
l
k
k
k
I
I
I
I
I
I
vrLn ˆˆˆˆ
xe
ye
ze
L̂
n̂r̂
v̂
Projeção
Simplificação da projeção cônica
Projeção cônica
plano de projeçãoeye
direção de projeção
plano de projeção
Projeção ortográfica
Projeção cônica simples
ye
zepp
xeze
n
y e
z e
xe
xp
ye
yp
-ze
-zeye
yp n=
n yeyp -ze=
n
e
e
e
z
y
x
p
e
e
e
ep
p
p
p
z
y
x
z
n
z
y
x
p
e
e
e
ep
p
p
p
z
y
x
z
n
z
y
x
p
xexp -ze=
n
xe
xp
-ze=
n
n
xe
Projeção cônica simples
e
e
e
e
e
e
e
p
p
p
z
nz
ny
nx
z
y
x
n
n
n
w
wz
wy
wx
10100
000
000
000
ye
zepp
e
e
e
z
y
x
p
e
e
e
ep
p
p
p
z
y
x
z
n
z
y
x
p
e
e
e
ep
p
p
p
z
y
x
z
n
z
y
x
p
nxe
e
e
e
ep
p
p
nz
ny
nx
zz
y
x1
Distorce o frustum de visão para o espaço da tela
xe
ye
ze
ze = -n
ze = -f
1
2
3
4
5
6
7
8
xe
ye
ze
ze = -n ze = -f
1
2
3
4
56
7
8
?H
Transformação projetiva- a origem vai para o infinito em z+ -
133323130
23222120
13121110
03020100
i
i
i
i
ii
ii
ii
z
y
x
mmmm
mmmm
mmmm
mmmm
w
zw
yw
xw
0
0
0
1
0
0
0
33
23
13
03
33323130
23222120
13121110
03020100
1
0
0
0
0
0
0
m
m
m
m
mmmm
mmmm
mmmm
mmmm
0
0
0
323130
222120
121110
020100
mmm
mmm
mmm
mmm
P
Transformação projetiva- os pontos do plano z =–n ficam imóveis -
Ryxn
y
x
n
y
x
,
1
Ryx
nmymxm
nmymxm
nmymxm
nmymxm
n
y
x
mmm
mmm
mmm
mmm
n
y
x
,
10
0
0
323130
222120
121110
020100
323130
222120
121110
020100
nmymxmx 020100
0, 121011121110 mmmnmymxmy
0, 212022222120` mmn
mnmymxmn
0, 313032323130 mmn
mnmymxm
0, 020100 mmm
Transformação projetiva- matriz P com estas condições -
000
00
000
000
n
n
H
Transformação projetiva- condição sobre os pontos do plano z = –f -
Ryx
f
yf
n
xf
n
f
y
x
,
1
Ryx
n
fn
ff
y
x
f
y
x
n
nf
yf
n
xf
n
,
1000
00
000
000
f
n
nfn
ff
1
Transformação projetiva- condição sobre os pontos do plano z = –f -
01
00
00
000
000
f
nf
nf
nf
n
P
f
0100
00
000
000
fnfn
n
n
H
Resumindo
[ P ] = ?
xe
ye
ze 12
34
5
6
7
8
xe
ye
ze 12
34
5 6
78
0100
00
000
000
nffn
n
n
H
xe
ye
ze
Outro enfoque: distorce o frustum de
visão para o espaço da tela
ze = -n ze = -f
xe
ye
ze
ze = -n
ze = -f
d = n
0100
00
000
000
ba
n
n
H
Uma equação para profundidade
n
ban Ptos no near (z=-n):
f
baf Ptos no far (z=-f):
nfb
nfa
[ H ] =
n
0
0
0
0
n
0
0
0
0
n+f
-1
0
0
n f
0
z
baz
Transforma o prisma de visão cubo normalizado [-1,1]×[-1,1] ×[-1,1]
xe
ye
ze
lr
b
t
xe
ye
ze
-(r-l)/2
(r-l)/2
-(t-b)/2
(t-b)/2
(f-n)/2 -(f-n)/2
1000
2/)(100
2)(010
2)(001
nf
bt
lr
T
xe
ye
ze
111
-1-1-1
far
near
1000
0)(200
00)(20
000)(2
nf
bt
lr
S
xn
yn
zn
111
-1-1-1
near
far
1000
0100
0010
0001
M
Matriz Frustum do OpenGL
1000
2/)(100
2)(010
2)(001
nf
bt
lr
T
1000
0)(200
00)(20
000)(2
nf
bt
lr
S
1000
0100
0010
0001
M
0100
00
000
000
nffn
n
n
H
0100
2)(00
02
0
002
nf
fn
nf
nfbt
bt
bt
nlr
lr
lr
n
NHP
OpenGL Spec
1000
2/)(100
2)(010
2)(001
1000
0)(200
00)(20
000)(2
1000
0100
0010
0001
nf
bt
lr
nf
bt
lr
N
Resumo das transformações (até o momento)
xe
ye
ze
center
eye
zo
yo
xo
up
xn
yn
zn
w
z
y
x
c
c
c
110
0
0
z
y
x
z
y
x
viewe
e
e
M
1e
e
e
c
c
c
z
y
x
w
z
y
x
P
w
z
y
x
wz
y
x
c
c
c
n
n
n1
ze
Projeção Paralela(Ortho)
xe
ye
leftright
bottom
top near far
void glOrtho( GLdouble left, GLdouble right, GLdouble bottom, GLdouble top, GLdouble near_, GLdouble far_ );
void gluOrtho2D( GLdouble left, GLdouble right, GLdouble bottom, GLdouble top );
eye
direção de projeção
Matriz Ortho do OpenGL
OpenGL Spec
1000
200
02
0
002
nf
nf
nf
bt
bt
bt
lr
lr
lr
MST
1000
2/)(100
2)(010
2)(001
nf
bt
lr
T
1000
0)(200
00)(20
000)(2
nf
bt
lr
S
1000
0100
0010
0001
M
Requisitos de uma câmera de uma estação de Realidade Virtual
Recorte
Diferentes problemas de recorte
Condição de pertinência
1n
2n
3n4n
5n
p é interior
p
ii 0pn
01 pn
01 pn
01 pn 01111 dzcybxa
0
11
1
1
1
z
y
x
d
c
b
a
Interseção de aresta × hiperplano
n
1p
2p
11 pnd
22 pndip
121
22
21
1 pppdd
d
dd
di
intercepta 021 dd
segmento de retaou aresta
hiperplano
121
22
21
1 pppdd
d
dd
di
Recorte de segmentos com base no algoritmo Cohen-Sutherland
A
BC
D
Casos de clipping de linhas
A
B
C
E
(x1, y1)
(x2, y2)
D
(x’1, y’1)
(x’2, y’2)
Códigos das regiões
1001 1000 1010
0001 0000 0010
0101 0100 0110
tbrl
Cálculo do código de um vértice
unsigned char code(double x, double y, double xmin, double xmax, double ymin, double ymax){ unsigned char code=0; if (y > ymax) code += 8; if (y < ymin) code += 4; if (x > xmax) code += 2; if (x < xmin) code += 1; return code;}
1001 1000 1010
0001 0000 0010
0101 0100 0110
tbrl
void CohenSutherlandLineClip(double x0, double y0, double x1, double y1, double xmin, double xmax, double ymin, double ymax) { unsigned char outcode0, outcode1, outcodeOut; double x, y; boolean accept = FALSE, done = FALSE;
outcode0 = code(x0, y0, xmin, xmax, ymin, ymax); outcode1 = code(x1, y1, xmin, xmax, ymin, ymax);
do { if (outcode0 == 0 && outcode1 == 0) { accept = TRUE; done = TRUE; /* trivial draw and exit */ } else if((outcode0 & outcode1) != 0) { done = TRUE; /* trivial reject and exit */ } else { /* discart an out part */ outcode = (outcode0 != 0) ? outcode0 : outcode1; /* pick an out vertice */ if (outcodeOut & 8) { /* discart top */ x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0); y = ymax; } else if(outcodeOut & 4) { /* discart bottom */ x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0); y = ymin; } else if(outcodeOut & 2) { /* discart right */ y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0); x = xmax; } else if(outcodeOut & 1) { /* discart left */ y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0); x = xmin; } if (outcodeOut == outcode0) { x0 = x; y0 = y; outcode0 = code(x0, y0, xmin, xmax, ymin, ymax); } else { x1 = x; y1 = y; outcode1 = code(x1, y1, xmin, xmax, ymin, ymax); }
} } while (!done);
if (accept) DrawLineReal(x0, y0, x1, y1);}
Algoritmo deCohen & Sutherland
Algoritimo de Cyrus-Beck(Liang-Barsky)
PEi
N Ei
P0 P1
P t P P P t 0 1 0( )
N P t PEi Ei 0
)(tP
Algoritimo de Cyrus-Beck(Liang-Barsky)
PEi
N Ei
P0 P1
P t P P P t 0 1 0( )
0 EiEi PtPN
N P t PEi Ei 0 N P t PEi Ei 0
N P t PEi Ei 0
tN P P
N P PEi Ei
Ei
0
1 0
Entrando ou Saindo ?
P0P1
Ei
N Ei
N P P PEEi 1 0 0
P0
P1
Ei
N Ei
N P P PLEi 1 0 0
Recorte de segmentos com base no algoritmo de Cyrus-Beck
C
B
Ate
tete
ts
ts
te
te
ts
ts
ts
ts
te
n
n
n
n
Cyrus-Beck - caso geral
{ Calcule Ni e escolha um PEi para cada aresta
tE = 0; tL = 1; for (cada aresta ){ if (Ni.(P1-P0)!=0 ){ /* aresta não é paralela ao segmento */ calcule t; use sign of Ni.(P1-P0) para categorizar como PE ou PL; if( PE ) tE = max(tE, t); if( PL ) tL = min(tL, t); } else { /* aresta paralela ao segmento */ if (Ni.(P0-PEi) > 0) /* está fora */ return nil; } if (tE > tL) return nil; else return P(tE) and P(tL) as true clip intersections; } }}
Liang e Barsky- caso particular -
Ei NEi PEi t
left: x = xmin (-1, 0) (xmin, y)-(x0-xmin)(x1-x0)
right: x = xmax (1, 0) (xmax, y)(x0-xmax)-(x1-x0)
bottom: y = ymin (0,-1) (x, ymin)-(y0-ymin)(y1-y0)
top: y = ymax (0, 1) (x, ymax)(y0-ymax)-(y1-y0)
xmin xmax
ymin
ymax
x
y
Liang e Barsky- Cálculo da interseção em uma fronteira -
boolean Clipt(double den, double num, double *tE, double *tL){ double t; if (den > 0) /* intersecao PE */ { t = num/den; if (t > *tL) /* tE > tL */ return FALSE; else if (t > *tE) *tE = t; } else if (den < 0) /* intersecao PL */ { t=num/den; if (t < *tE) /* tL < tE */ return FALSE; else if (t < *tL) *tL = t; } else if (num > 0) /* linha esta fora */ return FALSE; } return TRUE;}
Algoritimo de Liang e Barsky
boolean Clip2D(double *x0, double *y0, double *x1, double *y1, double xmin, double max, double ymin, double ymax){ double dx = *x1 - *x0; double dy = *y1 - *y0; boolean visible = FALSE; if (dx==0)&&(dy==0)&&ClipPoint(*x0,*y0,xmin,xmax,ymin,ymax) visible=TRUE; else { double tE=0.0, tL=1.0;
if ( Clipt(dx,xmin-*x0,&tE,&tL) ) if ( Clipt(-dx,*x0-max,&tE,&tL) ) if ( Clipt(dy,ymin-*y0,&tE,&tL) ) if ( Clipt(-dy,*y0-ymax,&tE,&tL) ) { visible=TRUE; if (tL<1.0) { (*x1)=(*x0)+tL*dx; (*y1)=(*y0)+tE*dy; } if (tE>0.0) { (*x0)=(*x0)+tE*dx; (*y0)=(*y0)+tE*dy; } } } return visible;}
Recorte de polígonos com base no algoritmo de Hodgman-Sutherland
Clip contra uma aresta (plano) de cada vez
Classificação de um segmento contra um hiperplano no algoritmo de Hodgman-Sutherland
Saída: pSaída: p Saída: iSaída: i Saída: i, pSaída: i, p
interno saindo externo entrando(a) (b) (c) (d)
• Para cada aresta (hiperplano) da região de recorte•Para cada segmento do polígono
• Existem quatro casos possiveis para um vértice e seu antessessor
s
p
s
p
sp i
s pi
Exemplo do algoritmo de Hodgman-Sutherland
1 5
A B
CD E
F1
32
45
6A B
CD
1 45
A BCD E
F
s p saída
1 2 A
2 3
3 4 B e 4
4 5 5
5 6 C
6 1 D e 1
s p saída
A B B
B 4 E
4 5 F e 5
5 C C
C D D
D 1 1
1 A A
Clipping de polígonos(Exemplo 1)
1
23
4
56
A
B
S P Ação
1 2 x
2 3 store A,3
3 4 store 4
4 5 store 5
5 6 store B
6 1 x
Clipping de polígonos(Exemplo 2)
1
S P Ação1 2 store A2 3 x3 4 store B,44 5 store 55 6 store C6 1 store D,1
32
45
6A B
CDx x x x
1 45
BCDA
Clipping de polígonos(Exemplo 2)
1
S P Ação
1 A store 1, A
A B store BB 4 store E4 5 store F,55 C store CC D store D
45
A B
CDx x x x
E
F
x
x
D 1 x
B, E, F, 5, C, D, 1, AB, E, F, 5, C, D, 1, A
Clipping de polígonos(Concatenação de planos)
1
AB
45C
1 45
A B
CDx x x x
E
F
x
x
D
1, A, B, E, F, 5, C, D1, A, B, E, F, 5, C, D
12
3 4 5 6
1
32
45
6A B
CDx x x x
1 5
A B
CDx x x x
E
F
x
x
first[0]S[0]P[0]
first[1]S[1]P[1]
APIs para definição de polígonosint npoints; double x[10],y[10];
FillPoly(npoints, x, y);
typedef struct { double x,y; } Point;
Point vertex[10];
FillPoly(npoints, vertex)
Begin(FILL); Vertex(30.,20.); Vertex(15.,18.); …End( );
void Vertex(double x, double y, double z) { ClipAtPlane( x, y, z);}
void End( );{ ClipAtPlane(xf,yf,zf); FillSavedPoly( );}
Recorte de polígono contra um plano
void ClipAtPlane( double x0, double y0, double x1, double y1, int plane ){ double d0 = Distance(x0,y0, plane); double d1 = Distance(x1,y1, plane);
if ((d0<0)^(d1<0)) { double t=d0/(d0-d1); SaveVertex(x0+t*(x1-x0),y0+t*(y1-y0),plane); } if (d1<=0.0) SaveVertex(x1,y1,plane);}
Saída: pSaída: p Saída: iSaída: i Saída: i, pSaída: i, p
interno saindo externo entrando(a) (b) (c) (d)
s
p
s
p
sp i
s pi
Recorte de polígono contra um plano
double Distance (double x, double y, int plane ){ switch( plane ) { case 0: return( x_min - x ); case 1: return( x - x_max ); case 2: return( y_min - y ); case 3: return( y - y_max ); } return( 0.0 );}
xmin xmax
ymin
ymax
x
y
Recorte de polígono contra um plano
void ClipVertex(double x, double y, int plane, int last){ static int first=1; static double x_first, y_first; static double x_previous, y_previous;
if (first) { x_first=x, y_first=y; first =0; } else if (!last) { ClipAtPlane(x_previous,y_previous,x,y, plane); } else { ClipAtPlane(x_previous,y_previous,x_first, y_first, plane); } x_previous=x; y_previous=y; }
Recorte de polígono contra um plano
void Begin(void){}
void Vertex(double x, double y) { int plane = 0; int last = 0; ClipVertex(x,y,plane,last);}
void End(void) { ClipVertex(0,0,0,1);}
Regiões de recorte do rendering pipeline
xe
ye
ze
center
eye
zo
yo
xo
up
xn
yn
zn
w
z
y
x
c
c
c
-1 xn 1 -1 yn 1 -1 zn 1
Problema do clipping no R3
w
1
1
1
1
1
1
0100
00
000
000
211 n
n
n
n
n
nnffn
n
n
Hpp
1
2
1
1
2
1
1
1
0100
00
000
000
222 fn
n
nfn
n
n
nnffn
n
n
Hpp
1p2p
xe
ye
ze
p1p2
xe
ye
ze
Escolhas dos hiperplanos do PR3
yn
1nx
1w
xc
0 wsewxc
0 wsewxc
-1 1
xn
cxw 0
0 cxw
0 cxw
0 cxw
cxwd
cxwd
cl xwd
OpenGL Spec
Cálculo das distâncias aos hiperplanos no PR3
double Distance (double x, double y, double z, double w, int plane ){ switch( plane ) { case 0: return( -w - x ); case 1: return( -w + x ); case 2: return( -w - y ); case 3: return( -w + y ); case 4: return( -w - z ); case 5: return( -w + z ); } return( 0.0 );}
n
1p
2p
11 pnd
22 pndip
hiperplano
121
22
21
1 pppdd
d
dd
di
intercepta 021 dd
121
22
21
1 pppdd
d
dd
di
Recorte de polígonos de Sutherland-Hodgman
void ClipAtPlane( double x, double y, double z, double w, int plane ){ double d = Distance(x, y, z, w, plane); /* Check whether it is the first point */ if( first[plane] ) { fx[plane]=x; fy[plane]=y; fz[plane]=z; fw[plane]=w; fd[plane]=d; first[plane]=0; } else if ((sd[plane] < 0)^(d < 0)) Intersect( x, y, z, w, plane, sd[plane], d );
/* Save as previous */ sx[plane]=x; sy[plane]=y; sz[plane]=z; sw[plane]=w; sd[plane]=d; /* Check whether it is a visible point */ if ( d <= 0.0 ) { if ( plane == LAST_PLANE ) SaveVertex( x, y, z, w ); else ClipAtPlane( x, y, z, w, plane+1 ); }}
static int first[]={1,1,1,1,1};static double fx[5],fy[5],fz[5],fw[5],fd[5];static double sx[5],sy[5],sz[5],sw[5],sd[5];
Teste de interseção com uma fronteira
void Intersect(double x, double y, double z, double w, int plane, double d1, double d2){ double t = d1 / (d1 - d2);
double xi = sx[plane] + t * (x - sx[plane]); double yi = sy[plane] + t * (y - sy[plane]); double zi = sz[plane] + t * (z - sz[plane]); double wi = sw[plane] + t * (w - sw[plane]); if( plane == LAST_PLANE ) SaveVertex( xi, yi, zi, wi ); else ClipAtPlane( xi, yi,zi, wi, plane+1 );}
Fechando o processo
void ClipClose( int plane ){ if ((sd[plane]<0)^(fd[plane]<0)) Intersect( fx[plane], fy[plane], plane, sd[plane], fd[plane] );
first[plane]=1; if( plane == LAST_PLANE ) FillSavedPolygon( ); else ClipClose( plane+1 );}
void ClipClose( int plane ){ if ((sd[plane]<0)^(fd[plane]<0)) Intersect( fx[plane], fy[plane], plane, sd[plane], fd[plane] );
first[plane]=1; if( plane == LAST_PLANE ) FillSavedPolygon( ); else ClipClose( plane+1 );}
Begin(FILL); Vertex(30.,20.); Vertex(15.,18.); …End( );
Begin(FILL); Vertex(30.,20.); Vertex(15.,18.); …End( );
Transformação para o viewport
xn
yn
zn
111
-1-1-1
void glViewport(int x0, int y0, int w, int h );
zw[0.. zmax], zmax = 2n-1 geralmente 65535
2
10
nw
xwxx
2
10
nw
yhyy
2
1max
nw
zzz
xw
yw
w
h
0
y0
x0
Mapa de profundidade
10100
2)(00
02
0
002
e
e
e
c
c
c
z
y
x
nf
fn
nf
nfbt
bt
bt
nlr
lr
lr
n
w
z
y
x
e
ec
zw
nf
fnz
nf
nfz
2
e
cn znf
fn
nf
nf
w
zz
12
-1
1
ze
zn
n=1n=10
n=30-f=-100
Mapa de profundidade
e
en znf
fn
nf
nf
w
zz
12
12,12 maxmax n
nw zzz
z
5.01
)(5.0
max
e
w
znf
fn
nf
nf
z
z
e
w
znf
fn
nf
nf
z
z 1
)(5.05.0
max
e
w
znf
nf
z
z
fn
nf 15.05.0
)(
max
5.05.0)(
max nfnf
zz
nf
fnz
w
e
nfnfnf
z
z
fnz
w
e
5.05.0)(max
fnfz
zfn
zw
e
)(max
112
2max
ew znf
fn
nf
nfzz
!!!39665534
65535,01.0,1000 max
ew zz
znf
Transformações de um vértice
OpenGL Spec
Modelo do Pintor
prof
undidad
e
z
ZBuffer: idéia básica
z
MATRIZ DEPROFUNDIDADES
ZBuffer - pseudo-código
void ZBuffer( void){ int x,y;
for (x=0; x<w; x++) { for (y=0;y<h; y++) { WritePixel(x,y, bck_color); WriteZ(x,y,far+1); } }
for (each primitive) { for (each pixel in the projected primitive) { double pz = z coordinate of the (x,y) pixel; if (pz <= ReadZ(x,y)) { WritePixel(x,y, color); WriteZ(x,y,pz); } } }
} /* Zbuffer */
void glEnable( GL_DEPTH_TEST );void glEnable( GL_DEPTH_TEST );
Rastreio de Polígonos e Linhas
Coordenadas de um ponto na janela(windows coordinate)
w=6 e h=5
ponto: (3,2)tamanho 1sem anti-alias ponto: (3,3)
tamanho 3sem anti-alias
21
21
w
w
y
x
y
x
OpenGL Spec
0.5 1.5 2.5 3.5 4.5 5.5
0.5
1.5
2.5
3.5
4.5
5.5
0 1 2 3 4 5
0
1
2
3
4
xw
yw
Critério geométrico para linhas horizontais, verticais e à 450
0 1 2 3 4 5
0
1
2
3
4
linha: (0,0),(4,0)linha: (5,1),(5,4)linha: (0,2),(3,5)
Critério geométrico de Bresenham (1965) para linhas
linha: (0,0),(5,2)
0 1 2 3 4 5
0
1
2
3
0 1 2 3 4 5
0
1
2
3
x dominante
1212 yyxx x dominante, um pixel por coluna
1212 yyxx y dominante, um pixel por linha
Critérios geométricos para linhas do OpenGL™
linha: (0,0),(5,2)
0 1 2 3 4 5
0
1
2
3
Bresenham (1965)OpenGL™ spec
0 1 2 3 4 5
0
1
2
3
Algoritmo simples de rastreio de linha(no primeiro octante)
#define ROUND(x) (int)floor((x)+0.5)
void linha(int x1, int y1, int x2, int y2){ float m = (y2-y1)/(x2-x1); float b = y1 - m*x1; float y; fragmento(x1,y1); while( x1 < x2 ) { x1++; y = m*x1 + b; fragmento(x1,ROUND(y)); }}
bmxy ii
11
12
12
mxyb
xx
yym
),( 11 yx
),( 22 yx
Podemos evitar a multiplicação?
0 1 2 3 4 5
0
1
2
3
Forma incremental do algoritmo simples de linha
void linha(int x1, int y1, int x2, int y2){ float m = (y2-y1)/(x2-x1); float b = y1 - m*x1; float y=y1; pixel(x1,y1); while( x1 < x2 ) { x1++; y += m; fragmento(x1,ROUND(y)); }}
bmxy ii
11
12
12
mxyb
xx
yym
),( 11 yx
),( 22 yx
bxmy ii 11
bmxy ii
myy ii 1
Podemos evitar o uso de ponto flutuante?
Equação implícita da reta
x1 x2
y1
y2
x
y
112
121
12
12 xxx
yyyx
xx
yyy
21
12
xx
yyn
F x y( , ) 0
F x y( , ) 0
cybxayxF ..),(
1121121212 xyyyxxxyyyxx
01121122112 xyyyxxyxxxyy
bmxy ii
11
12
12
mxyb
xx
yym
Equação básica do algoritmo do ponto médio para linhas
cybxayxF ..),(
e
ne
xp
yp
m
0),( mm yxF
xp+1 xp+2
yp+1/2
yp+1
yp+2
me
e
ne
e
ne
xp xp+1 xp+2
yp
myp+1/2
yp+1
yp+2mne
e
ne
0),( mm yxF
Algoritimo do ponto médio- redução para inteiros -
),(2),( yxFyxd
e
nemm
escolha
escolhaFd
0
0)(2)(
ecybxayxFd ppppnovo 2)(2)2(2),2(2 2
12
1
add antnovo 2
cybxayxFd ppppnovo 2)(2)2(2),2(2 23
23
badd antnovo 22 ne
ae 2
bane 22
e
ne
xp xp+1 xp+2yp
myp+1/2
yp+3/2mne
me
bacybxayxFdini 22)(2)1(2),1(2 21
0021
00
bad ini .2
ba
a
ne
e
2
2
Algoritimo do ponto médio para linhas- código C -
void linhaPM(int x1, int y1, int x2, int y2){ int a = y2-y1; int b = x1-x2; int d=2*a+b; /* valor inicial da var. decisao */ int incrE = 2*a; /* incremento p/ mover E */ int incrNE = 2*(a+b); /* incremento p/ mover NE */ fragmento(x1,y1);
while (x1<x2) { x1++; if (d<=0) /* escolha E */ d+=incrE; else { /* escolha NE */ d+=incrNE; y1++; } fragmento(x1,y1); }
}
Algoritimo do ponto médio para linhas com estilo - código C -
void linhaPM(int x1, int y1, int x2, int y2){ int a = y2-y1; int b = x1-x2; int d=2*a+b; /* valor inicial da var. decisao */ int incrE = 2*a; /* incremento p/ mover E */ int incrNE = 2*(a+b); /* incremento p/ mover NE */ int style[8]={1,1,0,0,1,1,0,0}; int k=1; fragmento(x1,y1); /* primeiro pixel */
while (x1<x2) { x1++; if (d<=0) /* escolha E */ d+=incrE; else { /* escolha NE */ d+=incrNE; y1++; } if (style[(++k)%8]==1) fragmento(x1,y1); }
}
Critério geométrico para rastreio de elipses
e
se
mme
mse
F(x,y) = 0
F
F
xF
y
x
F(x,y) = 0
45o
y
Rastreio de círculos
x=0,y=raio; fragmento(x,y);while (x<y) { x++; if (F(M)<0) escolha E; else escolha SE; fragmento(E ou SE);}
x
y
simetrias do círculo:cada ponto calculado define 8 pixels
e
se
mme
mse
F(x,y) = 0
x
y
45o
yx
Rastreio de polígonos
Conceito de interior num polígono qualquer (regra par-ímpar)
02
1
1
0
1
3
6
1
Preenchimento de polígonos
y
ys
x
0
1
2
3
4
0xi4
ymax
ymin
dados: {(x0,y0), (x1,y1), (x2,y2) (x3,y3), (x4,y4)}
acha ymax e ymin
Para cada y [ymax,ymin]
Para cada aresta calcula as interseções
ordena interseções
desenha linhas horizontais
vx= {xi1 , xi0 , xi4 , xi3}vx= {xi1 , xi0 , xi4 , xi3}
i0i1 i3i4
xi1 xi0 xi3
Interseção nos vértices
inclui vértices: i0-i1, i2-i3, i4-?
não inclui vértices: i0-?
x
y
ys
50
1
2 4
i0 i2
i3
0
i1 i4
3x
y
ys
50
1
2 4
i0 i2
i3
0
i1 i4
3x
y
ys
50
1
2 4
i0 i2
i3
0
i1 i4
3
Solução:
x
y
ys
50
1
2 4
i0
0
i4
3
ou
x
y
ys
50
1
2 4
i0 i2
i3
0
i1
3
Otimização do algoritmo de preenchimento: interpolação linear
,2,, 000 dxxdxxx
Interpolação linear na aresta
ys+1dy = 1
01
01
yy
xxdx
x
y
y0
y1
ys
x1x00 xi xi+1
,2,, 000 dccdccc
Otimizações do algoritmo de preenchimento: triângulos
0
1
2
3
4
5
6B
C
a
b
c
x
y A
Posições possíveis de um triângulo dado yA≥ yB ≥ yC
))(())(( ABACACAB yyxxyyxxbc
B
Ca
b
c
x
y A
0bc x
y
B
C
a
b
c
A
0bc
Rastreio de triângulo
B
C
a
b
c
x
y A
yC
yA
yB
xa xb
ys
B
Ca
b
c
x
y A
yC
yA
yB
xc xb
ys
Interpolação perspectiva
plano de projeção
zeye
Interpolação perspectiva
zeye
0P 00 zw
10)1()( swwssw
11 zw
10
10
)1(
)1(
)(
)()(
swws
ss
sw
ss
PPP
p
n=1
10)1()( ppp ttt
10)1()( PPP sss
1P
10
10
1
1
0
0
)1(
)1()1(
swws
ss
wt
wt
PPPP
0p
1p
)()( ts pp 10
1
)1( swws
swt
01
0
)1( twwt
tws
Interpolação de atributos
1)1( sIIsI o
101
0
01
0
)1()
)1(1( I
twwt
twI
twwt
twI o
01
1001
)1(
)1(
twwt
ItwIwtI
01
0
)1( twwt
tws
10
1100
11)1(
)1(
wtwt
wItwItI
OpenGL Spec
Interpolação de atributos homogêneos
1
1
)1(
)1(
sqqs
suus
q
u
o
o
101
0
01
0
101
0
01
0
)1()
)1(1(
)1()
)1(1(
qtwwt
twq
twwt
tw
utwwt
twu
twwt
tw
q
u
o
o
01
0
)1( twwt
tws
1001
1001
)1(
)1(
qtwqwt
utwuwt
q
u
1100
1100
)1(
)1(
wqtwqt
wutwut
q
u
OpenGL Spec
Suavização da tonalização
c1 c4
c2
c3
c12 c43c
Gouraud void glShadeModel (GL_FLAT);
void glShadeModel (GL_SMOOTH);
Interpolação da profundidade
1)1( szzsz o
101
0
01
0
)1()
)1(1( z
tzzt
tzz
tzzt
tzz o
01
01
01
1001
)1()1(
)1(
tzzt
zz
tzzt
ztzzztz
01
0
)1( twwt
tws
01
0
)1( tzzt
tzs
10
11)1(
1
zt
zt
z
Uma outra forma de ver a interpolação da profundidade
z
yy
z
e
en znf
fn
nf
nf
w
zz
12
z
y
-1
-n -f
-1
ezez
Algortimo de ZBuffer
void ZBuffer( void){ for (cada primitva gráfica dos objetos da cena) { for (cada fragmento gerado pelo rastreio da primitiva) { if (o fragmento não pertencer a janela) break; /* pertinencia */ if (o fragmento não pertencer ao retangulo de janela de recorte) break; /* scissor test */ if (a profundidade do fragmento for maior que a corrente) break; /* profundidade */ . . . WritePixel(x,y, color); WriteZ(x,y,pz); } } }
}
Exercício 1
zexe
ye
eye
xeze
near
left right
far
near
ye
far
topbotton
ze
Derive a matriz de projeção da seguinte câmera
FIM
Cor e iluminação
Luzes
Pipeline visualizaçãoou Cadeia de rendering
BSP
Partição Binária do Espaço
(Binary Space Partition)
Modelo do Pintor
prof
undidad
e
z
Problemas na ordenação de faces
+ +
zazb
(a)
(b)
BSP trees: Binary Space Partion Trees
1
23
4
5a5b
3
12
5a
45b
atrásfrente
1
23
4
5a5b
3
45b
atrásfrente
2frente atrás
5a 1
1
23
4
5a5b
3
2
5a 1
4
5b
Exibição de uma BSP
void bspDisplay(bspTree *tree){ if (arvore não é vazia) { if (observador está a frente da raiz) { bspDisplay(treebackChild); DisplayPolygon(treeroot); bspDisplay(treefrontChild); } else { bspDisplay(treefrontChild); DisplayPolygon(treeroot); bspDisplay(treebackChild); } }}
Mostra a árvore detrás, a raiz e a árvoreda frente.
Mostra a árvore dafrente, a raiz e a árvorede atrás.
BSP trees: Dois exemplos de exibição
1
23
4
5a5b
3
2
5a 1
4
5b
5a, 2, 1, 3, 5b, 45a, 2, 1, 3, 5b, 4
1
23
4
5a5b
3
2
5a 1
4
5b
4, 5b, 3, 5a, 2, 14, 5b, 3, 5a, 2, 1
Sistema de Coordenadas do Modelo
OpenGL: Linha de produção de imagens
Câmera
O
Equação de um plano
N=(A,B,C)
P=(x,y,z)
x
y
z
P0
N.P = N.(P0 + P) = N.P0 = d N.P = N.(P0 + P) = N.P0 = d
P
d = Ax + By + Cz d = Ax + By + Cz
d
N.P = Ax + By + Cz N.P = Ax + By + Cz
Ax + By + Cz +D = 0Ax + By + Cz +D = 0
(A, B, C) = NeD = -d = N.(-P0 )
(A, B, C) = NeD = -d = N.(-P0 )
O
Distância de um ponto a um plano
N=(A,B,C)
P=(x,y,z)
Pp
x
y
z
P N.P = Ax + By + Cz N.P = Ax + By + Cz
N.P = Ax + By + Cz+D N.P = Ax + By + Cz+D
N.Pp = d = -D N.Pp = d = -D
N. P = N.P - N.Pp N. P = N.P - N.Pp
Interseção de reta com plano
P1
P2
x
y
z
d1 = Ax1 + By1 + Cz1+D
d1
d2
d2 = Ax2 + By2 + Cz2+DP
P =d1 P2 - d2 P1
d1 - d2
Projeção de Vértices
xh
yh
zh
w
xyz1
m11 m12 m13 m14
m21 m22 m23 m24
m31 m32 m33 m34
m41 m42 m43 m44
=
P
P’
z
x
y
P
xyz
=
P’ =
x’y’z’
xh /wyh/wzh/w
=
xd
yd
zd
111
-1-1-1
near
far
Clipping em coordenadas homogêneas
x[left, right]y
-1 xh/w 1
-1 1
x
xh/w 1
xh w , se w>0 xh w , se w>0
xh w , se w<0 xh w , se w<0
OpenGL Spec
Região de recorte no espaço normalizado
-1 xh/w 1 -1 yh/w 1 -1 zh/w 1
-1 xn 1 -1 yn 1 -1 zn 1
x[left, right] y[bottom, top]z[near, far]
xn
yn
zn
111
-1-1-1
nearfarright
left
bottom
top
Mapa de profundidade
10100
2)(00
02
0
002
e
e
e
c
c
c
z
y
x
nf
fn
nf
nfbt
bt
bt
nlr
lr
lr
n
w
z
y
x
e
ec
zw
nf
fnz
nf
nfz
2
e
en znf
fn
nf
nf
w
zz
12
30n
10n
1n
ez-n -f
nz
-1
-1
ez
100f
Efeito de profundidade
x
y
x
y
Critério geométrico de Bresenham (1965) para linhas
x = 5, y =3