階層的境界ボリュームを用いた 陰関数曲面の高速なレイトレーシング法 西田研究室　 渡辺健人

発表の流れ 研究の背景・目的 関連研究 提案法 結果 まとめと今後の課題

発表の流れ 研究の背景・目的 関連研究 提案法 結果 まとめと今後の課題

研究の背景 ３次元物体の表示はCGでは重要 より多くの現象を扱えることは重要 なめらかな曲面を扱えることは重要

研究の背景（２） レイトレーシング ３次元シーン上での視線の経路を追跡することで多くの現象を扱える 計算コストが大きい レイトレーシングのイメージ図

研究の背景（３） 陰関数曲面 曲面の表現の１種で少ないプリミティブでなめらかな曲面を表現できる ここではメタボールを扱う

研究の目的 多数のメタボールをレイトレーシングするのは計算コストが高い レイトレーシングでは反射、屈折等を考慮してよりリアルな画像を生成できる 多数のメタボールに対して高速にレイトレーシングを行いたい

発表の流れ 研究の背景・目的 関連研究 提案法 結果 まとめと今後の課題

関連研究（１） レイトレーシング 再帰的にレイの経路を追跡することで、反射、屈折、影などの現象を扱える An Improved Illumination Model for Shaded Display [T. Whitted 1980] Bounding Volume Hierarchy(BVH),kd-treeなどのレイトレーシング高速化用データ構造の特徴を説明 State of the Art in Ray Tracing Animated Scenes [I. Wald, et al 2007]

関連研究（２） 陰関数曲面 任意の陰関数曲面のレイトレーシング 多数の動的なメタボールのレイキャスティングをGPUで高速化 Interactive Ray Tracing of Arbitrary Implicit Functions [A.Knoll, et al] 多数の動的なメタボールのレイキャスティングをGPUで高速化 GPU-based Fast Ray Casting for a Large Number of Metaballs [Y.Kanamori et al]

メタボールとは 陰関数曲面の一種で球内で定義された密度関数を重ね合わせたものの等値面となる １つのメタボール 複数のメタボール

メタボールの描画方法 Nishita, Nakame(1994)の方法による まず、その区間に寄与する各メタボールの密度関数をBezier曲線形式に変換し、de Castejauのアルゴリズムで関数を区間に限定する Bezier曲線の各係数を足してできるBezier曲線がその区間での密度関数になる Bezier曲線との交差判定はBezierClippingを用いる これらを図を使いながら説明する 区間を求めるのにレイと球との交差判定を行う必要があり、球の数が増えると計算コストの割合が増える（ここを高速化した）

発表の流れ 研究の背景・目的 関連研究 提案法 結果 まとめと今後の課題

提案法 区間を求めるのにレイと球との交差判定を行う必要がある BVHによるレイのトラバースを２つの異なる方法で高速化を行った

レイと球との交差判定 レイと球との交差判定 レイとすべての球との交差判定を行い、最も近い交点を求める BVHを用いれば高速化できる

BVHを用いた球との交差判定

BVHを用いた交差判定

BVHを用いた交差判定

BVHを用いた交差判定

BVHを用いた交差判定

球との交差判定 BVHありとなしのときの実行時間の比較 生成した図

単純にBVHを用いた場合 単一のレイに対して、連続する区間を求めるときに、実際にBVHをたどる際に、重複した経路をたどることになることを図で説明する

案１ １回前にBVHをたどったときに最初にレイと交差する球を含むノードからはじめればよい 求めた最も近い交点の球を含むノードとは限らない

解説図 右の図のような場合 1ループ目は Aから探索を行う ２~6ループ目からは Bから探索を始めればよい 7ループ目からは 　Cから探索を始めればよい

案２ BVHをたどりときに、交点をソートしてくと、たどっている途中で区間が求められる 交点は１つの葉ノード内のみのソートでは不十分でノード間に渡ってソートする必要がある たどるノードをレイに近い順にすれば、BVHを探索中に区間が定まっていく

解説図 右の図のような場合 たどる経路はA->B->Cとなり Bで交点が４つ求まる 次にCでレイとCの近いほうの 　　交点より近いものは順序が確定する ここではBで求めた交点のうち２つの順序が確定する 求まった区間で曲面と交差判定を行い 交差すれば終了 交差しなければ、探索を続ける

特徴 案１について 案２について 長所：単純なものに対して根から最初に交差判定が必要になる葉ノードまでの探索コストが減る 短所：単純なものと同じで同じ球、同じノードと何度も交差判定が必要になることがある 案２について 長所：各球、ノードとの交差判定は１度のみ 短所：たどるノードの順序が変わるのでたどるノードをつむスタックのサイズが大きくなる 　交点をソートする必要がある

結果 実行環境 Core 2 Duo 2.00GHz, Memory 2GB ２スレッドで計算 画像サイズは640x480

結果　例１ 20個のメタボールに対して４回まで反射を考慮

結果　例２ 6000個のメタボールに対して４回まで屈折を考慮

結果　例３ 100000個のメタボールに対して３回反射を考慮

結果 例４ 左が屈折、右が反射を３回まで考慮したもの 効果球の数 1000個: 10000個:

実行時間について None 屈折 反射 Copy Sort 1000 4.64 2.91 3.87 2.41 1.49 0.94 10000 各手法について左が屈折、右が反射を考慮した場合の計算時間で単位は秒(sec) 一番左の列は効果球の数 None 屈折 反射 Copy Sort 1000 4.64 2.91 3.87 2.41 1.49 0.94 10000 12.68 3.84 10.12 3.11 3.23 1.17 100000 47.42 4.32 37.99 3.24 10.04 1.24 例１ 0.35 0.47 0.28 例２ 19.10 15.17 6.15 例３ 19.13 14.73 3.75

実行時間のグラフ １回でなく１０回とかの平均の時間をとる トレースの回数を変えたときの実行時間の変化

発表の流れ 研究の背景・目的 関連研究 提案法 結果 まとめと今後の課題

まとめ 曲面が存在しうる区間を高速に求める方法を示した

今後の課題 球が密集している場合にそこでの計算コストが高すぎる メタボール以外の陰関数曲面の描画 屈折が遅いのは基本的に球が密集しているところにレイが行きやすくなるから メタボール以外の陰関数曲面の描画

ご清聴ありがとうございました