04 Algoritmo de Bresenham para Tracado de Circulos (1)

Prévia do material em texto

Algoritmo de 
Traçado de Círculos 	
	
Computação	Gráfica	(N521)	
Prof.	Daniel	Valente	de	Macedo,	D.Sc.	–	UNIFOR	
Profa.	Maria	Andréia	Formico	Rodrigues,	Ph.D.	–	UNIFOR	
	
Características 
•  Baseado	no	algoritmo	de	Bresenham	(ponto	médio)	
•  Algoritmo	eficiente	
•  Leva	em	consideração	a	simetria	do	círculo	
Traçado de Círculos 
•  Considere	um	círculo	centrado	na	origem	
Vamos	discutir	a	simetria	
do	círculo.	
Se	 o	 ponto	 (x,	 y)	∈	 ao	
círculo	
Outros	7	pontos	certamente	
também	Pertencem	
Explorando a Simetria do Círculo 
•  Outros	7	Pontos:	
2)	(y,	x)	
3)	(y,	-x)	
4)	(x,	-y)	
5)	(-x,	-y)	
6)	(-y,	-x)	
7)	(-y,	x)	
8)	(-x,	y)	
Traçado de Círculos 
•  Sendo	assim,	só	precisamos	calcular	os	pontos	num	intervalo	de	45°,	
ou	seja,	calcularemos	os	pontos	de	1/8	do	círculo,	fazendo	x	variar	de	
0	 a	 raio/√2	 (enquanto	 y	 >	 x).	 Os	 outros	 7	 pontos	 são	 plotados	
fazendo-se	uso	da	simetria	do	círculo.	
Traçado de Círculos 
•  Seja	 (0,	 r)	 o	 ponto	 inicial,	 à	 medida	 que	 incrementamos	 x	 de	 uma	
unidade	(de	0	a	raio/√2),	a	coordenada	y	descrecerá	de	uma	unidade	
(pixel)	 ou	 permanecerá	 inalterada,	 ou	 seja,	 caminharemos	 para	 a	
direita	(E)	ou	para	baixo	e	direita	(SE).	
(0,	r)	
Algoritmo de Traçado de Círculos 
•  Como	calcular	em	que	lado	da	reta	o	ponto	médio	está?	
Pode-se	escrever	a	equação	da	reta:	
X2	+	y2	=	R2		para	c(0,	0)	e	R	
	
Tem-se	então	uma	equação	implícita	F(x,	y):	
F(x,	y)	=	X2	+	y2	-	R2	=	0	
Algoritmo de Traçado de Círculos 
•  F(x,	y)	é	zero	para	pontos	no	círculo,	positivo	para	pontos	fora	do	
círculo	e	negativo	para	pontos	dentro	do	círculo.	
•  Com	base	nisso,	para	o	teste	do	ponto-mé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)	define-se	uma	variável	de	decisão	d:	
•  d	=	F(M)	=	F(Xp	+	1,	Yp	–	1/2)		
Algoritmo de Traçado de Círculos 
•  Se	d	>	0,	significa	que	M	está	fora	do	círculo,	então	é	escolhido	o	pixel	
SE	
•  Se	d	<	0,	significa	que	M	está	dentro	do	círculo,	então	é	escolhido	o	
pixel	E	
•  No	possível	caso	em	que	d	=	0,	é	escolhido	qualquer	um	dos	dois	
pixels,	SE	ou	E.	
	
Algoritmo de Traçado de Círculos 
•  Após	a	decisão	de	qual	pixel	será	considerado,	deve-se	atualizar	o	
valor	de	d.		
•  Se	E	foi	o	último	pixel	escolhido,	M	será	incrementado	somente	na	
direção	x.		
•  Têm-se	então	as	seguintes	igualdades:	
dold	=	F(Xp	+	1,	Yp	–	1/2)	
dnew	=	F(Xp	+	2,	Yp	–	1/2)	
•  Subtraindo	dold	de	dnew	para	obter	a	diferença	incremental,	tem-se	
dnew	=	dold	+	2x	+	3.	Dessa	forma,	quando	o	último	pixel	escolhido	é	E,	
deve-se	incrementar	d	de	2x	+	3.	
	
Algoritmo de Traçado de Círculos 
•  Por	outro	lado,	se	SE	foi	escolhido,	M	é	incrementado	de	1	em	x	e	
decrementado	de	1	em	y.	Obtém-se	o	seguinte:	
dold	=	F(Xp	+	1,	Yp	–	1/2)	
dnew	=	F(Xp	+	2,	Yp	–	3/2)	
•  Subtraindo	dold	de	dnew	para	obter	a	diferença	incremental,	tem-se	
dnew	=	dold	+		2(x-y)	+	5.	Dessa	forma,	quando	o	último	pixel	escolhido	
é	SE,	deve-se	incrementar	d	de		2(x-y)	+	5.	
	
Algoritmo de Traçado de Círculos 
•  Agora	é	preciso	descobrir	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):	
dstart	=	F(Xp	+	1,	Yp	–	1/2)	onde	Xp	=	0	e	Yp	=	R,	ou	seja,	F(0	+	1,	R	–	1/2)	
dstart	=	5/4	-	R	
	
(0,	R)	
Algoritmo de Traçado de Círculos 
•  Resumo	dos	limiares	de	decisão:	
dstart	=	5/4	–	R																				->				condição	inicial	
dnew	=	dold	+	2x	+	3												->				se	E	for	escolhido	
dnew	=	dold	+		2(x-y)	+	5				->				Se	NE	for	escolhido	
	
Algoritmo de Traçado de Círculos 
function	drawcircle(int	radius)	
{	
/*	Círculo	tem	centro	na	origem	(0,	0)	
int	x	=	0;	
int	y	=	radius;	
float	d	=	5/4	–	radius;	
drawCirclePixel(x,	y,	valor_cor);	
while	(y	>	x)	
{	
								if	(d	<	0)	{	
												d	=	d	+	2*x	+	3;	
												x++;	
								}	else	{	
												d	=	d	+	2*(x-y)	+	5;	
												x++;	y--;	
								}	
								drawCirclePixel(x,	y,	valor_cor);	
}	
}	
Exercício 
•  Pesquise	e	responda:	como	obter	um	algoritmo	para	traçado	de	um	
círculo	não	centrado	na	origem?	
Referências 
•  Apostila:	http://www.gbdi.icmc.sc.usp.br/documentacao/ap	
•  Slides:	
https://sites.google.com/site/fpaulovich/Home/Teaching/scc-250-
computao-grfica	
•  Livro:	Foley,	J.D.	et	al:	Computer	Graphics-Princliples	and	Practice,	
Addison-Wesley	Publishing	Company,	1990	
•  http://www.lcad.icmc.usp.br/~rosane/CG/Scanline.pdf	
•  https://marciobueno.com/arquivos/ensino/cg/
CG_03_Primitivas_Graficas.pdf	
•  http://www.univasf.edu.br/~jorge.cavalcanti/
comput_graf04_prim_graficas2.pdf	
•  http://www.demic.fee.unicamp.br/~jeff/ArquivosIndex/Bresenham