Rasterização,
Anti-aliasing e Preenchimento
Alex F. V. Machado
[email protected]
Rasterização: Revisão
1.
2.
3.
4.
O que é rasterização?
Que métricas podemos usar para definir se um algoritmo de
rasterização de seguimentos de reta é melhor do que um outro?
Quais foram os algorimos de rasterização de seguimentos de retas
estudados?
Aplique o algoritmo de Bresenham para unir os pontos das
seguintes imagens, posteriormente defina sua forma de aplicação.
Amostragem, Aliasing, e Anti-aliasing
 A linha, que no universo físico é contínua, é amostrada em uma
matriz finita 2D de pixels.
 Tal discretização pode causar distorções visuais como
cisalhamento ou efeito de escada.
 Essas distorções são chamadas de aliasing.
 Para reduzir o problema de aliasing, usa-se uma técnica
chamada anti-aliasing.
 A técnica consiste em uma superamostragem (uma vez que o
aliasing é causada por uma subamostragem)
SUPERAMOSTRAGEM
 Superamostragem = Amostrar um objeto numa resolução maior do
que será reconstruído.
dividir os pixels em subpixels (i.e. 9), aplicar o
algoritmo de Bresenham
nesses sub-pixels
contar o número de
sub-pixels “acesos”
por pixel
O pixel será aceso com
intensidade proporcional
ao número de sub-pixels
acesos.
1
3
3
2
3
3
Exemplo de Anti-aliasing em Linhas
 Observe que quando a cor de fundo não é preto, o anti-aliasing
deve fazer uma composição da intensidade com a cor de fundo.
 Anti-aliasing é necessário não só para linhas, mas também para
polígonos e texturas (o que já é mais complicado)
Rasterização de Círculos
• Mesma idéia de avaliar
incrementalmente uma função
que classifica o ponto médio entre
um pixel e outro com relação a
uma função implícita
• Apenas um octante precisa ser
avaliado, os demais são
simétricos
– Para cada pixel computado, oito
são pintados
• Derivação um pouco mais difícil
que a da reta
• Outras cônicas podem também
ser rasterizadas de forma
semelhante
E
V1
V0
SE
C(x,y) = 0
V1’
y
x
Preenchimento de regiões
• Fill methods: 2 algoritmos
– Boundary Fill
– Flood Fill (para bordas multicoloridas)
– Atuam ao nível do pixel
– Interessantes para aplicações do tipo painting
• Scanline-Fill Approaches
– Atuam no nível dos polígonos
– Melhor performance
Fill Methods
• Algoritmos não tratam objetos isoladamente
• Dá-se um ponto interior a figura e prossegue-se até a
borda
• Similar a função existente em aplicativos do tipo
paintbrush
• Denominados seed-fill (preenchimento a partir da
semente)
• Dado um pixel qualquer, quais são seus vizinhos?
– 4-connected
– 8-connected
Fill Methods
•
•
•
•
•
Inicia com um ponto dentro de uma região
Pinta o interior até a próxima aresta
Deve ser definida a cor da aresta
Pinta regiões 4-connected ou 8-connected
Regiões 4-connected são mais rápidas, mas
podem apresentar problemas
Fill Methods
• Algoritmo recursivo
– Preenche vizinhos da semente que atendem
ao critério
– Aplica o algoritmo recursivamente tomando
esses vizinhos como sementes
– Termina quando nenhum vizinho atende o
critério
Fill Methods
Algoritmo de Preenchimento
• Pseudo-código:
Procedure FloodFill (x, y, cor, novaCor)
Se pixel (x, y) = cor então
pixel (x, y) ← novaCor
FloodFill (x + 1, y, cor , novaCor)
FloodFill (x, y + 1, cor , novaCor)
FloodFill (x - 1, y, cor , novaCor)
FloodFill (x, y - 1, cor , novaCor)
• Uso abusivo de recursão pode ser contornado
preenchendo intervalos horizontais iterativamente
Algoritmos scanline-fill
(Rasterização de Polígonos)
• Operação fundamental em computação
gráfica
• Polígono é dado por uma lista de vértices
– Último vértice = primeiro vértice
• Usar conceito de paridade
Algoritmos scanline-fill
(Rasterização de Polígonos)
• Algoritmo clássico usa
técnica de varredura
y
ymax
– Arestas são ordenadas
a
• Chave primária: y mínimo
• Chave secundária: x mín.
• Exemplo: (e,d,a,b,c)
– Linha de varredura
perpendicular ao eixo y
percorre o polígono
(desde ymin até ymax)
– Intervalos horizontais
entre pares de arestas
são preenchidos
b
c
d
ymin
e
x