オブジェクトレベルでの空間構造
レイトレーサにおいて、扱う対象が三角形の集合（メッシュ）だけならいいのだが、それ以外にも球や曲面を扱うとすると、シーン全体でひとつの空間分割構造に押しこめてしまうのは無理が出てくる。
ここでは、メッシュや球・曲面などのひとかたまりをオブジェクトと呼んで、これらの集合をトラバースするための空間構造について考える。
空間構造を考える上で、オブジェクトの集合では三角形のそれとは異なる。
- オブジェクトは三角形に比べ、空間的に疎であり、オブジェクト同士のスケール比が大きいことがある
- オブジェクトの正確な形状を要求できない
- オブジェクトは一回のテストが高負荷である
- オブジェクトは三角形に比べ、数はそれほど多くない
１．三角形の集合・メッシュでは三角形同士はつながっていて、空間として局所的だ。
いっぽうオブジェクトの集合ではオブジェクト同士は非常に密集していることも考えられるが、ある程度の距離離れているのが普通だ。さらに、非常に離れていることも考えられる。
またそれぞれのオブジェクトの比が大きいこともしばしばあるだろう。たとえば巨大なビルのオブジェクトとそこに立つ人物のオブジェクトのような場合だ。
以上より空間構造の分割軸はその分割位置がより自由が利くほうが好ましいだろう。たとえばUグリッドよりKDツリーのほうがこの点において優れているはずだ。
２．オブジェクトに正確な形状を要求し空間構造を構築することは難しい。たとえば曲面など同様にして考えるとわかるだろう。
そのため、空間構造を構築するための材料としてそのオブジェクトを包む球やAABB、OOBBなどを用いることになる。
だからオブジェクトの形状に左右されるアルゴリズムは採用できないことが多い。
３．ひとつのオブジェクトは一回のテストが非常に高負荷になることになることも考えなくてはならない。たとえばひとつのオブジェクトが数万ポリゴンのメッシュとなることも考えられる。このためトラバース時に複数回テストすることは必ず避けなければならない。
これには
- 空間構造中の複数のセルにひとつのオブジェクトをまたがせない
- メールボックスをつかって一度テストしたら２度とテストさせない
が考えられる。
複数のセルにまたがせないようにするには、
- ３分木
- BIH (B-KDTREE)
のような構造を遣うことになるだろう。
ここでいう３分木はKDツリーを拡張したもので、分割軸をまたがるオブジェクトは左・右セルとは別の中央セルに登録するようにしたもの。
メールボックスを用いる場合でトラバースのマルチスレッドも考慮に入れる場合
メールボックス実装は、TLSを使うか、スレッドIDをキーとしたマップとするなどが必要だろう。
４．オブジェクトの数はそれほど多くないと考えられる。たとえば１０万ポリゴンのメッシュを何十万個も表示するシーンなど普通はありえないだろう。
そのため、構築にはある程度時間がかけられる。
今のとこ僕が考えているオブジェクトレベルの空間構造としては以下がある。
今のところ僕の自作レンダラでは
KDツリー＋メールボックス、Uグリッド＋メールボックス、BIH、３分木
を実装し試してみた。
結果を今のところ経験論的なもので申し訳ないが以下に書く。
構築においてはよほどの数のオブジェクトを扱うのでなければ、わずかであり、
メッシュ構築時間と比べれば些細な時間なので気にしなくていいと思う。
トラバースにおいては、シーンによって異なるのでなんともいいがたいが、
メールボックスを使うものでは、KDツリーのほうがわずかに速いことが多いようだ。とくにオブジェクト同士の距離が大きいとUグリッドは効率が良くない。
BIHはメールボックスを使うものに比べ大分遅い。特にオブジェクト同士が密集してる場合は良くない。
３分木はメールボックスを使うものと同様のスピードが出せる。ただやはり密集してるとノードが分割できないので遅くなる。
以上からいまのところ、KDツリー＋メールボックスが一番オブジェクトレベルでの空間構造に適していると判断している。
第１候補：KDツリー＋メールボックス
第２候補：３分木
メールボックスはマルチスレッドではどうなるか実際試してみなければならない（まだ試してない・・・）だろう。
またいくつか実装を行ってないものもあるので、試してみたいと考えている。
