My initial BIH implementation

by syoyo

This is my initial BIH implemetation.
BIH を実装してみました。

http://lucille.atso-net.jp/svn/angelina/spatial/bih/

今回はトラバーサルも込みです。BIH の欠点を見つけました。
それは、大きなポリゴン(1 枚のポリゴンでできた床とか)があると、
トラバーサルのコストが wost case の O(N) になってしまうことです。

いくつかのシーンでテストしましたが、ここでは 1 万ポリゴンの happy buddha のシーンを取り上げます。

BIH ツリーの統計は以下の通り。

=== BIH tree statistics ============================
nNonEmptyLeaves : 7377
nEmptyLeaves    : 0
nBifurcations   : 7376
maxDepth        : 19
nTriangles      : 10002
maxTris/leaf    : 26
aveTris/leaf    : 1.355836

床なし版 

bih_noplane.png
 
 nRays            = 65536
 nCandidateTrianglesToTest = 5173440 (78.940430 tris/ray)
 nActuallyTestedIsectTris = 181236 (2.765442 tris/ray)
 nFailedIsectTris = 5153594 (78.637604 tris/ray)
 nTraversals      = 12986098 (198.152130 trav/ray)

スクリーンショットはレンダリング結果です。色は法線を出しているだけなので、特に意味はありません。
実際にテストした三角形の数は 2.7 tris/ray と、交差判定数ではかなり理想値に近いです。
(背景では 0 tris/ray なので、実際の可視部分ではもう少し増えますので 5 tris/ray くらいでしょうか)

トラバースの回数は結構多いです。しかしパケットトラバースなどすれば、実際には 1/4 – 1/10 には減るでしょうか。

床(2 polygon で構成)あり版

bih_show_split.pngbih_with_plane.png
 nRays            = 65536
 nCandidateTrianglesToTest = 444096622 (6776.376678 tris/ray)
 nActuallyTestedIsectTris = 1539230 (23.486786 tris/ray)
 nFailedIsectTris = 444042139 (6775.545334 tris/ray)
 nTraversals      = 656813420 (10022.177429 trav/ray)

はっきり言ってありえません。ほぼ全レイが worst case のトラバース量になっています。
レンダリング時間もアホみたいに遅くなりました。
(あと、床なし版は 90 度回転しているので、法線色が床あり版と異なっています)

ある意味これはしょうがないことで、巨大なポリゴンがあると、
シーンのバウンディングボックスのインターバル区間 = そのポリゴンのインターバル区間
となり、いくら細分割したところでインターバルが狭くならず、ほぼすべてのツリーをトラバース
しなければならなくなってしまうためです。
また今回さらに悪いのは、ツリーの最初の分割面が床に垂直になっていますが、
ここで切ると、床ポリゴンの一枚は手前に、もう一枚は奥に割り振られてしまい、どのレイもルートの両方の子ノードをたどらなければならなくなってしまうことです。

論文では、このような巨大なポリゴン問題があることを認めていますが、

「我々の手法はプロダクション向けを考えている。プロダクションでは、そんなローポリなシーンなんてつかわねーんだよ。バリバリディスプレースメントマップ使うから、そんなケース(一枚の大きな床ポリゴン)なんて生じねー。だから問題ないね。」

と説明しています。これは正直賛同しかねます。オフラインやプロダクションでしたら、どのような入力シーンにも対応できるべきですから。
(少なくとも mental images の技術顧問?っぽいことをしている Alexander Keller が言う言葉ではないと思うのですが、、、それとも mental ray 使いは皆、バリバリディスプレースメントマップ使ったハイポリシーンを使うのがデフォルトなのでしょうか?)
あと、この問題が実は wost case のトラバーサルコストになることも書かれていないのも問題です。

デザイナやプログラムがあらかじめポリゴン分割をするという前提では、BIH はよさそうです。
リアルタイムレイトレでは、うまくツリーが構築できるように結局シーンをいじるでしょうし。

しかしオフライン用途では、シーンの構成によっては worst case のトラバースがほとんどになってしまうという状況はちょっと使い物になりません。BKD も同じ問題を抱えていますが、こちらは分割面の選択により自由度があるため、もう少し問題は緩和されそうです。
(BIH では単純に最も長い軸を二分、としていますが、これが今回のような条件では問題になる)

うーん、やっぱりまずは軽く一様グリッドで切りボクセルトラバースを行い、各グリッドセルでは BKD or BIH を使うという手法がやっぱり一番よさそうでしょうか。

それとも H-tree ならなんとかしてくれるでしょうか。こちらも実装してみたいですね。

V. Havran, R. Herzog, H.-P. Seidel: “On Fast Construction of Spatial Hierarchies for Ray Tracing”,
http://www.cgg.cvut.cz/~havran/

Advertisements