🔘 Muestreo de Disco de Poisson

El muestreo de disco de Poisson genera un conjunto de puntos aleatorios en el espacio de modo que cada par de puntos esté separado por al menos una distancia mínima r, mientras sigue pareciendo irregular y orgánico en lugar de parecido a una cuadrícula. Se sitúa entre la dispersión totalmente aleatoria (que se agrupa) y una cuadrícula regular (que parece artificial), y es la forma estándar de producir distribuciones de puntos de "ruido azul".

Se comienza con un punto semilla aleatorio y se añade a una "lista activa". Repetidamente se elige un punto aleatorio de la lista activa y se prueban hasta k candidatos aleatorios en el anillo entre r y 2r alrededor de él. Se acepta el primer candidato que esté a al menos r de distancia de todos los puntos existentes y se añade tanto al conjunto de puntos como a la lista activa; si ninguno de los k intentos tiene éxito, el punto padre se elimina de la lista activa. El proceso termina cuando la lista activa está vacía.

Comprobar un nuevo candidato contra todos los puntos existentes tomaría un tiempo O(n) por candidato, haciendo que todo el algoritmo fuera O(n²). El truco clave de Bridson es una cuadrícula de fondo con tamaño de celda r/√2, elegido de modo que cada celda pueda contener como máximo un punto aceptado. Un candidato solo necesita comprobar su propia celda y el vecindario circundante (un pequeño número fijo de celdas), por lo que cada comprobación se ejecuta en O(1), y todo el algoritmo se ejecuta en tiempo O(n) para n puntos de salida.

El ruido azul describe una distribución de puntos cuyo espectro de potencia tiene poca energía en las frecuencias espaciales bajas — lo que significa que no hay grandes agrupaciones ni grandes huecos vacíos, solo variación de grano fino distribuida uniformemente. Esta propiedad es visualmente importante porque el ojo humano es muy sensible a patrones de baja frecuencia como agrupaciones o artefactos de moiré. Por eso el muestreo de ruido azul es la técnica estándar para el punteado, el tramado, el antialiasing y la dispersión procedimental de objetos como árboles, rocas o hierba de forma natural.

En lugar de usar un radio fijo r en todas partes, la distancia mínima local se puede consultar en un mapa de densidad: se usa un radio pequeño en regiones densas (permitiendo que los puntos se sitúen más cerca entre sí) y un radio mayor en regiones dispersas (separando más los puntos). La comprobación de vecindad usa entonces el mayor de los radios del candidato y de cada punto existente, de modo que el empaquetado se mantiene consistente en todas partes. Esto produce una densidad de puntos que varía suavemente manteniendo la misma garantía de no solapamiento en todas partes, que es exactamente lo que la herramienta Pintar mapa de densidad te permite esculpir a mano.