Superficies Visibles

Dpto. de Informática Fac. Cs. Físico-Mat. y Nat. Universidad Nacional De San Luis Argentina

Simulación de la Apariencia – Superficies Visibles

Superficies Visibles Introducción 



 

En teorías anteriores se aprendió a transformar la geometría de modo que los tamaños relativos se conservaran al momento de descartar la coordenada z. La mayoría de los objetos en una escena son opacos. Una primer propuesta implica dibujar todas las caras de un objeto. No obstante, solo la cara que es visible al ojo debe ser realmente pintada. Cómo determinar cual es la geometría correcta con la que debe ser plasmado un objeto?

Correcta? Dpto. de Informática - Roberto Guerrero @ 2015

Correcta? 2

Simulación de la Apariencia – Superficies Visibles

Superficies visibles Definición del Problema 

Dado un conjunto de objetos 3D y una especificación de visualización (cámara), determinar qué líneas o superficies de un objeto son visibles.



Por qué es necesario determinar que objetos pueden no ser visibles? 

No se desea dibujar elementos que no se encuentran en el área de pintado.



No se desea perder tiempo.



Evitar innecesarios accesos a memoria.



Mejorar la apariencia.

Dpto. de Informática - Roberto Guerrero @ 2015

3

Simulación de la Apariencia – Superficies Visibles

Superficies visibles Recorte vs. Oclusión 

El recorte se realiza evaluando de a un objeto por vez, la oclusión es global.



Recorte:  



Remueve elementos no deseados dentro del área de pintado. Recorta vistas.

Oclusión: también conocida como Problema de Eliminación de Superficies Ocultas (Hidden Surface Elimination) o Problema de Determinación de Superficies Visibles (Visible Surface Determination). 

Maneja un conjunto diverso de primitivas geométricas. .

Dpto. de Informática - Roberto Guerrero @ 2015

4

Simulación de la Apariencia – Superficies Visibles

Recorte (clipping) Recorte de línea básico 

Recortar líneas según los lados de la región de recorte 

Si ambos extremos están fuera de la región, descartar y parar.



Si ambos están dentro de la región, aceptar y proseguir.



Si un extremo esta dentro y el otro fuera, recortar el extremo en el punto de cruce y proseguir. .

Dpto. de Informática - Roberto Guerrero @ 2015

5

Simulación de la Apariencia – Superficies Visibles

Recorte 

Funciona bien en 2D y 3D con regiones de recorte convexas.



Múltiples implementaciones :    

Cohen-Sutherland. Liang-Barsky. Sutherland-Hodgman. Weiler

Dpto. de Informática - Roberto Guerrero @ 2015

6

Simulación de la Apariencia – Superficies Visibles

Oclusión Reseña 

Problema establecido primeramente para el wireframe.

Casa canónica



Solución: Remoción de Líneas Ocultas 

nota: las líneas por sí mismas no ocultan líneas. Las líneas son bordes de superficies opacas que esconden líneas.



Algunas técnicas muestran a las líneas como segmentos punteados.

Dpto. de Informática - Roberto Guerrero @ 2015

7

Simulación de la Apariencia – Superficies Visibles

Pipeline de Rendering 3D Primitivas 3D Coordenadas de modelado 3D Transformación de Modelado Coordenadas de mundo 3D Transformación de Visualización Coordenadas de cámara 3D Transformación de Proyección Coordenadas de pantalla 2D Recorte Determinación de Sup. Visibles

Coordenadas de pantalla 2D Transformación de ventana Coordenadas de imagen 2D Digitalización imagen Dpto. de Informática - Roberto Guerrero @ 2015

Coordenadas de imagen 2D 8

Simulación de la Apariencia – Superficies Visibles

Determinación de Superficies Visibles Enfoques 

Primero: cual de los n objetos es visible en cada pixel de la imagen. for (cada pixel - determinar observador través del - dibujar el }



en la imagen) { el objeto mas cercano al que es tocado por un proyector a pixel; pixel con el color apropiado;

Segundo: comparar los objetos entre sí, eliminando objetos enteros o porciones de ellos que no son visibles. for (cada objecto en el mundo) { - determinar aquellas partes de objetos cuya visión es obstruida por otras partes propias o de otros objetos; - dibujar las partes visibles con el color apropiado; }

Dpto. de Informática - Roberto Guerrero @ 2015

9

Simulación de la Apariencia – Superficies Visibles

Determinación de Superficies Visibles Tres clases de algoritmos 





“Conservadores” - realizan un rechazo trivial. Se intenta formular técnicas inteligentes. No brinda una respuesta final! 

ej., recorte por volumen de visualización canónico, volúmenes envolventes, recorte de cara trasera.



bueno, usado para obtener resultados previos a otros algoritmos.

Precisión de Imagen – resuelve la visibilidad por medio de los puntos discretos de una imagen. 

muestrea el modelo, luego resuelve la visibilidad, es decir, resuelve que objetos tiene sentido evaluar.



ej, Z-buffer, buffer de profundidad de escaneo (ambos en hardware!), algoritmo del pintor, raytracing.

Precisión de Objeto – resuelve todas la posibles direcciones de visualización para un único punto de vista. 

independiente de la dirección de visualización o la densidad de muestreo.



resuelve la visibilidad con exactitud, luego muestrea lo resultante.



e.g., recorte de polígonos, ordenamiento por profundidad 3D, árboles BSP.

Dpto. de Informática - Roberto Guerrero @ 2015

10

Simulación de la Apariencia – Superficies Visibles

Determinación de Superficies Visibles Criterios de los Algoritmos 

Diferencias entre los algoritmos: 

cuál es la geometría a evaluar? triángulos vs. superficies implícitas



existen objetos transparentes?.



hay procesamiento de anti-aliasing?.



que porcentaje del escenario debe evaluarse?.



se debe pre-procesar el modelo?.



el algoritmo considera objetos que se desplazan?.



performance: complejidad espacio-tiempo. Con grandes modelos, la complejidad O(n) es baja

• Qué es n?, # total de objetos, # objetos visibles, # pixels…?



En el pipeline, usualmente se utiliza primero algún algoritmo conservador, luego uno de precisión de imagen o precisión de objeto.

Dpto. de Informática - Roberto Guerrero @ 2015

11

Simulación de la Apariencia – Superficies Visibles

Determinación de Superficies Visibles Explotar la Coherencia Es el grado por el cual las partes de un ambiente exhiben similaridades lógicas. Hace buenas suposiciones!. Reutiliza cálculos previos. 

Imagen: excepto en los bordes de los objetos, los pixels adjacentes tienden a pertenecer al mismo objeto. 



Objetos: los objetos no son nubes de puntos; ellos tienden a ser superficies continuas. 





el rasterizado (scan-line conversion) toma ventaja de esta característica.

el rasterizado (scan-line conversion) toma ventaja de esta característica.

Conjunto visible: el conjunto de objetos visibles no cambia a medida que el punto de vista se mueve incrementalmente (animaciones). 

la mayoría de los objetos no se mueven de frame a frame.



los objetos del fondo tienden a estar estáticos mientras que unos pocos objetos del frente se mueven (ventaja usada en los juegos).

Los objetos tienden a agruparse en el espacio. 

la subdivisión espacial toma ventaja de esta característica.

Dpto. de Informática - Roberto Guerrero @ 2015

12

Simulación de la Apariencia – Superficies Visibles

Determinación de Superficies Visibles Tres clases de algoritmos 





“Conservadores” - realizan un rechazo trivial. Se intenta formular técnicas inteligentes. No brinda una respuesta final! 

ej., recorte por volumen de visualización canónico, volúmenes envolventes, recorte de cara trasera.



bueno, usado para obtener resultados previos a otros algoritmos.

Precisión de Imagen – resuelve la visibilidad por medio de los puntos discretos de una imagen. 

muestrea el modelo, luego resuelve la visibilidad, es decir, resuelve que objetos tiene sentido evaluar.



ej, Z-buffer, buffer de profundidad de escaneo (ambos en hardware!), algoritmo del pintor, raytracing.

Precisión de Objeto – resuelve todas la posibles direcciones de visualización para un único punto de vista. 

independiente de la dirección de visualización o la densidad de muestreo.



resuelve la visibilidad con exactitud, luego muestrea los resultante.



e.g., recorte de polígonos, ordenamiento por profundidad 3D, árboles BSP.

Dpto. de Informática - Roberto Guerrero @ 2015

13

Simulación de la Apariencia – Superficies Visibles

Recorte por Volumen de Visualización 

 



Los poliedros transformados en el mundo normalizado, luego son recortados según los bordes del volumen de visualización canónico; un polígono por vez. Los polígonos son recortados de a un borde por vez. Los cálculos de intersección son triviales debido a la formulación del volumen de visualización. Es necesario crear nuevos vértices cuando los objetos son recortados. recorte

rechazo trivial (todos los vértices se encuentran fuera del volumen )



aceptación trivial (todos los vértices se encuentran dentro del volumen)

El uso de volúmenes envolventes permite rechazar grupos de objetos rápidamente.

Dpto. de Informática - Roberto Guerrero @ 2015

14

Simulación de la Apariencia – Superficies Visibles

Volúmenes Envolventes 



Los volúmenes envolventes (Bounding Volumes) intentan evitar recortes innecesarios, así como también innecesarias comparaciones entre los objetos y sus proyecciones: 

delimitar cada objeto complejo con un objeto simple – Ejemplo de volúmenes simples: esfera, cuboide, poliedro



si el volumen envolvente no es visible, tampoco lo es el objeto en su interior.



se pueden colocar varios objetos en un único volúmen: aumenta la eficiencia.



un volumen envolvente efectivo depende de la orientación y forma del objeto.

Muy bueno para el pipeline de harware tradicional! 

rechaza rápidamente un gran número de triángulos durante el proceso de recorte.



ej., si el volumen envolvente de una esfera poligonal no es visible, se rechaza directamente.

Dpto. de Informática - Roberto Guerrero @ 2015

15

Simulación de la Apariencia – Superficies Visibles

Jerarquía de Volúmenes Envolventes Una técnica para organizar la escena completa Dos métodos de construcción: 

En forma repetitiva agrupar volúmenes de objetos cercanos hasta que la escena completa se encuentra delimitada 



requiere de alguna forma de ordenamiento espacial.

Se puede utilizar un grafo de escena: volúmenes envolventes en los nodos = unión de volúmenes envolventes hijos 

fácil de realizar…



útil solamente si el grafo de la escena es espacialmente coherente (sino los volúmenes serán independientes).

A

root volume

C bbox A

B Dpto. de Informática - Roberto Guerrero @ 2015

A

bbox B

bbox C

B

C

16

Simulación de la Apariencia – Superficies Visibles

Recorte de Cara Trasera Interpretación de la línea de visión 







El enfoque considera los objetos como poliedros cerrados, con el ojo observando siempre desde afuera de ellos. Utiliza la normal del polígono (plano) de cada objeto (outward normal (ON)) en sentido dextrógiro, para el test de rechazo. La línea de visión (Line of Sight (LOS)), es el proyector que emana del centro de proyección (center of projection (COP)) hacia cualquier punto P del polígono. Si la normal se orienta en la misma dirección del LOS, entonces la cara es trasera: 

if LOS • ON > 0, then el polígono es invisible - descartar



if LOS • ON < 0, then el polígono puede ser visible

LOS = P - ojo

LOS ON

ON ojo

ojo Dpto. de Informática - Roberto Guerrero @ 2015

cara oculta en el contexto

sólo la cara oculta 17

Simulación de la Apariencia – Superficies Visibles

Determinación de Superficies Visibles Tres clases de algoritmos 





“Conservadores” - realizan un rechazo trivial. Se intenta formular técnicas inteligentes. No brinda una respuesta final! 

ej., recorte por volumen de visualización canónico, volúmenes envolventes, recorte de cara trasera.



bueno, usado para obtener resultados previos a otros algoritmos.

Precisión de Imagen – resuelve la visibilidad por medio de los puntos discretos de una imagen. 

muestrea el modelo, luego resuelve la visibilidad, es decir, resuelve que objetos tiene sentido pintar.



ej, Z-buffer, buffer de profundidad de escaneo (ambos en hardware!), algoritmo del pintor, raytracing.

Precisión de Objeto – resuelve todas la posibles direcciones de visualización para un único punto de vista. 

independiente de la dirección de visualización o la densidad de muestreo.



resuelve la visibilidad con exactitud, luego muestrea los resultante.



e.g., recorte de polígonos, ordenamiento por profundidad 3D, árboles BSP.

Dpto. de Informática - Roberto Guerrero @ 2015

18

Simulación de la Apariencia – Superficies Visibles

Algoritmos de Precisión de Imagen Idea básica   

Encontrar el punto visible más cercano a través de cada pixel de la imagen. Los cálculos se realizan acorde con la resolución de pantalla. No requiere gran precisión.

Complejidad 

Enfoque Naïve que chequea todos los n objetos en cada pixel. O(n, m2).



Mejores enfoques solo chequean los objetos que podrían ser visibles en cada pixel. Si en promedio d objetos son visibles en cada pixel, luego O(d, m2).

Implementación 

Muy simple de implementar 

Muy usado en la práctica para otros usos

Dpto. de Informática - Roberto Guerrero @ 2015

19

Simulación de la Apariencia – Superficies Visibles

Revisión de la Transformación en Perspectiva (TP) 

La TP preserva la relación “delante de”, las líneas rectas y los planos, recortándolos en perspectiva. (-1,1,-1)

(1,1,1)

ojo

(k,-k,-k)

(-1,-1,0)

-(z-near)/(far-near)

Volumen de visualización canónico de un cubo con proyección en perspectiva

antes de TP Dpto. de Informática - Roberto Guerrero @ 2015

ojo

Luego de TP al volumen de visualización paralelo normalizado, El cubo se distorsiona (TP transforma z desde [-1,0] a [0,1]).

después de TP 20

Simulación de la Apariencia – Superficies Visibles

Transformación en Perspectiva 

El recorte luego de TP es simple utilizando los planos definidos (-1 < x < 1), (-1 < y < 1), (0 < z < 1)



La comparación de profundidad antes de la TP –

– 

Si el par (x, y) de cada punto están en el mismo proyector, luego se evalúan las z

La comparación de profundidad luego de la TP —

—



comparar de a pares de puntos, P 1 y P 2 : realizar cálculos para determinar si ellos se encuentran en el mismo proyector

Comparar de a pares de puntos, P' 1 y P' 2 : x' debe =x ' 2 , y y' 1 debe = y' 2 para que uno de los puntos oculte al otro, 1 (muy simple si estan en el mismo proyector) Si los pares (x’, y’) de los puntos son iguales, luego se evalúan los valores de z

Luego de la TP simplemente se descartan los valores de z!

antes de TP Dpto. de Informática - Roberto Guerrero @ 2015

ojo

después de TP 21

Simulación de la Apariencia – Superficies Visibles

Revisión de Buffers 





Para solucionar el problema de parpadeo, la pantalla deber ser refrescada al menos 60 veces por segundo. La pantalla es refrescada a partir de información de pixel almacenada en un Frame Buffer o Buffer de Refresco. Buffers adicionales pueden ser utilizados para almacenar otro tipo de información de los pixels. Un z-buffer almacenará los valores de profundidad z de los pixels para poder realizar la determinación de superficies visibles.. monitor

disco duro

z-buffer con valores de profundidad de los pixels grises del frame buffer Dpto. de Informática - Roberto Guerrero @ 2015

frame buffer con pixmap

22

Simulación de la Apariencia – Superficies Visibles

Algoritmo del Z-Buffer 

Requiere 2 “buffers” Buffer de Intensidades — es el buffer de pixels RGB — está inicializado en el color de fondo Buffer de Profundidad (“Z”) — mantiene la profundidad de la escena en cada pixel — está inicializado a la máxima profundidad



Los polígonos son digitalizados en cualquier orden. Cuando los pixels se superponen, utilizar el Z-buffer para decidir que polígono se pinta en el pixel

Ejemplo utilizando un Z-buffer de enteros con near = 0, far = 255

Dpto. de Informática - Roberto Guerrero @ 2015

23

Simulación de la Apariencia – Superficies Visibles

Algoritmo del Z-Buffer

Ejemplo utilizando un Z-buffer de enteros con near = 0, far = 255 Dpto. de Informática - Roberto Guerrero @ 2015

24

Simulación de la Apariencia – Superficies Visibles

Algoritmo Z-Buffer 

Se dibuja cada polígono que no se puede rechazar trivialmente.



Si se encuentra una pieza que debe ser pintada (uno o más pixels), se pinta por encima de lo que existía en el buffer.

Dpto. de Informática - Roberto Guerrero @ 2015

25

Simulación de la Apariencia – Superficies Visibles

Z-Buffer Pros 

Simplicidad – permite su implementación en hardware! 

actualmente utilizado por todas las tarjetas gráficas



Los polígonos pueden evaluarse en cualquier orden. Paralelismo!!



Sólo se considera a los polígonos









...la oclusión sigue siendo un problema global!



Fuerza bruta, pero rápido!

El Z-buffer puede almacenarse junto con la imagen, permitiendo componer imágenes, en lugar de modificar escenarios (animación). 

gran beneficio para escenarios complejos



todos los algoritmos de VSD pueden generar un Z-buffer

Puede utilizarse con superficies no poligonales. CSGs (intersect, union, difference), any z = f(x,y). Se requiere procesamiento y memoria, aunque la imagen puede ser divida en su procesamiento..!!... paralelismo.

Dpto. de Informática - Roberto Guerrero @ 2015

26

Simulación de la Apariencia – Superficies Visibles

Z-Buffer Contras 

Problema de precisión: recorte por proyección en perspectiva 

la compresión del eje z producto de la TP



antes 



  

los objetos que originalmente se encuentran lejos terminan con valores de z cercanos y pequeños. se pierde precisión en la información de profundidad lo cual genera errores en el plasmado por objetos pequeños a la distancia. los polígonos co-planares muestran una “pelea de z” el uso de flotantes reduce el problema... no lo elimina.

No se puede realizar anti-aliasing  



después

requiere conocer todos los polígonos involucrados en un pixel (vecindario de polígonos). concepto de A-buffer para el tratamiento de anti-aliasing.

Algoritmo original evalua todos los objetos (aún no recortados) 

Z-buffering jerárquico (Greene & Kass SIGGRAPH ‘94).

Dpto. de Informática - Roberto Guerrero @ 2015

27

Simulación de la Apariencia – Superficies Visibles

Determinación de Superficies Visibles Tres clases de algoritmos 





“Conservadores” - realizan un rechazo trivial. Se intenta formular técnicas inteligentes. No brinda una respuesta final! 

ej., recorte del volumen de visualización canónico, volúmenes envolventes, recorte de cara trasera.



bueno, usado para obtener resultados previos a otros algoritmos.

Precisión de Imagen – resuelve la visibilidad por medio de los puntos discretos de una imagen. 

muestrea el modelo, luego resuelve la visibilidad, es decir, resuelve que objetos tiene sentido pintar.



ej, Z-buffer, buffer de profundidad de escaneo (ambos en hardware!), algoritmo del pintor, raytracing.

Precisión de Objeto – resuelve todas la posibles direcciones de visualización para un único punto de vista. 

independiente de la dirección de visualización o la densidad de muestreo.



resuelve la visibilidad con exactitud, luego muestrea los resultante.



e.g., recorte de polígonos, ordenamiento por profundidad 3D, árboles BSP.

Dpto. de Informática - Roberto Guerrero @ 2015

28

Simulación de la Apariencia – Superficies Visibles

Algoritmos de Precisión de Objetos Idea Básica 

Opera sobre los objetos en sí mismos. (Los objetos serán tratados como “primitivas”).



Los objetos comúnmente se interponen unos con otros.



El test se realiza a alto nivel.



La lista de objetos visibles puede luego ser plasmada en diferentes resoluciones.

Complejidad 

Para n objetos, computar la visibilidad puede llevar O(n2).



Para una pantalla (imagen) de m x m pixels, se debe evaluar m2 pixels.



La complejidad total sería O(kobjn2+ kdispm2).

Implementación 

Generalmente complejos.



Problemas numéricos.

Dpto. de Informática - Roberto Guerrero @ 2015

29

Simulación de la Apariencia – Superficies Visibles

Algoritmo de Precisión de Objeto Primeros enfoques 

Roberts ’63 – Remoción de Líneas Ocultas 

comparar cada lado con cada objeto, eliminando los lados invisibles o partes de lados.



los objetos deben ser poliedros convexos.



Complejidad: peor a O(n2) dado que cada objeto debe ser comparado con todos los lados.



Un enfoque similar para superficies ocultas: 

cada polígono es recortado usando las proyecciones de los otros polígonos por delante de él.



se eliminan las superficies invisibles y se crean sub-polígonos visibles.



lento, sin mucha precisión en casos particulares.

El polígono A es recortado por B que está enfrente de él. Un nuevo sub-polígono C es creado

Dpto. de Informática - Roberto Guerrero @ 2015

30

Simulación de la Apariencia – Superficies Visibles

Particionado Binario del Espacio (Fuchs, Kedem, and Naylor) 

Provee una subdivision espacial y orden de pintado



Divide y conquista: 

divide recursivamente el espacio en una jerarquía de semi-espacios, mediante la división de polígonos en esos semi-espacios, usando de referencia el plano del polígono.



construye un árbol BSP que representa la jerarquía.



Cada polígono seleccionado es la raíz de un sub-árbol.



Permite realizar pre-cálculos para procesamientos independientes del punto de vista (animaciones).

Dpto. de Informática - Roberto Guerrero @ 2015

31

Simulación de la Apariencia – Superficies Visibles

Particionado Binario del Espacio 



Para mostrar cualquier polígono correctamente: 

plasmar primero todos los polígonos que se encuentren por detrás (en relación con el punto de vista) del polígono, luego el polígono actual, luego todos los polígonos por delante.



cómo determinar el orden?. Elegir un polígono y procesar en forma recursiva.

Ejemplo:

BSP-0: Escenario Inicial Dpto. de Informática - Roberto Guerrero @ 2015

32

Simulación de la Apariencia – Superficies Visibles

Particionado Binario del Espacio BSP-1: Elegir cualquier polígono (ej. polígono 3) y subdividir los otros a partir de este plano. Subdividir polígonos cuando sea necesario.

BSP-2: Procesar el sub-árbol frontal recursivamente

Dpto. de Informática - Roberto Guerrero @ 2015

33

Simulación de la Apariencia – Superficies Visibles

Particionado Binario del Espacio

BSP-3: Procesar el árbol trasero recursivamente

BSP-4: un árbol BSP alternativo, utilizando al polígono 5 como raíz

Dpto. de Informática - Roberto Guerrero @ 2015

34

Simulación de la Apariencia – Superficies Visibles

Particionado Binario del Espacio 

Realizar el árbol BSP dependiente de la vista cada vez que el punto de vista cambia: 

los nodos pueden visitarse en orden back-to-front utilizando un recorrido modificado in-order del árbol.



En cada nodo, el lado negativo son los polígonos que estan en el lado en que no se encuentra el punto de vista del nodo.



muy rápido! Quake III utiliza este método para acelerar su evaluación de intersecciones.



BSP es creado en las coordenadas del mundo.

Dpto. de Informática - Roberto Guerrero @ 2015

35

Simulación de la Apariencia – Superficies Visibles

Particionado Binario del Espacio 

Ejemplo de un árbol BSP de una escena 3D:

back

Dpto. de Informática - Roberto Guerrero @ 2015

front

36

Simulación de la Apariencia – Superficies Visibles

Particionado Binario del Espacio

{back}

{front}

{front}

{back}

Dpto. de Informática - Roberto Guerrero @ 2015

37

Simulación de la Apariencia – Superficies Visibles

Particionado Binario del Espacio 

Ejemplo de un recorrido in order del árbol BSP de una escena 3D (utilizando la relación ojo – normal de la superficie, en cada cara):

a)

b) Dpto. de Informática - Roberto Guerrero @ 2015

38

Simulación de la Apariencia – Superficies Visibles

Modelo sin recorte

Dpto. de Informática - Roberto Guerrero @ 2015

Recorte de cara trasera

Recorte ideal

39

Simulación de la Apariencia – Superficies Visibles

Dpto. de Informática - Roberto Guerrero @ 2015

40