Quando um engenheiro precisa fazer um projeto de algum circuito eletrônico, ele tem várias decisões a serem tomadas. Talvez a primeira delas seja decidir qual plataforma de desenvolvimento será usada.Têm-se hoje várias alternativas no mercado: FPGAs, PSOCs, PLCs, microcontroladores, etc.
Quando uma das premissas desse projeto é ter uma interface homem-máquina, aí aparece uma nova gama de caminhos a seguir: LEDs, displays de sete segmentos, alto-falantes, displays LCD, etc. Escolhido o hardware, uma segunda tarefa incumbida ao projetista é a de desenvolver o código a ser “gravado” no componente controlador, a fim de atribuir valor funcional ao circuito. Às vezes, o tempo despendido pelo circuito na interface homem-máquina é tão grande que chega a atrapalhar o seu desempenho. Gerar códigos mais eficientes pode ser a solução para esse problema.
Neste artigo será dada uma motivação ao uso de algoritmos otimizadores para aplicações em microcontroladores e apresentaremos o Algoritmo de Bresenham.
Motivação
Traçar curvas elementares, como segmentos de reta ou arcos de circunferência, requer a construção de algoritmos capazes de determinar na matriz de pixels da superfície de exibição quais pixels devem ser alterados de forma a simular a aparência do elemento gráfico desejado. Hoje em dia, com computadores que possuem frequência de trabalho da ordem de 2 GHz, munidos com vários processadores auxiliares (coprocessadores) que fazem, por exemplo, conta com ponto flutuante, ficou fácil traçar curvas elementares. Prova disso é a perfeição encontrada nos jogos, com cenários de aparência bem reais. Mas, por outro lado, os microcontroladores estão se tornando cada vez mais usados, inclusive para aplicações gráficas.
Eles podem ser vistos como microprocessadores envolvidos por vários periféricos, tudo dentro de um mesmo chip. Esses periféricos são contadores, comparadores, interfaces seriais, e vários outros dispositivos que fazem dos microcontroladores CIs muito funcionais e, consequentemente, de grande aplicabilidade em projetos de eletrônica.
Sabe-se que a potência dissipada em um microcontrolador é diretamente proporcional ao produto do quadrado da tensão de alimentação com a freqüência de trabalho do mesmo. Sabe-se também que o preço dos circuitos integrados cresce se for aumentada a frequência na qual ele trabalhará. Por esses e outros motivos, os fabricantes de microcontroladores geralmente optam por fabricar dispositivos que operam em frequências não muito elevadas (por volta de 8MHz).
Gráficos complexos requerem o traçado de uma grande quantidade de segmentos de reta, e a velocidade é importante. Se as contas forem feitas por um microprocessador moderno, não haverá problemas, contudo, se essa tarefa for incumbida a um microntrolador, o gráfico poderá aparecer no visor depois de um longo tempo, e isso será desconfortável para nossa visão, sendo dessa forma impraticável animações em tempo real.
Uma alternativa muito interessante para traçar curvas, gastando para isso um tempo de processamento bem menor, é conseguida com o uso do Algoritmo de Bresenham. Adiante, mostraremos o processo de construção desse algoritmo para traçar uma reta. Outras curvas podem ser conseguidas usando o mesmo princípio.
O Algoritmo
Para começar, propõe-se uma pergunta: como você escreveria um algoritmo para traçar uma reta, usando, por exemplo, a linguagem do Matlab®? Talvez o algoritmo que você pensou seja parecido com o descrito no box 1.
Esse algoritmo é pouco eficiente, pois, para todos os valores de x, uma conta que usa ponto flutuante deve ser efetuada. Contas com ponto flutuante exigem do processador vários ciclos de clock para serem executadas.
Algoritmos de alto nível podem ser utilizados para minimizar o esforço computacional e assim tornar o processo mais rápido. O mais famoso desses algoritmos foi proposto em 1965 por Jack E. Bresenham, um então funcionário da IBM, formado em Ciência da Computação. O Algoritmo de Bresenham é um algoritmo clássico para traçar curvas ,e usa apenas variáveis inteiras e permite que o cálculo de um próximo ponto (x1+1,y1+1) seja feito de forma incremental, utilizando os cálculos já feitos para o ponto anterior (x1,y1).
Suponha que a superfície de exibição (LCD) possua igual densidade de pixels na horizontal e na vertical (razão de aspecto gráfico igual a 1). O algoritmo assume que a inclinação da linha está entre zero (0) e um (1) (outras inclinações podem ser tratadas por simetria). O ponto (x1,y1) seria o inferior esquerdo, e (x2,y2) o superior direito.
Na figura 1, assumindo-se que o pixel que acabou de ser selecionado é P, em (xp, yp), e o próximo deve ser escolhido entre o pixel à direita superior a M (pixel S) e o pixel à direita inferior a M (pixel I).
Seja Q o ponto de intersecção entre a reta e a coluna x = xp + 1 da malha, e M o ponto intermediário entre os pixels S e I, o que se faz é observar de que lado da reta está o ponto M. É fácil verificar que se M está acima de Q, o pixel está mais próximo da reta; se M está abaixo de Q, S está mais próximo. Dessa forma, o teste do pontomédio permite a escolha do pixel mais próximo da reta. Veja que assumindo uma distância normalizada e igual a 1 (adimensional) entre os pixels adjacentes, tem-se com esse algoritmo um erro de no máximo ½ (adimensional), que é a metade da distância entre dois pixels vizinhos da mesma coluna. Precisa-se agora de um método para calcular de que lado da reta está o ponto M.
Se 
, pode-se escrever a equação da reta:
Tem-se então uma equação implícita F(x,y):
Pode-se reescrever a equação acima,como:
Verifica-se que F(x,y) é 0 (zero) para pontos sobre a reta, positiva para pontos abaixo dela, e negativa para pontos acima dela. Com base nisso, para o teste do pontomédio, basta calcular F(M) = F(xp + 1, yp + 1/2) e verificar o seu sinal. Como a decisão será tomada com base no valor da função no ponto (xp + 1, yp + 1/2), definese uma “variável de decisão” d:
Se d > 0, significa que M está abaixo de onde a curva ideal passa, então é escolhido o pixel S; se d < 0, significa que M está acima de onde a reta ideal passa, então é escolhido o pixel I. No possível caso em que d = 0 é escolhido qualquer um dos dois pixels, S ou I.
Após a decisão de qual pixel será considerado, deve-se atualizar o valor de d. Se I foi o último pixel escolhido, M será incrementado somente na direção x.
Têm-se ntão as seguintes igualdades:
Subtraindo dold de dnew para obter a diferença incremental, tem-se dnew = dold + a. Dessa forma, quando o último pixel escolhido é I, deve-se incrementar d de a = ∆y. Em outras palavras, pode-se derivar o valor da variável de decisão do próximo passo a partir do seu valor atual, sem necessidade de calcular F(M) diretamente. Por outro lado, se S foi escolhido, M é incrementado de 1 em ambas as direções, x e y. Obtém-se o seguinte:
Subtraindo dold de dnew para obter a diferença incremental, tem-se dnew = dold + a + b. Dessa forma, quando o último pixel escolhido é S, deve-se incrementar d de a + b = ∆y - ∆x. Em outras palavras, podese derivar o valor da variável de decisão do próximo passo a partir do seu valor atual, sem necessidade de calcular F(M) diretamente.
Neste ponto já se tem quase tudo para escrever o Algoritmo de Bresenham, só falta decidir qual será o valor inicial de d. Sendo (x1,y1) o primeiro ponto a ser traçado, a próxima decisão será feita para (x1 + 1,y1 + 1/2):
Sendo (x1,y1) um ponto da reta, F(x1,y1) = 0.
Dessa forma:
Pode-se eliminar a fração acima multiplicando F(x, y) por 2. Isto multiplica cada constante e a variável de decisão por 2, mas não afeta o sinal da variável de decisão, que é o que interessa para o teste do pontomédio. Veja um resumo dos limiares de decisão:
Com esses valores em mãos, o próximo passo é desenvolver realmente o algoritmo. Nobox 2, uma versão simplificada do Algoritmo de Bresenham pode ser verificada.
Note que as operações mais complexas a serem feitas são multiplicações por 2, que na lógica binária nada mais é do que deslocamento de um bit para a esquerda.
CONCLUSÃO
Com o Algoritmo de Bresenham, um novo dinamismo é apresentado para o uso dos microcontroladores. Códigos como os sugeridos por Bresenham, além de acrescentarem bons efeitos aos LCDs e darem maior dinamismo ao circuito, também possuem a vantagem de não serem longos,o que possibilita economia de espaço de memória, uma vez que tal recurso é diretamente proporcional ao número de linhas de comando.
Jefferson Zortea Moro - SABER ELETRÔNICA ONLINE
