Representação por Células

Prévia do material em texto

Computação Gráfica
Modelagem Hierarquica de Objetos 
Universidade Federal Rural do Semi-Árido - UFERSA
Leandro C. Souza
leandro.souza@ufersa.edu.br
Representações por 
Enumeração Espacial
 Dividem o espaço em sub-regiões 
convexas.
 Grades: cubos de tamanho igual.
 Octrees: cubos cujos lados são potências de 
2.
 BSP-Trees: poliedros convexos.
Grades
• O espaço é subdivido em cubos formando 
uma grade tridimensional.
– A cada um destes cubos dá-se o nome de 
voxel.
– Codifica-se um sólido determinando quais 
voxels pertencem a ele.
Grades
• Vantagens:
– É fácil determinar se um dado ponto pertence ou não ao 
sólido: basta verificar se o ponto pertence a algum 
dos voxels.
– É fácil determinar se dois objetos se interferem (se tocam.
– Facilita a realização de operações de união, interseção e 
diferença entre sólidos.
• Desvantagem:
– Uma representação detalhada requer muita 
memória.
Octrees 
 Para melhor entendermos as octrees, 
discutiremos antes as quadtrees (caso 
2D).
 Quadree efetua subdivisão do espaço em 
quadrantes, de acordo com:
 Heterogeneidade do quadrante examinado.
 Nível máximo de subdivisão da árvore.
 Quadtree é uma estrutura de árvore onde 
cada nó possui exatamente 4 filhos.
Quadtree
Quadtree
Quadtree
Quadtree
Quadtree
 Estrutura de dados:
Octrees 
 Dividem o espaço em cubos, chamados 
voxels.
 Cada voxel pode sofrer sucessivas divisões.
 O critério de divisão é: se o voxel for 
heterogêneo – e ainda não atingimos um nível 
máximo de subdivisão – divida-o em octantes.
 O processo de divisão é recursivo. 
 Representação em árvore contendo nós 
com exatamente 8 filhos.
Octree – Estrutura de Dados
Octrees 
Octrees
 Exemplo:
Subdivisão de Voxels
 Os vértices de cada voxel são classificados 
como estando “dentro”, “fora”, ou 
parcialmente dentro (fora) do objeto.
Esta classificação é feita por testes de 
cada um dos vértices de um voxel contra 
as faces de um poliedro.Efetuaremos, portanto, testes de pontos 
contra planos.
Para isso, precisamos obter a equação do 
plano e calcular a distância de um ponto 
ao plano.
Obtendo a Equação de um 
Plano
 A equação de um plano é dada pelo vetor 
normal e um ponto conhecido do plano (P1).
 Podemos definir um vetor conectando o ponto 
conhecido P1 a um ponto qualquer do plano (P):
Como o vetor encontrado 
e o vetor normal são 
perpendiculares entre si, o 
produto interno deles será 
zero.
Obtendo a Equação de um 
Plano
 O produto interno entre o vetor normal e o 
vetor encontrado nos dá a equação do plano. 
 Calculando o produto interno, obtemos:
 Substituindo os termos constantes por 
d = -(ax1+by1+cz1), obtemos:
Testando um Ponto contra o 
Plano
 Para classificar um ponto (P2) em relação 
a um plano, precisamos calcular a sua 
distância D do ponto P2 ao plano.
Testando um Ponto contra o 
Plano
 A distância D é obtida 
por meio dos passos 
abaixo:
 Tome um ponto do plano 
(P1) e defina o vetor 
 . 
 A componente desse vetor 
na direção da normal tem 
comprimento igual à 
distância procurada.
 Assim, para calcular o 
valor da distância entre P2 
e o plano, basta calcular a 
norma da projeção de 
 sobre o vetor normal.
p⃗2− p⃗1
p⃗2− p⃗1
Testando um Ponto contra o 
Plano
 Usando a fórmula para o vetor projeção 
ortogonal, a distância D entre o plano ax + 
by + cz + d = 0 e o ponto P2 é:
 Expandindo o numerador:
Testando um Ponto contra o 
Plano
 Finalmente, a expressão para calcular a 
distância de um ponto a um plano é:
Note que a fórmula para obter a distância 
parece a inserção do ponto P2 na equação 
do plano seguida de uma divisão pelo 
comprimento do vetor normal.
Testando um Ponto contra o 
Plano
 Por exemplo, a distância do ponto (-1, -2, 
-3) ao plano x + 2y + 2z – 6 = 0 é:
 Note que a distância pode assumir 
valores negativos. 
 Se D < 0, o ponto está no lado oposto ao da 
normal ao plano (o ponto está dentro do 
poliedro).
 Se D > 0, o ponto está no mesmo lado que o 
da normal ao plano.
BSP-Tree
 Cada nó interno representa um plano que 
particiona o espaço, com dois ponteiros 
(um para o lado de dentro e outro para o 
lado de fora).
 O plano de subdivisão pode ter qualquer 
posição e qualquer orientação.
 Isto pode reduzir a profundidade da árvore e o 
tempo de busca, se comparada à octree.
BSP-Tree
BSP-Tree X Quadtree
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25