algoritmos para desenhar retas e círculos

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.