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