1 Linha de produção de imagens com o OpenGL™ (OpenGL Rendering Pipeline)Computação Gráfica Interativa - Gattass 12/18/2017 Linha de produção de imagens com o OpenGL™ (OpenGL Rendering Pipeline) Modelo de Camera do OpenGL
2 Complexidade do Algoritmo de Rastreamento de Raiosxe ye ze xo yo zo Para cada pixel da tela Defina um raio Para cada objeto da cena Calcule o objeto visível Para cada luz da cena Lance um raio Teste se o objeto faz sombra Calcule sua iluminação Complexidade maior que O(num. de pixels num. de objetos2)
3 Uma outra forma de menor complexidadeye ze xe Calcule a cor de cada vertice Projete cada vertice Preencha o triângulo dos vértices projetados
4 Macro passos da linha de produção de imagensAplicação Geometria Rastreio Cinemática dos objetos e testes de colisão Transformações do modelo e de câmera Conversão vetorial matricial Iluminação Operações de fragmentos Extração da posição, forma e aparência dos objetos na resolução adequada Projeção e Recorte Mapas de cor e profundidade Descarte dos objetos fora do campo de visão Mapeamento para tela
5 Projeção
6 Simplificação da projeção cônicaComputação Gráfica Interativa - Gattass 12/18/2017 Simplificação da projeção cônica Projeção cônica plano de projeção eye Projeção ortográfica plano de projeção direção de projeção Modelo de Camera do OpenGL
7 Projeção cônica simplesye pp ze xe n xe z e n y xp ye yp -ze xe xp -ze = n -ze ye yp n = xe xp -ze = n
8 Projeção cônica simplesye pp ze xe n
9 Distorce o frustum de visão para o espaço da telaComputação Gráfica Interativa - Gattass 12/18/2017 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 5 6 7 8 Modelo de Camera do OpenGL
10 Transformação projetiva - a origem vai para o infinito em z+ -
11 Transformação projetiva - os pontos do plano z =–n ficam imóveis -
12 Transformação projetiva - matriz P com estas condições -
13 Transformação projetiva - condição sobre os pontos do plano z = –f -
14 Transformação projetiva - condição sobre os pontos do plano z = –f -
15 Resumindo [ P ] = ? xe ye ze 1 2 3 4 5 6 7 8
16 Outro enfoque: distorce o frustum de visão para o espaço da telaComputação Gráfica Interativa - Gattass 12/18/2017 Outro enfoque: distorce o frustum de visão para o espaço da tela xe ye ze ze = -n ze = -f d = n xe ye ze ze = -n ze = -f Modelo de Camera do OpenGL
17 Uma equação para profundidadePtos no near (z=-n): Ptos no far (z=-f): [ H ] = n n+f -1 n f
18 Transforma o prisma de visão cubo normalizado [-1,1]×[-1,1] ×[-1,1]Computação Gráfica Interativa - Gattass 12/18/2017 Transforma o prisma de visão cubo normalizado [-1,1]×[-1,1] ×[-1,1] xe ye ze -(r-l)/2 (r-l)/2 -(t-b)/2 (t-b)/2 (f-n)/2 -(f-n)/2 xe ye ze l r b t xn yn zn 1 -1 near far xe ye ze 1 -1 far near Modelo de Camera do OpenGL
19 Projeção Cônica (Frustum)void glFrustum(GLdouble left,GLdouble right,GLdouble bottom, GLdouble top, GLdouble near_, GLdouble far_ ); near ye ze far top botton xe ze near left right far view frustum ze xe ye eye xn yn zn 1 -1 near far
20 Matriz Frustum do OpenGLComputação Gráfica Interativa - Gattass 12/18/2017 Matriz Frustum do OpenGL OpenGL Spec Modelo de Camera do OpenGL
21 Resumo das transformações (até o momento)center eye zo yo xo up III. xe ye ze xn yn zn IV. I. II. entrada saída
22 Projeção Paralela (Ortho)Computação Gráfica Interativa - Gattass 12/18/2017 Projeção Paralela (Ortho) direção de projeção near ye top far bottom ze eye xe left right void glOrtho( GLdouble left, GLdouble right, GLdouble bottom, GLdouble top, GLdouble near_, GLdouble far_ ); void gluOrtho2D( GLdouble left, GLdouble right, GLdouble bottom, GLdouble top ); Modelo de Camera do OpenGL
23 Matriz Ortho do OpenGL OpenGL Spec
24 Transformação para o viewportComputação Gráfica Interativa - Gattass 12/18/2017 Transformação para o viewport void glViewport(int x0, int y0, int w, int h ); xw yw w h y0 x0 xn yn zn 1 -1 zw[0.. zmax], zmax = 2n-1 geralmente 65535 Modelo de Camera do OpenGL
25 Requisitos de uma câmera de uma estação de Realidade Virtual
26 Rastreio de Polígonos e LinhasComputação Gráfica Interativa - Gattass 12/18/2017 Rastreio de Polígonos e Linhas Modelo de Camera do OpenGL
27 Coordenadas de um ponto na janela (windows coordinate)w=6 e h=5 OpenGL Spec 1 2 3 4 5 xw yw 0.5 1.5 2.5 3.5 4.5 5.5 ponto: (3,2) tamanho 1 sem anti-alias ponto: (3,3) tamanho 3 sem anti-alias
28 Critério geométrico para linhas horizontais, verticais e à 4501 2 3 4 5 linha: (0,0),(4,0) linha: (5,1),(5,4) linha: (0,2),(3,5)
29 Critério geométrico de Bresenham (1965) para linhas1 2 3 4 5 1 2 3 4 5 x dominante x dominante, um pixel por coluna y dominante, um pixel por linha
30 Critérios geométricos para linhas do OpenGL™OpenGL™ spec Bresenham (1965) 1 2 3 4 5 1 2 3 4 5
31 Algoritmo simples de rastreio de linha (no primeiro octante)1 2 3 4 5 #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)); } Podemos evitar a multiplicação?
32 Forma incremental do algoritmo simples de linhavoid 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)); } Podemos evitar o uso de ponto flutuante?
33 Equação implícita da retay y2 y1 x x1 x2
34 Equação básica do algoritmo do ponto médio para linhasne xp xp+1 xp+2 yp m yp+1/2 yp+1 yp+2 mne e ne xp yp m xp+1 xp+2 yp+1/2 yp+1 yp+2 me
35 Algoritimo do ponto médio - redução para inteiros -ne xp xp+1 xp+2 yp m yp+1/2 yp+3/2 mne me e ne
36 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
37 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
38 Critério geométrico para rastreio de elipsesx F(x,y) = 0 45o y e se m me mse F(x,y) = 0
39 Rastreio de círculos y x F(x,y) = 0 45o e me m se mse x=0,y=raio;fragmento(x,y); while (x
40 Rastreio de polígonos
41 Conceito de interior num polígono qualquer (regra par-ímpar)2 6 1 1 3 1 1
42 Preenchimento de polígonosdados: {(x0,y0), (x1,y1), (x2,y2) (x3,y3), (x4,y4)} y ymax ymin 1 4 acha ymax e ymin Para cada y [ymax,ymin] Para cada aresta calcula as interseções ordena interseções desenha linhas horizontais ys i0 i1 i3 i4 xi1 xi0 xi3 2 3 x xi4 vx= {xi1 , xi0 , xi4 , xi3}
43 Interseção nos vérticesL L x y ys 5 1 2 4 i0 i2 i3 i1 i4 3 x y ys 5 1 2 4 i0 i2 i3 i1 i4 3 x y ys 5 1 2 4 i0 i2 i3 i1 i4 3 inclui vértices: i0-i1, i2-i3, i4-? não inclui vértices: i0-? ou x y ys 5 1 2 4 i0 i2 i3 i1 3 Solução: x y ys 5 1 2 4 i0 i4 3
44 Otimização do algoritmo de preenchimento: interpolação linearInterpolação linear na aresta x y y0 y1 ys x1 x0 ys+1 dy = 1 xi xi+1
45 Otimizações do algoritmo de preenchimento: triângulos1 2 3 4 5 6 B C a b c x y A
46 Posições possíveis de um triângulo dado yA≥ yB ≥ yCx y A x y B C a b c A
47 Rastreio de triângulo y y x x xa xb xc xb yA yA c c ys b b yB yB a ysyC yC C C xa xb x xc xb x
48 Profundidade
49 Mapa de profundidade -1 1 ze zn n=1 n=10 n=30 -f=-100
50 Mapa de profundidade
51 Transformações de um vérticeOpenGL Spec
52 Computação Gráfica Interativa - Gattass12/18/2017 Modelo do Pintor profundidade z Modelo de Camera do OpenGL
53 Problemas na ordenação de facesComputação Gráfica Interativa - Gattass 12/18/2017 Problemas na ordenação de faces (b) (a) + + za zb Modelo de Camera do OpenGL
54 Computação Gráfica Interativa - Gattass12/18/2017 ZBuffer: idéia básica z MATRIZ DE PROFUNDIDADES Modelo de Camera do OpenGL
55 ZBuffer - pseudo-códigovoid ZBuffer( void) { int x,y; for (x=0; x
56 Interpolação perspectivaComputação Gráfica Interativa - Gattass 12/18/2017 Interpolação perspectiva plano de projeção z eye Modelo de Camera do OpenGL
57 Interpolação perspectivaComputação Gráfica Interativa - Gattass 12/18/2017 Interpolação perspectiva z eye n=1 Modelo de Camera do OpenGL
58 Interpolação da profundidade
59 Uma outra forma de ver a interpolação da profundidadeComputação Gráfica Interativa - Gattass 12/18/2017 Uma outra forma de ver a interpolação da profundidade z y y z L -1 -n -f z y Modelo de Camera do OpenGL
60 Interpolação de atributosOpenGL Spec
61 Interpolação de atributos homogêneosOpenGL Spec
62 Suavização da tonalizaçãoComputação Gráfica Interativa - Gattass 12/18/2017 Suavização da tonalização Gouraud void glShadeModel (GL_FLAT); c1 c4 c2 c3 c12 c43 c void glShadeModel (GL_SMOOTH); Modelo de Camera do OpenGL
63 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); }
64 Exercício 1 ye ze xe ye ze xe zeDerive a matriz de projeção da seguinte câmera ze xe ye eye xe ze near left right far near ye far top botton ze
65 Resumo das transformações (até o momento)center eye zo yo xo up III. xe ye ze xn yn zn IV. I. II. entrada saída
66 Recorte
67 Diferentes problemas de recortelinhas polígonoss
68 Condição de pertinênciap é interior
69 Interseção de aresta × hiperplanosegmento de reta ou aresta hiperplano intercepta
70 Recorte de segmentos com base no algoritmo Cohen-Sutherland
71 Casos de clipping de linhasComputação Gráfica Interativa - Gattass 12/18/2017 Casos de clipping de linhas E (x1, y1) (x2, y2) D A C (x’1, y’1) (x’2, y’2) B Os problemas de recorte e seleção de linhas são mais complicados como ilustra a Figura. Dada uma linha definida de (x1,y1) até (x2,y2) ela pode: (a) estar totalmente fora da janela e não ser desenhada (casos A e B); ou (b) estar totalmente dentro da janela e ser desenhada (caso C); ou (c) estar parcialmente dentro da janela e precisar ser recortada para um sub-segmento que vai de (x’1,y’1) até (x’2,y’2) antes de ser desenhada (casos D e E). Modelo de Camera do OpenGL
72 Computação Gráfica Interativa - Gattass12/18/2017 Códigos das regiões 1001 1000 1010 0001 0000 0010 0101 0100 0110 O exemplo do desenho do mapa de municípios do Brasil mostra que em muitos casosos segmentos de reta estão totalmente acima, abaixo, a direita ou a esquerda da janela de interesse. Procurando tratar eficientemente estas situações, Cohen-Sutherland apresentaram um algoritmo que divide o plano de acordo com a janela em nove regiões mostradas na figura. Cada uma das regiões é classificada com um código de quatro valores lógicos que podem assumir os valores verdade (1) ou falso (0). São eles: (1) está acima; (2) está abaixo; (3) está a direita; e (4) está a esquerda. Cada segmento de reta tem dois vértices e cada vértice está em uma das nove regiões, logo um segmento tem dois códigos: um para o vértice 0 e outro para o 1. Estes códigos de podem ser armazenados numa variável tipo Outcode que em C do tipo: typedef struct { unsigned char all; unsigned char left; unsigned char right; unsigned char bottom; unsigned char top; } Outcode; A rigor só precisariamos de meio Byte para armazenar esta informação, mas para deixar o algoritmo mais simples de entender decidimos criar um código de 5 Bytes que é redundante. O campo all da estrutura contem todos os 4 códigos posicionados nos 4 últimos bits. Os campos left, right, bottom e top explicitam o valor de se a região está a esquerda, a direita, abaixo ou acima da janela de interesse. tbrl Modelo de Camera do OpenGL
73 Cálculo do código de um vérticeComputação Gráfica Interativa - Gattass 12/18/2017 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 O algoritmo da Figura determina o código de um vértice através da comparação de suas coordenadas (x,y) com as coordenadas da janela de interesse (xmin, xmax, ymin, ymax). Notem que o campo all é determinado com a adição de 1, 2, 4 ou 8 caso o ponto esteja acima, abaixo, a diretia e a esquerda, respectivamente. As constantes decimais 1, 2, 4, e 8 tem representação binária , , e e por isto a adição define corretamente a posição do vértice. Notem tambem que a codificação os valores das bordas são considerados interiores a janela de interesse. tbrl Modelo de Camera do OpenGL
74 Algoritmo de Cohen & Sutherlandvoid 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); Computação Gráfica Interativa - Gattass 12/18/2017 O algoritmo de Cohen e Sutherland se baseia em 3 princípios: Se uma reta estiver totalmente acima, abaixo, a direita ou a esquerda a janela ela pode ser descartada. Ou seja, não precisa ser desenhada pois não tem interseção com a janela. Se estiver dentro da janela ela pode ser denhada como ela é. Ou seja, não precisa ser recortada. Se descartamos pedaços do segmento que estão acima, abaixo, a direita ou a esquerda o problema não se altera. Ou seja, podemos trocar uma segmento de reta por um sub-segmento tirando fora partes que estão fora. As tres condições acima podem ser re-escritas como: Se o segmento estiver totalmente acima, abaixo, a direita ou a esquerda os códigos dos dois vétices terão necessariamente o valor 1 (verdadeiro) na fronteira correspondente. Se fizermos um AND lógico nos dois códigos eles produzirão um resultado diferente de zero. Inversamente, se o AND codigo a código também resultar em algum valor igual a 1 isto significa que os dois vértices estão ou acima, ou abaixo, ou a direita ou a esquerda da janela. Para implementar este teste de maneira eficiente codificamos as quatro condições no campo all. Se o segmento estiver totalmente dentro ambos os códigos dos vértices tem valor 0 (falso). Se um segmento tem, por exemplo, um vértice com código 1 na fronteira superior da janela podemos trocar este vértice por outro que fica no segmento e tem como ordenada y=ymax. Ou seja, se trocarmos as coordenadas do vértice para: x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0) y = ymax Estamos descartando a parte de fora do segmento. O mesmo raciocínio se aplica para as outras fronteiras. É importante notarmos que no caso de recorte de linhas o algoritmo precisa ajustar ambos os vértices para produzir o sub-segmento que é interior a janela. Quando o problema é de seleção, e não de recorte, o algoritmo pode ser simplificado para recortar apenas um lado do segmento. Ou seja, só um vértice precisa se mover. Se o segmento de reta tiver interseção com a janela de seleção qualquer um dos vértices vai ficar com todos os códigos 0 (falso) quando forem descartadas as partes externas. O algoritmo de seleção é um caso particular do algoritmo de recorte e é deixado come exercício para o leitor. Algoritmo de Cohen & Sutherland Modelo de Camera do OpenGL
75 Algoritimo de Cyrus-Beck (Liang-Barsky)Computação Gráfica Interativa - Gattass 12/18/2017 Algoritimo de Cyrus-Beck (Liang-Barsky) Uma outra estratégia para recorte de segmentos de reta contra uma janela de interesse foi apresentada por Cyrus e Beck. Esta estratégia se baseia na análise dos pontos de interseção da reta suporte do segmento com as retas da janela de interesse. Um ponto importante deste algoritmo é que a janela pode ser qualquer polígono convexo. A determinação do ponto de inteseção, P(t), da reta suporte do segmento P0P1 com a reta suporte de uma aresta que passa pelo ponto PEi e tem como normal o vetor NEi pode ser determinada através de: a condição do P(t) pertencer a reta suporte de P0P1: P(t) =P0 + (P1-P0) t a condição do vetor PEiP(t) ser ortogonal a NEi: NEi(P(t)-PEi)=0 Modelo de Camera do OpenGL
76 Algoritimo de Cyrus-Beck (Liang-Barsky)Computação Gráfica Interativa - Gattass 12/18/2017 Algoritimo de Cyrus-Beck (Liang-Barsky) Estas duas condições resultam na expressão de t dada na Figura. Quando os pontos P(t) da reta suporte do segmento que estão no lado positivo da normal temos: NEi(P(t)-PEi)>0 Quando est Modelo de Camera do OpenGL
77 Computação Gráfica Interativa - Gattass12/18/2017 Entrando ou Saindo ? Uma questão importante para o algoritmo é a determinação se o segment P0P1 está possivelmente entrando ou saindo da região. Se a normal das arestas apontar para fora, como mostra as figuras, ele estará entrando quando P0P1 tiver o sentido cotrário. Ou seja, NEi(P1 - P0)<0 Contrariamente ele estará saindo se NEi(P1 - P0)>0 Como a interseção é de retas suporte e não do segmento e da aresta em si, não podemos garantir que este ponto seja realmente um ponto de entrada ou saida da região. Na próxima Figura vemos casos onde a interseção se dá fora do segmento e/ou da areasta. Por isto a palavra “possivelmente”. Modelo de Camera do OpenGL
78 Recorte de segmentos com base no algoritmo de Cyrus-Beckts n C ts te n A ts ts ts te B ts n te te te te n
79 Cyrus-Beck - caso geralComputação Gráfica Interativa - Gattass 12/18/2017 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) else return P(tE) and P(tL) as true clip intersections; A Figura mostra um pseudo-código do algoritmo de Cyrus-Beck. Modelo de Camera do OpenGL
80 Liang e Barsky - caso particular -Computação Gráfica Interativa - Gattass 12/18/2017 Liang e Barsky - caso particular - y ymax ymin xmin xmax x 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) Liang e Barky propuseram um mesmo algoritmo restrito para janelas retangulares e alinhadas com os eixos cartesianos. Nesta situação o cálculo do parametro t fica bem mais simplificado como ilustra a Figura. Modelo de Camera do OpenGL
81 Liang e Barsky - Cálculo da interseção em uma fronteira -Computação Gráfica Interativa - Gattass Liang e Barsky - Cálculo da interseção em uma fronteira - 12/18/2017 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 */ if (t < *tL) *tL = t; if (num > 0) /* linha esta fora */ return TRUE; Uma maneira eficiente de implementaruma função que atualiza ou o valor de tE ou de TL dado o numerador numerador e o denominador da equação de t é mostrada na função da Figura. Modelo de Camera do OpenGL
82 Algoritimo de Liang e BarskyComputação Gráfica Interativa - Gattass 12/18/2017 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) ) { 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; Com base na função de atulização de tE e tL o algoritmo de Liang e Basky pode ser implementado como uma sequencia de atlizações, uma para cada aresta da janela. Modelo de Camera do OpenGL
83 Recorte de polígonos com base no algoritmo de Hodgman-Sutherland Clip contra uma aresta (plano) de cada vez
84 Classificação de um segmento contra um hiperplano no algoritmo de Hodgman-SutherlandPara 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 s p i s p i Saída: p Saída: i Saída: i, p (a) interno (b) saindo (c) externo (d) entrando
85 Exemplo do algoritmo de Hodgman-Sutherland1 3 2 4 5 6 A B C D 1 4 5 A B C D E F 1 5 A B C D E F s p saída A B 4 E 5 F e 5 C D 1 s p saída 1 2 A 3 4 B e 4 5 6 C D e 1
86 Clipping de polígonos (Exemplo 1)Computação Gráfica Interativa - Gattass 12/18/2017 Clipping de polígonos (Exemplo 1) S P Ação 2 1 2 x A 3 2 3 store A,3 1 4 3 4 store 4 4 5 store 5 6 B 5 5 6 store B 6 1 x A Figura mostr um exemplo do algoritmo aplicado ao polígono 1,2,...6. O resultado é o polígono definido pelos vértices A,3,4,5,B. Modelo de Camera do OpenGL
87 Clipping de polígonos (Exemplo 2)Computação Gráfica Interativa - Gattass 12/18/2017 Clipping de polígonos (Exemplo 2) 2 3 A 6 B S P Ação x x x x D C 1 2 store A 3 x 4 store B,4 5 store 5 6 store C store D,1 1 5 4 A Figura ilusta um caso em que o recorte de um polígono gera duas áreas conectadas por arestas infinitesimais. A D C B 1 5 4 Modelo de Camera do OpenGL
88 Clipping de polígonos (Exemplo 2)Computação Gráfica Interativa - Gattass 12/18/2017 Clipping de polígonos (Exemplo 2) A B S P Ação x x x x E D C A B store B x B 4 store E 1 x 4 5 F 4 5 store F,5 5 C store C C D store D D 1 x 1 A store 1, A A Figura ilustra o recorte do polígona da Figura anterior submetido a uma nova fronteira. B, E, F, 5, C, D, 1, A Modelo de Camera do OpenGL
89 Clipping de polígonos (Concatenação de planos)Computação Gráfica Interativa - Gattass 12/18/2017 Clipping de polígonos (Concatenação de planos) 6 5 1 3 2 4 5 6 A B C D x 4 3 2 1 first[0] S[0] P[0] D 1 4 5 A B C D x E F C 5 4 B A Este processo de recorte de polígonos em fronteiras de uma região convexa pode ser implementado com um algoritmo recursivo em que cada vértice que passa pelo recorte em uma fronteira é submetido a fronteira seguinte. A dificuldade da recursão, neste caso, é que a análise de um vértice depende da situação do seu antecessor. Por isto a implementação mostrada armazena em variáveis globais (que não são afetadas pela pilha de recursão) o primeiro vértice de cada polígono e a situação atual dos vértices S correspondentes a cada fronteira. 1 first[1] S[1] P[1] 1 5 A B C D x E F 1, A, B, E, F, 5, C, D Modelo de Camera do OpenGL
90 APIs para definição de polígonosComputação Gráfica Interativa - Gattass 12/18/2017 APIs para definição de polígonos int 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); } A interface de preenchimento de polígonos adotada aqui segue o formato Begin...End do OpenGL. Assim o algoritmo recebe consecutivamente os vértices do polígono até que uma instrução de fim é chamada. Notem que neste formato nao temos que criar um tipo abstrato de dados, tipo Point. void End( );{ ClipAtPlane(xf,yf,zf); FillSavedPoly( ); } Modelo de Camera do OpenGL
91 Recorte de polígono contra um planoComputação Gráfica Interativa - Gattass 12/18/2017 Recorte de polígono contra um plano s p s p s p i s p i Saída: p Saída: i Saída: i, p (a) interno (b) saindo (c) externo (d) entrando 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); Modelo de Camera do OpenGL
92 Recorte de polígono contra um planoComputação Gráfica Interativa - Gattass 12/18/2017 Recorte de polígono contra um plano y ymax ymin xmin xmax x 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 ); Modelo de Camera do OpenGL
93 Regiões de recorte do rendering pipelinecenter eye zo yo xo up xe ye ze xn yn zn -1 £ xn £ 1 -1 £ yn £ 1 -1 £ zn £ 1
94 Problema do clipping no R3Computação Gráfica Interativa - Gattass 12/18/2017 Problema do clipping no R3 p1 p2 xe ye ze xe ye ze ¸ w Modelo de Camera do OpenGL
95 Escolhas dos hiperplanos do PR3Computação Gráfica Interativa - Gattass 12/18/2017 Escolhas dos hiperplanos do PR3 yn -1 1 xn OpenGL Spec Modelo de Camera do OpenGL
96 Cálculo das distâncias aos hiperplanos no PR3Computação Gráfica Interativa - Gattass 12/18/2017 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 ); hiperplano intercepta Modelo de Camera do OpenGL
97 FIM