Mário Rui Gomes
Computação Gráfica
1 Recorte de Segmentos
de Recta e Polígonos
1.1 Introdução
Relembrando os andares do pipeline de visualização, podemos verificar que no andar
anterior foi efectuada a Transformação de Visualização a qual consistiu na definição
de uma vista sobre a cena, recorrendo à especificação dos parâmetros de uma câmara
virtual e à definição de uma projecção, seguindo-se a transformação do volume de
visualização num volume canónico.
No andar de recorte de objectos 3D sobre o volume canónico pretende-se identificar
quais os objectos que se encontram totalmente dentro desse volume, os quais são
trivialmente aceites, e quais os que se encontram parcialmente dentro do volume
canónico, pelo que têm que ser recortados (clipping em Inglês) pelas faces da
fronteira do volume canónico.
Como foi descrito no capítulo anterior, o volume canónico é um paralelepípedo que
tem como limites os planos x = -1, x = 1, y = -1, y = 1, z = 0 e z = 1 como pode
observar-se na figura 1.1.
(-1, 1, 0)
y
(-1, 1, 1)
(1, 1, 1)
plano de recorte
posterior (z = 0)
(-1, 1, 0)
plano de recorte
anterior (z = 1)
z
(-1, -1, 1)
x
(1, -1, 0)
(-1, -1, 1)
Figura 1.1 – Volume canónico.
1
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
O objectivo do recorte será, assim, eliminar as partes dos objectos da cena que se
encontrem fora do volume canónico.
Nas representações mais simples, os objectos são descritos pelas suas arestas (modelo
em arames) ou pela sua fronteira definida por uma malha de polígonos, pelo que,
neste capítulo serão descritos os algoritmos que permitem o recorte de segmentos de
rectas e de polígonos.
Mas os algoritmos de recorte têm, em Computação Gráfica, múltiplas aplicações para
lá de permitirem escolher as partes dos objectos que se encontram no interior do
volume de canónico.
Considere-se, por exemplo, a situação em que existe uma cena composta por dois
polígonos, A e B os quais, ao serem vistos segundo um dado ponto de vista, o
polígono A encobre parcialmente o polígono B pelo que só deste estará visível.
Para obter a parte visível do polígono B basta rejeitar a parte deste polígono que é
recortada pelo polígono A. Esta operação designa-se por cálculo de elementos
invisíveis e será tratada noutro capítulo.
Objectivos
•
Introduzir o recorte de segmentos de recta no pipeline de visualização
•
Identificar os vários tipos de utilização dos algoritmos de recorte de segmentos
de recta e polígonos
•
Identificar as situações em que cada algoritmo deve ser aplicado
•
Descrever o funcionamento dos algoritmos mais importantes
1.2 Recorte de Linhas
O recorte de segmentos de recta consiste em identificar os valores das coordenadas X,
Y e Z que correspondem aos pontos de intersecção com cada uma das faces do
volume canónico, caso esses pontos existam.
Por facilidade expositiva considera-se unicamente uma das paredes rectangulares do
volume canónico a qual passamos a designar por rectângulo de recorte.
Uma vez que o recorte é aplicado também na remoção de elementos ocultos
considera-se que um rectângulo de recorte genérico com as coordenadas que podem
ser observadas na figura 1.2.
2
Mário Rui Gomes
Computação Gráfica
D
F
D´
F´
Ymax
H
B
C
J
H´
E
A
J´
G´
Rectângulo
de Recorte
I´
G
I
Xmin
Ymin
Xmax
Figura 1.2 – Recorte de segmentos de recta contra o rectângulo de recorte.
Nos polígonos convexos (todos os ângulos internos inferiores a 180º) em, por
exemplo, rectângulos, pode ser usada a propriedade geométrica que garante que se os
dois vértices de um segmentos de recta estiverem dentro do polígono, então todo o
segmento de recta está dentro do polígono.
Um vértice com coordenadas (X, Y) encontra-se dentro de um rectângulo quando se
verificarem, simultaneamente, as duas condições
X min ≤ X ≤ X max
Ymin ≤ Y ≤ Ymax
(1-1)
Tal como acontece com o segmento de recta AB da figura, se ambos os vértices
estiverem dentro do rectângulo de recorte, então todo o segmento de recta se encontra
também dentro dele, pelo que pode ser trivialmente aceite.
Se ambos os vértices estiverem fora do rectângulo de recorte, o segmento de recta
pode estar completamente fora (segmento EF da figura 1.2) e deve ser trivialmente
rejeitado, ou não (caso do segmento GH da mesma figura), situação em que tem que
ser efectuado o recorte.
Quando um só dos vértices está dentro do rectângulo o recorte é inevitável (segmento
CD da figura).
1.2.1
Algoritmo da Força Bruta
Designa-se por algoritmo da Força Bruta aquele que efectua o cálculo de recorte de
um segmento de recta através do cálculo da sua intersecção com cada uma das arestas
que limitam o rectângulo de recorte.
Considere-se a representação paramétrica de um segmento de recta cujas coordenadas
dos vértices são, respectivamente, (X0, Y0) e (X1, Y1):
3
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
X = X 0 + t seg ( X 1 − X 0 )
Y = Y0 + t seg (Y1 − Y0 )
(1-2)
0 ≤ t seg ≤ 1
Por seu lado, a representação paramétrica dos segmentos de recta constituintes do
rectângulo de recorte é
 X aresta = X min + t aresta ( X max − X min )

Ymin

Y
=

aresta

Ymax


 X min
 X aresta = 
(1-3)

 X max
Y
 aresta = Ymin + t aresta ( Ymax − Ymin )
consoante sejam os limites inferior ou superior ou os limites esquerdo ou direito. Para
determinar as intersecções de um segmento de recta a recortar com o rectângulo de
recorte basta resolver o sistema de equações simultâneas da segmento de recta a
recortar e de cada uma das arestas que delimitam o rectângulo em ordem a t seg e a
t aresta . Para o caso do limite vertical esquerdo do rectângulo de recorte temos:
X aresta = X min
Yaresta = Ymin + t aresta ( Ymax − Ymin )
(1-4)
Determinam-se então t seg e a t aresta , por esta ordem. Existirá intersecção quando se
verificarem simultaneamente:
0 ≤ t aresta ≤ 1
0 ≤ t seg ≤ 1
(1-5)
Para calcular as coordenadas do ponto de intersecção basta substituir na representação
paramétrica da aresta o parâmetro t aresta pelo valor que foi calculado.
1.2.2
Algoritmo de Cohen-Sutherland
Considerando que o cálculo de intersecções é um algoritmo pesado, surgiram vários
algoritmos mais eficientes que se baseiam em técnicas de “atrasar” o cálculo das
intersecções. Essa técnica é utilizada pelo algoritmo cuja descrição será agora
efectuada, o algoritmo de Cohen-Sutherland.
Considere-se um rectângulo de recorte e classifique-se cada vértice dos segmentos de
recta a recortar consoante a posição relativa às rectas colineares com cada uma das 4
arestas do rectângulo de recorte, conforma figura 1.3 apresenta.
4
Mário Rui Gomes
Computação Gráfica
1
2
3
4
5
6
7
8
9
Figura 1.3 – Algoritmo de Cohen-Sutherland: os limites do rectângulo de recorte
determinam 9 sub espaços.
O algoritmo inicia-se com o cálculo do sub espaço em que se encontra cada um dos
vértices do segmento de recta a recortar. Por exemplo, se ambos os vértices se
encontrarem nos sub espaços superiores, respectivamente 1, 2 ou 3, o segmento de
recta será rejeitado. Se ambos os vértices estiverem no sub espaço 5, o segmento será
aceite. Em ambos os casos não foi necessário efectuar qualquer cálculo de
intersecção.
Para simplificar a identificação dos sub espaços em que se encontram os vértices, os
autores recorreram a uma codificação dos 9 sub espaços usando uma codificação com
4 bits, em que cada um dos bits define a posição do sub espaço relativamente a uma
das arestas do polígono de recorte. Estes conjuntos de 4 bits denominam-se códigos
ou outcodes.
O 1º bit está relacionado com a aresta superior, tomando o valor 1 se o vértice se
encontra no sub espaço superior e 0 se no sub espaço inferior relativamente à recta
colinear com a aresta superior. O código 1 é sempre usado para codificar os sub
espaços que não contêm o rectângulo de recorte, conduzindo, desse modo a que a
codificação do sub espaço 5 será 0000.
A tabela 1.1 apresenta os valores assumidos pelos vários bits do código de acordo
com a posição do ponto em relação ao rectângulo de recorte. Daqui resulta a
codificação dos sub espaços apresentada pela figura 1.4.
Bit
1
2
3
4
Aresta
Superior
Inferior
Direito
Esquerdo
Valor
1
1
1
1
Posição
acima
abaixo
à direita
à esquerda
Tabela 1.1 – Valores dos bits do código de posição de um ponto em relação ao
rectângulo de recorte no algoritmo de Cohen-Sutherland.
5
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
1001
1000
1010
0001
0000
0010
0101
0100
0110
Figura 1.4 – Algoritmo de Cohen-Sutherland: códigos dos 9 sub espaços
determinados pelas rectas que suportam os segmentos de recta correspondentes
aos lados do rectângulo de recorte.
Usando esta codificação dos sub espaços é possível identificar vários tipos de
situações e tratá-las adequadamente, realizando cálculos de intersecções apenas
quando tal seja necessário.
Considere-se que OC0 é o código do sub espaço dentro do qual se encontra o primeiro
vértice do segmento de recta a recortar e que OC1 é o código do sub espaço dentro do
qual se encontra o 2º vértice do segmento.
Como já foi referido, teremos OC1 = OC0 = 0 se ambos os vértices se encontrarem
dentro do rectângulo de recorte e o segmento será aceite.
O segmento será rejeitado se os seus dois vértices se encontrarem num dos 4 semiespaços definidos por cada uma das rectas sobre as quais assentam cada uma das 4
arestas do rectângulo de recorte. Essa situação ocorre quando
OC1 & OC0 ≠ 0
(1-6)
Nos restantes casos, em que OC1 & OC0 = 0, terá que ser efectuada uma primeira
subdivisão do segmento de recta. A tabela 1.2 resume estas situações e as acções
correspondentes.
Situação
OC1 = OC0 = 0
OC1 & OC0 ≠ 0
OC1 & OC0 = 0
Acção
Aceitação
Rejeição
Subdivisão
Tabela 1.2 – Algoritmo de Cohen-Sutherland: Sequência de testes aos códigos
dos pontos extremos de um segmento de recta.
Nas situações em que é necessário subdividir o segmento de recta tem que se calcular
a intersecção com a recta sobre a qual assenta uma das arestas do rectângulo de
recorte.
6
Mário Rui Gomes
Computação Gráfica
Utilizando uma aproximação do tipo “força bruta” teria que calcular-se a intersecção
da segmento de recta com cada um dos 4 lados do rectângulo de recorte. No entanto,
como existe informação sobre em que sub espaço se encontra cada um dos vértices do
segmento de recta a recortar, podemos utilizar essa informação para escolher um dos
lados do rectângulo.
Considere-se o caso do segmento de recta GH representado na figura 1.5 em que o
segmento de recta GH não é nem trivialmente aceite pois pelo menos um dos códigos
é diferente de 0 (OCG = 0100 e OCH = 0010), nem trivialmente rejeitado
(OCG & OCH = 0).
H
G
Figura 1.5 – Algoritmo de Cohen-Sutherland: o segmento de recta a recortar
intersecta o rectângulo de recorte.
Analisando os códigos dos vértices obtém-se informação sobre qual o lado do
rectângulo de recorte que deverá ser seleccionado em primeiro lugar para recortar o
segmento de recta, eliminando as partes do segmento de recta que se encontram fora
do rectângulo de recorte.
O bit a 1 do código do 1º vértice, o vértice G, identifica a aresta inferior como aquela
que deve ser seleccionada. Efectuando o cálculo de intersecção obtêm-se um novo
vértice, G´ (veja-se a figura 1.6), que tem como código o valor 0000.
Uma vez que o código do 1º vértice do novo segmento de recta passou a ter todos os
bits a 0, selecciona-se agora o 2º vértice, H. O bit a 1 do 2º vértice conduz à selecção
da aresta direita do rectângulo de recorte. Daqui resulta o cálculo de um novo vértice,
H´, cujo código é 0000. O segmento de recta resultante, G´H´, que a figura 1.6
apresenta, é trivialmente aceite.
7
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
H
H´
J
I´
G´
G
I
Figura 1.6 – Algoritmo de CohenSutherland: segmento de recta depois
de recortado.
Figura 1.7 – Algoritmo de CohenSutherland: segmento de recta não
trivialmente rejeitado. A rejeição
ocorre depois do primeiro recorte que
gera o novo ponto I’.
Neste exemplo foi possível efectuar o número mínimo de cálculos de intersecções
para obter-se o segmento de recta recortado, mas nem sempre tal acontece como se
pode observar no exemplo que se segue.
Considere-se agora uma nova situação, ilustrada na figura 1.7 e na qual os códigos do
1º e 2º vértice são os mesmos que anteriormente, mas que não intersecta o rectângulo
de recorte.
Sendo os código dos dois vértices exactamente os mesmos do exemplo anterior, será
em primeiro lugar seleccionada a aresta inferior do rectângulo de recorte e calculado
um novo vértice. O código deste vértice é idêntico ao código do 2º vértice, de que
resulta a situação em que o segmento recortado é rejeitado.
Dos dois exemplos é possível concluir que o algoritmo de Cohen-Sutherland não
garante que o cálculo de intersecções seja efectuado só quando é necessário.
Em contrapartida, o algoritmo é eficiente nas situações em que a maioria dos
segmentos de recta são trivialmente aceites ou trivialmente rejeitadas, casos em que
basta serem calculados os códigos dos vértices.
Existem situações em que a maioria dos segmentos são trivialmente aceites ou
rejeitados, pelo que o Algoritmo de Cohen-Sutherland é eficiente. Sempre que o
rectângulo de recorte é muito pequeno comparado com a cena a maioria dos
segmentos de recta são trivialmente rejeitados. Sempre a que o rectângulo é muito
grande a maioria dos objectos são trivialmente aceites.
Uma das técnicas usadas para identificar os objectos que estão na proximidade do
cursor (selecção de objectos ou pick em Inglês) baseia-se na aplicação do algoritmo de
recorte sobre um rectângulo de reduzidas dimensões centrado nas coordenadas do
cursor, o rectângulo de selecção. Todos os objectos que sejam recortados por esse
rectângulo, são seleccionados. Esta é uma situação em que o Algoritmo de CohenSutherland é eficiente.
O algoritmo é facilmente estendido para 3D, bastando para tal identificar 27 sub
espaços e utilizar códigos compostos por 6 bits.
8
Mário Rui Gomes
1.2.3
Computação Gráfica
Algoritmo Paramétrico de Cyrus-Beck
Os investigadores Cyrus e Beck seguiram uma aproximação ao problema do recorte
de segmentos de recta bastante diferente da anterior. Para tal conceberam um
algoritmo que permite o recorte de um segmento de recta por qualquer polígono
convexo, em 2D, ou de um segmento de recta em 3D por qualquer poliedro convexo.
Consideremos novamente a representação paramétrica de um segmento de recta.
Como pode observar-se na figura 1.8, existem sempre 4 valores de t que resultam da
intersecção da recta contendo o segmento do recta a recortar com as 4 arestas do
rectângulo de recorte.
t4
t3
t2
t1
Figura 1.8 – Recorte paramétrico: pontos de intersecção da recta contendo o
segmento de recta a recortar com o rectângulo de recorte.
Através da classificação de cada um dos pontos de intersecção é possível saber quais
os valores de t dos vértices do segmento recortado, caso existam (no exemplo da
figura seriam os vértices correspondentes a t2 e t3).
Intersecção entre linhas
Considere-se novamente a representação paramétrica de um segmento de recta:
P (t ) = P0 + t ( P1 − P0 )
0 ≤ t ≤1
(1-7)
O polígono de recorte é definido pela enumeração dos seus lados (ou vértices)
segundo a convenção da circulação directa (sentido contrário ao dos ponteiros do
relógio). Para cada aresta define-se a normal, Ni, orientada para o exterior do
polígono.
Seja Pei um ponto arbitrário pertencente a uma aresta do polígono de recorte. Como
pode observar-se na figura 1.9, podemos definir três vectores que partem desse ponto,
9
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
um deles seguindo a fronteira e os outros dois para o espaço interior e para o espaço
exterior ao polígono convexo de recorte.
Lado Ei
Pei
P1
Ni . [P(t) - Pei] > 0
Ni . [P(t) - Pei] < 0
Ni . [P(t) - Pei] = 0
P0
Ni
Figura 1.9 – Algoritmo de Cyrus-Beck: produtos internos dos três vectores com a
normal exterior ao polígono de recorte.
O produto interno da normal à aresta do polígono com cada um destes três vectores é,
respectivamente, nulo, negativo e positivo. O sinal do produto interno permite
determinar se um ponto do segmento de recta coincide com a aresta ou é um ponto
interior ou exterior do polígono de recorte.
Para determinar o ponto de intersecção do segmento de recta com a aresta que
estamos a considerar é necessário obter o valor do parâmetro no ponto de intersecção.
Como vimos atrás, no ponto de intersecção o produto interno da normal à aresta com
o vector que une o ponto arbitrário Pei com o ponto de intersecção é nula, ou seja
N i • [P(t ) − Pei ] = 0
(1-8)
Substituindo P(t) pela equação paramétrica da recta que contem o segmento de recta e
explicitando o parâmetro t, obteremos sucessivamente:
N i • [P0 + (P1 − P0 ) t − Pei ] = 0
N i • (P0 − Pei ) + N i • [(P1 − P0 ) t ] = 0
t=
N i • (P0 − Pei )
− N i • (P1 − P0 )
e, definindo D=P1-P0,
t=
N i • (P0 − Pei )
− Ni • D
Para ser possível calcular t é necessário que:
•
N i ≠ 0 , o que é sempre verdadeiro;
10
(1-9)
Mário Rui Gomes
Computação Gráfica
•
P1 e P0 não sejam coincidentes, o que é verdadeiro para qualquer segmento de
recta de comprimento não nulo;
•
N i • D ≠ 0 , o que aconteceria se o segmento de recta a recortar fosse paralelo
à aresta do polígono;
Não existe intersecção se o valor de t for inferior a 0 ou superior a 1.
Tendo sido obtido um modo de calcular se um ponto está no exterior ou no interior do
polígono convexo de recorte e um modo de calcular o valor de t na intersecção
estamos em condições de descrever o algoritmo paramétrico.
Descrição do Algoritmo
O algoritmo de Cyrus-Beck aplica-se sucessivamente a cada uma das arestas do
polígono convexo. Para cada uma das arestas, escolhe-se, por exemplo, o primeiro
vértice como Pei, calcula-se a normal exterior, Ni e o valor de t no ponto de
intersecção.
É ainda necessário identificar se o primeiro vértice do segmento de recta está no
exterior e o 2º no interior, situação em que a intersecção é definida como
Potencialmente de Entrada, PE, ou vice-versa em que a intersecção é definida como
Potencialmente de Saída, PS.
Para efectuar essa identificação poderia classificar-se cada vértice do segmento de
recta, tal como acontecia no algoritmo da Cohen-Sutherland. No entanto, é possível
efectuar a classificação com base no ângulo existente entre o vector P0P1 e o vector
Ni. Se o ângulo for inferior a 90º trata-se de uma intersecção do tipo PS, se não, será
do tipo PE. Esta informação está contida no sinal do produto interno entre aqueles
dois vectores e que é necessário para o cálculo do próprio valor de t.
N i • D < 0 ⇒ PE
N i • D > 0 ⇒ PS
(1-10)
Estando calculados todos os valores t dos pontos de intersecção, e devidamente
classificados como sendo do tipo PE ou PS, estamos em condições de identificar
exactamente os valores de t dos vértices do segmento de recta já recortado.
Identifica-se a intersecção do tipo PE que corresponde ao maior t e a intersecção do
tipo PS que corresponde ao menor t e comparam-se os dois valores de t.
Se o valor de t da intersecção do tipo PE for superior ao valor de t da intersecção do
tipo PS, então todo o segmento de recta pode ser rejeitado.
Se o valor de t da intersecção do tipo PE for inferior ao valor de t da intersecção do
tipo PS, então usam-se os dois valores para obter as coordenadas dos vértices do
segmento de recta recortado.
A figura 1.10 apresenta um polígono convexo de recorte com 5 lados e um segmento
de recta a recortar (P0P1).
11
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
P1
PS
PS
PE
PE
P0
Figura 1.10 – Algoritmo de Cyrius-Beck: segmento de recta a recortar com
identificação do tipo (PE ou PS) das suas intersecções com o polígono de recorte.
Do cálculo das intersecções resultam 4 valores de t, sendo dois do tipo PE e dois do
tipo PS. Como o segmento de recta é paralelo ao lado inferior direito do polígono, o 5º
valor de t não foi calculado uma vez que N i • D = 0 .
Escolhendo-se a intersecção do tipo PE com maior valor de t e a intersecção do tipo
PS com o menor valor de t obtêm-se os valores paramétricos de cada um dos vértices
do segmento recortado.
Considere-se agora o exemplo apresentado pela figura 1.11. Aplicando o algoritmo,
são calculados 5 valores de t dos quais só são classificados os três valores
representados na figura uma vez que os restantes têm valores de t inferiores a 0 ou
superiores a 1.
P1
PE
PS
PE
P0
Figura 1.11 – Algoritmo de Cyrus-Beck: segmento de recta rejeitado (o maior t
das intersecções de tipo PE é superior ao menor t de tipo PS).
12
Mário Rui Gomes
Computação Gráfica
Como pode observar-se, a intersecção do tipo PS tem um valor de t inferior ao maior
valor de t de uma intersecção do tipo PE pelo que se conclui que o segmento de recta
deve ser rejeitado.
Pseudocódigo
Pré-calcular Ni e seleccionar Pei para cada aresta
Para cada segmento de recta
Se P1 = P0 então
segmento de recta degenerado: recortar como ponto
Senão
te = 0; tl= 1;
para cada aresta de recorte
Se Ni . D ≠ 0 então /* ignorar arestas paralelas ao segmento */
calcular t; /* de intersecção do segmento com aresta */
usar sinal de Ni . D para caracterizar PE ou PS;
Se PE então tE = max(tE, t);
Se PS então tS = min(tS, t);
FimSe
Se tE > tS então devolve nulo;
Senão devolve [P(tE), P(tS)]
Rectângulo de Recorte (Liang e Barsky)
Quando os polígonos de recorte são rectângulos com as respectivas arestas horizontais
e verticais podem ser efectuadas várias simplificações.
Em primeiro lugar, os valores de Ni só têm uma coordenada com valor diferente de 0
e a outra coordenada toma o valor 1 ou –1 (veja-se a figura 1.12).
Ni=(0,1)
Ni=(-1,0)
Ni=(1,0)
Ni=(0,-1)
Figura 1.12 – Algoritmo de Liang e Barsky: normais às arestas do rectângulo de
recorte
13
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
Como nos cálculos de t é utilizado o produto da normal com o vector P0 Pei, basta
utilizar uma das coordenadas de Pei, sendo irrelevante o valor da outra coordenada.
Neste caso os cálculos são bastante simplificados, como pode observar-se na tabela
1.3.
O algoritmo paramétrico é eficiente quando é necessário recortar a maioria dos
segmentos de recta, uma vez o cálculo das coordenadas dos pontos de intersecção é
adiado até se ter a certeza de que existe intersecção.
Aresta
Normal Ni
Pei
P0-Pei
Esquerda: x=xmin
(-1,0)
(xmin,y)
(xo-xmin, yo-y)
Direita: x=xmax
(1,0)
(xmax,y)
(xo-xmax, yo-y)
Superior: y=ymin
(0,-1)
(x, ymin)
(xo-x, yo-ymin)
Inferior: y=ymax
(0,1)
(x, ymax)
(xo-x, yo-ymax)
t=
N i • ( Po − Pei )
− Ni D
− ( x0 − x min )
( x1 − x0 )
( x0 − x max )
− ( x1 − x0 )
− ( y 0 − y min )
( y1 − y 0 )
( y 0 − y max )
− ( y − y0 )
Tabela 1.3 – Algoritmo de Liang e Barsky: expressões do parâmetro do ponto de
intersecção de um segmento de recta com os limites do rectângulo de recorte.
1.3 Recorte de Polígonos
O recorte de polígonos implica a identificação do lugar geométrico dos pontos que
simultaneamente pertencem ao polígono a recortar e ao polígono de recorte.
A existência de uma topologia no caso de polígonos torna esta operação mais
complexa que no caso de segmentos de recta. Assim, não basta usar as coordenadas
de cada um dos vértices do polígono. Estes têm que estar ordenados segundo o sentido
directo (contrário ao dos ponteiros do relógio).
Figura 1.13 – Recorte de um Triângulo
14
Mário Rui Gomes
Computação Gráfica
Figura 1.14 – Recorte de um Polígono Côncavo
Figura 1.15 – Recorte de um Polígono Côncavo (2 polígonos recortados)
O problema também fica mais complexo quando é aplicado a um polígono côncavo,
como o da figura 1.14.
Quando é aplicado o recorte a um polígono côncavo podemos obter mais do que um
polígono recortado, como pode observar-se na figura 1.15.
1.3.1
Algoritmo de Sutherland - Hodgman
O algoritmo de Sutherland-Hodgman permite o recorte de qualquer tipo de polígono
por um polígono convexo de recorte. Baseia-se na aproximação de “dividir para
conquistar” segundo a qual se obtém um polígono recortado por recorte
sucessivamente efectuado por cada uma das rectas de suporte de cada uma das arestas
do polígono de recorte.
Como pode observar-se nas figuras 1.16 e 1.17, o algoritmo consiste em recortar o
polígono por cada uma das linhas que suportam as arestas do polígono de recorte (4
arestas, se for um rectângulo).
15
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
Figura 1.16 – Algoritmo de Sutherland-Hodgman: primeiro recorte pela recta
que suporta a aresta direita do polígono de recorte.
Figura 1.17 – Algoritmo de Sutherland-Hodgman: recorte pelas rectas que
suportam as arestas inferior, esquerda e superior do polígono de recorte.
A formulação do algoritmo passa do problema do recorte de um polígono por outro
polígono para o recorte de um polígono por uma recta, garantindo que se mantém a
topologia.
Assim sendo, dada a descrição de um polígono através de uma lista de vértices (V1,
V2, …, Vn), o algoritmo consiste em, ao recortar o polígono contra cada uma das
rectas sobre a qual assenta uma aresta do polígono de recorte, obter uma nova lista de
vértices, ou mais do que uma lista se houver lugar ao aparecimento de polígonos
degenerados que são separados. Cada uma destas listas descreve um dos polígonos
recortados contra cada um desses limites.
Em primeiro lugar é necessário identificar se o 1º vértice se encontra dentro ou fora
do polígono de recorte. Este vértice é colocado na lista de vértices do polígono já
recortado se o vértice se encontrar dentro do polígono de recorte. Caso contrário, a
lista permanecerá vazia.
16
Mário Rui Gomes
Computação Gráfica
Seguidamente podem ocorrer 4 situações quando é efectuado o tratamento de cada par
de vértices formando uma aresta do polígono de recorte (vejam-se as figuras 1.18 e
1.19)
•
Transição Interior-Interior: Quando ambos os vértices estão contidos no
semi-plano interior, o 2º vértice da aresta é adicionado à lista de vértices do
polígono recortado.
•
Transição Interior-Exterior: Quando ocorre uma transição do semi-espaço
interior para o exterior é necessário calcular o vértice de intersecção, I, o qual
é adicionado à lista de vértices do polígono recortado.
•
Transição Exterior-Exterior: Quando ambos os vértices estão contidos no
semi-plano exterior nada é adicionado à lista de vértices do polígono
recortado.
•
Transição Exterior-Interior: Quando ocorre uma transição do semi-espaço
exterior para o interior é necessário calcular o vértice de intersecção, I, o qual
é adicionado à lista de vértices do polígono recortado, assim como o 2º vértice
da aresta.
Interior
Interior
Exterior
Exterior
S
P
I
S
P
Figura 1.18 – Transição Interior – Interior e Interior – Exterior
Exterior
Interior
Exterior
Exterior
I
P
S
P
S
Figura 1.19 – Transição Exterior – Exterior e Exterior - Interior
17
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
A
H´
F
H
F´
F´´
D´
E
G´
G
D
B´
B
C
Figura 1.20 – Recorte de polígono côncavo pelo algoritmo de SutherlandHodgman.
Como exemplo, vamos agora aplicar o algoritmo de Sutherland-Hodgman ao polígono
côncavo com 8 vértices ordenados segundo o sentido directo (contrário ao dos
ponteiros do relógio) representado na figura 1.20.
Escolhendo em primeiro lugar a recta sobre a qual assenta a aresta esquerda:
•
A é um ponto exterior, pelo que a lista de vértices resultantes se mantém vazia;
•
AB: Transição EE -> nenhum dos vértices é adicionado à lista que continua
vazia;
•
BC: Transição EI -> calcula-se a intersecção B´ que é adicionada à lista assim
como o 2º vértice (B´C);
•
CD: Transição II -> o vértice D é adicionado à lista (B´CD);
•
DE: Transição IE -> calcula-se a intersecção D´ que é adicionada à lista
(B´CDD´);
•
EF: Transição EE -> nenhum dos vértices é adicionado à lista (B´CDD´);
•
FG: Transição EI -> calcula-se a intersecção F´ a qual é adicionada à lista
assim como o 2º vértice (B´CDD´F´G);
•
GH: Transição II -> o vértice H é adicionado à lista (B´CDD´F´GH);
•
HA: Transição IE -> calcula-se a intersecção H´ a qual é adicionada à
(B´CDD´F´GHH´);
Antes de passar ao recorte pela aresta superior, convém verificar o que foi obtido
como polígono recortado. Analisando o conteúdo da lista de vértices
(B´CDD´F´GHH´) verifica-se que obtivemos um rectângulo (B´CDD´), ligado por
uma aresta (D´F´) a um 2º polígono (F´GHH´) o qual está, também ligado por uma
aresta (H´B´) ao 1º polígono. Obteve-se um polígono degenerado, pelo que será
18
Mário Rui Gomes
Computação Gráfica
necessário efectuar um pós-processamento que transforme o polígono degenerado em
dois polígonos (B´CDD´ e F´GHH´).
Seguidamente efectuam-se os mesmos cálculos para cada um dos polígonos. O 1º
polígono não será mais recortado pela recta que suporta a aresta superior uma vez que
todos os vértices estão contidos no semi-plano interior. O 2º polígono, (F´GHH´), será
processado do seguinte modo:
•
F´ é um vértice pertencente ao semi-espaço exterior pelo que a lista de vértices
se mantém vazia ();
•
F´G: Transição EI -> calcula-se a intersecção F´´ que é adicionada à lista
assim como o 2º vértice (F´´G);
•
GH: Transição IE -> calcula-se a intersecção G´ que é adicionado à lista
(F´´GG´);
•
HH´: Transição EE -> nenhum dos vértices é adicionado à lista (F´´GG´);
•
H´F´: Transição EE -> nenhum dos vértices é adicionado à lista (F´´GG´);
Obtém-se assim o triângulo (F´´GG´);
Exercícios
1-1
Descreva, sucintamente, o algoritmo de recorte Força Bruta e descreva,
justificando, uma das suas fraquezas.
1-2
Explique como procederia para adaptar o algoritmo de Cohen-Sutherland para
três dimensões. Escreva o pseudocódigo resultante.
1-3
Proponha uma extensão para 3D do algoritmo de Cohen-Sutherland, incluindo o
cálculo dos códigos e das intersecções.
1-4
O algoritmo de Cohen-Sutherland é particularmente eficaz no recorte de
segmentos de recta contra janelas rectangulares. Considere a figura seguinte e
explique como seriam processados cada um dos 5 segmentos, pelo algoritmo
mencionado. Além de calcular os códigos, deve definir o critério seguido na
subdivisão dos segmentos.
1
Ymax
2
5
3
Ymin
4
Xmin
1-5
Xmax
Qual o critério usado no Algoritmo de Cohen-Sutherland para a definição dos
códigos do 9 sub espaços?
19
Computação Gráfica
Recorte de Segmentos de Recta e Polígonos
1-6
No Algoritmo de Cohen-Sutherland como é que os códigos dos vértice de um
segmentos de recta pode ser usado na escolha da aresta do polígono de recorte
com a qual se deve proceder ao calculo de uma intersecção?
1-7
Considere o caso da figura anexa com a qual vai ser utilizado o algoritmo de
Cohen-Sutherland no recorte da segmento de recta poligonal ABCD pelo
polígono de recorte. Calcule os códigos dos vértices. Qual o significado de um 1
no código do ponto C? Como aplicaria esse algoritmo no recorte do polígono
ABCD?
C
B
A
D
1-8
Considere o algoritmo de Cohen – Suntherland.
a) Qual o número máximo de recortes de um segmento de recta aplicando esse
algoritmo?
b) Quais os códigos dos vértices de um segmento de recta de modo a que o
número máximo de intersecções seja 0?
1-9
Descreva sucintamente o modo como funciona o Algoritmo de Cyrus-Beck e
indique um ponto fraco e outro forte desse algoritmo.
1-10 Aplique o algoritmo de Cyrus-Beck à figura. Inclua a classificação de todos os
pontos de intersecção que o algoritmo calcula.
1-11 Descreva os principais problemas que podem ocorrer ao aplicar o recorte a um
polígono côncavo? Justifique, utilizando uma figura.
1-12 Descreva o algoritmo de Sutherland – Hodgman. O que poderá acontecer se o
algoritmo for aplicado a um polígono côncavo? Ilustre com um exemplo.
1-13 Por que é que o algoritmo de Sutherland-Hodgman só funciona com polígonos
de recorte convexos? Dê um exemplo.
20