El scenegraph

El scenegraph es la parte que se encarga de definir nuestra escena. Es lo que modifica el juego o nuestra aplicación, y lo que usaremos para precalcular las listas, visibilidades, etc.

El scenegraph se basa en el patron visitor , que basicamente es un objeto que ejecuta un codigo para cada uno de los nodos. Lo que lo hace especial es que el objeto puede guardar datos entre cada "visita". Por ejemplo, podemos visitar la escena y contar cuantas luces hay, cuantas camaras, etc. Tambien podemos hacer algo despues de la visita de todos los nodos, como imprimir en pantalla el resultado final de nuestras cuentas. En el caso del scenegraph, visitamos todos los nodos, y sus hijos, y vamos agregando la informacion "raw" necesaria para rendear en lista. Al final, enviamos estas listas ya preparadas a quien se encarge de rendear.

Hay muchos errores que se suelen cometer cuando no se emplea un visitor. Por ejemplo, ir pintando mientras se recorre la escena. Eso es un error, porque si tenemos varios objetos con el mismo shader, pero no están directamente emparentados (por ejemplo, las hombreras y unos guantes de cuero), tendremos que pintar, primero las hombreras, después el brazo, después el codo, con lo que estaremos cambiando de contexto continuamente. Hacer un loadmatrix para un objeto es muy rápido para el driver y nos independiza el objeto del resto de la escena. Otro fallo que se comete es que cada objeto tenga su método Draw. Esto es otro error, porque si queremos pasar a modo wireframe, etc, tenemos que reescribir este método para todos los tipos de objetos (arboles, casas, coches, etc).

El concepto de scenegraph, entendido tradicionalmente como un grafo de estados jerárquicos es algo totalmente abandonado por ser incompatible con el modelo actual del driver gráfico. Por lo general cada nodo del scenegraph representa un estado entero y no un delta con respecto al padre. A mi me gusta pensar en una escena, como un conjunto de N objetos lineales y que en cada frame se decide cuales es van a ver (buenos algoritmos para esto suelen ser un kd-tree + hardware oclussion)

Cuando visitamos la escena, podemos ir haciendo otro tipo de listas que nos ayudaran a pintar despues. Por ejemplo, podemos hacer listas de luces que afecten al objeto (descartando las que estan lejos), podemos hacer listas de objetos que van a tener sobra (para el shadow map), etc. Para que sea rapido, es importante que la escena guarde algun tipo de estructura (como un grid uniforme) para que estas búsquedas sean rápidas.

Sobre la iluminación. A la hora de tratar las luces, hay que calcular cada uno de los sets de objetos necesarios. Cada luz suele tener una lista concreta de objetos que va a iluminar (manía de los artistas). Para ello es muy importante que nuestra escena tenga una estructura de datos que permita hacer consultas muy eficiente y de forma rápida. Por un lado tenemos el conjunto de objetos visibles, calculado mediante frustum culling y quiza hardware oclussion culling. Luego para cada luz, tenemos el conjunto de objetos a los que una luz afecta (usando el radio de la luz, fuera de ese radio, nunca recibiremos sombra de esa luz). La intersección de los objetos visibles por la camara y los objetos visibles por la luz determinan el conjunto de objetos receptores de una luz. El siguiente conjunto a calcular es el conjunto de "casters" de una luz. Este es mas complicado de calcular porque incluye objetos fuera de los objetos visibles (hay objetos que no se ven pero que arrojan sombra a los objetos visibles). Con todos estos cálculos, tenemos para cada luz, un conjunto de casters (se rendean en el shadow map) y un conjunto de receivers (emplean el shadow map. por ejemplo, un suelo es el típico ejemplo que lee del shadow map pero que no se pinta en el shadow map).

Lo ideal es agrupar los objetos por sets de luces para poder pintarlos de un tiron. Por supuesto, no todas las luces arrojaran sombra y por tanto es mas fácil de agrupar. Lo normal incluso es que a un objeto le caigan varias luces y le de distinta importancia a cada tipo de luz: las luces menos importantes se pueden colapsar en una única luz (promedio de ellas) y aplicarla a nivel de vértices, las luces mas importantes se pueden aplicar por pixel y las super importantes son las que castean sombras. La transición entre el conjunto de luces asociadas a un objeto y su importancia (que varia según las luces / objetos se acercan) es un problema que debe resolverse de una manera suave para evitar transiciones bruscas.

Tenemos que calcular toda esta información de iluminación antes de enviarla a las listas, para que el driver gráfico tenga todo esto muy bien machacado (por ejemplo, generaremos la información necesaria para rendear el shadow map, configuraremos los vértices con los valores adecuados de iluminacion, y sabremos la cantidad precisa de luces que afectan a cada objeto)

Podemos también generar los shaders optimizados para cada objeto (como son ficheros de texto, podemos precalcular ciertos valores por frame). Como ya sabemos cuantas luces caen por objeto, podemos generar un shader optimizado para esa iluminación (si tenemos luces que solo afectan al especular, y no caen sobre nuestro objeto, podemos descartar los cálculos especulares).

Otro factor al tener en cuenta cuando recorremos la escena son los niveles de detalle de las texturas y los objetos. Según estemos mas lejos de la cámara, tendremos que ir calculando los distintos niveles correspondientes, para insertar correctamente cada nivel en las listas.

Las tarjetas y el buffer de datos es muy rápido enviando arrays de vértices, y una vez en memoria de tarjeta, es importante reutilizarlos. Por eso descartes del tipo fustrum o sistemas mas complejos suelen evitarse, porque requieren una lectura de datos que podemos tener en memoria de la tarjeta, y por ello seria probable que fuese mas lento. Sistemas como una jerarquía de bounding boxes son útiles, ya que los cálculos no requieren la descarga de la malla para que la CPU lo procese. Otros métodos de ordenación requieren tiempos de preprocesado muy grandes, por lo que no sirven para objetos animados y en movimiento.

Hay que tener cuidado con la animación y las físicas. Normalmente la escena ser rendear varias veces (para shadow maps, y los distintos pases), así que debemos de aplicar la animación lo antes posible, y tener cuidado de que cuando generamos las listas, los objetos no se muevan (saldría mal que un objeto estuviese en distinta posición que la sombra). Por eso, cuando visitamos el objeto, lo insertamos ya animado en las listas correspondientes.

Al visitar la escena, tenemos que tener preparado un sistema para los recursos de datos: texturas, mallas, etc. Podemos tener un thread que se encargue de la carga, y así hacer el recorrido asíncrono. Tambien, especialmente en el mundo de los videojuegos, necesitaremos algún tipo de sistema de ficheros virtual, que nos permita acceder a los datos dentro de un .dat o un .zip, o alguna estructura que dado un identificador, nos devuelva los datos que necesitamos. Aquí es importante estar desacuerdo con las herramientas y con el resto de artistas (cosa complicada).

Normalmente, una vez creada, la lista se ordena siguiendo distintos criterios, para que al pintarlo todo sea mucho mas rápido. Por ejemplo, intentamos juntar los objetos del mismo shader, para que no tengamos que cambiar de contexto cada vez que cambiamos de objeto. Para esto podemos usar un simple radixsort con un identificador para cada elemento de la lista que iremos componiendo con los distintos valores. Para objetos del mismo shader, juntaremos los que tengan la misma textura. Y para objetos de mismo shade y misma textura, los ordenaremos de adelante para atrás, para aprovechar el descarte del zbuffer. Aquí tambien podemos detectar los objetos transparentes, etc. Esto podemos complicarlo cuanto queramos, pero la idea es que en la siguiente etapa, el driver gráfico solo tenga que recorrer la lista, configurar lo que tenga que configurar, y pintar, así por cada nodo (por eso es importante ordenar y que los cambios sean los mínimos posibles).

Ya que hablamos de motores de render modernos, debemos de indicar que hoy en día todo se programa pensando en threads, ya que los procesadores multicore son comunes hoy en día. La implementación normal es que el GUI del juego, o la misma inteligencia artificial, envie los comandos a una cola de eventos de forma asíncrona. El thread que se encarga de las visitas puede leer los comandos de forma secuencial durante la visita. Sobre esto, hay muchas formas de hacerlo. EL motor puede actualizar todo, o solo un porcentaje de cosas (para garantizar un frame rate), puede dar prioridades, o puede ir modificando entre visitas. Dependerá de la aplicación. O puede que un thread vaya actualizando el estado de las entidades, y otro thread leyendo en modo solo lectura. Lo importante es usar una cola para los eventos de cambio. De ese modo, evitamos tener que bloquear los threads cuando queremos actualizar la posición de alguna entidad, o cambiar algun estado. Como veis, insertar en listas es una tarea muy común dentro de un motor.

Es una pena, pero con esto terminamos la serie de artículos sobre motores 3D para tarjetas. Seguramente se han quedado cientos de cosas en el tintero, y mucha gente no haría las cosas de este modo, sobre todo ahora que el mundo multicore es una realizad, pero al menos la guía os servirá de base para plantearse dudas sobre vuestro desarrollo, y tomar ideas para lo que ya tenéis desarrollado.

Referencias

Tom's Tech Blog. Renderstate change costs.

Scene Graphs - just say no

Optimizando DirectX

This e-mail address is being protected from spam bots, you need JavaScript enabled to view it  

blog  Jesús de Santos

blog de Iñigo Quilez