GPUに適したJump Floodingおよびボロノイ図と距離変換への応用

注：このページのデモはWebGL機能を使っているためモバイル機器では機能しないことがあります。きちんと表示させるためにはデスクトップコンピュータ上で記事を読むことをお勧めします。

ボロノイ図とはなんでしょうか。下記のデモを見ていただければお分かりになると思います。左のキャンバスをクリックすると、色付きの「母点」が植え付けられます。右のキャンバスでは、各ピクセルが一番近い点の色に着色されます。ドラッグすればより多くの点を配置できます。

デモ#2：左のキャンバスには動いている点が複数あります。右のキャンバスには対応するボロノイ図が表示されています。どちらのキャンバスでも構いませんから、マウスオーバして黄色い点を動かしてみてください。水の中を泳いでいる黄色い魚をイメージしました。

もう1つ面白いデモを用意しました。左のキャンバスには、写真の上に放射状のパターンで母点を重ねています。各母点は下層にある画像のピクセルの色が反映されています。円をドラッグすると母点が動き、四角をドラッグすると回転できます。 (編注：本記事上では動作しないため、 元記事 で動作をお試しください)

どのように機能するのか？

ボロノイ図の演算にはいくつか有名なアルゴリズムがあります。上記のデモを構築するのに用いた手法について説明します（コードは ここ です）。この手法は『 GPUに適したJump Floodingおよびボロノイ図と距離変換への応用 』という論文に基づいています。これをJFAと呼びましょう。Jump Floodingアルゴリズムの短縮形です。

JFAへの入力となるのは（上記のデモのような）空白の背景と色の付いたいくつかの母点です。 ステップ長 をkとして、画像上での反復処理を 循環 します。毎回、各ピクセル（i, j）を反復処理し、周囲8ピクセルを調べます。調査する8ピクセルは直接の近接ではなく、その回のステップ長によります。kというステップ長なら、下記の図表に表されたようなパターンで近くのピクセルを探します。

ステップ長が1なら、すぐ隣の近接を探します。ステップ長が10なら、四方向とその間の方向の10ピクセルを探します。

各ピクセルは、それまでに見つけた一番近い母点の色だけでなく位置を覚えています。ピクセルを処理する時、そのピクセルが覚えている母点（もしあれば）の位置と、訪問した各ピクセルとを比べます。より近い母点を見つけた場合、代わりにそちらを覚えます。

ピクセルは、母点に到達しなくても母点のことを知ることが可能です。ただ、その母点に到達した別のピクセルに到達すればいいのです。または、そこに到達したピクセルに到達したピクセルに到達する、などでも大丈夫です。

最初の回のJFAはステップ長がN/2で、Nはグリッドのサイズです。次のステップ長はN/4、更にその次はN/8、などと、N/kが1になるまで続きます。全部でlog（N）回行います。次のインタラクティブなデモでは、各回でグリッドに沿ってJFAが移動するパターンを見ることができます。各ステップでは、処理中のグリッドセルと、母点を探して到達したそれの周りの8つのセルを表示しています。スライダを使って回数を変えてみてください。

要約すると、JFAは次のように機能します。グリッドログ内の全てのピクセルをN回通るとします。最初、現時点のピクセルから8ピクセル「近接」、約N/2ピクセル離れた母点を探します。次の回では、N/4ピクセル離れた近接の母点を探すといったように続きます。各ピクセルはそれまでで一番近くにある母点を保持し、アルゴリズムの過程で情報はグリッド内の他のセルへと伝えられます。

場合によっては、JFAに入力した母点セットを与えると微妙に誤った結果を生成することがあります。しかしここでは、これについて深入りはしません（ 論文 のセクション5と6でこれについて説明しています）。これに触れた理由はアルゴリズムが正しくないことが分かっても気を悪くしないためです。アルゴリズムは正しいとは限りません。しかし、多くの場合は、このページのデモのように正しく動きます。

毎回終了した時のJFAグリッドがどうのようになるか見るのはとても面白いと思います。次のデモはこのページの一番上のデモと同じですが、JFAの回数の最大値を設定できるスライダがあります。例えば、5に設定すると、JFAの演算は5回で終了し、結果を2つ目のキャンバスで表示します。母点をいくつか追加してスライダを0からゆっくりと上げてみてJFAがどうなるか確認してください。個人的には、ボロノイ図に近づいている最後の2回の工程を見るのが面白いと感じています。

距離場

JFAはピクセルごとに次のことを教えてくれます。一番近い母点の色(上のボロノイ図のために使ったように)と一番近い母点の場所です。一番近い母点の場所をどのように教えてくれるのかデモするため、上で使った「魚」のデモと同じものをベースに、母点の近さに応じてピクセルに色を付けていきます。色の薄いピクセルが母点に一番近く、色の濃いピクセルは遠いことを示します。

これを使って2DのドロップシャドウをGPUでレンダリングするアイデアをくれたのは Evan Wallace でした。CSSでドロップシャドウをレンダリングする難しい点は、’spread'(広がり)という値があるからです。これが大きいほど影がフェードアウトするまで時間がかかります。つまり、形状をぼかして影を落とすことではドロップシャドウを実装することができないのです。

では、どのようにすればいいのか。影を落としたい形をレンダリングし(次の例では「Voronoi（ボロノイ）」というテキストを使っています)、レンダリングされた各ピクセルがJFAの母点として扱われます。そしてJFAを実行すると、画像内のピクセルから図形の中のピクセルまでの距離が出ます。これが広がりを持つドロップシャドウをレンダリングするのに必要なのです。図形に近いピクセルは影になり、遠いピクセルは影になりません。

上のテキストをキャンバス上でドラッグするとドロップシャドウを動かすことができます。また、スライダを使えば影の広がりやぼかしを変えることができます。

では、一体GPUはどこにあるのか？

JFAは母点の数が増えても遅くなることなく、「一定の速度」で実行されます。しかし、速い理由の説明にはなっていません。JFAを512×512ピクセルの画像で実行する（例えば、隣に母点があるか確認をする）とそれぞれのピクセルを200万回以上処理します。しかし、これをただJavaScriptで実装しても、インタラクティブなデモの毎フレームで実行される計算が遅すぎてしまいます。

JFAが効率的になる理由は、GPUでの実行に実によく適しているからです。200万もの計算は並行して実行されます。まだWebGLを使い始めたばかりなので、機能を深く理解しているとは言えません。さらに勉強して補足の記事を書くかもしれません。それまで、気になる人は、この Chris Wellonsの記事 を参考にするといいでしょう。GPUでJohn Horton Conway考案のライフゲームを作成する方法を読みやすく詳細に説明しています。同じような問題を取り上げていますので、この記事が理解できれば、なぜJFAが速いのかも理解できるはずです。

記事をここまで読んでくれてありがとうございます。お礼にデモを追加しました。1つ目のキャンバスは点のグリッドを2つ表示しています。グリッドの1つは右下へと移動しています。2つ目のキャンバスは対応するボロノイ図を表示しています。どちらのキャンバスもキャンバス上でドラッグするとグリッドの動きを制御できます。

グラフック処理を考えるのが好きな人へ。 Figma では、グラフィックデザイン用の協調ツールの作成に参加してくれるクリエイティブな人材を募集しています。