Download Algoritmos de Visibilidad

Algoritmos de Visibilidad
 BASADOS EN LA IMAGEN:
Para cada pixel en la imagen determinar objeto visto más cercano dibujar pixel al
color apropiado.
o Z-buffer (coherencia de profundidad)
Es el más popular, y es el que viene implementado en la mayoría de las tarjetas
gráficas.




Usa dos memorias:
o Memoria profundidad
o Memoria color
Pre proceso
o Inicialización memorias
Proceso
o Conversión desordenada de polígonos
o Comprobación de cercanía y actualización
Características destacables
o No precisa ordenación
o Maneja todo tipo de escenas
o Dimensión de la memoria
Algoritmo:
Inicializar imagen a color del fondo
Inicializar zbuffer a la z de máximo alejamiento
Para cada polígono
Para cada píxel en la proyección del polígono z:=z(x,y) si z más
cercana que zbuffer(x,y) zbuffer(x,y):= z
Escribir píxel (x,y) al color conveniente

Ventajas del método:
o El tiempo de ejecución no depende de la complejidad de la escena, sino
sólo de su parte visible.
o Puede utilizarse cualquier tipo de objeto
o No se necesitan algoritmos de intersección
o Óptimo para ser implementado en hardware
o Rastreo de Línea
Si se intersecta la escena con un plano horizontal, correspondiente a una línea de
barrido (scan-line) de la pantalla, y aparecen polígonos 2D.
Ahora para esa línea, obtenemos varios intervalos -> SPANS.
Para cada span:
1. Si no contiene ningún elemento -> pintamos color de fondo
2. Si sólo contiene 1 segmento -> pintamos del color de ese polígono
3. Si hay más de 1 segmento -> pintamos con el color del más cercano
Para calcular cuál, testeamos la componente z en la mitad del span
X = (x4 + x5) / 2
Z = f (x, yk)
El algoritmo anterior es rápido y potente, pero ineficiente, pues en cada línea de
barrido debe calcular la intersección del plano con toda la escena.
o Warnock
Para decidir sobre pintar o subdividir un área hay 4 casos:
1.- Todos los polígonos son disjuntos respecto al área. Con el color de fondo se
puede pintar el área.
2.- Sólo hay un polígono intersecantes o contenido.
3.- Hay un solo polígono que interseca al área y es circundante.
4.- Hay varios polígonos intersecantes, uno de ellos es circundante y está enfrente
de los demás polígonos. Esto se controla con los valores z de los polígonos en los
4 vértices del área.
Existen estas 4 posibles relaciones entre Polígono y Elemento de Área (o trozo de
ventana):
Aquí se muestran los puntos de intersección de cada polígono respecto a los 4
vértices del área proyectada:
En este caso se subdivide el área. La reacción es diferente al algoritmo de
ordenamiento por profundidad, ya que en este no sería necesario subdividir.
 BASADOS EN LOS OBJETOS:
Para cada objeto en la escena determinar partes visibles comparándolo con el resto
dibujar partes visibles.
o Orden de profundidad
Es un procedimiento de resolución automática del problema de visibilidad cuando
se conocen las prioridades de cada polígono.
Los polígonos se ordenan de menor a mayor prioridad, y se van dibujando en ese
orden.
El color de cada pixel corresponderá al del polígono dibujado en último lugar.
Funciona muy bien cuando se tienen objetos de distinto tipo, cada uno con su propio
algoritmo de visibilidad.
Conociendo su prioridad relativa, se pueden dibujar por orden, cada uno con su
algoritmo.
La gran desventaja es que existen pixeles en la imagen que han sido pintados varias
veces.
La gran ventaja es que no hay que calcular las múltiples intersecciones entre los
polígonos de la escena.
o Particionamiento Binario del Espacio (BSP)
Aquí se tienen 5 objetos. Se toma uno como raíz y se subdivide el espacio en dos
(front y back). Paralelamente se genera una estructura de árbol donde se
especifican qué objetos están en qué semiespacio.
Luego, en uno de los semiespacios se hace la misma tarea. Se toma un elemento
raíz y se subdivide el semiespacio en dos. Paralelamente se construye la estructura
de árbol. Se continúa hasta que haya un objeto por nodo.
Posible subdivisión espacial y árbol final.
Luego de construido el árbol, lo que interesa es que rápidamente se puedan dibujar
los polígonos en el orden correcto según la posición del observador.
Se recorre el árbol recursivamente. Se comienza por la raíz. Cómo el observador
está detrás del polígono 3 (observe la normal) entonces el orden correcto es:
recorrer primero el subárbol front, luego pintar el polígono raíz y luego recorrer el
subárbol back.
Siga el algoritmo y verá que se pintan todos los polígonos en el orden correcto. El
algoritmo es de orden n, luego de hallado el árbol.
Otra posible subdivisión espacial y árbol final.