Estructuras espaciales: rejilla, octree y qué elegir

Todas las técnicas de un mundo grande —culling, streaming, colisiones, búsqueda de vecinos, consultas de proximidad— acaban planteando la misma pregunta: qué hay cerca de aquí. Responderla recorriendo todos los objetos es lineal, y lineal por frame y por consulta es exactamente lo que no puedes permitirte. Las estructuras espaciales convierten esa pregunta en una consulta de índice, y la elección entre ellas es menos misteriosa de lo que parece: casi siempre gana la más simple.

La rejilla uniforme

Divide el espacio en celdas de lado fijo, guarda cada objeto en la celda de su centro, y para consultar mira las celdas que intersecan la región de interés. Sin árbol, sin balanceo, sin recursión.

class Rejilla {

	constructor( tamCelda ) {

		this.tam = tamCelda;
		this.celdas = new Map();

	}

	clave( x, y, z ) {

		const cx = Math.floor( x / this.tam );
		const cy = Math.floor( y / this.tam );
		const cz = Math.floor( z / this.tam );

		return cx + ':' + cy + ':' + cz;

	}

	insertar( objeto, posicion ) {

		const k = this.clave( posicion.x, posicion.y, posicion.z );

		let celda = this.celdas.get( k );

		if ( celda === undefined ) {

			celda = [];
			this.celdas.set( k, celda );

		}

		celda.push( objeto );
		objeto.userData.celda = k;

	}

	mover( objeto, posicion ) {

		const nueva = this.clave( posicion.x, posicion.y, posicion.z );
		const vieja = objeto.userData.celda;

		if ( nueva === vieja ) return;      // el caso comun: no hacer nada

		const celdaVieja = this.celdas.get( vieja );
		if ( celdaVieja ) {

			const i = celdaVieja.indexOf( objeto );
			if ( i !== - 1 ) celdaVieja.splice( i, 1 );

		}

		this.insertar( objeto, posicion );

	}

	enRadio( centro, radio, salida = [] ) {

		const r = Math.ceil( radio / this.tam );

		const cx = Math.floor( centro.x / this.tam );
		const cy = Math.floor( centro.y / this.tam );
		const cz = Math.floor( centro.z / this.tam );

		const r2 = radio * radio;

		for ( let z = cz - r; z <= cz + r; z ++ ) {

			for ( let y = cy - r; y <= cy + r; y ++ ) {

				for ( let x = cx - r; x <= cx + r; x ++ ) {

					const celda = this.celdas.get( x + ':' + y + ':' + z );
					if ( celda === undefined ) continue;

					for ( const o of celda ) {

						if ( o.position.distanceToSquared( centro ) <= r2 ) salida.push( o );

					}

				}

			}

		}

		return salida;

	}

}

Tres decisiones de diseño están en ese código y las tres importan.

El Map con clave de cadena en lugar de un array tridimensional. Un array de un mundo de mil por mil por mil celdas ocuparía mil millones de entradas casi todas vacías. Con un Map, solo existen las celdas ocupadas: la estructura es dispersa y su memoria es proporcional al número de objetos, no al volumen del mundo. El coste es el hash de la cadena, que en un motor de JavaScript moderno es rápido pero no gratis; si el rendimiento aprieta, se puede empaquetar las tres coordenadas en un único entero con desplazamientos de bits.

El corte temprano en mover. La mayoría de los objetos, la mayoría de los frames, no cambian de celda. Comprobarlo antes de tocar nada convierte la actualización de miles de objetos en miles de comparaciones de cadena, que es despreciable.

La comprobación de distancia real dentro del bucle. Las celdas son cubos y la consulta es una esfera: las celdas de las esquinas contienen objetos que están fuera del radio. Sin el filtro final devolverías falsos positivos.

El parámetro que decide todo es el tamaño de celda. Demasiado pequeña y una consulta de radio moderado tiene que visitar cientos de celdas vacías. Demasiado grande y cada celda contiene tantos objetos que vuelves a hacer una búsqueda lineal. La regla que funciona: el lado de la celda igual al radio de consulta típico, lo que hace que cualquier consulta toque como mucho ocho celdas en tres dimensiones. Si tus objetos tienen tamaño, usa el diámetro del mayor.

El octree

Un octree subdivide recursivamente el espacio en ocho, y solo subdivide donde hay contenido. Su ventaja aparece cuando la distribución es muy desigual: si el 90 % de tus objetos está en el 1 % del volumen, una rejilla uniforme acaba con unas pocas celdas saturadas y millones vacías, mientras que el octree se profundiza donde hace falta y se queda superficial donde no.

Sus desventajas son reales y suelen olvidarse. El recorrido es recursivo, con saltos de puntero y mala localidad de caché. Insertar y borrar puede provocar subdivisiones y fusiones. Y los objetos que cruzan el límite entre dos hijos hay que meterlos en el padre, o duplicarlos, o subdividirlos: ninguna de las tres opciones es limpia.

En la práctica, la regla que se sostiene: si tus objetos son dinámicos, empieza por la rejilla; si son estáticos y la distribución es muy desigual, considera el octree. Los motores de juego usan rejillas o BVH para objetos móviles y árboles para geometría estática, y esa división no es casual.

Three.js incluye un octree en sus addons, especializado en triángulos para colisiones contra geometría estática:

import { Octree } from 'three/addons/math/Octree.js';
import { Capsule } from 'three/addons/math/Capsule.js';

const octree = new Octree();

// Recorre la jerarquia, convierte cada malla en triangulos en espacio de mundo
// y construye el arbol. Hazlo una vez, tras cargar el nivel.
octree.fromGraphNode( escenario );

// Colision de un personaje modelado como capsula.
const colisionador = new Capsule(
	new THREE.Vector3( 0, 0.35, 0 ),
	new THREE.Vector3( 0, 1.65, 0 ),
	0.35
);

const resultado = octree.capsuleIntersect( colisionador );

if ( resultado ) {

	// resultado.normal y resultado.depth describen como salir del solido.
	colisionador.translate( resultado.normal.multiplyScalar( resultado.depth ) );

}

Su configuración está en dos propiedades: trianglesPerLeaf, que por defecto es 8 y define cuántos triángulos caben en una hoja antes de subdividir, y maxLevel, que por defecto es 16 y limita la profundidad. También tiene un layers para filtrar qué mallas entran al construirlo, lo que permite tener geometría visual que no colisiona sin tener que separarla en el grafo.

Además de capsuleIntersect, ofrece sphereIntersect, boxIntersect y rayIntersect. Es la base del ejemplo oficial de movimiento de personaje de Three.js y funciona sorprendentemente bien para lo compacto que es.

Sus límites: es estático. fromGraphNode transforma los triángulos a coordenadas de mundo en el momento de construir; si mueves el escenario, hay que reconstruirlo entero. Y guarda todos los triángulos como objetos Triangle de JavaScript, lo que para geometría muy densa consume bastante memoria.

Elegir según la consulta

La estructura correcta depende menos del número de objetos que del tipo de pregunta que haces. Esta tabla resume lo que se sostiene en la práctica:

Un par de matices sobre la tabla. Para “el más cercano”, la rejilla se consulta en anillos crecientes alrededor de la celda del punto, parando en cuanto se encuentra un candidato y se comprueba que ninguna celda del anillo siguiente puede contener nada más cercano. Y para el frustum, agrupar objetos en regiones de una rejilla gruesa y comprobar la región completa —tal como viste en la lección de culling— captura casi todo el beneficio de un octree con una décima parte del código.