Gráficos en Computación

¿Qué son?

Como su nombre indica, un Octree es un árbol lógico en el que cada nodo tiene un máximo de ocho hijos.

Se pueden utilizar para diversas tareas, y una de ellas es la partición de un espacio o “mundo” 3D.

¿Y por qué iba a querer yo partir el espacio? Muy simple. Imagina que tenemos un espacio con unos 50,000 polígonos. No podemos mandarle a nuestra tarjeta gráfica que nos pinte los 50,000 a cada frame, se haría muy lento y arruinaría nuestro programa; ni tampoco podríamos hacer 50,000 tests de visibilidad para ver si cada polígono está o no dentro de nuestra área de visión.

Vale, tienes razón, pero ¿cómo me van a ayudar los octrees en esa tarea? Verás, la idea básica en los octrees es la siguiente: primero se crea el octree, el cual va a envolver el mundo y se irá adaptando a él, lo que te dejará el espacio dividido en zonas de forma cúbica. Cada uno de estos cubos contiene a un máximo de otros 8 cubos de menor tamaño. Ahora que tenemos la herramienta creada, a la hora de pintar todo, vamos a mirar si un cubo está en el área de visión (un test simple y rápido); si no lo está, no necesitamos probar a sus hijos, ya que no estarán dentro; si está dentro probaremos si sus hijos están dentro del área, y así recursivamente. En el siguiente ejemplo se ve mejor ilustrado:

Área de Visión sobre el Octree

Si este es nuestro octree, y el punto rojo es nuestra posición, sólo necesitaremos pintar los polígonos contenidos en los cubos sombreados.

Vaya, menudo lío de imagen, ¿qué son todos esos rectángulos? Todo ese conjunto es un octree visto desde arriba; lo entenderás mejor viendo cómo se crean.

¿Cómo se crean?

Empezamos con nuestro mundo, simple, contenido como un montón de polígonos. Vamos a empezar hallando el mayor de entre la máxima altura, la máxima anchura y la máxima profundidad. Una vez lo tenemos vamos a crear un cubo centrado en el centro de nuestro mundo, y lo vamos a crear de lado igual al máximo de los tres. Este cubo que abarca el mundo por completo va a ser nuestro nodo raíz del árbol. Algo así:

Nodo Raíz

Los árboles se construyen recursivamente, y los octrees también.

Ahora que tenemos un nodo, vamos a contar cuántos polígonos están en la región que delimita. Si consideramos que son demasiados lo tenemos que subdividir en 8 cubos iguales que serán sus 8 hijos (de ahí el nombre de Octree). Esta subdivisión se hace dividiendo el espacio del padre en 8 zonas del mismo tamaño, es decir, 4 cubos arriba y 4 cubos abajo. Ten en cuenta que el cubo no se ve, sólo aparece a modo ilustrativo.

Primera Subdivisión

Bueno, ahora ya no tenemos que pintar todo, podemos probar si los cubos son visibles y pintar su contenido si lo son. ¿Y si seguimos subdividiendo? Pues obtendremos nodos con menos polígonos cada vez, y así podremos pintar acelerar más el proceso. Pero debemos tener cuidado al decidir si se subdivide, ya que podemos llegar a crear nodos con tan pocos polígonos que tarde más el test que el pintado. Además, también podemos querer un máximo número de subdivisiones, para que el árbol no coja demasiada profundidad. Otra forma de vigilar el tamaño del árbol es poner un número máximo número de nodos.

Una vez terminado el octree, podemos asignar los polígonos a los nodos hoja del árbol a los que pertenecen.

Sucesivas Subdivisiones

Una nota especial merecen aquellas zonas que no “merecerían” un nodo: aquellas zonas que se deben subdividir porque su padre debe dividirse, pero que al hacerlo quedan vacías. Al subdividir hay que mirar si el número de polígonos que habrá en los nuevos nodos es mayor que 0. De este modo nos ahorramos nodos innecesarios. Por ejemplo:

Nodos Imprescindibles

Y así es como se crea un Octree.

¿Para qué sirven?

Un Octree se puede usar para cualquier tarea que requiera una información local del mundo. Cabe destacar entre otros, el pintado del mundo y la detección de colisiones.

El pintado se acelera con la siguiente idea: miras si un nodo está en la región visible; si lo está, prueba recursivamente en sus hijos; si no lo está, puedes descartar el nodo y a todos sus hijos, ya que ninguno es visible.

En el caso de la detección de colisiones, identificamos la región en la que queremos probar la colisión y actuamos igual, probando si un nodo está en esa zona y sus hijos en caso positivo. Así identificamos los polígonos que pertenecen a esa zona y podemos ver si hay colisión con alguno de ellos.

La idea de la utilización de un octree es identificar una zona de interés y hallar los polígonos de dicha zona.

Conclusión

Es importante trabajar sólo con lo que necesitas o el trabajo se hará demasiado grande para la máquina. También es importante ver cuándo es necesario un octree y cuando no. Un octree debe utilizarse para aquello que no vaya a cambiar durante la ejecución del programa; es decir, debe usarse para el mundo y no para aquellos objetos que tengan libertad de movimiento, ya que reconstruir un árbol no es viable en tiempo de ejecución. Un Octree debe generarse (o ser cargado desde un fichero) en tiempo de carga, no en tiempo de ejecución.

Hay muchas opciones para la partición del espacio: BSPs, Quadtrees, Octrees… Puedes elegir cualquiera de ellos, pero como punto de partida, un octree es la opción más simple y fácil de implementar y utilizar.

Javier Martínez Castro