CG2009 raster preenche

Prévia do material em texto

MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
COMPUTAÇÃO GRÁFICA
Rasterização e Preenchimento de Regiões
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Objetivos
•• Conhecer os fundamentos da Conhecer os fundamentos da
construção de linhas e círculosconstrução de linhas e círculos
•• Conhecer o modeloConhecer o modelo scan-line scan-line ee
modelo de sementes paramodelo de sementes para
preenchimento de polígonospreenchimento de polígonos
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Rasterização
O processo que determina quaisO processo que determina quais pixels pixels
produzem a melhor aproximação para aproduzem a melhor aproximação para a
representação de uma linha é denominadorepresentação de uma linha é denominado
dede rasterizaçãorasterização..
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Rasterização
•• A escolha é óbvia para linhas A escolha é óbvia para linhas
verticais, horizontais e linhas a 45ºverticais, horizontais e linhas a 45º
Linhas Verticais, Horizontais e a 45Linhas Verticais, Horizontais e a 45oo
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Rasterização
•• Para linhas com outras angulaPara linhas com outras angulaçõesções……
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Rasterização
 Características Características
•• Linhas retas devem parecer retas Linhas retas devem parecer retas
•• Brilho constante ao longo da linha Brilho constante ao longo da linha
•• Eficiência na construção Eficiência na construção
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Algoritmo de Bresenham - Retas
•• Fundamentos Fundamentos
(0,0)
(0,1) (1,1)
(1,0)
1/2 ≤ Δy / Δx ≤ 1 (erro ≥ 0)
Plot(1,1)
0 ≤ Δy / Δx < 1 (erro < 0)
Plot(1,0)
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Algoritmo de Bresenham - Retas
•• Análise do erro Análise do erro
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Algoritmo de Bresenham - Retas
•• Análise do erro Análise do erro
0
0
1 2 3
1
0.5
-0.5
0
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
BresenhamBresenham - construção de linhas cujos pontos inicial e final são (x- construção de linhas cujos pontos inicial e final são (x11,y,y11) e) e
(x(x22,y,y22), respectivamente), respectivamente
x = xx = x11
y = yy = y11
ΔΔxx = x = x22 - x - x11
ΔΔyy = y = y22 - y - y11
e = m - 1/2e = m - 1/2
PARAPARA i = 1 i = 1 ATÉATÉ ΔΔx x FAÇAFAÇA % início do laço principal % início do laço principal
PlotarPixelXYPlotarPixelXY(x, y)(x, y)
ENQUANTOENQUANTO (e > 0) (e > 0) FAÇAFAÇA
 y = y + 1 y = y + 1
 e = e - 1 e = e - 1
FIM ENQUANTOFIM ENQUANTO
x = x + 1x = x + 1
e = e + me = e + m
FIM PARAFIM PARA
FIM ALGORITMOFIM ALGORITMO
m = m = ΔΔy / y / ΔΔxx
Obs.: algoritmo válido para 0 Obs.: algoritmo válido para 0 ≤≤ ΔΔy y ≤≤ ΔΔxx
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Algoritmo de Bresenham - Retas
•• Exemplo: Construir uma linha cujas Exemplo: Construir uma linha cujas
extremidades são (0,0) e (5,5) usando oextremidades são (0,0) e (5,5) usando o alg alg..
BresenhamBresenham i setpixel e x y
 1/2 0 0
1 (0, 0)
2 (1, 1)
3 (2, 2)
4 (3, 3)
5 (4, 4)
 -1/2 0 1
 -1/2 1 2
 1/2 1 1
 1/2 2 2
 -1/2 2 3
 1/2 3 3
 -1/2 3 4
 1/2 4 4
 -1/2 4 5
 1/2 5 5
Δx = 5
x = 0
y = 0
Δy = 5
m = 1
e = 1/2
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Algoritmo de Bresenham - Retas
0
0 1 2 3 4 5
1
2
3
4
5
•• Desenho da linha - (0,0) e (5,5). Desenho da linha - (0,0) e (5,5).
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Algoritmo de Bresenham
Algoritmo genérico - retasAlgoritmo genérico - retas
Algoritmo para construção de círculosAlgoritmo para construção de círculos
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Algoritmo de Bresenham - Círculos
•• Eficiente Eficiente
•• Somente um Somente um octante octante do cdo círculo é gerado:írculo é gerado:
as outras partes são obtidas por sucessivasas outras partes são obtidas por sucessivas
reflexõesreflexões
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Algoritmo de Bresenham - Círculos
•• Suponha que o círculo será gerado no sentido Suponha que o círculo será gerado no sentido
horário. Portanto, para qualquer pontohorário. Portanto, para qualquer ponto
pertencente ao círculo, existirá 3 possibilidadespertencente ao círculo, existirá 3 possibilidades
de movimento para o de movimento para o pixel pixel seguinte:seguinte:
Horizontalmente à direita; Horizontalmente à direita; Diagonalmente para Diagonalmente para
baixo à direita; baixo à direita; Verticalmente para baixo Verticalmente para baixo
•• O algoritmo escolhe o O algoritmo escolhe o pixel pixel que minimiza umaque minimiza uma
medida de distância entre estes movimentos emedida de distância entre estes movimentos e
aqueles produzidos por um aqueles produzidos por um ““círculo realcírculo real””..
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Exercício
•• (prova - 2004) (prova - 2004) Deseja-seDeseja-se
desenhar uma letra desenhar uma letra VV
usando os Algoritmos usando os Algoritmos dede
Bresenham e/ou Bresenham e/ou DDA (DDA (vejaveja
Figura ao ladoFigura ao lado).).
ComoComo você resolveria esse problema você resolveria esse problema? (? (pensepense
em umaem uma forma forma eficiente eficiente)) Faça Faça as as
considerações que forem necessáriasconsiderações que forem necessárias..
ApresenteApresente o o acompanhamento acompanhamento dos dos algoritmos algoritmos
parapara a a construção da construção da(s)(s) reta reta(s).(s).
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Para saber mais:
[ROGERS98] Capítulo 2
[FOLEY95] Capítulo 3
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Preenchimento - Fundamentos
•• Contornos fechados podem ser vistos Contornos fechados podem ser vistos
como polígonos.como polígonos.
•• O método mais simples para se preencher O método mais simples para se preencher
polígonos é o de varrer cadapolígonos é o de varrer cada pixel pixel da imagemda imagem
e verificar se ele está dentro do polígono.e verificar se ele está dentro do polígono.
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Fundamentos
•• Para melhorar a eficiência da Para melhorar a eficiência da
varredura, utiliza-se um varredura, utiliza-se um ““bounding boxbounding box””..
•• Bounding box Bounding box é o menor retângulo que é o menor retângulo que
contém o polígono.contém o polígono.
 bounding boxbounding box
 bounding boxbounding box
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Varredura por linha
•• É provável que É provável que pixels pixels adjacentes em umaadjacentes em uma
linha de varredura tenham as mesmaslinha de varredura tenhamas mesmas
características (mudam quando a linha decaracterísticas (mudam quando a linha de
varredura corta a borda de um polígono).varredura corta a borda de um polígono).
•• Também conhecido como Também conhecido como scan-linescan-line
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Varredura por linha
P1 P2
P3
P4
P5
2
4
0
Scan line 4
Scan line 2
6
2 4 6 8 10
x < 1 x < 1 →→ fora do polígono fora do polígono
1 1 ≤≤ x x ≤≤ 8 8 →→ dentro do polígono dentro do polígono
x > 8 x > 8 →→ fora do polígono fora do polígono
x < 1 x < 1 →→ fora do polígono fora do polígono
1 1 ≤≤ x x ≤≤ 4 4 →→ dentro do polígono dentro do polígono
4 < x < 6 4 < x < 6 →→ fora do polígono fora do polígono
6 6 ≤≤ x x ≤≤ 8 8 →→ dentro do polígono dentro do polígono
x > 8 x > 8 →→ fora do polígono fora do polígono
SCAN LINE 2SCAN LINE 2
SCAN LINE 4SCAN LINE 4
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Varredura por linha
•• Dificuldade: intersecção de uma linha Dificuldade: intersecção de uma linha
de varredura com um vértice dode varredura com um vértice do
polígonopolígono
P1
P2
P3
P4
Scan line 10
Scan line 5
Scan line 4
Scan line 1
•• Um resultado Um resultado
correto é obtidocorreto é obtido
quando se conta duasquando se conta duas
intersecções quando aintersecções quando a
scan linescan line cruza com cruza com
um máximo ou mínimoum máximo ou mínimo
local (P3 e P1,local (P3 e P1,
respectivamente).respectivamente).
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Preenchimento por semente - PPS
•• Assume que pelo menos um ponto no interior Assume que pelo menos um ponto no interior
do polígono é conhecido.do polígono é conhecido.
•• Regiões podem ser definidas no interior do Regiões podem ser definidas no interior do
polígono ou em seu contorno.polígono ou em seu contorno.
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Preenchimento por semente
•• É importante definir a relação de vizinhança É importante definir a relação de vizinhança
entreentre pixelspixels, 4 ou 8-conectada., 4 ou 8-conectada.
VIZINHANÇA 4-CONECTADAVIZINHANÇA 4-CONECTADA
p
VIZINHANÇA 8-CONECTADAVIZINHANÇA 8-CONECTADA
p
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
 ALGORITMO PPS SIMPLES - USA PILHA FILOALGORITMO PPS SIMPLES - USA PILHA FILO - Efetua o preenchimento de - Efetua o preenchimento de
regiões partindo de um ponto interno conhecido denominado de sementeregiões partindo de um ponto interno conhecido denominado de semente
Coloque um Coloque um pixel pixel qualquer, denotado por semente qualquer, denotado por semente (s),(s), na pilha na pilha
ENQUANTOENQUANTO pilha pilha ≠≠ vazio vazio FAÇAFAÇA
-Retire um-Retire um pixel pixel pp da pilha da pilha
-Atribua o valor da cor de preenchimento ao-Atribua o valor da cor de preenchimento ao pixel pixel pp
-Para cada-Para cada pixel pixel adjacente a adjacente a pp, observe o seu, observe o seu
status. Caso seja umstatus. Caso seja um pixel pixel de contorno ou jáde contorno ou já
tenha sido visitado, ignore-os. Caso contrário,tenha sido visitado, ignore-os. Caso contrário,
coloque-os na pilha.coloque-os na pilha.
FIM ENQUANTOFIM ENQUANTO
FIM ALGORITMOFIM ALGORITMO
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Preenchimento por semente
s s
s s
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Preenchimento por semente
•• Exercício: verificar a ordem de Exercício: verificar a ordem de
preenchimento dospreenchimento dos pixels pixels pertencentes à região pertencentes à região
delimitada pelo contorno abaixo. Faça duasdelimitada pelo contorno abaixo. Faça duas
implementações para vizinhanças 4 e 8.implementações para vizinhanças 4 e 8.
Comente os resultados.Comente os resultados.
s
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Aliasing
•• Efeito gerado pela Efeito gerado pela subamostragem subamostragem de sinais (imagem).de sinais (imagem).
Halftoning
•• Técnica que utiliza uma baixa quantidade de níveis de Técnica que utiliza uma baixa quantidade de níveis de
cinza a fim de obter uma imagem de boa resolução visual.cinza a fim de obter uma imagem de boa resolução visual.
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Primitivas - OpenGL
•• Vértices definidos por um bloco Vértices definidos por um bloco
glBeginglBegin(GL_ POLYGON);(GL_ POLYGON);
 glVertex2f(0.0,0.0); glVertex2f(0.0,0.0);
 glVertex2f(0.0,3.0); glVertex2f(0.0,3.0);
 glVertex2f(3.0,3.0); glVertex2f(3.0,3.0);
 glVertex2f(4.0,1.5); glVertex2f(4.0,1.5);
 glVertex2f(3.0, 0.0); glVertex2f(3.0, 0.0);
glEndglEnd();();
•• As faces de um pol As faces de um polígono ígono possuem possuem ““frentefrente”” e e ““versoverso””
MARCO ANTONIO GARCIA DE CARVALHO
Fevereiro de 2009
Computação Gráfica
Para saber mais:
[ROGERS98] Capítulo 2
[MANSSOUR06] Capítulo 8