Graficación Computacional
11:
Representaciones de
Objectos 3D
Octrees
Octrees
Los octrees son estructuras de árbol usadas para representar
objectos sólidos binarios (pero es posible incluir atributos,
como el color de las componentes en la figura).
Son especialmente útiles en
aplicaciones que requieren vistas
de secciones transversales (“cross
sections”).
Los octrees se usan en particular
cuando el interior es importante, y
para objetos de forma muy
compleja pero que ocupan el
espacio de forma irregular,
dejando huecos.
Octrees y Quadtrees
Los octrees son una extensión del esquema de
representación 2D conocido como codificación de
quadtree. Es también un esquema de compresión.
Los quadtrees dividen una región cuadrangular del
espacio en cuatro regiones de igual área (cuadrantes),
repitiendo la subdivisión en cada cuadrante, hasta hallar
regiones homogéneas. La representación de estas
regiones se pueden entonces disponer en un árbol.
En 3D, los octrees subdividen un área cúbica en ocho
octantes de igual volumen.
Quadtree Ejemplo 2
Octrees
La codificación en quadtrees o en octrees permite reducir
la memoria dedicada almacenar una escena cuando hay
regiones de color constante (u otra característica de
homogeneidad).
Cada región componente de un octree se denomina
elemento de volumen o voxel.
Existen algoritmos rápidos para recorrer el árbol asociado
al octree y conocer el vecino de un voxel dado, en
cualquier resolución.
El despliegue de Ray tracing (trazado de rayos) se
beneficia de esta codificación, al permitir un avance
rápido de los rayos en zonas donde no hay detalles.
Octrees (cont…)
Elementos codificados
en un nodo del Octree
Región cúbica, subdividida
en 8 octantes
Octrees (cont…)
En 3 dimensiones las regiones se pueden considerar
homogeneas en términos de color, tipo de material,
densidad o cualquier otro tipo de características o
atributos.
Los voxels también pueden estar vacíos (por ejemplo:
atributo nulo).
El tamaño de los voxeles en un octree disminuye al
aproximarse a una frontera (es, decir donde hay cambio
de la característica que determina la homogeneidad).
La codificación es muy eficiente con objetos compactos,
y pobre cuando los objetos son muy irregulares (en
particular con los fractales).
Octrees: Ejemplo
Octrees
Voxeles: Arreglos de indice marginal
unsigned char ***V;
Descargar

Brian’s Graphics Lectures