kdツリーできましたが．．．

ひとまずkdツリーを使ってレンダリングできるようになったのですが、レイを使ってツリーをトラバースする処理のオーバーヘッドが大きすぎてかえって実行速度が遅くなってしまいました。作業PC上で計測した実時間の比較では2倍以上遅いです。
プロファイラで調べたところ、どうもレイとAABBの交差判定回数が多すぎるよう。現在のプログラムでは、ツリーの構築は単純にAABBの中点を選択して再帰的に分割して行っているので、ツリーのトラバースに必要な交差判定回数は、ノード数をNとすると最低でもlog₂Nになるはず。だとすると、ポリゴン数が一定数以上にならないと、交差判定回数が決まってlog₂N回多い分、単純に線形検索した方が速いのではないでしょうか*1。そう仮定すると今回の結果は納得がいきます*2。もっとポリゴン数が多いシーンをレンダリングして比較しないと。
でも、今はシーン情報をプログラムの中にハードコーディングしてるので複雑なシーンをレンダリングすることができないんですね。ついこの間まで、普通にパストレーシングを実行させるのに精一杯だったのでそれ以外の事は後回しになっていたのでした。なので、次は複雑なシーンをレンダリングできるように標準的なフォーマットで記述されたシーンデータをインポートできるようにしたいと思います。ただし、3D関連のファイルフォーマットは巷にたくさんあるようで、どれに対応するか悩むところですが。
あと並行して、kdツリーを高速にトラバースする手法がないか調べてみます。とりあえずは、lucilleの開発者の方が紹介している*3以下の論文を読んでみようと思います。
　「Heuristic Ray Shooting Algorithms」- http://www.cgg.cvut.cz/members/havran/phdthesis.html

*1:もしかすると、レンダリングするシーンによって空間データ構造を切り替えるっていう手法はありかもしれません。

*2:単に私の実装がへぼいのかもしれませんが。

*3:http://lucille.atso-net.jp/wiki/index.php?%B6%F5%B4%D6%A5%C7%A1%BC%A5%BF%B9%BD%C2%A4