TRAÇADO DE RAIO PARA UMA NUVEM DE PONTOS

Trabalho final do curso de sistemas gráficos 3D/2002

by José Luiz Soares Luz


1. Ray Tracing

2. Octree

3. Ray Tracing Point Sampled Geometry

4. Resultados

5. Download

6. Bibliografia

 

 

   

O trabalho consistiu na implementação de uma técnica de traçado de raios para uma nuvem de pontos, descrita no artigo Ray Tracing Point Sampled Geometry, de Gernot Schauffer e Henrik Wann Jensen; foi utilizado o pacote gráfico do curso para a desenvolvimento do projeto. Vejamos algumas noções iniciais.


 

1. RAY TRACING

         Em linhas gerais, determina a visibilidade de uma superfície pelo traçado de raios de luz imaginários do olho do observador até o objeto na cena. Um centro de projeção (olho do observador) e uma janela sobre um plano de visão arbitrário são selecionados. Podemos imaginar a janela dividida em uma grade regular, cujos elementos correspondem à pixels (picture elements) na resolução desejada.

 

 

         Assim para cada pixel na janela, um raio (eye Ray) é disparado do centro de projeção através do centro do pixel na cena, a cor do pixel é fixada de acordo com o objeto, cujo ponto de intersecção com o raio está mais próximo.

  

  

1.1. Calculando Interseções

         A tarefa principal no traçado de raios consiste no cálculo da intersecção de um raio com o objeto, para isto utilizamos a representação paramétrica de um vetor. Cada valor (x,y,z) ao longo do raio indo de (x0,y0,z0) (centro de projeção) até (x1,y1,z1) (centro do pixel) é definido por algum valor t no intervalo [0,1] ; tal que

 

 

         Valores negativos de t representam pontos atrás do centro de projeção, enquanto que valores maiores que 1 correspondem a pontos no lado da janela mais afastados do centro de projeção. Assim precisamos achar uma representação para cada tipo de objeto que nos possibilite determinar t, que define o ponto de intersecção do objeto com o raio. Podemos utilizar uma estrutura de dados conhecida como octree para acelerar o traçado de raio (Ray Tracing).

   TOP

2. OCTREE

         Seja S um conjunto de objetos no espaço 3D, e B  uma caixa cujas arestas estão alinhadas com os eixos coordenados OX, OY, OZ e que contém o conjunto S .( B=[ x0,xf ]x[ y0,yf ]x[ z0,zf ] ).

 

 

 

1)    Se card(S) <=m , onde m é uma constante pré-selecionada, então a OCTREE consiste de um simples nó folha armazenando todos os objetos no conjunto S; outro critérios também são possíveis.

2)    Se card(S) > m , sejam BLUF, BLUB, BLDF, BLDB, BRUF, BRUB, BRDF e BRDB    os oitos octantes de B , onde temos L: left, R: right, U: up, D: down, F: front e B: back, e x0 <= xmed <= xf, y0 <= ymed <= yf, z0 <= zmed <= zf, e (xmed, ymed, zmed) é um ponto dentro de B. Os conjuntos dos objetos e as caixas envolventes dos oito filhos (octantes) são respectivamente Sijk={s S | s Bijk vazio } , para i {L,R}, j {U,D}, k {F,B} , e Bijk = XixYjxZk , onde XL=[x0,xmed], XR=[xmed,xf], YU=[y0,ymed], YD=[ymed,yf], ZF=[z0,zmed], ZB=[zmed,zf] . Neste caso, a OCTREE é compreendida de um nó interno com oito filhos, cada qual é uma OCTREE com raiz (caixa envolvente) Bijk  para o conjunto de objetos Sijk .

 

A figura abaixo é um exemplo de uma OCTREE de dois níveis, cada octante como descrito acima. Objetos são armazenados nos nós folhas (não possui filhos); os nós folha em uma OCTREE tem diversos nomes: obe, prism, voxel, cell, cube ou octree box. Uma OCTREE tradicional somente armazena os objetos nos nós folha, mas objetos podem ser armazenados em ambos: nós internos ou folha. Se um objeto intersecta mais de um nó, pedaços do objeto são armazenados em cada um deles.

TOP

3. RAY TRACING POINT SAMPLED GEOMETRY

         Este artigo introduz uma técnica de intersecção para traçado de raio, tal que intersecções com uma nuvem de pontos são detectadas dentro da cena, onde a densidade dos pontos está acima de um certo limite pré-definido, então usa-se todos os pontos dentro de uma distância fixa do raio, para interpolarmos a posição, normal, e qualquer outro atributo da intersecção. Este método assume que a nuvem de pontos satisfaz certos critérios, tais como:

1)    A densidade dos pontos deve ser pelo menos duas vezes tão alta quanto a mínima distância entre diferentes porções da superfície.

2)    O máximo espaço na amostra entre os pontos é conhecido.

3)    Os pontos estão uniformemente distribuídos.

4)    Temos uma normal por ponto.

 

3.1. Calculando Intersecção

         O cálculo da intersecção com os pontos está dividido em duas partes:

a)    Detectar se uma intersecção ocorreu.

b)    Calcular o atual ponto de intersecção e a normal.

 

a) Cada ponto é considerado como o centro de um disco que tem a mesma normal à superfície no ponto, o raio do disco r é fixado como sendo um pouco maior do que o tamanho do maior distância entre os pontos na nuvem. Uma intersecção é detectada quando o raio intersecta um disco. Podemos pensar em cada disco como um pequeno pedaço do plano tangente a superfície naquele ponto, deste modo quando calcularmos os parâmetros da intersecção, estaremos obtendo informações que nos possibilitarão reconstruir a superfície a partir destes pequenos discos, e das interpolações que serão feitas.

         Nesta fase do trabalho foi criado o elemento primitivo disc, utilizando o pacote gráfico do curso, este primitivo possui os seguintes parâmetros: normal, centro e raio.

 

         No pacote gráfico do curso utilizamos a linguagem de descrição de cena 3D, para o traçado de raios, onde para o elemento primitivo disco teremos:

 

 

 

         Após a criação do elemento primitivo disco, buscou-se uma forma mais eficiente para a linguagem de descrição de cena, de modo a podermos realizar o traçado de raio através da nuvem de pontos, para isto criou-se o primitivo cloud, que corresponde a uma lista dos discos associados aos pontos.

 

 

 

b) A busca pelos pontos é acelerada usando uma octree, o raio(Ray Tracing) é considerado como sendo o eixo de um cilindro de raio r, e somente aqueles nós na octree que intersectam o cilindro são atravessados. Uma vez que uma intersecção é detectada, outro cilindro é iniciado neste ponto e todos os pontos dentro deste cilindro são coletados. O ponto de intersecção será calculado pela interpolação dos atributos destes pontos; convém destacar que a interpolação permite suavizar a superfície.

 

   

Esfera com poucos pontos (discos) com interpolação.

 

Esfera com poucos pontos (discos) sem interpolação.

 

 

         Onde di  é a distância do ponto ao raio (Ray Tracing), não a distância ortogonal, mas a distância no plano do disco associado ao ponto.

 

 

 

 

          O cálculo do ponto de intersecção depende levemente da posição do observador (centro de projeção). A posição final da superfície irá variar com a direção do raio incidente, mas as variações são pequenas de forma que não resultam em mudanças visíveis na superfície.

TOP

4. Resultados

 

Esfera com 180 pontos e discos de raio 0.09

 

Esfera com 684 pontos e discos de raio 0.09

 

Esfera com 684 pontos e discos de raio 0.11

Esfera com 16380 pontos e discos de raio 0.04

 

Cilindro com 360 pontos e discos de raio 0.09

 

Cilindro com 360 pontos e discos de raio 0.1

 

Cilindro com 720 pontos e discos de raio 0.1

Cilindro com 1800 pontos e discos de raio 0.1

 

Cone com 324 pontos e discos de raio 0.04

 

Cone com 648 pontos e discos de raio 0.05

 

Cone com 648 pontos e discos de raio 0.0815

Cone com 3240 pontos e discos de raio 0.04

 

Toro com 1369 pontos e discos de raio 0.07

 

Toro com 1369 pontos e discos de raio 0.1

 

Toro com 5329 pontos e discos de raio 0.07

Toro com 5329 pontos e discos de raio 0.09

 

Bunny com 1889 pontos e discos de raio 0.01

 

Bunny com 1889 pontos e discos de raio 0.02

 

Bunny com 1889 pontos e discos de raio 0.03

 

 Bunny com 1889 pontos e discos de raio 0.04

 

Bunny com 11927 pontos e discos de raio 0.01

 

Bunny com 11927 pontos e discos de raio 0.02

 

Bunny com 11927 pontos e discos de raio 0.03

Bunny com 11927 pontos e discos de raio 0.04

 

Toro e Esfera 

 

TOP

5. DOWNLOAD: S3D (apenas o pacote gráfico do curso sem a implementação feita)

6. Bibliografia

1.  Elon Lages Lima, Geometria Analítica e Álgebra Linear – Coleção Matemática Universitária, IMPA, Rio de Janeiro, 2001.  

2. Hebert Schildt, C Completo e Total, São Paulo: Makron Books, 1996.  

3. James Foley et all, Computer Graphics:Principles and Practice, 2nd edition, Addison-Wesley, 1996.  

4. Luiz Velho e Jonas Gomes, Sistemas Gráficos 3D – Série Matemática e Computação, IMPA, Rio de Janeiro, 2001.  

5. L. H. de Figueiredo e P. C. Carvalho, Introdução à Geometria Computacional, 18o Colóquio Brasileiro de Matemática, IMPA, 1991.

TOP