Googleが圧倒的な存在感を見せたGDC開幕直後のチュートリアルセッション

　開幕2日目も、GDCはチュートリアルセッションが中心に執り行なわれた。

　“つかみ”の話題として雰囲気的な話をすると、GDCは隣接する3ホールで開催されており、先日の「Advanced Visual Effects with DirectX 11」や、本日執り行なわれた「Physics for Game Programmers」などはWEST HALLと呼ばれるサブ会場で行なわれた。かつてはWEST HALLがメイン会場であったが、昨年より、GDC会場はNORTHとSOUTHの2ホールがメインとなっており、WEST HALLはあまり賑わってはおらず、昼食もSOUTH HALLまで5分ほど歩いて取りに行かなければならず、完全な“僻地”と化してしまった感がある。

　NORTH HALLでは、Googleが「Google Developer Day」や「Android Developer Day」を開催しており、なんとそこでGoogleは、両日、共にセッション受講者にノートPCやタブレットを無償プレゼントしたのだ。そんなこともあってNORTH & SOUTHとWESTのホールの温度差は激しい。

　今回も、本連載は僻地のWEST HALLから若干の“ひがみ”の情念を交えて地味にお届けする（笑）。

■ ゲーム向け物理シミュレーションの基本
トンネル現象とは何か。そしてその回避方法とは?

Squirrel Eiserloh氏（Director,True Thought Games）

　チュートリアルセッションの「Physics for Game Programmers」は、そのタイトル通り、ゲーム向け物理シミュレーションの話題を取り扱ったもので、別部屋で同時進行されていたゲーム向け人工知能を取り扱う「AI SUMMIT」とならんで、GDCのチュートリアルでは看板セッションコースとなっている。

　「Physics for Game Programmers」セッションの冒頭で取り扱われたのは、ゲーム向け物理でもっとも基本的な話題であるトンネル現象についてだ。

　ゲームは、フレームレート基準で時間が進行するため、この世界で処理される物理シミュレーションは、どうしても離散的な時間進行の下で処理される。

　なので、現実世界のような連続時間世界では衝突して当たり前の「壁にボールを投げつける」ような表現でも、壁の厚みとボールの大きさ、ボールの速度の関係性によってはすり抜けることがざらにある。

　これが「トンネル現象」だ。

トンネル現象

　セッションでは、前時間と現在時間までのオブジェクトの移動の軌跡を衝突判定用の形状に用いる方法などが示されたが、これは確かに「衝突したか否か」……の問いに対してYES/NOの判定は行なえるものの、「いつ衝突したか」、「衝突の瞬間の両者の運動状態はどうだったのか」という回答は得られない。

前時間と現在時間までのオブジェクトの移動の軌跡を衝突判定用の形状に用いるアイディア		この手法ならばトンネル現象は回避できるが……

しかし、逆に、本来ならば衝突していないものも衝突したと誤認してしまうケースもあり得る

　そこで、提案されていたのは「相対的な概念の導入」と「Configuration Space Obstacle（CSO）の導入」だ。

　「相対的な概念の導入」とは、話を自分基準にして、衝突判定をする相手との相対的な関係性に基づいて処理をすることで、例えば「両者が動いていたとしても、自分は静止しているものとして考える」というようなことだ。具体的に言えば時速50kmで互いに正面衝突した場合、自分は静止していて、相手が時速100kmで突っ込んできた……と考えるようなことだ。

こうした2者の運動があった場合……	五角形基準で見れば相対的には三角形が接近してくる運動になる	三角形基準で見れば相対的には五角形が接近してくる運動になる

　CSOは、概念的には、「あらかじめ決めておいた自分の基準点と相手の基準点に基づき、相手を自分に対して全周にこすりつけてできるその基準点の軌跡」という感じのものになる。2Dの世界だと軌跡だが、3Dだと自分の周りを覆う外皮のような領域……というものになる。

　この概念の導入より、衝突判定は相手の基準点がCSOに接触したかどうかの判定に帰着できる。

五角形基準の三角形に対するCSOとは……	三角形を五角形にこすりつけてできる三角形側の基準点の軌跡となる

　また、「いつ衝突したか」という問題についても、前時間から現在時間に向かって相手の基準点の移動軌跡に沿ってレイを飛ばし、どの時点でCSOに接触したかを求めればよい。「衝突の瞬間の両者の運動状態はどうだったのか」については、求めた衝突時点が、前時間からどのくらい時間が経過したかを求め、その時間から運動方程式を解けばいい。十分にフレームレートが高く、ゲーム用ということであれば、衝突時刻までの経過時間割合を元にした両者の運動状態を線形補間で近似値を取るのも悪くないかもしれない。

こうした2者の運動はCSOに配慮した五角形側としては、三角形の接近は点の接近に置き換えられる

さらに五角形の座標系基準で考えれば三角形の接近はこんな感じになる	衝突判定はCSOに三角形の基準点が接触したか（CSOに進入したか）に置き換えられる	衝突判定は衝突したか否かで済むが、物理シミュレーションはその判定の上で運動方程式を解かなければならない
衝突のタイミングによっては運動が全く異なるケースが考え得るため、いつ、どう衝突したかは物理シミュレーションでは重要な問題		十分にフレームレートが高く、ゲーム用ということであれば、衝突時刻までの経過時間割合を元にした両者の運動状態を線形補間で近似値を取るのも悪くないかもしれない

回転する物体同士の衝突判定は難しい?

　ただ、実は、このCSOを算出するのがそれほど簡単なことではなく（ミンコフスキー差の算出など）、それもリアルタイムで行なわなければならないため、この点についてはさまざまなCSO獲得のためのテクニックが各所で研究されている。

　セッション終了後の質疑応答の時間帯では、「回転運動していた場合は離散的単位時間ごとに求めるCSOでは不十分なのでは?」という鋭い質問が飛びだし、これに対して講演者は「確かに、高速回転している物体同士ではこの手法では不十分で、何か別の工夫を考案しなくてはならないかもしれない」と答えていた。

　近年、ゲーム向けに物理シミュレーションの導入が流行しているが、追求されるリアルタイム性と、期待される精度の関係性においては、まだまだ進化の途上ということなのだろう。

■ GPU向けに物理シミュレーションを実装する方法

原田隆宏氏（AMD）

　昨日の「Advanced Visual Effects with DirectX 11」で登壇したAMDの原田隆宏氏は、本日は「Physics for Game Programmers」の方でも登壇し、「DESIGINING PHYSICS ALGORITHMS FOR GPU ARCHITECTURE」（GPU向けに物理シミュレーションを実装する方法）という題目の講演を行なった。

　「物理シミュレーションというテーマが、CPUよりもGPUに向いている」とよく言われるが、これはどうしてなのか。

　CPUは複雑なロジックを処理するのに長けているが、同時多発的に大量の演算を行なうことには向いていない。

　CPUプログラムはあるひとまとまりのアルゴリズムを高速に処理するために進化を遂げてきたのに対し、GPUはある基本的なアルゴリズムを大量のデータに対して一気に適用するために進化してきた経緯がある。

　しかし、進化と共に両者は互いの美点を取り込みだし、近年では、両者は似たもの同士になるための歩み寄りを始めている。その1つがCPUとGPUの統合化だったり、CPUのマルチコア化だったり、GPUのプログラマビリティ向上やキャッシュ構造およびメモリ階層の改善だったりするのだが、こうした進化型の近代プロセッサに適したテーマとして物理シミュレーションが浮上してきており、その実装に際しては様々な試みが行なわれている。

AMD RADEON HD5870のスペックとアーキテクチャ

　原田氏の講演は、まさにそうした試みの1つということになる。

　さて、原田氏はかつてHAVOKに所属していた経験を持つ人物だが、今はAMDの人間と言うこともあり、彼が講演で引き合いに出すGPUは表向きはAMDのRADEON系GPUを指すことになるが、話はDirectComputeに置き換えて捉えても大きな問題にはならない。

　GPUで物理シミュレーションを実装する際に気を付けなければならないのは、ロジックの分岐実行を多発させるとGPUの並列性の旨味が出てこなくなってしまうという点だ。

　例えば多面体同士の衝突判定に用いられるGJKアルゴリズム（Gilbert・Johnson・Keerthi distance algorithm）では、2つの立体物の最小距離を求めるために数回の反復計算を行なわせることになるが、これをGPUで並列実行させる実装にしても、結局、その結果ごとの処理の場合、分ける作業が必要となるため、GPU向けとは言い難い。

GPUの各コアの実行で分岐が起きたときには、分岐したときの命令と分岐しないときの命令は各スレッドで並列実行されない。分岐したときの命令と分岐しないときの命令の両サイクル分が全スレッドに掛かってしまう。これがGPUにおいて分岐が遅くなる理由

　原田氏は、これをGPUを模したシンプルな図で解説した。プログラムとしてはシンプルに見えても、GPUにおいてはそうでもない。GPU内部の各コア（RADEON系ではSIMDユニットになるが、一般的な概念として“シェーダーユニット”と置き換えて解釈してもらってもいい）はSIMT（Single Instruction, Multiple Thread。1つの命令を複数のスレッドに並列実行させるという実行形態のこと）実行がなされているため、分岐が起きたときには、分岐先の各命令を、グループ内の全スレッドに対して実行するか/しないかの場合分けで処理していくことになるので、並列性は阻害されてしまうのだ。

　そこで、GPUの向きのアルゴリズムの実装を考えなければならない。それは分岐を起こさず、並列性を徹底させるアルゴリズムだ。極端な話を言えば、並列性さえ徹底できれば、行なった演算がある程度無駄になってもいい。

　原田氏が例で挙げたアルゴリズムは、衝突判定をパーティクル単位に落とし込むものだ。この場合、3Dモデルは、その形状に近いパーティクルの集合体の形で近い値を取る。

　GPU内の各SIMDユニットで動作するスレッドは各パーティクルごとの衝突判定処理となり、並列性は維持されたまま実行ができる。もちろん、多くのパーティクルにおいては、全く衝突に絡まず、衝突判定の演算そのものが無駄になる場合も出てくるがそれは構わないのだ。

GPU内の各SIMDユニットで動作するスレッドは各パーティクルごとの衝突判定であり、完全に独立したタスクになるので同時並列実行が可能。衝突にまったくからまないパーティクルも続出するがそれはもうよしとする

　GPU内の各SIMDユニットは、複数からなるパーティクル衝突判定の処理を並列に実行することができるが、これを1つのグループとして管理している（DirectComputeにおける“グループ”と同義）。

　各SIMDユニットは、1つのグループの処理ではなく、実は複数のグループの処理を受け持っており、あるグループの処理において、メモリアクセスが発生したときに別のグループの処理に切り替えるスイッチングを行なっている。

各SIMDユニットは、1つのグループではなく、複数のグループの実行を受け持っている

　メモリアクセスはとてつもなく遅い処理であるため、あるグループがメモリ読み出しをリクエストして、その値が読み出されて帰ってくるまでの待ち時間に、別のグループの処理をオーパラップして開始してしまうのだ。

　これがメモリアクセス遅延時間の隠蔽に繋がる。

　逆に言うと、メモリアクセスの待ち時間の間にSIMDユニット内の演算リソースを遊ばせておくのがもったいないので、待ち時間の間独立した別スレッドを実行させて演算リソースを積極活用しよう……ということでもある。ちなみに、インテルのCPUのHyper-Threadingに代表されるSMT（Simultaneous Multithreading）技術も、このアプローチによるパフォーマンス向上技術の1つである。

メモリアクセス時の待ち時間に、スレッドグループを切り替えてメモリレイテンシーを隠蔽する。これはGPU側が勝手に自発的に行なってくれること

　原田氏は、こうしたGPUで実装した物理シミュレーションのパフォーマンスを向上させるためには、その処理の実行になるべく使用レジスタを少なくし（変数を少なく）することも心がけるべきだ、と指摘した。これは、レジスタ使用を少なくすれば各SIMDユニットにて、より多くのグループを取り扱えるようになるためだ。

レジスタの使用を節約すればより多くのスレッドを実行できる	超高速なLDSを積極利用すれば遅いメモリアクセスを繰り返さなくて済むためパフォーマンスアップに繋がる

　どうしてもレジスタの使用が多くなるというのであれば、グループ内で共有して利用できるLocal Data Store（共有メモリのこと。DirectComputeにおけるTGSM:Thread Group Shared Memoryと同義）の利用に代替させることを考える必要がある。

　こうして見てくると、CUDAやDirectComputeに代表されるGPGPUプラットフォーム向けの物理シミュレーションは、そのアルゴリズムをかなりGPU向けに最適化した上で実装しなければならないことに気づかされる。

　いわゆる、マルチコアCPU向けの一般的なマルチスレッディングプログラムとは少々異なった並列プログラミングのやり方だ。むしろ、HPC（High Performance Computing）分野でのプログラミング技法に近いといえる。

原田氏が実装したGPUベースの物理シミュレーション。形状をパーティクルで近似し、衝突判定はそのパーティクル単位で行なっている。このようにうまくGPUに実装できれば数千個に及ぶ剛体物理シミュレーションを実践的なフレームレートで実行が可能