tak0kadaの何でもノート

発声練習、生存確認用。

医学関連は 医学ノート

空間分割アルゴリズム

三角形に分割された閉曲面(球面)と複数の半直線があったとき、それぞれが交差するかどうかの判定をしたい。レイトレーシングで使用されるようなアルゴリズムとしてはBVH、Quadtree、Octreeなどが見つかった。

BVH (Bounding Volume Hierarchies)は、領域を木構造に分割して、AABBという直方体との交差判定を行うことで、オブジェクトとの交差の判定回数を減らす方法である。この方法は、疎にオブジェクトが散らばっている場合、木構造が容易に定まり、光線の大半はオブジェクトと交差しないため特に有効だと思われる。

今回の状況を考えると、三角形は球面を全て埋め尽くしているため半直線は必ずいずれかの三角形と交差すること、頂点の座標は極座標で与えれば2次元であることが特徴的である。四分木を用いて三角形を含む「長方形」を事前に処理しておくのが良さそうである。

(とはいえ実装は出来れば回避したく、たぶん使わないのでこのページは開きすぎたタブの供養にあたる)