【Unity】ComputeShaderでランタイムにSDFマップを生成するエクスペリメント

はじめに

こんにちは、ソーシャルゲーム事業部 ゲーム技研所属のアファトです。 この記事はカヤックUnityアドベントカレンダー2018の23日目の記事です。

「面白法人カヤック」をUnityでのダイナミックフォントで普通に描画するとこうなります。

f:id:hitorijan41:20181221163107p:plain

SDFマップのフォントアトラスを生成したら、ベベルや影など、リッチなエフェクトがリアルタイムで描画できるようになります。

f:id:hitorijan41:20181221163110p:plain

しかし、そのSDFマップの生成処理は結構時間がかかります。なので漢字とカタカナのキャラクターセット「面」、「白」、「法」、「人」、「カ」、「ヤ」、「ッ」、「ク」が入っているSDFマップを事前に生成しないと作れないですね。

今回のエクスペリメントではそのマップをランタイムで生成できるようにして、こんなエフェクトが作れるようになります。

f:id:hitorijan41:20181221163210g:plain

どうやってでしょうか?まずは SDF マップについて軽く紹介します。

Signed Distance Field (SDF) とは

Signed Distance Field は Signed Distance Function という関数から生成されます。その関数は簡単に言いますと、ある座標から輪郭までの最短の距離の関数です。Signedというのはシェイプの外か中かによって符号が違うことを指します。具体的に言うと、シェイプの中にある座標は距離がポジティブで、外の場合は距離がネガティブになります。そしてフィールド内の全座標からこの関数を評価すると Signed Distance Field が作れます。今回は2次元の表示のため、この記事で書いてあるSDFは2次元のSDFのことになります。

そして去年 Unity 2017 に統合されたTextMeshProプラグインがこのSDFマップを利用します。おかげでリッチなフォントのエフェクトがリアルタイムで表現できます。しかし、その SDF マップを生成するのに結構時間がかかり、エディターで事前に生成する必要があります。アルファベットを使っているゲームには特に問題がないですが、漢字を使っている日本または中国のゲームでは問題になるかもしれません。漢字を利用するゲームではダイナミックフォントをよく使っているため、事前にSDFマップを生成することができません。そのために今回は初めてCompute Shaderを触りながら、CPUで処理していたSDFマップの生成を、GPUで処理してランタイムで生成できるようにしようと思います。

CPUでSDFマップを生成する処理の実装

参考とするCPUベースSDFマップ生成処理は Anti-aliased Euclidean distance transform のペーパーに基づいた Unity AssetStoreにある Catlike Coding SDF Texture Generator のツールです。 Valve社のペーパー で使われている入力データと違って、このツールの入力データはアンチエイリアスのかかった白黒テクスチャーなのです。そのため高解像度バイナリテクスチャーを用意する必要がありません。

このCPUの実装は基本的に3つのステップに別れています:

  • Sobel フィルター: 輪郭とエッジの方向(ノーマル)
  • アンチエイリアスエッジとの距離の計算( このペーパー のメインテクニック)
  • SSED-8 (eight-points signed sequential Euclidean distance transform) での距離ベクターの伝播

Sobel フィルター

   class Pixel 
    {
        public float alpha; // Inputテクスチャーのアルファ
        public float distance;
        public Vector2 gradient;
        public int dX, dY;
    }

    void ComputeEdgeGradients (Pixel[,] pixels) 
    {
        float sqrt2 = Mathf.Sqrt(2f);
        for(int y = 1; y < height - 1; y++)
        { 
            for(int x = 1; x < width - 1; x++)
            {
                Pixel p = pixels[x, y];
                if(p.alpha > 0f && p.alpha < 1f)
                {
                    // 周りのalphaで方向を計算する
                    float g =
                        - pixels[x - 1, y - 1].alpha
                        - pixels[x - 1, y + 1].alpha
                        + pixels[x + 1, y - 1].alpha
                        + pixels[x + 1, y + 1].alpha;
                    p.gradient.x = g + (pixels[x + 1, y].alpha - pixels[x - 1, y].alpha) * sqrt2;
                    p.gradient.y = g + (pixels[x, y + 1].alpha - pixels[x, y - 1].alpha) * sqrt2;
                    p.gradient.Normalize();
                }
            }
        }
    }

アンチエイリアスエッジへの距離の計算

    float ApproximateEdgeDelta (float gx, float gy, float a) 
    {
        // (gx, gy) エッジへの方向
        
        if(gx == 0f || gy == 0f){
            return 0.5f - a;
        }
        
        // (gx, gy) をノーマライズ
        float length = Mathf.Sqrt(gx * gx + gy * gy);
        gx = gx / length;
        gy = gy / length;
        
        // シンメトリーなので、最初の象限だけで十分
        // gx >= 0, gy >= 0, gx >= gy
        gx = Mathf.Abs(gx);
        gy = Mathf.Abs(gy);
        if(gx < gy){
            float temp = gx;
            gx = gy;
            gy = temp;
        }
        
        // デルタの計算
        float a1 = 0.5f * gy / gx;
        if(a < a1){
            // 0 <= a < a1
            return 0.5f * (gx + gy) - Mathf.Sqrt(2f * gx * gy * a);
        }
        if(a < (1f - a1)){
            // a1 <= a <= 1 - a1
            return (0.5f - a) * gx;
        }
        // 1-a1 < a <= 1
        return -0.5f * (gx + gy) + Mathf.Sqrt(2f * gx * gy * (1f - a));
    }

    void GenerateInitialEdgeDistances (Pixel[,] pixel) 
    {
        int x, y;
        Pixel p;
        
        // 距離の初期化
        for(y = 0; y < height; y++)
        { 
            for(x = 0; x < width; x++)
            {
                p = pixels[x, y];
                p.dX = 0;
                p.dY = 0;
                if(p.alpha <= 0f)
                {
                    // シェイプの外
                    p.distance = 1000000f;
                }
                else if (p.alpha < 1f)
                {
                    // シェイプのエッジ
                    p.distance = ApproximateEdgeDelta(p.gradient.x, p.gradient.y, p.alpha);
                }
                else
                {
                    // シェイプの中
                    p.distance = 0f;
                }
            }
        }
    }

SSED-8での距離ベクターの伝播

    void PropagateEdgeDistance(Pixel[,] pixels)
        // 8SSED (eight-points signed sequential Euclidean distance transform)を実行する
        // 上
        for(y = 1; y < height; y++){
            // |P.
            // |XX
            p = pixels[0, y];
            if(p.distance > 0f){
                UpdateDistance(p, 0, y, 0, -1);
                UpdateDistance(p, 0, y, 1, -1);
            }
            // -->
            // XP.
            // XXX
            for(x = 1; x < width - 1; x++){
                p = pixels[x, y];
                if(p.distance > 0f){
                    UpdateDistance(p, x, y, -1, 0);
                    UpdateDistance(p, x, y, -1, -1);
                    UpdateDistance(p, x, y, 0, -1);
                    UpdateDistance(p, x, y, 1, -1);
                }
            }
            // XP|
            // XX|
            p = pixels[width - 1, y];
            if(p.distance > 0f){
                UpdateDistance(p, width - 1, y, -1, 0);
                UpdateDistance(p, width - 1, y, -1, -1);
                UpdateDistance(p, width - 1, y, 0, -1);
            }
            // <--
            // .PX
            for(x = width - 2; x >= 0; x--){
                p = pixels[x, y];
                if(p.distance > 0f){
                    UpdateDistance(p, x, y, 1, 0);
                }
            }           
        }
        // 下
        for(y = height - 2; y >= 0; y--){
            // XX|
            // .P|
            p = pixels[width - 1, y];
            if(p.distance > 0f){
                UpdateDistance(p, width - 1, y, 0, 1);
                UpdateDistance(p, width - 1, y, -1, 1);
            }
            // <--
            // XXX
            // .PX
            for(x = width - 2; x > 0; x--){
                p = pixels[x, y];
                if(p.distance > 0f){
                    UpdateDistance(p, x, y, 1, 0);
                    UpdateDistance(p, x, y, 1, 1);
                    UpdateDistance(p, x, y, 0, 1);
                    UpdateDistance(p, x, y, -1, 1);
                }
            }
            // |XX
            // |PX
            p = pixels[0, y];
            if(p.distance > 0f){
                UpdateDistance(p, 0, y, 1, 0);
                UpdateDistance(p, 0, y, 1, 1);
                UpdateDistance(p, 0, y, 0, 1);
            }
            // -->
            // XP.
            for(x = 1; x < width; x++){
                p = pixels[x, y];
                if(p.distance > 0f){
                    UpdateDistance(p, x, y, -1, 0);
                }
            }
        }
    }

GPU実装アイデア

GPUで計算するために、各ステップを効率的に並列化しないといけません。GPUに適したメモリアクセスパターンなどを考慮する必要がありますが、今回はCompute Shaderへの踏み台としてそこまで深く最適化しません。

最初のステップはSobelフィルターです。各ピクセルのアウトプットは3x3の隣接するピクセルで計算され、部分的に処理されるので自然に並列化できます。

#define TWO_SQRT 1.41421356237

groupshared float gs_input[BLOCK_SIZE_X][BLOCK_SIZE_Y];

inline float2 CalcGradientSobel(float diag1, float diag2, float dh, float dv)
{
    float gx = diag1 + diag2 + dh * TWO_SQRT;
    float gy = diag1 - diag2 + dv * TWO_SQRT;
    return float2(gx, -gy);
}

inline float2 GetGradient(int2 id)
{
       float diag1 =
               - gs_input[id.x-1][id.y+1]
               + gs_input[id.x+1][id.y-1];
       float diag2 =
               - gs_input[id.x-1][id.y-1]
               + gs_input[id.x+1][id.y+1];

       float right = gs_input[id.x+1][id.y];
       float left =  gs_input[id.x-1][id.y];
       float down =  gs_input[id.x][id.y-1];
       float up =    gs_input[id.x][id.y+1];
       return CalcGradientSobel(diag1, diag2, right - left, down - up);
}

次のステップはアンチエイリアスエッジとの距離の計算です。各ピクセルを処理するために必要なデータがそれ自体に含まれているので、そのまま並列化することができます。いくつか分岐が入ってますが、とりあえずスルーします。

inline float ApproximateDistance (float2 grad, float a) 
{
    grad = normalize(grad);
    grad = abs(grad);

    float gx = grad.x;
    float gy = grad.y;

    grad.xy = float2(max(gx, gy), min(gx, gy));

    gx = grad.x;
    gy = grad.y;

    float a1 = 0.5 * gy / gx;
    if (a < a1)
    {
        return 0.5 * (gx + gy) - sqrt(2 * gx * gy * a);
    }
    if (a < (1 - a1))
    {
        return (0.5 - a) * gx;
    }
    return -0.5 * (gx + gy) + sqrt(2 * gx * gy * (1 - a));
}

そしてカーネルは次のようになります

RWTexture2D<float4> InputTex;
RWTexture2D<float3> GradResult;

#define GROUP_COL 16
#define GROUP_ROW 4

[numthreads(GROUP_COL, GROUP_ROW, 1)]
void GradientPass (uint3 id : SV_DispatchThreadID, uint3 tid : SV_ThreadID, uint3 gid : SV_GroupThreadId)
{
    LoadInput(); // デバイスメモリから groupshared gs_input にロードする
    float2 grad = GetGradient(tid);
    bool isEdge =              // エッジかどうかは
        + step(abs(alpha - 0.5), 0.499)   // 0 < alpha < 1 か
        + step(2.5, length(grad)) > 0; // はっきりしたエッジ (adhoc)

    float2 distance = isEdge //エッジじゃなかったら無限の距離にアサインする
        ? normalize(grad) * ApproximateDistance(grad, alpha) 
        : infinite;

    GradResult[id.xy] = float3(
        distance, 
        sign(alpha - 0.5) // シェイプの中か外の情報
    );
}

問題は最後のステップです。SSED-8アルゴリズムはピクセルを順番に処理しないと正しい結果が得られないので、直接並列化することが出来ません。なのでGPUに適した違うアプローチが必要です。シンプルなアプローチとして局所的にSDFマップを生成するようにします。局所的というのは、各ピクセルが周りの3x3のピクセルに対して、輪郭までの最短の距離ベクターを持つことです。そうするとSobelフィルターみたいに各ピクセルを平行で実行できるようになります。

f:id:hitorijan41:20181221163009p:plain

これをすべてのピクセルに対して行うことにより、各ピクセルが1x1の局所的SDFマップになります。この手法を反復すると、これらの小さな1x1SDFマップは、その近隣と重複する3x3のSDFマップになります。これを反復で実行することによって、完全なSDFマップを作成することができます。

反復処理毎に全てのスレッドの処理が完了しないと次の反復処理は実行できません。そのためにグローバルなスレッド同期が必要ですが、そのためのHLSLのキーワード globallycoherent はなんだか効果がなかったみたいです。とりあえず一回の反復はカーネルを一回実行するという解決にします。そうすると、NxNのテクスチャーのSDFマップを生成するために、カーネルをN/2回実行します。幸いなことに、フォントレンダリングのための典型的なSDFマップは、一定のピクセル数に制限された距離情報しか必要としません(大体4~10ピクセル)。これにより、必要とされるカーネル呼び出しの数がその値に制限されます。したがって、オーバーヘッドは、並列化によるパフォーマンスの向上と比べて小さいです。

パフォーマンス

テスト用のマシンはIntel Iris Graphics 550 GPU(1.5GBのメモリ)と3.3GHzのIntel Core i7 CPUを搭載した13インチのMacBook Pro 2017を使用しました。この反復手法では、SDFマップを生成するのに必要な時間は距離制限に大きく依存します。その一方でCPUでのSDF生成処理に必要な時間は、距離制限に対して不変(常に最大限距離)であるため、最大限の距離制限をテストする必要があります。そのため、いくつかSDFマップの距離制限をテストします: 10px、20px、40px、および最大限の距離(テクスチャーの対角線のピクセル数)。

解像度 CPU SDF GPU SDF 距離制限10px GPU SDF 距離制限20px GPU SDF 距離制限40px GPU SDF 最大限の距離
256x256 1347 ms 8 ms 10 ms 15 ms 26 ms
512x512 5356 ms 9 ms 13 ms 18 ms 129 ms
1024x1024 20732 ms 13 ms 19 ms 33 ms 790 ms

上記のテーブルによりますと、距離制限が最大に設定されていても、GPUの方がまだCPUより26~51倍早いと示しています。NVIDIAやAMDのちゃんとしたGPUじゃなくても、こんなスピードアップができるのは正直びっくりしました。

CPUとGPUで生成されたSDFマップの比較

f:id:hitorijan41:20181221163014p:plain

両方の結果を比較すると、GPUで生成されたSDFマップは、形状の内側のグラデーションがより短いとわかります。これによって、内側に表現したいベベルなどのエフェクトが若干浅くなりそうですね。対策案としては、距離計算のチューニングか、距離ベクターからalphaテクスチャーへ書き出しのポストプロセスでなんとか調整できそうな気がします。

まとめ

これはGPU上のプロセスを最適化せずに単純に並列化しようとするCompute Shaderの試みなので、大きな改善の余地があるはずです。それでも CPUのプロセスに比べるとパフォーマンスが大幅に向上しました。これで、ランタイム時にSDFマップを生成することができ、ダイナミックフォントを使用してもTextMeshProと同様にフォントレンダリングに豊富なエフェクトを表現することが可能になります。

明日の記事は荻原さんによる「CINEMA 4D+Unityでクリスマスイルミネーションを作る」です。

LINE Thingsでお年玉を楽しくする

この記事は、Tech KAYAC Advent Calendar 2018 の23日目の記事になります。

こんにちは!面白法人カヤックのIoT芸人こと入江(@shinnoske0714)です。

業務ではHTMLファイ部というチームでフロントエンドエンジニアをやっています。

技術の無駄遣いをモットーに日々最新技術を追っています。今回は先日のLINE DEVELOPER DAYで発表されてたLINE Thingsを使って、お年玉をランダムに決めれるおみくじを作りました。

できたもの

まずはこちらをご覧ください。

youtu.be

なんで作ったの?

  • 弊社にはサイコロ給という制度があり、親戚にはサイコロで給料が決まると思っている方も多かったから。
  • 単純に年功序列で渡していく行為に面白みを感じなかったから。
  • 誰に何円あげようって考えるのが単純にめっちゃめんどくさかったから。
  • 今年もらえるお年玉の額を見積もるような子どもになって欲しくないから。(自分はそうだった)

そもそもLINE Thingsとは

LINE Thingsとは超簡単に言うと、LINEを介して、BLE対応デバイスにアクセスすることができるプラットフォームです。 また、制御のビューはLIFF(LINE Front-end Framework)というLINE上で動くWEBアプリでできていて、Web Bluetooth APIと同様に、フロントエンドのJavaScriptで開発ができることから今回使ってみようと思いました。

環境設定

WEB側

line-things-starterをフォークする

こちらのレポジトリをフォークしましょう。

https://github.com/line/line-things-starter liff-app以下のファイルがLIFFのコードになります。js, css, htmlなどおなじみの拡張子で構成されています。

ホスティングする

WEBアプリなので、外部からアクセスできるようにする必要があります。今回はforkしたrepositoryをそのままnetlifyでホスティングしました。 できたサイトがこちらになりますhttps://compassionate-fermat-f925fc.netlify.com/

注) LINE Things経由でアクセスしないと、認証されません。

LINE側

LINE Botをつくる(Botと自分の端末で友達になるのを忘れずに)

割愛します。

下の記事を参考にしてください。 https://qiita.com/n0bisuke/items/ceaa09ef8898bee8369d

Botを作ったら、忘れずに自分のLINEアカウントで友達になっておきましょう。 (僕はこれでLINE Thingsに繋がらなくて詰まってました。)

f:id:kiyoshidainagon:20181222104052p:plain

こちらのアクセストークンを控えておいてください。

LIFFアプリをつくる

curlを叩く or 追加画面で作成します。公式がcurlだったのでそちらに準じました。

curl -X POST https://api.line.me/liff/v1/apps \
 -H "Authorization: Bearer {channel access token}" \
 -H "Content-Type: application/json" \
 -d '{
  "view":{
    "type":"{view size}",
    "url":"{LIFF APP URL}"
  },
  "description" : "{LIFF APP name}",
  "features" : {
    "ble": "true"
  }
}'
  • channel access token : 先ほどのアクセストークン
  • view size : Full, Tall, Compactの中から選べます。(どれでもいいかと)
  • LIFF APP URL : ホスティングしたURLを指定します。
  • LIFF APP name : 名前は適当に決めてあげましょう。

レスポンスで {"liffId":"1234abcd-xxxxxxx"} みたいなのが帰ってくると同時に、LIFFのタブに追加されていると思います。どうやらline://app/hogehoge のhogehogeの部分がliffidに当たるみたいですね。

f:id:kiyoshidainagon:20181222104126p:plain

トライアルプロダクトをつくる

curlを叩きます。

curl -X POST https://api.line.me/things/v1/trial/products \
-H 'Authorization: Bearer {channel access token}' \
-H 'Content-Type:application/json' \
-d '{
  "name": "{trial product name}",
  "liffId": "{LIFF APP ID}"
}'
  • channel access token : 先ほどのアクセストークン(2回目)
  • trial product name : 名前は適当に決めてあげましょう。(2回目)
  • LIFF APP ID : 先ほどレスポンスで帰って来た値を入れましょう

レスポンスで返ってきた、serviceUuidをLIFFアプリ, デバイスのUSER_SERVICE_UUIDに代入します。

電子工作

f:id:kiyoshidainagon:20181222102407p:plain

構成されたパーツは、以下になります。シンプルですね。

  • ESP32-DevKitC
  • タクトスイッチ
  • 抵抗10kΩ

接続

これで事前の環境設定は完了したのでLINE Thingsに繋いでみましょう。 f:id:kiyoshidainagon:20181222101602p:plain

https://github.com/line/line-things-starterこちらのREADME.mdの下方にLINE Thingsを有効化 兼 一覧画面に遷移するので読み込みましょう。

f:id:kiyoshidainagon:20181222101828p:plain

写真のようにデバイスとBluetooth接続していきます。

f:id:kiyoshidainagon:20181222101943p:plain:w150

するとこのような画面になり、ボタンを押すと、Click Countが増加していきます。 これで準備完了です。

つくる

実装

LIFF(WEBアプリ)

おみくじのロジックはめっちゃ単純で、報酬額の配列があって、そこからランダムに1つ選ぶってだけです。

Vue CLIで開発したいなと思い、早速環境作ってみましたが、Line Thing上だとうまく動かなかったので、しぶしぶline-things-starterをちょこちょこいじる感じに実装していきました。lodashTweenMaxなどのライブラリは全てCDNで読み込んでます。あとあとになって気づいたのですが、LINE ThingsでLIFFアプリを開かないと表示確認ができないため、デバッグがかなり辛かったです。console.logの代わりにalertを使いまくりました。後々今時のフロントエンド環境にしたい。

お世辞にもいいコードとは言い難いですが、一応貼っておきます。何かの参考にしてください。

github.com

ESP32

line-things-starterのsample.inoにもともスイッチの入力プログラムが入ってたので、ほぼ触ってません。ピン番号を変更したくらい。

モデリング

おみくじをモデリングします。

f:id:kiyoshidainagon:20181222103013p:plain

安定のFusion 360を使いました。 カバーと蓋の2パーツでできてます。

3Dプリント

AFINIA H400で出力しました。

f:id:kiyoshidainagon:20181222103136j:plain:w200

出力後100円ショップで買った壁に貼る木目調のシールとマスキングテープを貼りました。

できたのがこちら(ボタン部分の穴を適当に作ってしまったので、若干歪んでますが。。。)

f:id:kiyoshidainagon:20181222111250j:plain

f:id:kiyoshidainagon:20181222110331j:plain

まとめ

いかがでしたか。

LINE Thingsは前述したようにデバッグしにくい部分やUUIDを変更するとOS側で前のキャッシュが残り続けて発見できなくなる現象みたいなのがちらほらありますが、フロントエンドの知識があれば簡単に実装できるので便利だなという印象でした。

あと、作ってから気づいたのですが、これおみくじ引くんじゃなくて押してますね。まぁたまには押すことも必要でしょう。

明日クリスマスイブは面白法人カヤックのテック芸人ことpontaroくんがUnityでなんかやってくれるそうです。芸人コンボ。乞うご期待!!!

ありがとうございました〜〜〜

参考

https://engineering.linecorp.com/ja/blog/line-things-developer-trial/ https://qiita.com/n0bisuke/items/0c09ae5da43b551e98b1 https://www.youtube.com/watch?v=RHHSoUyAOyE