Upload
doanbao
View
224
Download
1
Embed Size (px)
Citation preview
Preenchimento de Polígonos
Preenchimento de Polígonos
SCC0250 - Computação Grá�ca
Prof. Fernando V. Paulovichhttp://www.icmc.usp.br/~paulovic
Instituto de Ciências Matemáticas e de Computação (ICMC)Universidade de São Paulo (USP)
24 de maio de 2011
1 / 46
Preenchimento de PolígonosIntrodução
Sumário
1 Introdução
2 Teste de Interior-Exterior
3 Preenchimento de ÁreasAlgoritmo ScanlinePreenchimento de Regiões Irregulares
2 / 46
Preenchimento de PolígonosIntrodução
Sumário
1 Introdução
2 Teste de Interior-Exterior
3 Preenchimento de ÁreasAlgoritmo ScanlinePreenchimento de Regiões Irregulares
3 / 46
Preenchimento de PolígonosIntrodução
Introdução
Além do desenho de linhas, uma outra construção útil é opreenchimento de áreas
Usado para descrever superfícies ou objetos sólidos
Embora qualquer forma possa ser preenchida, normalmente as APIsgrá�cas suportam polígonos
Maior e�ciência por serem descritos por equações linearesMaioria da superfícies curvas podem ser aproximadas por polígonos
4 / 46
Preenchimento de PolígonosIntrodução
Introdução
Aproximação de uma curva é normalmente chamada de tesselaçãode uma superfície ou malha de polígonos
Essas aproximações podem ser rapidamente geradas como visõeswire-frame
5 / 46
Preenchimento de PolígonosIntrodução
Introdução
Um polígono é uma �gura plana especi�cada por um conjunto de 3ou mais vértices (posições) ligados sequencialmente por arestas(linhas retas)
Arestas só tem pontos comuns nos seus inícios e �nsTodos os vértices no mesmo plano
Devido a erros de arredondamento, as arestas de um polígonopodem não ser coplanares
Usar triângulos para resolver esse problema
6 / 46
Preenchimento de PolígonosIntrodução
Classi�cação de Polígonos
Se todos os ângulos interiores de um polígono forem menores que1800, o polígono é convexo caso contrário é dito côncavo
Em um polígono convexo, dois pontos interiores de�nem umsegmento de reta também no interior
7 / 46
Preenchimento de PolígonosIntrodução
Classi�cação de Polígonos
O termo Polígono Degenerado descreve um polígono com vérticescolineares, ou que apresenta vértices repetidos
Uma API grá�ca para ser robusta deve rejeitar polígonos nãoplanares ou degenerados
Na verdade isso é deixado a cargo do programador
8 / 46
Preenchimento de PolígonosIntrodução
Classi�cação de Polígonos
APIs grá�cas normalmente só trabalham com polígonos convexos
Melhor dividir um polígono côncavo em um conjunto de polígonosconvexosOpenGL requer que todos os polígonos sejam convexos
9 / 46
Preenchimento de PolígonosIntrodução
Identi�cando Polígonos Côncavos
Criar vetores com as arestas e fazer o produto vetorial de arestasadjacentes
A coordenada-z de todos os produtos deve ter o mesmo sinal emum polígono convexo
10 / 46
Preenchimento de PolígonosIntrodução
Dividindo Polígonos Côncavos
Dividindo Polígonos Côncavos
Criar vetores para dois vértices consecutivosEk = Vk+1 − Vk
Calcular o produto vetorial desses no sentido anti-horárioSe algum produto for negativo, o polígono é côncavo
Dividir o polígono ao longo da linha do primeiro vértice
11 / 46
Preenchimento de PolígonosIntrodução
Dividindo em Polígono em Triângulos
Um polígono convexo pode ser dividido em triângulos
Pegue quaisquer três vértices consecutivos e forme um triânguloRemova o vértice do meio da lista de triângulosRepita o procedimento até restarem 3 vértices
12 / 46
Preenchimento de PolígonosTeste de Interior-Exterior
Sumário
1 Introdução
2 Teste de Interior-Exterior
3 Preenchimento de ÁreasAlgoritmo ScanlinePreenchimento de Regiões Irregulares
13 / 46
Preenchimento de PolígonosTeste de Interior-Exterior
Testes de Interior-Exterior
Vários processos grá�cos precisam identi�car regiões interiores deobjetos mais complexos que quadrados ou círculos
Dois algoritmosRegra par-impar (ou regra da paridade impar)Regra do winding-number não zero
14 / 46
Preenchimento de PolígonosTeste de Interior-Exterior
Regra Par-Impar
Desenhar um segmento de reta de um ponto P a um ponto distantefora dos limites de coordenadas do polígono
Contar os cruzamentos de arestas com esse segmentoSe o número for ímpar, P está dentro
Caso contrário P está fora
Assegurar que o segmento não intercepta nenhum vértice
15 / 46
Preenchimento de PolígonosTeste de Interior-Exterior
Regra do Winding-number não zero
Conta o número de vezes que a fronteira de um objeto gira emvolta de um ponto particular na direção anti-horária
Um ponto é dito interior se sua contagem for diferente de zero
Algoritmo
Inicializa a contagem com zeroDe�ne um segmento de reta de uma posição P até um pontodistante
Não pode passar pelos vértices
Conta a quantidade de cruzamentos com as arestas (direcionais)+1 toda vez que cruzar uma aresta da direita para esquerda
−1 toda vez que cruzar uma aresta da esquerda para direita
17 / 46
Preenchimento de PolígonosTeste de Interior-Exterior
Regra do Winding-number não zero
Conta o número de vezes que a fronteira de um objeto gira emvolta de um ponto particular na direção anti-horária
Um ponto é dito interior se sua contagem for diferente de zero
Algoritmo
Inicializa a contagem com zero
De�ne um segmento de reta de uma posição P até um pontodistante
Não pode passar pelos vértices
Conta a quantidade de cruzamentos com as arestas (direcionais)+1 toda vez que cruzar uma aresta da direita para esquerda
−1 toda vez que cruzar uma aresta da esquerda para direita
18 / 46
Preenchimento de PolígonosTeste de Interior-Exterior
Regra do Winding-number não zero
Conta o número de vezes que a fronteira de um objeto gira emvolta de um ponto particular na direção anti-horária
Um ponto é dito interior se sua contagem for diferente de zero
Algoritmo
Inicializa a contagem com zeroDe�ne um segmento de reta de uma posição P até um pontodistante
Não pode passar pelos vértices
Conta a quantidade de cruzamentos com as arestas (direcionais)+1 toda vez que cruzar uma aresta da direita para esquerda
−1 toda vez que cruzar uma aresta da esquerda para direita
19 / 46
Preenchimento de PolígonosTeste de Interior-Exterior
Regra do Winding-number não zero
Conta o número de vezes que a fronteira de um objeto gira emvolta de um ponto particular na direção anti-horária
Um ponto é dito interior se sua contagem for diferente de zero
Algoritmo
Inicializa a contagem com zeroDe�ne um segmento de reta de uma posição P até um pontodistante
Não pode passar pelos vértices
Conta a quantidade de cruzamentos com as arestas (direcionais)+1 toda vez que cruzar uma aresta da direita para esquerda
−1 toda vez que cruzar uma aresta da esquerda para direita
20 / 46
Preenchimento de PolígonosTeste de Interior-Exterior
Regra do Winding-number não zero
Processo baseado em Produto Vetorial
Calcular o produto vetorial entre o vetor de�nido pela aresta e ovetor de�nido pelo segmento de reta
+1 se o componente-z do produto for positivo−1 caso contrário
Processo baseado em Produto Escalar
Encontrar um vetor perpendicular ao vetor do segmento de reta(vx, vy)→ (−vy, vx) e fazer o produto escalar com o vetor da aresta
+1 se o produto for positivo−1 caso contrário
22 / 46
Preenchimento de PolígonosPreenchimento de Áreas
Sumário
1 Introdução
2 Teste de Interior-Exterior
3 Preenchimento de ÁreasAlgoritmo ScanlinePreenchimento de Regiões Irregulares
23 / 46
Preenchimento de PolígonosPreenchimento de Áreas
Preenchimento de Áreas
Maioria das APIs limita o preenchimento de áreasPolígonos porque esses são descritos por equações lineares
Polígonos convexos porque assim somente duas arestas são cruzadas
Porém, é possível preencher o interior de qualquer tipo de forma(ferramentas de desenho)
24 / 46
Preenchimento de PolígonosPreenchimento de Áreas
Preenchimento de Áreas
Existem basicamente duas formas
Determinar os intervalos de preenchimento usando scalines epreencher o interior
Indicado para polígonos
A partir de um ponto, colorir a vizinhança até encontrar as bordasIndicado para formas mais complexas
25 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Sumário
1 Introdução
2 Teste de Interior-Exterior
3 Preenchimento de ÁreasAlgoritmo ScanlinePreenchimento de Regiões Irregulares
26 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Algoritmo Scanline
Primeiro determina as intersecções das scanlines com o polígono
Então, as seções da scanline que residirem dentro do polígono sãocoloridas
Usa a regra par-ímpar
Para polígonos, 2 equações lineares são usadas para encontrar asintersecções
Calcula as intersecções de um polígono da esquerda para a direita
27 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Problema da Scanline
Problemas quando a scanline passa por um vértice
Intersecta dois polígonos simultaneamente
29 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Problema da Scanline
A contagem de intersecção deve ser diferente dependendo datopologia
Duas arestas de lados opostos da scaline: conta uma intersecção
Duas arestas do mesmo lado da scaline: conta duas intersecções
30 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Solução para o Problema da Scanline
Para descobrir se as arestas estão opostasDe�nir a fronteira do polígono de forma anti-horária (ou horária) eobservar as mudanças em ySe os 3 vértices de duas arestas consecutivas são monotonicamentecrescentes (ou decrescentes) conta somente uma intersecção
Caso contrário conta duas
31 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Solução para o Problema da Scanline
Outra solução (pré-processamento)Percorrer as arestas no sentido anti-horário (ou horário) e veri�car se3 vértices consecutivos são monotonicamente crescentes
(decrescentes) em relação a yNesse caso a aresta inferior pode ser reduzida para assegurarsomente uma intersecção
32 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Algoritmo Scanline (Intersecção)
A interseção da i-ésima scanline com uma aresta {(x1, y1), (x2, y2)}é calculada com duas equações
y = ix = y/m− bm = (y2 − y1)/(x2 − x1)b = y1/m− x1
33 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Algoritmo Scanline (Intersecção)
É possível acelerar esse processo usando uma abordagem incremental
m = (yk+1 − yk)/(xk+1 − xk)
Como entre duas scalines consecutivas
yk+1 − yk = 1
Entãom = 1/(xk+1 − xk)xk+1 = xk + 1/m
34 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Algoritmo Scanline
É possível usar somente inteiros lembrando que
m =∆y
∆x
Então
xk+1 = xk +∆x
∆y
35 / 46
Preenchimento de PolígonosPreenchimento de ÁreasAlgoritmo Scanline
Algoritmo Scanline
Para polígonos convexos, só existe um bloco de pixelssubsequentes em cada scanline
Só processa a scanline até encontrar duas intersecções
Mesmo algoritmo anterior, porém muito mais simplesIntersecções nas arestas não apresentam dubiedade
36 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Sumário
1 Introdução
2 Teste de Interior-Exterior
3 Preenchimento de ÁreasAlgoritmo ScanlinePreenchimento de Regiões Irregulares
37 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Preenchimento de Regiões Irregulares
É possível preencher uma região irregular selecionando um pixel epintando os pixels vizinhos até alcançar as bordas
38 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Algoritmo de Preenchimento de Borda
Se a borda de uma região tem a mesma cor, é possível preencheressa região pixel por pixel até atingir a cor da borda
Normalmente usado em programas grá�cosComeça com um ponto inicial (x, y) e testa os vizinhos para ver acor, se não for borda, preenche
39 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Algoritmo de Preenchimento de Borda
(a) Diferentes testes de vizin-hança
(b) Problemas com a máscara de quatro viz-inhos
40 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Algoritmo de Preenchimento de Borda
1 void fill(int x, int y, int fillcolor, int bordercolor) {2 int intcolor;3 getPixel(x,y,intcolor);4 if((intcolor != bordercolor) && (intcolor != fillcolor)) {5 setpixel(x,y, fillcolor);6 fill(x+1,y,fillcolor,bordercolor);7 fill(x-1,y,fillcolor,bordercolor);8 fill(x,y+1,fillcolor,bordercolor);9 fill(x,y-1,fillcolor,bordercolor);
10 }11 }
41 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Algoritmo de Preenchimento de Borda
Problemas se algum pixel interior já for da cor escolhida para serpreenchida
Algum ramo da recursão pode ser descartado
Pode levar a um consumo excessivo de memória devido a recursãoSolução é empilhar, ao invés de pixels vizinhos, blocos de pixelssucessivos (o pixel inicial desses)
42 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Algoritmo de Preenchimento de Borda
43 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Algoritmo Flood-Fill
As vezes é necessário colorir uma área que não é de�nida apenaspor uma cor de borda
Ao invés de procurar uma cor de borda, procurar por uma cor de
interior
Se o interior tem mais de uma cor, pode-se inicialmente substituiressa cor para que todos pixels do interior tenham a mesma cor
44 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Algoritmo de Preenchimento de Borda
1 void fill(int x, int y, int fillcolor, int interiorcolor) {2 int color;3 getPixel(x,y,color);4 if(color == interiorcolor) {5 setpixel(x,y, fillcolor);6 fill(x+1,y,fillcolor, interiorcolor);7 fill(x-1,y,fillcolor, interiorcolor);8 fill(x,y+1,fillcolor, interiorcolor);9 fill(x,y-1,fillcolor, interiorcolor);
10 }11 }
45 / 46
Preenchimento de PolígonosPreenchimento de ÁreasPreenchimento de Regiões Irregulares
Observação
No caso de preenchimento de áreas irregulares, cada pixel está sendo�pintado� com uma cor
No caso de rendering de superfícies, cada pixel é pintado com a cordeterminada pela aplicação do algoritmo de iluminação +tonalização (shading)
46 / 46