COMPUTAÇÃO GRÁFICA

Cortes de LinhasCortes de Polígonos

Prof. Edison Oliveira de Jesus

Introdução

Corte ou Clipping é o processo que determina as partes visíveis da imagem dentro de uma janela;

Estes pontos visíveis são então mapeados para o viewport;

Corte de Pontos

Um ponto está dentro de uma janela retangular se sua ordenada estiver entre as ordenadas do lado esquerdo e direito do retângulo e sua abscissa estiver entre o lado superior e inferior do retângulo da janela.Assim: xw_esq x xw_dir

yw_inf y yw_sup

Xw_esq Xw_dir

Yw_sup

Yw_inf

(x, y)

Corte de Pontos

É possível fazer este teste para cada pixel da ima-gem;

Desvantagens desta opção: A imagem pode ser muito grande e complexa A imagem pode não ser definida pelos seus pixels,

mas sim pelos seus vetores e ai tem-se apenas as coordenadas de seus extremos

Em ambos os casos o custo computacional pode complicar muito as operações de corte de pontos num desenho;

Corte de Linhas

i

j

g

h

a

b

c

d’d

e

f

g’

h’

Nesta figura são mostradas as diversas formas que um segmento de reta pode ou não interceptar uma janela;

Dois casos são triviais: Os segmentos de retas com os dois extremos dentro

da janela são reconhecidos como visíveis;

Os segmentos totalmente fora da janela e portanto, são ditos invisíveis;

Algoritmo de Cohen Sutherland

b

a c

e

f

d1 2 3

4

567

8 janela

Regras do Algoritmo de Cohen Sutherland para o corte de linhas:

Dividir o sistema de coordenadas em nove regiões;

O extremo de um segmento de reta pode pertencer a apenas uma destas regiões;

Qualquer ponto que estiver sobre uma borda exten-dida, será considerado na região vizinha à borda;

Exemplo: um ponto sobre a borda que divide as regiões 1 e 8, será considerado pertencente à região 8;

Qualquer ponto sobre uma borda da janela, será considerado dentro da janela;

Desta forma, as seguintes direções poderão ser consideradas:

Região 0 ►dentro da janela Região 1 ► superior esquerda Região 2 ► superior Região 3 ► superior direita Região 4 ► direita Região 5 ► inferior direita Região 6 ► inferior Região 7 ► inferior esquerda Região 8 ► esquerda

Os dois casos triviais são:

Um segmento de reta é visível se ambos seus extre-mos pertencerem à janela;

Um segmento de reta é invisível se seus extremos pertencerem à regiões que têm pelo menos uma direção em comum;

Exemplo: segmento ab

As coordenadas do ponto a estão na região 1

As coordenadas do ponto b estão na região 7

A região 1 tem as seguintes direções: Superior esquerdo

A região 7 tem as seguintes direções: Inferior esquerdo

Portanto, em comum elas têm a direção esquerdo, o que torna este segmento de reta invisível àquela janela

Se nenhum dos dois casos é obtido, então o segmento é sub dividido nos pontos onde intercep-tam as bordas extendidas;

Cada uma das 4 direções é testada na seguinte ordem:

Esquerda Direita Inferior superior

As partes do segmento claramente fora da janela, são descartadas;

As partes restantes são verificadas com os casos triviais;

Exemplo: segmento de reta cd

b

a c

e

f

d1 2 3

4

567

8 janela

Ele não satisfaz os casos triviais;

Inicia no ponto c na região 6 ( inferior );

Intercepta a borda inferior da janela, no ponto e;

o segmento ce tem seus extremos numa direção comum: a inferior, logo ele é descartado, ficando agora o segmento ed;

O segmento ed também não satisfaz aos casos triviais;

Como o ponto e pertence à janela, então inicia-se o processo pelo outro extremo, no caso o ponto d;

Este ponto está na região 3 ( superior direita );

A ordem dos testes é realizada primeiro para a direita que é antes da superior;

Logo, o ponto f é encontrado na borda direita que intercepta o segmento de reta;

o segmento fd tem seus extremos numa direção comum, a direita, logo ele é descartado, ficando agora o segmento ef;

Este segmento satisfaz ao caso trivial 1, ou seja, ele é visível;

Considerações Matemáticas

As coordenadas do ponto de intersecção ( x, y ) de um segmento de reta com uma das borda da janela, podem ser obtidas através das seguintes considerações:

( x1, y1 )

( x, y )

( x2 , y2 )

Para um ponto qualquer ( x, y ) tem-se que a inclinação do segmento de reta é dado por:

m = ( y – y1 ) / ( x – x1 ) = ( y2 – y1 ) / ( x2 – x1 )

Se um segmento de reta cruza uma borda esquerda ou direita da janela, então x1 é diferente de x2 e, portanto a inclinação do segmento tem denominador diferente de zero;

Da mesma forma, se o segmento de reta cruza a borda superior ou inferior, então y1 é diferente de y2 e, portanto o inverso da inclinação do segmento tem denominador diferente de zero;

Como o valor da inclinação m pode ser obtido através das coordenadas dos pontos extremos do segmento dado, os valores do ponto de intersec-ção ( x, y ) podem ser obtidos como:y = m ( x – x1 ) + y1

x = ( y – y1 ) / m + x1

onde: m e ( x1, y1 ) são conhecidos; x na primeira equação, corresponde à abscissa da borda

esquerda ou direita que o segmento de reta está cru-zando;

y na segunda equação corresponde à ordenada da borda inferior ou superior que o segmento está cruzando.

Implementação

Criar uma rotina para dado as coordenadas de um ponto, ela retornar a região a qual este ponto per-tence;

A melhor forma de implementar esta rotina é criar uma lista associada ao ponto, de tal forma que esta lista contenha as direções da região que o ponto pertence;

Exemplo: região ( x, y, < direcoes > )

Lista contendo as direções

Criar 4 rotinas, uma para cada direção, para o cál-culo das coordenadas do ponto de intersecção do segmento de reta com a borda da janela;

Criar a rotina de corte, a qual utilizando as rotinas anteriores, fará o corte dos segmentos de retas dados;

Para cada segmento de reta:

Obter as direções dos pontos inicial e final;

Calcular a inclinação m quando x1 for diferente de x2;

Calcular o inverso da inclinação m quando y1 for diferente de y2;

Obter o corte do segmento, utilizando o algoritmo se-guinte.

Seja dir_inic e dir_fim, respectivamente as listas contendo as direções dos pontos inicial e final do segmento de reta.

Algoritmo

enquanto dir_inic ≠ λ ou dir_fim ≠ λ faça se dir_inic ∩ dir_fim ≠ λ

então segmento é invisível ( tem direções em comum ) senão

se dir_inic = λ então

direções ← dir_fim ( x, y ) ← ( x2 , y2 )

senão direções ← dir_inic ( x, y ) ← ( x1 , y1 )

fim_se

// Corte contra as bordas

Se “esquerda” ε direções então corte_esquerda ( x, y ) senão se “direita” ε direções então corte_direta ( x, y ) senão idem com “inferior” e “superior” fim_se

fim_se

Coordenadas do ponto de intersecção do segmento com

a borda

Se direções = dir_inic então ( x1 , y1 ) ← ( x, y ) região ( x1 , y1 , direção 1 ) senão

( x2 , y2 ) ← ( x, y ) região ( x2 , y2 , direção 2 ) fim-se

fim_enquanto linha ( x1 , y1 , x2 , y2 )

rotina corte_esquerda ( x1 , y1 , xw, m )

y ← m ( xw – x1 ) + y1

x ← xw retorna ( x, y )fim_rotina

Onde:x1 , y1 → ponto inicial do segmento de reta

xw → abscissa borda esquerda da janelam → inclinação do segmento de reta

O mesmo raciocínio se aplica às outras direções

rotina região ( x, y, direção ) direção ← λ se x < xw_esq então direção ← “esquerda” senão se x > xw_dir então direção ← “direita”

senão se y < yw_inf então direção ← “inferior”senão se y > yw_sup então direção ← “superior”

fim-se

Fim-rotina

POLIGONOSPOLIGONOS

Corte de polígonos

O algoritmo de corte de linhas somente deve ser utilizado para linhas desconectadas;

No caso de linhas conectadas a outras linhas, formando desta forma um polígono fechado, deve-se utilizar outro algoritmo;

Existem situações onde um polígono cortado por uma janela, resulta em outro polígono;

exemplojanela

figura

exemplo

Figura cortada

Algoritmo Sutherland-Hodgman

Este algoritmo é utilizado para o corte de polí-gonos;

Corta o polígono contra uma borda a cada vez;

Para cada borda da janela de corte tem-se uma lista de vértices do polígono e obtém-se outra lista de vértices para o polígono cortado, a qual é submetida para o corte da próxima borda da janela;

A lista de entrada é uma seqüência dos vértices consecutivos do polígono, obtidos do ultimo corte contra uma borda da janela;

A lista inicia-se com os vértices do polígono original;

A lista termina com os vértices do polígono cortado contra todas as bordas;

O algoritmo testa um par de vértices consecutivos contra uma borda.

Existem 4 casos possíveis:

v1

v2

v3

v4

Caso 1Caso 3

Caso 4

Caso 2

a

b

O polígono de teste originalmente tem quatro vértices: { v1 , v2 , v3 , v4 }

Caso 1: O 1o e o 2o vértice estão dentro da janela de corte; Neste caso, o vértice v2 é enviado à lista de saída;

Caso 2: O 1o vértice está dentro da janela de corte e o 2o

vértice está fora da janela; Neste caso, o ponto de interseção da borda da janela

com o polígono ( ponto a ) é enviado à lista de saída;

Caso 3: Ambos os vértices estão fora da janela; Neste caso, nenhum ponto é enviado à lista de saída;

Caso 4: O 1o vértice está fora da janela de corte e o 2o vértice

está dentro da janela; Neste caso, o ponto de interseção da borda da janela

com o polígono ( ponto b ) é enviado à lista de saída;

O algoritmo é invocado quatro vezes, uma para cada borda a janela;

Corte à direita

Corte inferior

Corte à esquerda

Corte superior

Polígono final

Implementação

Uma lista com os vértices iniciais;

Uma lista com os vértices finais ( vazia no inicio do processo );

Rotina para o cálculo da interseção da linha do polígo-no com uma borda da janela;

Rotina para definir se um ponto está dentro de uma dada borda da janela;

Rotina para atualizar lista com os vértices de saída;

Rotina Southerland HodgmanRotina SH ( lista_entrada, lista_saida, borda ) v1 ← retira_no ( lista_entrada )

enquanto lista_entrada ≠ λ faça v2 ← retira_no ( lista_entrada )

se dentro ( v2, borda )

então { caso 1 ou 4 } se dentro ( v1, borda )

então { caso 1 } coloca_no ( lista_saida, v2 )

senão { caso 4 } intercepta ( v1, v2, borda, p )

coloca_no ( lista_saida, p ) coloca_no ( lista_saida, v2 )

fim_se

senão { caso 2 ou 3 } se dentro ( v1, borda ) então { caso 2 } intercepta ( v1, v2, borda, p ) coloca_no ( lista_saida, p ) fim_se fim_se

v1 ← v2

fim_enquanto

fim rotina

Rotina dentro

Rotina dentro ( v, borda ) dentro ← falso caso borda.lado “superior” : se ( v.y ≤ borda.valor ) então dentro ← verdade “inferior” : se ( v.y ≥ borda.valor ) então dentro ← verdade “esquerda” : se ( v.x ≥ borda.valor ) então dentro ← verdade “direita” : se ( v.x ≤ borda.valor ) então dentro ← verdade fim_caso

retorna ( dentro )Fim rotina