我々の身近にはコンピュータグラフィックス(CG)を駆使した映像が多く存在する.多くの研究によりCGのライティング技術が向上しCGの映像は実写に近づいてきている.しかし物体の挙動は一般的に手作りであることが多く, 作成されたアニメーションは物理法則に基づいているわけではないため,不自然に見えるという問題が生じている.そこでCGの分野でも数値シミュレーションを用いて物体の挙動の計算が行なわれるようになった.例としてゲームなどのリアルタイムアプリケーションがあるが,ここではユーザの入力が一意に決まっておらず,応答をその場で計算を実行しなければならない.そのためリアルタイムアプリケーションでは時間の制約により高速なシミュレーションが求められる.

現在,リアルタイムアプリケーションにおいて剛体シミュレーションは多く用いられているが,流体計算は一般的に剛体計算に比べると計算コストが高いため,リアルタイムに計算することが困難である.流体の計算手法としては格子法と粒子法があるが,格子法を用いて自由表面流れを計算する場合,流体の速度以外に流体表面を追跡しなければならない.リアルタイムアプリケーションでは計算速度の制約が厳しいため高解像度の格子で計算することができない.しかし低解像度の格子での計算では移流による数値拡散などの問題が発生する.一方,計算空間を分割せず流体を粒子の集合として表現し,支配方程式を粒子間相互作用にして粒子の運動を計算する粒子法では,粒子自体が移動することによって移流計算を行なうため,移流による数値拡散が生じないという利点や,自由界面の追跡を行なう必要がないという利点がある.そのため粒子法における流体計算はリアルタイムアプリケーションに適していると考えられるが,本研究の開始時点ではリアルタイムで計算できる粒子数が少なく,視覚的に十分な結果は得られていなかった.

また最近までCentral Processing Unit(CPU)は周波数を増加させその演算性能を向上させてきたが,周波数増加による性能向上は突然終焉を迎え,プロセッサテクノロジは複数のプロセッサを1CPUに搭載させ,並列で演算をすることにより演算の効率性を向上させる方向に進み始めた.またグラフィックスの描画専用のGraphics Processing Unit(GPU)は以前から多くのプロセッサを1GPU上に搭載し,並列で演算を行ない高い演算性能を出すように設計されてきた.しかしここで問題が生じる.それは従来の1プロセッサ用に開発していたアルゴリズムを用いて,これらのマルチコアプロセッサの能力を引き出すことができないということである.そのためマルチコアプロセッサの性能を引き出すためにはそれらにあわせた並列計算アルゴリズムの開発が必要であり,今後その重要性は一層高まると考えられる.

これらをふまえ,本論文ではまずリアルタイムアプリケーションを含めた映像制作のための粒子法を開発する.そしてまた粒子法シミュレーションのアルゴリズムを並列化し,マルチコアプロセッサとしてGPUを用いた粒子法の高速化手法を開発する.そして最後にここまでの研究をさらに拡張し,複数のGPUを用いた粒子法シミュレーションの高速化手法を開発する.

第一部では映像制作のための粒子法の開発を行なった.粒子法では壁境界を扱うときには,一般的に壁境界を壁粒子に変換して計算を行なう.非圧縮流体解析が可能な粒子法であるMoving Particle Semi-Implicit(MPS)法では圧力を流体と同様に計算する圧力計算壁粒子と,その粒子数密度の低下を防ぐための粒子の2種類が必要である.壁粒子を用いると境界の斜面を正確に表すことができないという欠点があり,計算結果だけでなく視覚的結果に影響を及ぼす.またこれらの壁粒子は全体の粒子数の中の大きな割合を占め,圧力のポワソン方程式を大きくし,計算効率を低下させている.この壁粒子の問題はMPS法だけではなく,粒子法の流体の計算手法の1つであるSmoothed Particle Hydrodynamics(SPH)でも同様である.そこで本研究ではMPS法とSPHにおいて壁粒子を用いない壁境界計算手法を開発した.この手法は壁境界からの距離で壁の寄与を数値的に求めるため,壁粒子を用いた場合のように斜面で粒子がスムーズに流れないという問題を解決した.

また粒子法シミュレーションでは近傍粒子探索においてはデータの構築とアクセスが高速であるユニフォームグリッドがよく用いられるが,ユニフォームグリッドはメモリ効率が悪いという問題点があった.一方,四分木などの階層格子はメモリ効率は良いが,データへのアクセスの効率が悪い.動的にデータを構築し,さらに頻繁にこれらにアクセスをくり返す粒子法には致命的である.そこで本研究ではデータへのアクセス効率が良く,さらにメモリ消費量も少ないスライスグリッドを開発した.定量的比較により,スライスグリッドはユニフォームグリッドとほぼ同じ速度でデータの構築とアクセスが可能であるだけでなく,四分木と同等のメモリしか消費しないということを示した.スライスグリッドを用いることによってメモリ効率よく計算することが可能になったが,これは同時に同じ大きさのメモリを用いることが可能であれば,より広い計算領域を計算することができるようになったということである.

粒子法の計算結果を流体として可視化するためには,粒子から流体表面を定義しなければならない.一般的にそれぞれの粒子に濃度分布を持たせ,それらの和の陰関数をある閾値で切り出して流体表面を求める.しかしこのように表面を求めると流体表面に凹凸が残ったり,薄い膜や鋭いエッジを表現するのが困難であった.そこで本研究では2段階で流体粒子から表面を構築する手法を開発した.この手法を用いることで粒子法の計算結果の可視化において薄い膜や鋭いエッジを持つ表面を計算粒子から構築することが可能になり,流体の可視化において表現の幅が広がった.

第二部では粒子法シミュレーションを並列化し,GPUを用いて様々な粒子法シミュレーションを高速化した.GPUを用いて物理シミュレーションを高速化する様々な研究が行なわれてきたが,それらは全て計算ノードの接続関係が計算中に変化しないという共通点を持っていた.例えば格子を用いた流体計算では各計算点はその計算点を囲む点のみと相互作用し,布のシミュレーションでは質点同士の接続は計算中に変化しない.しかし粒子法では,計算粒子は自由に動くことが可能であり,タイムステップごとに相互作用する計算粒子が変化する.そのため,計算粒子の近傍粒子を探索しなくてはならない.接続関係が動的に変化する粒子法シミュレーションを GPUを用いて高速化する際に問題になるのは近傍粒子探索であり,今まではそれを実現した研究は存在しなかった.そこで本研究ではまずユニフォームグリッドを用いた近傍粒子探索をGPU上で実行する手法を開発した.そしてこの手法を第一部で開発したスライスグリッドに応用して,スライスグリッドを用いた近傍粒子探索をGPUで行なう手法を開発した.これらにより粒子法を含め,計算要素間の接続関係が動的に変化するシミュレーションをGPUを用いて高速化することが可能になった.

そして手法の応用としてまずDEMを用いた粉体,SPHを用いた流体のシミュレーションを高速化し,両方のシミュレーションで約十倍以上の計算の高速化を実現した.本研究に数万の粒子をリアルタイムで計算することが可能になり,粒子数高解像度のシミュレーションをリアルタイムアプリケーションで用いることができるようになった.本研究で開発したGPUを用いた近傍粒子探索手法は粒子法を用いた粉体や流体シミュレーション以外の計算にも有効である.そこで本研究ではこれらのシミュレーション以外に,粒子を用いた剛体,布,そしてそれらの連成計算に本手法を応用した.粒子間の力が粒子間距離から計算されるDEM等のペナルティベースの手法の欠点としては大きなタイムステップを刻めないということである.一方,撃力ベースの手法ではそのような制約がないが,計算がデータ並列ではないためGPUを用いて高速化することができなかった.そこで本研究では撃力ベースの剛体シミュレーションをGPUを用いて高速化する手法を開発した.また粒子法でも不均一な粒子径を用いる研究も行なわれてきている.そこで本研究ではそのような計算体系に有効な木構造を用いた衝突検出手法を開発した.

最後に複数のGPUを用いた粒子法の高速化手法を開発した.この手法ではサーバとなる全てのデータを管理するプロセッサを置かず,計算領域を分割し,それぞれのGPUが一領域を受け持ちそのデータ管理を行なう.特にこの手法は計算の周期が速いリアルタイムアプリケーションを目標としており少しの無駄な計算さえも如実に結果に現れる.よってデータ管理において,近傍粒子探索を効率化するために構築した格子を再利用することによって動的なデータ管理のオーバーヘッドを押さえ,計算を行なうGPUの数にほぼスケールした計算性能を出した.また4個のGPUを用いることによって100万粒子のシミュレーションの1タイムステップを約30msで計算することが可能になった.

本論文は、映像制作のための粒子法を開発するとともに、様々な粒子法のアルゴリズムを並列化することでマルチコアプロセッサを用いた高速化をおこない、その結果、リアルタイムアプリケーションに用いることができる、高速かつ高解像度の粒子法シミュレーションを実現したものである。本論文は2部9章で構成されている。

第1章は序論で、本研究の背景、従来の研究および本研究の目的が述べられている。

第1部では映像制作のための粒子法の開発が述べられている。第2章および第3章の内容は、流体解析にこれまで用いられているMoving Particle Semi-Implicit(MPS)法およびSmoothed Particle Hydrodynamics(SPH)に対して、壁面境界条件として壁の外側に粒子を配置しない計算手法が開発されたことである。本手法により3次元複雑形状の粒子法シミュレーションにおいて計算容量の低減と計算速度の向上が実現された。

第4章では粒子法シミュレーションにおける近傍粒子探索のアルゴリズムとして、スライスグリッドが提案されている。そして定量的比較により、スライスグリッドは従来のユニフォームグリッドとほぼ同じ速度でデータの構築とアクセスが可能であるだけでなく、従来の四分木と同等のメモリしか消費しないということを示した。これによってより大規模な計算が可能になった。

第5章では2段階で流体粒子から流体表面を構築する手法を開発した。この手法を用いることで粒子法の計算結果の可視化において、薄い膜や鋭いエッジを持つ表面を構築することが可能になり、粒子法シミュレーションを用いた映像制作の品質を向上させることに貢献した。

第2部では粒子法シミュレーションを並列化し、マルチコアプロセッサであるGraphics Processing Unit(GPU)を用いて様々な粒子法シミュレーションを高速化する技術を開発した。第6章ではユニフォームグリッドを用いた近傍粒子探索をGPU上で実行する手法を開発した。さらにこの手法を第1部で開発したスライスグリッドに応用して、スライスグリッドを用いた近傍粒子探索をGPUで行なう手法を開発した。これらの成果により粒子法シミュレーションをGPUを用いて大幅に高速化することができた。

第7章では様々な粒子法シミュレーションのアルゴリズムの並列化をおこない、GPUを用いてその有効性を確認した。それらは、Discrete Element Method(DEM)を用いた粉体シミュレーション、SPHを用いた流体のシミュレーション、粒子を用いた剛体シミュレーション、流体と剛体との連成計算、流体と布との連成計算、弾性体シミュレーション、撃力を用いる剛体シミュレーション、木構造を用いた広域衝突検出である。特にDEMとSPHでは約10倍以上の計算の高速化を実現した。これにより数万粒子をリアルタイムで計算することが可能になり、高解像度のシミュレーションをリアルタイムアプリケーションで用いることができるようになった。

第8章では複数のGPUを用いた粒子法シミュレーションの高速化が示されている。この手法ではサーバとなる全てのデータを管理するプロセッサを置かず、計算領域を分割してそれぞれのGPUが1領域を受け持ってそのデータ管理のみを行なうものである。そのデータ管理において、近傍粒子探索を効率化するために構築した格子を再利用することによって動的なデータ管理のオーバーヘッドを押さえ、計算を行なうGPUの数にほぼスケールした計算性能を出している。また4個のGPUを用いることによって100万粒子のシミュレーションの1タイムステップを約30msで計算することを可能にしている。

第9章は結論であり、本研究がまとめられている。

以上を要するに、本論文では、映像制作のための粒子法の開発をおこなうとともに、様々な粒子法の並列計算アルゴリズムを考案してマルチコアプロセッサを用いた高速化をおこなっている。その結果、リアルタイムアプリケーションに用いることができる、高速かつ高解像度の粒子法シミュレーションを実現している。こうした成果は今後の計算科学技術の進展に寄与するところが少なくない。

よって本論文は博士(工学)の学位請求論文として合格と認められる。