Loading

Alison's New App is now available on iOS and Android! Download Now

Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Olá e bem-vindo à palestra número 22 no curso Computer Graphics. Atualmente estamos discutindo o pipeline de gráficos 3D. E o pipeline tem 5 estágios. Já discutimos representação de objetos que é a primeira etapa. Em seguida, modelagem de transformações-segundo estágio. Iluminação ou designação de cor-terceira fase. Atualmente, estamos na quarta etapa que está visualizando pipeline. Como você pode ver, ele consiste em 5 sub-estágios. Já discutimos poucos desses e continuando a nossa discussão sobre os restantes.
Por isso, entre essas sub-etapas já discutimos anteriormente. Visão de transformação, transformação de projeção e transformação de viewport.
Mais duas operações estão lá, como vimos no pipeline; recorte e remoção de superfície oculta. Entre eles atualmente estamos discutindo recorte.
Por isso, na última palestra, introduzimos a ideia básica de clipping e também discutimos o recorte de linha 2D. Assim, continuará nossa discussão sobre clipping. Hoje, vamos discutir clipping de área de preenchimento, bem como recorte 3D.
Então, o que é esse recorte de área de enchimento? Por isso, como mencionamos, quando falamos de recorte, há uma janela de clipping e mais cedo discutimos como clip pontos e linhas contra esta janela. No entanto, quando projetamos objetos a projeção talvez na forma de uma área de preenchimento como um polígono onde há um limite.
Agora recortar uma área preenchida é diferente de captar um ponto ou uma linha, como veremos na palestra de todays. Na verdade, tais situações são bastante frequentes na prática onde temos que clip polígonos contra a janela de recorte. Então, ele requer algum mecanismo para fazer isso.
Agora, o que pode ser uma abordagem muito óbvia e direta, vamos tentar entender a situação. Suponhamos que esta seja a nossa janela de recorte e nos seja dado um polígono, algo assim após a projeção dizer este triângulo. Por isso, temos que manter essa parte que está dentro da janela de recorte, que eu estou mostrando com sombra e temos que cortar a parte externa, de fora. Como podemos fazer isso?
Uma maneira pode ser usar os clippers de linha que discutimos em palestra anterior para cada uma das borda, como aqui é uma borda, uma borda, uma borda da área de campo. E, em seguida, realizar recorte nas bordas e decidir sobre a região recortada. No entanto, como você pode ver a partir deste exemplo, isso não é necessariamente fácil, eficiente e indo nos dar uma boa abordagem. Às vezes, é até difícil entender como funciona Em vez disso, exigimos abordagens melhores. Há de fato, muitos algoritmos eficientes propostos para o propósito. Nesta palestra vamos discutir duas dessas abordagens. Um é o algoritmo Sutherland-Hodgeman e o outro é o algoritmo Weiler-Atherton. Vamos tentar entender esses algoritmos.
Começaremos com o algoritmo Sutherland-Hodgeman, o que este algoritmo faz? Aqui neste algoritmo começamos com 4 clippers. Agora, esses clippers são essencialmente as linhas que definem o limite da janela. Por exemplo, se este é o meu limite de janela, então cada uma dessas linhas definindo o limite é um clipper.
Então, há 4 clippers em clipping 2D que é certo, esquerda, acima e abaixo. Agora, cada clipper leva como entrada uma lista de vértices ordenados que indicam, basicamente, as bordas, cada par de vértice indica a borda. E a partir dessa lista de entrada ela produz uma outra lista de vértices de saída que é a ideia básica. Sendo assim, há 4 clippers, cada clipper leva como entrada uma lista de vértices ordenados onde cada par de vértices representam uma borda. E então ele realiza algumas operações para produzir uma lista de saída de vértices.
Agora, quando executamos essas operações, impomos alguma ordem de verificação contra cada clipper que pode ser qualquer ordem. Aqui nesta discussão irá supor o clipper esquerdo primeiro, depois o clipper certo, depois o clipper de baixo e no final o topo ou acima do clipper.
Agora, como dissemos que começamos com o clipper esquerdo. Assim, seu conjunto de entrada são os vértices do polígono original ou em outras palavras, as bordas de polígono originais representados pelo par de vértices que é o conjunto de entrada para o primeiro ou o clipper esquerdo.
Agora, para criar uma lista de vértice como saída ou também para fornecer a lista de vértice de entrada, precisamos seguir uma convenção de nomenclatura, seja para nomear os vértices de maneira no sentido horário ou antirrelógio. Aqui novamente, vamos supor que seguiremos uma nomenclatura anticlockwise de vértices. Com essas convenções, vamos denotar a lista de vertex de entrada para um clipper pelo conjunto V tendo esses vértices.
Agora, para cada borda ou para o par de vértices na lista denotada por vi, vj. Realizamos algumas verificações e com base nos resultados da verificação, realizamos alguma ação. Então, quais são esses cheques?
Se vi está dentro e vj está fora do clipper então retornamos o ponto de interseção do clipper com a borda representada pelo par vertex vi, vj. Se ambos os vértices estiverem dentro do clipper, então retornamos vj.
Se vi está fora e vj está dentro do clipper, então retornamos duas coisas. Um deles é o ponto de interseção do clipper com a borda representada pelo par vi, vj e também vj. Ambas as coisas retornamos ponto de interseção e vj. E, finalmente, se ambos os vértices estiverem fora do clipper então não retornamos nada, retornamos nulo.
Agora aqui temos uso dos termos dentro e fora. Então, como eles são definidos? Na verdade esses termos devem ser interpretados de forma diferente para um clipper diferente. Então, não há um único significado para esses termos com base no clipper que definimos estes termos.
E vamos agora passar por essa definição para cada um dos 4 clippers. Por isso, para o clipper esquerdo, quando se fala de insight queremos dizer que o vértice está do lado direito do clipper e quando falamos de fora queremos dizer que ele está do lado esquerdo do clipper. Para o clipper certo é justamente o oposto.
Quando o vértice está do lado esquerdo, chamamos por dentro. Caso contrário, está fora. Para o clipper top se um vértice estiver abaixo do clipper que significa que ele está dentro.
Caso contrário, está fora. E para um clipper inferior, é novamente apenas o oposto de top clipper que significa dentro de vértice significa que está acima do clipper, enquanto que fora significa que está abaixo. E como determinar se um vértice está do lado direito ou esquerdo ou acima ou abaixo, apenas considerando-se os valores de coordenadas, comparando os valores coordenados do vértice com relação ao clipper particular.
Por exemplo, suponha que este seja o clipper superior, suponha que seja equação é dada por x = y = 4. Agora suponha que um ponto seja denotado por (3, 5). Agora verificamos aqui o valor y do ponto que é 5, claramente 5 é maior do que 4 que é o valor y do limite, limite superior. Depois, podemos dizer que este ponto está fora porque está acima do clipper. Da mesma forma, podemos determinar o interior e o exterior com base na comparação do valor de coordenadas x ou y do vértice com relação aos valores do clipper.
Se o vértice estiver sobre o clipper então ele é considerado dentro de todos os casos. Por isso, para um recortador de esquerda dentro significa ou está do lado direito ou no clipper, caso contrário, fica do lado de fora. E o mesmo é verdade para todos os outros clippers.
Agora, vamos tentar entender esse algoritmo em termos de um exemplo ilustrativo. Consideremos esta situação aqui definimos uma janela de clipping e temos uma área de preenchimento. Agora essa área de preenchimento é definida pelos vértices {1, 2, 3} como você pode ver aqui, seguimos uma convenção de nomenclatura em sentido horário ou anticlockwise para listar os vértices.
Nosso objetivo é determinar o polígono recortado. Esse é esse polígono denotado pelos vértices {2 ', 3', 3 '', 1 ' e 2}. E nós usamos para fazer isso seguindo o algoritmo Sutherland-Hodgeman.
Por isso, no início começamos com o clipper esquerdo. Em seguida, verificamos contra o clipper certo, depois o top clipper e depois o clipper inferior.
Vejamos o que acontece depois de verificar contra o clipper esquerdo. Portanto, aqui a lista de vertex de entrada são os vértices originais que são {1, 2, 3} o que indica as três bordas representadas pelo par vértice; {1, 2}; {2, 3} e {3, 1}. Por isso, para cada par realizamos o cheque. Para o par {1, 2} podemos ver que ambos os vértices estão no lado direito do clipper esquerdo que significa que ambos estão dentro. Então, Vout é 2 conforme o algoritmo.
Da mesma forma, depois de verificar por {2, 3} contra o clipper esquerdo, podemos ver que o Vout final torna-se {2, 3} levando em conta 2. E após verificar {3, 1} a lista final torna-se {2, 3, 1}. Em todos os casos contra o clipper esquerdo todos os vértices estão dentro.
Agora, vamos verificar contra o clipper certo. Então, agora a lista de vertex de entrada é {1, 2, 3} igual e inicialmente a Vout é NULL. Por isso, par de vértices tem que ser verificado {1, 2; 2, 3} e {3, 1}, todas as três bordas que precisamos verificar. Para 1, 2 ambos estão dentro do clipper certo. Podemos verificar comparando seus valores coordenativos porque ambos estão do lado esquerdo do clipper certo. Então, o Vout agora é 2. Então nós verificamos o par {2, 3} aqui podemos ver que 2 está dentro enquanto 3 está fora. Então, nesse caso nós computamos o ponto de interseção 2 'este ponto e então configuramos Vout para ser {2, 2'}.
Aí nós verificamos {3, 1} aqui o vértice 3 está fora porque ele está do lado direito do clipper, enquanto que 1 está dentro porque está do lado esquerdo. Então, aqui calculamos o ponto de interseção 3 'e, em seguida, finalizamos a lista de vertex de saída como {2, 2', 3 ' (e) 1}; pois neste caso retornamos 1 também. Então, depois de verificar contra o clipper certo, obtemos essa lista de saída; {2, 2 ', 3' (isso significa este ponto e), 1}.
Em seguida, verificamos contra o clipper top. Agora neste caso, o Vin ou a lista de vertex de entrada é a lista de vertex de saída após verificar contra o clipper certo. Sendo assim, são 2, 2 ', 3', 1. Então, inicialmente Vout é NULL. E o par de vértices que precisamos verificar são 4; {2, 2 ', 2', 3 ', 3' 1} e {1, 2}.
Então, primeiro nós verificamos {2, 2 '} contra o clipper top e descobrimos que tanto 2 quanto 2 traço estão dentro porque ambos estão abaixo do clipper. Então, a lista de saída se torna 2 '. Então verificamos o próximo par de vértice {2 ', 3'} novamente {2 ', 3'} ambos estão abaixo, então dentro então Vout se torna 2 'e 3'.
Depois verificamos 3 ', 1 neste caso, vemos que 3' está dentro, enquanto que 1 está fora. Em seguida, calculamos o ponto de interseção 3 '' aqui e modifique nossa lista de saída para ser {2 ', 3', (e) 3 ''}. Finalmente, verificamos {1, 2}. Aqui vemos que 1 está fora enquanto 2 está dentro. Em seguida, novamente calculamos o ponto de interseção 1 'e modifique o Vout para ser {2', 3 ', 3' ', 1' (e) 2}. Então, esta é nossa lista de saída após verificar contra o clipper top, e isto serve como a lista de entrada para o clipper restante a ser verificado que é de baixo clipper.
Esta é a lista de entrada para a lista de baixo clipper e a lista de saída é inicialmente nula e como podemos ver todos esses vértices 2, 2 ', 3', 3 '' e 1 ' estão dentro porque estão acima do clipper inferior. Então, a lista de saída passa a ser a mesma que é {2 ', 3', 3 '', 1 ', 2}. Esta também é a saída do algoritmo, pois aqui não há mais clippers estão lá para verificar contra e o algoritmo pára. Por isso, no final do algoritmo, obtemos esta lista de vértice que representa a região recortada. É assim que o algoritmo funciona.
Agora nos movamos para o nosso próximo algoritmo que é o algoritmo Weiler-Atherton. Agora, o algoritmo Sutherland-Hodgeman que acabamos de discutir funciona bem quando a área de preenchimento é um polígono convexo e ela deve ser recortada contra uma janela de clipping retangular. Então, se essa condição satisfazer então o algoritmo Sutherland-Hodgeman funciona bem.
No entanto isso não precisa ser o caso sempre e que o algoritmo Weiler-Atherton fornece uma solução mais geral. Este algoritmo pode ser usado para qualquer polígono, côncavo ou convexo contra qualquer janela de clipping poligonal. Não precisa ser apenas um retângulo. Vejamos como funciona.
Assim, tentaremos entender o algoritmo em termos de um exemplo em vez de passos formais. Consideremos este cenário aqui temos uma janela de recorte retangular e uma área de enchimento. Por isso, vamos tentar entender como o algoritmo nos ajuda a identificar as peças a serem descartadas que é essa região e as peças a serem mantidas após recorte que são essas duas regiões esta e esta. Então, aqui começamos com o processamento das bordas da área de preenchimento em uma ordem particular, o que é tipicamente anti-horário. Por isso, aqui começamos com o processamento das bordas da área de preenchimento em uma ordem particular que tipicamente é anti-horário.
Então, o que fazemos no processamento, verificamos as bordas uma por uma, continuamos ao longo das bordas até encontrarmos uma borda que cruza para o lado de fora do limite da janela do clipe. Comecemos por esta borda (1, 2) esta borda. Então, nós verificamos se ele cruza o limite da janela ou não, esse é o nosso processamento. Ele não se crua assim continuamos até a próxima etapa, ou seja {2, 3} representada pelo par vértice {2, 3}.
Agora esta borda cruza para o lado de fora do limite da janela. Observe que aqui estamos seguindo a ordem anticlockwise. Se a borda não crua para o exterior em vez disso se a borda estiver atravessando para dentro da janela então nós apenas registramos por ponto de interseção, enquanto se a borda estiver atravessando para o limite exterior, então paramos e realizamos alguma ação diferente, o que fazemos nesse caso.
No ponto de interseção, fazemos um desvio. Então, aqui o ponto de interseção é 2 ' este ponto. Então, então nós fazemos um desvio. Não continuamos mais ao longo desta direção. Em vez disso, o que fazemos agora seguimos a borda da janela do clipe ao longo da mesma direção, mantendo a ordem transversal.
Então, agora neste exemplo assim seguiremos este sentido anti-horário e faremos um desvio daqui agora ao longo do limite da janela, então aqui seguiremos esta ordem. Então, essencialmente, como você está atravessando, nós inicialmente atravessamos desta forma então enquanto atravessamos desta forma descobrimos que esta borda está atravessando para o lado de fora. Então, então nós atravessamos desta forma em vez de continuar ao longo da borda.
Agora, este ao longo do atravessamento da fronteira, continuamos até encontrar outra borda de área de preenchimento que cruza para o interior da janela do clipe. Então, aqui como você pode ver, se seguirmos um traversal anti-horário, então essa borda é na verdade cruza para o interior. Então, a borda é de 6, 1 denotada pelo par vértice 6, 1 que cruza para o interior da janela e a encontramos enquanto atravessava ao longo do limite da janela. Nesse ponto o que fazemos?
Nesse ponto, retomamos o traversal de borda do polígono novamente ao longo da mesma direção. Então, nós paramos aqui e então novamente continuamos ao longo da mesma direção até que nos deparamos com ponto de interseção previamente processado. Então, aqui continuamos até o ponto 1 porque o ponto um já está processado. Então, nós paramos aqui.
Então, depois dessa parte, vemos que começamos a partir daqui, depois atravessamos até este ponto, determinamos esse ponto de interseção, depois atravessamos nessa linha até este ponto de interseção, atravessado de volta até o ponto de origem. Por isso, há duas regras de passagem de um ponto de interseção devido a fora para dentro da área de preenchimento dentro devemos seguir as bordas do polígono a partir de um ponto de interseção devido a dentro para fora da área de preenchimento da área de preenchimento devemos seguir os limites da janela.
Então, essas são as regras que aplicamos enquanto realizamos o traversal. Mas isso nos dá uma parte da área recortada que é essa parte e, aparentemente aqui, parou. Então, como chegar à outra parte? Na verdade, aqui o algoritmo não para. O que acontece depois?
Antes de entrarmos nisso, também, deve-se lembrar que sempre que estamos atravessando a direção transversal permanece o mesmo, independentemente de se você está atravessando ao longo da borda ou ao longo do limite do windows. Por isso, se você está seguindo um sentido anti-horário, deve ser antihorário sempre.
E depois que esse traversal termina, a saída é a lista de vértice representando uma área recortada, como vimos. Por isso, neste caso o atravessado terminou em 1. Então, nós conseguimos a lista de vértice {1, 2, 2 ', (e) 1'} o que nos dá essa área recortada.
Mas, claramente aqui, toda a área de preenchimento não está coberta. Alguns dos vértices ainda não são processados, então então o que fazemos? Retomamos o atravessamento caso todos os vértices não sejam processados. Retomamos o traversal ao longo das bordas do polígono na mesma direção a partir de último ponto de interseção de um interior de borda fora do polígono. Então, nosso último ponto de interseção de um dentro de fora do polígono edge é 2 ' aqui. Lembre-se que este 1 ' está fora do interior de borda. Então, não é aplicável. Então, o que é aplicável é 2 '. Por isso, a partir daí retomamos nossa passagem até cobrimos os demais vértices.
E esse traversal é de uma forma semelhante que fizemos antes. Então, aqui o que fazemos, trafegamos ao longo deste sentido anti-horário para o vértice aqui. Então, atravessamos esta borda, depois esta borda. Mas aqui, como você pode ver, há um fora para dentro da travessia. Então, nós não fazemos nada, continuamos atravessando desta forma, desta forma. Agora a esta altura podemos ver que um dentro para a passagem externa está lá. No caso anterior, estava do lado de fora para dentro.
Aqui está, dentro para fora aos 6 '. Então, agora atravessamos ao longo da borda. Em seguida, encontramos este ponto de interseção novamente. Isso é de fora para dentro. Então, agora retomamos nossos atravessados ao longo da borda. Então, finalmente o que fizemos, atravessamos esta direção, esta direção, esta direção, então esta direção, então esta direção, esta direção. Agora já que já encontramos 4 minutos antes para que paremos nosso traversal aqui quando encontramos 4. Em seguida, obtemos essa porção restante da área recortada também exatamente como a forma como conseguimos mais cedo. Então, é assim que Weiler-Atherton trabalha.
Então, nós encontramos ou discutimos dois algoritmos; um é Sutherland-Hodgeman, um é Weiler-Atherton. Sutherland Hodgeman é mais simples mas tem uso restritivo. É aplicável quando possuímos um polígono convexo que é recortado contra uma janela retangular. Considerando que Weiler-Atherton é mais genérico é aplicável para qualquer área de preenchimento, área de preenchimento poligonal, côncavo ou convexo contra qualquer janela de clipping poligonal.
Por isso, até agora discutimos clipping em 2D. Por isso, aprendemos como cortar uma linha de ponto e preencher área. Agora vamos tentar entender clipping em 3D, porque aqui nosso foco principal é o pipeline gráfico 3D. Então, vamos tentar entender clipping em 3D que é essencialmente extensão das ideias que já discutimos que é recorte em 2D. Vejamos como essas extensões são feitas.
Só coisa que temos que ter em mente é que aqui estamos falando de recorte contra o volume de visualização normalizado que geralmente é um simétrico fofo com cada coordenada na faixa menos 1 1 nas direções de 3 segundos. Esse é um volume de visualização normalizado que supomos enquanto desenvolvemos o ou realizando o recorte. Agora, Cohen-Sutherland podemos estender a versão básica 2D para 3D com alguma modificação.
Recorte de ponto também, podemos estender, por isso, vamos primeiro falar sobre recorte de ponto. Aqui verificamos por x, y e z mais cedo estamos verificando apenas para x e y se esses valores estão dentro do intervalo do volume canônico. Se é assim, então o ponto é para ser mantido. Caso contrário, é para ser recortado.
Em caso de algoritmo de recorte de linha Cohen Sutherland, ele pode ser facilmente estendido para o recorte 3D. No entanto, com algumas modificações, a ideia central permanece a mesma. Ou seja, dividimos o espaço de coordenadas de coordenadas em regiões. Agora, antes tínhamos 9 regiões. Agora já que estamos lidando com 3D temos 27 regiões, 3 vezes. Agora já que temos 27 regiões. Então, cada região precisa ser representada com 6 bits. Cada um pouco para os 6 aviões que definem o volume de visualização canônica. Longe, perto, de cima, de baixo, direita, esquerda isso está em contraste com os 4 bits anteriores usados para denotar os 4 lados da janela.
Agora para cada avião, temos essas 9 regiões definidas para que haja 9 regiões atrás do plano distante. Há 9 regiões entre quase e de longe avião e há 9 regiões em frente ao plano próximo. Juntas há 27 regiões e cada região é representada com este código de 6 bit, onde o bit 6 representa a região distante, bit 5 é a região próxima, bit 4 é a região superior, bit 3 é a região inferior, bit 2 representa a região direita e bit 1 representa a região esquerda. A ideia permanece a mesma com 2D apenas o tamanho muda porque agora estamos lidando com 3D. Os outros passos permaneceram os mesmos.
Agora, vamos tentar entender a extensão dos algoritmos para o recorte de área de preenchimento. Então, aqui o que fazemos. Verificamos, primeiramente, se o volume de arredondamento do poliedro que é a área de preenchimento está fora do volume de visualização simplesmente comparando seus valores de coordenadas máxima e mínima em cada uma das direções x, y e y. Se o volume de aterramento estiver fora então nós o clivamos para fora e inteiramente. Caso contrário aplicamos a extensão 3D do algoritmo de Sutherland Hodgeman para recorte.
Aqui também a ideia central do algoritmo 3D Sutherland Hodgeman permanece a mesma com a versão 2D com duas diferenças principais. Quais são essas diferenças?
Um poliedro é composto de superfícies poligonais. Então, aqui nós tiramos uma superfície de cada vez para realizar clipping. Mais cedo o que estávamos fazendo, pegamos uma linha de cada vez. Aqui estamos tomando uma superfície de cada vez. Agora, geralmente polígonos divididos em malhas triangulares e há algoritmos a fazê-lo a que se possa referir no material de referência no final desta palestra. Assim, usando esses algoritmos, podemos dividir um polígono em uma malha triangular e, em seguida, cada triângulo é processado de cada vez.
E a segunda diferença é que, em vez dos 4 clippers que tínhamos anteriormente, agora temos 6 clippers. Que correspondem às 6 superfícies balizantes do volume de visualização normalizada que é um cubo. Sendo assim, essas são as diferenças entre a versão 2D do algoritmo e a versão 3D que mais cedo estamos considerando linha em um momento para recorte. Agora estamos considerando uma superfície de cada vez. Agora essas superfícies são superfícies poligonais e podemos converter essas superfícies em malhas triangulares.
E então realizamos clipping para cada triângulo em um momento que é uma diferença. Outra diferença é anterior estamos lidando com 4 clippers, agora temos 6 clippers representando os 6 aviões de bounding do volume de visualização que é um cubo. Assim, é em resumo as principais diferenças entre o recorte 2D e o recorte 3D. As ideias principais permanecem as mesmas algumas pequenas mudanças estão aí. Então, com isso chegamos ao fim da nossa discussão sobre clipping.
E nosso próximo tópico será a remoção de superfície oculta. Então, aqui poucas coisas omitidas durante a discussão. Por exemplo a criação de malha triangular a partir de determinado polígono. Por isso, para esses detalhes você pode se referir ao material que será mencionado no próximo slide.
Então, o que quer que eu tenha coberto hoje pode ser encontrado neste livro. Você pode passar pelo capítulo 7, seção 7.1.3, 7.1.4 e seção 7,2. Para os tópicos que eu cobri no entanto fora deste tópicos também há poucas coisas interessantes que eu não discuti mas você pode encontrar isso no livro. Então, você pode gostar de passar por esses materiais também. Isso é tudo para hoje. Obrigado e adeus.