Poisson disk sampling: el algoritmo de 1 página con 1.000 citas

Por qué un paper de una página sigue siendo referencia casi 20 años después

En 2007, Robert Bridson publicó un artículo de una sola página con una idea que sigue siendo citada casi 1.000 veces. Mientras un equipo de nueve matemáticos necesitaba cerca de 1.000 páginas en 2024 para demostrar la conjetura geométrica de Langlands, Bridson resolvió en un folio un problema cotidiano de gráficos por computadora y simulación: cómo colocar puntos al azar sin que queden demasiado juntos. La estructura resultante se llama Poisson disk distribution, y su algoritmo es la base invisible detrás de bosques generados, escenas de render, simulaciones de física y efectos visuales en tiempo real que cualquier startup que toque gaming, VFX o simulación acaba reutilizando.

Lo cuenta el desarrollador StripeAcross en un análisis técnico publicado esta semana, donde además recoge dos optimizaciones propias y un algoritmo alternativo de 2022 que, según él, no ha recibido la atención que merece.

Qué es Poisson disk sampling y por qué el muestreo aleatorio «de toda la vida» no basta

Una distribución de Poisson disk es un conjunto de puntos en un espacio donde ningún par de puntos queda más cerca que una distancia mínima r. La idea es simple y aparece en casi cualquier producto visual o simulación: árboles en un bosque procedural, estrellas en un fondo, partículas en una simulación de fluidos, muestras en un mapa de ruido.

👥 ¿Quieres ir más allá de la noticia?

En nuestra comunidad discutimos las tendencias, compartimos oportunidades y nos ayudamos entre emprendedores. Sin humo, solo acción.

👥 Unirme a la comunidad

El muestreo aleatorio uniforme falla aquí: algunos puntos caen encima de otros, lo que rompe la propiedad visual o física buscada. Lo que necesitas es esa distancia mínima garantizada sin perder la sensación de aleatoriedad.

Una solución naive es el rejection sampling: tiras dardos al azar y rechazas los que caen dentro de r de otro punto existente. El problema, como explica el autor, es que la verificación de colisiones es lineal sin una estructura de datos apropiada, y la tasa de rechazo se acerca a 1 conforme se acumulan puntos.

Cómo funciona el algoritmo de Bridson en cinco pasos

El algoritmo de Bridson trabaja sobre un espacio de dimensión cualquiera y respeta la distancia mínima r. En términos generales:

Divide el espacio en una cuadrícula con celdas de lado r/√d. Esto garantiza que cada celda contenga como máximo un punto, lo que vuelve la detección de colisiones O(1).
Inicializa la lista active con un punto aleatorio uniforme.
Mientras active no esté vacía: toma un elemento al azar de active, y dentro del anillo (annulus) centrado en ese punto, con radio interior r y radio exterior a lo sumo k·r (Bridson recomienda k = 30), muestrea hasta encontrar un candidato válido que respete la distancia mínima a sus vecinos. Si lo encuentra, lo añade a active y selecciona un nuevo padre. Si no, lo descarta.
Al final, exporta el conjunto resultante.

El truco está en la cuadrícula: con celdas de lado r/√d, solo hay que inspeccionar un número constante de celdas vecinas para validar cada candidato, en lugar de revisar todos los puntos ya colocados.

Para muestrear el anillo de forma uniforme, el autor remite a un vídeo suyo donde lo explica: un vector unitario aleatorio y un escalar en [r², (k·r)²] (o, equivalentemente, un radio entre r y k·r con la distribución correcta) bastan.

Las dos mejoras que recortan iteraciones de verdad

El artículo no se queda en explicar el algoritmo: propone dos optimizaciones que, según sus pruebas empíricas, reducen drásticamente las iteraciones necesarias para generar la misma cantidad de puntos.

1. Optimización por nodo padre (2D)

Cuando el algoritmo coloca un punto p' y muestrea su anillo para generar el siguiente p'', p' es el padre de p''. Hay un cono angular alrededor de la dirección padre→hijo dentro del cual cualquier candidato estaría demasiado cerca del padre. Si guardas ese cono y excluyes sus ángulos al muestrear el anillo del hijo, evitas un montón de rechazos seguros.

La fórmula del ancho del cono se reduce, en esencia, a un mínimo entre dos términos trigonométricos: el ángulo de intersección con el círculo exterior y el de intersección con el círculo interior. El cambio de qué círculo «manda» sucede cuando la distancia entre los puntos cruza un umbral que sale de la propia geometría del anillo.

Implementarlo cuesta solo guardar el padre de cada punto. Los gráficos del autor muestran una reducción clara de iteraciones. Él mismo advierte que generalizarlo a más dimensiones funcionaría, pero el coste de almacenar los conos anula las ganancias porque el volumen del anillo intersectado con esferas se vuelve proporcionalmente insignificante en dimensiones altas.

2. Optimización por exponente del radio (cualquier dimensión)

La segunda idea es aún más elegante: cambiar la distribución del radio dentro del anillo. La CDF estándar da una densidad uniforme de puntos en el anillo, pero puedes sustituirla por una familia de distribuciones con un exponente arbitrario. Cuando el exponente tiende a infinito negativo, todos los hijos caen a distancia fija r de su padre, lo que maximiza densidad pero introduce artefactos visibles: cadenas largas de puntos y huecos donde la distancia restringida no llega.

El artículo muestra visualmente cómo varía el resultado según el exponente y propone un equilibrio empírico: para mantener la cobertura típica de un muestreo maximal (aproximadamente 54,7 % de área cubierta, la saturated coverage del random sequential adsorption model), el autor deriva por búsqueda binaria un valor óptimo del exponente.

Stippling y «Poisson Cam»: la aplicación creativa del algoritmo

Una de las aplicaciones más vistosas que menciona el artículo es el stippling: hacer que la densidad mínima de puntos varíe según la función r(p) que tú definas. Si esa función es el brillo de una imagen, las zonas claras reciben menos puntos y las oscuras más, generando un efecto puntillista que reproduce la imagen con calidad editorial.

El autor llevó esto más allá con Poisson Cam, un stippler de vídeo en tiempo real construido sobre el algoritmo PixelPie, que corre enteramente en GPU y es paralelo por diseño. Es la diferencia clave respecto a Bridson: Bridson es inherentemente secuencial porque cada nuevo punto depende de los anteriores. PixelPie sacrifica algo de optimalidad a cambio de poder procesar vídeo en vivo.

El algoritmo de Mitchell (2022): maximalidad y uniformidad sin rejection sampling

La parte más interesante del análisis, según el autor, es un algoritmo de 2022 firmado por Scott A. Mitchell que, hasta donde él sabe, no ha recibido atención desde su publicación. Lo destaca porque cumple tres propiedades que ningún otro algoritmo reunía antes:

Maximalidad: cuando termina, es matemáticamente imposible añadir otro punto sin violar la distancia mínima.
Uniformidad: muestrea una distribución uniforme sobre todos los conjuntos maximales posibles.
Determinismo: no usa rejection sampling, lo que elimina por completo los intentos fallidos.

El trade-off es que el algoritmo es sustancialmente más complejo: parte el espacio en una cuadrícula, pondera cada celda por su área restante, la descompone en triángulos y chocks (una figura de tres lados limitada por un arco, un rayo y una tangente), muestrea dentro del triángulo o chock elegido y recorta el círculo prohibido. El paper original, dice el autor, explica los detalles con una claridad que él no pretende replicar.

Según su propia implementación, Mitchell corre más o menos a la misma velocidad que Bridson con las dos optimizaciones activas y produce una cantidad similar de puntos, pero con la garantía teórica de maximalidad y uniformidad que Bridson solo puede aspirar a alcanzar de forma aproximada.

Qué significa esto para tu startup

El Poisson disk sampling es una de esas piezas de infraestructura invisible que aparecen en cualquier producto que genere contenido visual, simule un mundo o renderice multitudes. Si trabajas en gaming, VFX, simulación, gemelos digitales o incluso visualización de datos, es muy probable que tu motor ya lo use sin que lo sepas.

Acciones concretas que puedes tomar hoy:

Audita tu pipeline procedural: si generas bosques, multitudes, partículas, estrellas o cualquier patrón espacial con sampling aleatorio puro, prueba el algoritmo de Bridson con las dos optimizaciones del artículo. Vas a ver menos puntos solapados y ejecuciones más rápidas sin escribir un sistema de física.
Si necesitas paralelismo en GPU: usa PixelPie como referencia. Bridson es secuencial por diseño; si tu cuello de botella está ahí, necesitas otro algoritmo o ejecutar varios Bridson en paralelo sobre subregiones.
Si la maximalidad importa para tu producto (por ejemplo, quieres garantizar que tu simulación no admite más agentes en el mismo espacio), evalúa el algoritmo de Mitchell de 2022 antes que la opción clásica. Es más complejo, pero la ganancia teórica vale para simulaciones certificables.
Para prototipos visuales rápidos: una implementación de Bridson en pocas líneas de Python o Rust resuelve el 90 % de los problemas de «mis partículas se solapan» que aparecen en demos y mockups.

La lección emprendedora: un paper de una página bien resuelto puede sostener toda una categoría de productos durante casi dos décadas. Si tu startup está construyendo infraestructura técnica, el listón que Bridson puso en 2007 es el tipo de estándar de eficiencia que vale la pena perseguir.