quarta-feira, 20 de fevereiro de 2013

Pipeline Gráfico Completo


            O objetivo do trabalho proposto consiste em implementar  todos os passos essenciais de um pipeline simples: desde a descrição de vértices no espaço do objeto até a sua rasterização no espaço de tela, assim como a rasterização de outras primitivas, além de vértices.
            Basicamente, cada passo de um pipeline, envolve uma mudança de sistema de coordenadas (mudança de espaço). Consequentemente, iremos usar diversas transformações geométricas para gerar novos sistemas de bases, por isso a importância de representar vértices e transformações por meio de matrizes.
      
Sequência de Passos do Pipeline

      1)    Espaço do Objeto
O espaço do objeto é um espaço tridimensional onde não há limites de extensão, podendo assim o objeto ter qualquer dimensão ao longo dos três eixos.
Geralmente, cada objeto tem seu próprio sistema de coordenadas, objetos os quais posteriormente, irão se juntar e passarem a dividir o espaço do universo.
O espaço do objeto não é utilizado para definir a posição do objeto em uma cena, e sim apenas para descrever as suas dimensões. A posição desse objeto na cena, apenas será informada quando for posto no espaço do universo, onde será definido uma posição a qual ele irá ocupar no universo, junto com outros objetos.
Aqui, poderemos aplicar qualquer transformação sobre o objeto: rotação, translação, shear e/ou escala. Após aplicado tais transformações, o objeto passará para o espaço do universo.


Possíveis transformações aplicadas no espaço do objeto.


      2)    Espaço do Universo
É onde posicionamos todos os objetos juntos, dividindo um mesmo espaço (sistema de coordenadas). Agora, temos toda a cena formada, com objetos já dimensionados e posicionados nos seus devidos lugares. O próximo passo a ser feito é a filmagem da cena, após o posicionamento de uma câmera.


      3)    Espaço da Câmera
Quando adicionamos uma câmera filmando a cena, os pontos do espaço do universo irão passar para um novo sistema de coordenadas. Esse sistema será construído por meio de informações de como a câmera foi posicionada na cena. São elas: sua posição  (double posição [4]), a direção para qual ela aponta (double direção [4]) e o vetor up, que informa para onde a cabeça da câmera aponta (double up [4]). Esses valores serão necessários para formar as bases do espaço da câmera.
Então, por qual eixo começar? Deve-se começar primeiro pelo Eixo Z, tendo em vista que a câmera aponta para a mesma direção do Eixo Z, porém com sentido oposto. Logo, para calcular o valor do Eixo Z, basta normalizar (base ortonormal)  o vetor direção e inverter o sentido.
O Eixo X é calculo por meio do produto vetorial entre o vetor up e o novo valor do Eixo Z, tendo em vista que o Eixo X é perpendicular a estes outros dois vetores. O resultado do produto vetorial, normalizado, será o valor do eixo X.
O mesmo acontece com o Eixo Y. Basta aplicar uma multiplicação vetorial entre os Eixos X e Z, em seguida de uma normalização do vetor resultante.

Cálculo dos valores do Eixo X, Y e Z do espaço da câmera.


Com esses valores, podemos cria a matriz view, que transformará pontos no espaço do universo, para o espaço de câmera, após a sua multiplicação. A matriz view é composta por uma rotação (alinhar as bases do espaço do universo com as bases do espaço de câmera) e uma translação (igualar as origem):

A primeira, segunda e terceira linha da matriz transposta de B seram preenchidas respectivamente, pelos valores encontrados parao e ixo X, Y e Z ( Xcam, Ycam e Zcam).
O vetor posição da câmera é representado por: P(Px, Py, Pz, 1)


       Multiplicando os pontos do espaço do universo pela matriz view, teremos os mesmo pontos representados agora no espaço de recorte ou projeção.

      4)    Espaço de Recorte (Clipping Space)


Agora com os pontos já no espaço da câmera, o próximo passo do pipeline será projetá-los em um plano de projeção (view plane), para em seguida, passarem pelo procedimento de recorte. Ao realizar isso, podemos escolher como queremos que tais primitivas sejam projetadas: com projeção em perspectiva ou projeção em paralelo.

  • Projeção Ortogonal
            Na projeção ortogonal a forma e tamanho da imagem original são mantidas após projetadas no view plane. Uma projeção ortogonal nada mais é do que uma simples desconsideração da coordenada Z, transformando um objeto tridimensional em um objeto bidimensional.
            Com isso, a matriz de um projeção ortogonal é simplesmente a matriz identidade, tendo em vista que nesse tipo de projeção, não há alteração do valor da coordenada homogênea, nem nas demais coordenadas.


Eixo X (cor verde), Eixo Y (cor azul) e Eixo Z (laranja) projetados sobre o view plane de forma ortogonal.



  • Projeção Perspectiva
            Agora com esse tipo de projeção, teremos o tamanho e a forma de um objeto modificados de acordo com a sua posição do espaço do universo, dando a sensação de distante ou perto quando projetado em tela.
                  Para fazer a projeção, primeiro precisaremos trabalhar com as coordenadas homogêneas, o que não acontecia com a projeção ortogonal. Primeiramente, altera-se o valor de w. Esse é o único o momento do pipeline em que a coordenada homogênea pode ter valor diferente de 1. A matriz que altera o valor da coordenada w está representada pela variável perspectiva.
            Após isso, todas as outras quatro coordenadas do ponto serão divididas pelo novo valor de w, ou seja, passaram pelo processo de homogeneização. Esse processo é feito para que ocorra uma distorção na imagem, comprimindo toda a cena em um cubo, que quando diminuído as dimensões, irá representar o espaço canônico.
               Por fim, o ponto homogenizado será multiplicado pela matriz de projeção, como é mostrado abaixo:






Eixo X (cor verde), Eixo Y (cor azul) e Eixo Z (laranja) projetados sobre o view plane com perspectiva.
Parâmetros da Câmera:  double PosicaoCamera [4] = {30, -20, 2, 1}, 
doube Direcao [4] = {0, 0, -1, 1} e double PosicaoCamera [4] = {0, 1 0, 1}






terça-feira, 5 de fevereiro de 2013

Pipeline Gráfico: Transformação do Espaço Canônico para o Espaço de Tela


  O objetivo do trabalho proposto consiste na implementação de um dos últimos passos de um pipeline gráfico simples: transacionar primitivas descritas no espaço canônico para o espeço de tela. Tal transição é feita por meio de transformações geométricas, das quais para neste caso, usaremos apenas transação e escala.
  A partir de agora, as antigas funções PutPixel, DrawLine e DrawTriangle receberão como parâmetros qualquer número real contido no intervalo entre -1 e 1 (espaço canônico). Porém, não é possível representar pontos com quaisquer valores reais em um sistema de tela, sem antes esses valores passarem por sucessivas alterações. Seguindo as transformações a seguir, será possível representar em espaço de tela, qualquer ponto de coordenadas reais que esteja contido no espaço canônico.


  • Deve-se inverter o eixo dos y, tendo em vista que no Sistema de Tela, o eixo y assume sentido oposto ao eixo y no Sistema Canônico. Para fazer essa modificação, multiplicamos o vetor pela matriz abaixo:


  • Efetuar uma translação, afim de mapear uma das faces do cubo do espaço canônico (um quadrado) para o espaço de tela. Após transladado, o vértice superior do "cubo" do espaço canônico, ocupará o lugar da origem do espaço de tela. Para fazer essa translação, multiplica-se o vetor pela matriz abaixo:



  • Por fim, deve ser feito um aumento nas dimensões para que o triângulo, por exemplo, torne-se perceptível no espaço de tela, e a proporção se mantenha.


  É importante ressaltar algumas observações que devem ser consideradas para que o código funcione corretamente:

  1. As transformações devem ser aplicadas sobre um vértice de cada vez de um polígono(ex.: triângulo), e não sobre a figura já formada. Somente após transladar e "escalonar" os vértices (que no caso de um ponto, são operações de mesmo efeito), é que ocorre a formação da figura. 
  2. A  função PutPixel deve ser alterada, incrementando agora as seguintes instruções abaixo:
     Isso é necessário para que a função não tente rastrear um pixel com coordenadas do tipo ponto flutuante, ocasionando o aborto do programa. Isso acontece porque o espaço de tela possui coordenadas inteiras, que representam a posição do pixel na tela. Com isso, a função PutPixel deve trabalhar com valores inteiros.

            Agora, será possível rastrear pontos com coordenadas de qualquer valor real pertencente ao espaço canônico. Consequentemente, também será possível rastrear retas e triângulo, cujos pontos podem assumir qualquer valor real entre o intervalo [-1,1].
                    A seguir, são mostrados alguns prints comparativos entre a aplicação desenvolvida e a aplicação gerada pelo rastreador do OpenGL. Os resultados obtidos foram iguais.


Rasterização de Pontos.
O código mostra que para representar um vetor foi criada uma estrutura que contém a propriedade "vetor", que nada mais é, do que um array bidimensional que armazena as coordenadas de um vetor. A variáveis "novo_T1", "novo_T2" e "novo_T3" são os novos valores dos pontos, adquiridos após sofrerem transformações geométricas, para serem representados no espaço de tela.








Referências

Foley et al.; Computer Graphics – Principles and Practice with C; Addison-Wesley

domingo, 16 de dezembro de 2012

Rasterização de Primitivas - Pontos, Retas e Triângulos

           Rasterização de Pontos

       O acesso aos pixels na região do framebuffer é realizado por meio do ponteiro FBptr, que está apontado inicialmente para a sua primeira posição de memória, ou seja, para o pixel de coordenadas (0,0) - canto superior esquerdo da tela. O framebuffer consiste em uma matriz unidimensional, com tamanho relativo a dimensão da tela. Com isso, para acessar o pixel que deseja-se pintar, o ponteiro FBptr move-se na direção horizontal, passando por um determinado número de bytes, até chegar ao pixel desejado. Todo pixel da tela é formado por quatro componentes (R,G,B,A), as quais em conjunto, ocupam um espaço em memória de 4 bytes (1 byte para cada componente). Assim, para acessarmos um pixel de coordenadas (x,y), em uma tela de dimensões w*h (largura*altura), usa-se a fórmula:
                                                                 x*4 + y*w*4.
       Depois de localizar o pixel na memória de video, o próximo passo é alterar as suas componentes para assim, forma a cor desejada. O ponteiro FBptr irá apontar para as componentes do pixel localizado, da seguinte forma:
                                               FBptr[p] =   cor.r;       // componente R (read)
                                               FBptr[p+1] = cor.g;    // componente G (green)
                                               FBptr[p+2] = cor.b;   // componente B (blue)
                                               FBptr[p+3] = cor.a;   // componente A (transparência)
               Abaixo é mostrado um print da função PutPixel:
Implementação da funçã PutPixel.

               Para uma melhor organização do código, foram criadas structs para representar o ponto e a cor de um pixel, como é mostrado no print abaixo:

Estrutura de um ponto e uma cor.
               A rasterização de pontos é feita quando ocorre a chamada da função PutPixel, a qual recebe três parâmetros, que representarão respectivamente, a abscissa, a ordenada e a cor do pixel a ser escrito na memória de video.
Chamada da função PutPixel dentro da função MyGlDraw.
Resultado da chamada da função PutPixel do exemplo anterior.
Observação: É recomendável que se utilize o conceito de scissoring(ou clipping), para verficar se as coordenadas do pixel a ser escrito na memória de video,  estão entre o limite das dimensões da tela.


Função para garantir que o pixel escolhido, esteja dentro da tela.

Rasterização de Linhas - Algoritmo de Bresenham


A rasterização de linhas será implementada por meio do algoritmo do Ponto Médio, tendo em vista que para esse algoritmo, o cálculo de rasterização não envolve operações de arredondamento, soma e multiplicação com dados do tipo ponto flutuante, como ocorria em versões anteriores do algoritmo. Tais modificações, implicaram num melhor desempenho no que diz respeito a rapidez no traçado da reta, tendo vista que agora, para localizar o próximo pixel a ser pintado, usaremos variáveis inteiras e o cálculo do próximo pixel será feito incrementalmente, usando os cálculos já feitos para o pixel antecessor.
O problema a ser resolvido pelo algoritmo consiste em: dado dois pontos extremos, determinar quais pixels devem ser pintados para gerar na tela uma boa aproximação do segmento de reta desejado.
Primeiramente, o algoritmo lida com retas que tenham coeficiente angulares entre 0 e 1 (primeiro octante). Para expandir o o algoritmo para os demais octantes, usaremos a relação de simetria entre os octantes, como é mostrado mais adiante no post.
Para as retas do primeiro octante, dado um pixel sobre a reta, o próximo pixel a ser pintado está à direita (E) ou à direita acima (NE), ou seja, tendo o pixel (Xi, Yi), o próximo pixel a ser pintado é E em (Xi+1, Yi), ou NE em (Xi+1, Yi+1), como é mostrado na figura ao lado.
   


         Deveremos pintar o pixel que estiver mais próximo da reta. Para tomarmos tal decisão, usaremos como referência o ponto médio M(Xi+1, Yi + ½). Se a reta estiver acima do ponto médio, o próximo pixel a ser escolhido será NE, caso contrário, o próximo pixel será E. A inclinação da reta será determinada pela forma implícita da equação da reta: f(x,y) = ax + by + c. Substituindo as coordenas de M (Xi+1, Yi + ½) nessa equação da reta, obtemos a localização do ponto médio, e assim decidiremos por qual pixel optar. Com isso, chamaremos de variável de decisão (d)  a expressão:
                   d = f(Xi+1, Yi + ½) = a(Xi+1) + b(Yi + ½) + c = 0  (forma implícita da reta em função do ponto médio M)
                  Se d > 0, escolhemos o pixel NE;
                  Se d < 0, escolhemos o pixel E;
               Se d = 0, o ponto médio pertence a reta, logo pode-se escolher qualquer das duas opções.
         Após escolhido um dos dois pixels, o valor de ponto médio (M) é alterado e consequentemente, o valor de d também. Se E for escolhido, M é incrementado de 1 na direção x:

                       d = f(Xi+1 +1, Yi + ½) = a(Xi+1 +1) + b(Yi + ½) + c


Subtraindo o antigo valor de d com o seu novo valor, observamos que o novo valor de d, é o seu valor antigo incrementado do coeficiente a:

                                              d
new = dold + a

Logo o incremento de NE é dado por: incrNE = a
         Já se NE for escolhido, M é incrementado de 1 em ambas as direções, x e y. A variável d nesse caso, assume o valor:

                         d = f(Xi+1 +1, Yi + ½ + 1) = a(Xi+1 +1) + b(Yi + ½ + 1) + c

Subtraindo o antigo valor de d com o seu novo valor, observamos que o novo valor de d, é o seu antigo valor incrementado do coeficiente a e b;

                                             d
new = dold + a + b

Logo o incremento de NE é dado por: incrNE = a + b
         Utilizando duas, das possíveis formas de representar a reta por meio de equações, podemos chegar nos valores de a, b e c:

                                             f(x, y) = a.x + b.y + c
                                                    y = mx + b
a = (y2-y1)        b = - (x2-x1)       c = (x2-x1)B

Para encontrar o primeiro valor da variável de decisão (d),substituímos o primeiro valor do ponto médio, na equação implícita da reta. Encontramos o seguinte valor:

                                              Dstart = a + ½ b

         Multiplicando o valor de Dstart, incrE e incrNE por 2, afim de simplicar o cálculo, obtemos os seguintes resultados finais:
  •                    Dstart = 2a + 2b
  •                    incrE = 2 (y2-y1)
  •                    incrNE = 2 [(y2-y1) – (x2-x1)]
Agora que obtemos os valores necessários para plotar retas no primeiro octante, podemos expandir o algoritmo para traçar retas em qualquer octante, seguindo o algoritmo abaixo:

      1.  Estabelecer um valor positivo para delta X, fazendo (x2-x1) ou (x1-x2).
1.1   Se x2 > x1, o incremento de X será +1, pois o próximo pixel está à direita;
1.2   Se x1 > x2, o incremento de X será -1, pois o próximo pixel está à esquerda;
      2.  Estabelecer um valor positivo para delta Y, fazendo (y2-y1) ou (y1-y2).
2.1   Se y2 > y1, o incremento de Y será +1, pois o próximo pixel está abaixo;
2.2   Se y1 > y2, o incremento de Y será -1, pois o próximo pixel está acima;
      3. Antes de começar a plotar a reta, verifica-se primeiro se a reta é uma coluna (90º) ou uma linha(0º). Caso seja um dos casos, há uma maneira mais rápida de esboçar essas retas;
      4. Se o delta X = 0, tem-se uma coluna (variação apenas em Y)
4.1   Se o incremento de Y for maior que zero, plota-se pontos com o valor fixo de  X, e incrementa-se  y1 até chegar no valor de y2.
4.2   Se o incremento de Y for menor que zero, plota-se pontos com o valor fixo  de X, e incrementa-se y2 até chegar no valor do y1.

      5. Se delta Y = 0, tem-se uma linha (variação ocorre apenas em X)
5.1   Fazer os mesmos passos em 4.1 e 4.2, porém agora, mantem Y com valor constante e o incrementou ou decremento ocorre a respeito de X;

      6. Se a inclinação da reta for diferente de 0º e 90º, verifica-se qual delta é maior (delta x ou delta y).
6.1   Se o delta x for maior, avalia-se os pixels ao longo do eixo x (e se NE for escolhido, ao logo do eixo y também), movimentando no sentido de acordo com o valor da variável incx (se negativo, para esquerda, e se positivo, para direita). A cada avaliação de sinal da variável de decisão (d) um pixel será pintado (E ou NE), e o valor de x será incrementado ou decrementado, para poder calcular o próximo pixel (pixel adjacente).

6.2    Se o delta y for maior, ocorre os mesmo passos do item 6.1, porém agora, avalia-se os pixels ao longo do eixo y, movimentando no sentido de acordo  com o valor da viariável incy (se negativo, para cima, e se positivo, para baixo).


As retas de cor azul delimitam os octantes.
As retas de cor verde mostram que o algoritmo plota retas em todos os octantes.



Rasterização de Triângulos

                Depois de desenvolver as funções PutPixel e DrawLine, a função DrawTriangle nada mais é do que a chamada da função DrawLine três vezes seguidas, esboçando retas:

  • Do ponto1 ao ponto2;
  • Do ponto2 ao ponto3;
  • Do ponto 3 ao ponto1, fechando o triângulo.
DrawTriangle






Referências