My initial BKD tree implementation

by syoyo

bkd_test.png

BKD ツリーを実装してみました。まだ構築だけできたというレベルで、実際にレイをトラバースしてうまく動くかはこれからです。
Here is my initial BKD tree implementation.

 

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

http://lucille.atso-net.jp/svn/angelina/spatial/bkd/bkd.exe
http://lucille.atso-net.jp/svn/angelina/spatial/bkd/cornellbox.obj
(demo binary + scene file. put them in same directory to run the demo)

オリジナルでは SAH(surface area heuristic) を使っているようですが、
とりあえずは簡潔のために object median で分割するようにしました。
アルゴリズムはこんな感じです。
I use object median for simplicity. the following is the algorithm.

1. バウンディングボックスが 2D なら、(3) に進むが、そのときテストする軸は他の 2 軸(幅のある軸)のみとする。
2. 軸並行(x, y, z)なポリゴンがあれば、その位置で分割を試みる(3 軸すべてをテスト)
2.1. 軸並行なポリゴンの位置と分割面が同一であるので、軸並行なポリゴンをどちらに分けるかが問題となる。今回はノードのバウンディングボックス(bmin, bmax)とポリゴンの位置を比較し、距離が近いほうにポリゴンを振り分けました。
2.2 どちらかの子ノードに振り分けられるポリゴンの数がゼロなら、分割失敗。三軸テストしてすべてダメなら、次のテストに進む
3. object median で分割を試みる(三軸テスト)
4. すべてでダメなら、あきらめて葉ノードをつくって終了(1 葉ノード 1 三角形にはならない)
5. 子ノードを 1 から繰り返す。

こんな感じです。

あと、実装していく過程で、いくつかうまくいかない(分割が難しい)ケースを見つけました。

split_bbox.png
この左のような二つの三角形。三角形の bounding box(中央や右) を分割面の候補にしたり、spatial median で分割しようとすると分割できない。
For such two triangles(left), it couldn’t split with spatial median using triangle’s bounding box.

split_objmedian.png
ポリゴンの重心を使えば、object median を分割面とし、ポリゴンの重心で左右どちらかに振り分けることが可能。
Using object median, it could be splittable.

ただ、object median だけだと、これまたうまくいかないケースがあり、

same_center.png
このように重心が重なっていると、分割面と物体の重心が重なってしまうので object median だけでは分割できません。このときは spatial median のときのように、
In such a case, object median == center of triangle. it can’t splittable.

split_aabb.png

分割面をポリゴンの bounding box + ポリゴンの重心で振り分け、もしくは
分割面はポリゴンの重心 + ポリゴンの bounding box で振り分け、とすることができるでしょう。
Use object median for split candidate and triangle’s bounding box to classify.

まずはポリゴンの bounding box を分割面の候補としてテスト、だめなら object median を分割面の候補にしてテスト、とするとよさそうです。

また、軸並行なポリゴンは最初にそのようなポリゴンが見つかったときに、そこで分割するようにしていますが、
複数の軸並行なポリゴンがある場合、なるべく断面積が大きくものや、ノードの bounding box の端に近い
ものを優先的に選ぶなどするとより高品質なツリーが構築できると思います。

さて、BKD ツリーは構築が高速であるというのがとりえだったような気がしますが、
なんか結構普通の kd-tree のようにめんどうな手続きになってしまいました。
オンラインの場合はある程度シーンを作るときに変な形状を取り除くでしょうから上記のような
特殊なケースを考えなくともよいかもしれませんが、
オフラインレンダラでの利用となると任意のポリゴンシーンでも安定して構築できなければならなくなりますので、
いろいろ特殊なケースに対応できるようにしないといけません。

それでも、kd-tree に比べて、bkd tree は数値的にロバストであったり、構築が高速になるなら、
利用してみる意義はあると思います。

Advertisements