Computação Gráfica
Rodrigo Toledo
Rasterização
de linhas
Desenhando uma linha
Como decidir quais
pixels devem ser
acesos para que seja
traçada uma linha?
Método 1
•Para cada coluna ascender um pixel
y
y
y

x
x
Obs: Considere os cruzamentos de linhas
e colunas como o centro dos pixels
•O que acontece quando a inclinação é maior que 1 (maior que 45º)?
•Se inclinação > 1, inverte-se x e y.
•Vamos considerar apenas o caso 0<inclinação<1
(observe que são 8 casos)
x
Método 1 – eq. da reta e algoritmo
void Line1(int x1, int y1, int x2, int y2, int color)
{
float m = (y2-y1)/(x2-x1);
float b = y1 - m*x1;
float y;
int x;
yi = m xi + b
onde:
m = Dy/Dx
b = y1 - m x1
PutPixel(x1,y1,color);
Exemplo
(x2,y2)
}
y=mx+b
b
for (x=x1+1; x<=x2; x++)
{
y = m*x + b;
PutPixel(x,ROUND(y), color);
}
(x1,y1)
(9,4)
y=(1/3)x+1
1
(3,2)
3
(3,2)
(4,2)
2
2
3
Calcula-se m e b
(5,3)
(4,2.33)
1a
iteração
2a
4
iteração
(5,2.66)
3a
5
iteração
Como melhorar o algoritmo?
void Line2(int x1, int y1, int x2, int y2, int color)
{
float m = (y2-y1)/(x2-x1);
float b = y1 - m*x1;
float y;
int x;
PutPixel(x1,y1,color);
}
for (x=x1+1; x<=x2; x++)
{
y = m*x + b;
PutPixel(x,ROUND(y), color);
}
① multiplication
Como tirar a multiplicação?
② addition
③ round operation
Método 2 – Algoritmo de linha incremental
Se
xi+1 = xi + 1
m
então
yi+1 = yi + Dy/Dx
void LineDDA(int x1, int y1, int x2, int y2, int color)
{
float y;
float m = (y2-y1)/(x2-x1);
int x;
PutPixel(x1,y1, color);
y = y1;
}
for (x=x1+1; x<=x2; x++)
{
y += m;
PutPixel(x,ROUND(y), color);
}
 Ainda são necessários uma adição de floats e uma round operation.
 É possível fazer um algoritmo apenas com somas de inteiros.
O nome desse algoritmo é: Bresenham’s algorithm.
Bresenham’s Line Drawing Algorithm
 No processo de rasterização de (x1,y1) para (x2,y2), suponha
que o pixel (xk, yk) já foi desenhado.
 Obviamente, a posição X do próximo pixel é: xk+1.
 0<m<1, então a posição Y do próximo pixel é: yk ou yk+1.
NE
yk+1
yk
E
xk
xk+1
xk
xk+1
 Qual devemos escolher? E=(xk+1, yk) or NE=(xk+1, yk+1)?
Bresenham’s Line Drawing Algorithm
 Chamemos de ek, o erro do último pixel desenhado (xk, yk).
NE
yk+1
m
ek
yk
(xk,yk)
ek+1
E
NE
yk+1
ek+1
m
ek
yk
(xk,yk)
E
Algoritmo:
 Estima-se o novo erro (ek+1) caso a escolha seja o pixel E (yk+1 = yk)

ek+1 = ek + m
 Se (ek+1 > 0.5) significa que deveríamos escolher NE (yk+1 = yk +1)
 Neste caso, o valor correto para ek+1 é:
ek+1 = ek + m – 1 (um valor negativo)
 Para facilitar o algoritmo, considere o primeiro pixel com erro = -0.5 e a
decisão passa a ser (ek+1 > 0)
Bresenham’s Line Drawing Algorithm
void BresLine0(int x1, int y1,
int x2, int y2,
int color)
{
int
Dx = x2 - x1;
int
Dy = y2 - y1;
float m = (float)Dy/Dx;
float e = -0.5;
int
x,y;
}
void BresLine1(int
int
int
{
int DDx, Dx = x2
int DDy, Dy = y2
DDx = Dx<<1;
DDy = Dy<<1;
int ei = -Dx;
int x,y;
x1, int y1,
x2, int y2,
color)
- x1;
- y1;
PutPixel(x1, y1, color);
PutPixel(x1, y1, color);
for (x=x1+1; x<=x2; x++)
{
e+=m;
if (e>=0)
{
y++;
e-=1;
}
PutPixel(x, y, color);
}
for (x=x1+1; x<=x2; x++)
{
e+=DDy;
if (e>=0)
{
y++;
e-=DDx;
}
PutPixel(x, y, color);
}
}
ei = 2*Dx*e
Para transformar todas as operações em inteiros: multiplicar por (2*Dx)
Rasterização de Retas
-caso geraly
x
y
1
outros quadrantes
2
2
1
x
orientação
Estilos de linha
void BresLine2(int x1, int y1, int x2, int y2, int color)
{
int DDx, Dx = x2 - x1;
int DDy, Dy = y2 - y1;
DDx = Dx<<1;
DDy = Dy<<1;
int ei = -Dx;
int x,y;
int style[8]={1,1,0,0,1,1,0,0}; int k=1;
PutPixel(x1, y1, color);
for (x=x1+1; x<=x2; x++)
{
e+=DDy;
if (e>=0)
{
y++;
e-=DDx;
}
if (style[(++k)%8])
PutPixel(x, y, color);
}
}
Paradigma dos 4 Universos da Linha
Universo
Físico
Universo
Matemático
Universo de
Representação
Universo de
Implementação
Uma linha consiste
em  points
Existem diversas
maneiras de se definir
matematicamente
uma linha!
A representação é feita com o
uso de alguma definição
matemática. Mas a discretização
mais relevante ocorre mesmo no
momento do raster.
• (x1,x2) (y1,y2)
• y = mx + b
• Equação implícita
• Equação paramétrica
• Variáveis para as definições
matemáticas
• Algoritmos de rasterização
• int x1, x2, y1, y2;
• Bresenham
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)
Eqaução Implícita da Reta
y
y
F ( x, y)  0
dy
xB
dx
y2
F ( x, y)  0
y1
n  dy  dx
x1
x2
x
F ( x, y )  dy. x  dx. y  B. dx  0
Usada no “algoritmo do
ponto médio” de raster de
linha:
F ( x, y)  a. x  b. y  c
NE
(três variáveis apenas: a, b e c)
yp+1/2
M
yp
E
xp
xp+1
xp+2
Equação Paramétrica da Reta
Para toda a reta:
r
γ(t) = P + tv, t R
v
P
Para um segmento de reta:
P1
P(t) = P0 + (P1 – P0)t, t [0,1]
onde: t=0 em P0
P0
e
t=1 em P1