はじめに
ボロノイ図とは、平面に配置された複数の点（母点）に対して、平面上の点を最も近い母点によってグループ分けした図です。
3次元空間にも適用することができますが、本記事では平面でのボロノイ図を扱います。
こんなやつです。(このサイトで作成しました)
ゲームでもよく使われて……るわけではありませんが、私はチームの領域図生成に使用しました。
ということで、そこで用いた、ボロノイ図のビットマップ（画像）をコンピュートシェーダーを利用してGPUで生成する方法を、本記事では解説していきます。
なお、ボロノイ図には様々な種類がありますが、特に説明がない限り、以降の説明では重みなしボロノイ図を前提とします。
環境
- Unity2019.1.12.f1
- Windows10
ボロノイ図の生成アルゴリズム
まずはボロノイ図を生成する方法について紹介しながら、今回紹介する方法を採用した理由を説明します。
ボロノイ図の画像を求めるアルゴリズムとして代表的なものは以下の5種類です。
- 全てのピクセルに対して最近隣点を求め画像を生成
- 直接法
- 逐次添加法
- 分割統治法
- Fortuneのアルゴリズム
1番は、全てのピクセルに対して、各母点との距離を計算して最も距離の近い母点をもとめ、ボロノイ図の画像を生成する方法です。
最も直感的です。直感的ですが、画像が大きい場合の計算量が半端ないです。
計算量は母点の数n、ピクセル数mに対して、O(nm)です。
2番は、母点を一つずつ増やしていきながら、既存の母点との垂直二等分線とほかの境界との交点を調べていく愚直な方法です。
計算時間は最大で$O(n^3)$です。これも計算量が半端ないです。
この資料に載っています。
3番は、母点を一つずつ増やしていきながら、その近隣の境界のみを考慮してボロノイ図を生成する方法です。
計算時間の期待値は最大で$O(n^2)$です。2番よりも計算時間のオーダーが小さいです。
この資料が詳しいです。
4番は、母点を二つのグループに分け、それぞれボロノイ図をもとめて、それらを統合して最終的なボロノイ図を求める方法です。
計算時間は最大で$O(nlog(n))$です。3番よりもさらに計算時間のオーダーが小さいです。
この資料に載っています。
5番は、直線を上から下へと走査させていきながら、ボロノイ図を生成する方法です。計算時間は最大で$O(nlog(n))$です。
重みなしボロノイ図を生成する場合は、4番のアルゴリズムと計算時間のオーダーが変わりません。
しかし、このアルゴリズムの論文によると、他のアルゴリズムよりも、重み付きボロノイ図を生成する際の計算時間のオーダーが小さいようです。
このサイトが詳しいです。
まとめるとこんな感じです。
| アルゴリズム | 計算時間 | 出力 | 補足 |
|---|---|---|---|
| 全ピクセル探査 | $O(nm)$ | ビットマップ | mは画像のピクセル数 |
| 直接法 | $O(n^3)$ | 交点、境界情報 | |
| 逐次添加法 | $O(n^2)$ | 交点、境界情報 | |
| 分割統治法 | $O(nlog(n))$ | 交点、境界情報 | |
| Fortuneのアルゴリズム | $O(nlog(n))$ | 交点、境界情報 | 重み付きの場合は既存のものより計算時間のオーダーが小さいらしい |
CPUを用いて実用的なサイズのボロノイ図を生成しようとした場合、方法1,2は現実的ではありません。
この場合、必然的に3,4,5番のアルゴリズムを使用して求めることになります。
また、2,3,4,5を用いる場合は、ボロノイ図の画像ではなく、ボロノイ図の交点や境界の情報が求められます。
ボロノイ図のビットマップを生成したい場合は、ボロノイ図の交点や境界から画像を生成する必要があります。
CPUでこれを行うとなると、さらに一処理必要になるため、なかなか時間がかかると思われます。（この部分だけGPUで計算すれば短縮できるかもしれません）
一方で、GPUを用いた場合は話が別です。
GPUの並列性を生かすことで、1番の全ピクセルに対して再近隣点を求める方法であっても、現実的な時間で、1ステップで直接ボロノイ図のビットマップを生成することができます。
このことから、今回想定している「母点からボロノイ図のビットマップを生成する」という状況では、簡単さと計算時間を考えて、1番の方法でGPUを使用するのが適しているといえます。（おそらく）
また、この方法だと、計算時間のオーダーを変えずに重み付きボロノイズに対応させることができます。
実装
GPUでの計算には、コンピュートシェーダー(Compute Shader)を使用します。
通常のシェーダーがレンダリング時の挙動をカスタマイズするために使われるのに対して、コンピュートシェーダーはその名の通り、GPUでの計算を行うために用いられるシェーダーです。
コンピュートシェーダーの記法や概念については、この記事が参考になります。
ボロノイ図のビットマップを生成するためのシェーダー、それに着色するためのシェーダー、そして、それをUnityのプログラムから使用するためのスクリプトについて、それぞれ説明していきます。
ボロノイ図生成シェーダー
重みなしボロノイ図を生成するシェーダーの実装を示します。
コード
#pragma kernel CSMain
RWTexture2D<float> result;
int site_count;
float3 sites[128];
float4 bounding_box;
float2 to_world_position(float2 pos) {
float width, height;
result.GetDimensions(width, height);
pos.x = pos.x / width * (bounding_box.z - bounding_box.x) + bounding_box.x;
pos.y = pos.y / height * (bounding_box.w - bounding_box.y) + bounding_box.y;
return pos;
}
[numthreads(8, 8, 1)]
void CSMain(uint3 id : SV_DispatchThreadID) {
float2 pos = to_world_position(id.xy);
float min_dis = 10000000;
int nearest_site_idx = -1;
for (int i = 0; i < site_count; ++i) {
float weight = sites[i].z;
float dis = distance(sites[i].xy, pos);
if (dis < min_dis) {
min_dis = dis;
nearest_site_idx = i;
}
}
result[id.xy] = (float)nearest_site_idx / 255;
}
コンピュートシェーダーの構造
簡単にコンピュートシェーダーの構造について説明しておきます。
コンピュートシェーダーでは、計算はカーネルと呼ばれる単位で行われます。雑に例えると、カーネルは通常のプログラム言語で言うmain関数のようなものです。
カーネルは関数の形で定義され、#pragma kernel カーネル名でカーネルであることを宣言します。
今回のシェーダーではCSMainという名前の関数がカーネルになっています。
このカーネルはスレッドという単位で実行されます。スレッドは、GPUの並列性を生かして、指定した数だけ並列に実行されます。
スレッド数の指定はカーネルとなる関数の直前に[numthreads(x, y, z)]と書くことで行えます。
パラメータはそれぞれx,y,z軸方向のスレッド数を表しており、スレッド数の合計は$xyz$となります。
コンピュートシェーダーで扱うデータは、テクスチャなどの2次元構造や3次元構造をとるものが多いため、このようなスレッド数の指定方法になっているようです。
今回のシェーダーでは、x軸方向に8個、y軸方向に8個、z軸方向に1個のスレッド、計64個のスレッドを生成します。
結果として、$(8,8,1)$の計64個スレッドの塊で、それぞれカーネルが実行されることになります。
シェーダー中でのスレッドの扱いは、下で説明します。
入力と出力
このシェーダーの入力は以下の三つです。
- int site_count: 母点の数。sitesのサイズ128以下である必要がある
- float3 sites[128]: 母点の座標と重み。x,y成分が座標、z成分が重み(このシェーダーでは未使用)
- float4 bounding_box: ボロノイ図を求める範囲。x,yが最小頂点の座標、z,wが最大頂点の座標
出力はボロノイ図を描画したテクスチャ(RWTexture2D<float> result。ランダムに書き込み可能なテクスチャという意味)で、各ピクセルが属している母点のインデックスが書き込まれます。
それぞれコンピュートシェーダーを呼び出すスクリプトから設定します。
スレッドIDとテクスチャ座標
上で説明した通り、このシェーダーのカーネルはx軸方向に8、y軸方向に8、z軸方向に1スレッドの、合計64スレッドの塊で実行されます。
コンピュートシェーダーの実行時にはさらに、このスレッドの塊を何グループ作成して実行するのかを指定します。
スレッドグループ数の指定も$(x,y,z)$の三次元ベクトルで行うようになっており、スレッドの塊をそれぞれの軸方向にx,y,z個並べて実行することになります。
例えば、ボロノイ図生成シェーダーの実行時に、スレッドグループを$(64,64,1)$で指定すると、$(8,8,1)$だけあるスレッドの塊を、x軸方向に64,y軸方向に64,z軸方向に1個作成される、つまり全部で$(256,256,1)$のスレッドがGPUで実行されることになります。
このようにして何がうれしいのかというと、生成するボロノイ図の画像サイズが256×256であるならば、スレッド一つにつき1ピクセルの計算を行っているとみなせるわけで、スレッドごとにどの座標のピクセルについて計算しているのかが、簡単になるのです。
ここで、スレッド内でピクセルを計算しているのかを把握するために使用するのが、SV_DispatchThreadIDです。
ボロノイ図生成シェーダーではidという名前の引数で定義されています。
SV_DispatchThreadIDはスレッド数とスレッドグループ数を合わせて、全体で、現在実行しているのがどこのスレッドなのかを表したベクトルす。x軸方向100番目、y軸方向200番目、z軸方向0番目のスレッドならば$(100,200,0)$となります。
今回は、z,y方向のスレッド数が一致するようにスレッド数とスレッドグループ数を設定しているので、このベクトルのx,y成分(id.xy)がそのままボロノイ図画像出力テクスチャのx,y座標として使用できます。
SV_DispatchThreadID以外にも自分のスレッドがどの位置にあるのかを判断するためのIDは存在します。
そこらへんも含めた、スレッドに関する詳しい説明は、この記事が参考になるかと思います。
動作内容
まず、id.xyにより取得した現在のテクスチャ座標を、ボロノイ図の計算に用いる座標に変換しています。
その座標とすべての母点との距離を求め、最も距離が近い母点のインデックスを出力テクスチャに書き込んでいます。
また、出力テクスチャへの書き込み時に、インデックスを255で割っています。これは、float型のテクスチャの値は、0から1の範囲外にあると自動的に丸められてしまうためです。
これを避けるために、255で割って値が0から1の範囲内に収まるようにしています。インデックスが必要な場面では、逆に255をかけています。
動作例
生成される画像は以下の通りです。
一応うっすらボロノイ図になっていますが、なんかよくわかりませんね。
強調したのがこれです。
色の濃淡でボロノイ図になっています。
ちなみに、ボロノイ図生成シェーダーは1チャンネルテクスチャに出力を行っていますが、出力先の実体は4チャンネルテクスチャです。この場合、出力は全チャンネルに反映されるため、白黒画像のようになっています。
ボロノイ図着色シェーダー
上で生成したボロノイ図画像を着色するためのシェーダーです。
コード
:voronoi_map_colorer.compute
#pragma kernel CSMain
Texture2D<float> input;
RWTexture2D<float4> result;
float4 color_list[128];
[numthreads(8, 8, 1)]
void CSMain(uint3 id : SV_DispatchThreadID) {
result[id.xy] = color_list[input[id.xy] * 255];
}
動作内容
基本的にはボロノイ図生成シェーダーと同じです。
ですが、こちらはさらに単純で、入力として渡された色リストから各ピクセルの母点インデックスに対応する色を取り出し、出力テクスチャに設定しています。
動作例
このシェーダーを、ランダムな色配列を入力として上で生成した画像に適用したものです。想像していたボロノイ図が生成できています。
ボロノイ図生成スクリプト
上に書いた二つのコンピュートシェーダーを使用して、ボロノイ図を生成するUnity用のスクリプトです。
ちょっと長いです。
コード
/// <summary>
/// コンピュートシェーダーによりボロノイ図を生成するクラス。
/// 使用か終了したら必ずDispose()を呼び出すこと。
/// </summary>
public sealed class VoronoiMapGenerator : IDisposable {
/// <summary>
/// 生成されたボロノイマップ
/// </summary>
public RenderTexture voronoiMap { get; }
/// <summary>
/// 色付けされたボロノイマップ
/// </summary>
public RenderTexture voronoiColoredMap { get; }
/// <summary>
/// 生成されたボロノイマップをTexture2Dに変換したもの。
/// ピクセル情報を取得する時などに使う。
/// enableGenerateTexture2Dがtrueの場合にのみ有効。
/// </summary>
public Texture2D voronoiMapTexture2D { get; private set; }
/// <summary>
/// 色付けされたボロノイマップをTexture2Dに変換したもの。
/// ピクセル情報を取得する時などに使う。
/// enableGenerateTexture2Dがtrueの場合にのみ有効。
/// </summary>
public Texture2D voronoiColoredMapTexture2D { get; private set; }
/// <summary>
/// Texture2Dの生成を有効にするかどうか
/// </summary>
public bool enableGenerateTexture2D {
get => _enableGenerateTexture2D;
set {
if (value != _enableGenerateTexture2D) {
_enableGenerateTexture2D = value;
if (_enableGenerateTexture2D) {
//RFloatだとReadPixelsが使えないのでARGB32にする
voronoiMapTexture2D = new Texture2D(voronoiMap.width, voronoiMap.height, TextureFormat.ARGB32,
false);
voronoiColoredMapTexture2D = new Texture2D(voronoiMap.width, voronoiMap.height,
TextureFormat.ARGB32, false);
}
else {
voronoiMapTexture2D = null;
voronoiColoredMapTexture2D = null;
}
}
}
}
/// <summary>
/// 使用か終了したら必ず呼び出すこと
/// </summary>
public void Dispose() {
voronoiMap.Release();
voronoiColoredMap.Release();
enableGenerateTexture2D = false;
}
/// <summary>
/// コンストラクタ
/// </summary>
/// <param name="voronoi_generator">ボロノイ図生成シェーダー</param>
/// <param name="voronoi_colorer">ボロノイ図着色シェーダー</param>
/// <param name="map_size">ボロノイ図のサイズ</param>
public VoronoiMapGenerator(ComputeShader voronoi_generator, ComputeShader voronoi_colorer,
Vector2Int map_size) {
//ボロノイマップ初期化
_voronoiMapGeneratorShader = voronoi_generator;
_generatorShaderKernel = _voronoiMapGeneratorShader.FindKernel("CSMain");
_voronoiMapGeneratorShader.GetKernelThreadGroupSizes(_generatorShaderKernel, out _threadSizeX,
out _threadSizeY, out _);
voronoiMap = new RenderTexture(map_size.x, map_size.y, 0, RenderTextureFormat.ARGB32, RenderTextureReadWrite.Linear) {
enableRandomWrite = true
};
voronoiMap.Create();
_voronoiMapGeneratorShader.SetTexture(_generatorShaderKernel, "result", voronoiMap);
//カラーマップ初期化
_voronoiMapColorerShader = voronoi_colorer;
_colorerShaderKernel = _voronoiMapColorerShader.FindKernel("CSMain");
voronoiColoredMap = new RenderTexture(map_size.x, map_size.y, 0, RenderTextureFormat.ARGB32, RenderTextureReadWrite.Linear) {
enableRandomWrite = true,
};
voronoiColoredMap.Create();
_voronoiMapColorerShader.SetTexture(_colorerShaderKernel, "input", voronoiMap);
_voronoiMapColorerShader.SetTexture(_colorerShaderKernel, "result", voronoiColoredMap);
}
/// <summary>
/// ボロノイ図を更新する
/// </summary>
/// <param name="weights">重みリスト</param>
/// <param name="bounding_box">ボロノイ図を求める領域</param>
/// <param name="site_positions">母点の位置リスト</param>
public void UpdateVoronoiMap(Vector2[] site_positions, float[] weights, Rect bounding_box) {
if (site_positions.Length != weights.Length) {
Debug.LogError($"母点数({site_positions.Length})と重み数({weights.Length})が一致しません。");
return;
}
_voronoiMapGeneratorShader.SetInt("site_count", site_positions.Length);
var site_info_array = new Vector4[site_positions.Length];
for (var i = 0; i < site_positions.Length; ++i) {
site_info_array[i].x = site_positions[i].x;
site_info_array[i].y = site_positions[i].y;
site_info_array[i].z = weights[i];
}
_voronoiMapGeneratorShader.SetVectorArray("sites", site_info_array);
_voronoiMapGeneratorShader.SetVector("bounding_box",
new Vector4(bounding_box.xMin, bounding_box.yMin, bounding_box.xMax, bounding_box.yMax));
_voronoiMapGeneratorShader.Dispatch(_generatorShaderKernel, voronoiMap.width / (int)_threadSizeX,
voronoiMap.height / (int)_threadSizeY, 1);
//必要ならtexture2Dにコピー
if (enableGenerateTexture2D) {
CopyRenderTextureToTexture2D(voronoiMap, voronoiMapTexture2D);
}
}
/// <summary>
/// ボロノイ図の着色を更新する
/// </summary>
/// <param name="color_list">母点の色リスト</param>
public void UpdateVoronoiMapColor(Color[] color_list) {
_voronoiMapColorerShader.SetVectorArray("color_list",
color_list.Select(c => new Vector4(c.r, c.g, c.b, c.a)).ToArray());
_voronoiMapColorerShader.Dispatch(_colorerShaderKernel, voronoiColoredMap.width / (int)_threadSizeX,
voronoiColoredMap.height / (int)_threadSizeY, 1);
//必要ならtexture2Dにコピー
if (enableGenerateTexture2D) {
CopyRenderTextureToTexture2D(voronoiColoredMap, voronoiColoredMapTexture2D);
}
}
/// <summary>
/// 座標から所属する母点のインデックスを取得する。
/// enableGenerateTexture2Dが有効な場合のみ使用可能。
/// </summary>
/// <param name="position"></param>
/// <returns></returns>
public int GetSiteIndex(Vector2Int position) {
if (!enableGenerateTexture2D) {
Debug.LogError("enableGenerateTexture2Dが有効な場合のみ使用可能です。");
return -1;
}
return Mathf.RoundToInt(voronoiMapTexture2D.GetPixel(position.x, position.y).r * 255);
}
private readonly ComputeShader _voronoiMapGeneratorShader;
private readonly ComputeShader _voronoiMapColorerShader;
private readonly int _generatorShaderKernel;
private readonly int _colorerShaderKernel;
private readonly uint _threadSizeX, _threadSizeY;
private bool _enableGenerateTexture2D;
/// <summary>
/// RenderTextureをTexture2Dにコピーする
/// </summary>
/// <param name="source">コピー元</param>
/// <param name="destination">コピー先</param>
private static void CopyRenderTextureToTexture2D(RenderTexture source, Texture2D destination) {
// アクティブなレンダーテクスチャをキャッシュしておく
var current_rt = RenderTexture.active;
// アクティブなレンダーテクスチャを一時的にTargetに変更する
RenderTexture.active = source;
// Texture2D.ReadPixels()によりアクティブなレンダーテクスチャのピクセル情報をテクスチャに格納する
destination.ReadPixels(new Rect(0, 0, source.width, source.height), 0, 0);
destination.Apply();
// アクティブなレンダーテクスチャを元に戻す
RenderTexture.active = current_rt;
}
}
コンストラクタ
まずはコンストラクタについて説明します。
コンストラクタで行っていることは、コンピュートシェーダーのカーネル取得、カーネルのスレッド数取得、出力先レンダーテクスチャの作成、コンピュートシェーダーへの入力と出力に使用する変数の設定です。
カーネルは、コンピュートシェーダーで計算を行う際に必要なために取得しています。ComputeShaderクラスのFindKernelメソッドにより、コンピュートシェーダーで宣言されている名前で取得できます。
カーネルのスレッド数は、全体のスレッド数を画像サイズに合わせるために必要になります。ComputeShaderクラスのGetKernelThreadGroupSizesメソッドで取得できます。
出力先のレンダーテクスチャはRenderTextureFormat.ARGB32で作成します。
また、コンピュートシェーダー側でRWTexture2Dとして扱うためには、ランダムな書き込みが可能でなければなりません。このため、enableRandomWriteをtrueに設定しています。
なお、Unityのプレイヤー設定においてColorSpaceがLinearに設定されている場合、標準ではRenderTextureへの書き込み時にsRGBからLinearへの変換が、読み込み時にLinearからsRGBへの変換が行われるようになります。
RenderTextureで色情報を扱っている場合はこれで問題ないのですが、今回のように色情報ではない値を扱っている場合は、この変換により計算結果が正しくなくなります。
この問題を回避するため、RenderTextureのコンストラクタが受け取るreadWrite引数にRenderTextureReadWrite.Linearを指定することで、変換を行わないようにしています。
ColorSpaceの設定については、公式のドキュメントを参照してください。
ちなみに、母点のインデックスしか書き込まないならRenderTextureFormat.RIntとかの方がメモリを使わないからよいのではないか、と思う方がいらっしゃるかもしれませんが、ARGB32を指定しているのには理由があります。
このスクリプトでは、下で説明するGetSiteIndexメソッドのために、レンダーテクスチャをTexture2Dにコピーしています。
コピーのために、Texture2DのReadPixelsメソッドを使用しています。
このメソッドは、現在カメラの描画先として設定されているテクスチャから、ReadPixelsメソッドを実行したテクスチャにピクセル情報をコピーします。その際に、描画先テクスチャのフォーマットが、RGBA32,ARGB32,RGB24かそれに類似したものいずれかである必要があります。
ここでの描画先テクスチャはコンピュートシェーダーの出力先テクスチャになるので、コンピュートシェーダーの出力先テクスチャはRGBA32,ARGB32,RGB24のいずれかである必要があります。このため、この中でオーソドックスなARGB32を指定しています。
最後に、入力テクスチャや出力テクスチャをコンピュートシェーダーに設定しています。
UpdateVoronoiMapメソッド
UpdateVoronoiMapメソッドでは、ボロノイ図のビットマップを更新します。
母点リスト、重みリスト、領域を入力として、ボロノイ図テクスチャvoronoiMapに出力しています。
ボロノイ図テクスチャvoronoiMapはコンストラクタで設定されているため、ここでの設定は不要です。
シェーダーを実行するDispachメソッドを呼び出す際には、スレッドグループ数を指定する必要があります。
上で説明した通り、ここではテクスチャサイズとスレッドの総数が同じになるようにしたいので、テクスチャサイズをカーネルのスレッド数で割った数をスレッドグループ数として設定します。
カーネルのスレッド数はコンストラクタで取得したものを使用します。
例えば、テクスチャサイズが$256*256$の場合、スレッドの総数は$(256,256,1)$にします。
カーネルのスレッド数は$(8,8,1)$のため、$(256,256,1)$を要素ごとに$(8,8,1)$で割った、$(64,64,1)$をスレッドグループ数として指定することになります。
UpdateVoronoiMapColorメソッド
UpdateVoronoiMapColorメソッドでは、ボロノイ図の着色ビットマップを更新します。
これは特筆すべきことはありません。ボロノイ図テクスチャvoronoiMapと色リストを入力として、ボロノイ図着色シェーダーを実行し、ボロノイ図着色テクスチャvoronoiColorMapに着色したボロノイ図を出力しているだけです。
入力のボロノイ図テクスチャvoronoiMapと出力のvoronoiColorMapはコンストラクタですでに設定されているため、ここで改めて設定する必要はありません。
GetSiteIndexメソッド
GetSiteIndexメソッドでは、ボロノイ画像の指定された座標がどの母点に属しているかを、そのインデックスで返します。
やっていることは単純で、ボロノイ図テクスチャのTexture2D番に対して、GetPixelメソッドを用いて指定された座標の母点インデックスを取得しているだけです。
RenderTextureだとGetPixelメソッドが使用できないため、Texture2Dを生成しておく必要があります。
この機能を実装するために、ボロノイ図の生成と着色を別のシェーダーに分けました。
補足
ボロノイ図テクスチャは、上で説明した通りARGBの4チャンネルで作成されていますが、ボロノイ図生成シェーダー側では、RWTexture<float>(1チャンネルテクスチャ)で入力を受け取っています。この場合、書き込み時にはすべてのチャンネルに書き込まれ、読み込み時には最初のチャンネル(ARGBならAチャンネル)の値が参照されるようです。
ボロノイ図着色テクスチャについては、ボロノイ図着色シェーダー側でRWTexture<float4>(4チャンネルテクスチャ)として受け取っているため、全チャンネルが参照されます。
発展
ボロノイ図生成シェーダーの母点との距離を求める部分を修正することで、簡単に重み付きボロノイ図を生成することができます。
以下に挙げる例以外のボロノイ図についても、距離の計算部分を修正すれば比較的簡単に生成することができるでしょう。
加法重み付きボロノイ図
母点との距離に、母点ごとに設定された重みを加算し、それを重みとして用いることで得られるボロノイ図です。
境界が双曲線になるのが特徴です。
シェーダーによるコードは以下の通りです。
:additively_weighted_voronoi_generator.compute
#pragma kernel CSMain
RWTexture2D<float> result;
int site_count;
float3 sites[128];
float4 bounding_box;
float2 to_world_position(float2 pos) {
float width, height;
result.GetDimensions(width, height);
pos.x = pos.x / width * (bounding_box.z - bounding_box.x) + bounding_box.x;
pos.y = pos.y / height * (bounding_box.w - bounding_box.y) + bounding_box.y;
return pos;
}
[numthreads(8, 8, 1)]
void CSMain(uint3 id : SV_DispatchThreadID) {
float2 pos = to_world_position(id.xy);
float min_dis = 10000000;
int nearest_site_idx = -1;
for (int i = 0; i < site_count; ++i) {
float weight = sites[i].z;
float dis = distance(sites[i].xy, pos) + weight;
if (dis < min_dis) {
min_dis = dis;
nearest_site_idx = i;
}
}
result[id.xy] = (float)nearest_site_idx / 255;
}
乗法重み付きボロノイ図
母点との距離に、母点ごとに設定された重みを乗算し、それを重みとして用いることで得られるボロノイ図です。
境界が円形になるのが特徴です。
シェーダーによるコードは以下の通りです。
:multiplicatively_weighted_voronoi_generator.compute
#pragma kernel CSMain
RWTexture2D<float> result;
int site_count;
float3 sites[128];
float4 bounding_box;
float2 to_world_position(float2 pos) {
float width, height;
result.GetDimensions(width, height);
pos.x = pos.x / width * (bounding_box.z - bounding_box.x) + bounding_box.x;
pos.y = pos.y / height * (bounding_box.w - bounding_box.y) + bounding_box.y;
return pos;
}
[numthreads(8, 8, 1)]
void CSMain(uint3 id : SV_DispatchThreadID) {
float2 pos = to_world_position(id.xy);
float min_dis = 10000000;
int nearest_site_idx = -1;
for (int i = 0; i < site_count; ++i) {
float weight = sites[i].z;
float dis = distance(sites[i].xy, pos) * weight;
if (dis < min_dis) {
min_dis = dis;
nearest_site_idx = i;
}
}
result[id.xy] = (float)nearest_site_idx / 255;
}
応用例
現在制作しているゲームで使用している、本記事で書いた方法の使用例を載せておきます。
現在作成しているゲームでは、ステージ内にタワーが配置されており、タワーは「影」「光」「中立」チームのいずれかが保持しています。
タワーの周辺はそのチームの領域になり、それによってステージの見た目が変化する仕組みになっています。
チーム領域の計算と、ステージの見た目へ反映するために用いるテクスチャ割り当てマップに、今回のボロノイ図を使用しています。
まず、Fortuneのアルゴリズムを用いて、ボロノイ図の境界と交点を求めます。
次に、本記事で説明したボロノイ図生成シェーダーとボロノイ図着色シェーダーから、チーム領域テクスチャを作成します。
緑が光、青が影、赤が中立チームです。
チーム領域テクスチャの色によって、領域ごとにテステージにクスチャを貼り付けます。
これをリアルタイムで行うことで、チームの支配領域によって視覚的にステージの見た目が変わる仕組み、チーム領域境界にシールドが生成される仕組みを実装しました。
タワーを破壊するとチーム領域が変わって、リアルタイムに見た目が変わります。
(面白いかどうかは別として)
参考文献
ボロノイ図生成関連
- A Sweepline Algorithm for Voronoi Diagrams: Fortuneのアルゴリズムの論文です。重みなしボロノイ図の生成アルゴリズムについて載っていますが、変更を加えることで重みありボロノイ図も生成できます。と論文には書いてあるので実装しようと試みましたが、具体的な実装方法がわからなかったので断念しました……
- 大山崇のボロノイ図のページ: 様々な種類のボロノイ図について説明されています
- 計算機科学入門「テーマ６：ボロノイ図とデローネイ三角形分割」: 逐次添加法の説明が載っています
- 計算機科学「第四章 ボロノイ図」: ボロノイ図の生成アルゴリズムについて一通り載っています
- ゆるふわブログ「ボロノイ図を描く！ ~Fortune's Algorithm~」: Fortuneのアルゴリズムについて分かりやすい説明が載っています
コンピュートシェーダー関連
- e.blog「ComputeShaderを触ってみる その1 ～スレッド編～」: Unityのコンピュートシェーダーについて一通り説明が載っています
- NEAREAL「Unity : ComputeShader のシンプルなサンプル(1)」: Unityのコンピュートシェーダーについて一通り説明が載っています
- NEAREAL「Unity : ComputeShader のシンプルなサンプル(2)」: 上の続きです
- Qiita「[Unity] UnityでComputeShaderを使う解説をしているページを訳してみた その2」: Unityのコンピュートシェーダーについて一通り説明が載っています
- Qiita「GLSLについてのメモ」: コンピュートシェーダーを書くときに使えるビルドイン関数が載っています