prime's diary

そすうの日々を垂れ流しちゃうやつだよ

フラグメントシェーダを用いて、VRChatのワールドで計算機を作る 【KMCアドベントカレンダー 2日目】

GPGPU ネタ

この記事はKMCアドベントカレンダー 2日目の記事です

adventar.org

概要

最近遊んでいるVRChatというゲームにはユーザーの作成したアバターやワールドをアップロードできる機能があります。さらに、アバターやワールドのバーテックスシェーダー*1/フラグメントシェーダー*2を自分で作ったものに差し替えてアップロードすることができます。

これを悪用（？）し、fragment shaderにBrainf*ckという難解プログラミング言語のインタプリタを実装することで、VRChatで、ゲームプレイ中に指定した任意の計算を実行することができるような仕組みを実装しました*3。

GPGPUとは

みなさんが普段ゲームなどのグラフィック処理をするときには、大抵GPU(Graphic Processing Unit)という装置*4が使われます。 GPUは、三次元のポリゴンの移動・変形や、陰影処理等の計算を行うために、たくさんの演算機を備えています。

この演算機の演算能力をグラフィック処理以外にも使おうというアイデアが、GPGPU(General Purpose compution on GPU)と呼ばれています。 今日では、GPGPUはCUDAやOpenCL、OpenACC、グラフィックAPIのCompute Shader等によって比較的手軽に行えるようになりました。

VRChatにおける演算

VRChatはゲームなので、これらの便利なGPGPUプログラミング環境を使う方法はありませんが、アバターやワールドのバーテックスシェーダー/フラグメントシェーダーなどである程度の計算を行うことができます。 バーテックスシェーダーでは各頂点ごとに、フラグメントシェーダーでは画面の各画素ごとにシェーダーのプログラムが実行されます。 が、通常これらのシェーダーは状態を保存したり、他の頂点/画素と通信することはできません。GPUはたくさんのプログラムを並列で計算することでスループットを稼いでいるため、単一の要素に対する計算はあまり高速ではありません。 したがって、まともな速度でゲームが進行するためには、1頂点/画素あたりの計算量は十分小さくないといけません。 つまり、これらのシェーダーで大規模な計算をすることはできません（完）。

という問題を解決する方法がいくつかあり、今回はCustomRenderTextureを使いました。 CustomRenderTextureでは、ダブルバッファリングを有効にすることで、フラグメントシェーダー上で「前のフレームの演算結果」をテクスチャの色情報として得ることができます。また、他のテクスチャ（他のCustomRenderTextureを含む）を入力として受け取ることもできます。 これを利用すると、テクスチャ上に状態を保存することで、フレームをまたいだ計算が可能になります。 また、前のフレームの別の画素の色情報を得ることもできるので、フレームをまたぐことで別の画素と通信が可能になり、並列計算への道が開かれます。 テクスチャは2048x2048程度は問題なく持つことができるため、400万ワードほどのメモリを持つことができます。

これにより、理論上は任意の計算を他のプレイヤーのGPU上で走らせることができます。 とはいえ、shaderのプログラムはアップロード時に決定されてしまうため、このままでは動的に（ゲームプレイ中に）実行するプログラムを差し替えることはできません*5。

そこで、fragment shaderに何らかの仮想計算機を実装し、何らかの方法でゲームプレイ中にプログラムを与えることで、ゲームプレイ中にプログラムを差し替えて計算することができるようになります。

Brainf*ck

Brainf*ck*6は難解プログラミング言語と呼ばれる、「プログラミングすることが難しい」プログラミング言語のひとつです。Brainf*ckではソースコードは8つの命令のみで構成されていて、それぞれごく単純なことしかできません。 詳しくは、Brainfuck - Wikipediaなどを参照してください。 例えば、現在VRChatのBF Interpreterワールドに置かれている、4段のハノイの塔のパズルの解法を計算するプログラムは次のようになります。見やすさのために改行やインデントを入れています。 gist.github.com

Brainf*ckでまともな計算をすることはとても難しいですが、Brainf*ckの処理系(コンパイラ/インタプリタ)を作ることは（他のプログラミング言語に比べて）比較的簡単です。 今回は今後より実用的な処理系を作る練習として、実装の容易なBrainf*ckインタプリタを実装することにしました。

処理系の構成

BF処理系の全体像

処理系本体

処理系の本体はこの図の赤色の部分で、Interpreter Shaderが計算を、Memory/State Textureが状態を保存する役割を果たしています。 Memory/State Textureは64x64pxのRGB値を持ち、最初の1行が命令カウンタなどの状態管理用レジスタ、残りの行がBrainf*ckプログラムの使用するメモリ領域になっています。 状態管理レジスタは[命令カウンタ, データポインタ, 動作モード(実行/前方にジャンプ/後方にジャンプ/プログラム終了), 入力済みバイト数, 出力済みバイト数, 出力データ, ジャンプ時の[ ]の対応を見るカウンタ, 出力validフラグ]の8個となっています。 シェーダー内部では、R,G,Bの各色に対して8bitのデータをエンコードして持たせることで、1画素あたり24bitのデータを保持しています。

処理系の動作はおおむね次のように動きます。 状態管理レジスタに該当する画素: 各レジスタの次フレームの値を計算する - 命令カウンタなら、1進めたり、ジャンプ命令では戻ったり - データポインタは> <命令を実行する状態になっているときのみ増減させる - 出力validフラグは、.命令を実行する状態になっているときのみ1、それ以外を0にする など メモリ領域に該当する画素: データポインタが自身のアドレスと一致しているときのみ、いま命令カウンタが指している命令が+ - ,なら、適切に値を変更する

このような実装により、1フレームに1命令（ジャンプ時はジャンプ場所を線形探索するため何フレームもかかりますが）処理する処理系ができました。

Control Panel

ワールドに設置したカメラでアバターを検出することにより、タッチパネルを実現し、状態のリセットを行うことができます。カメラで撮影した画像をRenderTextureに出力する機能を利用しています。これにより他のシェーダーがプレイヤーの操作を受け取ることができます。 Control Shaderはカメラの入力画像をparallel reductionにより使いやすい形に変換しています。

Output Buffer / Output Text Buffer

出力バッファー用のシェーダーとテクスチャです。 Memory/State Textureの出力validフラグが来たら1文字読み、次の書き込み位置を一つずらします。 Output Text Bufferでは、改行が来たときにも次の書き込み位置を次の行の先頭に移動します。

表示用のシェーダー/テクスチャ

処理系内部では数値はRGB値にエンコードされているので、これを人間が理解できる形式に変換する処理が必要です。 デバッグ用の出力は2進数に変換して黒/白で表示しているだけです。 ソースコードと出力のテキスト表示は、しみさんの

をお借りして実現しています。図がぐちゃぐちゃになるので、上の構成図からはフォント用のテクスチャは省略してあります。 フォントデータが2値画像（をRGBA32bitに詰め込んだもの）なので、大きく表示したときにジャギーが目立つと感じたので、中央値を基にしたジャギー軽減アルゴリズムを実装しています。

今後の課題

  • ソースコードを編集する機能がないので、簡易なテキストエディタを実装して、プレイ中にソースコードを差し替える仕組みを作る
  • ワールドにはインターネット上から画像をダウンロードする方法が存在するので、これにより外部から動的にソースコードを持ってこれるようにする
  • より高級な計算用仮想マシンを実装する
    • Piet DM's Esoteric Programming Languages - Piet の処理系ができると見た目に楽しそう　ただし、カラーブロックの連結成分の大きさを高速に求めるのは簡単ではない。
  • 並列計算が可能な仮想マシンとアーキテクチャを実装する
    • フラグメントシェーダーはその仕様上、「指定した場所に値を書き込む」という仕組みの実現が難しい（複数フレームを掛けてデータをルーティングする必要がある）
  • 高級で並列計算可能な計算機で、実用的な計算速度を得る

*1:ポリゴンの頂点位置を計算するプログラム

*2:色や陰影を計算するプログラム

*3:CPU側に干渉するわけでもなく、負荷も軽いので他のプレイヤーが困ることはないです

*4:これは物理的に個別のユニットとして存在することもあれば、CPUと同じチップ内に存在することもあります

*5:数個程度なら条件分岐で差し替えることはできる

*6:*にはuが入ります