ALGORITMOS DE VISIBILIDAD

ALGORITMOS DE VISIBILIDAD

• BASADOS EN LA IMAGEN

• Z-BUFFER

Las partes visibles de una escena se pueden descubrir haciendo un arreglo con las distancias desde el observador hasta la superficie mas cercana por cada pixel del plano de visión.

La “profundidad” se mide la coordenada z. Por cada objeto que forma parte de una escena, por cada cara que forma parte del objeto y por cada punto (x,y,z) de la cara , calcular su profundidad z y compararla con la almacenada en el buffer Z para el correspondiente (x,y), si la profundidad del punto es menor, reemplaza a la del buffer Z.

Los valores de profundidad de una cara se pueden obtener a partir de la ecuación del plano correspondiente a esa cara mediante la siguiente formula: 

A continuación se muestra un ejemplo mas detallado para la comprensión de este algoritmo: 

• RASTREO DE LINEA (SCAN LINE)

Es una extensión del algoritmo de rasterizado ya que, mientras se avanza a lo largo de una línea de scan, permite 

• Determinar las superficies que se proyectan a un pixel.

• Elegir la más cercana de un determinado subconjunto de éstas

Este algoritmo consta de los siguientes pasos:

1. Se crea una tabla de aristas
1. Cada arista viene representada por cinco valores 
1. Coordenada y del punto mas alto
2. Coordenada x del punto mas bajo 
3. Inversa de la pendiente
4. Identificador del polígono
5. Puntero a otra arista en la misma scan-line

1. Se crea una tabla de poligonos
1. Identificador
2. Ecuación del plano
3. Color
4. Flag in/out

1.  Se crea un vector vacío, con tantas posiciones como filas tenga la pantalla, y se coloca cada arista en la posición de la scan-line del punto más bajo:

Otra forma es: 

Como se interfecta la escena con un plano horizontal, correspondiente a una scan-line aparecen poligonos en 2D, para esta linea se obtienen intervalos.

Para cada Intervalo:

• Si no contiene ningún elemento: pintamos el color de fondo.
•  Si sólo contiene 1 segmento: pintamos del color de ese polígono.
• Si hay más de 1 segmento: pintamos con el color del más cercano.
• Para calcular cual:

• WARNOCK

Es un algoritmo de determinación de caras ocultas. como solución al problema de visualización de imágenes complicadas por subdivisión recursiva de una escena hasta que las áreas obtenidas sean fácilmente calculables. En otras palabras, hasta que la escena sea tan sencilla que permita calcular eficientemente su visualización. 

Hay cuatro formas en las que puede estar visible un polígono o los cuatro casos que nos van a permitir dividir o pintar un área:

1. Todos los polígonos son disjuntos respecto al área. Con el color de fondo se puede pintar el área.

1. Sólo hay un polígono intersecante o contenido. 

1. Hay un solo polígono que intersecta al área y es circundante.

1. 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.

Subdivisión recursiva: 

•  El rectángulo inicial comprende todos los pixeles.
• La lista inicial comprende todos los polígonos 
• Si se puede resolver la visibilidad para un rectángulo y unos polígonos, se resuelve (se asigna color a los pixeles del rectángulo) 
• En caso contrario, el rectángulo se divide en cuatro sub-rectángulos 
• Se calculan las listas de polígonos de cada sub-rectángulo 
• Se invoca recursivamente al algoritmo para cada sub-rectángulos

Casos posibles:

A cada llamada, se consideran los polígonos y el rectángulo:

1. Si todos los polígonos son disjuntos se rellena el rectángulo con el color del fondo.
   
2. Si hay un polígono que rodea el rectángulo, entonces el rectángulo con el color del polígono. 
   
3. Si solo existe un polígono incluido en el rectángulo, se rellena con el color del fondo y después se dibuja el polígono.
   
4. Si solo existe un polígono que intersecta al rectángulo, se rellena con el color de fondo y después se dibuja la parte del polígono incluida en el rectángulo. 
   
5. Si hay varios polígonos que se intersectan, pero uno de los que rodea oculta a todos los demás, se rellena el rectángulo con el color de ese polígono.
   
6.  Si el rectángulo ocupa único pixel, se dibuja el pixel con el color del polígono que se proyecta en su centro.
   
7. Si no estamos en ninguno de los casos anteriores el rectángulo se subdivide en otros cuatro y se subdivide en otros cuatro y se aplica el mismo algoritmo a cada sub-rectángulo.  
   

• BASADOS EN EL OBJETO
• PARTICIONAMIENTO BINARIO

Un orden correcto de dibujo sería: todos los polígonos del grupo A, polígono P, todos los de B (ya que el plano que contiene a P separa completamente A de B) .

Recursividad y el árbol binario.

• El problema pendiente es seleccionar un orden para dibujar los polígonos de los grupos A y B. Para ello se aplica el mismo principio recursivamente. 
• El algoritmo BSP se basa en un árbol binario estático, que puede ser usado para cualquier punto de vista (no hay que modificarlo)
• El árbol tiene un polígono P en cada nodo. En el subarbol izquierdo de ese nodo, están los polígonos de un lado de P, y en el derecho los del otro lado.

En la imagen anterior se muestra la creación de un árbol a partir de los polígonos anteriores.  La función recursiva para crear el árbol se muestra en la imagen siguiente: