Rasterizando Linhas

Agora vamos desenhar, ou, mais precisamente, rasterizar, linhas. Vamos utilizar como parâmetros de entrada para a nossa função os pontos da coordenada inicial (x0, y0), da coordenada final (x1, y1), a cor do ponto inicial e do final, para depois fazermos a interpolação de cores.

Para esclarecer logo, o sistema de coordenadas do framework tem origem no canto superior esquerdo da tela, por isso temos que fazer uma leve ginástica mental para entendermos logo como o algoritmo funciona!

Vamos dividir a rasterização em oito funções, cada uma especializada em trabalhar com linhas em um octante diferente. Octantes são divisões angulares, então temos cada octante abrangendo 45°, totalizando 360°, ou uma rotação copleta, como um relógio. Por exemplo, uma linha reta que é desenhada a partir do canto superior esquerdo da tela,  para baixo e para a direita fazendo um ângulo de 30° com o topo da tela estaria no primeiro octante.

Para desenharmos uma linha, que é, na matemática, infinitamente fina, em um uma tela de pixels, onde linhas precisam ter pelo menos um pixel de espessura, precisamos utilizar um método de rasterização, ou seja, um algoritmo que decide quais pixels devem ser utilizados para representar uma linha infinitamente fina qualquer.

O método utilizado é o algoritmo de incremental de linha de Bresenham. É um algoritmo bem simples e muito rápido por fazer apenas multiplicações e incrementos.Utilizando o algoritmo padrão, implementamos uma função que pode rasterizar linhas no primeiro quadrante. Podemos facilmente modificar esta função para aplicá-la aos outros octantes. Vejamos como alguns quadrantes diferem logicamente do primeiro:

Para uma linha no segundo octante, |dy| > |dx|, então vamos precisa ter mais do que um pixel aceso por coluna da tela, ou a linha ficaria descontínua. Por isso, precisamos rasterizar a linha em função do eixo y ao invés do eixo x, como no primeiro octante. No código, precisamos trocar os dx por dy e vice-versa e colocar o while dependendo de y e y1. Estamos, de fato, espelhando a função para o eixo y!

void DrawLine2O(int x0, int y0, int x1, int y1, cor color0, cor color1){

    int dx = x1 - x0;
    int dy = y1 - y0;

    int d = 2*dx - dy; //valor inicial de d

    cor color = color0;
    
    int incS = 2*dx;            //valores iniciais para incrementos S e SE
    int incSE = 2*(dx - dy);

    int x = x0; //valores iniciais para rasterizacao
    int y = y0;

    PutPixel(x, y, color); // bota primeiro pixel

    while(y < y1){
        if(d<=0){
            d += incS;
            y++;
        }else{
            d +=incSE;
            y++;
            x++;
        }
        
        PutPixel(x, y, color);
    }
}

Outro caso: o quadrante 5. Nele, voltariamos a rasterizar em função de x, já que |dx|>=|dy|, ou seja, a linha está fazendo um ângulo menor ou igual a 45° com o eixo x. No entanto, dx é negativo, então a rasterização ocorre de trás para frente - da direita para a esquerda! Para isso, precisamos fazer o loop rodar enquanto x>x1(trocamos x e x1), e decrementar x e y ao invés de incrementá-los, já que o linha está também sendo rasterizada de baixo para cima. Finalmente, negativamos o dx e dy pois dentro da função eles servem apenas como comprimentos.

As funções para octantes onde os valores finais do eixo da função sao menores que os iniciais utilizam esta mesma logica de escrever "de tras pra frente", sendo diferenciadas apenas pelas mudanças lógicas para cada octante. 

A função principal que chamamos para rasterizar nossas linhas apenas decide, a partr das coordenadas, qual das outras oito funções deverá ser chamada, passando os seus parâmetros para ela. E assim, uma linha é criada!

Teste de linhas em todos os octantes.

O número de funções poderia ser reduzido se implementássemos elas sempre colocando os pixel da esquerda para a direita, ou até mesmo utilizar apenas um única função que se adapta dependendo dos valores de entrada. Desse modo, nos livraríamos até da função de decisão. Decidi seguir pelo caminho de uma funções por octante pois sua lógica é bem explícita e faz uso de pequenas modificações para acomodar cada quadrante. De toda forma, é necessáro criar algum tipo de estrutura de decisão para acomodar todas as possíveis possibilidades, como decidir em função de qual eixo devemos colocar os pixels, ou se devemos colocá-los de trá pra frente etc. Talvez uma única função universal seja mais eficiente, mas acho que as oito funções são mais didáticas e de fácil manutenção. De toda forma, as linhas são rasterizadas sem nenhum problema.

Referências:
Notas de aula do professor Christian.
Capítulo 3.2 do Foley.

Álbum da vez: