階層的空間 構造を用いた陰関数曲面の高速なレイトレ

階層的境界ボリュームを用いた
陰関数曲面の高速なレイトレーシング法
西田研究室
渡辺健人
発表の流れ





研究の背景・目的
関連研究
提案法
結果
まとめと今後の課題
発表の流れ





研究の背景・目的
関連研究
提案法
結果
まとめと今後の課題
研究の背景

レイトレーシング


3次元シーン上での視線の経路を追跡するこ
とでリアルな画像が生成できる
欠点:計算コストが大きい
[Wald06]
研究の背景(2)

陰関数曲面

少数のプリミティブでなめらかな曲面を表現できる
直接描画することで正確に曲面を表現可能

ここではメタボールを扱う

[Knoll07]
研究の目的

多数のメタボールに対する高速なレイト
レーシング方法の開発


多数のメタボールに対するレイキャスティング
はあるが、レイトレーシングはない
レイトレーシングは計算コストが高いので高速
化が必要
屈折1回のみ
3回まで屈折を追跡
発表の流れ





研究の背景・目的
関連研究
提案法
結果
まとめと今後の課題
関連研究(1)

レイトレーシング


再帰的にレイの経路を追跡することで、反射、屈折、
影などの現象を扱う手法 [Whitted 1980]
大規模なシーン向けの高速化

Bounding Volume Hierarchy(BVH),kd-treeなどの空間デー
タ構造を用いた手法 [Wald 2007]
[Whitted80]
[Wald07]
関連研究(2)

陰関数曲面

任意の陰関数曲面のレイトレーシング
[Knoll et al. 2007]



長所:任意の陰関数曲面を扱える
短所: 区間演算法を用いているので計算量が大きい
多数の動的なメタボールのレイキャスティング
をGPUで高速化 [Kanamori et al. 2008]


[Knoll07]
長所:大量の動的なメタボールをリアルタイムで描画可能
短所:反射、屈折などは1回までしか扱えない
[Kanamori08]
メタボールとは


空間上に配置された密度を持った球
各球の密度を足してできる密度場の等値面に
よって表現される陰関数曲面
メタボールとの交差判定

[Nishita et al. 1994]の方法による

メタボールの曲面は球内にのみ存在する


球との交差判定行い、球内でのみ曲面との交差判
定(BezierClipping)を行う
さらに、曲面との正しい交点を効率よく求める
ために球内でも交差判定を行う範囲を分ける
メタボールとの交差判定
メタボールとの交差判定
メタボールとの交差判定
メタボールとの交差判定
メタボールとの交差判定
メタボールとの交差判定
発表の流れ





研究の背景・目的
関連研究
提案法
結果
まとめと今後の課題
提案法

メタボールの交差判定でのボトルネックは
区間を求めるための球との交差判定部分


球との交差判定の高速化に2分木の空間
データ構造であるBVHを用いる
区間の求め方を2種類検討した


1区間ずつを高速に求める
1度に複数区間求めることで高速化
レイと球との交差判定

レイと球との交差判定


空間データ構造なしの場合:
レイとすべての球との交差判定を行い、最も
近い交点を求める
BVHを用いれば高速化できる

プリミティブ(今回は球)の集合をつつむ領域による
2分木構造
BVH
BVH
BVH
BVHを用いた球との交差判定
A
B
D
E
C
F
G
Stack
BVHを用いた球との交差判定
A
B
D
E
C
F
G
Stack
BVHを用いた球との交差判定
A
B
D
E
C
F
G
Stack
BVHを用いた球との交差判定
A
B
D
E
C
F
G
Stack
BVHを用いた球との交差判定
A
B
D
C
E
F
G
Stack
D
BVHを用いた球との交差判定
A
B
D
E
C
F
G
Stack
球との交差判定(2回目)
A
B
D
E
C
F
G
Stack
球との交差判定(2回目)
A
B
D
E
C
F
G
Stack
球との交差判定(2回目)
A
B
D
E
C
F
G
Stack
球との交差判定(2回目)
A
B
D
E
C
F
G
Stack
曲面との交差判定
A
B
D
求まった交点間で曲面との交差判定を行う
交点が求まらなければ、球との交差判定をも
う一度行う
E
C
F
G
Stack
方法1


同じレイでBVHを複数回たどると余分な交
差判定を繰り返すことになる
2回目以降は交差判定が必要なノードから
判定を開始

経路は基本的に同じなので、最初に球と交差
したノードとスタック
BVHを用いた球との交差判定
A
B
D
E
C
F
G
Stack
BVHを用いた球との交差判定
A
B
D
E
C
F
G
Stack
BVHを用いた球との交差判定
A
B
D
E
C
F
G
Stack
BVHを用いた球との交差判定
A
B
D
C
E
F
G
Stack
D
BVHを用いた球との交差判定
A
B
D
E
C
F
G
Stack
球との交差判定(2回目)
A
B
D
E
C
F
G
Stack
球との交差判定(2回目)
A
B
D
E
C
F
G
Stack
球との交差判定(2回目)
A
B
D
E
C
F
G
Stack
球との交差判定(2回目)
A
B
D
E
C
F
G
Stack
球との交差判定(2回目)
A
B
D
E
C
F
G
Stack
方法2

複数の区間を1度に求める

最も単純な方法


全交点を求め、ソートすれば全区間が求まる
BVHを用いれば、レイに近い順の交点を部分
的に求められる


交点を順次ソートしながらたどる
スタックに積む際にノードをソートしながら積む
BVHを用いた球との交差判定
A
B
D
E
Stack
C
F
G
BVHを用いた球との交差判定
A
B
D
E
Stack
C
F
G
BVHを用いた球との交差判定
A
B
D
E
Stack
B
C
F
G
BVHを用いた球との交差判定
A
B
D
E
Stack
B
C
F
G
BVHを用いた球との交差判定
A
B
D
E
Stack
C
F
G
BVHを用いた球との交差判定
A
B
D
E
Stack
C
F
G
BVHを用いた球との交差判定
A
B
D
E
Stack
D
C
F
G
BVHを用いた球との交差判定
A
B
D
E
Stack
C
F
G
BVHを用いた球との交差判定
A
B
D
E
Stack
C
F
G
結果

実行環境



Core 2 Duo 2.00GHz, Memory 2GB
2スレッドで計算
画像サイズは640x480
実行時間のグラフ(時間はsec)
ランダムに生成した球に対する結果で、屈折を3回まで
実行時間のグラフ(時間はsec)
ランダムに生成した球に対する結果で、反射を3回まで
結果 例1
20個のメタボールに対して4回まで反射を考慮(0.23sec)
右図は左図の赤い部分の拡大図
結果 例2
5000個のメタボールに対して3回屈折を考慮
結果 例3
8351個のメタボールに対して3回屈折を考慮(2.68sec)
発表の流れ





研究の背景・目的
関連研究
提案法
結果
まとめと今後の課題
今後の課題

球との交差判定のさらなる高速化



質の高いBVHの構築方法
GPUによる実装
メタボール以外の陰関数曲面の描画

Sparse Low degree Implicit(SLIM)曲面など
まとめ

多数のメタボールに対する高速なレイト
レーシング方法の提案


BVHを用いた密度球との交差判定の高速化
曲面が存在しうる区間を高速に求める方法を
示した



方法1:1つの区間を求めることを高速化
方法2:1度に複数求めることによる高速化
BVHを使っただけの方法より、方法1では10
~20%、方法2では3~4倍の高速化
ご清聴ありがとうございました