Este post se lo dedico a mi amigo Jose. Él sabe porqué

El frustum culling es una técnica muy conocida que permite averiguar si un objeto se encuentra dentro del campo de visión del jugador no. Básicamente, la librería gráfica correspondiente realiza una comprobación similar a nivel de polígono. Es decir, los polígonos que están fuera del campo de visión no se dibujan. Esto es muy costoso y no tiene ninguna eficiencia.

El frustum es el trapezoide (o como se diga) que representa el campo visible. Lo que se suele hacer es comprobar si un objeto está dentro de él o no. Si está dentro, se dibuja y si no no. Así no se comprueba a nivel de polígono a menos que sea necesario. Sin embargo, en escenas con muchos elementos, esto no es nada eficiente. Una de las primeras mejoras que se suele realizar es simplificar las comprobaciones de cada objeto con el frustum. Para ello, en lugar de comprobar la geometría real del objeto, se comprueba alguna forma geométrica sencilla en su lugar, por ejemplo una caja o una esfera. También se suele emplear una esfera y luego comprobar la caja, pues parece que da buenos resultados.

Sin embargo, lo que mejora muchísimo el rendimiento es la combinación del frustum culling con un octree. Un octree es una estructura de datos con forma de árbol, en la que cada nodo tiene 8 nodos hijo. No voy a entrar muy en detalle en este tema, pero cada hijo se asocia a una zona del espacio tridimensional (si el programa es 2D, se usan quadtrees que es lo mismo, pero con 4 hijos). Así en lugar de comprobar si un objeto está en el frustum se comprueban los nodos del octree.

De esta forma, si hay un nodo que contiene cientos de objetos y ninguno se encuentra en la zona de visión, solo se realiza UNA comprobación. Hay muchos otros métodos para realizar el cálculo de visibilidad: BSP, técnicas basadas en portales, etc. Pero el octree es algo bastante genérico y que suelen implementar la mayoría de motores.