ALGORITMOS PARA DESENHAR RETAS E CÍRCULOS Jann Claude Mousquer1 , Kenner Alan Kliemann1 , Miguel Diogenes Matrakas1 1 Curso de Ciência da Computação – Faculdades Anglo-Americano (FAA) Foz do Iguaçu, PR - Brasil {jannclaude,kenner.hp}@gmail.com, [email protected] Abstract. This article is a bibliography review about algorithms to draw lines and circles using graphic primatives. The algorithms currently used, are based on cartesian plane and are defined in the SRPG (Simple Raster Graphics Package). Will be discussed some of the algorithms that rasterize graphic objects. Resumo. Este artigo é uma revisão bibliográfica sobre algorı́tmos para desenhar retas e circulos utilizando primitivas gráficas. Os algorı́tmos atualmente utilizados se baseiam no plano cartesiano, e são definidos no SRGP (Simple Raster Graphics Package). Será abordado alguns dos algorı́tmos que fazem a rasterização de objetos gráficos. Palavras Chave: Primitivas Gráficas, Retas, Cı́rculos; 1. Introdução É chamado de primitivas gráficas os comandos e funções que manipulam e alteram os elementos gráficos de uma imagem. Também entram na definição os elementos básicos de gráficos a partir dos quais são construı́dos outros, mais complexos.(Hetem Annibal Jr.,2006). Com base nesta afirmação, será abordardado o estudo das primitivas gráficas responsáveis pelo desenho de retas e cı́rculos. Computacionalmente, todos os objetos são representados por um conjunto de pontos. O ponto é a unidade gráfica fundamental e também pode ser chamada de pixel. As propriedades básicas de um pixel são: posição no plano gráfico (x,y) e cor. Para se obter um pixel é necessário informar o par ordenado (x,y), que possibilita as coordenadas de linha e coluna onde será pintada a grade do vı́deo; de acordo com a resolução especificada no sistema operacional. Com isso, podemos unir pontos a fim de construir objetos mais complexos. Para se desenhar uma reta ou qualquer outro objeto, é necessário fazer uma rasterização. Rasterização é o processo que é utilizado para determinar quais são os pixels que melhor aproximam uma linha desejável na tela, isso se dá ao fato de que dispositivos gráficos não conseguem representar uma reta perfeita, como apresentado na Figura 1, apenas uma aproximação. O Simple Raster Graphics Package (SRGP) é um pacote gráfico, independente de dispositivo, que explora as habilidades de rasterização dos dispositivos gráficos. Ele implementa primitivas gráficas, fornecendo suporte à aplicações. Figura 1. Rasterização. O SRGP trata a tela de saı́da como um plano cartesiano, considerando o ponto de origem (0,0), o canto inferior esquerdo. Partindo deste princı́pio, as entradas (x1,y1,x2,y2), são tratadas como coordenadas no plano, tendo como unidade o pixel. 2. Retas O SRGP fornece procedimentos para desenhos de retas, o procedimento para o desenho de uma reta é: 1 procedure SRGP_lineCoord (0,0,100,300); Neste exemplo uma linha do ponto (0,0) ao ponto (100,300) será desenhado na tela. Para que a reta seja representada em tela, a rasterização será efetuada pelo SRGP uma vez que o procedimento anterior seja invocado. Será abordardado alguns dos algoritmos de rasterização à seguir. 2.1. Algorı́tmo Iterativo Basico A ideia mais simples para rasterização de linhas é determinar a qual valor inteiro no eixo y, uma reta se aproxima. De modo geral, para cada valor x, calcula-se o arredondamento de y. Logo, temos que: Para i pontos em X = (Xi, Round(Yi)); Na Figura 2 podemos observar o resultado da rasterização com esse algoritmo e notamos ainda que, para retas verticais o algoritmo apresenta uma grande falha, isso se dá ao fato de não haver um cálculo dos pontos aproximados no eixo x. Esta falha é o principal motivo pelo qual não é implementado atualmente esse algoritmo, uma vez que se torna pouco versátil. 2.2. Bresenham Também conhecido como algorı́tmo do ponto médio, baseia-se no argumento de que um segmento de reta, ao ser plotado, deve ser contı́nuo, os pixels que compõem o segmento devem ser vizinhos; Isso fará com que os pontos das retas Figura 2. Demonstração do Algorı́tmo Iterativo Básico. sejam próximos não havendo separação entre os pixels pintados, evitando o erro produzido pelo algorı́tmo demonstrado anteriormente. Um outro atrativo é que o algorı́tmo de Bresenham utiliza-se apena de aritmética inteira para cálculo dos pontos, evitando a função de arredondamento (Round), fornecendo uma economia de processamento. O procedimento em pseudo-código abaixo, apresenta a lógica da implementação do algorı́tmo. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 procedure midpointLine (x0, y0, x1, y1, value : Integer); var dx, dy, incrE, incrNE, d, x, y : Integer; begin dx := x1 - x0; dy := y1 - y0; d := 2*dy - dx; incrE := 2*dy; incrNE:= 2*(dy - dx); x := x0; y := y0; writePixel(x, y, value); while x < x1 DO IF d <= 0 THEN d:= d + incrE; x:= x + 1; else 17 d:= d + incrNE; x:= x + 1; y:= y + 1; 18 19 20 end; writePixel(x, y, value); 21 22 23 24 end; end midpointLine; Na Figura 3 temos a demonstração de retas desenhadas pelo Algoritmo de Bresenham. Figura 3. Exemplo de retas desenhadas com Bresenham. 3. Cı́rculos Para traçar cı́rculos, o SRGP trata-os como um caso particular devido a sua simetria. Desta forma, para a rasterização o cı́rculo deve ser transladado de forma que o cı́rculo esteja centrado na origem (0,0). É calculado então os pontos do primeiro quadrante e os demais são então escritos por simetria. Para calcular os valores em y, é considerado que: y 2 = R 2 − x2 (1) No entanto, um cálculo neste formato para cada ponto é computacionalmente inviável, visto que haveria um alto número de cálculos de potência e raiz, que exigem considerável processamento. 3.1. Simetria de Ordem 8 Segundo [Foley et al. 1995], o Algoritmo de Simetria de Ordem 8 considera que, o traçado de uma circunferência pode tirar proveito de sua simetria. Considere uma circunferência centrada na origem. Se o ponto ( x, y ) pertence à circunferência, pode-se calcular de maneira trivial sete outros pontos da circunferência Figura 4. Consequentemente, basta computar um arco de circunferência de 45o para obter a circunferência toda. Para uma circunferência com centro na origem, os oito pontos simétricos podem ser traçados usando o procedimento CirclePoints. Este algorı́tmo não calcula os valores de entrada x e y, mas uma vez calculados nos dá outros sete pontos do cı́rculo. Figura 4. Simetria de Ordem 8. 1 2 3 4 5 6 7 8 9 10 void CirclePoints(int x, int y, int color){ write_pixel( x, y, color); write_pixel( x, -y, color); write_pixel(-x, y, color); write_pixel(-x, -y, color); write_pixel( y, x, color); write_pixel( y, -x, color); write_pixel(-y, x, color); write_pixel(-y, -x, color); }/* end CirclePoints */ É recomendável que x seja diferente de y, pois seria calculado 4 valores repetidos, subutilizando assim o algoritmo. 3.2. Algoritmo do Ponto Médio Bresenham desenvolveu em 1965 um algoritmo clássico que usa apenas variáveis inteiras e que permite que o cálculo de (xi + 1, yi + 1) seja feito incrementalmente, usando os cálculos já feitos para (xi , yi), uma variação do algorı́tmo de mesmo nome, para retas. Este algoritmo assume que a inclinação da linha está entre 0 e 1 (outras inclinações podem ser tratadas por simetria). O ponto (x1, y1) é o inferior esquerdo, e (x2, y2) é o superior direito. Considere a curva na Figura 5. Assumindo que o pixel que acabou de ser selecionado é P, em (xp, yp), e o próximo deve ser escolhido entre o pixel à direita (pixel E) e o pixel abaixo à direita (SE). Seja M o ponto intermediário entre os pixels E e SE. O que se faz é observar de que lado da reta está o ponto M. E fácil verificar que se M está abaixo da curva, o pixel E está mais próximo da reta; se M está acima, SE está mais próximo da curva. A seguir é apresentado o algoritmo simples para conversao matricial de retas. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void MidpointCircle(int radius, int value) { int x = 0; int y = radius; int d = 1 - radius; CirclePoints(x, y, value); while(y > x) { if (d < 0) d += 2 * x + 3; else { d += 2 * (x - y) + 5; y--; } x++; CirclePoints(x, y, value); } } Figura 5. Algoritimo do Ponto Médio M e as escolhas E e SE. Como demonstrado por [Traina and de Oliveira 2006], o teste do pontomédio permite a escolha do pixel mais próximo da curva. Além disso, o erro (a distância vertical entre o pixel escolhido e a linha) é sempre inferior a 0.5. A aritmética necessária para calcular o próximo ponto a cada passo é adição simples, nenhuma multiplicação é necessária. Após o cálculo dos pontos no primeiro quadrante, de 0o à 45o , utiliza-se o algoritmo de simetria de ordem 8 para calcular os restantes, acelerando o processo. 4. Conclusão A interação visual que hoje ocorre entre usuário e máquina pelos dispositivos gráficos, só é possı́vel devido ao estudo da rasterização e abstração dos dados reais para o meio digital. Os algoritmos de rasterização nos auxiliam a fazer a abstração dos elementos gráficos mais básicos, possibilitando a construção de infinitos objetos. Para que fosse possı́vel a velocidade e qualidade de exibição de objetos gráficos que possuı́mos hoje, não somente o hardware precisou evoluir, mas algoritmos eficientes e eficazes foram necessários. Referências Foley, J. D., van Dam, A., Feiner, S. K., and Hughes, J. F. (1995). Computer graphics: Principles and practice. Traina, A. J. M. and de Oliveira, M. C. F. (2006). Apostila de computação gráfica. Disponı́vel em: http://www.inf.ufes.br/˜thomas/graphics/ www/apostilas/GBdI2006.pdf. Acesso em Maio/2014.