T1 Extra - Preenchimento de triângulos

O trabalho extra é, com três pontos não alinhados, preencher o triângulo gerado por esses três pontos. Para fazer isso, vamos utilizar as coordenadas baricêntricas para determinar se um ponto pertence ou não a um triângulo.

Definição: De acordo com esse método, cada ponto p do plano pode ser escrito na forma p = λ1 p1 + λ2 p2 + λ3 p3 , onde λ1, λ2 e λ3 são números reais e λ1 + λ2 + λ3 = 1 . Os coeficientes λ1, λ2 e λ3 são denominados coordenadas baricêntricas de p em relação a p1, p2 e p3.

Os valores de  λ1, λ2 e λ3 podem ser obtidos pela regra de Cramer:

O método de coordenadas baricêntricas nos diz que, se λ1, λ2 e λ3 forem maior que 0, então o ponto p pertence ao triângulo formado pelos pontos p1, p2, p3.

Problematização: Mas para saber quais pontos pertencem a um triângulo teríamos que checar todos os pontos da tela.

Bom, para otimizar o algoritmo, podemos limitar quantas comparações o programa pode vir a fazer. Pegando os maiores e menores valores para as coordenadas (x,y) dos vértices dos triângulos, iremos criar um retângulo que engloba o triângulo, limitando assim o número de comparações.

Exemplo da otimização, considere o triângulo abaixo:

Ilustração de um triângulo

Sem a otimização para preencher este triângulo deveríamos checar todos os pontos da tela. Com a otimização, vamos checar apenas os pontos dentro do retângulo, como ilustra a imagem abaixo.

Exemplificação da área de comparação utilizando a otimização

A imagem abaixo exibe o resultado final:

Resultado final do exemplo

Referências Bibliográfica: Bancos de Dados Geográficos - Capítulo 2. Algoritmo geométricos e relacionamentos topológicos. Disponível em:  <http://mtc-m12.sid.inpe.br/archive.cgi/sid.inpe.br/iris@1912/2005/07.01.19.38.>
How to determinate a point in a triangle - Stackoverflow. Disponível em: <http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle>

T1 - Função DrawTriangle();

DrawTriangle: Uma função que desenhe um triângulo na tela, recebendo como parâmetros as posições dos três vértices (xa,ya), (xb,yb) e (xc,yc) bem como as cores (RGBA) de cada um dos vértices. As cores dos pixels das arestas do triângulo devem ser obtidas através da interpolação linear das cores de seus vértices. Não é necessário o preenchimento do triângulo.

Para implementar esta funções é necessário apenas rasterizar 3 linhas ligando os 3 vértices. Como a função de rasterização de linhas já esta implementada, iremos utiliza-lá.

Agora um exemplo de execução:

Exemplo de execução da função DrawTriangle() - exemplo 1

Outro exemplo de execução:

Exemplo de execução da função DrawTriangle() - exemplo 2

T1 - Função DrawLine();

DrawLine: Uma função que rasteriza uma linha na tela, recebendo como parâmetros os seus vértices (inicial e final, representados respectivamente pelas tuplas (x0,y0) e (x1,y1)), e as cores (no formato RGBA) de cada vértice. As cores dos pixeis ao longo da linha rasterizada devem ser obtidas através da interpolação linear das cores dos vértices extremos. O algoritmo de rasterização a ser implementado deve ser o algoritmo de Bresenham.

 Sabemos como rasterizar linhas com o coeficiente angular (m) entre 0 e 1 utilizando o algoritmo de Bresenham. Foi demostrado o cálculo realizado para chegar em um algoritmo que rasteriza linhas com m entre 0 e 1. Utilizando os mesmos cálculos, vamos obter o algoritmo para realizar as rasterizações em retas com o coeficiente angular fora do intervalo 0 e 1.

O algoritmo demostrado em sala rasteriza linhas nos octantes 1 e 6 (rasterização de linha no 6 é obtido por reflexão no algoritmo para o octante 1). Precisamos apenas implementar o algoritmo de Bresenham para os octantes 2, 7 e 8. Pois os demais octantes podem ser rasterizados pela reflexão dos octantes citados.

"Como realizar a reflexão?": Para obter a reflexão basta mudar o octante da linha a ser rasterizada. Os algoritmos para rasterização apenas rasteriza em octantes em que o dx > 0. Antes de inicia a rasterização bastar checar se o dx é positivo, em caso negativo, é necessário realizar a troca do P1 com o P2 (o algoritmo rasteriza do ponto P1 até o P2, onde P1 tem menor valor de coordenada X comparado a P2). Assim o octante será trocado.

Os seguintes cálculos foram obtidos:

Para o segundo octante (m > 1): O valor inicial (d) é igual a dy - 2*dx. Se o valor inicial for maior que  0, o incremento será igual a -2*dx e o pixel a ser rasterizado será o (Xc + 1, Yc), caso contrario, o incremento é igual a 2*(dy - dx) e o pixel a ser rasterizado será o (Xc + 1, Yc + 1).

Para o sétimo octante (m < -1): O valor inicial (d) é igual a dy + 2*dx. Se o valor inicial for maior que  0, o incremento será igual a 2*dx e o pixel a ser rasterizado será o (Xc + 1, Yc), caso contrario, o incremento é igual a 2*(dy + dx) e o pixel a ser rasterizado será o (Xc+ 1, Yc - 1).

Para o oitavo octante (-1 <= m < 0): O valor inicial (d) é igual a 2*dy + dx. Se o valor inicial for maior que  0, o incremento será igual a 2*dy e o pixel a ser rasterizado será o (Xc + 1, Yc - 1), caso contrario, o incremento é igual a 2*(dy + dx) e o pixel a ser rasterizado será o (Xc, Yc - 1).

Imagens:

Rasterização de linhas

T1 - Função PutPixel();

PutPixel() : Uma função que rasteriza um ponto na memória de vídeo, recebendo com parâmetros a posição do pixel na tela (x,y) e sua cor (RGBA).

Como foi passado em sala de aula, para acessar e rasterizar um determinado pixel é necessário multiplicar por 4 a linha a qual o pixel se encontra e somar com a multiplicação da coluna em que o pixel se encontra por 4 e pela largura da tela. Representado pela formula:

Pixel(i, j) = 4*i + 4*Width*j

Estruturas:

Abaixo segue um exemplo de execução:

Exemplo de execução da função PutPixel

T1 - Interpolação de cores

A primeira ideia para a resolução do problema foi, pegar a diferença entre as duas cores e dividir a diferença entre a distância entre os dois pontos. E essa divisão seria incrementada a cor do pixel anterior para definir a cor do próximo pixel. Mas gerou o seguinte resultado:

Rasterização com a diferença de cor dividida pela distância entre os dois pontos

Isso ocorreu por que a distância entre dois pontos não nos dá a quantidade de pixeis que serão pintados, fazendo com que o incremento seja diferente do necessário para fazer a interpolação.

Bom, para saber quantos pixeis serão pintados, basta saber em que octante se encontra e qual é a distância entre uma de suas coordenadas.

Por exemplo, no primeiro octante (0 <= m <= 1), a quantidade de pixeis que serão pintados é igual a diferença entre Xf - Xi, ou seja , Δx. Isso também acontece no oitavo octante.

Já no sétimo e no segundo octante, a quantidade de pixeis que serão pintados é igual a diferença entre o Yf - Yi, ou seja, Δy.

Rasterização com a diferença de cor dividida pela diferença de coordenadas