Renderizando Objetos CSG Utilizando Subdivisão

Trabalho realizado no curso de Introdução aos sistemas gráficos 3D

Guilherme Schirmer de Souza e Antonio Fernando da Rocha Júnior

 

Os modelos CSG são baseados em primitivos geométricos e nas operações com conjuntos de pontos de união, interseção e diferença.

As operações são definidas através de operadores lógicos e a função classificação ponto-conjunto, a qual determina se um ponto p Î Â 3 está no interior, exterior ou na fronteira do sólido C.

Estes modelos são representados por meio de árvores binárias, onde as folhas representão os primitivos e os nós são as operações.

   

Na biblioteca S3D, um primitivo é representado por uma estrutura denominada PRIM. A biblioteca contém o primitivo esfera (SPHERE) já implementado.

Foram criados como extensão os primitivos cone (CON) e cilindro (CYLINDER).

 

 

 

 

 

            Representação em linguagem de cena:

 

 

 

 

 

 

  1. Em uma cena CSG, cada pixel da imagem é renderizado percorrendo-se toda a árvore da cena.
  2. A idéia é subdividir a árvore de uma cena CSG em árvores menores visando acelerar a renderização da imagem.
  3. Subdividindo as arestas do "bounding box" da cena por um inteiro n, obtivemos desta forma n³ "bounding box" menores.

  4. Cada uma das caixas obtidas deve conter de 0 a 2 objetos, tornando fácil e rápido o traçado de raios na região.

  5. Devemos aumentar o valor de n atá a condição acima ser satisfeita por todos os "bounding box" da cena ou até atingirmos um número máximo de divisões predeterminado. Verificamos então o tipo de relacionamento entre os objetos na região considerada e construímos uma árvore CSG para esta.

  6. Executamos então o traçado de raios para cada parte da cena, utilizando a árvore correspondente.

 

Inicialmente, criamos a função evalBbox, que retorna o "bounding box" de uma cena.

As operções entre os nós da árvore são calculadas utilizando-se um percurso em pós-ordem modificado.

A rotina retorna resultados aproximados, uma vez que utilizamos apenas operações entre as caixas.

A rotina interBbox retorna o número de objetos que intersectam um determinado "bounding box" passado como parâmetro . Além do mais, retorna uma lista, que é passada por referência, contendo todos os "bounding box" dos objetos que intersectaram o "bounding box" passado como parâmetro.

O percurso na árvore é semelhante ao da rotina evalBbox.

A rotina interBbox será usada na verificação do número de objetos que pertencem aos "bounding box" resultantes da divisão.

A rotina relacionamento recebe como parâmetros a árvore CSG original e a lista de todos os "bounding box" que interessam numa determinada cena. Ela retorna uma árvore CSG com as respectivas operações booleanas entre os primitivos dessa cena.

A rotina copia_arvore faz uma copia da árvore original para não perdermos os apontamentos originais na função relacionamento.

A rotina matriz_arvore cria uma matriz tridimensional, que será uma representação da divisão da cena, onde cada elemento da matriz contém a árvore correspondente de cada cena.

Plane_intersect calcula o parâmetro "t" de interseção de um determinado raio com um plano (r = r.o + t*r.d).

Os planos utilizados nestes cálculos são as faces dos "bounding box". O parâmetro utilizado no cálculo do ponto de interseção do raio com uma das faces, utilizando box_point.

Finalmente, a rotina what_box retorna os índices de um elemento da matriz de sub-árvores CSG.

Para este elemento é feito o cálculo de interseção do raio, caso o elemento não seja nulo.

 

 

 

 

 

 

 

 

Como exemplo, a segunda figura representa um trem composto por 16 objetos. Se fizermos uma matriz_dimensional composta por 153 cubos obtemos 1012 árvores vazias, 1260 árvores com apenas um objeto, 877, com apenas dois, 216 com 3 e apenas 10 com 4, o que mostra árvores bem mais simples que a original (composta por 16 objetos), facilitando assim o traçado de raios.

 

 

 

 

 

 

 

 

 

 

 

 

 

Podemos observar que a técnica ainda precisa de algumas correções na parte do cálculo de qual árvore da matriz tridimensional devemos usar, o que poderá ser resolvido com a adoção de alguns algoritmos de rasteração 3D. Percebemos ainda que foram obtidas árvores bem mais simples que a original, o que poderá proporcionar um desempenho bem mais elevado na renderização quando implementado em hardware.

 

          Código-fonte