Rasteirização

Rasterização

Representação Vetorial x Matricial

.Normalmente, gráficos são definidos através de primitivas geométricas como pontos, segmentos de retas, polígonos, etc

!Representação vetorial

.Dispositivos gráficos podem ser pensados como matrizes de pixels (rasters)

!Representação matricial

.Rasterização é o processo de conversão entre representações vetorial e matricial

Considerações Gerais

.Rasterização é um processo de amostragem

!Domínio contínuo →discreto

!Problemas de aliasingsão esperados

.Cada primitiva pode gerar um grande número de pixels

!Rapidez é essencial

.Em geral, rasterização é feita por hardware

.Técnicas de antialiasingpodem ser empregadas, usualmente extraindo um custo em termos de desempenho

Rasterização de Segmentos de Reta

.Segmento de reta entre P1= (x1, y1) e P2= (x2, y2)

!Já foi recortado com relação ao viewport

.Objetivo é pintar os pixels atravessados pelo segmento de reta

!Na verdade, nem todos, apenas os mais próximos

.Reta de suporte dada por a x+ b y+ c= 0

.Queremos distinguir os casos

!Linhas ~ horizontais →computar ycomo função de x

!Linhas ~ verticais →computar xcomo função de y

Algoritmo Simples

.Assumimos segmentos de reta no primeiro octante, com

!Demais casos resolvidos de forma simétrica

.Inclinação(entre 0 e 1) dada por m =(y2.y1) / (x2.x1)

.Algoritmo:

!Para x desde x1até x2fazer:

.y ← y1+ m * (x .x1) + 0.5

.Pintar pixel (x, y)

Algoritmo Incremental

.Algoritmo simples tem vários problemas:

!Utiliza aritmética de ponto-flutuante

!Sujeito a erros de arredondamento

!Usa multiplicação

!Lento

.Se observarmos que mé a variação em y para um incremento unitário de x, podemos fazer ligeiramente melhor:

x← x1; y← y1

Enquanto x ≤ x2fazer:

x← x + 1

y← y+ m

Pintar pixel (x, y+ 0.5)

.Ainda usa ponto-flutuante

Algoritmo de Bresenham

.Algoritmo clássico da computação gráfica

.Algoritmo incremental que utiliza apenas soma e subtração de inteiros

.Idéia básica:

!Em vez de computar o valor do próximo yem ponto flutuante, decidir se o próximo pixel vai ter coordenadas (x + 1, y) ou (x + 1, y + 1)

!Decisão requer que se avalie se a linha passa acima ou abaixo do ponto médio (x + 1, y + ½)

.Variável de decisão Vé dada pela classificação do ponto médio com relação ao semi-espaço definido pela reta

.Caso 1: Linha passou abaixo do ponto médio

.Caso 2: Linha passou acima do ponto médio

Algoritmo de Bresenham .Coeficientes da reta!a= y2.y1!b= x1.x2!c= x2y1.x1y2.Para iniciar o algoritmo, precisamos saber o valor de V em (x1+ 1, y1+ ½)!V= a(x1+ 1) + b(y1+ ½) +c= ax1+ by1+c + a + b/2= a + b/2.Podemos evitar a divisão por 2 multiplicando a, be cpor 2 (não altera a equação da reta)0

Algoritmo de Bresenham - Resumo

a← y2.y1

b←x1.x2

V ←2 * a+ b

x ←x1

y ←y1

Enquanto x≤ x2fazer:

Pintar pixel (x, y)

x ←x + 1

Se V ≤ 0

Então V←V+ 2 * a

Senão V←V+ 2 * (a + b); y←y + 1

Extensão para demais Octantes

.Se x2< x1

!Trocar P1com P2

.Se y2< y1

!y1← -y1

!y2← -y2

!Pintar pixel (x, -y)

.Se |y2.y1| > |x2.x1|

!Repetir o algoritmo trocando .y. com .x.

Rasterização de Círculos

.Mesma idéia de avaliar incrementalmenteuma função que classifica o ponto médio entre um pixel e outro com relação a uma função implícita

.Apenas um octanteprecisa 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