三角形に分割された閉曲面(球面)と複数の半直線があったとき、それぞれが交差するかどうかの判定をしたい。レイトレーシングで使用されるようなアルゴリズムとしてはBVH、Quadtree、Octreeなどが見つかった。
BVH (Bounding Volume Hierarchies)は、領域を木構造に分割して、AABBという直方体との交差判定を行うことで、オブジェクトとの交差の判定回数を減らす方法である。この方法は、疎にオブジェクトが散らばっている場合、木構造が容易に定まり、光線の大半はオブジェクトと交差しないため特に有効だと思われる。
今回の状況を考えると、三角形は球面を全て埋め尽くしているため半直線は必ずいずれかの三角形と交差すること、頂点の座標は極座標で与えれば2次元であることが特徴的である。四分木を用いて三角形を含む「長方形」を事前に処理しておくのが良さそうである。
(とはいえ実装は出来れば回避したく、たぶん使わないのでこのページは開きすぎたタブの供養にあたる)
- 領域分割について色々のまとめ:
- 2次元の線分交差判定: 計算幾何の基礎と領域探索 - RAMBO
- AABB
- 二分木
- インターフェースが参考になりそう
- HaskellでB-treeを実装 - でかいチーズをベーグルする
- バイナリ空間分割
- Quadtree
- 2次元空間を4つずつに分割する
- その8 4分木空間分割を最適化する!
- Octree
- 3次元空間を8つずつに分割する
- その15 8分木空間分割を最適化する!