Preenchimento de
Áreas e de Polígonos
(Filled-Area Primitives)
Antonio L. Bajuelos
Departamento de Matemática
Universidade de Aveiro
Preenchimento de Áreas e de Polígonos
Preenchimento de áreas é o processo de coloração do
interior de uma dada área ou região
região..
Ás áreas (ou regiões) podem ser descritas ao nível do:
Pixel –
Ao nível do pixel, à área é descrita ou:
pela totalidade dos pixels que a compreendem ou,
em termos dos pixels-fronteira que a delimitam
Geométrico –
Uma região é descrita em termos de objectos, tais como segmentos de
recta, polígonos, circunferências, etc.
2
Preenchimento de Áreas e de Polígonos
A tarefa de preencher um polígono pode ser dividida em duas:
Decidir que pixels pintar para preencher o polígono
polígono..
Decidir com que valor pintar o pixel
pixel..
Em geral, a decisão sobre quais pixels preencher é feita:
varrendo (scan top-down)
interceptam a primitiva e,
linhas
sucessivas
que
preenchendo da esquerda para a direita, blocos de pixels
preenchendo,
adjacentes que estão dentro da primitiva que define a
região.
3
Preenchimento de Áreas e de Polígonos
Rectângulos
Iremos assumir que:
O rectângulo é coerente no espaço i.e. que mantém a sua figura
geométrica (forma), sem alterações internas e que a cor dos seus
pixels ao longo da figura não varia.
Esta propriedade é importante e será explorada no processo de
preenchimento de regiões.
Para preencher um rectângulo com uma única cor, pinta-se cada pixel
dentro de uma linha de varrimento da esquerda para a direita com o
mesmo valor de pixel, isto é, pode-se preencher cada "bloco" de xmin a
xmax.
Para y = ymin até ymax do rectângulo
Para x = xmin até xmax
write_pixel (x, y, valor)
{Por linha de varrimento }
{Cada pixel dentro do bloco}
4
Preenchimento de Áreas e de Polígonos
Rectângulos (cont …)
Consideremos agora dois rectângulos que compartilham um mesmo lado.
Atenção! Se preenchermos cada rectângulo isoladamente, o lado
(aresta) compartilhado pelos dois será gerado duas vezes o que não é
desejável.
Surge então o problema de definição de área pertencente a cada
primitiva, isto é, quais os pixels que pertencem a cada primitiva e
quais os pixels que não.
De forma natural, podemos definir os pixels que matematicamente se
encontram no interior de uma área definida pela primitiva, como
pertencente a ela.
Mas como podemos definir os pixels que estão
no limite da primitiva?
5
Preenchimento de Áreas e de Polígonos
Rectângulos (cont …)
Uma solução de “compromisso”:
Os pixels que estão sobre os lados (arestas) esquerdo e
inferior pertencem a primitiva e serão desenhados,
porém os lados superior e direito não pertencem a
primitiva e portanto não serão desenhados
Assim, uma aresta vertical compartilhada por dois rectângulos
pertencem ao lado que está mais a direita.
Os blocos dentro de um rectângulo representam um intervalo que é
fechado a esquerda e em baixo e aberto em cima e a direita
6
Preenchimento de Áreas e de Polígonos
Rectângulos (cont …)
Algumas considerações devem ser feitas sobre esta regra:
A regra se aplica da mesma forma a polígonos arbitrários e não
somente a rectângulos.
O vértice do canto inferior esquerdo ainda continua sendo
desenhado duas vezes.
A regra faz com que em cada bloco esteja faltando o seu pixel mais
a direita, e em cada rectângulo fique faltando o seu lado (aresta)
superior.
Os problemas apresentados nas considerações acima
demonstram que não há solução perfeita para o problema de
não escrever mais de uma vez linhas que sejam
potencialmente compartilhadas por mais de um polígono
polígono..
7
Preenchimento de Áreas e de Polígonos
Preenchimento por Gérmen
Neste tipo de métodos o utilizador
deverá indicar um pixel inicial chamado
gérmen (seed). Este gérmen deve estar
no interior do polígono.
A partir do gérmen
gérmen, o algoritmo
inspecciona os pixels adjacentes para
determinar se toda a região já foi
coberta.
O processo é repetido até que todos os
pixels do interior da região tenham sido
inspeccionados.
Este tipo de métodos de preenchimento
é indicado para aplicações interactivas.
8
Preenchimento de Áreas e de Polígonos
Preenchimento por Gérmen
Existem dois tipos básicos de preenchimento por gérmen
gérmen:
Preenchimento por Saturação (Flood
Flood--Fill
Fill))
Este método é utilizado quando a fronteira da região é
monocromática. O objectivo é, a partir do gérmen P,
determinar a maior região ligada de pontos cujo cor (valor de
pixel) é igual ao valor de P.
Preenchimento por Fronteira (Boundary
Boundary--Fill
Fill))
Este método é usualmente utilizado quando a fronteira da
região pode ser definida por primitivas policromáticas. Neste
caso o objectivo é determinar a maior região ligada de pontos
cujo cor (valor de pixel) não é igual ao valor da fronteira.
9
Preenchimento de Áreas e de Polígonos
Preenchimento por Gérmen
Os algoritmos do tipo Flood
Flood--Fill e do tipo Boundary
Boundary--Fill
podem ser implementados na versões 4 ou 8-connected
4 movimentos: N, S , E, W
8 movimentos: N, S , E, W, NE, NW, SE, SW
A versão 4-connected é mais rápida mas NÃO garante a
cobertura de todos os tipos de regiões
Estes algoritmos são altamente recursivos podendo gerar
problemas de stack overflow (utilização excessiva de
memória)
10
Preenchimento de Áreas e de Polígonos
Algoritmo Boundary
Boundary--Fill
(Versão 4-connected)
void BoundaryFill4(int x, int y, color newcolor, color edgecolor)
{
int current;
current = ReadPixel(x, y);
if(current != edgecolor && current != newcolor)
{
BoundaryFill4(x+1, y, newcolor, edgecolor);
BoundaryFill4(x-1, y, newcolor, edgecolor);
BoundaryFill4(x, y+1, newcolor, edgecolor);
BoundaryFill4(x, y-1, newcolor, edgecolor);
}
}
11
Preenchimento de Áreas e de Polígonos
Algoritmo Flood
Flood--Fill
(Versão 4-connected)
void FloodFill4(int x, int y, color newcolor, color oldColor)
{
if(ReadPixel(x, y) == oldColor)
{
FloodFill4(x+1, y, newcolor, oldColor);
FloodFill4(x-1, y, newcolor, oldColor);
FloodFill4(x, y+1, newcolor, oldColor);
FloodFill4(x, y-1, newcolor, oldColor);
}
}
* Replace a specified interior color (old color) with fill color
12
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
O algoritmo que vamos discutir a seguir é válido para
polígonos de forma arbitrário (côncavos e convexos).
Inclusive funciona para polígonos com auto-intersecções
e/ou buracos.
Este algoritmo opera determinando blocos de pixels que
estão entre os lados mais à esquerda e mais à direita do
polígono.
13
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
Ideias básicas
Calcula o preenchimento sempre entre as arestas mais à
esquerda e mais à direita
Incrementalmente calcula a intersecção da linha raster
(scan line) com as arestas do polígono, a partir da
anterior linha raster
14
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
Na figura: as intersecções da linha de varrimento 8 com os lados FA
e CD possuem coordenadas inteiras, enquanto as intersecções com
os lados EF e DE possuem coordenadas reais (não inteiras).
É preciso determinar que pixels da linha de varrimento estão dentro
do polígono.
No exemplo da figura: Os blocos para x = 2 até 4 e 9 até 13 com
seu valor apropriado.
15
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
Algumas observações
Devemos nos preocupar com a definição dos pontos extremos do
polígono, i.e. não podemos desenhar pixels que não pertençam
verdadeiramente ao interior do polígono, pois podemos estar invadindo o
domínio de outro polígono
É preferível traçar apenas os pixels que estejam estritamente na
região definida pelo polígono, mesmo que um pixel exterior esteja
mais próximo a aresta real.
real.
16
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
O processo de preencher os polígonos pode ser dividido em
três passos:
Obter a intersecção da linha de varrimento com todos os
lados do polígono.
Ordenar os pontos de intersecção (por incremento da
coordenada x).
Preencher os pixels entre pares de pontos de intersecção
do polígono que são internos a ele. Para determinar
quais os pares que são internos ao polígono, podemos
usar a regra de Paridade
17
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
Regra da Paridade
Paridade::
Iniciando com par, sempre que encontra uma intersecção inverte a
paridade.
O pixel é pintado quando a paridade é impar
O pixel NÃO é pintado quando é par.
18
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
Caso I: Se a intersecção é um valor
fraccionário, como determinar qual o
pixel que deverá ser tomado para que
fique interior ao polígono?
O valor deverá ser arredondado de
forma a que o ponto fique dentro do
polígono. Passos a seguir:
Se estamos dentro do polígono
(paridade ímpar) e atingimos uma
intersecção fraccionária pela direita
(exemplo, o ponto b), arredondamos a
coordenada x da intersecção para
baixo.
Se estamos fora do polígono (paridade
par) arredondamos para cima(exemplo,
o ponto c). Isso garante que sempre
teremos um ponto dentro do polígono.
19
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
Caso II: Como tratar o caso de
intersecção com coordenadas inteiras?
Pode-se utilizar o critério visto
anteriormente, para evitar conflitos
entre
lados
compartilhados
em
rectângulos. Passos a seguir:
Se a coordenada x de um pixel mais a
esquerda de um bloco (span) é inteira
ele é definido como interno (exemplo, o
ponto a).
Se a coordenada x do pixel mais a
direita de um bloco é inteira, ele é
definido como externo ao polígono
(exemplo, o ponto d).
20
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
Caso III: Como tratar o caso II para
vértices que são compartilhados por mais
de uma aresta do polígono?
Usamos a técnica de paridade. Ou seja:
Contamos o vértice de ymin de um lado
para alterar a paridade, mas não
contamos o vértice de ymax, dessa forma
o vértice de ymax é desenhado somente
se ele é o vértice de ymin do lado
adjacente.
Assim ambos os lados e blocos são
tratados como intervalos que são
fechados em seu valor mínimo e
abertos em seu valor máximo.
Exemplo: Na figura, o vértice
A é contado uma vez no
cálculo de paridade porque é
o vértice de ymin para o lado
FA, mas é também o vértice
de ymax para o lado AB.
21
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
Ilustração do algoritmo:
Para a linha de varrimento y = 8:
Os pixels serão preenchidos a partir do ponto
a (coordenadas (2,8)), até o primeiro pixel a
esquerda do ponto b (coordenadas (4,8));
E do primeiro pixel a direita do ponto c
(coordenadas (9,8)) até o primeiro pixel a
esquerda do ponto d (coordenadas (12,8)).
Para a linha de varrimento y = 3:
O vértice A conta uma vez porque é o vértice
de ymin do lado FA (e é também o vértice ymax
do lado AB), isto causa paridade ímpar, assim
o bloco é desenhado a partir de A até um
pixel a esquerda da intersecção com o lado
CB, onde a paridade é estabelecida como par
e o bloco é terminado.
22
Preenchimento de Áreas e de Polígonos
Preenchimento de Polígonos (ScanScan-Line Algorithm
Algorithm))
Ilustração do algoritmo (cont…):
Para a linha de varrimento y = 1
Ela passa apenas pelo vértice B, e os lados AB
e BC tem como vértice de ymin o vértice B, o
qual é dessa forma contado como paridade par.
Este vértice actua como um bloco nulo, pois a
linha de varrimento entra pelo vértice, desenha
o pixel e sai por ele mesmo.
Assim, o pixel que corresponde ao ponto B
não é pintado.
Isso acontece com a intersecção da linha de
varrimento 9 com o vértice F, compartilhado
pelos lados FA e EF. Para ambos os lados, F é
vértice ymax, e dessa forma não afecta a
paridade, que continua par.
23
Preenchimento de Áreas e de Polígonos
Slivers (tiras)
Existe um outro problema com o nosso algoritmo de
conversão matricial: polígonos com lados muito
próximos criam um sliver
Sliver - uma área poligonal tão estreita que seu interior não
contém um bloco de pixels para cada linha de varrimento
(ver figura).
Devido à regra de que são traçados apenas os pixels que
estejam no interior ou sobre arestas inferiores ou a
esquerda, podem existir muitas linhas de varrimento com
um único pixel, ou sem nenhum.
Para melhorar a aparência nesses casos, pode-se usar
técnicas de antialiasing (se tivermos múltiplos bits por
pixel).
Antialiasing implicaria em "suavizar" nossa regra de
"traçar apenas pixels que estejam no interior ou numa
aresta inferior ou à esquerda"
24