Occlusion Culling (III de IV)

************************************************************************************************

Back-face culling

Frustum Culling

Occlusion Culling

Optimizaciones para el Occlusion Culling

************************************************************************************************

Por fin toca escribir sobre la técnica que puso nombre a esta serie de artículos XD, Occlusión Culling también es una técnica que podemos incluir dentro de los algoritmos de visibilidad, esta técnica intenta acelerar el rendimiento gráfico evitando que los objetos que van a ser eclipsados por otros sean enviados a la gráfica. Desde la técnica del back-face culling lo que se intenta siempre es enviar solo lo imprescindible a la tarjeta gráfica, ya que el principal cuello de botella actual se encuentra en el intercambio de información entre la CPU y la GPU.

Occlusion Culling-0

Se puede apreciar en la imagen superior que tanto a la izquierda como a la derecha, el resultado del render de la escena es el mismo (parte inferior de la imagen), sin embargo si miramos en la parte superior de la imagen, en el lado izquierdo solo se está enviando a la gráfica la habitación donde se encuentra la cámara mientras que en la parte derecha vemos que a la gráfica se envía todo.

(esta imagen de ejemplo no es demasiado buena ya que quien la reconozca sabe que es de unity 3D y que ellos tienen implementado el occlusion culling mediante un algoritimo de visibilidad espacial y no como vamos a explicar en este artículo, pero es que no he encontrado una imagen mejor XD).

¿Cómo funciona el occlusion culling?, bueno pues hasta hace tiempo se intentaba conseguir mediante algoritmos espaciales tipo BSP, QuadTree, kdtree. Pero actualmente tenemos soporte a nivel de hardware de nuestras GPUs para implementar la técnica de forma más eficiente. Las tarjetas gráficas actuales tiene un conjunto de instrucciones llamadas queries, las cuales nos informan del estado actual de la GPU, como por ejemplo cuanta memoria estamos consumiendo, que test tenemos activados en nuestro pipeline etc.

Estas instrucciones son algo muy potente ya que es como si tuviésemos una base de datos rellena tras cada render de la gráfica y mediante queries podemos conocer datos internos que solo están en la GPU.

La query en la que nos apoyaremos para implementar la técnica de Occlusion Culling se llama Occlusion query, mediante esta instrucción podemos saber cuantos pixeles a nivel de raster de la imagen final han sido coloreados de un objeto concreto.

675px-Raster_graphic_fish_40X46squares_hdtv-example

Esto lo utilizaremos para determinar si un objeto ha sido eclipsado que ocurrirá cuando el número de pixeles devuelto por la query sea 0. Pero la query es algo que podemos lanzar a posteriori por lo que ¿cómo nos ayudará esto a acelerar el render? ya que nosotros necesitamos saberlo a priori. El siguiente seudocódigo nos ayudará a aclararnos un poco:

1- Ordenamos los objetos de delante hacia atrás con respecto a la posición de la cámara
2- Por cada objeto de la escena
    2.1- Occlusion Culling
        2.1.1 Iniciamos la query
        2.1.2 Desactivamos la escritura en el zbuffer y en el frame buffer, esto hace que el raster de la gráfica sea muy rápido.
        2.1.3 Renderizamos un volumen que represente una aproximación más simple del objeto (normalmente boundingbox).
        2.1.4 Preguntamos por el número de pixeles dibujados y esperamos la respuesta.
    2.2- Si el número de pixeles es mayor que 0, renderizamos el objeto.

El secreto está en que lo que renderizamos para determinar si un objeto será visible o no, es un volumen simplificado de nuestro objeto (un boundingbox), y que al haber desactivado la escritura en el zbuffer y el frame buffer el test será muy rápido, de todas formas a mayor complejidad de los modelos mayores serán los beneficios obtenidos. Si el test determina que un objeto hay que renderizarlo, activaremos la escritura en el zbuffer y en el frame buffer, de manera que esos datos quedará guardados en el zbuffer y los utilizaremos para las siguientes pasadas del test.

¿Cómo se desactiva la escritura del zbuffer y el frame buffer en XNA 4.0?

//Para desactivar la escritura en Zbuffer, permitiendo la lectura 

GraphicsDevice.DepthStencilState = DepthStencilState.DepthRead;

 

//Para desactivar la escritura en el framebuffer no existe un estado predeterminado dentro del BlendState

//Por lo que nos crearemos nuestro propio objeto blendState

BlendState blendState = new BlendState();

blendState.ColorWriteChannels = ColorWriteChannels.None;

 

//Posteriormente solo tendremos que asignarlo donde lo deseemos

GraphicsDevice.BlendState = blendState;

¿Cómo restaurar la escritura en el zbuffer y frame buffer?

GraphicsDevice.BlendState = BlendState.Opaque;

GraphicsDevice.DepthStencilState = DepthStencilState.Default;

¿Cómo se realiza una occlusion query en XNA?

//Creamos el objeto query

OcclusionQuery query = new OcclusionQuery(GraphicsDevice);

 

//Inicializamos la query

query.Begin();

 

    //Draw BoundingBox

 

query.End();

 

//Esperamos a que se realize la query

while (!query.IsComplete);

 

if(query.PixelCount > 0)

 

    //Draw object

 

Aquí os dejo un video de una implementación que realizé en XNA para XNACommunity sobre esta técnica, el código lo analizaremos en el siguiente post ya que en el se aplican varias técnicas para optimizar esta técnica.

Occlusion Culling (II de IV)

************************************************************************************************

Back-face culling

Frustum Culling

Occlusion Culling

Optimizaciones para el Occlusion Culling

************************************************************************************************

Frustum Culling: Es otra de las técnicas de visibilidad más usadas ya que es muy simple de implementar, consiste en no enviar a la tarjeta gráfica aquellos objetos que queden fuera del volumen de render de la cámara llamado Frustum.ViewingFrustum

Como podemos ver en la imagen de arriba, se le llama frustum al trozo de pirámide encerrado entre dos planos, near plane y far plane. Todo lo que está dentro de este volumen será dibujado por la tarjeta gráfica, y todo lo que quede fuera será descartado. La mejora de rendimiento que obtendremos con esta técnica esta en no esperar a que la tarjeta gráfica descarte los objetos que estén fuera del frustum perdiendo un tiempo valioso en transferir la información de estos objetos a la GPU, sino detectarlo en CPU.

El frustum de la cámara queda determinado por las matrices de view y projection de una cámara, es muy importante para el futuro rendimiento de nuestro juego que el frustum de la cámara tenga el tamaño optimo. Es decir, el near plane tiene que estar cerca de la cámara y el far plane tiene que estar a una distancia optima, si el far plane se coloca demasiado lejos estaremos dibujando más de lo necesario y si lo situamos demasiado cerca nuestros jugadores verán como van apareciendo polígonos en el horizonte. Antiguamente esto era un serio problema ya que no tenían las GPU de hoy en día entonces siempre si intentaba afinar mucho con el far plane, para evitar que los jugadores viesen como se iba generando el escenario por ejemplo en juegos de rally, el circuito estaba lleno de curvas que impedían ver más allá de la siguiente curva, en otros juegos utilizaban el fog para disimular esto.

Bueno una vez que tenemos el frustum solo nos queda calcular la intersección entre los objetos del escenario con dicho volumen.

view.frustum.culling

 

Pero para hacer más eficiente el test no se realiza una comprobación a nivel de polígono, sino que envolvemos cada uno de nuestros modelos en BoundingBox o BoundingSphere y realizamos el test con estos volumenes simplificados.

220px-BoundingBox

Por lo que a mayor poligonación de los elementos de nuestro juego mayor será la optimización realizada, para que esta técnica nos dé un buen resultado los elementos de nuestro juego de ven ser de un tamaño mediano. Por lo que si tenemos algún elementos muy grande lo partiremos en trozos y a cada trozo le asignaremos un BoundingBox o BoundingSphere.

El código en XNA podría ser algo así:

Matrix view = Matrix.CreateLookAt(new Vector3(0, 0, -10), Vector3.Zero, Vector3.Up);

float aspectRatio = (float)graphics.PreferredBackBufferWidth / graphics.PreferredBackBufferHeight;

Matrix projection = Matrix.CreatePerspectiveFieldOfView(MathHelper.PiOver4, aspectRatio, 1, 1000);

 

BoundingFrustum frustum = new BoundingFrustum(view * projection);

 

foreach (Model model in models)

{

    foreach (ModelMesh mesh in model.Meshes)

    {

        if (frustum.Contains(mesh.BoundingSphere) != ContainmentType.Disjoint)

        {

            //Draw

        }

    }

}      

Podemos mejorar el rendimiento de esta técnica utilizando estructuras de subdivisión de espacio como  QuadTree, OcTree ó KdTree, ya que sino el 90% del test estaremos comprobando intersecciones entre objetos que no serán dibujados.

Octree2

 

Esta mejora consiste en hacer agrupaciones jerárquicas de los elementos de la escena, de manera primero haremos comprobaciones de los boundingbox que representan a conjuntos de objetos, si descartamos alguno nos habremos ahorrado calcular la intersección de todos los elementos que contiene.

Aquí os dejo un pequeño video que muestra el resultado de esta técnica y como podemos optimizarla realizando agrupaciones jerárquicas:

Occlusion Culling (I de IV)

************************************************************************************************

Back-face culling

Frustum Culling

Occlusion Culling

Optimizaciones para el Occlusion Culling

************************************************************************************************

Hacía tiempo que no escribía y me alegra que el regreso sea con un tema tan interesante como el Occlusion Culling. Esta técnica podríamos clasificarla dentro de las técnicas de visibilidad para mejorar el rendimiento del render, y se suele usar junto a muchas otras técnicas de visibilidad conocidas, como el frustum culling o el back-face culling.

Back-face Culling: En esta técnica el objetivo es detectar cuales son las caras o polígonos de un objeto que no serán vistos desde la posición actual de la cámara (no se usará con objetos transparentes). De forma que dichas caras no serán dibujadas y por lo tanto reduciremos el coste en tiempo del render, sobre todo para objetos complejos donde podamos descartar gran cantidad de polígonos.

¿Y cómo funciona?, se obtiene la normal de una cara la cual puede tenerse ya almacenada tras la carga del modelo o se puede calcular usando el producto vectorial de dos aristas de la cara, después estudiaremos el signo del producto escalar entre dicha normal ( N ) y el vector de vista del observador ( L ), si el signo es “=” ó “> 0” significa que el ángulo formado por estos vectores es mayor o igual a 90º, lo que indicará que no será visible al observador y podremos descartar el polígono.fres-01

Esta técnica a día de hoy viene ya integrada dentro de la funcionalidades de las tarjetas gráficas y se realizan en uno de los estados del Pipeline llamado Geometry Processing, por lo que se realizar a nivel del hardware y por lo tanto es muy rápido, el ahorro se produce para las caras que no pasen el test ya que no llegarán al estado de Pixel Processing ahorrandonos por tanto el tiempo en rasterizar, y texturizar el polígono. El rendimiento obtenido crece con la complejidad de la escena y se acentúa cuando los shaders usados son muy complejos.

En XNA 4.0 esta técnica viene activada por defecto pero podemos configurarla a nuestro antojo, su funcionalidad viene encapsulada dentro de RasterizerState:

RasterizerState raster = new RasterizerState();

raster.CullMode = CullMode.CullCounterClockwiseFace;

CullMode tiene 3 posibles valores, estos tienen que ver con el sentido de las normales de las caras de un modelo, (CullCounterClickwiseFace es el valor que XNA asigna por defecto).
normal
Pongamos un ejemplo, esta cara ha sido expresada con los vértices en un orden determinado v1,v2,v3, es decir en sentido contrario a las agujas del reloj, si un triángulo lo expresamos de esta forma su normal queda hacia arriba siguiendo la regla de la mano derecha.
 
Right_hand_rule_simple
Si los vértices los expresamos en otro orden por ejemplo v1, v3, v2, la normal apuntaría hacia abajo siguiendo también la regla de la mano derecha, de esta manera también se determina desde que parte del espacio se verá un triangulo, esto tan simple puede provocarnos grandes quebraderos de cabeza.
 
– CullClockwiseFace : Los vértices de un polígonos han sido expresados siguiendo él sentido de las agujas del reloj.
– CullCounterClockwiseFace : Los vértices de un polígono han sido expresados siguiendo el sentido contrario de las agujas del reloj.
– None: Queremos que nuestros polígonos sean dibujados por ambos lados por lo que desactivamos el back-face culling.
 
En la siguiente imagen podemos ver el back-face culling en acción, a la izq tendríamos CullMode = None y en la derecha alguna de las otras dos posibilidades dependiendo de como hayan sido expresados los polígonos del objeto.
backfaceculling