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 25 no curso Computer Graphics. Estamos discutindo atualmente o pipeline gráfico 3D que consiste em cinco estágios. Vamos recapitear rapidamente as etapas.
Como você pode ver nessa figura, primeiro estágio é representação de objetos, então temos transformação de modelagem, depois iluminação ou a coloração de objetos, então visualizando pipeline, e o quinto estágio é de conversão de varredura. Entre eles, já discutimos as quatro primeiras etapas a saber, representação de objetos, transformação de modelagem, iluminação e o pipeline de visualização.
Agora vamos discutir a quinta etapa que está renderizando ou também conhecida como conversão de varredura. Então, de que é que se trata esta etapa?
Vamos ter uma olhada no problema muito básico que tentamos abordar nesta quinta etapa.
Até o momento, o que quer que tenhamos aprendido que nos dá alguma ideia de uma coisa em particular. Através dessas quatro etapas que discutimos até o momento, podemos transformar uma cena 3D em uma descrição de viewport 2D, que está no sistema de coordenadas do dispositivo. Basta ter rapidamente uma reveja em como é feito como aprendemos em nossas discussões anteriores.
Então, primeiro, temos uma cena de 3D dizer, por exemplo, esse cubo. Agora, esse cubo é definido em seu próprio sistema de coordenadas ou coordenadoria local, o que fazemos na primeira etapa que é a representação de objetos. Depois o que fazemos, transferimos para um sistema de coordenadas mundial através da transformação de modelagem.
Por isso, o objeto está agora em coordenadoria mundial. Portanto, este é o estágio um. E na segunda etapa através da transformação de modelagem, transferimos para a descrição de coordenadoria mundial que é o estágio dois.
Em seguida, atribuímos cores usando a iluminação, modelos de sombreamento. Por isso, colorimos o objeto em stage-3 e depois disso, executamos a transformação de visualização, que é o estágio quatro no qual transferimos para uma descrição de viewport. Assim, envolve primeiro, transferindo o mundo coordenadas para um sistema de coordenadas de visualização, então a partir da coordenada de visualização, realizamos projetos e transformação e transferimos-o para visualizar plano, então, a partir de plano de visualização, executamos uma janela para visualizar mapeamento para transferi-lo para este viewport, que está no sistema de coordenadas do dispositivo.
Por isso, essas três transformações acontecem no palco quatro junto com, é claro, recorte e remoção de superfície oculta. E depois disso o que obtemos é uma representação 2D do objeto ou cena em um viewport, que está no sistema de coordenadas do dispositivo. É assim que as coisas são transformadas da definição de objeto para a descrição do viewport.
No entanto, o sistema de coordenadas de dispositivos de que estamos falando é um sistema contínuo que significa que os valores de coordenadas de qualquer ponto podem ser qualquer número real. Assim, podemos ter coordenações como 2, 3, que são números inteiros, enquanto que, também podemos ter uma coordenada como 2,5, 3,1, que são números reais. Assim, todos os tipos de coordenadas são permitidos em sistema de coordenadas de dispositivos.
Em contraste, quando na verdade estamos tentando exibirá-lo em uma tela, temos uma grade de pixels que significa que é um sistema de coordenadas discretas. Assim, todas as coordenadas possíveis não são permitidas, em vez disso, devemos ter algo onde apenas as coordenadas de número inteiro são definidas. Sendo assim, o que quisermos exibir na grade do pixel deve ser exibido em termos de coordenadas inteiro, não podemos ter valores de coordenadas reais.
Assim o que precisamos? Precisamos mapear a partir da descrição do viewport, que é um espaço de coordenadas contínuas a uma grade de pixels, que é um espaço de coordenadas discretas. Portanto, este é o mapeamento final que precisamos fazer antes que uma cena seja renderizada em uma tela de exibição física. Agora, esses algoritmos de mapeamento ou as técnicas que usamos para o mapeamento são coletivamente conhecidos como renderização ou mais popularmente, eles são chamados de conversão de varredura ou em algum momento de rasterização já que estamos lidando principalmente com dispositivos de varredura raster. Por isso, todos esses três termos são usados, renderização, conversão de varredura ou rasterização.
Então, qual pode ser a abordagem direta para fazer isso? Você pode achar que é bem simples. O que podemos fazer é simplesmente arredondar as coordenadas reais para as coordenadas de número inteiro mais próximo. Por exemplo, se temos um valor de coordenada como (2,3, 2,6), podemos arredoná-lo até (2, 3) que é os valores de coordenadas inteiro mais próximo.
No entanto, isso pode ser bom para converter pontos ou mapear pontos de espaço de coordenadas contínuas para espaço de coordenadas discretas, no entanto, o mesmo esquema pode não ser bom para linhas, círculos ou outras formas primitivas que são necessárias para renderização de uma cena. Agora, vamos tentar entender como então podemos cuidar da conversão de escaneamento de linhas, círculos ou outras formas primitivas.
Comecemos com a conversão de varredura de linha, como podemos basicamente mapear uma linha definida em um espaço de coordenadas contínuas para uma linha definida em um espaço de coordenadas discretas.
Começaremos com uma abordagem muito simples e intuitiva e então, tentaremos entender o problema com a abordagem intuitiva e, em seguida, introduziremos melhores e melhores abordagens. Agora, todos nós sabemos que podemos definir um segmento iluminado em termos de seus terminais. Então, para escanear converter, o que precisamos? Precisamos primeiro mapear os pontos finais na linha para os pixels apropriados e também os outros pontos que estão na linha para os pixels apropriados.
Agora, vamos passar por uma abordagem bem simples, como podemos mapear os pontos que estão na linha até os pixels mais próximos na grade do pixel.
Assim, podemos seguir uma abordagem de quatro passos. Na primeira etapa, mapeamos os pontos finais para pixels simplesmente arredondando para o inteiro mais próximo. Dessa forma, obtemos os pixels de início e final para o segmento de linha. Por isso, agora sabemos quais pixels estão definindo a linha. Em seguida, na segunda etapa, tiramos um terminal tendo os valores menores x e y como ponto de partida. Na terceira etapa, trabalhamos o valor y para os valores x sucessivos.
Agora, já que estamos lidando com uma grade de pixels, sabemos que pixels são separados por distâncias unitárias. Assim, os valores x sucessivos terão uma diferença de valor de 1, portanto esses valores sucessivos vão diferir em 1. Na quarta etapa, esses valores de y computados são mapeados para o inteiro mais próximo dando-nos as coordenadas pixel desse ponto específico.
Então nós primeiro convertemos os pontos finais para os pixels mais próximos, depois escolhemos o ponto final tendo valores menores x e y como ponto de partida, e começando com esse ponto, computamos valor de y tomando como entrada o valor x, em que os valores x sucessivos diferem em 1 e continuamos isso até o outro terminal. Por isso, computamos todos os valores y entre os pixels iniciantes e finais. E esses valores de y computados são então mapeados para os valores inteiros mais próximos, dando-nos as coordenadas do pixel para esses pontos. Vamos tentar entender isso em termos de um exemplo.
Suponha que este seja o nosso segmento de linha, como mostra esta figura. Portanto, este é um terminal, este é outro terminal. Inicialmente, a linha foi definida por esses dois terminais, A e B. Como você pode ver, ambos são números reais. Por isso, temos que mapeá-lo para o pixel mais próximo.
Para A, se fizermos o arredondamento fora, obteremos este pixel como o pixel mais próximo, e para B obteremos este como o pixel mais próximo se executamos o arredondamento. Agora, podemos ver que as coordenadas de A 'é menor que B'. Por isso, começamos com A ', escolhemos como nosso pixel inicial. Por isso, começamos com esse pixel e continuamos descobrando os valores y até chegarmos a este outro pixel, outro terminal.
Agora, nosso objetivo é computar os valores y para os valores x sucessivos. Para isso, exigimos a equação de linha que envolve cálculo da inclinação m, que no nosso caso acaba por ser esta.
Pois sabemos os dois terminais podemos computar a ladeira e também, o valor de interceptação. Estamos assumindo aqui que a linha é expressa em termos dessa equação, y = mx + b, onde m é a inclinação, e b é o y-intercept. Considerando os dois terminais, podemos resolver por m e b e achar que m é 3 por 5 e b é 4 por 5.
Então o que fazemos? Para cada x separado por distância de unidade, a partir do pixel de ponta inferior que é x valor é 2, computamos os valores y usando a equação da linha até chegarmos ao outro terminal. E a equação de linha é dada aqui. Por isso, nesta equação, usamos os valores x para obter os valores y.
Se o fizermos, o que vamos encontrar? Então, para x =2, temos y= 2; quando x é 3, portanto, o próximo pixel, x coordenada, ficamos y é 2,6; quando x é 4, então ficamos y a ser 3,2; x= 5, y=3.8; x= 6, y=4.4. Assim, obtemos os quatro pixels intermediários e valores de y correspondentes computados usando as equações de linha.
Assim, os quatro pontos são (3, 2,6), (4, 3,2), (5, 3,8) e (6, 4,4). Estes são os quatro valores que computamos usando a equação da linha. Agora, mapeamos esses valores y como mostrado aqui para o inteiro mais próximo para obter os locais do pixel. Assim, se fizermos o arredondamento fora, obteremos os quatro pixels a serem (3, 3) que está aqui; depois (4, 3), que está aqui; (5, 4) aqui e (6, 4) aqui. Portanto, estes são os nossos quatro pixels intermediários correspondentes aos pontos da linha.
Agora, com essa abordagem, como você pode ver, a forma como nós computamos os valores e afinal descobriu os pixels, há dois problemas amplamente. Primeiro problema é a necessidade de realizar a multiplicação de m e x. Agora, m é provável que seja um valor real, então isso é uma operação de ponto flutuante. Em segundo lugar, precisamos arredondar os valores de coordenadoria y que também é operação ponto flutuante. Juntas essas operações de ponto flutuante são intensivas de computação.
Por isso, temos uma abordagem computacionalmente cara para converter uma linha em pixels correspondentes. Na realidade, precisamos escanear converter muito grande número de linhas dentro de um tempo muito pequeno. Agora, se temos operações de ponto flutuante envolvidas, então esse processo se tornará lento e perceberemos os piscinas, o que é naturalmente algo que não queremos. Então, do que precisamos, precisamos de algumas soluções melhores. Vejamos uma abordagem um pouco melhor.
Mas antes disso, gostaria de apontar sua atenção para um outro tópico importante que é a consideração de inclinação de uma linha quando estamos realizando essa conversão de varredura.
No nosso exemplo, o que fizemos, calculamos os valores de coordenada y para cada valor de coordenada x. Então aumentamos x em 1 e correspondentes y valores, calculamos usando a equação de linha. Você pode se perguntar por que nós fizemos isso, nós poderíamos ter feito de forma semelhante ao contrário. Poderíamos ter aumentado y e calculado os valores x. Vamos tentar ver o que acontece se fizermos isso se calcularmos x valores aumentando os valores y.
Agora, temos esses dois pixels de terminal e o pixel inferior é o ponto de partida indicado por A '.
Desta vez, estamos a aumentar y em 1. Isso significa que estamos a mover-nos por este caminho. Mais cedo, estávamos caminhando nesse sentido, agora estamos nos movendo desta forma de uma linha de varredura para a próxima. E então, calculamos o x baseado na equação. Agora, precisamos de uma equação modificada que se dá aqui e já conhecemos b e m, o y-intercept e slope, respectivamente. Por isso, simplesmente substituímos o valor y para obter o valor x.
Agora, se o fizermos, veremos que temos apenas dois valores y sucessivos, este e este entre y= 2 e y=5. Por isso, mais cedo, computamos quatro valores x, desta vez nós exigimos computar apenas dois valores porque temos apenas dois aumentos de y entre os terminais. Por isso, somos obrigados a calcular dois valores x. Assim, quando y= 3, então o x acaba sendo 3,7 usando a equação, e quando y= 4, x é 5,3.
Então o que computamos entre os dois pontos finais? Dois novos pontos, (3,7, 3) e (5,3, 4). Se a arredarmos para os números inteiros mais próximos, então, obtemos os pixels (4, 3) e (5, 4); deixe-nos situá-lo aqui. Portanto (4, 3) é este ponto e (5, 4) é este ponto. Note que mais cedo, conseguimos dois pontos adicionais quando nos movemos ao longo de x-direção, agora estamos recebendo apenas dois pontos, esses dois, quando estamos nos movendo ao longo de y-direção e computação x.
Claramente, o primeiro conjunto que são estes 4 mais os 2 terminais, total de 6, os pixels nos darão uma melhor aproximação à linha em comparação com o segundo conjunto composto por total de 4 pixels, os dois terminais e os dois pixels recém-computados. Assim você tem o primeiro set, que é melhor do que segundo set porque a aproximação é melhor devido ao número maior de pixels.
Agora, essa é a questão aqui. Como decidir qual a coordenada para calcular e quando? Devemos começar com x e calcular y, ou devemos aumentar y e calcular x? Agora, essa decisão é tomada com base na inclinação da linha, dependendo da ladeira a gente faz uma chamada.
Se a inclinação está dentro desses intervalos, então nós trabalhamos fora ou calculamos valores de y com base em coordenadas x dos pixels. Então você aumenta x em 1 e computa os valores y quando m está dentro deste intervalo. Se m não estiver dentro deste intervalo, então computamos x aumentando as coordenadas y. Então essa é a nossa regra. Então, quando m está dentro dos intervalos dados aqui, então nós computamos com base em x, em que x indica as coordenadas do pixel que significa inteiros. Caso contrário, isso significa que quando m não estiver dentro deste intervalo, computamos x baseado em y onde y indica as coordenadas do pixel em inteiros. Então, é assim que fazemos a decisão.
Agora, voltemos a um algoritmo de conversão de varredura de linha melhor em comparação com a abordagem simples que aprendemos anteriormente. Por isso, essa abordagem é chamada de DDA ou analisador diferencial digital.
DDA defende o analisador diferencial digital e esta é uma abordagem incremental que é desenvolvida para reduzir as operações de ponto flutuante. Isso significa aumentar a velocidade da computação, acelerar o processo de conversão de varredura.
Vamos tentar primeiro entender a ideia. Utilizaremos o mesmo exemplo que vimos anteriormente mas, desta vez, vamos notar mais alguns pontos. Por isso, mais cedo, computamos 4 pontos entre os dois pontos finais (2, 2) e (7, 5) aumentando os valores de x e computação y. Agora, estes 4 pontos são (3, 2,6), (4, 3,2), (5, 3,8) e (6, 4,4). Agora, teremos um olhar mais atento sobre esses pontos, o que eles nos dizem.
Computamos que a inclinação é de 3/5 ou 0,6. Agora, os valores de y sucessivos são, na verdade, adição deste valor de inclinação ao valor atual. O primeiro valor que conseguimos é 2,6. Segundo valor que conseguimos é 3,2, o que podemos obter adicionando 0,6 que é o valor do slope para o valor anterior que é 2,6.
O próximo valor que conseguimos é o 3,8, que é novamente o valor anterior mais a inclinação. Por fim, conseguimos 4,4, o que é novamente o valor anterior mais o declive. Portanto, há um padrão. Adicionamos o valor do slope ao valor anterior para obter o novo valor. Essa ideia é explorada neste algoritmo DDA.
Por isso, em vez de computar y com a equação da linha toda vez, podemos simplesmente adicionar m ao valor y atual. Isso significa o novo y que podemos obter adicionando m ao valor atual. Por isso, não precisamos ir para resolver a equação de linha toda vez que quisermos computar o valor y.
Qual é a vantagem disso? Elimina-se a multiplicação de ponto flutuante que está envolvida neste cálculo que é m em x. Assim, podemos eliminar esses cálculos que, por sua vez, vai reduzindo as complexidades computacionais.
Agora, como eu disse anteriormente, o slope é uma consideração importante aqui. Então, quando a inclinação não está dentro do intervalo que significa que a inclinação é maior que 1 ou menos de menos 1, então não computamos sucessivos valores de y, em vez disso computamos valores x. Novamente, de forma semelhante que é novo valor é o valor antigo mais um termo constante, que neste caso é 1/m, mais cedo era apenas m. Assim, podemos obter o novo valor x adicionando esta constante 1/m ao valor atual. E aqui também, por isso, estamos eliminando operações de ponto flutuante.
Assim, o algoritmo completo é mostrado aqui. A entrada é o terminal, os dois endpoints são a entrada. E a saída é o conjunto de todos os pixels que fazem parte da linha. Então nós computamos m. Agora, quando m está dentro dessa faixa, computamos sucessivos valores de y como mostrado aqui, adicionando m ao valor atual y, arredando-o para obter o pixel, e adicionando o pixel ao conjunto. E quando m não estiver dentro deste intervalo, computamos sucessivos valores de x adicionando 1/m ao valor atual e realizamos os mesmos passos novamente.
Por isso, continuamos em ambos os casos até o outro ponto final como você pode ver nessas condições de término do loop. Sendo assim, é assim que melhoramos na abordagem de conversão de linhas simples, explorando uma determinada propriedade que seja, podemos computar os valores sucessivos x ou y simplesmente adicionando um termo constante.
Esta é claramente alguma melhoria em relação à abordagem simples. No entanto, ainda há questões.
Com o algoritmo DDA como notamos, podemos reduzir as operações de ponto flutuante, mas apenas algumas dessas operações de ponto flutuante. Não podemos remover todos, só podemos reduzir multiplicações.
Isso ainda nos deixa com outras operações de ponto flutuante, que são adição e arredondamento. Agora, qualquer operação de ponto flutuante é computacionalmente cara e envolve recursos adicionais. Por isso, quando nós, na realidade, exigimos gerar grande número de segmentos de linha em um período de tempo muito curto, nosso objetivo ideal deve ser eliminar todas as operações de ponto flutuante por completo, em vez de eliminar poucos. Eliminar poucos, é claro, melhora a taxa de renderização geral, mas eliminar todos deve ser o nosso objetivo final.
Isso é assim, uma vez que, para os segmentos de grande linha ou grande número de segmentos de linha, essas operações de ponto flutuante podem criar problema. Particularmente, quando estamos lidando com um segmento de linhas muito grande, o arredondamento pode resultar em pixels distantes de linha real, por exemplo, considere uma linha muito grande como esta. Agora, se executamos arredondando fora então fazemos continuar recebendo pixel, tipo, algo assim. Esta realmente parece distorcida linha para os segmentos de grande linha. Para os pequenos segmentos, este pode não ser o caso, mas para os segmentos de grandes linhas, existe uma possibilidade de distorção visível, que é claro, não queremos.
Então, o que quer que tenhamos discutido hoje pode ser encontrado neste livro, Computer Graphics. Você é aconselha a passar pelo Capítulo 9 até a Seção 9.1.1 para saber em mais detalhes o que nós tenhamos discutido. Assim, o algoritmo de desenho de linha aperfeiçoado será tomado na próxima palestra. Até lá, obrigado e adeus.