Gゼミ
2010/1/7
発表者 渡辺健人
陰関数曲面との交差判定法

前提条件


陰関数曲面が存在する区間は効果半径球内のみ
方法

視点に近い順にレイと球との交差点を求め、連続する2
つの交差点間で陰関数曲面と交差判定を行う
最も単純な方法



1.BVHを用いて、最も近いレイと球との交差点を
求める
2.交差点を求めたら、その交差点と1つ前の交差
点との間で陰関数曲面の交差判定を行う
3.陰関数曲面との交差判定に成功したら終了
失敗したら、レイの始点を新しい交差点に更新し、
1に戻る
問題点


各交差点を求めるのに毎回BVHの根から交差判
定を行う必要がある
1つのレイに対して、同じノード、球と何度も交差判
定を行う必要が生じる
区間の求め方 その1(copy)

アイディア:


ここで用いる情報:



交差点を求める際に、1つ前の交差点を求めたときの
情報を使うともう少し効率よく区間を求められる
BVHと交差判定をした際に、最初にレイと交差する球
を含むノードとそのときのスタック
交差点を求める際に、前回保存したノードとスタッ
クから交差判定を始める
利点:

レイと交差する最初の葉ノードまでたどるコストが減る
問題点

最初のノード以降は最初の方法と変わらず、同じ
球と何度も交差判定を行うことになる
1000個の球に対して反射を考慮
左が2回、右が5回まで
BezierClip
BVH trav
total time
ray/sec
total ray
方法1 方法2(copy)
0.613
0.609
2.114
1.800
4.544
4.218
0.000046
0.000043
98188
98188
BezierClip
BVH trav
total time
ray/sec
total ray
方法1 方法2(copy)
0.670
0.663
2.225
1.885
4.789
4.427
0.000047
0.000044
101104
101104
1000個の球に対して屈折を考慮
左が2回、右が5回まで
BezierClip
BVH trav
total time
ray/sec
total ray
方法1 方法2(copy)
5.758
5.810
12.240
9.523
27.150
24.510
0.000277
0.000250
98188
98188
BezierClip
BVH trav
total time
ray/sec
total ray
方法1 方法2(copy)
5.958
5.952
12.800
9.885
28.350
25.400
0.000201
0.000180
141339
141256
1000個の球に対して反射を考慮
左が2回、右が5回まで
BezierClip
BVH trav
total time
ray/sec
total ray
方法1 方法2(copy)
0.768
0.776
2.898
2.449
5.687
5.262
0.000062
0.000057
92162
92161
BezierClip
BVH trav
total time
ray/sec
total ray
方法1 方法2(copy)
1.026
1.004
3.635
2.944
7.062
6.314
0.000063
0.000056
111914
111913
1000個の球に対して屈折を考慮
左が2回、右が5回まで
BezierClip
BVH trav
total time
ray/sec
total ray
方法1 方法2(copy)
2.653
2.652
8.049
6.423
15.260
13.260
0.000166
0.000148
92162
92161
BezierClip
BVH trav
total time
ray/sec
total ray
方法1 方法2(copy)
4.588
3.709
12.360
8.766
23.530
18.360
0.000046
0.000043
172354
156790
区間の求め方 その2(sort)

アイディア

陰関数曲面と交差しない場合の高速化



BVHを最初から最後までたどると、すべての球との交差点が
求まる、それをソートして前から順番に陰関数曲面と交差判
定を行えばよい
陰関数曲面と交差する場合を考慮する

すべての球との交差点が必要になるとは限らない

そこで、BVHをたどる際に視点に近い方の葉ノードから、球
との交差点を求め、交差点をソートしながらたどると、現在の
葉ノードの前面よりレイに近い交差点の順番は確定するので
、確定した交差点間で陰関数曲面と交差判定を行えばよい
利点

1つのレイに対して、各ノード、球とは1回しか交差判定
をしなくてよい
10000個の球
total time
方法1 方法2(copy)
3.402
2.910
方法3(sort)
1.782
今後の予定
•
方法1にバグがあるので、その修正
•
方法2の実装を完成させる
•
論文を書く
ダウンロード

Gゼミ 2010/1/7 発表者 渡辺健人 陰関数曲面との交差判定法 前提条件