spatial data structure considerations

by syoyo

最近、レンダリングのための空間データ構造をいろいろ再考し始めています。大規模なシーンを、いかに少ないメモリで処理するか、いかに交差するポリゴンの数を刈り込むか、いかに処理を cache-oblivious や streamable にできるか、が自分の中で重要になってきたためです。というか、某プロダクションレンダラ(スキャンライン + レイトレ)はわずか 32 MB のメモリで数十ギガ単位のシーンのレンダリング処理をしているそうですから(テクスチャデータ含む)、それくらい lucille でもできなきゃね、というのもあります。

やはり大規模シーンの取り扱いでは、空間データ構造をいかにうまく構築するかが一番の問題です。

とりあえず今までは、空間データ構造として、 kd-tree と uniform grid をためしていました。まず、kd-tree では構築が O(N log^2 N) or O(N^2) 時間という問題があります。havran の cut plane を求める方法を実装してみましたが、普通に実装すると、これは、xyz で全部 cut plane を求め、最小コストの cut plane を選択するので、ポリゴン数が多くなるとアホみたいに時間がかかってしまうことが分かりました。

これに対しては、まだ十分には読んでいませんが、

Ingo Wald
On building fast kd-trees for ray tracing, and on doing that in O(N log N)
Technical Report, SCI Institute, University of Utah, No UUSCI-2006-009
http://www.sci.utah.edu/~wald/Publications/

がこの構築時間の問題の解決の糸口になりそうです。が、やはり数百、数千万ポリゴンのシーン全体に対してひとつの kd-tree を適用するというのは現実的ではなさそうです。

変わって、uniform grid は、構築が O(N) と高速であるという、 kd-tree に対してのアドバンテージがあります。
(27 M 三角形の stanford lucy でも、128x128x128 のボクセルで構築が数十秒ほど)
しかし、物体が密集したシーンだと、ひとつのボクセルに多くのポリゴンが登録されてしまい、交差判定処理がネックになってしまうという問題があります。
(たとえば、sponza atrium シーンを 128x128x128 のボクセルで構築すると、最大で一ボクセルに 300 ポリゴン程度がはいってしまいます)
交差判定すべきポリゴンが百を超えるくらいから、トラバースよりも交差判定処理がネックになってくると思います。

よって、ひとつの空間データ構造のアルゴリズムをシーン全体に適用するよりは、いくつかのアルゴリズムを組みあわせたほうがよさそうです。
いまのところ私が考えているのは、基本はまず一様グリッドでシーンを切ります。そして、ボクセル内のポリゴン数が 60 以上のボクセルに対しては、ボクセル内のポリゴンに対して kd-tree を構築することです。60 は、 kd-tree による平均的に交差テストをすることになるポリゴン数 log2(60) とでちょうど 10 倍の差くらいになるところから決めてみましたが、もう少し少なくともよいかもしれません。

こうすれば、少ないポリゴン数に対して kd-tree を構築すればよいので、kd-tree からみれば構築時間が少なくて済みますし、uniform grid からみれば数百のポリゴンに対してマジメに交差判定をしなくてよくなります。もちろんこのように組み合わせる方法は昔から提案されてきたので、別新しい手法でもなんでもないのですが、kd-tree と一様グリッドを実装した経験からすると、この組み合わせが今のところ最良であろうという結論に落ち着きました。あとは実際に実装してみてテスト、テスト、テストですね。

省メモリ化

さらに、単純にグリッドを voxel[N][N][N] という感じでメモリ上に確保すると、カラのボクセルでもメモリが割り当てられてしまいますし、ボクセルトラバース時にメモリアクセスのキャッシュミスが生じやすくなります。そのため、グリッドはハッシュ化して、メモリ使用量の圧縮とメモリアクセスのキャッシュパフォーマンスの向上を図りたいと考えています。

ハッシュが衝突した場合はリストにするのですが、これもクエリ時に線形に探索するのは無駄なので、ここにも kd-tree を構築して探索を効率化できます。これは (x, y, z) の point location と同じなので、photon map 本のソースコードがそのまま使えます。

あとさらに、ボクセルに対して、ボクセルがカラかどうかのビットマスクを用意しておき、ハッシュを探索する前にまずはビットマスクを見てテストするということもオプションとしてできそうです。

Advertisements