UE4マテリアルによるDistanceField生成(Jump Floodingアルゴリズム)

UE4 GPGPU Graphics UE4 UE5 シェーダ マテリアル 数学 Material

2023/12/16更新
SDF生成ツールをUE5向けに公開しました.

サンプルプロジェクト有 (UE4.27).

Jump Flooding アルゴリズムによるDistanceField生成をUEマテリアルで実装したメモ.
ついでに Editor Utility Widget でSeedテクスチャの生成とDistanceFieldの生成をトリガーするテスト.

Jump Flooding Algorithm (JFA)の詳細については各種資料参照.
https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf
Jump flooding algorithm - Wikipedia
GPU Voronoi Diagrams using the Jump Flooding Algorithm / Ricky Reusser | Observable

サンプルプロジェクト

DistanceFIeldByJFA00.zip - Google ドライブ


プロジェクトの[ThirdPersonBP/DF]に関連BPやマテリアル等がある.

関連コンテンツフォルダ

DistanceFieldテクスチャ生成手順

EUW_JfaTestアセット を右クリック->Run Editor Utility Widget でWidgetを表示する.
Generate Seed Texture ボタン を押すとマテリアルによってSeedテクスチャが更新される.

Generate SeedTexture

Run JFA ボタン を押すとSeedテクスチャを元にDistanceFieldテクスチャが生成される.

Generate DistanceField

アセット説明

  • RT_Seed
    • DistanceFieldの元になるSeedテクスチャ. 黒テクセルは無効で, それ以外の色のテクセルがSeedとして評価される.
    • どんなテクスチャでもよいが,今回はマテリアルM_DistanceSeedでその場で生成している.
    • サイズはデフォルト512x512だが変更可能. ただし動作確認しているのは2の冪のみ.
  • RT_Jfa0
    • DistanceFieldの出力先テクスチャ.
  • M_DistanceSeed
    • Seedテクスチャの生成用マテリアル. 適当な計算で適当な位置に黒(0,0,0)ではないSeedを書き込む.
  • MF_JumpFlood
    • JFAのメイン処理をCustomNodeで記述したMaterialFunction. M_JumpFlood_SetupとM_JumpFlood_Itrはこれを呼び出す.
  • M_JumpFlood_Setup
    • JFAの初回パス用マテリアル. Seedテクスチャを元に黒(0,0,0)ではないテクセルをSeedとしてJFAの初回パスを実行する.
  • M_JumpFlood_Itr
    • JFAの反復パス用マテリアル. 基本的には初回パスと同じだが,JFA入力が前回のJFAパスの結果テクスチャになる.
  • M_JumpFlood_Copy
    • JFA結果テクスチャを元に出力先テクスチャRT_Jfa0 へ出力するマテリアル.
  • EUW_JfaTest
    • JFA処理のMaterialDrawなどをするWidget. 今回のJFA関連の処理はほぼここに書いてある.
    • JFAのワークテクスチャ(PingPong用に2枚)を内部で生成して利用する.
    • JFA自体はテクスチャサイズXに対して (log2(X)-1)回のマテリアルDrawで完了する.

Jump Flooding ステップ

JFAの1ステップの処理は MF_JumpFlood のCustomで行っている.
初回のSeedテクスチャの処理だけ少し特殊対応しているがそれ以外は素直な実装.
テクスチャサイズは2の冪でのみ動作確認.

//  MF_JumpFlood
//  入力テクスチャの非ゼロ(0,0,0)テクセルをSeedとして最近接Seedテクセル位置をJFAで計算する.
//
// inTexture : 入力テクスチャ.
//        初回パスは黒(0,0,0)が無効値扱いである任意のテクスチャ.
//        反復パスではRG=(0,0)が無効値であるような最近接Seedテクセル位置テクスチャ.
//        テクセル位置は必ずテクセル中心を指すものとする. 具体的には半テクセルサイズ分のオフセットが付加されたもの.
// texelPosition : ハーフテクセルサイズ込のテクセル中心位置.
// textureSize : テクスチャサイズ.
// stepLength : この反復でのステップのテクセル数.
//        入力サイズ/2 から開始し, 反復的に 1/2 としてサイズが 1 になるまで実行することでJFAが完了する.
// isSetupPass : 初回パスの場合非0.
//
float bestDistance = 65535.0;
float2 bestSeed = float2(0.0, 0.0);
for(int j = -1; j <= 1; ++j)
{
    for(int i = -1; i <= 1; ++i)
    {
        float2 samplePosition = texelPosition + float2(i, j) * stepLength;
        
        const float2 sampleUv = samplePosition / textureSize;
        const float4 col = Texture2DSample(inTexture, inTextureSampler, sampleUv);

        if(any(float2(0.0,0.0) > samplePosition) || any(textureSize <= samplePosition))
            continue;

        float2 seedPosition = samplePosition;
        if(0.0 != isSetupPass.x)
        {
            // 最初のパスは黒テクセルを無視.
            if(all(float3(0.0, 0.0, 0.0) == col.xyz))
                continue;   
        }
        else
        {
            // 有効であればハーフピクセルオフセット付きのテクセル位置が格納されている.
            seedPosition = col.xy;
            // 0,0 は有効なシードを格納していない.
            if(all(float2(0.0, 0.0) == seedPosition))
                continue;
        }

        float curDist = distance(seedPosition, texelPosition);
        if(bestDistance > curDist)
        {
            bestSeed = seedPosition;
            bestDistance = curDist;
        }
    }
}

return float4(bestSeed.x, bestSeed.y, 0.0, 0.0);


以下の疑似コードのように反復をすることで最終的に各テクセルの最近接Seedテクセル座標が計算される.
それを元にDistanceFieldテクスチャを生成する.

// Pseudo Code.
int stepCount = log2(TextureSize) - 1;
for(int i = 0; i < stepCount; ++i)
{
    JumpFlood(stepLength = pow(2, stepCount - i));
}

その他

今回の実装ではSeedテクスチャの黒(0,0,0)は無効値として扱う.
同様にJFAワークテクスチャは最近接Seedテクセル座標float2を格納するが, (0,0)が格納されている場合は無効値扱いとする.
テクセル座標は必ずテクセル中心位置であり, 必ず半テクセルサイズ分がオフセットされているため (0,0)という値にはなりえないことから.