Representação Gráfica em 3D

Sistemas de coordenadas 3D

Sistemas de Coordenadas em 3D existem de dois tipos: de mão direita e de mão esquerda. Visualização em 3D pode partir de dois princípios diferentes mas equivalentes:

Sistemas de Coordenadas em 3D

• Câmera móvel: Move-se a câmera (plano de projeção) no mundo. As coordenadas do mundo não se modificam;
• Mundo móvel: Move-se o mundo para que se posicione no ângulo que mais nos agrada ou permite nelhor visualização.

Estes princípios são apenas metáforas computacionais e equivalentes em termos de processamento.

Metáforas sde mobilidade e posicionamento da câmera

Transformações geométricas em 3D

As mesmas três operações fundamentais que encontramos em 2D também vamos encontrar em 3D. A diferença é trabalhamos com matrizes 4×4 no sistema de coordenadas homogêneo e, para algumas operações, temos um grau de liberdade a mais. A rotação em 3D será bem mais complexa, pois aqui temos vários graus de liberdade a mais, visto que em 2D uma rotação era na verdade uma rotação em torno de um eixo z virtual. Em 3D temos três eixos reais e podemos escolher qualquer um deles ou então um eixo arbitrário em torno do qual girar o objeto.

Translação

A translação é bastante simples e pode ser expressa pela matriz abaixo:

ou então pelas três fórmulas particulares:

1. X´= X + Tx
2. Y´= Y + Ty
3. Z´=Z + Tz

Translação 3D

Escalonamento

O escalonamento 3D pode ser realizado de forma independente nas direções dos três eixos, possibilitando que se realizem distorções de proporção do sobjetos A transformada de escala 3D é representada em coordenadas homogêneas pela matriz dada a seguir:

 

ou pelas equações:

1. X´= X * Sx
2. Y´= Y * Sy
3. Z´=Z * Sz

Quando os fatores de escala são diferentes sobre os três eixos, chamamos o escalonamento de escalonamento diferencial.

Considere:

Alto: (Sx,Sy,Sz) = (2,1,2)

Direita:(Sx,Sy,Sz) = (1,2,1)

e observe a aplicação do escalonamento na figura adiante.

Escalonamento diferencial

Rotação

A rotação simples em 3D, como já foi mencionado, pode ser executada sobre qualquer um dos três eixos.

Rotações possíveis

Para cada um dos casos, temos uma matriz de transformação em coordenadas homogêneas diferente:

 

 

 

Rotação em torno de um eixo arbitrário

Rotacionamos de um ângulo q um objeto em torno de um eixo A, que passa pelo ponto P. Para podermos realizar esta rotação é necessário calcular uma matriz de transformação em coordenadas homogêneas que integre os sete passos descritos a seguir.

Rotação em torno de eixo arbitrário A, o qual passa pelo ponto P

Passos necessários para uma rotação arbitrária

Passo 1. Translação T do sistema objeto/eixo de uma distância vetorial -D de forma que algum ponto P sobre o eixo fique sobre a origem.

Passo 2. Rotação R
x
em torno do eixo x por
θ

x
de forma a trazer o eixo A sobre o plano xy.

Passo 3. Rotação R
z
em torno do eixo z por
θ

z
de forma a alinhar o eixo A com o eixo y.

Primeiros 4 passos na rotação em torno de um eixo arbitrário em 3D

Passo 4. Rotação R
y
em torno do eixo y pelo ângulo
α
desejado original.

Passo 5. Rotação R
z
-1 em torno do eixo z por –
θ

z
de forma a desfazer (3).

Passo 6. Rotação R
x

-1
em torno do eixo x por –
θ

x
de forma a desfazer (2).

Passo 7. Translação T
-1
de uma distância D para desfazer (1).

Passos para finalizar a rotação em torno de um eixo arbitrário em 3D

Estruturas de dados para representação de objetos em computação gráfica

Visão Geral

Requisitos para Técnicas de Representação de Objetos em Computação Gráfica:

• Acesso rápido, simplicidade e economia de memória;
• Evitar ambigüidades;
• Suportar interação;
• Suportar transformações geométricas;
• Suportar operações de combinação, construção;
• Generalidade, capazes de representar qualquer tipo de objeto;
• Exatidão.

Estruturas baseadas em listas de pontos

Esta categoria de estruturas de dados 3D é dividida em modelos de arame/linhas e modelos de facetas/superfícies. É a forma mais simples de se representar tanto estruturas 2D como 3D. Representamos um objeto por três estruturas de dados:

• Um conjunto de pontos, indicando os vértices do objeto;
• Um conjunto de pares (ou listas) destes pontos, indicando quais formam uma aresta (ou polígono) delimitando uma supefície do objeto;
• Uma conjunto de listas de arestas que formam uma superfície plana pertencente ao objeto (faceta). Esta pode ser considerada opcional, dependento da qualidade de representação desejada, como veremos adiante.

A representação mais simples para uma estrutura espacial é formada por somente duas listas. Neste caso ignoramos a representação explícita das superfícies do objeto e representamos apenas as suas arestas como um modelo de arame.

Um modelo de arame, também chamado de wireframe, é uma representação 3D extremamente simples e fácil de se manipular de um objeto. Onde representamos este objeto por uma nuvem de pontos e pelas arestas que interligam os pares de pontos que formam as “bordas” ou “quebras” do objeto. O resultado é uma representação gráfica de um objeto parecendo um modelo 3D realizado com varetas ou com arame, daí o seu nome.

Durante muito tempo, nos primórdios da Computação Gráfica, os wireframes foram a única forma de representação suportada pelos softwares gráficos em função de suas limitações de processamento. O processamento gráfico necessário para representar modelos de arame é bastante reduzido e por isso são modelos extremamente eficientes. Em um modelo de arame não nos preocupamos com iluminação, ocultação de faces ou de partes do objeto, pois a representação do objeto não suporta nenhum tipo de visualização de suas superfícies, que são elementos essenciais quando trabalhamos com efeitos de iluminação.

Em aplicações de engenharia ou de algumas áreas da arquitetura, os wireframes são modelos representacionais suficientemente poderosos, pois contêm toda a informação estrutural necessária para cálculos de área, volume, resistência do material, etc.

Modelo de arame representado por duas listas

Adicionando elementos a um modelo de arame

O processo de adição de novos elementos a um modelo de arame ou de sua modificação é bastante simples e resume-se à adição de novos pontos na lista de pontos e de novos pares de índices de pontos na lista de arestas.

Adição de uma superfície ao paralelepípedo representado como modelo de arame

Implementação das listas de um wireframe utilizando ponteiros

Existem muitas possibilidades diferentes para você implementar um objeto do tipo wireframe. Se você está utilizando uma linguagem de programação orientada a objetos de alto nível como Smalltalk ou Java, vai provavelmente querer criar uma classe cujos atributos vertices e pontos contenham instâncias de estruturas de lista como
OrderedCollection
ou
SortedCollection
, onde os elementos contidos na lista vertices referenciam os pontos contidos na lista pontos. Se você está trabalhando com uma linguagem estruturada o mais interessante é utilizar listas encadeadas com ponteiros, para permitir uma melhor manipulação do espaço de memória utilizado e maior flexibilidade na construção dos objetos.

Independentemente da linguagem, porém, você vai necessitar de duas listas, onde a lista de arestas referencia os pontos que compõe cada aresta e onde cada ponto existe na lista de pontos apenas uma vez, independentemente de quantas arestas o utilizem, para poder manipular os objetos de forma confortável, por exemplo ao realizar operações de translação ou de rotação de um objeto. Dessa forma, ao mover, escalonar ou rodar um objeto, você somente precisa aplicar a operação aos pontos da lista de pontos e o objeto vai estar automaticamente transformado, pois a posição e o tamanho de uma aresta são conseqüência do estado de seus pontos. Se você optar por uma representação de um wireframe em uma única lista, onde uma aresta é representada por um par de pontos, você terá para duas arestas que compartilham um determinado vértice, uma cópia diferente da posição daquele vértice em cada aresta e vai ter de calcular a transformação daquele ponto duas vez, tornando a manipulação de sua estrutura ineficiente.

Listas de vertices e pontos como listas encadeadas

Modelos de arame para estruturas mais complexas

O processo mais comum para a construção de modelos de arame complexos, representando estruturas que não possuem uma conformação geométrica simples, mas sim são irregulares e constituídas por superfícies que originalmente eram curvilíneas é a triangularização.

Em um modelo de arame triangualrizado, representamos a superfície ou a estrutura do objeto como um conjunto de triângulos. Para o cálculo destes triângulos existem alguns algoritmos tradicionais que veremos adiante.

Modelo de Arame de um Esqueleto de Pé (Univ. de Graz)

Modelo de Arame de uma Cabeça Humana tomografada construída como listas de polígonos triangulares (Projeto Cyclops – paciente de Ibirama/SC)

A grande vantagem de modelos de arame triangularizados é a sua capacidade representacional. Podemos representar estruturas extremamente complexas e irregulares ou cenas constituídas por um grande número de objetos utilizando wireframes. Mesmo que se deseje representar algo muito complexo, as estruturas de dados são as mesmas

Representação de um acena complexa como wireframe

Observe que na figura acima algumas estruturas estão representadas como quadriláteros. Isto e´uma otimização possível: se triângulos adjacentes são coplanares pode-se fundílos em um quadrilátero e assim por diante. Normalmente o processo se torna muito caro se continuamos, mas fundir triângulos em quadriláteros aumenta a eficiência.

Construindo um modelo de arame

Nesta página vemos um exemplo do processo de geração dos dados para um modelo de arame a partir de dados reais.

Dados iniciais são valores de um segmento de uma superfície porosa.

Para construir um modelo de arame, tomamos um grid de pontos sobre a figura, interligamos todos os vizinhos e plotamos com y=claridade (a). Por fim, construindo um modelo de arame, atribuímos aos segmentos de reta a média do tom de cinza dos seus vértices na imagem original (b).

Geração dos dados para modelos de arame

Ao tomarmos um conjunto de dados naturais em 3D, isto é, um conjunto de dados que não foi gerado artificialmente por algum programa mas que representa alguma estrutura que foi medida, escaneada, etc, várias perguntas se nos colocam ao desejarmos criar um modelo de arame triangularizado para descrever estes dados. As principais são:

• Como geramos a grade de pontos?
• Temos um objeto qualquer, como obtemos um conjunto de pontos relevantes que o descreva adequadamente?
• Como geramos o conjunto de segmentos de reta ou de polígonos que definem a estrutura do objeto?
• Tenho os pontos. Quais eu ligo com quais?

Veremos adiante como responder estas perguntas computacionalmente.

Geração das Nuvens de Pontos

O método mais utilizado para a geração de pontos descrevendo um objeto é a interpolação poligonal. Para tanto tomamos as bordas dos objetos que queremos descrever e substituímo-las por um polígono com um grau de acuidade desejado.

• Em 2D: Isto já gerou os dados que queremos;
• Em 3D: definimos uma direção qualquer onde vamos gerar um conjunto de polígonos em planos paralelos, para depois reconstruir.

Gerando polígonos

Modelos de facetas: adicionando uma terceira lista

Quando queremos representar a superfície externa ou mesmo as várias superfícies das estruturas que formam um objeto, um modelo de arame não basta mais. Precisamos de uma estrutura de dados com um poder representacional maior, que seja capaz de conter informação sobre como as arestas dos objetos se interrelacionam para formar superfícies. Isto é especialmente importante quando queremos dar realismo à nossa renderização e calcular efeitos de iluminação. Para poder calcular estes efeitos precisamos ter uma referência para calcular quanta luz cada parte de um objeto recebe e a orientação das superfícies que o compõem nos fornece esta informação.

Chamamos as estruturas de dados que representam a parte externa das estruturas de um objeto aravés de conjuntos de listas de superfícies planares de modelos de facetas. Estas facetas podem ser geradas pelo usuário ou calculadas através de um processo de triangularização que não é diferente daquele usado para modelos de arame.

Iniciemos analisando a estrutura de dados necessária para representar internamente um modelo de facetas. Uma estrutura de dados contendo duas listas já não é mais um alternativa eficiente. Agora necessitamos de uma terceira lista, contendo nodos que descrevam cada uma das facetas como conjuntos de arestas. Mais uma vez, por uma questão de eficiência no cálculo de transformações geométricas é importante que estes nodos não contenham cópias dos segmentos de reta que constituem suas bordas, mas sim que referenciem estes segmentos, os quais são representados apenas uma vez.

Estruturas de dados para um modelo de facetas. Cada objeto é representado por três listas, contendo respectivamente seus pontos, suas arestas e suas facetas.

Se nós possuírmos dados naturais, isto é, calculados a partir de algum objeto real medido, o mais provável é termos uma reconstrução realizada através de triangularização, como vemos na figura adiante, onde o modelo de arame da cabeça reconstruída a partir de uma série de tomografias agora está sendo representado como modelo de facetas. Observe que agora é possível impingir mais realismo à representação, calculando-se e reflexo de uma fonte de luz sobre a superfície do objeto.

Visualização do Modelo de Facetas: Cabeça Humana tomografada construída como listas de triângulos (Projeto Cyclops – paciente de Ibirama/SC)

Cálculo de Reflexos de Luz

Facetas permitem a definição de normais à superfície e assim o cálculo de reflexão da luz. Nós vamos ver esta técnica e seus algoritmos em detalhes mais adiante neste texto, vamos aproveitar aqui apenas para citar os seus princípios gerais.

Para toda superfície planar, isto é, contida em um plano, é possível calcular-se um número infinito de vetores perpendiculares à superfície, todos paralelos entre si. Chamamos a estes vetores de normais da superfície. São os ângulos entre um raio de luz incidente sobre uma superfície e o seu vetor normal e entre o raio refletido em direção ao observador e a normal à superfície que, com base em alguma regras óticas, nos vão dizer como essa superfície se comporta, se ela reflete muita ou pouca luz e se ela pode produzir reflexos “espelhados”, como o centro da testa da cabeça na figura a seguir. Exemplos de vetores normais a duas superfícies estão na figura apresentada a seguir.

Normais

Um problema que ainda permanece fica bastante evidente na See Visualização do Modelo de Facetas: Cabeça Humana tomografada construída como listas de triângulos (Projeto Cyclops – paciente de Ibirama/SC), onde a diferença do comportamento de reflexos luminosos entre uma faceta e outra é acentuada, deixando óbvio para o observador que se trata de uma estrutura constituída por facetas. É um resultado pouco natural e indesejável em uma renderizaçãoi realista. A definição de normais intermediárias, que são a média das normais de duas ou três facetas adjacentes, aplicadas para o cálculo do reflexo de luz nas regiões fronteiriças entre as facetas resolve este problema, como mostra a See Visualização do Modelo de Facetas com bordas “amaciadas”. Artéria Aorta Humana tomografada construída como listas de triângulos (Projeto Cyclops – paciente de São José/SC).

Visualização do Modelo de Facetas com bordas “amaciadas”. Artéria Aorta Humana tomografada construída como listas de triângulos (Projeto Cyclops – paciente de São José/SC)

Problemas na triangularização

Bifurcações das estruturas

Single-branching não trata este problema e devemos tratá-lo com algoritmos adicionais.

Usamos o método da Geração do contorno interpolado (Ck)

Primeiro, um contorno único e fechado (Ck) é criado a partir de r contornos (Ck, 1), (Ck, 2)… (Ck,r) no nível zk. Depois, o contorno intermediário (C’k), no nível z, é obtido pela interpolação entre (Ck, 1) e (Ck).

Estrutura com várias bifurcações reconstruída atravpés de triangularização co o método da geração do contorno interpolado.

Geração do contorno interpolado (Ck): Passo 1a

o contorno (Ck) construído a partir de (Ck, 1), (Ck, 2)… (Ck,r) é obtido utilizando-se um polígono, cujos vértices são os centróides B1, B2…Br dos r contornos.

Entre todas as possibilidades possíveis é escolhido o polígono P(r) que possui a maior área. Para esse fim, o casco convexo de B1…Br é calculado utilizando-se o método de Graham.

Em seguida, os vértices que não pertencem ao casco convexo são ligados aos vértices da borda do casco convexo mais próximo.

Geração do contorno interpolado (Ck): Passo 1a

Geração do contorno interpolado (Ck): Passo 1b

Finalmente o contorno (Ck) é obtido conectando-se os r contornos (Ck, 1)… (Ck,r) à P(r) nos 2r pontos de intersecção I1,1, I1,r; I2,1, I2,r destes contornos com P(r)

Geração do contorno interpolado (Ck): Passo 1b

Técnicas de subdivisão do espaço

Ao invés de se recosntruir os dados de uma estrutura espacial de forma a se poder representá-la computacionalmente de maneira eficiente, outra forma de se chegar a esta representação é subdividir o espaço até se obter um conjunto de subdivisões que represente o objeto desejado. Existem duas estruturas de dados que se baseiam neste princípio: Quadtrees e Octrees.

A idéia básica é subdividir recursivamente o espaço (2D ou 3D) até possuirmos somente subregiões homogêneas que ou pertencem a um objeto ou não.

A seguirmos um determinado ramo ou subregião, paramos sempre que uma região for homogênea. Dessa forma o grau de acuidade de nossa representação pode ser definido arbitrariamente.

Ideal para construir estruturas de dados que representem espacialmente um objeto real qualquer que possuamos.

Estrutura de dados resultante será sempre uma árvore, que pode ser inserida no ambiente gráfico e manipulada através de transformações.

Quadtree

A quadtree é originalmente uma estrutura de dados para subdivisão do espaço bidimensional, mas podemos utilizá-la com sucesso na representação de estruturas 3D criadas a partir de dados adquiridos a partir de um volume de dados constituído por um conjunto de planos representando fatias deste volume, como acontece em dados médicos de tomografias ou ressonâncias magnéticas. Neste caso criamos uma quadtree para cada fatia e depois unimos estas quadtrees de forma a gerar a estrutura 3D final, atribuindo a todos os pontos de uma mesma quadtree a faixa de mesma coordenadas z, atribuindo à quadtree uma espessura. A quadtree possui algumas características que a tornam computacionalmente interessante:

• Representação compacta;
• Estrutura hierárquica 4-ária;
• Cada folha descreve uma região homogênea;
• Cada nó intermediário tem quatro filhos que decompõem a imagem;
• Decomposição pode ser feita por algoritmos recursivos.

Uma quadtree é obtida através de sucessivas subdivisões de duas dimensões num plano bidimensional para formar quadrantes, como mostra a See Divisões sucessivas do espaço bidimensional formando uma árvore. Quando uma quadtree é usada para representar uma área num plano, a imagem em cada um dos quadrantes pode ter uma só cor, ou pode ser heterogênea. Um quadrante heterogêneo é recursivamente subdividido até que todos os quadrantes fiquem homogêneos, ou até que um nível predeterminado de divisão seja atingido.

Pode-se definir a resolução da decomposição pré-fixando o número máximo de vezes em que o processo de decomposição será aplicado, ou definindo como critério de parada, um grau de homogeneidade. Na imagem da figura abaixo, cada bit é preto ou branco. A imagem foi dividida até que cada quadrante fosse homogêneo, isto é, até que cada quadrante fosse totalmente branco ou totalmente preto.

Divisões sucessivas do espaço bidimensional formando uma árvore

As sucessivas subdivisões podem ser representadas por uma hierarquia onde os quadrantes heterogêneos são representados pelos nós internos e quadrantes homogêneos pelos nós folhas. Neste caso, o nó topo da hierarquia representa a imagem como um todo.

Quadtree

No exemplo da See Quadtree:

• Um nodo é representado por um quadrado branco se entre os nodos folha que este nodo representa existem apenas pixels brancos.
• Um nodo é representado por um quadrado preto se entre os nodos folha que este nodo representa existem apenas pixels pretos.
• Um nodo é representado por um circulo se entre os nodos folha que este nodo representa existem pixels brancos e pretos.

Existem vários tipos diferentes de quadtrees. O quadtree de região é uma partição do espaço em um conjunto de quadrados, em que o lado é uma potência de dois, isto é, de cada divisão em quadrantes resultam quatro quadrados iguais. Este é o tipo mais usado de quadtree.

Uma vantagem da utilização de quadtrees é que uma imagem pode ser representada de forma compacta, mas esta característica depende da imagem a ser representada. Imagens com áreas grandes da mesma cor serão representadas de forma bem compacta, enquanto que imagens mais sofisticadas, onde cada pixel tem uma cor diferente não apresentarão vantagem. Quadtrees também são muito úteis para variar a resolução de um objeto. Observe que o número de nodos em um quadtree correspondente a uma imagem é diretamente proporcional à resolução da imagem. Quando renderizamos um objeto “visto de longe”, onde ele será representado pequeno na tela, podemos limitar a profundidade de percurso da quadtree que o representa e assim otimizar o processo de renderização.

Objeto a ser modelado em quadtree, grau de resolução escolhido e resultado final

Outra vantagem é que existem muitos algoritmos disponíveis para manipular estruturas de dados neste formato. Existem algoritmos para caminhamento e manipulação de hierarquias (árvores) como as utilizadas na representação de quadtrees, além de algoritmos para operações booleanas, como união e interseção, transformações e localização de nós adjacentes, e rotações em ângulos múltiplos de 90 graus.

Operações sobre quadtrees

Quadtrees também permitem uma manipulação eficiente em casos onde se deseja construir novos objetos a partir de antigos. Para fazer a união entre duas quadtrees A e B em uma quadtree C, os nós, das hierarquias das quadtrees A e B, são examinados do topo até os nós inferiores, par a par e em seus respectivos níveis, e o nó da hierarquia resultado C é obtido conforme as regras:

1 – Se um dos nós que estão sendo analisados nas hierarquias A e B, for um nó preto, o nó resultante na hierarquia C será preto;

2 – Um nó, na hierarquia C, assume o valor branco apenas se os dois nós correspondentes, nas hierarquias A e B, forem brancos;

3 – Se ambos os nós, nas hierarquias A e B, forem heterogêneos, o nó resultante, hierarquia C, será heterogêneo.

União de duas quadtrees

O algoritmo é aplicado recursivamente até os pares do último nível, sendo que o último nível da arvore resultante deve ser inspecionado, pois se um conjunto de nós de um mesmo quadrante for todo preto, estes serão apagados e o nó correspondente de ordem superior é trocado para preto.

Com relação a transformações espaciais, duas situações podem ocorrer:

• Utilizamos o algoritmo de criação da estrutura espacial apenas para gerá-la e depois permitimos que as lados de uma quadtree não sejam mais paralelos ou ortogonais aos eixos x e y.
• Exigimos que a estrutura tenha sempre um lado paralelo ao eixo x e outro paralelo ao eixo y.

Se optarmos pela primeira interpretação do modelo, teremos um modelo extremamente flexível, mas que não aproveita algumas otimizações na sua movimentação. Se optarmos pela segunda interpretação, teremos alguns métodos específicos para sua manipulação, mas sérias limitações sobre quais operações podem ser realizadas com a estrutura.

Por exemplo, uma rotação de 90 graus pode ser atingida simplesmente movendo-se cada nodo da hierarquia como mostra a See Rotação em 90 graus de uma quadtree. A principal desvantagem das quadtrees é que é praticamente impossível comparar duas estruturas que diferem apenas em rotação ou translação. Isso acontece porque a representação em quadtree de uma imagem transladada ou rotacionada é totalmente diferente da imagem original. Os algoritmos disponíveis para a rotação de imagens são restritos à rotações de 90 graus, ou múltiplos deste ângulo.

Rotação em 90 graus de uma quadtree

Otimização de Quadtrees

Podemos otimizar a representação de quadtrees através da eliminação dos nodos representando espaços vazios, como mostra a See Otimização de quadtree aravés de eliminação dos nodos representando espaços vazios.

Otimização de quadtree aravés de eliminação dos nodos representando espaços vazios

Armazenamento externo de quadtrees

Quadtrees podem ser facilmente armazenadas de forma compacta em arquivos, o que facilita enormemente a sua utilização em arquivos de descrição de cenas ou de configuração de ambientes que vão ser renderizados.

Uma forma de armazenar este tipo de estrutura em arquivo é utilizando o esquema mostrado na See Codificação de quadtree para armazenamento compacto em disco. A See Codificação de quadtree para armazenamento compacto em disco mostra o esquema de representação em arquivo, a See Representação de quadtree em discoa mostra um quadtree exemplo, a See Representação de quadtree em discob mostra a hierarquia representando a quadtree exemplo, e a See Representação de quadtree em discoc mostra o conteúdo de um arquivo representando o quadtree da See Representação de quadtree em discoa de acordo com o esquema representado na See Representação de quadtree em disco.

Codificação de quadtree para armazenamento compacto em disco

Representação de quadtree em disco

A partição em quadtrees tem muitas aplicações além da Computação Gráfica, por exemplo em geometria computacional e aplicações geométricas incluindo data clustering, representação de formas, modelagem de moléculas, geração de malhas, GIS sistemas de informação geográficos.

Octree

Uma Octree é a progressão natural de um quadtree para representação de um espaço tridimensional. Octrees dividem recursivamente um objeto de três dimensões em 8 cubos menores chamados de células ou octantes. Se alguma das células resultantes é homogênea, isto é, se a célula está inteiramente dentro ou fora do objeto, essa célula não será mais dividida.

Octree é uma estrutura de dados equivalente à matriz de voxel, mas ocupa menos memória Na octree a resolução varia ao longo do modelo, e pode ser ajustada da mesma forma como na quadtree.

Do ponto de vista matemático, a Octree é uma estrutura hierárquica 8-ária. Cada nó da octree corresponde a uma região cúbica do universo. O valor de cada nó é atribuído da mesma forma que na quadtree.

Octree

Vamos adiante examinar alguns exemplos de octrees.

Octree: Distribuição de dados em 3D a ser Modelada

Modelagem dos mesmos dados como Árvore de Subdivisão Espacial

“Rosquinha” como octree

Caneco-octree

Exemplos de Aplicações com Octrees

Como foi dito anteriormente, as octrees e quadtrees se prestam muito bem a aplicações onde temos um conjunto de dados naturais que necessitam ser modelados em 3D e representados em um sistema de computação gráfica.

A área de aplicação médica, onde se trabalha com volumes de voxel representados por conjuntos de cortes tomográficos isto é uma situação constante. Em muitos casos desejamos escolher de forma simples e rápida uma determinada estrutura de um volume de imagens médicas e visualizar uma reconstrução tridimensional desta estrutura em um sistema de Computação Gráfica. A octree é uma forma de representação ideal para este tipo de situação, pois permite ao mesmo tempo que seja utilizada como estrutura de dados auxiliar no processo de reconstrução 3D e também mais tarde como representação compacta para visualização.

As duas figuras abaixo mostram primeiramente os passos iniciais de cálculo de quadrantes em uma imagem de tomografia onde se utiliza um critério de similaridade de valor de pixel para decidir se se vai dividir ou não um nodo e depois uma reconstrução 3D do esqueleto deste paciente gerada com esta técnica.

Octree: Exemplo de Aplicação Médica Reconstrução de Esqueleto (Projeto Cyclops – Paciente de Florianópolis/SC)

Geometria construtiva

A Geometria Construtiva (GC) é na verdade uma forma de definição de operações sobre objetos geométricos sólidos e não um tipo de estrutura de dados. Ela toma primitivas tridimensionais como entrada e aplica operações sobre conjuntos e operadores de translação, escalonamento e rotação para produzir objetos 3D complexos a partir das primitivas. Como os objetos resultantes dessas operações são na verdade novos objetos complexos e se pode usar uma seqüência de operadores em GC para descrever este novo objeto resultante, a GC acaba sendo considerada uma forma de se definir estruturas de dados. Em função disso está aqui neste capítulo.

Uma das vantagens da GC é que suas primitivas geométricas incluem cilindros, esferas, cones e outras formas normalmente não abordadas por outras técnicas, justamente pela dificuldade de se definir operações sobre elas.

A implementação destas operações é bastante complexa e estudar os algoritmos necesários para implementá-las iria além dos objetivos deste texto, por isso nós vamos examinar esta técnica apenas do ponto de vista teórico e de sua utilização, não do ponto de vista de implementação da GC. Mais adiante neste texto, quando estivermos vendo Raytracing, no tutorial de POV-Ray, vamos realizar alguns exercícios usando as facilidades de GC oferecidas pelo ambiente do POV-Ray.

Operações de Geometria Construtiva

A Geometria Construtiva define uma série de operações a serem realizadas com dois ou mais sólidos. Cada operação gera como resultado um novo sólido, que pode ser, por sua vez, objeto de novas operações. As principais operações são as seguintes quatro:

• União: Duas ou mais formas são unidas;
• Intersecção: Duas formas são combinadas para fazer um novo objeto consistindo do subespaço comum a ambos;
• Diferença: Tomamos um objeto inicial e subtraímos dele os volumes do espaço ocupados por todos os objetos subseqüentes;
• Junção (Merge): Duas ou mais formas são unidas. Permanece apenas o limite/superfície mais externo. Útil em objetos transparentes.

União em Geometria Construtiva

A união em GC é a operação de criar um novo sólido a partir de dois sólidos pré-existentes, tomando-se como novo limite ou nova superfície externa a superfície mais externa resultante de se unir estes dois sólidos. Na prática significa que fundimos os dois elementos assumindo que são sólidos ocos formados unicamente por sua superfície externa e que o sólido resultante possue a superfície que resulta dessa junção.

União em GC

Intersecção em Geometria Construtiva

A intersecção em GC pode ser interpretada como o subvolume comum aos solidos que são intersectados. A superfície do objeto resultante é a superfície desse subvolume comum.

Intersecção em GC

Diferença em Geometria Construtiva

A diferença em GC pode ser interpretada como retirar o segundo sólido de dentro do primeiro, observadas as posições definidas para os dois sólidos durante a operação. O resultado dessa operação é o primeiro sólido, de onde foi retirada a parte constituída pela sua intersecção com o segundo.

Diferença em GC

Veremos adiante o resultado de uma seqüência de operações de GC sobre 4 paralelepípedos achatados. O objetivo é “construir” uma peça complexa. As operações são uma diferença com o resultado de uma união aplicada ao resultado de uma intersecção.

Seqüência de operações de GC

Modelos hierárquicos

A utilização de modelos hierárquicos é uma técnica aplicável a qualquer das representações anteriores. Objetos complexos são construídos como hierarquias (árvores) de objetos mais simples representando suas partes.

Organiza o display file por objetos tais quais o usuário os experiencia (“homem”, “árvore”, “robô”). Permite melhor controle e a aplicação eficiente de transformações geométricas

Há duas formas de implementação:

• Procedural: Cada parte de um objeto complexo é representada por uma função que descreve o comportamento desta parte e a desenha de acordo com o contexto momentâneo. A estrutura hierárquica na verdade é uma árvore de chamadas de funções. É útil em aplicações fortemente orientadas à animação. Esta forma de implementação da utilização de Modelos Hierárquicos é detalhada no capítulo de Modelos Hierárquicos deste texto.
• Estrutural: Utiliza uma estrutura de dados em árvore que representa as várias componentes do objeto. O comportamento é dado pela aplicação de transformações ao objeto.

Hierarquia das peças de um acena de uma pessoa com uma máquina.

Estrutura da hierarquia anterior

Exercício 1.5: Objetos e transformações 3D

Implemente uma classe Ponto3D capaz de realizar as 3 transformações básicas e também a rotação em trono de um eixo arbitrário.

Implemente uma Classe Objeto3D para representar um Modelo de Arame com as seguintes características:

• Possuir uma lista de segmentos de reta representados através de uma classe deniminada Aresta3D que possui um par de referências a Pontos3D;
• Possuir uma lista de Pontos3D;
• Ser capaz de realizar as 3 operações básicas e também a rotação em torno de um eixo arbitrário.

Neste capítulo nós não vimos ainda a projeção, por isso você ainda não sabe como visualizar estes objetos. Em função disso, o teste da implementação terá necessariamente de ser “no seco”.

Modelagem da estrutura para objetos 3D

A interface de usuário poderá ser desenvolvida como esta mostrado na See SGI para operações 3D. Cortesia de Brian Schmitz Tani.. Observe que para possibilitar a realização da rotação você tem de estender consideravelmente o conjunto de informações que necessita ser entrado no sistema antes de ser possível realizar uma rotação. Para a rotação você sempre tem de fornecer o eixo de rotação. O caso mais simples é o caso de uma rotação em torno de um dos eixos (origem), onde você somente necessita fornecer o ângulo e o eixo.

SGI para operações 3D. Cortesia de Brian Schmitz Tani.

Para facilitar a vida do usuário no caso de uma rotação arbitrária, você pode permitir que ele entre com apenas um ponto, fazendo com que seu vetor até a origem seja o eixo de rotação.

Obseve que o usuário deverá sempre entrar com os dados em coordenadas do mundo.