Binning-based SAH BVH construction

by syoyo

I’ve implemented binning-based SAH BVH construction [1].

sponza_bvh.png

http://lucille.svn.sourceforge.net/viewvc/lucille/
trunk/src/render/bvh.c?view=markup

binning-based SAH construction is known in realtime raytracing field as it computes sufficiently optimal SAH in blazingly fast construction time.

Despite to my previous manner(implementing an algorithm in indivisual program), I’ve implemented binning-based SAH BVH in lucille core, since I believe this method is promising and practical.

How much is it fast?

Construction with binning-based SAH is amazingly fast.

SAH BVH for sponza scene(76k triangles) was constructed just 0.49 sec on my Core2 2.16 GHz!

And more, current my implementation is straightforward and unoptimized, thus there’s a enough room for optimization by using MUDA and tuning memory access(x10 speed up could be possible).
But I am much satisfied with the speed from current implementation
(less than 1 sec is sufficient for offline rendering)

Visual diagnositics for spatial data structure

I’ve also added visual diagnostics for BVH traversal to debug & tuning traversal.

Visualizing hit distance.

sponza_depth.png

Visualizing # of node traversals(blue = few, green = middle, red = much).
sponza_travs.png

Visualizing # of triangle isects
sponza_isects.png

[Ja]

やっとこさ、lucille の次期バージョンがモノになりつつあります.
その第一弾として、ビンニングベースの SAH BVH を lucille 本体のコアに実装しました.

いままではアルゴリズムのテスト実装は独立プログラムとしてコーディングしてばっかりだったのですが、
ビンニングベースの SAH BVH はかなり実務的かつ効率的なので、
lucille の空間データ構造アルゴリズムとして採用することにしたためです.

sponza シーン(7 万三角形)で、leaf には 4 個の三角形以下になるまで再分割して構築して、Core2 2 GHz で 0.49 sec.
特に SIMD 化もメモリ最適化もしていない素直なコードでも、
これだけ高速に構築できて、個人的には非常に満足していませす.

ついでに、テストビューアとビジュアルダイアグノスティックス(ビジュアル診断)も実装して、
レイのトラバース回数などを視覚化して確認できるようにしました.
パフォーマンスのチューニングなどに使っていく予定です.

とはいえ、ちょっと視覚化してみて傾向を見て分かったことですが、
小手先のトラバース処理のチューニングではもうダメで、
効率化にはアルゴリズムそのものを変えないとダメですね.

トラバースの視覚化診断結果から、なんか新しくてとても効率のよいレイトレの
空間データ構造が、いくつか首のあたりくらいまで思いつくのですが、
なかなか最後までひらめききらないですね。もう少し時間がかかりそうです。

[1] Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes
Maxim Shevtsov, Alexei Soupikov and Alexander Kapustin.
EUROGRAPHICS 2007
http://graphics.cs.uni-sb.de/Courses/ss07/sem/index.html

Advertisements