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

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

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

研究の背景 レイトレーシング ３次元シーン上での視線の経路を追跡することでリアルな画像が生成できる 欠点：計算コストが大きい レイトレーシングは視線を追跡することで、反射、屈折、影等の影響を考慮して写実的な画像を生成できる方法です。 欠点としては、各画素ごとに別々に計算するので計算コストが大きい。 [Wald06]

研究の背景（２） ここではメタボールを扱う 陰関数曲面 少数のプリミティブでなめらかな曲面を表現できる 直接描画することで正確に曲面を表現可能 ここではメタボールを扱う CGで扱う面の表現としては、ポリゴンメッシュ、陽関数、陰関数によるものがあります。 今回は、直接描画することで正確に描画できる陰関数、その中でも、メタボールを扱います。 [Knoll07]

研究の目的 多数のメタボールに対する高速なレイトレーシング方法の開発 多数のメタボールに対するレイキャスティングはあるが、レイトレーシングはない レイトレーシングは計算コストが高いので高速化が必要 メタボールは流体のシミュレーションなどに使われますが、多数のメタボールに対して曲面を近似せずにレイトレーシングを行ったものはない。 屈折１回のみ ３回まで屈折を追跡

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

関連研究（１） レイトレーシング 再帰的にレイの経路を追跡することで、反射、屈折、影などの現象を扱う手法 [Whitted 1980] 大規模なシーン向けの高速化 Bounding Volume Hierarchy(BVH),kd-treeなどの空間データ構造を用いた手法 [Wald 2007] レイトレーシングの関連研究として [Whitted80] [Wald07]

関連研究（２） 陰関数曲面 任意の陰関数曲面のレイトレーシング [Knoll et al. 2007] 長所：任意の陰関数曲面を扱える 短所： 区間演算法を用いているので計算量が大きい 多数の動的なメタボールのレイキャスティング　　　　　をGPUで高速化 [Kanamori et al. 2008] 長所：大量の動的なメタボールをリアルタイムで描画可能 短所：反射、屈折などは１回までしか扱えない [Knoll07] [Kanamori0８]

メタボールとは 空間上に配置された密度を持った球 各球の密度を足してできる密度場の等値面によって表現される陰関数曲面 次にメタボールについて説明します。 メタボールは空間上に配置された密度を持った球の重ねあわせによってできる密度場の等値面によってできる曲面です。 図の青い曲面ができます。

メタボールとの交差判定 [Nishita et al. 1994]の方法による メタボールの曲面は球内にのみ存在する 球との交差判定行い、球内でのみ曲面との交差判定（BezierClipping)を行う さらに、曲面との正しい交点を効率よく求めるために球内でも交差判定を行う範囲を分ける 西田先生の方法の説明 区間の定義をきちんとする

メタボールとの交差判定 図のような場合について説明します。

メタボールとの交差判定 下のグラフはレイ上の各球の密度関数です。 ２つ目の区間では両方の密度関数の和によってあらわされる関数が閾値に達しているかがわかる必要があります。

メタボールとの交差判定 レイトレーシングでは最も近い交点が必要になるので、 図のような区間で交差判定を行います。

メタボールとの交差判定

メタボールとの交差判定 このように

メタボールとの交差判定 このように、球との交点によりレイを各区間に分けて曲面と交差判定を行いますが。 多数のメタボールの場合、ボトルネックはレイと球との交差判定部分になります。

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

提案法 メタボールの交差判定でのボトルネックは区間を求めるための球との交差判定部分 区間の求め方を２種類検討した 球との交差判定の高速化に２分木の空間データ構造であるBVHを用いる 区間の求め方を２種類検討した １区間ずつを高速に求める １度に複数区間求めることで高速化 メタボールとのレイトレーシングでは先ほど述べましたように レイと球との交差判定とレイと曲面の交差判定を行いますが、球の数が多い場合ボトルネックとなるのはレイと球との交差判定部分です。 そこで、提案法ではまず、球との交差判定をBVHを用いることで高速化します。 それに加えて、区間を１度に１つずつ求める方法と、複数求める方法のそれぞれを考え、 それぞれを高速化しました。

レイと球との交差判定 レイと球との交差判定 空間データ構造なしの場合： レイとすべての球との交差判定を行い、最も近い交点を求める 空間データ構造なしの場合：　　　　　　　　　　　　　　　　　レイとすべての球との交差判定を行い、最も近い交点を求める BVHを用いれば高速化できる プリミティブ（今回は球）の集合をつつむ領域による２分木構造 ここでは、まずレイと球との交差判定について説明します。 最も近い交点を求めるには空間データ構造がない場合にはすべてのプリミティブと交差判定が必要になり、プリミティブの数Nに対してオーダーNかかる。 BVHという２分木の空間データ構造を用いることでプリミティブの数Nに対して大体logNですむ BVHは任意のプリミティブを扱えますが、ここではプリミティブは球となります。

BVH 次に、BVHについて説明します。 BVHは対象が球とは限らない

BVH

BVH

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G 遠いほうをスタックにつみます。 Stack

BVHを用いた球との交差判定 A B C D E F G Stack D

BVHを用いた球との交差判定 A B C D E F G Stack

球との交差判定(２回目） A B C D E F G Stack

球との交差判定(２回目） A B C D E F G Stack

球との交差判定(２回目） A B C D E F G Stack

球との交差判定(２回目） A B C D E F G Stack

曲面との交差判定 A B C D E F G 求まった交点間で曲面との交差判定を行う 交点が求まらなければ、球との交差判定をもう一度行う 求まった交点間で曲面との交差判定を行う　交点が求まらなければ、球との交差判定をもう一度行う Stack

方法１ 同じレイでBVHを複数回たどると余分な交差判定を繰り返すことになる ２回目以降は交差判定が必要なノードから判定を開始 経路は基本的に同じなので、最初に球と交差したノードとスタック 関連研究があればいれるべき

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack D

BVHを用いた球との交差判定 A B C D E F G Stack

球との交差判定(２回目） A B C D E F G ２回目はこうなります Stack

球との交差判定(２回目） A B C D E F G 本来ならこうなる Stack

球との交差判定(２回目） A B C D E F G Stack

球との交差判定(２回目） A B C D E F G Stack

球との交差判定(２回目） A B C D E F G Stack

方法２ 複数の区間を１度に求める 最も単純な方法 BVHを用いれば、レイに近い順の交点を部分的に求められる 全交点を求め、ソートすれば全区間が求まる BVHを用いれば、レイに近い順の交点を部分的に求められる 交点を順次ソートしながらたどる スタックに積む際にノードをソートしながら積む たどるノードをレイに近い順にすることで、レイに近いほうの

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack B

BVHを用いた球との交差判定 A B C D E F G Stack B

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack D

BVHを用いた球との交差判定 A B C D E F G Stack

BVHを用いた球との交差判定 A B C D E F G Stack

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

実行時間のグラフ(時間はsec) ランダムに生成した球に対する結果で、屈折を３回まで 図の差し替え

実行時間のグラフ(時間はsec) ランダムに生成した球に対する結果で、反射を３回まで 図の差し替え

結果　例１ 20個のメタボールに対して４回まで反射を考慮(0.23sec) 右図は左図の赤い部分の拡大図

結果　例２ ５０００個のメタボールに対して３回屈折を考慮

結果　例３ 8351個のメタボールに対して３回屈折を考慮(2.68sec)

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

今後の課題 球との交差判定のさらなる高速化 メタボール以外の陰関数曲面の描画 質の高いBVHの構築方法 GPUによる実装 Sparse Low degree Implicit(SLIM)曲面など 他の陰関数とは何か？

まとめ 多数のメタボールに対する高速なレイトレーシング方法の提案 BVHを用いた密度球との交差判定の高速化 曲面が存在しうる区間を高速に求める方法を示した 方法１：１つの区間を求めることを高速化 方法２：１度に複数求めることによる高速化 BVHを使っただけの方法より、方法１では１０～２０％、方法２では３～４倍の高速化 全体のまとめをする

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