2.1 Conceitos iniciais do Algoritmo de Bresenham

A imagem que se vê nas telas do computador é definida por uma malha retangular, tal como o cenário da Figura 05. A diferença é que a malha usada em uma imagem é de pixels, o que torna as quebras menos perceptíveis. Porém, se você for olhar atentamente, irá notar os “degraus” gerados pelos pixels pintados, como a Figura 08 ilustra.

O algoritmo usado para desenhar uma reta de um ponto a outro em uma imagem faz exatamente o que se quer com o personagem. Ou seja, ele segue o rastro gerado pela tinta do algoritmo de Bresenham.

Esse algoritmo se baseia na equação da reta definida pelos seus pontos de extremidade. Essa equação define a reta “ideal” (uma reta contínua, sem quebras nem degraus). O algoritmo funciona, então, usando um laço para percorrer as coordenadas de um determinado eixo, por exemplo o eixo X, e calcular o Y correspondente na equação da reta. O pixel da coordenada X que tiver valor em Y mais próximo do Y calculado pela equação da reta será o pixel pintado.

Para ficar mais claro, observe a Figura 09.

Nela, a reta r é calculada a partir da equação da reta tomando base os pontos extremos (no caso do percurso do personagem são os pontos de origem e de destino). Para um determinado valor x, temos y calculado a partir da equação da reta. Então, o pixel no eixo X que possui o Y mais próximo do y calculado será o pixel a ser pintado. No caso do exemplo da Figura 09, será pintado o pixel do y1.

Ao se aplicar o mesmo procedimento em um laço (loop) para cada um dos valores em X entre os pontos extremos da reta, tem-se um resultado similar ao apresentado na Figura 10.

Porém, a princípio, a ideia acima funciona apenas para as retas cujo ângulo de inclinação se encontra no primeiro octante do plano… octante? O que é isso?

Bem, se o plano pode ser dividido em quatro quadrantes, ele também pode ser dividido em oito octantes!

A Figura 11 ilustra melhor o que é um octante. O que está ressaltado na figura é a região em que, para todos os pontos pertencentes a essa região, os valores de x são maiores do que 0 e maiores que os de y. Ele é o primeiro octante do plano.

A princípio, a ideia funciona apenas nesse octante porque, em vez de ficar procurando o pixel com o y mais próximo da reta da equação, você começará com um y fixo e irá incrementá-lo apenas quando necessário. Se você observar a Figura 10, os valores de y conservam o valor inicial, até o momento em que a distância para a reta da equação ultrapassa o tamanho do pixel. Quando isso ocorre, o valor de y é incrementado. Em seguida, ele continua com o valor para os próximos pixels, até o momento em que a diferença ultrapassa novamente o tamanho do pixel e, novamente, ele é incrementado. E assim por diante, até chegar no ponto destino.

Isso só funciona para o primeiro octante, mas não se preocupe. Você definirá mais tarde um procedimento para esse octante e os demais casos serão gerados a partir da aplicação do mesmo procedimento sobre um espelhamento das coordenadas (as coordenadas estarão invertidas).