Determinación de cara oculta
En gráficos por computadoras la determinación de las caras ocultas (HSR por sus siglas en inglés), también conocida como determinación de las superficies visibles (VSD), es el proceso usado para determinar que superficies y partes de superficies son visibles o no desde algún punto de observación.
Desde el inicio de los gráficos por computadora, muchas investigaciones se han enfocado en la obtención de realismo físico en la imagen generada. Sin embargo generar imágenes realistas tiene un precio. Los algoritmos para alcanzar estos resultados son costosos en el sentido computacional, razón por la que hasta hace unos pocos años solo podían incluirse en supercomputadoras o computadoras con hardware gráfico de carácter muy específico. Durante mucho tiempo las simulaciones tridimensionales, o se hacían en las computadoras antes mencionadas, o los programadores y diseñadores tenían que hacer un esfuerzo extraordinario para lograr que quien emplease la tecnología sobre una computadora de prestaciones comunes, no se sintiese defraudado por el bajo nivel de los gráficos.
Hoy día existe una situación diferente. La posibilidad de presentar gráficos en tiempo real es una realidad para las computadoras personales. Un resultado importante, ha sido la aparición de tarjetas aceleradoras gráficas. Estos dispositivos descargan, de manera considerable, el trabajo que hasta este momento se realizaba en el microprocesador de la computadora (CPU) a través de procesos gráficos implementados en software (software rendering).
La selección por visibilidad ha sido un problema esencial en gráficos por computadora desde sus inicios. Una variedad de algoritmos de HSR fueron desarrollados en los años 70, para resolver el problema de la determinación de secciones visibles de los objetos en la imagen final. El problema en la actualidad se considera resuelto y para la mayoría de las aplicaciones interactivas el algoritmo de selección es el: z buffer.
En la actualidad el tema es retomado por la imposibilidad de representar grandes bases de datos 3D en tiempo real. Las mejoras que se han realizado al hardware, no resuelven este problema, ya que el aporte nunca será suficiente ante el crecimiento de las bases de datos 3D. La solución a este problema es tener un gasto de cálculo solo para lo que será finalmente representado y no en dependencia de todos los datos de entrada. Lo anterior es conocido como sensibilidad a la salida (output sensitivity). De esta forma, es posible, representar escenas con alto número de polígonos, cumpliendo con las exigencias de tiempo real.
Técnicas para la eliminación de las caras ocultas
La selección por visibilidad puede ser dividida en: selección de objetos que se encuentran dentro del prisma de visión (view frustum culling), selección por caras ocultas (back face culling), variación del nivel de detalle (detail culling) y selección por oclusión (occlusion culling), encargada de eliminar objetos ocultados por otros objetos para el observador. En casos de interiores es utilizada una restricción del campo de observación al dirigirse la visión a través de una puerta o una ventana. Esta restricción se denomina técnica de portales, (portal culling).
Selección por prisma de visión
La selección por prisma es una representación geométrica del campo de visibilidad de la cámara. Naturalmente los objetos fuera de este prisma no serán visibles en la imagen final, por tanto serán descartados.
Selección de caras visibles
En la selección de caras visibles se tiene en cuenta que algunas caras de los objetos o polígonos de la malla no son visibles desde la cámara por lo que no hay razón para que sean dibujadas. Esta es la razón por la que algunos videojuegos si acercamos la cámara dentro de algún objeto de la escena este desaparece.
Selección por oclusión
Los objetos que se encuentran ocultados totalmente por otros objetos opacos pueden ser excluidos de la imagen final. Este es un mecanismo muy popular para aumentar el rendimiento del rendering de grandes escenas. Debido a su importancia y aplicación de esta última categoría, se profundizará un poco más en la siguiente sección.
Selección por Oclusión
Occlusion Culling desde una región vs Occlusion Culling desde un punto
Los algoritmos de oclusión pueden ser clasificados como from-point y from-region. Los algoritmos desde un punto calculan la visibilidad respecto a la posición y a la dirección en la que mira el observador, mientras que desde una región calculan la visibilidad que es válida para un área o volumen. Una de las mayores ventajas de la visibilidad desde una región es que la visibilidad puede ser precomputada y almacenada para su uso. Sin embargo tiene la desventaja de requerir almacenar gran cantidad de información.
Algoritmos de Espacio Imagen vs Algoritmos de Espacio Objeto
La idea de un algoritmo de visibilidad es realizar una eliminación rápida y conservativa de aquellas partes de la escena que no son visibles. Los algoritmos de espacio objeto son aquellos que realizan cálculos geométricos en la escena y determinan cuando un objeto es visible o no. Este tipo de algoritmo es muy utilizado para realizar pruebas de visibilidad en entornos urbanos. Es muy común seleccionar polígonos que realizarán función de oclusores. Para reducir los cálculos se realiza una aproximación de los oclusores utilizando bounding volumes que no son más que objetos con geometrías simples como prismas o esferas que contienen al objeto real.
En muchas ocasiones el entorno donde será usado el algoritmo influye en la manera en que este es diseñado. Los métodos de espacio objeto pueden ser considerados sensibles a la salida, que no son más que aquellos que su costo temporal depende solo del tamaño de la salida no del tamaño de la entrada. En el caso de los algoritmos de espacio imagen, la idea fundamental es realizar el cálculo de visibilidad para cada frame. Estos, tienen la ventaja de actuar en un arreglo de resolución finita lo que ofrece mayor facilidad de implementación y robustez que los algoritmos de espacio objeto. Otra gran ventaja de estos métodos es que no tienen limitaciones en cuanto a la forma de los bloqueadores, cualquier objeto puede ser representado y utilizado para la oclusión. Una de las primeras técnicas de espacio imagen fue el algoritmo de z buffer jerárquico. Esta solución, se basa en el z buffer común, pero utiliza dos estructuras de datos jerárquicas: Un octree y una pirámide de valores z.
Online vs Offline Occlusion Culling
Las pruebas de oclusión son llevadas a cabo durante la visualización (en línea) o antes de la visualización (offline). Los algoritmos en línea calculan la visibilidad en ejecución por lo que su escalabilidad es limitada si no se emplean técnicas geométricas de reducción. Los algoritmos offline calculan la visibilidad respecto a una región dividiendo el área en celdas. Estos algoritmos realizan cálculos de visibilidad y almacenan conjuntos de visibilidad para cada región (celda) del área. Esta manera de preprocesar información puede ser almacenada para su uso posterior. El poder de los algoritmos offline depende del tamaño escogido para la celda de visibilidad.
Occlusion Culling conservativo, aproximado y exacto
Los algoritmos de oclusión pueden ser clasificados como conservativos, aproximados y exactos. En el caso de los conservativos pueden seleccionar objetos que sean invisibles como visibles pero nunca deben seleccionar un objeto visible como invisible. Para los entornos urbanos esta es una aproximación bastante usada. Los algoritmos de visibilidad aproximados renderizan las primitivas visibles hasta un umbral especificado, es decir algunas no serán enviadas al motor gráfico mientras no sean visibles. Por último están los algoritmos exactos. Estos determinan exactamente que objetos son visibles realmente a expensas de un empeoramiento del costo temporal y espacial.
Algoritmos de oclusión para entornos específicos
Existen algoritmos de oclusión desarrollados para entornos específicos, como escenas interiores, escenas exteriores y entornos generales sin definición semántica para los objetos. En todos los algoritmos el área navegable es organizada con el objetivo de realizar las pruebas de oclusión lo más eficiente posible. En el caso de escenas interiores la escena dividida en habitaciones y son desarrolladas técnicas especiales como el uso de portales. En el caso de entornos urbanos los cálculos son realizados en áreas limitadas. Los algoritmos generales pueden ser usados en cualquier entorno realizando mayores o menores cambios pero los mejores resultados se obtienen utilizando algoritmos específicos al entorno.
Bibliografía
- Guzman, Jose Ignacio (2004). Visibilidad por regiones en zonas urbanas para Simuladores de Conducción.
- Wonka, Peter. Visibility Preprocessing with Occluder Fusion for Urban Walkthroughs. Vienna University of Technology.
- WU, SHIN-TING. Dynamic Scene Occlusion Culling using a Regular Grid.