BlogKLabは、多くのスマートフォン向けゲームを開発・提供しています。スマートフォン向けゲームの開発と運用は、Webソーシャルゲームと比べて格段に複雑で、またコンシューマゲーム開発とも異なったノウハウが求められる領域もあります。このブログでは、KLabのゲーム開発・運用の中で培われた様々な技術や挑戦とそのノウハウについて、広く紹介していきます。2015/12/11WebGLで暴力的な並列ソートに挑戦する日照時間足りてますか?やまだです。最近WebGLで実装できるちょっと強そうなソートアルゴリズムを知ったので書いてみました。WebGLよくわかんないやーって人も雰囲気だけでも伝われば幸いです。強さの秘訣WebGLは3Dを描くAPIとして著名ですが、2Dはもちろん、工夫次第で汎用計算(GPGPU)にも応用できます。WebGLでの演算は通常のJavaScript演算とは違い、GPUを使った並列な浮動小数点演算を可能とします。ソートアルゴリズムの中には計算量こそ地味なものの、並列処理が可能なものがあります。そのうちの一つがバイトニックソートです。GPUを使い、物量で計算する暴力的な並列ソートをやっていきましょう。バイトニックソートとは前述のとおり、並列処理が可能なソートアルゴリズムです。配列を小さい領域に分割し、その小さい領域内部で昇順(赤い部分)と降順(青い部分)に分けて整列させます。揃え終わると次は隣接する領域とマージして、これも昇順と降順に揃えます。これを繰り返すことにより最終的にソートが完成します。古典的なGPGPU続いてWebGLでこのソートをどうやって実現するかです。WebGLでは頂点位置の計算を行うバーテックスシェーダとピクセル単位の計算を行うフラグメントシェーダの2種類をGLSLというシェーダ用言語で記述します。バーテックスシェーダは主に頂点位置座標をカメラから見た位置に変換し、フラグメントシェーダはピクセルに色をつけます。通常、WebGLはCanvasに対して画像をレンダリングします。Canvasに対してではなく、テクスチャに対してレンダリングもできます。これをオフスクリーンレンダリングといいます。こちらはwgldにとてもわかりやすく解説されています。古典的なGPGPUのポイントはフラグメントシェーダに対する書き込みです。テクスチャは通常1画素あたりRGBAの4要素が格納されていますが、必ずしもこれを色情報として扱う必要はありません。そのためRGBAをXYZWと読み替えれば座標情報のソートができます。テクスチャの座標は二次元座標ですので左下から右上にむかってインデックスをふり、一次元にする必要があります。これにより1画素を配列の1要素とみなしてソートできるようになりました。ソートのために乱数でテクスチャを埋めて見ると次のようになります。このノイズ画像をシェーダに渡してからソート開始なのですが、WebGLは三角形や点をレンダリングする機能しか持ちません。そこでCanvasいっぱいに四角形ポリゴンをレンダリングし、ソートする要素の数だけフラグメントシェーダが実行されるようにします。そのため、バーテックスシェーダはとてもシンプルな実装になる一方で、フラグメントシェーダが複雑になっていきます。sort』にDirectX用のシェーダ言語であるHLSLのシェーダがあるのでそれを参考にWebGL版を実装しました。参考にというか変数名に至るまでほぼそのままです、助かりました(実はパラメータの求め方よくわかってない)。dst;}ソートのビジュアライズWebGL実装の更新1フレームが並列処理可能な単位です。ソートされていくのを眺めるのって楽しいですよね。デモと動画を用意しましたので是非ご覧ください。Zソートへの応用ソートの結果の活用方法の一つとしてはZソートがあるかもしれません。通常アルファブレンディングを行う場合は奥から手前に向けてレンダリングしないとアルファがかけおちてしまいます。そのため、深度でソートをかけることがあるのですが、パーティクル数が多い場合ソートに時間がかかってしまうこともあるでしょう。そこでWebGLを使ったバイトニックソートを活用して奥から手前にレンダリングします。ソートをかけなかった場合はアルファが不自然に抜け落ちているのを確認できると思います。こちらにデモを用意しましたが、少しGPUパワーが必要なので注意してください。明日はGopherの@tenntennです。