BIH実装
大分前から各所で話題になっていたBIHですが遅ればせながら、実装して試しました。
BIHって用は分割位置が二つあるkdtreeなんですが、ようは内部の三角形を２つの空間に分けるとき適当にどっちかに入れるか決めてしまってその境目は適当にやってしまおうという、適当の極みみたいなデータ構造*1です。
いつものアルマジロで結果は以下のような感じ（CoreDuo T2300 1GB Memory）
| 時間（ms） | オクトリー | KDツリー | BIH |
| 構築 | 4760 | 3882 | 1780 |
| レンダリング | 7132 | 7868 | 8365 |
まあ何せ構築が速い。だって分割軸の左か右かなんて三角形の重点みればいいんだもん。速いわけだ。
しかももうひとつ特徴としてひとつの三角形が複数の部分空間にまたがることがないため、メールボックスなんか、使う必要がない（使っても意味がない）*2です。
今回syoyoさんのところでソースを拝見しながら実装しました。この場を借りてお礼いたします。ありがとうございます。
氏のサイトで指摘されている大きな三角形があった場合ですが、これについては軸を選ぶとき、その基準となるバウンドを子に下るごとに三角形のリストから得るのではなく、親のバウンドから分割軸で分割したものをつかえば、あまり問題にならないはずです。あくまで「空間」を分割すればよいのです。
情報など、なにかご意見いただけたら幸いです。
以下にハンパなソースをおいときます。
http://www.wikiroom.com/ototoi/index.php?plugin=attach&refer=BIH&openfile=BIH.zip
