ボロノイ図（Voronoi）をUE4マテリアルでレンダリングしてみた。

f:id:neuliliilli:20190420144945p:plain — マテリアル編集画面

UE4の勉強兼、ボロノイ図を実装して見ました。基本的なものですが、実装するために様々なページを探してみたりしましたのでいい経験でした。（かもしれない）

ボロノイ図とは

en.wikipedia.org

ボロノイ図はある平面で（または平面と呼ばれる地域など）いくつかの点が配置されるとしたら、位置のよってどの点に一番近いかを測って区切りしたダイアグラムを指します。各点を中心として一定の地域を「Voronoi Cell」と言います。そしてそのボロノイ図を生成する過程自体を「ボロノイ分割」と言います。

ボロノイ図を生成するために必要となる、ある点（ $a$ ）と中心となる点（ $b$ ）の距離を求める数式は大体に２つに別れます。一つは「ユークリッド距離」、もう一つは「マンハッタン距離」です。

ユークリッド距離： $d[(a_1, a_2), (b_1, b_2)] = \sqrt{(a_1 - b_1)^2 + (a_2 - b_2)^2}$
マンハッタン距離： $d[(a_1, a_2), (b_1, b_2)] = | a_1 - b_1 | + | a_2 - b_2 |$

f:id:neuliliilli:20190525011402p:plain — ユークリッド距離・マンハッタン距離の比較

実装

f:id:neuliliilli:20190525111943p:plain

float resMin = min(iResolution.x, iResolution.y);
vec2 uv = texCoord / resMin;
vec2 pos = uv * 12.0;
vec2 iN = floor(pos);
vec2 iF = frac(pos);

最初にスクリーン上の位置を標準化して（ $[0, 1$ ]）、ボロノイ図の各セルの個数を掛け算したものを定数と少数で分けます。
iNとiF変数はボロノイ図を実装するに必要となります。

f:id:neuliliilli:20190525112953p:plain

ボロノイ図を実装します。上の青色いノードは各セルの壁部分（枠線）の色となります。下の黒い色のノードは各セルの中身の色を表します。（テクスチャーなどで塗り替えっても構いません）
Customノードはfloatリターン値を返します。（MASKノードでRチャンネルだけ値を取ります）そしてsmoothstepノードで0か1かを定めます。smoothstepの基準値の範囲が広くなればなるほど枠線が太ります。

Customオード（ボロノイ図）

Functions sF;
return sF.Out(iN, iF);

UE4のCustomノードは素のままじゃカスタム関数が作れないという謎仕様です。ですが、構造体を作って、その中に関数を作ることでカスタム関数が作れます。というわけで、Functionsという構造体インスタンスを作って、そしてOutという関数を呼び出します。
iN、iFが使われます。全部float2です。（vec2と同じ）

以下の関数は全部Functionsのメンバー関数となります。

float3 Out(in float2 n, in float2 f)
{
  float md = 8.0;
  float2 mg, mr;
  FirstPhase(n, f, md, mg, mr);
  md = 8.0;
  SecondPhase(n, f, md, mg, mr);

  return float3(md, 0, 0);
}

Out関数は２つのフェイズを通してボロノイ図のWeight値を作り出します。
最初のmdは、FirstPhaseで各セルの中点から測定する距離の範囲を示します。こっちでは8.0で多めに測るようにしました。0.25みたいに小さめになる時には測定結果がおかしくなりますし、最終的には枠線がちゃんと引きません。
mgは中点があるグリッドの位置オフセットを、mrはその中点までの方向ベクトルを示します。

float2 PseudoRandom(in float2 c)
{
  const float2 l = float2(127.1, 311.7);
  const float2 r = float2(266, 183);
  return frac(sin(float2(dot(c, l), dot(c, r))) * 43760);
}

PseudoRandom関数は、float2型の類似乱数を返します。ボロノイ図のランダムな中点を取り出すのに必須です。（ノイズマップを使用しても構いませんね）以下の図はこの関数にiFを入れてのリターン値をR、Gチャンネルに入力し、描画した結果です。
リターン地は小数点のみとなります。（重要？）
pseudoRandomの小数点は、グリッド内で座標が $[0, 0$ ]の場合の中点への方向・距離ベクトルを表しているようです。

f:id:neuliliilli:20190525115521p:plain — `PseudoRandom`関数のレンダリング結果

void FirstPhase(in float2 n, in float2 f, inout float md, inout float2 mg, inout float2 mr)
{
  for (int y = -1; y <= 1; ++y)
    for (int x = -1; x <= 1; ++x)
    {
      float2 g = float2(float(x), float(y));
      float2 o = PseudoRandom(n + g);
      float2 r = o + g - f;
      float  d = dot(r, r);

      if (d < md) { md = d; mr = r; mg = g; }
    }
}

f:id:neuliliilli:20190525131358p:plain — イテレーションごとの`g`、`o`、`f`、そして`r`の関係図

mdはボロノイ図の各セルの中点への距離を表します。二重forループを使用して、現在のグリッドから連接したセルの中点への距離、方向を探します。それで、一番距離dが短い時のr、g、dがリターンされるようになります。
上の図で、o、g、fと距離関係でのベクトル相応がどうなっているかがわかります。ちょっと注意するところは、各グリッドで一番右下が中点になるわけではないということですね。
中点に近いピクセル座標はmdが0に近接します。ですのでこれをsmoothstepでフィルタリングして描画させてみると、以下の図みたいになります。

f:id:neuliliilli:20190525120157p:plain — `FirstPhase`から返す`md`値の分布をレンダリングした結果

void SecondPhase(in float2 n, in float2 f, inout float md, in float2 mg, in float2 mr)
{
  for (int y = -2; y <= 2; ++y) // 2じゃなくて1でもあり
    for (int x = -2; x <= 2; ++x) // 2じゃんくて1でもあり
    {
      float2 g = mg + float2(float(x), float(y));
      float2 o = PseudoRandom(n + g);
      float2 r = g + o - f;
      float  d = dot(r, r);

      if (dot(mr-r,mr-r) > 0.0) { md = min(md, dot(0.5*(mr+r), normalize(r-mr))); }
    }
}

SecondPhaseでは、枠線のWeight値となるmdを0または0より小さい値に記録します。これで枠線が生成できます。
数式dot(0.5*(mr+r), normalize(r-mr))はちょっと最適化することで0.5 / len * (length2(r) - length2(mr))に置き換えることが出来ますね。lenはベクトルmr、rの距離となります。この数式によって、ボロノイ図の各セルの境界線部分は大体マイナス値を持ち、そしてそこから離れた部分は離れるほど大きな値を均一に持つことが出来ます。
最終のmd値はピクセルのボロノイ図の枠線の負のWeight値となります。

f:id:neuliliilli:20190525144756p:plain — `md`をレンダリングしてみた結果

Customノードの全体コード

struct Functions
{
  float2 PseudoRandom(in float2 c)
  {
    const float2 l = float2(127.1, 311.7);
    const float2 r = float2(266, 183);
    return frac(sin(float2(dot(c, l), dot(c, r))) * 43760);
  }

  void FirstPhase(in float2 n, in float2 f, inout float md, inout float2 mg, inout float2 mr)
  {
    for (int y = -1; y <= 1; ++y)
    {
      for (int x = -1; x <= 1; ++x)
      {
        float2 g = float2(float(x), float(y));
        float2 o = PseudoRandom(n + g);
        float2 r = g + o - f;
        float  d = dot(r, r);

        if (d < md) { md = d; mr = r; mg = g; }
      }
    }
  }

  void SecondPhase(in float2 n, in float2 f, inout float md, in float2 mg, in float2 mr)
  {
    for (int y = -2; y <= 2; ++y)
    {
      for (int x = -2; x <= 2; ++x)
      {
        float2 g = mg + float2(float(x), float(y));
        float2 o = PseudoRandom(n + g);
        float2 r = g + o - f;
        float  d = dot(r, r);

        float len = distance(mr, r);
        if (dot(mr-r,mr-r) > 0.0)
        {
          md = min(md, 0.5 / len * (length2(r) - length2(mr)));
        }
      }
    }  
  }

  float3 Out(in float2 n, in float2 f)
  {
    float md = 8.0;
    float2 mg, mr;
    FirstPhase(n, f, md, mg, mr);
    md = 8.0;
    SecondPhase(n, f, md, mg, mr);

    return float3(md, 0, 0);
  }
};

Functions sF;
return sF.Out(iN, iF);