Introdução ao Processamento e Síntese de imagens – · b c d e f g h i i i j j j k l 1 . ... das quais alguns serão vistos. ... Pegar máximo dos mínimos e mínimo dos máximos

Introdução ao Processamento e Síntese de imagens. Prof. Júlio Kiyoshi Hasegawa

1

Introdução ao Processamento e Síntese de imagens – Recorte 2D

Fontes:

Rogers, D. F. – Procedural Elements for Computer Graphics Traina, A. J. M. & Oliveira , M. C. F. (2004) 2016


2

Recorte - (Clipping)

Numa cena tridimensional, normalmente não é possível ver todas as superfícies de todos os objetos. Assim, essa técnica se preocupa em eliminar objetos ou partes deles não visíveis. Existem várias abordagens de recorte: • Recorte da primitiva antes da conversão matricial - cálculo

analítico das suas intersecções com o retângulo de recorte/visualização. Esses pontos de intersecção são os novos vértices da primitiva recortada. (Espaço Objeto)

• Conversão do polígono para o modo raster, mas traçar apenas os pixels visíveis no retângulo de visualização. Verificar cada pixel contra o retângulo de visualização. (Espaço Imagem)


3

Espaço do Objeto x Espaço da Imagem

• Métodos que trabalham no espaço do objeto • Entrada e saída são dados geométricos

• Independente da resolução da imagem

• Menos vulnerabilidade a aliasing

• Rasterização ocorre depois

• Exemplos: • Maioria dos algoritmos de recorte e culling

• Recorte de segmentos de retas

• Recorte de polígonos


4

Espaço do Objeto x Espaço da Imagem

Métodos que trabalham no espaço da imagem • Entrada é vetorial e saída é matricial

• Dependente da resolução da imagem

• Visibilidade determinada apenas em pontos (pixels)

• Podem aproveitar aceleração por hardware

• Exemplos: • Z-buffer

• Algoritmo de Warnock

• Mapas de sombra


5

Recorte bidimensional

- definir quais pontos, linhas ou partes das linhas estão dentro da janela de recorte.

Teste para ponto

xL ≤ x ≤ xR e yB ≤ y ≤ yT os pontos nas bordas da janela pertencem a janela de visualização.

XL XR

YB

YT


6

Teste para Linhas

Linha ab: extremos dentro da janela – linha toda dentro

Linha gh: extremos fora da janela – parte da linha na janela

Linhas ij: os extremos estão totalmente a esquerda, a direita, acima ou abaixo da janela – linhas invisiveis

Reta – análise dos extremos Posição na janela de recorte

Estado da reta

Extremo 1 Extremo 2

Dentro Dentro Reta interna Visível

Dentro Fora Tem intersecção Parcialmente Visível

Fora

Fora

2 extremos à direita 2 extremos à esquerda 2 extremos acima 2 extremos abaixo

Invisível

Qualquer posição indefinida

Os testes acima não eliminam as linhas: gh – que são parcialmente visíveis e kl – são totalmente invisiveis.


7

Dan Cohen e Ivan Sutherland – desenvolveram um teste, usando uma codificação com 4 dígitos (bit), indicando qual das nove regiões contém o extremo da linha.

Quadro de visibilidade Não Não Não

Não Sim Não

Não Não Não Convenção: - o bit + a direita é o 1o bit - os bits recebem o valor zero ou um:

- 1o bit = 1, se o extremo da linha está à esquerda da janela, senão zero;

- 2o bit = 1, se o extremo da linha está à direita da janela, senão zero;

- 3o bit = 1, se o extremo da linha está abaixo da janela, senão zero;

- 4o bit = 1, se o extremo da linha está acima da janela, senão zero; -

T 1001 1000 1010

0001 0000 0010

B 0101 0100 0110

L R

1o 4o 3o 2o


8

Desta forma o código da linha pode ser utilizado para eliminar linhas totalmente invisíveis, segundo o seguinte critério: TRUE = T, FALSE = F T e F = F 1 e 0 = 0 F e T = F F = 0 0 e 1 = 0 F e F = F T = 1 0 e 0 = 0 T e T = T 1 e 1 = 1 Assim, quando a interseção bit a bit (lógico) dos extremos não é zero – linha é totalmente invisível, podendo se recortada. Quando a interseção lógica é zero – a linha pode ser totalmente visível, parcialmente visível ou totalmente invisível.


9

Assim, para eliminar a dúvida devem-se analisar os códigos dos extremos das linhas isoladamente.

Fazer

4

3

2 j

i

a

b

c

d

e

f

g

h

i

i

i

j

j j

k

l

1


10

Preencher com códigos dos extremos.

Linh

a

Código Interseção

Lógica Comentários

Inicio Fim

ab

ij

ij

ij

ij

cd

ef

gh

kl


11

Linha Código Interseção

Lógica Comentários

inicio Fim

ab 0000 0000 0000 Totalmente visível

ij 0010 0110 0010 Totalmente invisível




cd 0000 0010 0000 Parcialmente invisível

ef 0001 0000 0000 Parcialmente invisível

gh 0001 1000 0000 Parcialmente invisível

kl 1000 0010 0000 Totalmente invisível


12

Para obter eficiência no processo de recorte deve-se realizar o procedimento por etapas: - 1o: utilizando o algoritmo de código – que eliminam as linhas totalmente visíveis, e

as realmente invisíveis. - 2o: combinando com um segundo procedimento, das quais alguns serão vistos.


13

Processo de interseção de linhas.

Assim, as linhas que não podem ser identificadas passam por um novo processo.

- uma reta pode ser definida por dois pontos P1(x1, y1) e P2(x2, y2)

- cuja equação pode ser definida por:

- y = m (x – x1) + y1 ou y = m (x – x2) + y2

onde:

- m = (y2 – y1)/(x2 – x1)


14

Para encontrar a intersecção da reta com a janela de recorte.

a interseção com a aresta da janela é dada por:

- esquerda → xl, y = m (xl – x1) + y1

- direita → xr, y = m (xr – x1) + y1

- Topo → yt, x = (1/m) (yt – y1) + x1

- Baixo → yb, x = (1/m) (yb – y1) + x1

Y= m(X – X1) + Y1

Yb

Yt

Xr Xl


15

Algoritmo sem otimizações – força bruta:

• Verificar se os extremos estão dentro da janela de recorte – sim: pintar a linha (Retas totalmente visível)

• verificar se os dois extremos da reta estão totalmente fora da janela de recorte – os 2 à esquerda, ou os 2 à direita, ou os 2 acima ou os 2 baixo da arestas da janela – não pintar a linha (Retas totalmente invisível)

• caso não atenda nenhum dos dois caso anteriores:

o para cada aresta da janela calcular a interseção com cada reta, verificando se é válida (a interseção deve pertencer aos dois segmentos - aresta e reta) ; e


16

� classificar as retas, conforme o número de interseções: 0, 1 ou 2.

o 2 (P3P4) – dois pontos externos, gerar 3 retas;

� pintar o segmento entre as interseções

� não pintar dos extremos a interseção.

I3

I2

I1

P4

P3

P1

P2

Yb

Yt

Xr Xl

P5

P6

0 (P5P6) – reta não é visível – não pintar

1 (P1P2) – um ponto interno e outro externo:

• do ponto fora até a interseção – não pintar;

• da interseção até o ponto interno (0000)– pintar.


17

Recorte de linha para contornos convexos

generalizados

Pode ser aplicada em janelas de recorte giradas em relação ao sistema de coordenadas.

Reta P1P2 → pode ser escrita de forma paramétrica, que é independente do sistema de coordenadas.

• P(t) = P1 + (P2 - P1) t 0 ≤ t ≤ 1 (define um seg. de reta)

• x(t) = x1 + (x2 - x1) t 0 ≤ t ≤ 1

• y(t) = y1 + (y2 - y1) t 0 ≤ t ≤ 1

Recorte utilizando uma janela retangular – 1 das coordenadas de interseção é conhecida, só resta calcular a outra.

t = (P(t) – P1)/(P2 – P1)


18

Para a janela:

Aresta esq. → tL = (xL – x1)/(x2 – x1) 0 ≤ t ≤ 1

Aresta dir. → tR = (xR – x1)/(x2 – x1) 0 ≤ t ≤ 1

Aresta sup. → tT = (yT – y1)/(y2 – y1) 0 ≤ t ≤ 1

Aresta inf. → tB = (yB – y1)/(y2 – y1) 0 ≤ t ≤ 1

YB

YT

XR XL

x(t) = x1 + (x2 - x1) t

y(t) = y1 + (y2 - y1) t


19

Reta com valor de t fora do campo (0→1) é descartada, ele representa ponto fora da janela de visualização.

Exercício:

Calcular os valores

de tL, tR, tT e tB para

as 2 retas.


20

Exemplo: linha P1(-3/2, -3/4) a P2(3/2, ½), janela de recorte (xL = -1, xR = 1, xB = -1, xT = 1)

Valores de t = (tL = 1/6, tR = 5/6, tB = -1/5, tT = 7/5)

Os valores –1/5 e 7/5 estão fora do intervalo, são rejeitados.

Assim: 1/6 ≤ t ≤ 5/6

- substituindo estes extremos na equação da reta têm-se:

t = 1/6 → x = -1 e y = -13/24

t = 5/6 → x = 1 e y = 7/24

Linha Parcialmente Visível P3(-5/2, -1) e P4(3/2, 2):

tL = 3/8, tR = 7/8, tB = 0, tT = 2/3)

ordenar – crescente: 0, 3/8, 2/3, 7/8

Pegar máximo dos mínimos e mínimo dos máximos.


21

Problemas: quando as linhas são totalmente visíveis e totalmente invisíveis, pois, nos dois casos, todos os valores de t estão fora do intervalo.

P1(-½ , ½), P2(½ , -½)

P3(3/2 , -½), P4(2 , ½) - p/ P1P2 : t → (tL = -1/2, tR = 3/2, tB = 3/2, tT = -1/2)

- p/ P3P4 : t → (tL = -5, tR = -1, tB = -1/2, tT = 3/2)

P2

P3

P4

P1

1 -1

-1

1


22

Algoritmo sem otimizações – 4 bits Subdivisão de Sutherland-Cohen para recorte de linha

• aplica-se o teste dos 4 bits (como programar isso?)

Janela de recorte – código dos bits

XL XR

YB

YT

V[i] = 0 p/ i=0;3

if(xi ≤ XL)v[3] = 1 if(xi < XL)v[3] = 1

if(xi ≥ XR)v[2] = 1 if(xi > XR)v[2] = 1

if(yi ≤ YB)v[1] = 1 ou if(yi < YB)v[1] = 1

if(yi ≥ YT)v[0] = 1 if(yi > YT)v[0] = 1


23

Divisão da reta em duas partes iguais (÷2)

Divisão em bits:

no 6 – 0110, deslocado um bit para a direita = 0011 - no 3

Tabela 1 – Representação dos números nas bases binária e decimal.

Base binária

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010

Base decimal

0 1 2 3 4 5 6 7 8 9 10

Conversão – base binária para decimal

- b0*2n + b1*2n-1 + b2*2n-2 +.......+ bn-1*21 + bn*20

Onde: n é o número de dígitos menos 1; b0 é o dígito mais significativo; e bn é o bit menos significativo.

Ex: 1 0 1 1 0 1 �[n = 6-1 = 5]; val = 1*25 + 0*24 +1*23 +1*22 +0*21 + 1*20 = 45

Calcular o valor o número binário:1 1 0 1 1 1 59


24

Conversão – base decimal para binária

1º início – {a) nu = INT(nd/2); b) bit = nd – nu*2;} nd � base decimal

2º e demais operações – fazer {a) e b)- com nd = nu } até o valor (nd=1)

3º o valor binário será definido pela concatenação dos bits: nd+bit (de cada divisão da última até a 1ª.

Ex: 45 : nd = 45;

nd 45÷2= 22÷2= 11÷2= 5÷2= 2÷2= 1

bit 1 0 1 1 0 Resto de cada operação

Número binário = 1 0 1 1 0 1 (contrário)

Calcular o valor do número decimal: 67 1000011


25

Subdivisão do ponto médio

Algoritmo muito eficiente para implementação em hardware, pois as operações de divisão e adição por 2 em hardware são muito rápidas.

O algoritmo utiliza o código de linhas associada à técnica de dividir a linha em duas partes iguais.

Procedimento:

• um teste inicial é aplicado para detectar linhas visíveis, invisíveis ou parcialmente visíveis ou invisíveis;

• linhas para as quais o teste inicial falha, são divididas em duas partes iguais:

- xm = (x1+x2)/2 ym = (y1+y2)/2


26

Reta f – subdivisões produzem duas retas, um que é realmente invisível (que é excluído), e a outra com a mesma característica da original, o procedimento continua até que todos os segmentos sejam realmente invisíveis ou até atingir a precisão especificada.

Reta c – 1a subdivisão produz dois segmentos com características semelhantes, parcialmente visíveis.

O procedimento deve-se concentrar em um dos extremos, por vez, realizando novas subdivisões até que uns dos extremos dos segmentos de retas coincidam com uma das arestas da janela, dentro do critério de precisão. Este ponto é declarado o ponto visível mais distante do outro extremo.


27

Identificação de polígonos convexos Produto Vetorial:

A identificação pode ser realizada pelo produto vetorial das arestas adjacentes.

Analisando o sinal a partir do produto:

- todos zero → polígono colinear (linhas paralelas).

- positivo e negativo → polígono côncavo.

- positivos ou zeros → polígono convexo, ponto à direita da linha.

- negativos ou zeros → polígono convexo, ponto à esquerda da linha.

(10,10) (10,10) (10,10)

(10,5) (9,5) (11,5)

(10,0) (10,0) (10,0)


28

O produto vetorial de dois vetores planares, definido por três pontos (vértice central - V2) resulta em:

n

1 - (x1, y1)

2 - (x2, y2) 3 - (x3, y3)

n = [(x1 - x2) (y2 - y3) - (x2 - x3) (y1 - y2)] k


29

Translação e rotação

Algoritmo: - Para cada vértice do polígono, transladar o polígono de tal forma que

i-ésimo vértice esteja na origem. - Rotacione o polígono de tal forma que o (i + 1)-ésimo vértice fique

sobre o eixo x (positivo). - Examine o sinal do (i+2)–ésimo vértice. - Se todas as coord. Y do (i+2)–ésimo vértice tem o mesmo sinal – o

polígono é convexo; senão é côncavo. - Se todas as coord. Y do (i+2)–ésimo vértice são nulos – é um

polígono degenerado – (linha). - Em cada aresta do polígono, a normal interna tem componente y com

o mesmo sinal do (i+2)–ésimo vértice, e os outros iguais a zero. - Determinando a direção da normal original, somente a rotação inversa

deve ser aplicada.


30


31

Documents

Introdução ao Processamento e Síntese de imagens – · b c d e f g h i i i j j j k l 1 . ... das quais alguns serão vistos. ... Pegar máximo dos mínimos e mínimo dos máximos