Clipping (Recorte)

Coordenadas de Window e Clipping

Neste capítulo vamos abordar duas coisas muito importantes: um sistema de coordenadas que vai nos permitir um grau de liberdade muito maior na navegação com a window pelo mundo e uma técnica de otimização de visualização que nos permitirá determinar quais partes do mundo serão mostradas na tela e assim calcular apenas a visualização destas, chamados Métodos de Clipping ou de Recorte. Além disso veremos conceitos como: View Up Vector, Sistema de Coordenadas Normalizado ou de Window.

Métodos para Cálculo de Visualização em 2D

Para motivar este capítulo vamos recapitular alguns dos conceitos mais importantes vistos até o momento: para representar um mundo virtual qualquer em uma tela de computador, precisamos, além de uma estrutura de dados denominada display file, que contém esse mundo, de três outras entidades. Estas entidades são: uma área virtual, que representa uma parte do mundo qu queremos mostrar, uma área física, que representa uma parte do vídeo onde queremos desenhar esta parte do mundo e uma transformação que nos permite calcular como vamos desenhar esta parte do mundo no vídeo. Chamamos a estas entidades de:

Transformada Window-para-Viewport

• Window (estrutura de dados – janela): Uma área de world-coordinates (coordenadas do mundo) selecionada para ser mostrada;
• Viewport (estrutura de dados – área de desenho da tela): Uma área em um dispositivo de display para a qual o conteúdo de uma window é mapeado;
• Transformação de visualização (transformação – viewing transform): É o mapeamento de uma parte de uma cena em coordendas do mundo para coordenadas de dispositivo. Executado pela transformada de viewport.

Visualização de mundos complexos em duas dimensões

Até o momento vimos apenas uma forma de realizar a transformação de visualização. Esta forma é através de um mapeamento direto da window para a viewport.

Desvantagens do mapeamento direto window => viewport

• Navegação limitada;
• Eixos de coordenadas de window e de viewport são sempre paralelos;
• Transformada de viewport é apenas um transformação de escala;
• Operações como rotação da window são impossíveis.

Para adquirir independência de dispositivo, os windows são tipicamente definidos dentro de um quadrado unitário ou normalizado (normalized coordinates)

Estendendo o conceito de Window

Window: Para permitir todos os graus de liberdade na navegação no mundo, uma window deveria ser um retângulo com qualquer orientação. Até agora foi visto apenas windows paralelas ao sistema de coordenadas do mundo. Para extendermos uma window de forma a podermos realizar o efeito de panning, mesmo em 2D, temos de definir um terceiro sistema de coordenadas intermediário, entre o sistema de coordenadas do mundo e o sistema de coordenadas do vídeo. Este sistema de coordenadas pode ser chamado de sistema de coordendas normalizado ou sistema de coordenadas de plano de projeção.

Em (a) vemos a window em sua posição original na cena 2D e como aparece o recorte da cena por ela delimitado quando mostrado na viewport. Se rotacionamos a window em sentido anti-horário na cena, teremos a situação mostrada em (b): os eixos da window não estão mais paralelos aos eixos de coordenadas do mundo e a viewport passaraá a mostrar a cena como se houvéssemos rotacionado o mundo em sentido horário.

O Sistema de Coordenadas Normalizado

Para criar um esquema flexível de referência para a especificação do window em relação às coordenadas do mundo criou-se o sistema de coordenadas normalizado – SCN. Este sistema de coordenadas definia um conjunto de coordenadas próprias para a window. Era chamado de normalizado porque se definia a window como tendo tamanho unitário quando representada nele.

O SCN é um nível de representação intermediário entre as coordenadas de tela (viewport) e as coordenadas de mundo (WC). Como define um novo sistema de coordenadas próprio para a window, permite um grau de liberdade a mais na navegação com a window: a rotação da window. Calcular a visualização do mundo agora tem de ser realizado em duas etapas: a) Mapear do mundo para o SCN e b) mapear do SCN para coordenadas de viewport. O mapeamento SCN => viewport é uma transformação de escala apenas, pois seus eixos de coordenadas são paralelos para windows retangulares.

• Origem das coordenadas de visualização: P0 = (x0, y0)
• View up vector vup: Define a direção yv de visualização

A origem do SCN é definida como sendo o centro da window.

Para uma determinada viewport conhecida, podemos calcular uma única matriz de transformação composta em coordenadas homogêneas. Toda vez que movemos ou rotacionamos a window temos de recalcular esta matriz de transformação. Fazer isto, porém, tem implicações sobre o cálculo do que é visível e do que cai fora da window/viewport. Veremos isto mais adiante. O procedimento padrão, se desejamos utilizar SCN, é mapear de WC para SCN e guardar estas coordenadas.

Implicações do sistema de coordenadas normalizado

Cada objeto do mundo agora é representado em dois sistemas de coordenadas:

• Coordenadas do Mundo: suas coordenadas reais. Abreviamos por WC – World Coordinates;
• Coordenadas Normalizadas: coordenadas do objeto expressas em termos de u e v, com origem em (Wcx, Wcy). Estas coordenadas são recalculadas toda vez que movemos, escalonamos ou rotacionamos a window. Tradicionalmente normalizadas dentro da window para o intervalo [0,1] ou [-1,1]. No exemplo da figura acima estamos utilizando [-1,1] pois colocamos a origem no centro da window. Para usar [0,1] teríamos de colocar a origem no canto inferior esquerdo da window.

O display file pode se extendido para suportar esta representação intermediária, se o desejarmos, da forma como está descrito abaixo..

Display file extendido para suportar SCN.

Alternativas ao Sistema de Coordenadas Normalizado

Pode-se continuar a representar a window em termos das unidades de medida do sistema de coordenadas do mundo, apenas introduzindo um novo sistema de eixos de coordenadas sempre paralelos às bordas da window. Chamamos este sistema de sistema de coordenadas de plano de projeção – CPP.

Quando não possuímos um hardware gráfico com capacidades de processamento de matrizes à nossa disposição e temos de realizar todas as operações via software, o uso do CPP possui várias vantagens:

• Mantem a unidade de medida do mundo: muito menos operações de divisão;
• Representa Vup por (xw1, yw1)(xw2, yw2) ao invés de (Wcx, Wcy)(vupx, vupy)

Uma vez representados os objetos do mundo em CPP, para todas as operações de navegação que utilizem apenas translações, podemos representar cada operação diretamente no CPP, sem necessidade de recálculo do mapeamento WC => CPP, apenas através de somas e subtrações, sem necessidade de operações matriciais.

Alternativas ao Sistema de Coordenadas Normalizado.

Criando uma representação de um mundo em CPP: Transformamos o sistema de coordenadas para um sistema com origem em Wc e eixos paralelos aos limites da Window. O processo é extremamente simples:

• Se vup for paralelo ao eixo Y, apenas transladamos Wc para a origem e aplicamos a transformada de viewport;
• Se vup não for paralelo ao eixo Y, rotacionamos o mundo e a window em torno de (Wcx, Wcy) por -§(Y, Vup);.

Transformando em coordenadas do plano de projeção.

Como representar e usar o CPP ?

Para representar e usar o CPP, altere o display file. Cada objeto gráfico de seu display file passará a possuir dois conjuntos de coordenadas:

• as coordenadas do mundo – WC;
• as CPP.

Altere a definição da Window: será representada por dois conjuntos de coordenadas também: WC e CPP. Isto é diferente do SCN. Ali não precisávamos representar a própria window em SCN.

Utilize a representação em CPP dos objetos e da window para a transformada de Viewport.

Como eu navego no Mundo usando o CPP ?

O referencial do usuário que está sentado ao computador é o CPP

• Calcule o deslocamento da window no CPP: Ex.: “seta para cima” faz window mover 10 unidades na direção Vup.
• Mova a Window em termos de WC:
  • Transforme movimento resultante para WC;
  • Mude a posição ou orientação da window no WC;
• A plique o algoritmo Gerar Descrição em CPP

Translação oblíqua da window

Como implementar a rotação da window durante a navegação?

Rotação da window durante a navegação peloi mundo 2D. Estamos com a window como mostra (a) e desejamos modificar a direção de “caminhada” da window, rotacionando-a em 85 graus no sentido anti-horário. Para tanto a window roda em torno de seu centro e termina na posição mostrada em (b).

Pode ser realizado em dois passos:

• Considere a window como um objeto gráfico qualquer e aplique a rotação de objetos sobre um ponto arbitrário à window em WC;
• Recalcule as coordenadas do mundo em PPC aplicando o algoritmo Gerar Descrição em CPP;
  • Observe que o mundo será girado na direção contrária àquela que você girou a window;

Como uso o CPP na prática ?

A utilização do sistema de Coordenadas do Plano de Projeção como sistema de coordenadas para a window nos traz uma série de vantagens em relação ao SCN – Sistema de Coordenadas Normalizado, pois não é necessário retransformar todo o mundo para o CPP a cada operação de navegação com a window, como teria de ser feito no SCN. No CPP a window não se encontra necessariamente na origem do sistema de coordenadas, mas sim navega livremente nele. A única exigência do CPP é que seus eixos sejam paralelos às bordas da window para que os algoritmos de clipagem que vamos ver adiante possam funcionar de forma eficiente. No CPP apenas relizamos uma transformação de sistema de coordenadas e recalculamos a representação do mundo em CPP quando a window sofreu uma operação de rotação durante a navegação pelo mundo, como mostrado na See Rotação da window durante a navegação peloi mundo 2D. Estamos com a window como mostra (a) e desejamos modificar a direção de “caminhada” da window, rotacionando-a em 85 graus no sentido anti-horário. Para tanto a window roda em torno de seu centro e termina na posição mostrada em (b). acima. Em todos os outros casos de navegação ou de zoom a window simplesmente é transladada no CPP, o que torna o processo bem mais eficiente.

Para usar o CPP, podemos estender o display file de uma forma bastante simples. Basta-nos estender cada estrutura de dados que representa algum objeto geométrico de forma a possuir duas representações: uma no sistema de coordenadas do mundo e outra do CPP. Toda vez que uma operação de rotação na window fizer com que tenhamos que rotacionar o sistema de referência do CPP, recalculamos os valores das coordenadas de CPP de cada objeto do display file com base nas coordenadas de mundo deles.

Display file extendido para suportar CPP.

SCN ou CPP?

Vimos duas formas de se realizar a representação intermediária entre o sistema de coordenadas do mundo e a viewport: o SCN e o CPP. Uma delas você vai precisar se desejar que seu SGI seja capaz de oferecer ao usuário a possibilidade de rotacionar a window ao navegar no mundo 2D e, mais tarde, quando virmos 3D, você não vai encontrar nenhum caminho para realizar a navegação que não passe por uma representação intermediária desse tipo.

A pergunta, porém é: qual representação é mais vantajosa ? Resumimos abaixo as vantagens e desvantagens de cada enfoque.

O que é clipping?

Clipping ou recorte é um procedimento para a otimização do processo de cálculo da visualização dos objetos do display file, eliminando desse cálculo as primitivas geométricas que não se encontram sob a window e particionado as primitivas geométricas parcialmente aparentes. Opera no sistema de coordenadas utilizado pela window. Seus objetivos são:

• Distinguir se primitivas geométricas estão dentro ou fora do viewing frustum (regiões do espaço especificadas);
• Distinguir se primitivas geométricas estão dentro ou fora do picking frustum, regiões do espaço que podem interagir com o mouse;
• Detectar intersecções entre primitivas;
• Calcular sombras (em 3D)

Por quê recortar?

Clipping é uma otimização importante por:

• Ser o preprocessamento de visibilidade;
• Remover uma fração considerável do mundo antes de se realizar o cálculo de visualização;
• Assegurar que somente primitivas potencialmente visíveis serão rasterizadas.

Recorte de Pontos

Para uma clip window retangular, o recorte de pontos ou point clipping é um processo rápido e muito simples. O ponto que deve ser apresentado na viewport é aquele para o qual as inequações abaixo são satisfeitas:

Recorte de Linhas

Existem vários relacionamentos possíveis com uma região de clipping retangular. Estes relacionamentos possíveis são:

Linhas em WC e depois do clipping.

• Completamente dentro do window de clipagem (desenhar);
• Completamente fora do window (não desenhar);
• Parcialmente dentro do window (o que desenhar ?).

Recorte de Linhas usando representação paramétrica da reta

Este método utiliza a verificação por meio da equação paramétrica envolvendo os limites da janela e a própria linha:

• Grande quantidade de cálculos e teste e não é muito eficiente. Num display típico, centenas ou milhares de linhas de linha podem ser encontradas.

Para que um algoritmo seja eficiente:

• Deve promover alguns testes iniciais de forma a determinar se cálculos de interseção são realmente necessários;
• O par de pontos finais pode ser checado de antemão para observar se ambos pertencem à window, significando que nenhum teste necessitará ser feito.

A representação paramétrica da reta é dada pela equação:

Recorte de Linhas de Cohen-Sutherland:

Este método utiliza uma representação das extremas dos segmentos de reta associada a códigos de regiões.

Estes códigos são códigos de região binários de 4 dígitos atribuídos a todo ponto final de uma linha na figura. São chamados region codes (RC).

Numera-se as posições no código de regiões de 1 a 4. Cantos são representados por soma de valores, como mostra a See Códigos binários de regiões para recorte.

Códigos binários de regiões para recorte.

Os valores dos códigos de região são determinados através da comparação das coordenadas das extremidades aos limites da window. Um valor 1 em qualquer posição indica que o ponto está neste quadrante.

Existem três possíveis relacionamentos:

• Segmento completamente contido na window.
  • 
    0000
    para ambas as extremidades.
• Segmento completamente fora da window.
  • 
    AND
    logico dos códigos de região para ambas as extremidades resulta diferente de
    0000.
• Segmento parcialmente contido na window.
  • As extremidades possuem códigos de região diferentes;
  • 
    AND
    logico dos códigos de região para ambas as extremidades resulta em
    0000
    .

Aceitando ou rejeitando segmentos de reta no recorte de retas de Cohen-Sutherland.

Exemplo de aplicação de recorte com Cohen-Sutherland

Duas retas paralelas para clipar com Cohen-Sutherland.

Entenderemos melhor o algoritmo acima através de um exemplo. Para isso observe as duas retas paralelas na figura abaixo. Vamos clipar passo a passo estas retas utilizando o algoritmo de Cohen Sutherland.

Clipando R1

• RC1 = [0001] -> esquerda e RC2 = [0000] -> dentro
  • Clipamos apenas à esquerda e calculamos novo y1 para a linha.
• Cálculo do coeficiente angular:
  • m = (y2 – y1)/(x2 – x1) = (17 – 12)/(15 – 5) = 5 / 10 = 0.5
• Aplicamos a fórmula esq.: yintersec = m* (xE – x1) + y1
  • yintersec = 0.5 * (10 – 5) + 12 = 2.5 + 12 = 14.5
• Como 14.5 > yF = 10 e 14.5 < yT = 20 aceitamos.
  • Nova linha clipada é: (10,14.5)(15,17);

Clipando R2

RC1 = [0001] -> esquerda e RC2 = [1000] -> topo

• Clipamos à esquerda e calculamos novo y1 para a linha.
• Clipamos ao topo e calculamos novo x2 para a linha

Cálculo do coeficiente angular:

• m = (y2 – y1)/(x2 – x1) = (23 – 18)/(15 – 5) = 5 / 10 = 0.5

Aplica-se a fórmula esq.: yintersec = m* (xE – x1) + y1

• yintersec = 0.5 * (10 – 5) + 18 = 2.5 + 18 = 20.5

Como 20.5 > yF = 10 mas 20.5 não é < yT = 20 rejeitamos.

• Intersecção é fora da window
• Não é necessário calcular x2 – se uma intersecção for fora a outra também o será.

O segmento de reta R2 é descartado como não visível.

O resultado obtido será o mostrado na figura abaixo.

Resultado da clipagem das retas da figura anterior.

O que fazer neste caso?

Como procedemos quando um ponto cair em um dos cantos?

Observe o exemplo da See Conjunto de retas a serem recosrtas com Liang-Barsky. Quando o RC associado a um ponto de uma linha possuir dois “1”, calculamos a intersecção com as bordas da window para os dois casos.

• No exemplo calcularíamos um x2 pelo topo e um y2 pela direita.

Aceitamos dentre os dois valores calculados, aquele que se encontrar sobre a window

• O outro estará fora.
• Exceção: linha cai exatamente sobre o canto. Nesse caso temos de escolher um dos dois.

Recorte de linhas de Liang-Barsky

Em 1978 Cyrus e Beck publicaram um novo algoritmo para o clipping de linhas usável para clipar linhas contra um polígono convexo em 2D ou um poliedro convexo em 3D usando a equação paramétrica. Em 1984 Liang e Barsky reformularam este algoritmo, tornando-o mais eficiente. Esta versão será vista a seguir. Reescreva as equações paramétricas como segue:

Condições:

• pk = 0, paralela a um dos limites:
  • qk < 0, fora dos limites
  • qk >= 0, dentro dos limites
• pk < 0, a linha vem de fora para dentro
• pk > 0, a linha vem de dentro para fora

Recorte de linhas de Liang-Barsky

Qual a parte que está dentro?

Os parâmetros u1 and u2 definem qual parte está dentro do retângulo:

• O valor de u1 : de fora para dentro (pk < 0)

Se u1 > u2, a linha está completamente fora.

Exemplo de Liang-Barsky

Exemplo detalhado usando Liang-Barsky

Calculemos detalhadamente um exemplo usando Liang-Barsky. Para tanto tome a figura abaixo como ponto de partida.

Conjunto de retas a serem recortadas com Liang-Barsky

Calcular p e q para R1

• p1 = -Dx = -(15 – 5) = -10
• p2 = Dx = 15 – 5 = 10
• p3 = -Dy = -(17 – 12) = -5
• p4 = Dy = 17 – 12 = 5
• q1 = x1 – xwmin= 5 – 10 = -5
• q2 = xwmax – x1 = 25 – 5 = 20
• q3 = y1 – ywmin= 12 – 10 = 2
• q4 = ywmax – y1 = 20 – 12 = 8

Calcular u1 para R1

p1 = -10 < 0

p3 = -5 < 0

r1 = q1/p1 = -5/-10 = 0.5

r3 = q3/p3 = 2/-5 = – 0.4

u1 = max (0, r1, r3) = max (0, 0.5, -0.4) = 0.5

Substituindo na equação paramétrica:

x = 5 + 0.5 * 10 = 10 (o que nós já sabíamos)

y = 12 + 0.5 * 5 = 14.5 (o que nós não sabíamos)

Calcular u2 para R1

p2 = 10 > 0

p4 = 5 > 0

r2 = q2/p2 = 20/10 = 2

r4 = q4/p4 = 8/5 = 1.6

u2 = min (1, r1, r3) = min (1, 2, 1.6) = 1

Como u2 resulta 1, rejeitamos o cálculo de novos valores de dentro para fora.

Recorte de linhas de Nicholl-Lee-Nicholl

A algoritmo de Nicholl-Lee-Nicholl utiliza uma forma bastante diferente de determinação da intersecção entre o segmento de reta examinado e os limites da window.

Toma-se um ponto do segmento de reta, P1, e divide-se a imagem em quadrantes, traçando novos segmentos de reta passando pelos vértices da window. Depois verifica-se em qual dos quadrantes P2 se encontra, simplesmente comparando as inclinações da retas que criamos interligando P1 e os vértices da wundow e o segmento que queremos clipar. Quando determinamos qual o quadrante, calculamos a intesecção de retas apenas com o lado da window que está neste quadrante.

Comparado NLN aos algoritmos C-S e L-B:

• NLN realiza menos comparações e divisões;
• NLN pode ser aplicado somente a 2D clipping.

Primeiros passos da clipagem deNicholl-Lee-Nicholl

O algoritmo NLN:

• Clipa uma linha com extremas P1 e P2;
• 1º passo: determinar P1 para os nove quadrantes:
  • Somente três regiões são consideradas;
  • Para o resto usa-se uma transformada de simetria;
• 2º passo: determinar a posição de P2 em relação a P1

Para determinar em qual região P2 está:

• Compare-se a inclinação da reta com as inclinações das retas hipotéticas calculadas. Ex: P1 está à esquerda, P2 está em LT.

Clip windows não retangulares

Em algumas situações especiais teremos windows não retangulares. Isto geralmente acontece quando a aplicação, por alguma razão estética, utiliza uma viewport não retangular. O sistema de janelas do sistema operacional NeXTSTEP, da linha de computadores NeXT, uma tentativa de um sócio da Apple de fazer algo diferente do Macintosh, utilizando um processador Motorola 68040, por exemplo, possuía planejada a possibilidade de se desenvolver aplicações com janelas redondas ou ovais.

NeXT Cube rodando NEXTSTEP

Para trabalhar com windows não convencionais, algumas técnicas foram desenvolvidas. Vamos apenas citá-las resumidamente aqui:

• Algoritmos baseados em equações parametricas podem ser extendidos a Polígonos Convexos:
  • Método de Liang-Barsky;
  • Modificar o algoritmo para incluir as equações paramétricas de todas as bordas definidas pelo polígono de clipping;
• Métodos de Recorte de Regiões Côncavas:
  • Dividir em um conjunto de polígonos convexos;
  • Aplicar métodos paramétricos;
• Círculos e outras regiões de clipagem curvas:
  • Linhas podem ser clipadas através do retângulo de limítrofe.

Recorte de windows na forma de polígonos côncavos:

Identificar se um polígono é côncavo:

• Calcular o produto cruzado dos vetores de borda;

Produto cruzados dos vetores da borda

• Uma componente z negativa resultante da multiplicação posicionada entre componentes positivas indica uma concavidade local;

Divisão de polígonos côncavos: método vetorial

• Calcular o produto cruzado dos vetores de borda em sentido anti-horário;
• Se alguma componente Z for negativa:
  • É côncavo.
  • Dividir ao longo da primeira das duas linhas do produto cruzado:

Polígonos convexos resultantes

Método da rotação

Outra opção é rotacionar o polígono sobre o eixo x aresta a aresta e verificar se há interesecção de alguma outra aresta com este eixo. Se houver, o intersecção já vai mostrar como subdividir o polígono em subpolígonos convexos.

Método da rotação

Após a rotacionar V3 em torno do eixo x, V4 está abaixo do eixo x.

O corte do poligono é realizado através da linha entre os pontos V2V3.

Recorte de polígonos

Recortar objetos de formato poligonal na cena pode ser tratado como recorte de linhas quando os polígonos são vazios. Quando os polígonos são preenchidos, este método já não traz mais resultados satisfatórios, como mosra a See Comparação entre clipping de polígonos como linhas clipping real de polígonos..

Comparação entre clipping de polígonos como linhas clipping real de polígonos.

Recorte de polígonos de Sutherland-Hodgeman

Este método processa as bordas do polígono como um todo contra cada aresta do window:

• Todos os vértices do polígono são processados contra cada uma das arestas do window;

Clipping de polígonos de Sutherland-Hodgeman.

• Passe cada par de vértices adjacentes do polígono a um clipador de linhas qualquer, criando novos pontos em um novo polígono: São quatro casos:

Sutherland-Hodgeman.

• Lista de vértices intermediários:
  • Cada vez que realizamos a clipagem para todos os vértices contra uma das 4 bordas do window, regeneramos o polígono;
  • Este novo polígono é clipado contra outra das 4 bordas do window;
• Polígonos convexos são tratados corretamente;
• Caso seja côncavo:
  • Divida em subpolígonos côncavos;

Recorte de polígonos de Weiler-Atherton

O algoritmo de Weiler-Atherton é o mais genérico algoritmo de recorte para polígonos e recorta um polígono côncavo com buracos interiores em relação aos limites de outro polígono côncavo, que também pode possuir buracos interiores. Na terminologia do algoritmo de Weiler-Atherton, o polígono a ser recortado é chamado de polígono-objeto e a região de recorte é chamada de polígono de recorte. As novas arestas do polígono-objeto, criada por seu recorte contra o poilígono de recorte, são idênticas a partes do polígono de recorte. O clipping de polígonos de Weiler-Atherton foi desenvolvido para identificação de superfícies visíveis.

Recorte de polígonos de Weiler-Atherton.

Características:

• Pode ser aplicado a uma região de recorte arbitrária;
• Pode ser usado para seguir as bordas de qualquer coisa com qualquer formato;

Se processamos em sentido horário procedemos assim:

• Para um par de vértices de fora para dentro, siga a aresta do polígono;
• Para um par de vértices de dentro para fora, siga o limite da window em sentido horário.

Detalhamento do método de Weiler-Atherton

A implementação do algoritmo de W-A utiliza uma lista circular de vértices para descrever o polígono de recorte e todos os polígonos-objeto. Escolhe-se como convenção percorrer o polígono de recorte e os polígonos-objeto externos de objetos com limite polígonal sempre no sentido horário e os limites internos de objetos com furos no sentido anti-forário. Desta forma a superfície ou área cheia do objeto delimitado pelo polígono está sempre à direita. As arestas do polígono de recorte e dos polígonos-objeto podem ou não intersectar. Caso o façam, isto ocorre sempre aos pares, uma de entrada e outra de saída.

O algoritmo inicia o processamento em alguma intersecção inicial e segue a borda externa do polígono-objeto em sentido horário até encontrar outra intersecção. Na interseção, dobra-se à direita e segue-se o exterior do polígono de recorte em sentido horário até encontrar uma intersecção com o polígono-objeto. Nesta intersecção dobra-se novamente à direita e segue-se o polígono-objeto. O processo é realizado até se voltar ao ponto de partida. Limites interiores do polígono-objeto são seguidos em sentido anti-horário.

Exemplos de Weiler-Atherton segundo Winfried Kurth, Universidade de Cottbus, Alemanha. Em cinza sempre a janela de recorte.

Outros tipos de Recorte

Além dos métodos de recorte vistos até agora, existem ainda alguns outros, específicos para aplicações avançadas ou para programas de desenho e design gráfico. Veremos resumidamente adiantes estes métodos.

Recorte de curvas

O recorte de curvas em SGIs utilizando modelos de arame, como veremos adiante, nos Capítulos 4 e 7, pode ser realizado através de métodos de recorte de linhas aplicados durante o processo de desenho das curvas 2D ou superfícies 3D. Se desejarmos uma representação eficiente e rápida de mundos contendo muitas curvas ou uma renderização realista em 3D de superfícies curvas preenchidas utilizando técnicas de renderização de raytracing como conversão por varredura, vistas no capítulo 8 e seguintes, teremos de possuir uma forma eficiente de realizar o recorte dessa curvas ou superfícies. Isto é especialmente importante em 3D, onde necessitamos determinar o polígono que representa a parte visível de uma superfície curva antes de iniciar o raytracing.

Existe um conjunto de técnicas bastante simples para recorte eficiente de curvas baseado na idéia de se usar o casco convexo da curva, que em curvas cúbicas é um losango, para testar se a curva se encontra totalmente dentro, totalmente fora ou parcialmente dentro da window. A partir daí pode-se utilizar diferentes graus de refinamento para determinar o ponto da curva que entra ou sai da window. Um algoritmo bastante utilizado para isso é denominado Bézier-Clipping justamente por se aproveitar da propriedade de casco convexo das curvas de Bézier e uma excelente análise dele, além de outras referências, se encontram em .

Recorte de círculos

Para o recorte de círculos usa-se as coordenadas de quadrantes individuais, dividindo o círculo em quadrantes e verificando a pertinência destes à window. Recursivamente o algoritmo devide as partes parcialmente contidas na window. Neste processo recursivo pode-se primeiramente gerar octantes e depois ir diminuindo no segmento onde a pertinência for parcial.

Recorte de texto

O clipping de texto pode ser realizado de duas formas diferentes. Em ambas as formas utiliza-se um casco convexo, que é ou definido ao redor do texto todo ou ao redor de cada caractere:

• All-or-none string-clipping: Tomar limites do casco convexo de um string como todo e verificar a pertinência total deste polígono à window utilizando a regra de pertinência dos pontos extremos;
• All-or-none character-clipping: Tomar limites do casco convexo de carateres individuais pela regra de pertinência do ponto;

Recorte de texto pelo método all-or-none string-clipping.

O método all-or-none string-clipping é o mais eficiente dos dois, mas possui a desvantagem de descartar strings parcialmente na window, como o texto mais à esquerda na See Recorte de texto pelo método all-or-none string-clipping.

Recorte exterior.

Exercício 1.3: Implementando Clipping

Parte I: Implementando recorte para os objetos já existentes em seu SGI

Implemente uma as principais técnicas de clipagem para windows retangulares vistas neste capítulo, usando clipagem de pontos e clipagem por C-S, L-B ou NLN para retas, de forma a integrá-las ao seu sistema gráfico de maneira que a transformada de viewport seja aplicada apenas aos objetos resultantes do clipping.

Exemplo de interface de usuário de uma realização do exercício proposto de forma a testar confortavelmente a clipagem.

Para ter certeza de que a clipagem está funcionando e não é o algoritmo de clipagem de pontos embutido no seu objeto de interface que está fazendo com que as linhas que você está desenhando sejam cortadas no lugar certo, faça sua viewport ser menor do que o seu objeto de desenho (canvas, subcanvas ou outra coisa que você escolheu), de maneira que a viewport inicie em coordenadas do tipo 10,10 e termine antes do fim da área de desenho, cmo mostra a figura abaixo, onde a viewport está limitada pela moldura imediatamente interna à área de desenho. Dessa forma, se o seu algoritmo clipar algo de forma incorreta, deixando de recortar algum elemento, você vai enxergar imediatamente pois verá o objeto sair de dentro deste retângulo. Como forma de debugar seu exercíco este é um subterfúgio excelente e torna desnecessário analisar os dados gerados para uma lista enorme de objetos clipados para testar o sistema.