Présentation

Le problème de placer des objets aléatoirement tout en respectant une distance minimale apparaît fréquemment en infographie, simulation de fluides ou génération procédurale de forêts. La distribution qui satisfait cette contrainte porte le nom de Poisson disk. Robert Bridson a proposé en 2007 un algorithme capable de produire de telles distributions en temps moyen constant, ce qui le rend largement adopté dans les moteurs graphiques.

Fonctionnement de l'algorithme de base

Soit r la distance minimale recherchée et d la dimension de l’espace. Bridson divise le domaine en une grille de pas r/√d, garantissant qu’une cellule ne peut contenir qu’un seul point. Le processus démarre avec un point aléatoire placé dans la grille et stocké dans une liste active. Tant que active n’est pas vide, l’algorithme :

while active not empty:
    pick random point p from active
    for i in 1..k (k≈30):
        sample radius ρ ∈ [r, 2r] uniformly
        sample direction u uniformly on unit sphere
        q = p + ρ * u
        if q respects distance r (checked via grid):
            add q to active and to grid
            break
    else:
        remove p from active

Le test de collision s’effectue en ne consultant que les cellules voisines du point candidat, ce qui réduit la complexité de O(N) à O(1) par itération. Le paramètre k fixe le nombre maximal d’essais dans l’annulus [r,2r] avant d’abandonner le point parent.

Optimisations proposées

Deux améliorations sont détaillées.

Exclusion angulaire par parentage (2 D) : lorsqu’un point q est généré à partir d’un parent p, une portion de l’annulus autour de p est géométriquement interdite, car tout angle appartenant à ce cône placerait le nouveau point à moins de r de q. La largeur du cône θ s’obtient par

θ = min( arccos(r/|p‑q|) , arccos((2r‑|p‑q|)/|p‑q|) )

En mémorisant le parent de chaque point, l’échantillonnage angular évite ces intervalles, réduisant le nombre moyen d’essais.

Modification de la distribution radiale : la densité de points dans l’annulus dépend de la fonction de répartition cumulative (CDF) F(ρ) ∝ ρ^α sur [r,2r]. En choisissant un exposant α≠2, on déplace les points vers le centre (α<2) ou vers la périphérie (α>2). L’échantillonnage inverse donne

if α ≠ 0:
    ρ = ((u*(2^α‑1) + 1))^(1/α) * r
else:
    ρ = r * exp(u * ln2)

où u est uniforme dans [0,1]. Des expériences montrent que des valeurs fortement négatives de α maximisent le nombre de points générés, mais introduisent des artefacts structuraux (filaments, zones vides).

Analyse des performances et limites

Les tests présentés utilisent 100 exécutions sur une grille de côté L (valeur exacte non précisée) avec r fixé, comparant le nombre moyen de points obtenus avec et sans optimisation parentale. La réduction du nombre d’itérations est notable en 2 D, tandis que l’impact de α devient marginal au‑delà de trois dimensions, car le volume d’intersection d’une annulus avec une sphère décroît rapidement.

Les deux améliorations augmentent la consommation mémoire : le suivi du parent (et éventuellement des enfants) nécessite un tableau supplémentaire, et le calcul de cônes impose des opérations trigonométriques. En haute dimension, le gain de vitesse s’estompe, ce qui rend l’optimisation radiale plus pertinente que l’exclusion angulaire.

En résumé, Bridson fournit une base robuste pour la génération de distributions Poisson Disk. L’exclusion angulaire améliore l’efficacité en deux dimensions, tandis que l’ajustement de la CDF offre un contrôle fin de la densité locale au prix d’une complexité algorithmique accrue et d’un risque de perte d’aléa.