BVH y AABB: broad-phase de colisión y raycasting
Bounding Volume Hierarchies son la base de toda colisión moderna. SAH para construir bien, slab method para rayos. Box2D, PhysX y los raytracers lo usan.
Publicado: · Por Juanjo "Banyo" López
0. Por qué BVH y no quadtree
El quadtree particiona el espacio en cuadrantes fijos. Un cuerpo grande puede atravesar la frontera entre dos cuadrantes y obligarte a ponerlo en un nodo interno (o duplicarlo). Funciona bien con puntos, mal con cajas.
El BVH (Bounding Volume Hierarchy) particiona los objetos, no el espacio. Cada nodo es una caja envolvente que contiene a sus hijos. No hay frontera fija — el árbol se adapta a las formas reales de los cuerpos.
Eso es lo que usan:
- Box2D, PhysX, Bullet — broad-phase de colisión.
- Embree, OptiX, Vulkan RT — aceleración de raytracing.
- Unity Physics, Havok — colliders de world-space.
Si has hecho Physics.Raycast o OverlapBox en Unity, estás usando un BVH detrás del telón.
1. La estructura
Un BVH es un árbol binario. Cada nodo tiene:
class BVHNode
bounds: AABB // envuelve a todo el sub-árbol
items: List<Body>? // si hoja: cuerpos que contiene
left, right: BVHNode? // si interno: dos hijos
Invariantes:
boundssiempre envuelve a todo lo que cuelga del nodo.- Hoja:
items != null,left == right == null. Iteraitemsdirectamente. - Interno:
items == null. Recurses por los hijos.
A diferencia del quadtree, los AABBs hermanos pueden solaparse — y eso está bien. El SAH minimiza ese solapamiento donde importa.
2. Construcción top-down con SAH
Cada nivel del árbol tiene un color. El SAH elige el plano de partición que minimiza el costo total — no parte por la mediana, sino por donde reduce más el área esperada de los hijos. Por eso ves AABBs ajustados a los clusters reales.
Figura 1 — Construcción nivel por nivel. El algoritmo recibe todos los cuerpos, calcula su AABB envolvente y decide en qué eje y posición partirlos. Cada split crea dos hijos; recurses en cada uno.
2.1 ¿Por dónde partir?
Ingenuo: parte por la mediana del eje más largo (equal-split). Funciona, pero produce árboles desbalanceados cuando los cuerpos no están bien distribuidos. La SAH (Surface Area Heuristic) hace algo mejor.
Idea de SAH: el costo esperado de procesar un nodo después del split es:
cost(N) = T_trav + (A(L) / A(N)) * |L| * T_int
+ (A(R) / A(N)) * |R| * T_int
donde:
A(X)= área de superficie del AABB deX(perímetro en 2D, área en 3D)|L|,|R|= número de items en cada hijoT_travyT_int= costos relativos de traverse vs intersection (constantes)
La interpretación: la probabilidad de que un rayo aleatorio toque el hijo izquierdo es proporcional a A(L) / A(N). Si lo toca, hay que probar contra sus |L| items. Lo mismo para el derecho.
El split óptimo minimiza esa fórmula.
2.2 SAH binned: el algoritmo práctico
Probar todos los splits posibles es O(N²). La versión binned prueba solo K posiciones por eje (K = 8 o 16 típico):
function findSAHSplit(items, parentBounds) -> Split?
bestCost = items.length * T_int # baseline: dejarlo como hoja
bestSplit = null
for axis in [x, y, z]:
lo, hi = min/max de centroides en este eje
if hi - lo < epsilon: continue
for bin = 1..K-1:
pos = lo + (hi - lo) * bin / K
left = items where centroid[axis] < pos
right = items where centroid[axis] >= pos
if left.empty or right.empty: continue
cost = T_trav
+ (area(unionBounds(left)) / area(parentBounds)) * left.length * T_int
+ (area(unionBounds(right)) / area(parentBounds)) * right.length * T_int
if cost < bestCost:
bestCost = cost
bestSplit = { left, right, axis, pos }
return bestSplit
Si ningún split mejora el baseline (|items| * T_int), la mejor decisión es no partir: deja una hoja con muchos items. Eso evita splits malos en distribuciones patológicas.
2.3 ¿Cuántos bins?
- K = 8: build rápido, calidad muy buena. Default sano.
- K = 16–32: build más lento, calidad marginalmente mejor. Para offline (compilación de assets).
- K = 4: build relámpago, calidad meh. Para BVH dinámico que se reconstruye cada frame.
3. Broad-phase: descartar pares lejanos
Las cajas iluminadas en azul son los AABBs internos del BVH que el query visitó (porque su AABB intersecta tu probe). Las hojas con verde son los hits reales. Cualquier cuerpo gris fue descartado a nivel de rama — el BVH ni siquiera vio su AABB.
Figura 2 — Arrastra el AABB azul. Las cajas iluminadas son las que el BVH visitó (intersección AABB-AABB). Las grises ni siquiera se evaluaron — su rama padre fue descartada.
3.1 Por qué importa el broad-phase
Para 1000 cuerpos rígidos, las posibles parejas son 1000 * 999 / 2 ≈ 500.000. Hacer narrow-phase (geometría exacta) en cada par es prohibitivo. El broad-phase devuelve los pocos centenares de pares cuyo AABB se toca; solo esos pasan al narrow.
function findCollisions(bvh) -> List<Pair>
pairs = []
for cuerpo in bvh.items:
candidates = bvh.queryAABB(cuerpo.bounds)
for cand in candidates:
if cand.id > cuerpo.id and aabbIntersect(cand, cuerpo):
pairs.add((cuerpo, cand))
return pairs
El check cand.id > cuerpo.id evita reportar el par dos veces.
3.2 Refit vs rebuild
Cuando los cuerpos se mueven, los AABBs cambian. Tres estrategias:
- Rebuild completo cada frame: simple, garantiza calidad SAH.
O(N log N). Apropiado hasta unos miles de cuerpos. - Refit: recorrer el árbol bottom-up, recalcular el AABB de cada padre.
O(N). Pero la calidad SAH se degrada con el tiempo — los splits ya no son óptimos para las nuevas posiciones. - Refit + rebuild incremental: refit cada frame y re-build local solo en sub-árboles “deformados” (heurística: comparar el SAH actual vs un baseline esperado).
Box2D usa una variante: dynamic AABB tree con rotaciones (treaps) para mantener calidad sin rebuild completo. Es código sutil; para un proyecto pequeño, rebuild cada frame es la elección razonable.
4. Raycasting con BVH
El rayo barre un sector. Azul: AABBs internos del BVH que el rayo atravesó (con slab method). Naranja: cuerpos hoja tocados pero no son el primer hit. Verde: primer impacto en el rayo. Arrastra el origen.
Figura 3 — Un rayo que rota desde el origen. El BVH usa el slab method para descartar AABBs en O(1). Las cajas naranjas son AABBs que el rayo atravesó pero no son el primer hit; la verde es el impacto efectivo.
4.1 Slab method: rayo vs AABB en 6 multiplicaciones
Para un AABB con esquinas (min.x, min.y) y (max.x, max.y), y un rayo origin + t * dir:
function rayBoxIntersect(o, d, bounds) -> t?
tmin = -inf, tmax = +inf
for each axis [x, y]:
if abs(d[axis]) < epsilon:
if o[axis] < bounds.min[axis] or o[axis] > bounds.max[axis]: return null
else:
t1 = (bounds.min[axis] - o[axis]) / d[axis]
t2 = (bounds.max[axis] - o[axis]) / d[axis]
tlo = min(t1, t2), thi = max(t1, t2)
tmin = max(tmin, tlo)
tmax = min(tmax, thi)
if tmax < 0 or tmin > tmax: return null
return max(0, tmin)
tmin es la distancia al primer hit del AABB. tmax es la distancia al último (sale del AABB). Si tmax < 0, el AABB está detrás del origen. Si tmin > tmax, el rayo no toca.
4.2 Recursión por el BVH
function raycast(node, o, d, bestT) -> Hit?
t = rayBoxIntersect(o, d, node.bounds)
if t == null or t > bestT: return null # podada brutal
if node is leaf:
bestHit = null
for body in node.items:
tBody = rayBoxIntersect(o, d, body.bounds)
if tBody != null and tBody < bestT:
bestT = tBody
bestHit = (body, tBody)
return bestHit
# ordenar hijos por distancia para podar más temprano
leftT = rayBoxIntersect(o, d, node.left.bounds)
rightT = rayBoxIntersect(o, d, node.right.bounds)
nearer, farther = (leftT < rightT) ? (left, right) : (right, left)
hit1 = raycast(nearer, o, d, bestT)
if hit1: bestT = hit1.t
hit2 = raycast(farther, o, d, bestT)
return closer(hit1, hit2)
El truco clave: visitar primero el hijo más cercano. Si encuentras hit ahí, el bestT se actualiza y el otro hijo casi seguro se descarta enseguida.
4.3 Aplicaciones
- Disparos hitscan en FPS (single ray per shot).
- Line-of-sight entre NPCs (rayo del ojo al objetivo, ¿pasa libre?).
- Raytracing: millones de rayos por frame, con el BVH como acelerador clave.
- AI navegación: probe rays para detectar obstáculos en steering.
5. Implementación en Unity / C#
public class BVH<T> where T : IBounded {
BVHNode root;
int leafCapacity;
int sahBins;
public class BVHNode {
public Bounds bounds;
public List<T> items; // null si interno
public BVHNode left, right;
}
public void Build(List<T> items) {
if (items.Count == 0) { root = null; return; }
root = BuildRecursive(items, 0);
}
BVHNode BuildRecursive(List<T> items, int depth) {
var bounds = UnionAll(items);
if (items.Count <= leafCapacity)
return new BVHNode { bounds = bounds, items = new List<T>(items) };
var split = FindSAHSplit(items, bounds);
if (split == null)
return new BVHNode { bounds = bounds, items = new List<T>(items) };
return new BVHNode {
bounds = bounds,
left = BuildRecursive(split.left, depth + 1),
right = BuildRecursive(split.right, depth + 1),
};
}
public void QueryAABB(Bounds region, List<T> result) {
QueryAABBNode(root, region, result);
}
void QueryAABBNode(BVHNode n, Bounds region, List<T> result) {
if (n == null || !n.bounds.Intersects(region)) return;
if (n.items != null) {
foreach (var it in n.items)
if (it.Bounds.Intersects(region)) result.Add(it);
} else {
QueryAABBNode(n.left, region, result);
QueryAABBNode(n.right, region, result);
}
}
}
Trucos:
- Usar
structparaBVHNodecon array índice en vez de pointers (cache locality). - Pre-allocar
resulty reusarlo entre queries. - Para builds en hot path, considera SAH binned con array de “bins” en vez de splits exhaustivos.
6. En otros engines
- Godot:
PhysicsServer3Dya tiene BVH para colisión global. Para custom: implementación en GDExtension/C# si necesitas control fino. - Unreal:
FPhysSceneusa Chaos Physics, que internamente usa BVH/AABB tree. Para gameplay:LineTraceMultiByChannelresuelve casi todo. - Web/JS: librerías como
bvh-treeo tu propia implementación. Para 100s–1000s de items, JS bien escrito es competitivo.
7. Errores comunes
- No actualizar
boundsen refit — los hijos se mueven pero su padre sigue con el AABB viejo. Las queries fallan silenciosamente. - SAH con cuerpos degenerados — si todos los items tienen el mismo centroide, ningún split funciona. Detecta
hi - lo < epsilony forza una hoja gorda. - Olvidar el orden por distancia en raycast — sin él, las podas son ineficaces y degeneras a recorrer todo el árbol.
- Build sin maxDepth — items idénticos pueden infinitar la recursión. SAH suele evitarlo (el baseline cost gana), pero un cap explícito es safety net.
- Rebuild en hot path con N grande —
O(N log N)es manejable hasta unos miles. Más allá, refit + rebuild incremental.
8. Quiz
Pon a prueba lo que entendiste
Responde una por una. La explicación aparece al elegir, correcta o no.
¿Por qué BVH y no quadtree para cuerpos rígidos con tamaño?
El SAH dice que el costo del split es proporcional al área del hijo. ¿Por qué área y no número de items?
Tu raycast contra un BVH grande es lento. Profilas: visitas el 80% de los nodos. ¿Probable causa?
Tu BVH se reconstruye cada frame y el game loop está clavado en 16ms con miles de cuerpos. ¿Primer paso?
9. Siguientes pasos
BVH es la columna vertebral de cualquier sistema de colisión o raytracing serio. Lo que sigue: cómo decidir cuáles agentes ni siquiera necesitan procesarse cada frame — LOD para IA.