Computação Gráfica
Gerando Circunferências
Há várias maneiras de gerar circunferências em um dispositivo raster (como o monitor de vídeo). Da
mesma maneira que fizemos para gerar segmentos (linhas), vamos discutir dois algoritmos que irão
determinar quais pixels devem ser “acesos” para representarmos um círculo.
A primeira coisa que devemos saber é que uma circunferência de raio R e centro na origem
(x,y)=(0,0), pode ser representada pela equação (no primeiro quadrante). Ver figura 1:
Figura 1:
Nos algoritmos que discutiremos a seguir, vamos nos preocupar somente com o primeiro quadrante,
os demais quadrantes serão gerados por simetria (como veremos mais tarde).
•
Primeiro algoritmo
Vamos incrementar x (inteiro) de 0 até R (um a um), determinando y (real) resolvendo a equação da
circunferência para o primeiro quadrante. Aproximamos o valor de y para um valor inteiro Yn e
“acendemos “ o pixel (x,Yn). Porém lembrando, o quadrante gerado terá origem em (0,0). Para
desenharmos uma circunferência de raio R e centro em um ponto qualquer (Xc,Yc), devemos assim que
determinarmos o pixel (x, Yn), uma translação para um novo pixel relacionado ao centro (Xc,Yc) e não
mais a origem (0,0). A figura 2 a seguir ilustra essa translação:
Prof Humberto B. Pinheiro
Página 1
Figura 2
Para gerarmos os demais quadrantes, podemos aproveitar a simetria da circunferência (figura 3):
figura 3
Assim, determinando pela equação um pixel no primeiro quadrante, podemos “acendê-lo” e ao
mesmo tempo os outros três pixels simétricos. Não esqueçamos que há a necessidade de transladarmos
também os pixels simétricos (que foram definidos em relação ao (0,0) ) para uma circunferência de centro
em (Xc,Yc) diferente de (0,0), como mostrado na figura 4 a seguir:
Prof Humberto B. Pinheiro
Página 2
figura 4
A figura 4 mostra uma circunferência de raio R e centro em (0, 0) gerada pelo algoritmo, sendo
transladada para a posição relativa ao centro de circunferência (Xc, Yc).
Dessa forma o algoritmo fica assim:
•
•
•
•
•
•
•
•
•
•
•
•
INPUT: raio R (inteiro), coordenada do centro da circunferência Xc,Yc (inteiros)
x recebe 0 (x := 0)
repetir até x > R
(ou para x variando de 0 até R)
x inteiro
y := RAIZ_QUADRADA( R*R - x*x)
y real
yn := APROXIMAR(y)
yn inteiro
ACENDE_PIXEL(Xc + x, Yc + yn)
{ primeiro quadrante}
ACENDE_PIXEL(Xc - x, Yc + yn)
{ segundo quadrante}
ACENDE_PIXEL(Xc - x, Yc - yn)
{ terceiro quadrante}
ACENDE_PIXEL(Xc + x, Yc - yn)
{ quarto quadrante}
incrementa x
(x:= x+1)
fim de repetir
fim do algoritmo
*** Esse algoritmo apresenta algumas deficiências:
1
•
Ineficiência computacional devido ao cálculo da raiz quadrada e operações de
multiplicação.
•
O desenho da circunferência fica descontínuo, com largos espaços (1GAPS) a medida
que x se aproxima de R.
Nesse texto, GAP é o espaço entre dois pixels “acesos” que fazem partede uma mesma figura.
Prof Humberto B. Pinheiro
Página 3
figura 5
Na figura 5 podemos notar que os pixels se distanciam à medida que x se aproxima de R. Isso
ocorre porque utilizamos uma equação que determina o y a partir do x e dessa forma, para cada x
(coluna) temos um único y (linha).
Prof Humberto B. Pinheiro
Página 4
•
Segundo algoritmo
Um outro algoritmo um pouco mais eficiente, e com a vantagem de diminuir os GAPS gerados no
algoritmo anterior, é fazendo x= R.cos(θ) e y= R.sen(θ), variando o ângulo θ de 0o a 90o (1o
quadrante):
figura 6
Nesse algoritmo não há necessidade de utilizarmos a equação da circunferência para determinarmos
o valor de y, pois tanto x quanto y são definidos a partir do ângulo θ. Além disso, o incremento do ângulo
(de 0o a 90o ) não precisa ser necessariamente de um em um, mas de um valor ∆θ (real) qualquer.
Quanto menor for ∆θ menores são os GAPS gerados no desenho e dessa forma mais perfeita será a
circunferência gerada, por outro lado mais tempo se leva para gerá-la. Ver figura 6.
Da mesma forma que aconteceu com o outro algoritmo, há a necessidade de transladarmos os pontos
gerados caso desejemos gerar uma circunferência de centro em (Xc,Yc) diferente da origem (0,0).
Também podemos aproveitar a simetria da circunferência, como ocorria no algoritmo anterior, para
determinarmos os outros 3 pontos simétricos àquele gerado no primeiro quadrante.
Dessa forma o algoritmo fica assim:
•
INPUT:
raio R (inteiro),
coordenada do centro da circunferência Xc,Yc (inteiros),
∆θ (real)
•
•
•
•
θ recebe 0 (θ := 0)
repetir até θ > 90
(ou para θ variando de 0 até 90 )
y := R.senθ
yn := APROXIMAR(y)
Prof Humberto B. Pinheiro
θ real
y real
yn inteiro
Página 5
•
•
•
•
•
•
•
•
•
x := R.cosθ
xn := APROXIMAR(x)
x
real
xn inteiro
ACENDE_PIXEL(Xc + xn, Yc + yn)
{ primeiro quadrante}
ACENDE_PIXEL(Xc - xn, Yc + yn)
{ segundo quadrante}
ACENDE_PIXEL(Xc - xn, Yc - yn)
{ terceiro quadrante}
ACENDE_PIXEL(Xc + xn, Yc - yn)
{ quarto quadrante}
θ := θ + ∆θ (incrementa θ)
fim de repetir
fim do algoritmo
A figura 7 mostra como seria um quarto de circunferência (1o quadrante) gerado por esse algorítmo,
com um ∆θ devidamente “calibrado”. Lembremos que quanto menor for o valor de ∆θ, mais perfeita
fica a circunferência (diminuição dos GAPS) , todavia maior é o custo computacional (tempo de
execução)
figura 7
•
Melhoramentos para ambos os algoritmos
Como discutimos anteriormente, aproveitamos a simetria da circunferência para que determinando os
pontos (pixels) do primeiro quadrante, tivéssemos simultaneamente os respectivos pontos simétricos nos
demais quadrantes. Em ambos os algoritmos podemos melhorar esse procedimento se falarmos em
“octantes” e não mais em quadrantes. Na próxima figura veremos a circunferência dividida em 8
“octantes” cada um abrangendo uma área referente a 45o (90o / 2) de arco. Dessa forma, se notarmos
bem, o primeiro quadrante foi dividido em dois octantes (1o e 2o ) que já possuem uma simetria entre eles,
ou seja para cada ponto (x,y) no primeiro octante existe um ponto simétrico no segundo octante na
coordenada (y,x). Então tendo dois pontos no 1o quadrante , (x,y) do 1o octante e (y,x) do 2o octante, basta
acharmos os seus simétricos nos demais quadrantes, como mostra a figura 8.
Prof Humberto B. Pinheiro
Página 6
figura 8
Melhorando o primeiro algoritimo
Poderíamos implementar o primeiro algoritmo variando x de 0 a R.cos(45o ) e “acendendo” 8 pixels
de uma vez:
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
INPUT: raio R (inteiro), coordenada do centro da circunferência Xc,Yc (inteiros)
x recebe 0 (x := 0)
repetir até x > R.cos(45o )
(ou para x variando de 0 até R.cos(45o) )
x inteiro
y := RAIZ_QUADRADA( R*R - x*x)
y real
yn := APROXIMAR(y)
yn inteiro
ACENDE_PIXEL(Xc + x, Yc + yn)
{octantes ímpares}
ACENDE_PIXEL(Xc - x, Yc + yn)
ACENDE_PIXEL(Xc - x, Yc - yn)
ACENDE_PIXEL(Xc + x, Yc - yn)
ACENDE_PIXEL(Xc + yn, Yc + x)
{octantes pares}
ACENDE_PIXEL(Xc - yn, Yc + x)
ACENDE_PIXEL(Xc - yn, Yc - x)
ACENDE_PIXEL(Xc + yn, Yc - x)
incrementa x
(x:= x+1)
fim de repetir
fim do algoritmo
Prof Humberto B. Pinheiro
Página 7
Melhorando o segundo algoritimo
Poderíamos implementar o segundo algoritmo variando θ de 0o a 45o e “acendendo” 8 pixels de
uma vez:
•
INPUT:
raio R (inteiro),
coordenada do centro da circunferência Xc,Yc (inteiros),
∆θ (real)
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
θ recebe 0 (θ := 0)
repetir até θ > 45o
(ou para θ variando de 0 até 45o )
y := R.senθ
θ real
y real
yn := APROXIMAR(y)
x := R.cosθ
xn := APROXIMAR(x)
ACENDE_PIXEL(Xc + xn, Yc + yn)
yn inteiro
x
real
xn inteiro
{octantes pares}
ACENDE_PIXEL(Xc - xn, Yc + yn)
ACENDE_PIXEL(Xc - xn, Yc - yn)
ACENDE_PIXEL(Xc + xn, Yc - yn)
ACENDE_PIXEL(Xc + yn, Yc + xn)
{octantes ímpares}
ACENDE_PIXEL(Xc - yn, Yc + xn)
ACENDE_PIXEL(Xc - yn, Yc - xn)
ACENDE_PIXEL(Xc + yn, Yc - xn)
θ := θ + ∆θ (incrementa θ)
fim de repetir
fim do algoritmo
Ficou claro que em ambos os algoritmos haverá, em maior ou menor grau, espaços entre pontos
consecutivos em um mesmo quadrante (GAP’s) deixando a circunferência com um aspecto descontínuo.
Para minimizar essa sensação, podemos gerar linhas entre esses pontos consecutivos, que embora possa
criar faces retilíneas (facetadas) na “circunferência”, acaba com a descontinuidade. Ver figura 9
Prof Humberto B. Pinheiro
Página 8
figura 9
Na figura 9 é tomado o exemplo do primeiro algoritmo (ver figura 5), onde há naturalmente a
formação de “GAP’s”.
Os pixels pretos na figura 9 são os pixels acesos pelo primeiro algoritmo de
circunferência.
As linhas vermelhas são os segmentos de reta reais que unem cada um desses pixels
pretos consecutivos.
Os pixels em branco (vazados) são os pixels acesos por um algoritmo de geração de
linhas qualquer, aplicados entre cada pixel preto. Notar que os pixels brancos são a
representação discreta das linhas vermelhas e que alguns pixels brancos coincidem com
pixels pretos. Dessa forma, os pixels gerados pelo algoritmo de linhas (pixels brancos)
preenchem os “GAP’s” dando aspecto contínuo à circunferência.
Isso faz com que a figura gerada seja completa embora deixe-a “facetada”. Lembrando que para o
primeiro algoritmo essa medida é extremamente necessária pois a formação de GAP’s é inerente a ele.
Para o segundo algoritmo, dependendo do ∆θ, pode não haver GAP’s, porém isso é difícil de prever
levando à necessidade de implementação desse melhoria. Deixarei a cargo do aluno, alterar os dois
algoritmos a fim de incluir a geração de linhas entre pixels consecutivos.
Exercícios
1) Altere o primeiro algoritmo (com simetria por octante) implementando o método de eliminação
de GAP’s (gerando linhas). Utilizar o procedimento LINE (xi, yi, xf, yf) para gerar os
segmentos.
2) Altere o segundo algoritmo (com simetria por octante) implementando o método de eliminação
de GAP’s (gerando linhas). Utilizar o procedimento LINE (xi, yi, xf, yf) para gerar os
segmentos.
Prof Humberto B. Pinheiro
Página 9