ポアソン・ディスク

なにか

水玉の布・壁紙のドット・印刷の網点・木の植え方・鳥の巣の分布がこれにあたる。「均等にばら撒きたいが、格子のように規則正しくは見せたくない」場面は多い。一様乱数は塊と隙間ができ、格子は規則が見える。ポアソン・ディスクはその間にある配置で、「どの 2 点も距離 r 以上」という反発だけで作る。Bridson（2007）の作り方は、一辺 r/√2 の格子で近所を引き、活動中の点のまわりに k 回だけ候補を撒く。1 マスに高々 1 点しか入らないので（対角がちょうど r）、近所の判定が速い。

問題は「均等だが規則でない」を数で言えるかである。このギャラリーには回折の道具がある。点の配置のフーリエ変換を見ればよい。

青ノイズ。長い波長の濃淡がない

同じ個数（258 点）の一様乱数・ポアソン・ディスク・六方格子を並べ、角度平均の構造因子 S(q) を測った。ポアソン・ディスクは q = 0.2〜0.5·(2π/r) で S ≈ 0.1。一様乱数の ≈ 1 に対して、長い波長の濃淡が消えている。q ≈ 2π/r（点の間隔の逆数）に環が立ち（1.46）、その上は平らに戻る。これが青ノイズ（低い周波数がない雑音）で、目には「均等」と映る。六方格子は同じ密度でも S に鋭い点（8.9・ブラッグ点）が立った。それが「規則」と映る。均等と規則は別の量で、ポアソン・ディスクは前者だけを持つ。

最近傍距離の変動係数（ばらつき÷平均）で言えば、乱数 0.49・ポアソン 0.09・格子 0.00。密度 n·r² は六方充填の上限 2/√3 = 1.155 の 56%（k=30）。

Bridson の論文（1 ページ）を全文読むと、k について書いてあるのは「1 点のまわりで諦めるまでの試行回数」という定義と「typically k = 30」の一語だけだった。k の値を勧めてもいないし、極大になるとも書いていない。論文が保証しているのは O(N) の計算量である。だから k を振って密度を測るのは、論文の主張を覆したのではなく、論文が触れていない量を測ったことになる。k を 100 にすると密度は 7% 増えた（0.645 → 0.688）。未被覆（どの点からも r より遠い場所）は k=5 で 3.2%・k=30 で 0.04%・k=100 で 0.02%。有限の点数なので S(q) には揺れが残る。

「青ノイズ」の出どころは三段に分かれていた。語を定義したのは Ulichney の 1988 年の論文で、対象は格子の上の 2 値ディザ模様である（p.62「よくできたディザ模様は、平均間隔 λ_g の等方な場でなければならない」。最小距離ではなく平均間隔で、点過程の話ではない）。図 13 が「主周波数での低域の切れ・急な遷移・平坦な高域」の 3 つを挙げている。反発する点の配置にこの条件を当てたのは Mitchell の 1987 年の論文で、そこで初めて「blue-noise criteria」と名づけられ、出どころは Yellott 1983 だとされている（p.66）。Mitchell の参考文献に Ulichney は入っていない。

⚠️ そのうえで「反発する点の分布は青ノイズになる」は、一般論としては成り立たない。Lagae と Dutré が多数の生成法を実測して、相対半径が大きすぎると規則的な配置に落ちるので ρ ≤ 0.90 に抑える必要があると書き、タイル型のいくつかはスペクトルが「rather bad」だと測っている。言えるのは「ここで作った配置のスペクトルは青ノイズ型だった」までで、測ったのはこの配置だけになる。

→ Hat の回折像（同じ構造因子。あちらは点で、こちらは環）

→ ボロノイ（このばら撒きを種にすると、面積の揃ったセルになる）

→ フィロタキシス（もうひとつの「均等だが規則でない」。こちらは黄金角 1 つで決まる）

どう作ったか

生成器は generators/poisson.js で、Bridson 法を自前で書いた。格子の目を r/√2 にとり、1 点あたり k 回まで試し、乱数は決定的にしてある。対照として同じ個数の一様乱数と六方格子を並べ、構造因子は 90 方向の角度平均で出している。k を 5 から 100 まで振ると、密度も未被覆の割合も単調に動いた。

出典

数理

R. Bridson, "Fast Poisson disk sampling in arbitrary dimensions", ACM SIGGRAPH 2007 Sketches＝1 ページの全文を読んだ（k は「typically k = 30」の一語だけ・保証は O(N) の計算量のみ）／R. Ulichney, "Dithering with blue noise", Proc. IEEE 76 (1988), 56–79＝語の定義は p.62 と図 13（対象は格子上の 2 値ディザ模様）／D. P. Mitchell, "Generating antialiased images at low sampling densities", SIGGRAPH '87, 65–72＝点の配置に当てた「blue-noise criteria」の命名は p.66、出どころは Yellott 1983／A. Lagae, Ph. Dutré, "A comparison of methods for generating Poisson disk distributions"＝生成法ごとのスペクトルの実測（KU Leuven テクニカルレポート CW 459 の版で読んだ。Computer Graphics Forum 27 (2008), 114–129 の刊行版は開けていない）。Yellott 1983（Science 221, 382）と Cook 1986（ACM TOG 5, 51）は本文を開けなかった

親戚

Hat の回折像（構造因子）・ボロノイ・フィロタキシス・トゥルシェ（乱数の模様の帳簿）

生成

generators/poisson.js（poisson.svg r=0.034 の水玉・poisson-book.svg 3 つの配置と S(q)）