ジャンプフラッド

ひとことで

画像の各画素について「最も近い種（シード）はどれか」を、GPU で高速に求めるアルゴリズムです。最初は種の画素だけが自分の位置を知っています。各パスで、一定の歩幅だけ離れた 8 近傍の画素が知っている種を調べ、より近いものがあれば受け継ぎます。歩幅を半分ずつにしながら繰り返すと、$\log_2 N$ 回のパスで全画素の最寄りの種が決まります。結果から、ボロノイ図と距離場が同時に得られます。

ゲームでの使いどころ

• 勢力圏・領土：戦略ゲームの地図で、各都市や拠点の支配範囲と国境線を求める（デモ）。
• 実行時の距離場生成：UI の図形や、画面に描いたマスクから距離場を作り、縁取り・光彩・柔らかい影に使う。
• アウトライン：選択したキャラクターの輪郭から一定距離の縁取りを、太さに関係なく一定のコストで描く。
• 最寄り探索の加速：流体やグローバルイルミネーション（Radiance Cascades など）で、各画素から最も近い物体や表面を調べる前処理。

しくみ

画像の大きさを $N$ として、歩幅 $k = N/2,\ N/4,\ \dots,\ 1$ の順にパスを実行します。

1. 初期化：種のある画素に、その種の座標（と番号）を書き込む。それ以外は「未確定」にする。
2. 各パス：画素 $\mathbf{p}$ は、自分と $\mathbf{p} + k\,(i, j)$（$i, j \in \{-1, 0, 1\}$）の 9 画素が持っている種の中から、$\mathbf{p}$ に最も近いものを選んで書き込む。
3. 歩幅を半分にして繰り返す。

大きな歩幅で種の情報を遠くまで一気に広げ、小さな歩幅で細部を修正していくイメージです。各パスは全画素で独立に計算できるので GPU に向いており、読み込み用と書き込み用の 2 枚のテクスチャを交互に入れ替えるピンポンバッファで実装します。

結果の各画素には最寄りの種の座標が入っているので、距離（$\lVert \mathbf{p} - \mathbf{s} \rVert$）も、隣の画素と種が違うかどうか（境界線）もすぐに分かります。

実装のポイント

• 座標の精度：種の座標を保存するので、浮動小数点テクスチャ（または 16 ビット整数）を使います。8 ビットでは精度が足りません。
• 最近傍でサンプリング：前のパスの結果を読むときは補間しないように、最近傍フィルタにします。
• 形からの距離場：種を点ではなく、図形の輪郭の画素すべてにすれば、その図形までの距離場が得られます。内側と外側で別々に実行して引き算すれば、符号付き距離場になります。

つまずきやすい点

• ごく一部の画素で誤りが出る：ジャンプフラッドは近似アルゴリズムで、まれに 2 番目に近い種を選んでしまう画素があります。最後に歩幅 1 のパスを追加する（1+JFA）、歩幅 2 と 1 を追加する（JFA+2）などで、誤りはほとんどなくなります。
• 画面外の種：画面の外にある種は見つかりません。広めの領域で計算するか、外部の種を別に扱います。
• 解像度とパス数：パス数は $\log_2 N$ ですが、1 パスごとに全画面を描くので、高解像度では帯域が負担になります。必要な精度に合わせて解像度を下げます。

デモで試すこと

1. 「パスを順に再生」で、最初は都市の画素だけ、次に 256 画素離れた点だけ、と情報が飛び飛びに広がり、9 回目で全体が埋まる様子を見てください。斜線はまだ情報が届いていない画素です。
2. 「実行したパス数」を途中で止めると、その段階で決まっている画素と、まだ誤った都市を持っている画素が分かります。
3. 都市（塔）をドラッグすると、国境線が毎フレーム計算し直されます。種の数を増やしても、1 パスのコストは変わりません。
4. 「最寄りの都市までの距離」表示では、同じ結果から距離場も得られていることが分かります。