Preenchimento de Polígonos
Computação Gráfica
Rodrigo Toledo
Polygon Filling
Como preencher um polígono arbitrário?
Quais pixels devem ser acesos?
Começando com um retângulo
Quais pixels devem ser acesos?
Esse é o resultado esperado?
O que aconteceu com os pixels da linha superior e da
coluna direita? Isso é bom por que?
Nenhum pixel deve pertencer a
dois polígonos simultaneamente!
• Eficiência  não ascendendo duas vezes o mesmo pixel!
• Interpretação  Se os polígonos são de cores diferentes, a
cor final irá depender da ordem em que são desenhados!
Idéias gerais sobre Polygon Fill
• Ascender pixels nas bordas inferior e esquerda, não
ascender nas bordas superior e direita.
• Se a borda estiver entre pixels em uma determinada
linha, arredondar para o inteiror (arredondar a
esquerda se for uma borda direita e arredondar a
direita se for uma borda a esquerda).
• O algoritmo deverá computar as interseções das
bordas com cada scan line horizontal, ascendendo os
pixels que estiverem entre os pares de interseções.
Primeiro rascunho do algoritmo
y
ymax
ys
1
i1
dados:
{x0, x1, x2, x3, x4}
{y0, y1, y2, y3, y4}
4
i0
i4
i3
acha ymax e ymin
Para cada ys[ymax , ymin]
0
ymin
Para cada aresta
2
3
0
xi1
xi0
xi4
vx= {xi1 , xi0 , xi4 , xi3}
xi3
calcula as interseções
x
ordena interseções
desenha linhas horizontais
Scan line cruzando vértices
y
1
0
i0
ys
i1 i2
i4
5 i3
3
2
4
0
x
inclui vértices:
i0-i1, i2-i3, i4-?
não inclui vértices:
i0-?
y
y
1
ys
i0
i1 i2
3
0
1
i4
i3 5
ys
3
L
5
L
2
2
4
0
0
i0
4
x
0
x
Tratando cruzamento com vértices
y
1
ys
i0
0
i1 i2
3
i4
5 i3
2
4
0
x
só inclui vértices de menor y:
i0-i4
J
Excluindo
bordas superiores
ou
só inclui vértices de maior y:
i0-i1, i2-i3
J
Bordas horizontais devem respeitar a regra da paridade!
Regra da paridade
(even-odd parity rule)
•Um ponto é considerado
dentro de um polígono se
uma raio vindo do infinito
cruzar um número par de
bordas!
A
B
•Ao se respeitar a regra de “só inclui vértices de menor y” e fazendo o controle
de paridade, naturalmente as bordas horizontais inferiores serão
desenhadas e as superiores não!
Cuidado!
Algoritmo
void FillPolygon (int np, int x[], int y[])
{
/* declarações */
. . .
/* calcula y max e min dos vértices*/
. . .
for(ys=ymim; ys<ymax; ys--)
/* para cada linha de scan (exceto a última)*/
{
num_inters = 0;
for(i=0; i<np; i++)
/* para cada aresta */
{
yi = y[i];
//y do vert. inicial da aresta
yf = y[(i+1)%np]; //y do vert. final da aresta
if (yi!=yf && ys >= MIN(yi,yf) && ys < MAX(yi,yf) )
{
vxs[num_inters] = x[i] + (ys-yi)*(x[(i+1)%np]-x[i])/(yf-yi));
num_inters++;
}
}
ordena(vxs,0,num_inters-1); /* ordena as interseções */
for (i=0;i<num_inters;i+=2)
if (vxs[i]+1 < vxs[i+1])
HLine(vxs[i],vxs[i+1],ys);
}
// Exceto o ultimo pixel
Algoritmo
void FillPolygon (int np, int x[], int y[])
{
/* declarações */
. . .
Exclui linha superior
/* calcula y max e min dos vértices*/
. . .
for(ys=ymim; ys<ymax; ys--)
/* para cada linha de scan (exceto a última)*/
{
num_inters = 0;
for(i=0; i<np; i++)
/* para cada aresta */
{
yi = y[i];
//y do vert. inicial da aresta
yf = y[(i+1)%np]; //y do vert. final da aresta
if (yi!=yf && ys >= MIN(yi,yf) && ys < MAX(yi,yf) )
{
vxs[num_inters] = x[i] + (ys-yi)*(x[(i+1)%np]-x[i])/(yf-yi));
num_inters++;
}
}
ordena(vxs,0,num_inters-1); /* ordena as interseções */
for (i=0;i<num_inters;i+=2)
if (vxs[i]+1 < vxs[i+1])
HLine(vxs[i],vxs[i+1],ys);
}
// Exceto o ultimo pixel
Algoritmo
void FillPolygon (int np, int x[], int y[])
{
/* declarações */
. . .
/* calcula y max e min dos vértices*/
. . .
o vértice final da última
aresta é o vértice inicial
da primeira
for(ys=ymim; ys<ymax; ys--)
/* para cada linha de scan (exceto a última)*/
{
num_inters = 0;
for(i=0; i<np; i++)
/* para cada aresta */
{
yi = y[i];
//y do vert. inicial da aresta
yf = y[(i+1)%np]; //y do vert. final da aresta
if (yi!=yf && ys >= MIN(yi,yf) && ys < MAX(yi,yf) )
{
vxs[num_inters] = x[i] + (ys-yi)*(x[(i+1)%np]-x[i])/(yf-yi));
num_inters++;
}
}
ordena(vxs,0,num_inters-1); /* ordena as interseções */
for (i=0;i<num_inters;i+=2)
if (vxs[i]+1 < vxs[i+1])
HLine(vxs[i],vxs[i+1],ys);
}
// Exceto o ultimo pixel
Algoritmo
void FillPolygon (int np, int x[], int y[])
{
/* declarações */
. . .
/* calcula y max e min dos vértices*/
. . .
for(ys=ymim; ys<ymax; ys--)
/* para cada linha de scan (exceto a última)*/
{
num_inters = 0;
for(i=0; i<np; i++)
/* para cada aresta */
{
yi = y[i];
//y do vert. inicial da aresta
yf = y[(i+1)%np]; //y do vert. final da aresta
Δx/Δy
if (yi!=yf && ys >= MIN(yi,yf) && ys < MAX(yi,yf) )
{
vxs[num_inters] = x[i] + (ys-yi)*(x[(i+1)%np]-x[i])/(yf-yi));
num_inters++;
}
}
ordena(vxs,0,num_inters-1); /* ordena as interseções */
for (i=0;i<num_inters;i+=2)
if (vxs[i]+1 < vxs[i+1])
HLine(vxs[i],vxs[i+1],ys);
}
// Exceto o ultimo pixel
Otimizações do algoritmo de fill
y
ymax
x = x+dx
ys+1
ys
dy = 1
ymin
x0
Lista de Arestas
struct edge
{
int
y_max;
int
y_min;
float
xs;
x1
x (ou z)
dx = (x1-x0)/(ymax-ymin)
/* maior y da aresta */
/* menor y da aresta */
/* x correspondente a ys */
/* (no início é o correspondente a y_max) */
float delta_xs; /* incremento de xs entre duas linhas de scan */
};
Algoritmo de Fill de Polígonos
(Parte 1-Alocação de Memória)
#define MAX(a,b)
#define MIN(a,b)
(((a) > (b)) ? (a) : (b))
(((a) < (b)) ? (a) : (b))
void fill (int np, int *x, int *y)
{
static struct edge *aresta=NULL;
/* vetor de arestas */
static int *vxs=NULL;
/* vetor de interseções */
static int old_np=0;
/* número de pontos da última chamada */
int
int
int
int
int
ymax, ymin;
num_inters;
num_arestas;
ys;
i;
/*
/*
/*
/*
limites do polígono */
num. de interseções */
num. de arestas */
ordenada da reta de scan */
/* realoca os vetores de arestas e de interseções */
if (np > old_np)
{
old_np=np;
if (vxs) free (vxs);
if (aresta) free (aresta);
vxs=(int *) malloc ((np-1)*sizeof(int)); /* max num. De inters.*/
aresta=(struct edge *) malloc (np*sizeof(struct edge));
}
/* CONTINUA NA PARTE 2 */
Algoritmo de Fill de Polígonos
(Parte 2-Lista de Arestas)
/* PARTE 1*/
/* calcula y max e min e monta o vetor de arestas */
ymax = y[0];
ymin = y[0];
num_arestas = 0;
for(i=0;i<np;i++)
{
int i1=(i+1)%np;
if (y[i] != y[i1])
{
aresta[num_arestas].y_max = MAX(y[i],y[i1]);
aresta[num_arestas].y_min = MIN(y[i],y[i1]);
aresta[num_arestas].delta = ((float)(x[i1]-x[i])/(float)(y[i1]-y[i]));
if (aresta[num_arestas].y_mim == y[i])
aresta[num_arestas].xs = x[i];
else
aresta[num_arestas].xs = x[i1];
ymax = MAX( ymax, aresta[num_arestas].y_max );
ymin = MIN( ymin, aresta[num_arestas].y_min );
num_arestas++;
}
}
/* CONTINUA NA PARTE 3 */
Algoritmo de Fill de Polígonos
(Parte 2-Lista de Arestas)
/* PARTE 1*/
Ignorando arestas
horizontais
/* calcula y max e min e monta o vetor de arestas */
ymax = y[0];
ymin = y[0];
num_arestas = 0;
for(i=0;i<np;i++)
{
int i1=(i+1)%np;
if (y[i] != y[i1])
{
aresta[num_arestas].y_max = MAX(y[i],y[i1]);
aresta[num_arestas].y_min = MIN(y[i],y[i1]);
aresta[num_arestas].delta = ((float)(x[i1]-x[i])/(float)(y[i1]-y[i]));
if (aresta[num_arestas].y_mim == y[i])
aresta[num_arestas].xs = x[i];
else
aresta[num_arestas].xs = x[i1];
ymax = MAX( ymax, aresta[num_arestas].y_max );
ymin = MIN( ymin, aresta[num_arestas].y_min );
num_arestas++;
}
}
/* CONTINUA NA PARTE 3 */
Algoritmo de Fill de Polígonos
(Parte 2-Lista de Arestas)
/* PARTE 1*/
min e max da aresta
/* calcula y max e min e monta o vetor de arestas */
ymax = y[0];
ymin = y[0];
num_arestas = 0;
for(i=0;i<np;i++)
{
int i1=(i+1)%np;
if (y[i] != y[i1])
{
aresta[num_arestas].y_max = MAX(y[i],y[i1]);
aresta[num_arestas].y_min = MIN(y[i],y[i1]);
aresta[num_arestas].delta = ((float)(x[i1]-x[i])/(float)(y[i1]-y[i]));
if (aresta[num_arestas].y_mim == y[i])
aresta[num_arestas].xs = x[i];
else
aresta[num_arestas].xs = x[i1];
ymax = MAX( ymax, aresta[num_arestas].y_max );
ymin = MIN( ymin, aresta[num_arestas].y_min );
num_arestas++;
}
}
/* CONTINUA NA PARTE 3 */
Algoritmo de Fill de Polígonos
(Parte 2-Lista de Arestas)
/* PARTE 1*/
min e max do
polígono
/* calcula y max e min e monta o vetor de arestas */
ymax = y[0];
ymin = y[0];
num_arestas = 0;
for(i=0;i<np;i++)
{
int i1=(i+1)%np;
if (y[i] != y[i1])
{
aresta[num_arestas].y_max = MAX(y[i],y[i1]);
aresta[num_arestas].y_min = MIN(y[i],y[i1]);
aresta[num_arestas].delta = ((float)(x[i1]-x[i])/(float)(y[i1]-y[i]));
if (aresta[num_arestas].y_mim == y[i])
aresta[num_arestas].xs = x[i];
else
aresta[num_arestas].xs = x[i1];
ymax = MAX( ymax, aresta[num_arestas].y_max );
ymin = MIN( ymin, aresta[num_arestas].y_min );
num_arestas++;
}
}
/* CONTINUA NA PARTE 3 */
Algoritmo de Fill de Polígonos
(Parte 3-Varredura)
/* PARTES 1 E 2 */
for(ys=ymin; ys<ymax; ys++) /* para cada linha de scan */
{
num_inters = 0;
for(i=0; i<num_arestas; i++)
{
if (aresta[i].y_max < ys)
/* retira da lista de arestas */
{
aresta[i] = aresta[num_arestas-1];
num_arestas--;
}
if((ys>=aresta[i].y_min)&&(ys<aresta[i].y_max)) /* intersepta */
{
vxs[num_inters] = aresta[i].xs;
aresta[i].xs += aresta[i].delta; /* atualiza o xs */
num_inters++;
}
} /* for */
ordena(vxs,0,num_inters-1);
for(i=0;i<num_inters;i+=2)
if (vxs[i]+1 <= vxs[i+1])
hline(vxs[i],vxs[i+1],ys,0xff);
}
} /* fill */
/* FIM */
/* ordena as interseções */
Algoritmo de Fill de Polígonos
(Parte 3-Varredura)
/* PARTES 1 E 2 */
for(ys=ymin; ys<ymax; ys++) /* para cada linha de scan */
{
num_inters = 0;
for(i=0; i<num_arestas; i++)
{
if (aresta[i].y_max < ys)
/* retira da lista de arestas */
{
aresta[i] = aresta[num_arestas-1];
num_arestas--;
}
Descarta definitivamente as
arestas que já foram scaneadas
if((ys>=aresta[i].y_min)&&(ys<aresta[i].y_max)) /* se intersepta */
{
vxs[num_inters] = aresta[i].xs;
/* guarda o x da intersecao */
aresta[i].xs += aresta[i].delta;
/* atualiza o xs */
num_inters++;
}
} /* for */
ordena(vxs,0,num_inters-1);
for(i=0;i<num_inters;i+=2)
if (vxs[i]+1 <= vxs[i+1])
hline(vxs[i],vxs[i+1],ys,0xff);
}
} /* fill */
/* FIM */
/* ordena as interseções */
Algoritmo de Fill de Polígonos
(Parte 3-Varredura)
/* PARTES 1 E 2 */
for(ys=ymin; ys<ymax; ys++) /* para cada linha de scan */
{
num_inters = 0;
for(i=0; i<num_arestas; i++)
{
if (aresta[i].y_max < ys)
/* retira da lista de arestas */
{
aresta[i] = aresta[num_arestas-1];
num_arestas--;
}
Aceita interseção com vértice
se for ymin, mas não se ymax
if((ys>=aresta[i].y_min)&&(ys<aresta[i].y_max)) /* se intersepta */
{
vxs[num_inters] = aresta[i].xs;
/* guarda o x da intersecao */
aresta[i].xs += aresta[i].delta;
/* atualiza o xs */
num_inters++;
}
} /* for */
ordena(vxs,0,num_inters-1);
for(i=0;i<num_inters;i+=2)
if (vxs[i]+1 <= vxs[i+1])
hline(vxs[i],vxs[i+1],ys,0xff);
}
} /* fill */
/* FIM */
/* ordena as interseções */
Stipples, patterns e imagens
Stipple
void SetPixel(int x,int y)
{
int i=(x-x0)%w;
int j=(y-y0)%h;
if (stipple[i][j]) {
Pixel(x,y,foreground);
} else {
if (backopacity) Pixel(x,y,background);
}
h=5
w=5
}
Pattern
void SetPixel(int x,int y)
{
color = pattern[(x-x0)%w][(y-y0)%h]
Pixel(x,y,color);
}
Comentários
• Os triângulos podem ser tratados como um caso especial
(mais eficiente).
y
A
yA
c
b
yB
B
aa
yC
• Slivers: triângulos muito finos.
C
xl
• Polígonos simétricos podem não ser desenhados simetricamente!
• Pintar somente o interior quando as arestas já tiverem sido desenhadas.
• Existem situações em que um pixel pode pertencer a dois polígonos.(?)
• Como melhorar este algoritmo? AET (Active Edge Table)
• Foley: excelente para Bresenham, poly fill e clipping (próxima aula).
xr
x
Active Edge Table Algorithm
..
.
0 1 2 3 4 5 6 7
4
3
2
1
0
y=0
ET
4
3
2
1
0
AET
2
3
-1 1/2
4 0 0
4 6 0
4 3 -3/2
2
3
4 3 3/2
1 1/2
Draw from 0, 3-3 (not including 3) Aka: Do nothing
Active Edge Table Algorithm
..
.
0 1 2 3 4 5 6 7
4
3
2
1
0
y=1
ET
4
3
2
1
0
AET
2 1 1/2 -1 1/2
Draw from 1, 2-5 (not inclusive)
4 0 0
4 6 0
4 3 -3/2
4 3 3/2
2 4 1/2 1 1/2
Active Edge Table Algorithm
..
.
0 1 2 3 4 5 6 7
4
3
2
1
0
y=2
ET
4
3
2
1
0
AET
4
0
4
0
3
Draw from 2, 0-3 and 3,6
1 1/2
4
3
4
-1 1/2
6
0
Active Edge Table Algorithm
..
.
0 1 2 3 4 5 6 7
4
3
2
1
0
y=3
ET
4
3
2
1
0
AET
4
0
0
4 4 1/2 1 1/2
Draw from 3, 0-2 and 5,6
4 1 1/2 -1 1/2
4
6
0
Active Edge Table Algorithm
..
.
0 1 2 3 4 5 6 7
4
3
2
1
0
y=4
ET
4
3
2
1
0
AET
Done!