🔘 Échantillonnage de disque de Poisson

L'échantillonnage de disque de Poisson génère un ensemble de points aléatoires dans l'espace de sorte que chaque paire de points soit séparée d'au moins une distance minimale r, tout en gardant un aspect irrégulier et organique plutôt que semblable à une grille. Il se situe entre une dispersion entièrement aléatoire (qui forme des amas) et une grille régulière (qui paraît artificielle), et constitue la méthode standard pour produire des distributions de points en « bruit bleu ».

On commence par un point de départ aléatoire ajouté à une « liste active ». On choisit ensuite de manière répétée un point aléatoire de la liste active et on essaie jusqu'à k candidats aléatoires dans l'anneau entre r et 2r autour de lui. Le premier candidat situé à au moins r de tout point existant est accepté et ajouté à la fois à l'ensemble de points et à la liste active ; si aucun des k essais ne réussit, le point parent est retiré de la liste active. Le processus se termine lorsque la liste active est vide.

Vérifier un nouveau candidat par rapport à chaque point existant prendrait un temps O(n) par candidat, rendant tout l'algorithme O(n²). L'astuce clé de Bridson est une grille d'arrière-plan avec une taille de cellule r/√2, choisie de sorte que chaque cellule ne puisse contenir qu'un seul point accepté. Un candidat n'a besoin de vérifier que sa propre cellule et le voisinage environnant (un petit nombre fixe de cellules), de sorte que chaque vérification s'exécute en O(1), et l'algorithme entier s'exécute en temps O(n) pour n points de sortie.

Le bruit bleu décrit une distribution de points dont le spectre de puissance a peu d'énergie aux basses fréquences spatiales — ce qui signifie qu'il n'y a ni gros amas ni grands vides, seulement une variation fine et uniformément répartie. Cette propriété est visuellement importante car l'œil humain est très sensible aux motifs basse fréquence tels que les amas ou les artefacts de moiré. C'est pourquoi l'échantillonnage en bruit bleu est la technique standard pour le pointillisme, le tramage, l'anticrénelage, et la dispersion procédurale d'objets tels que des arbres, des roches ou de l'herbe de manière naturelle.

Au lieu d'utiliser un rayon fixe r unique partout, la distance minimale locale peut être extraite d'une carte de densité : un petit rayon est utilisé dans les régions denses (permettant aux points de se rapprocher) et un rayon plus grand dans les régions clairsemées (éloignant davantage les points). La vérification de voisinage utilise alors le plus grand des deux rayons, celui du candidat et celui de chaque point existant, de sorte que le compactage reste cohérent partout. Cela produit une densité de points variant en douceur tout en conservant partout la même garantie d'absence de chevauchement, ce qui est exactement ce que l'outil Peindre la carte de densité permet de sculpter à la main.