ototoi https://blog.hatena.ne.jp/ototoi/ 明日ではないから https://ototoi.hatenadiary.org/ CG programming 大分前から各所で話題になっていたBIHですが遅ればせながら、実装して試しました。 BIHって用は分割位置が二つあるkdtreeなんですが、ようは内部の三角形を２つの空間に分けるとき適当にどっちかに入れるか決めてしまってその境目は適当にやってしまおうという、適当の極みみたいなデータ構造*1です。 いつものアルマジロで結果は以下のような感じ（CoreDuo T2300 1GB Memory） 時間（ms） オクトリー KDツリー BIH 構築 4760 3882 1780 レンダリング 7132 7868 8365 まあ何せ構築が速い。だって分割軸の左か右かなんて三角形の重点みればいいんだもん。速… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fototoi.hatenadiary.org%2Fentry%2F20060805%2Fp1" title="BIH実装 - 明日ではないから" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2006-08-05 00:00:00 rich https://ototoi.hatenadiary.org/entry/20060805/p1 1.0 100%