A maior rede de estudos do Brasil

Grátis
6 pág.
03   Algoritmo de Bresenham para Tracado de Retas

Pré-visualização | Página 1 de 1

07/03/19	
1	
Traçado de Retas 
	
	
Computação	Gráfica	(N521)	
Profa.	Andréia	Formico,	Ph.D.		
PPGIA	-	UNIFOR	
	
Algoritmos de Traçado de Retas 
•  Dados	os	pontos	extremos	em	coordenadas	do	dispositivo:	
•  P1(x1,	y1)	(inferior	esquerdo)	
•  P2(x2,	y2)	(superior	direito)	
•  Determina	 quais	 pixels	 devem	 ser	 marcados	 para	 gerar	 uma	 boa	
aproximação	do	segmento	de	reta	ideal	
•  DDA	
•  Algoritmo	de	Bresenham	
07/03/19	
2	
Equação Geral da Reta 
•  Limitações	
•  Arredondamentos	
•  Multiplicação	com	pontos-flutuantes	
•  Traçado	de	retas	verticais	
DDA (Digital Diferential Analyzer) 
•  Baseia-se	na	aplicação	direta	da	 fórmula	que	descreve	uma	 reta	no	
plano	
•  Algoritmo	incremental	
•  Aquele	 em	 que	 uma	 das	 variáveis	 tem	 incrementando	 o	 seu	 valor,	 por	
exemplo	x	=	x	+	1,	e	a	outra	variável	é	calculada	usando	uma	fórmula,	a	partir	
da	primeira.	
07/03/19	
3	
DDA (Digital Diferential Analyzer) 
•  Para	0	<	m	<	1	
•  Assume-se	 que	 os	 valores	 em	 x	 crescem	
mais	rapidamente	que	os	em	y	
•  Define-se	 x	 em	 intervalos	 unitários	 e	
calcula-se	o	y	correspondente	
•  Para	m	>	1,	basta	inverter	os	o	uso	das	
variáveis	x	e	y	
•  Assume-se	 que	 os	 valores	 em	 y	 crescem	
mais	rapidamente	que	os	em	x	
•  Define-se	 y	 em	 intervalos	 unitários	 e	
calcula-se	o	x	correspondente	
	
function	DDA(int	x1,int	y1,int	x2,int	y2)	{	
	int	x;	
	float	y,	m;		
	m	=	(y2	-	y1)	/	(x2	-	x1);		
	for	(x	=	x1	;	x	<=	x2	;	x++)	{		
	 	y	=	y1	+	m	*	(x	-	x1	);		
	 	write_pixel	(x,	round(y));		
	}		
}	
(0,0)	–	(3,2)	
(1,3)	–	(4,5)	
Algoritmo de Bresenham (1965) 
•  Conhecido	também	por	Algoritmo	do	Ponto	Médio	
•  Solução	iterativa	
•  Inicialmente,	considera	0	<	m	<	1	
•  Similarmente	 ao	 DDA,	 incrementa-se	 x	 em	 intervalos	 unitários,	
calculando-se	 o	 y	 correspondente	 (	 e	 y,	 calculando-se	 o	 x	
correspondente)	
•  Utiliza	o	ponto	médio	entre	dois	pixels	para	decidir	qual	pixel	pintar	
•  Não	necessita	de	arredondamentos	
•  Utiliza	apenas	aritmética	inteira	
07/03/19	
4	
Algoritmo de Bresenham 
•  Retas	com	inclinação	entre	0	e	1	
0	<	m	<	1	
•  Devemos	 escolher	 entre	 o	 pixel	
localizado	 à	 direita	 (E,	 pintar	 o	
pixel	à	direita)	e	o	pixel	 localizado	
à	 nordeste	 (NE,	 pintar	 o	 pixel	
localizado	à	direita	e	acima)	
•  Devemos	observar	em	que	lado	da	
reta	o	ponto	M	está	
•  Se	o	ponto	M	estiver	abaixo	da	reta,	
então	 o	 pixel	 NE	 será	 aceso,	 caso	
contrário,	E	será	aceso	
Algoritmo de Bresenham 
•  Como	calcular	em	que	lado	da	reta	o	ponto	médio	está	localizado?	
Se																												e			
	
Pode-se	escrever	a	equação	da	reta:	
	
	
Tem-se	então	uma	equação	implícita	F(x,	y)	:	
	
07/03/19	
5	
Algoritmo de Bresenham 
•  F(x,	y)	é	zero	para	pontos	na	reta,	positivo	para	pontos	abaixo	da	reta	e	
negativo	para	pontos	acima	da	reta	
•  Com	base	nisso,	para	o	teste	do	ponto-médio,	basta	calcular	o	valor	de	F	para	
o	primeiro	ponto-médio,	com	coordenadas	
				substituindo-se	estas	coordenadas	na	função	F(x,	y)	e	atribuir	o	valor									
				resultante	à	variável	de	decisão	(erro)	inicial	d	
																																																													
(Xp,	Yp)	
d	 dnew	E	
dnew	NE	
Análise do Sinal de d 
•  d	>	0,	significa	que	M	está	abaixo	do	pixel	onde	a	curva	ideal	passa,	
então	é	escolhido	o	pixel	localizado	à	NE	
•  d	<	0,	significa	que	M	está	acima	do	pixel	onde	a	reta	ideal	passa,	então	é	
escolhido	o	pixel	localizado	à	E	
•  No	possível	caso	em	que	d	=	0,	é	escolhido	qualquer	um	dos	dois	pixels,	
NE	ou	E	
07/03/19	
6	
Algoritmo de Bresenham 
•  À	cada	iteração,	após	a	decisão	de	qual	pixel	será	pintado,	deve-se	atualizar	o	valor	
da	variável	de	decisão	d		
•  Se	E	foi	o	último	pixel	escolhido,	M	será	incrementado	somente	na	direção	x.		
•  Têm-se	entã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	é	E,	deve-se	incrementar	d	de	a	=	Δy	
(Xp,	Yp)	
dold	 dnew	
Algoritmo de Bresenham 
•  Por	outro	lado,	se	NE	foi	escolhido,	M	é	incrementado	de	1	em	ambas	as	
direções,	x	e	y:	
•  Subtraindo	dold	de	dnew	para	obter	a	diferença	incremental,	tem-se	dnew	=	dold	+	
a	+	b.	Dessa	forma,	quando	o	último	pixel	escolhido	é	NE,	deve-se	
incrementar	d	de	a	+	b	=	Δy	-	Δx.	
(Xp,	Yp)	
dold	
dnew	
07/03/19	
7	
Cálculo do valor inicial de d 
•  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):	
•  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	
Cálculos dos Valores de Decisão (erros/
resíduos) e suas Atualizações 
	
																																																											condição	inicial	
																																																											se	E	for	escolhido	
																																																											se	NE	for	escolhido	
07/03/19	
8	
Código 
function	bresenham(int	x0,	int	y0,	int	x1,	int	y1)	{	
	int	dx,	dy,	incrE,	incrNE,	d,	x,	y;	
	dx	=	x1	-	x0;	
	dy	=	y1	-	y0;	
	d	=	dy	*	2	-	dx;	
	incrE	=	dy	*	2;	
	incrNE	=	(dy	-	dx)	*	2;	
	x	=	x0;	
	y	=	y0;	
	drawPixel(x,	y);	
	while	(x	<	x1)	{	
	 	if	(d	<=	0)	{	
	 	 	d	+=	incrE;	
	 	 	x++;	
	 	}	else	{	
	 	 	d	+=	incrNE;	
	 	 	x++;	
	 	 	y++;	
	 	}	
	 	drawPixel(x,	y)	
	}	
}	
Generalização para Todos os Octantes 
07/03/19	
9	
Generalização para Todos os Octantes 
Generalização para Todos os Octantes 
07/03/19	
10	
Observações 
•  Para	saber	a	qual	octante	pertence	uma	reta,	basta	calcular	a	sua	
declividade	m	
•  Para	implementar	o	algoritmo	para	os	demais	quadrantes,	basta	
substituir	o	par	(x,y)	pelo	par	adequado,	dependendo	do	octante	em	
questão	
•  Por	exemplo,	para	o	segundo	octante,	substituir	o	par	(x,	y)	por	(y,	x)	
•  Retas	que	estão	nos	octantes	da	esquerda	podem	ser	transformadas	
em	retas	dos	octantes	da	direita	
•  Invertendo-se	a	ordem	dos	pontos	se	dx	for	negativo	
Exercícios (incluindo avaliação atitudinal) 
•  Implemente	o	algoritmo	e	Bresenham	para	traçado	de	retas	para	
todos	os	octantes.	
•  Torneio	do	Algoritmo	de	Bresenham.	Bresenham	em	execução!	
	
07/03/19	
11	
Referências 
•  Slides:	
	http://www.demic.fee.unicamp.br/~jeff/ArquivosIndex/Bresenham	
	http://letslearnbits.blogspot.com.br/2014/10/icgt1-algoritmo-de-	
bresenham.html	
•  As	apostilas	de	CG	que	estão	no	unifor	online	
•  Livro:	Computer	Graphics	with	Java,	Rowe,	Palgrave.	
•  Artigo	do	Hill	(em	inglês)	no	unifor	online:	com	a	derivação	detalhada	
do	Algoritmo	de	Bresenham	(melhor	referência	na	área)