言語はC++、ベクトルや行列の演算には OpenGL Mathematics (GLM) という mathematics library を使ってとりあえず実装をはじめた。
mathematics library って訳すと数学ライブラリ？ 数値計算ライブラリだとなんかちょっと違う種類になるよね。

このGLM、GLSLに近い書き方で使えるように設計されてるので、OpenGLのシェーダーを書いた事があって「シェーダーってベクトルや行列の記述が楽でいいわぁ」って思ったことのある方にはめっちゃオススメです。

ベクトルや行列のライブラリはどこかの個人が間に合わせで作ったようなものまで含めるとそれこそ数えきれないほどあるけど、このGLMは今まで使った中では3Dプログラミング用としていちばん使いやすいというか、使ってて「ちょっとキビしいなぁ」思うような欠点が今のところまだない。

ベクトル、行列演算ライブラリとして立派にひとり立ちしてるような有名所だと汎用的過ぎて逆に使いづらかったり（普通の3Dプログラミングでベクトルの次元数を無制限にできても嬉しくないし）、3D関係のライブラリや物理演算エンジンに付属してるようなライブラリは逆に特化してて微妙な制限があったりするんだけど、このGLMは一般的な３Dプログラミング向けとしてはかなりバランスがいい。
CUDAやSSEにも対応してるし、swizzlingにも対応してる。
swizzlingってのは、例えば色（R,G,B,A）を表す vec4 color という変数があった場合、 gl_FragColor = color.rbga; なんて書き方で緑成分と青成分を簡単に入れ替えたりすること。
入れ替えだけじゃなくて同じ成分を繰り返したりもできる。
（GLSLではrgbaもxyzwも表記のしかたが違うだけで同じものを指してるから当然xyzwもswizzlingできる。）
さらにMITライセンスだしマジオススメ。

さてGLMの宣伝はこれくらいにして進捗を。

フォトンとポリゴンの当たり判定を高速化するために5次元空間分割によるRay Classificationを実装しようと思ってたけど、実はそんなに効率よくないんじゃないかと思ったり（明確な根拠なし）、実行結果を画として見れない段階から難しいことすると詰みそうな気がしたので、オブジェクトメディアン分割なBVHを実装した。
1次元配列にノードのデータを置いたりとか、そういう最適化はなにもしてないオーソドックスな実装。
配列化したり、コスト関数を使って分割したりとかは後々やればいいかなという考え。

実装したBVHの動作確認のために、視点から画面の真ん中に向かってレイを飛ばしてぶつかったポリゴンを緑色にするプログラム（OpenGLによるリアルタイムレンダリング）を書いた。
マウスやWASDでグリグリ動かせるんだけど、やはりQuick Timeの画面収録が激重なので静止画だけ公開。
こういう場合、時分割を1/30sとかの固定にし毎フレーム静止画を出力して、後から一連の画像を動画化するのが王道だと思うけど、下手にインタラクティブな作りにしてしまったせいでそういう手法ともマッチしなくなってる状態。
そのうち操作を記録して再生出来る機能を付けて動画を作れるようにするつもり。





ロウソクにポリゴン使い過ぎw

AABBとレイの当たり判定は http://gamedev.stackexchange.com/a/18459 を参考に、ポリゴンとレイの当たり判定は Tomas Moller の方法を参考にした。

しかしBVHを実装して思ったんだけど、BVHって一様なグリッドによる空間分割法より楽だと思った。
実装したことがあるワケじゃないけど、確かにビルド処理の実装はグリッドの方が楽だと思うけど、トラバース処理の実装は地味に面倒なんじゃないかな。
まぁブレゼンハムのアルゴリズムを3次元空間でやるようなイメージだと思うけど、ポリゴンとレイの交点を単に求めるだけじゃなくて交点がグリッドの中にあるかどうかまでチェックしないと正確じゃないらしいから、コードはそれなりの長さになるんじゃないかな。
一方BVHは再帰的に辿って交差判定してレイの視点から一番近い交点をもつポリゴンを見つければいいだけ。
実際書いたトラバース本体のコードは10行ぐらいだし。

BVHは一番簡単なものだと実装難度が低いし、そこから段階的に高度化していくことも可能だから、とりあえずの選択としてはオススメだと思う。
BVHフォーマットっていう有名なモーションキャプチャデータファイルフォーマットがあって、さらにどちらも3D関連なものだからWeb検索がしづらいという問題はあるけどねw

この後の予定としては、とりあえずフォトンをばら蒔いてみて着弾点を可視化してみる感じかな。