O algoritmo das linhas de Bresenham

Como curiosidade histórica, vamos recordar o algoritmo de Bresenham para desenhar linhas.

Hoje em dia quando se fala de gráficos de computador imeditamente se pensa em coisas como frames por segundo e ray-tracing. Mas, noutros tempos, as coisas eram bem mais simpes, mas ainda assim com desafios.

Em 1962, Jack Elton Bresenham trabalhava na IBM, a ligar plotters Calcomp - máquinas mecânicas que desenhavam com caneta sobre papel - a um computador IBM 1401. Desenhar linhas direitas nestes sistemas era surpreendentemente complicado. Um dos problemas estava em desenhar linhas diagonais, pois não era fácil transformar a linha "matemática" inclinada para os pontos físicos possíveis dos passos mecânicos das plotter ou dos píxeis no ecrã. Bresenham teve então uma ideia engenhosa para escolher os melhores pontos a desenhar, de forma a que a linha parecesse o mais direita possível, usando apenas operações inteiras: somas, subtrações e deslocamentos de bits - dispensando números com casas decimais, multiplicações ou divisões, operações que eram extremamente mais complexas de calcular pelo hardware da época.

Esta solução de 1962 continua omnipresente hoje em dia, desde drivers gráficos e motores de jogos a máquinas CNC e cortadores laser. A abordagem tradicional para desenhar uma linha entre dois pontos passa pela equação y = m·x + b, avançando um píxel de cada vez no eixo x e arredondando y. O problema é que este método depende de cálculos com casas decimais e é lento. A genialidade de Bresenham foi evitar o cálculo do valor real de y e, em vez disso, manter um acumulador de erro que mede o afastamento da linha ideal. O algoritmo avança sobretudo ao longo do eixo dominante e só ajusta o outro eixo quando o erro ultrapassa um certo limiar, usando apenas números inteiros e eliminando problemas de arredondamento.

plotLine(x0, y0, x1, y1)
   dx = x1 - x0
   dy = y1 - y0
   D = 2*dy - dx
   y = y0

   for x from x0 to x1
     plot(x, y)
     if D > 0
          y = y + 1
          D = D + (2 * (dy - dx))
     else
       D = D + 2*dy
     end if


Se estão a pensar "mas o algoritmo tem ali duas multiplicações!", não estão a ver mal. O que se passa é ambas são multiplicações por dois, que são operações fáces e rápidas de fazer no sistema binário fazendo um "deslizamento" dos bits para a esquerda. Por exemplo, o número 3 (que em binário é 0011) transforma-se rapidamente em 6 (0110) deslocando os dígitos para a esquerda, e mesmo é válido para qualquer outro número em representação binária - também é fácil multiplicar por 4x, 8x, 16x, deslizando mais casas.


Mesmo em 2026, o algoritmo continua relevante porque é extremamente rápido, usa apenas operações simples, e adapta-se perfeitamente a todo o tipo de hardware. Ainda que hoje existam técnicas mais sofisticadas, como o algoritmo de Wu para linhas com anti-aliasing, o Bresenham continua imbatível quando o objectivo é obter linhas nítidas, que encaixem uma linha diagonal num conjunto de píxeis exactos, há mais de 60 anos.