Pipeline Gráfico

Esse post faz parte faz parte da avaliação prática da disciplina Introdução a Computação Gráfica (UFPB - 2016.1), ministrada pelo professor Prof. Christian Pagot. Como segunda avaliação da parte prática devemos fazer a implementação de um  pipeline gráfico.

Conceitos Iniciais 

O que é um pipeline gráfico?

Um pipeline gráfico é a sequência de passos que leva uma cena ou objeto 3D para ser rasterizado em um espaço 2D. O pipeline gráfico a ser implementado é um pipeline gráfico semelhante ao utilizado pela OpenGL. No pipeline gráfico existe um fluxo de transformações e espaços pelo qual o objeto 3D deve passar até que seja rasterizado na tela do computador 2D.

A figura 1 mostra o pipeline gráfico dado em sala de aula.

Figura 1: Estrutura do pipeline gráfico

  Como se pode ver, partimos do Espaço do Objeto e passamos respectivamente pelo Espaço do Universo, Espaço da Câmera, Espaço de Recorte, Espaço Canônico para enfim chegar no Espaço da Tela. A figura 2 mostra o pipeline de modo mais detalhado com os espaços citados acima e as respectivas transformações entre os espaços.

Figura 2: Pipeline de transformação de coordenadas

Coordenadas Homogêneas

Coordenadas homogêneas são um sistema de coordenadas que possui a vantagem que coordenadas de pontos, incluindo pontos no infinito, podem ser representados usando coordenadas finitas. Entretanto, a maior vantagem de utilizar coordenadas homogêneas em computação gráfica é que elas permitem que transformações afins, como a translação, e  transformações projetivas de serem representadas por uma matriz.

Dessa forma utilizamos coordenadas homogêneas com o objetivo de permitir que qualquer transformação seja representada em matriz e assim ser possível combinar todas as transformações em uma única matriz.


Agora que já sabemos a importância de utilizar coordenadas homogêneas, vamos aprender a como converter uma coordenada cartesiana (euclidiana). Como mostrado na figura 3, para transformar uma coordenada euclidiana para uma coordenada homogênea basta acrescentar uma nova coordenada com valor w e multiplicar todas as outras coordenadas pelo o valor w. Em geral, para facilitar os cálculos adota que a coordenada homogênea w = 1.

Figura 3: Coordenada euclidiana e coordenada homogênea

Para converter uma coordenada homogênea para uma coordenada euclidiana basta dividir todas as coordenadas pelo valor da última coordenada e retirar a última coordenada.

Escala

 A escala é uma transformação para modificar o tamanho do objeto em cada um dos seus eixos. A operação de escala em coordenadas homogêneas é mostrada na figura 4.

Figura 4: Escala

Rotação

A rotação no espaço 3D é executada ao redor de um dos eixos do sistema de coordenadas. Assim, escolhemos qual eixo queremos rotacionar e quantos graus serão utilizados. A rotação em coordenadas homogêneas é mostrada na figura 5.

Figura 5: Rotação

Translação

A translação é uma transformação que descola o objeto de posição. A translação só pode ser representada em matriz em coordenadas homogêneas. A translação em coordenadas homogêneas é mostrada na figura 6.

Figura 6: Translação

Pipeline Gráfico

Espaço do objeto

É nesse espaço em que ocorre a modelagem do objeto. Cada objeto é modelado de maneira individual e possui suas próprias coordenadas. O espaço do objeto  é um espaço 3D que não tem limites de extensão, assim o objeto pode ter qualquer dimensão ao longo dos três eixos.
Em geral, cada objeto possui o seu sistema de coordenadas e depois vão se juntar para dividir o espaço do universo. Vale ressaltar que o espaço do objeto só define suas dimensões e não é responsável por definir a posição do objeto na cena. Essa tarefa é responsabilidade do espaço do universo.

Espaço do Universo

O espaço do universo é onde todos os objetos ficam reunidos, portanto dividem o mesmo sistema de coordenadas. É no espaço do universo que toma a cena é formada. Agora com a cena formada devemos registrar a cena através de uma câmera, dessa forma somos levas ao espaço da câmera.

Transformação: Espaço do Objeto → Espaço do Universo

Para transformar os vértices do espaço do objeto para o espaço do universo utilizamos a matriz Model. A matriz Model é composta por uma série de escalas, rotações e translações e cisalhamentos.

Espaço da câmera

 Quando colocamos a câmera na cena temos que transformar todos os pontos do espaço do universo para um novo sistema de coordenadas, o sistema da câmera. Para criar esse novo sistema de coordenadas precisamos informar a posição da câmera (EYE) no espaço do universo, o vetor direção (AT), para onde a câmera aponta, e o vetor (UP), que é o vetor que aponta para parte superior da câmera. Com esse parâmetros podemos criar o sistema de coordenadas do espaço da câmera.

Transformação: Espaço do Universo → Espaço da Câmera

 
A matriz View é  a responsável por transformar os vértices do espaço do universo para o espaço da câmera. Essa matriz é  composta por mais duas operações, uma  rotação e uma translação. Multiplicando as duas operações transferimos o centro da cena para a posição da câmera.

A partir dos parâmetros EYE, AT e UP conseguimos determinar o sistema de coordenada da câmera (x_c, y_c, z_c). O eixo e oposto a AT, isto é, fazemos a diferença entre EYE - AT. A direção x_c é obtida pelo produto vetorial de AT por UP e y_c pelo produto vetorial x_c e z_c.
Note que UP não é necessáriamente ortogonal a AT .

.

Espaço de Recorte

Como já possuímos os pontos no espaço da câmera precisamos projetar a cena restante um plano de projeção (view plane) e descartar pontos que não são vistos pelo câmera. Assim, devemos escolher como se as primitivas serão projetadas em perspectiva ou ortogonal.

Projeção Ortogonal

Na projeção ortogonal tanta a forma quanto o tamanho do objeto são mantidos após projetadas no view plane. A projeção ortogonal é uma transformação de um objeto 3D em um objeto bidimensional. Para isso basta que a coordenada Z seja desconsiderada.

Projeção Perspectiva

Na projeção perspectiva, o tamanho e a forma de um objeto são modificados de acordo com a posição no espaço do universo, dando a mesma sensação de distância que temos nos nossos olhos.
Quando realizamos a projeção perspectiva as coordenadas homogêneas podem assumir valores diferente de 1.

Figura 7: Projeção Paralela e Perspectiva

Transformação: Espaço da Câmera → Espaço Projetivo ou de Recorte

 Essa transformação é realizada pela matriz Projection. Essa matriz transforma os vértices do espaço da câmera para o espaço de recorte. A matriz Projection é dada no seguinte formato mostrado na figura 7 e só depende da distância até o view plane.

Figura 8: Matriz projection

Espaço Canônico

Agora devemos homogenizar todas as coordenadas, esse procedimento é feito dividindo todas as coordenadas pelo novo valor da coordenada w. Com esse procedimento ocorre uma distorção na imagem, comprimindo toda a cena e obtemos o espaço canônico. Assim os vértices sofrem uma distorção. Os objetos  mais próximos do view plane câmera ficam maiores enquanto os que estão mais longe ficam menores.

Espaço de Tela

O último procedimento é levar os objetos do espaço canônico para o espaço de tela. Isto é feito multiplicando todos os vértices do espaço canônico pela matriz view port. A matriz view port tem as seguintes operações:

1. Escala de -1 no eixo y;
2. Escala de w/2 e h/2 nos eixos x e y (w é número de pixels horizontais e h número de pixels verticais);
3.  Translação de (w-1)/2 em x e (h-1)/2 em y;

Figura 9:  Mudança do espaço canônico para espaço de tela

Transformação: Espaço “Canônico” → Espaço de Tela

 Na figura 6 é mostrado a cada operação implementada pela matriz ViewPort.

Figura 10: Matriz ViewPort

 

Resultado

No vídeo abaixo é apresentado o resultado de todo o pipeline implementado durante o trabalho.

 

A figura 10 faz a comparação do resultado do pipeline fornecido pelo professor e o implementado.

Figura 11: Resultado do pipeline do professor

Figura 12: Resultado do pipeline implementado

 

Dificuldades Encontradas

As maiores dificuldades encontradas foram a implementação do pipeline de modo que não ocorresse perda de fluxo de informações.

 

Possíveis Melhorias

 As possíveis  melhorias que podiam ser implementadas seriam o preenchimento completo dos triângulos e otimização de código.

Conclusão

 O trabalho proposto foi bem interessante pois proporciona o entendimento do que é um pipeline e o funcionamento do pipeline gráfico implementado pela OpenGL.

Referências Bibliográficas

Notas de aula do Prof. Christian Pagot
https://en.wikipedia.org/wiki/Homogeneous_coordinates
https://www.ntu.edu.sg/home/ehchua/programming/opengl/CG_BasicsTheory.html
https://en.wikipedia.org/wiki/Graphics_pipeline

 

Rasterização de pontos, linhas (Bresenham) e triângulos

 

Esse post faz parte faz parte da avaliação prática da disciplina Introdução a Computação Gráfica (UFPB - 2016.1), ministrada pelo professor Prof. Christian Pagot.

Instalando a OpenGL

 

 Para realizar esse trabalho é necessário ter instalado a OpenGL que é uma API livre bastante utilizada em computação gráfica. Também é necessário termos instalado a GLUT, uma biblioteca de funcionalidades do OpenGL. No meu caso esse problema foi resolvido com um comando único para sistemas Debian e Ubuntu, basta entrar no terminal e digitar o seguinte comando:

$ sudo apt-get install freeglut3-dev 

Conceitos Básicos

Pixel

O pixel é o menor elemento em um dispositivo de exibição (monitor), ao qual é possível atribuir uma cor. De outra forma, um pixel é o menor ponto que forma uma imagem digital e o conjunto de pixels formam uma imagem inteira. O computador representa os pixels do monitor em uma região da mémoria de vídeo conhecida como Color buffer. Agora que já sabemos a definição de um pixel, vamos conhecer como podemos representar um pixel.


Para representar um pixel utilizamos um sistema de cores chamado RGBA. Esse sistema é formado pelas cores Red (vermelho), Green (verde), B (Azul) e pelo canal Alpha que é reponsavél pela transparência. No maioria dos casos, cada uma das componentes do pixel é representada no computador por 8 bits. Ou seja, seus valores variam de 0 até 255. Assim, o valor de cada componente para o pixel significa a quantidade de vermelho, verde e azul que o pixel deverá possuir. O valor de alpha está relacionado com a transparência, não possuindo importância para esse trabalho. Com essa variação de valores para as componentes primárias de cores conseguimos gerar 256³ ≈ 16 milhões de cores.

Representação do espaço de cores RGB

Exemplo de representação (Big-Endian) das componentes de um pixel na mémoria

Estruturas de dados

Para realizar a programação do problema foram criados duas estruturas de dados auxiliares: color e point. A estrutura color tem 4 componentes para armazenar o valor RGBA para cada pixel e a estrutura point é formada pelas componentes x (horizontal), y (vertical) e pela estrutura cor.

Rasterizar um ponto ( PutPixel() )

Rasterizar um ponto no monitor é a primitiva mais básica que temos. Essa tarefa consiste simplesmente em escolher qual ponto do monitor queremos rasterizar (colorir) e escolhermos a cor na qual vamos pintar o ponto. Para realizar essa tarefa temos que sair de um domínio matemático, cartesiano formado por coordenadas (x,y) para o domínio do computador. As cores de todos os pixels do monitor são armazenados em uma região da mémoria de vídeo chamada Color buffer. O Color buffer funciona da seguinte forma: a primeira região de mémoria armazena as informações relativas ao primeiro pixel do monitor. As informações do segundo pixel estão salvas na segunda região de mémoria e assim sucessivamente. Dessa forma, já é possível determinamos uma função que nos tire de uma determinada posição cartesiana (x, y) para a sua correspondente região de mémiora do Color buffer.

  OffSet = x + y*IMAGE_WIDTH;

Assim, conseguimos ter acesso a região da mémoria de vídeo do pixel escolhido e assim configuramos os valores das suas variavéis de cores. Abaixo está o código da função PutPixel que recebe um ponto e as suas componentes RGBA.

void PutPixel(point p, color c){
    int x = p.x;
    int y = p.y;
    int offSet = x + IMAGE_WIDTH*y;   

    FBptr[offSet*4]   = c.red;
    FBptr[offSet*4+1] = c.green;
    FBptr[offSet*4+2] = c.blue;
    FBptr[offSet*4+3] = c.alpha;
   
}

 

Resultado:

Função PutPixel rasterizando um ponto branco no centro da tela

Rasterização de retas ( DrawLine() )

Existem vários algoritmos de rasterização de retas. Entretanto, o escolhido para ser implementado foi o algoritmo de Bresenham, também conhecido como algoritmo do ponto médio. Esse algoritmo é bem eficiente e gera resultados bem satisfatórios. O funcionamento do algoritmo será explicado brevemente.

Para desenhar uma reta no espaço matemático basta simplesmente escolher um ponto inicial e um ponto final e desenhar um segmento de reta entre esses dois pontos. Para levar esse conceito para o mundo do computador, um espaço discreto, temos o seguinte problema. Se uma reta passar em determinado ponto por 2 pixels, como escolher o pixel que deve ser pintado na tela? Já que não é uma boa ideia pintar dois pixels adjacentes para representar uma reta, pois a reta na sua descrição matemática deve ter espessura quase nula.

Ilustação de um algoritmo de rasterização de reta e o problema de escolher qual pixel pintar.

Algoritmo de Bresenham

O algoritmo de Bresenham não é um algoritmo muito custoso computacionalmente em comparação com outros algoritmos para rasterização de retas, sendo um algoritmo incremental e que evita multiplicações e arredondamentos.

O algorimo de Bresenham será explicado brevemente. Primeiro toma-se como caso particular retas que possuem coeficiente angular m ,entre 0 ≤ m ≤ 1.

A partir da equação da reta :    y = m*x + b

e com manipulações algébricas podemos chegar na seguinte expressão :  
Φ ( x , y )=Δ y⋅x−Δ x⋅y + b⋅Δ x =0.

E chamamos os seguites termos:
α = Δ y
β = −Δ x
γ = b⋅Δ x

Chegando em Φ (x , y ) = α x +β y + γ = 0 

A equação implícita da reta permite dizer que a partir da coordenada x e y de um ponto se ele está ou não está presente na reta. Bresenham observou que através dessa equação podemos saber se um ponto está abaixo ou acima da reta, através do sinal da equação explícita, como pode ser observado abaixo.

Bresenham teve a ideia de avaliar o ponto médio (ponto m da figura acima) para saber qual dos pixels cadidatos rasterizar, ou o pixel NE ou pixel E. Se observamos que a equação implícita avaliada no ponto médio der um valor positivo a reta está mais próxima do pixel E e portanto devemos rasteriza-lo. E se o resultado for negativo devemos rasterizar o pixel NE.



Assim cria-se uma variável de decisão d.

if (d < 0)   next pixel = ne
else  next pixel = e 

Porém avaliar cada pixel com a equação implícita da reta é custoso computacionalmente. Entretanto, Bresenham observou que se o pixel E foi o pixel escolhido para ser rasterizado a expressão de rasterização para o próximo ponto obedecia a seguinte expressão:

d_new =d_old +α



E caso o pixel escolhido fosse o pixel NE, a expressão para o próximo pixel obedecia a seguinte expressão:


d_new =d_old +α +β

E para o pixel inicial a seguinte expressão:

d =2 Δ y −Δ x


Dessa maneira, o algoritmo de Bresenham para valores de m ,entre 0 ≤ m ≤ 1, é expresso abaixo:

Algoritmo de Bresenham para o primeiro octante

Expandindo o algoritmo de Bresenham para os outros octantes

Oito octantes do plano cartesiano

A figura acima mostra as relações dos 8 octantes do plano cartesiano e relações entre os coeficientes angulares de reta e pontos. 

Para criar um algoritmo de Bresenham genérico foi observado primeiro que só era necessário conseguir rasterizar retas em uma das metades do plano, pois por simetria podemos rasterizar retas na outra metade apenas trocando a ordem dos pontos entre si. Por exemplo, visualmente temos o mesmo resultado desenhando uma reta entre (x1,y1) para (x2,y2) e de (x2,y2) para (x1,y1).

Dessa forma, eu escolhi fazer somente a rasterização para a metade direita do plano quando x2 > x1. Se x1 > x2, chamamos a função DrawLine outra vez com os pontos trocados entre si. 

Para o 8° octante observamos que os pixels escolhidos só podem ser E ou SE. Realizando o raciocínio análogo obtemos as seguintes expressões:

Para direção E:

d_new = d_old – 2dy

Para direção SE:

d_new = d_old – 2(dy + dx)

Portanto, no primeiro octante tanto x quanto y são incrementados a cada iteração. No oitavo octante o x é incrementado e y decrementado a cada iteração. Com essa ideia podemos obter todas as expressões para os outros octantes, sempre partindo da coordenada que x e y irão assumir.

Agora analisando quando o m > 1 (2° octante) e quando m < -1 (7° octante) , seguindo a mesma lógica e raciocínio do primeiro octante, obtemos:

2° Octante:
Para m > 1
int incl = (dy>0)? 1:-1;
int d = (2 * dx – dy) * incl;
int incr_e = 2 * dx * incl; 
int incr_ne = 2 * (dx – dy) * incl;

7° Octante
Para m < -1
int incl = (dy<0)? 1:-1;
int d = (2 * dx – dy) * incl;
int incr_e = 2 * dx * incl;
int incr_ne = 2 * (dx + dy) * incl;

Assim, conseguimos rasterizar qualquer reta em qualquer direção do plano cartesiano com o algoritmo de Bresenham.

Resultado:

Retas rasterizadas em várias direções com o algoritmo de Bresenham

Interpolação Liner de cores

Para realizar a interpolação linear de cores das retas foi utilizada a seguinte expressão:
 

 C(λ) = (1 - λ)C_A + λC_B, onde 0 ≤ λ ≤ 1. 

No qual, C_A e C_B são as cores passadas como parâmetros da função do primeiro ponto e di segundo ponto respectivamente. A expressão acima calcula a cor de acordo com λ que foi passado com parâmetro. Para calcular o λ realizamos a seguinte operação:

λ = (posição_atual - posição_inicial) / (posição_final- posição_inicial)

Esse cálculo do λ é realizado tanto para a posições X (variação no eixo OX) e para posições Y (variação no eixo OY) e em seguida calcula-se a média do
λx e λy. Gerando uma interpolação linear dependendo da variação de X quanto de Y.

Resultado:

Interpolação de 6 segmentos de retas

 

 

 

 Rasterização de Triângulos ( DrawTriangles () )

Para rasterizar um triângulo a partir da rasterização de uma linha é algo bem simples. A função DrawTriangle() mostrada abaixo realiza essa tarefa.

void DrawTriangle(point p1, color c1, point p2, color c2, point p3, color c3){

    DrawLine(p1, p2, c1, c2);
    DrawLine(p2, p3, c2, c3);
    DrawLine(p3, p1, c3, c1);

}

Resultado:
 

Triângulo rasterizado com interpolação de cores

 Dificuldades encontradas

O trabalho foi relativamente simples e com poucas dificuldades. A primeira dificuldade foi como adaptar o algoritmo de Bresenham para todos os octantes, mas através de analise de simetria e de crescimento e decrescimento de determinadas posições foi relativamente tranquilo fazer a generalização.

Possíveis melhoras

Uma possível melhora seria a implementação do algoritmo de Bresenham através de matriz de rotação para os outro octantes e comparar qual forma de execução é mais rápida. Uma segunda melhora seria implementar o preenchimento de todo o triângulo rasterizando pontos intermédiarios de uma aresta com o vértice oposto do triângulo. Acredito que isso não deve preencher todo o triângulo, pois como o algoritmo utilizado é o de Bresenham ele deve deixar alguns pontos sem serem coloridos.

 

 Conclusão

O trabalho não foi de grande dificuldade, mas bastante didático para entender a primeira parte do pipeline gráfico utilizado no OpenGL através da rasterização de primitivas (pontos, retas e trinângulos).

Referências

<pt.wikipedia.org/wiki/Algoritmo_de_Bresenham> Acesso: 7 de agosto de 2016
<http://howaboutanorange.com/blog/2011/08/10/color_interpolation/> Acesso em 7 de agosto de 2016
Notas de Aula do Prof. Christian Pagot