Loading
Nota de Estudos
Study Reminders
Support
Text Version

Métodos De Representação Espacial

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 a palestra número 9 no curso Computer Graphics. Estamos discutindo as etapas do pipeline gráfico. Como você pode se lembrar, há 5 estágios amplos, a primeiríssima etapa é a representação de objetos, e estamos discutindo atualmente sobre a técnica de representação de objetos.
Então, esse será o tema da nossa discussão hoje, os métodos de particionamento espacial.
Agora, quando falamos de particionamento espacial, a que nos referimos? Como o nome sugere, o particionamento espacial refere-se à representação de um objeto em termos do espaço 3D que ele ocupa. O espaço é definido por seus limites e nós representamos o espaço ou o volume que se encontra enalado pelos limites em vez dos limites, que vimos nas palestras anteriores.
Agora, há um conceito importante em técnicas de particionamento espacial, isto é chamado de voxels. Você já ouviu falar de pixels, mencionamos este termo anteriormente. Esta é a menor unidade de exibição. E em uma tela de exibição, assumimos que há uma grade de pixels. Da mesma forma, o voxel é basicamente a contrapartida 3D do conceito de pixel. O Voxel é a menor unidade de representação em um espaço 3D. Qualquer espaço 3D pode ser assumido para estar tendo uma grade de voxel.
Como uma grade de pixels, podemos criar ou assumir que uma grade de voxel existe para representar um espaço 3D. Por isso, a grade do pixel é para o espaço 2D, a grade de voxel é para o espaço 3D. E o voxel, como talvez óbvio, é a maneira mais simples de representar objetos 3D.
Agora, quando falamos de voxels, estamos essencialmente nos referindo a cubos de tamanho tipicamente uniformes ou paralelepípedos. Por isso, essencialmente, uma grade de cubos de tamanho uniforme ou paralelepípedos que são a nossa grade de voxel. Agora, em cada grade, cada elemento voxel da grade geralmente carrega várias informações. Quais são essas informações? A intensidade nessa região específica de 3D, a temperatura dessa região e assim por diante. E essas informações realmente ajudam a descrever com exclusividade a cena 3D. Assim, essencialmente os voxels estão tendo atributos que são informações características para o objeto em particular no local.
Usando voxels, podemos realmente aplicar várias técnicas para representar objetos. Uma dessas técnica é o método Octree. O que é esse método? Como o nome sugere, é espécie de representação de árvores, agora vamos tentar entender o que é essa árvore. Então, essencialmente ele se refere a um método para criar uma grade de voxel, mas na forma de uma árvore.
Por isso, neste método, a entrada é uma região 3D. Agora, dividimos esse espaço de entrada em 8 sub regiões e, em seguida, cada sub região por sua vez é novamente dividida em 8 sub regiões sub sub. Então, essencialmente este é um passo recursivo e essa recursividade continua até chegarmos a algum tamanho uniforme do preset das sub regiões. Agora, esse tamanho pode ser usuário definido, por exemplo, um cubo de unidade. Por isso, quando vemos que nossa divisão leva a regiões de tamanho de cubo da unidade, então paramos por aí, um exemplo é mostrado nesta figura da direita.
Então, esta é a nossa região inicial de 3D. Agora, como você pode ver, criamos 8 sub regiões daqui, isto é 1, 2, 3, 4, 5, 6, 7 e 8, então cada uma dessas sub regiões são mais divididas em 8 sub regiões como aqui como você pode ver nessa divisão, novamente existem 8 sub regiões 1, 2, 3, 4, 5, 6, 7, 8. Da mesma forma, aqui também, nós dividimos e todas as outras sub regiões também podemos dividir.
Agora, qual é a saída dessa recursividade? Isso cria uma árvore. Então, nós temos um nó raiz. Para cada nó raiz, criamos 8 nós filho daqui para cá. Agora para cada nó filho, novamente estamos criando 8 nós filho e esse processo continua. Então, essencialmente isso leva a uma árvore. Uma vez que cada nó tem 8 filhos, chamamos de ocárvore e os nós de folhas desta árvore representam o espaço 3D. Assim, todos os nós intermediários são representações intermediárias, eles não representam o objeto final, no nível da folha o objeto final é representado. Lembre aqui que junto com o espaço os atributos ou as informações características também são armazenados no nível do nó da folha.
Assim, para representar objetos diferentes, podemos associar propriedades exclusivas a esses nós de folhas ou voxels, as propriedades como cor, densidade, temperatura e etc., essa é a ideia básica. Então, nos é dado espaço 3D, o espaço que dividimos em 8 regiões e continuamos essa divisão, cada sub região é dividida ainda mais em 8 sub regiões e assim por diante. Nós continuamos essa divisão de maneira recursiva até chegarmos ao nível de voxel ou aos cubos de tamanho uniforme. E esse processo cria uma árvore; cada nó desta árvore tem 8 filhos, portanto, a árvore é chamada de ocárvore.
O nível de folha contém os voxels são representação do objeto 3D e as informações características como cor, densidade, temperatura e assim por diante estão associadas a cada voxel nesta árvore para identificar com exclusividade objetos. O octree é um dos vários métodos onde o espaço é usado para representar os objetos. Outro método popular é chamado de BSP ou o método BSP.
Agora, a BSP defende particionamento de espaço binário e o método é método de particionamento de espaço binário. Então, o que ele faz? No octree, fizemos algum particionamento recursal do espaço. Na árvore BSP, seguimos a recursividade semelhante que é a gente recebe um espaço nós dividimos em subespaço e depois dividimos o subespaço novamente e continuamos até que alguma condição seja atendida.
No entanto, em vez de dividir um espaço em 8 subespaços como temos feito no caso de ocárvore, aqui o que fazemos dividimos em 2 espaços ou subespaços em cada etapa recursiva. Por isso, em caso de ocárvore estamos dividindo a região em 8 sub regiões, em caso de árvore BSP estamos dividindo a região em 2 sub regiões, é por isso que se chama particionamento espacial binário. Agora, como se dividem? Usamos aviões. Por isso, nos é dada uma região que assumimos que os aviões estão disponíveis para dividir a região em sub regiões. Mas esses aviões não precisam ser paralelos aos aviões formados pelos axes XY, YZ ou ZX. Podem ser aviões de qualquer orientação. É claro que, se estamos tendo paralelo aos aviões formados pelo eixo principal então é mais fácil de implementar, caso contrário, temos que fazer cálculos adicionais.
Vejamos um exemplo. Suponhamos que nos seja dada essa região de 3D e vamos representá-la na forma de uma árvore BSP. Então, nosso nó raiz é todo o objeto, então utilizamos um avião este para dividá-lo em duas regiões, a região esquerda D e a região direita C. Esquerda com respeito ao avião e à direita com relação ao avião, esquerda sub região e sub-região direita. Depois, utilizamos outro avião aqui para dividir B em duas sub regiões D e E. Então, então, eventualmente, o que conseguimos? O objeto é representado em termos de três sub regiões D, E e C.
Então, esses três no nível da folha representam o objeto. E novamente como em caso de ocárvore, podemos associar propriedades únicas a cada uma dessas sub regiões para identificar com exclusividade o objeto. Agora, aqui utilizamos dois aviões que são ortogonais uns para os outros, são aviões ortogonais, mas isso é, como já vimos anteriormente, que não é uma exigência estrita. Os aviões de qualquer orientação podem ser usados para dividir as regiões em duas sub regiões.
Então, aqui em vez desses aviões ortogonais, poderíamos ter usado qualquer avião de qualquer orientação para dividi-lo em duas regiões, duas sub regiões que é a formulação mais geral para a criação de árvore BSP. Mas, como eu disse, se estamos usando aviões que não são paralelos aos aviões formados pelo eixo principal, então cálculos adicionais podem ser necessários para processar a representação. Vejamos mais um exemplo para a criação de árvores BSP, como podemos criar, como podemos escrever um algoritmo para criação de uma representação.
Considere esta figura, aqui queremos representar este círculo, este é naturalmente uma figura bidimensional, não é um objeto 3D, mas este objeto 2D queremos representar este círculo que está a ter o centro em Pm e raio r. Então, nós queremos representá-lo usando árvore BSP.
Como podemos fazer isso? Por isso, leva como entrada a região circundante R que é a praça representada pelos quatro vértices ou os pontos de esquina P 1, P 2, P 3 e P 4 e o círculo fica dentro desta região. Por isso, quando estamos representando o círculo, estamos essencialmente representando essa região com algumas regiões que fazem parte do círculo ter características únicas do círculo. Como podemos fazer isso?
Assim, partiremos a região em 4 sub regiões. Então, primeiro dividimos em 2 sub regiões, então cada uma dessas 2 sub regiões dividimos em mais 2 sub regiões e assim por diante. Por isso, só pela simplicidade estamos combinando esses passos juntos aqui e informando que estamos dividindo-a em 4 sub regiões. E aqui estamos usando linhas paralelas aos machados.
Usando essa ideia, o que podemos fazer? Podemos escrever um algoritmo para uma função criar para BSP onde R é a região de entrada. Agora, usaremos o R para criar um nó, então a partir de R criará 4 regiões unindo os pontos midpoints das laterais da praça, isto é o mesmo que aplicar as técnicas de particionamento espaçadas binárias em múltiplos passos. Como neste caso, nós primeiro criamos 2, depois para cada um desses dois criar mais dois e estamos realmente combinando esses passos aqui nessa linha.
Agora, para cada uma dessas sub regiões aqui neste nódulo de folha dessa figura, se o tamanho dessa sub região, suponhamos que esta região esteja dividida em 4 sub regiões, portanto, estamos considerando isso. Agora, se o tamanho da sub região for um quadrado unitário, onde estamos supondo que um pixel seja representado como um quadrado unitário. Em seguida, vamos para o próximo passo que é se a distância entre os centros da região original R e a sub região que estamos considerando atualmente é menor ou igual ao raio do círculo, então essa sub região faz parte do círculo.
Então, nós adicionamos como um nó folha a árvore BSP e marcamos como 'dentro'. Caso contrário, marcamos como 'fora', apesar de adicioná-lo como parte da árvore BSP. Agora, se o tamanho não for quadrado de unidade, ou seja, não atingimos a condição de rescisão de recursão. Assim, para cada nó executamos a função novamente, ou seja, chamamos a função novamente recursivamente mencionada nestes 2 passos. Assim, no final dele conseguimos uma árvore, onde os nós de folhas representam a região de delimitarmos, a região original dividida em sub regiões.
Agora, algumas dessas sub regiões estão marcadas como dentro deste objeto em particular, dentro da praça. Enquanto que, outros são marcados como fora. Então, a partir daquela árvore, obtemos uma representação da praça. Até agora tão bom. Agora, qual é o problema? Existe algum problema com essa abordagem de particionamento espacial?
Um problema pode ser muito óbvio para você até agora, ou seja, exigimos memória grande para armazenar essas informações da grade do voxel. Então, estamos criando árvore em que os nós de folhas representam a grade e se estamos particionando uniformemente, então haverá grande número de voxels e exigimos quantidade significativa de espaço de memória para armazenar as informações do voxel. O problema vem porque estamos dividindo espaço em voxels de tamanho uniforme independentemente das propriedades espaciais.
Como vimos no exemplo anterior, a região R é uma grande região, dentro disso, o círculo ocupa uma pequena área, mas estamos dividindo a região em sub-regiões de tamanho uniforme e muitas sub regiões podem estar fora do círculo. Por isso, se você quer representar o círculo, não é necessário representar aquelas regiões que estão fora do círculo que realmente desperdiça algum espaço de memória. Então, se nós temos algum método para evitar essas desperdícios, então é claro que isso seria útil.
Então, o que nós queremos? Se uma determinada região no espaço tem as mesmas propriedades em todos os lugares, então idealmente não devemos dividê-la mais adiante. Porque mesmo que dividamos o que obtemos, vamos obter a mesma propriedade. Em vez disso, o que fazemos, ainda dividimos em voxels, embora cada voxel contenha os mesmos atributos, pois a região mais ampla ou a região mais ampla no espaço tem a mesma propriedade em todos os lugares.
Então, nós podemos realmente salvar, isto é que existe um erro de digitação aqui, é seguro, podemos salvar a memória usando esta ideia de particionamento não uniforme. Por isso, mais cedo estamos falando de particionar uma região em voxels de tamanho uniforme. Agora, estamos falando de partidarização espacial de tamanho não uniforme. O que é isso? Ou seja, em vez de usar muitos voxels para representar uma região homogênea que é uma região onde a propriedade é mesma em todos os lugares utilizamos uma única unidade. Por isso, não dividimos mais essa região, em vez disso toda a região é representada como uma única unidade.
Como podemos fazer isso? Uma forma é modificar o método de ocárvore. Agora, mais cedo estávamos a ter fixado 8 crianças para cada nó porque estávamos dividindo a região em 8 sub regiões independentemente da propriedade da região. Agora, o que podemos fazer? Ou dividimos ou não dividimos. Então, se uma sub-região está tendo mesmo imóvel em todos os lugares, então nós não a dividimos. Assim, esse nó não terá nenhum filho ou 0 filhos. Mas se não for o caso, então dividimos em 8 sub regiões ou 8 crianças.
Por isso, agora, no método de ocárvore revisado, o que teremos 0 ou 8 crianças para cada nódulo, o que não foi o caso anteriormente. Então, mais cedo estávamos recebendo 8 crianças para cada nó, nó intermediário, agora teremos 0 ou 8 crianças para cada nó intermediário dependendo da propriedade desse espaço representado pelo nó.
O procedimento de recursão, é claro, permanecerá, o procedimento de recursão permanecerá o mesmo. Mas a cada passo da recursão, verificaremos se atributos de um espaço é mesmo em todos os lugares. Se for esse o caso, então não o dividimos mais. Então, nós não vamos para a divisão recursiva novamente para aquela região em particular.
A representação da BSP também sofre com o mesmo problema se vamos para partidarização uniforme.
E, para evitar isso, podemos ir por um método revisado ou um método refinado onde podemos dividir região em 2 sub regiões se as sub regiões estão tendo propriedades diferentes em locais diferentes ou não dividimos. Assim, os nós intermediários terão 0 ou 2 crianças semelhantes ao método de ocárvore revisado. Então, o que nós aprendemos é que a unidade básica de representação será voxel. Agora, usando o voxel podemos dividir um determinado espaço 3D para representar o objeto contido naquele espaço de duas maneiras, uma é divisão uniforme.
Agora, quando vamos para uma divisão uniforme, obteremos um determinado tipo de árvore se seguirmos o método de ocárvore ou um determinado tipo de árvore se seguirmos o método BSP. No método octree, se vamos para uma divisão uniforme, então teremos 8 filhos para cada nódulo. No método BSP, obteremos dois filhos para cada nódulo. Agora, se a região que estamos dividindo está tendo o mesmo atributo ou mesmo propriedades em todos os lugares então será desperdício de memória dividir essa região em sub regiões e armazenar as informações.
Em vez disso, não precisamos dividê-lo mais adiante. Assim, no caso do método octree, modificamos-o para particionamento não uniforme impondo o fato de que um nó pode ter 0 ou 8 filhos. Da mesma forma, em um método de BSP revisado, podemos modificar impondo o fato de que cada nó intermediário pode ter 0 ou 2 filhos.
Há um outro método de particionamento espacial conhecido como CSG. O que significa?
Apresenta-se para Geometria Sólida Construtiva. Então, esse é outro método para representação espacial de objetos. Agora, em caso de ocárvore ou BSP o que temos visto? Vimos que essas representações se baseiam em divisão do espaço. Então, nos é dado um espaço e estamos dividindo-o em subsPaces. Em comparação a isso, em caso de CSG o que temos? Na verdade é baseado em unir espaços, justamente o oposto do que fazemos em BSP ou métodos ocárvores. Por isso, em caso de CSG contamos com a junção de espaços para representar objetos. Vamos tentar entender isso com respeito a um exemplo.
Considere este objeto, este parece bem complexo. No entanto, quando estamos usando CSG ou método de geometria sólida construtiva, podemos representá-lo como uma união de algumas outras formas. Então, nós começamos aqui neste nível, aqui temos essa forma, essa forma, essa forma e essa forma, então 4 formas estão lá. Agora, combinamos essas 2 formas para obter uma forma e combinamos essas 2 formas aqui para obter essa forma. Agora, essas 2 formas são então mais combinadas para obter essa forma geral.
Então, aqui começamos com conjunto de formas primitivas ou formas básicas, então aplicamos um conjunto de operadores booleanos a saber: união, interseção, diferença etc. que são definidas sobre esse conjunto de formas primitivas para obter formas mais recentes. Como aqui nessas 2 formas, aplicamos um operador booleano para obter uma nova forma e esse processo continua até que obtemos a forma desejada aqui. Assim, as operadoras podem ser aplicadas hierarquicamente. Assim, a partir deste nível atingimos a este nível, a partir deste nível que atingimos para este nível, a cada nível aplicamos os operadores booleanos.
Portanto, essa é uma aplicação hierárquica das operadoras. Por isso, em outras palavras, temos um conjunto de formas primitivas definidas e um conjunto de operadores booleanos sobre essas formas também definidas. Agora, aplicamos aquelas operadoras nas formas para obter novas formas e aplicamos aquelas operadoras hierarquicamente até obtermos a forma desejada, até que somos capazes de representar a forma desejada. Então, qual é a representação? A representação é essencialmente as formas primitivas e as operadoras booleanas aplicadas de maneira hierárquica, portanto, essa é a representação.
Então, isso é em síntese, o que esta geometria sólida construtiva é tudo sobre. Agora, vamos resumir o que aprendemos até agora.
Hoje e em poucas palestras já aprendemos várias técnicas de representação, que é a primeira etapa do pipeline. A apresentação de limite incluindo splines, representação espacial e também obteve visão geral de outras representações. Agora, há muitas técnicas como vimos até agora. Uma questão é qual técnica usar e quando? Essa é uma questão que sempre confronta um desenvolvedor de sistema gráfico. Qual técnica deve ser usada e em qual situação? O que orienta esse processo de tomada de decisão?
Agora, podemos desejar ter representação mais realista. Claramente, as técnicas avançadas seriam úteis mas técnicas avançadas, como os sistemas de partículas, podem nem sempre ser possíveis porque requerem muitos recursos computacionais que podem não estar disponíveis em todos os sistemas gráficos. Então, cada técnica vem com um custo e há um tradeado, que técnica para usar em qual situação.
Agora, esse custo pode ser de exigência computacional ou de armazenamento ou ambos e dependendo do recurso disponível, temos que tomar a decisão. Se estamos a ter muito menos recurso então não podemos pensar em técnicas avançadas de modelagem, então talvez tenhamos de perder algum realismo e ter de se contentar com algumas cenas ou imagens menos realistas.
Por exemplo, suponhamos que queremos representar as linhas costeiras em uma cena. Então, o que é desejável? As linhas costeiras são estruturas tipicamente auto-repetições e a representação fractal é muito boa para tais formas. Então, nós, idealmente, devemos usar representação fractal para ter uma costa realista exibida. Mas pode não ser possível se estamos considerando uma plataforma móvel com processador de armazenamento limitado e bateria porque a representação fractal tem custo computacional adicional que pode não ser suportado em dispositivos móveis de baixa final.
Então, nesse caso, podemos ter que usar algum método mais simples. Então, nós estamos perdendo aqui alguma coisa, o efeito realista, mas ganhamos algo que é uma aproximação de trabalho. Então, tais trade-offs são muito parte do processo de tomada de decisão, equilibrando essas trade-offs.
Outra consideração talvez alivia de manipulação. Por isso, quando estamos criando animação, essa consideração vem a calhar e ela se torna importante. Agora, como dissemos que cada representação tem seus próprios métodos, algoritmos próprios, processo próprio. Os estágios subsequentes do pipeline precisam processar essas representações para realizar as operações que fazem parte das etapas subsequentes. Então, isso requer manipulação das representações.
Agora, se requer muito tempo para manipular, por exemplo, girar um objeto, deslocar 10 objetos horizontalmente ou verticalmente, fazer escala para cima ou para baixo um objeto ou clip, projetar ou executar melhor na remoção de superfície, etc. estes fazem parte de outras etapas do pipeline. Discutiremos sobre as etapas em detalhes mais tarde. Agora, se for necessário muito tempo para realizar essas operações, para objetos que são representados de uma maneira particular, a qualidade da animação pode ser reduzida. Então, nesses casos, devemos procurar por tipos mais simples.
Então, essa é outra consideração que deve ser mantida em mente enquanto escolhe um determinado modelo de representação que é facilidade de manipulação. Assim, se estamos a ter dispositivos de baixa final, sistemas gráficos de baixa final, então não é aconselhável ir para técnicas avançadas de representação que requerem muitas manipulações depois, sobretudo no contexto da animação.
Terceira consideração é facilidade de aquisição de dados. Por exemplo, a representação de lista de vértice para uma superfície curvada usando uma malha requer que grande número de vértices seja especificado. Agora, consideramos representação esplina. Nesse caso, exigimos menos pontos de controle para representar a mesma curva. Por isso, claramente aqui, representar uma curva usando mesh envolve mais esforço para aquisição de dados, enquanto que representar a mesma curva com uma spline envolve menos esforço para adquirir dados. Então, às vezes essa facilidade de adquirir dados pode ser um fator decisivo. Dependendo do designer do sistema gráfico, um método particular pode estar escolhendo onde os dados podem ser adquiridos facilmente.
Por isso, há vários trade-offs que temos que equilibrar e temos que decidir quais são esses recursos de trade-offs disponíveis, natureza das interações, recursos em termos de plataforma de computação, natureza da interação em termos de nosso nível de conforto com o fornecimento de grande quantidade de dados e também efeito, se queremos um efeito muito realista ou estamos buscando alguma aproximação considerando a falta de recursos.
Então, dependendo dessas amplas considerações de 3 minutos, temos que escolher uma técnica de modelagem particular. Por isso, com isso, chegamos ao fim da nossa discussão sobre a primeira etapa do pipeline gráfico que é a representação de objetos.