Quadtrees
• Estructura de árbol (cuatro descendientes).
• Se basa en la subdivisión recursiva de una estructura
cuadrada en cuadrantes.
• Cada nodo representa una región cuadrada del plano.
h = vacío
i = triángulo
b = circunferencia
l = rectángulo
h = vacío
i = triángulo
b = circunferencia
l = rectángulo
Otra
forma
de
subdividir el espacio:
• Menor espacio en
memoria
Octrees
• Extensión en 3D de
la estructura
quadtree.
• Estructura de árbol
(8 subnodos).
• Cada división
corresponde a un
octante.
Octrees
• La subdivisión espacial se debe realizar en función
de la resolución deseada.
• Las zonas sin objetos no hace falta dividirlas.
• Sólo tiene en cuenta los límites del objeto.
• En general, una hoja del árbol puede tener una lista
de objetos.
Arboles BSP
• Partición binaria del espacio mediante planos.
• Estructura de árbol (binario).
• Se adecua al ray tracing. El camino recorrido por un
rayo se traduce en movimientos por la estructura del
árbol, y en cada nodo habrá que testear si el rayo
intersecta con los objetos que hay en esa zona.
Arboles BSP
• Subdivisión adecuada:
– El plano para la división puede ser cualquiera.
– Se obtienen
profundidad.
árboles
más
equilibrados,
de
menor
Subdivisión de la escena normal:
La profundidad máxima
del árbol es de 8
- = vacío
Subdivisión de la escena adecuadal:
La profundidad máxima
del árbol es de 4
E x actitu d
C o n cisa
In v arian te afin
F ácil ad q u isició n
V alid ació n g aran tizad a
O p eracio n es b oo lean as eficien tes
V isu alizació n eficien te
V o x el
No
No
No
P o ca
Sí
Sí
No
O ctree
No
No
No
P o ca
Sí
Sí
No
BSP
P o ca
No
Sí
No
Sí
Sí
Sí
CSG
P o ca
Sí
Sí
P o ca
No
Sí
No
Obtención de la imagen mediante B-rep
• La entrada es una lista de polígonos, la salida un
conjunto de pixels coloreados.
• Se pasan distintos sistemas de referencia.
• Los objetos tienen su sistema de referencia.
• Todos se introducen en un mundo con el sist. de ref.
de la escena.
• En ese sistema se especifican las luces, el observador
....
• Se establece el sistema de referencia del observador.
Sistema de referencia del
objeto
Sistema de referencia del mundo
Completar la escena
Definición del objeto
Definir el sistema de referencia del
observador
Colocar las luces
Espacio 3D
Ventana del plano de
proyección
Eliminación de partes
ocultas
Discretización
Ilumimación
Espacio 2D
Sistema de referencia del observador
Eliminación de caras traseras
Limitar todos los objetos de la
escena con respecto al volumen de la
vista
Sistema de
referencia del
objeto
Sistema de referencia
del mundo
Define el sistema de
referencia del observador
Obtención de la imagen mediante B-rep
• Se pasa la escena al Sist. de Ref. de la cámara, se
eliminan caras traseras y se realiza el recorte.
• Se eliminan las partes ocultas y se calcula la
iluminación.
• Al final se pasa a pixels.
• Los últimos pasos se pueden dar de muy distintas
formas, hay muchos algoritmos.
Después del cambio de sistema de
referencia, pasamos al sistema de
referencia del observador
Eliminación de
partes ocultas
Sistema de
referencia del
observador
Se eliminan caras traseras
Transformación de perspectiva
Espacio 3D
Cálculo de la
iluminación
Dibujo en la
pantalla
Obtención de la imagen de los parches
• Lo más fácil es pasar los parches a polígonos.
• Estos objetos los crea el usuario de forma interactiva,
pero la traducción nos permite obtener la imagen
mediante B-Rep.
• El número de polígonos supera al de parches.
• La traducción se realiza en dos fases:
– Traducción a Bézier y subdivision de Bézier.
– Posterior traducción de Bézier a polígonos.
• Para terminar la subdivisión hay que establecer
condiciones de planaridad.
Aplicar la subdivisión de
los parches, hasta obtener
los parches tan cuadrados
como se quiera
Obtención de la imagen de CSG
• Aunque la creación de objetos sea fácil la obtención
de la imagen es complicada.
• El problema radica en la obtención de los bordes del
objeto. Tres técnicas:
1. Ray-tracing para CSG.
2. Trasladar de CSG a voxel y utilizar alguna técnica para
volúmenes.
3.Utilizar Z-buffer.
Objeto básico
Rayo propagado desde un pixel
Objeto básico
Descargar

Representación