Bounding Volume Hierarchy (BVH)

与えられたそれぞれのAABBを2つのグループに分け、それぞれ囲うAABBができる。

https://scrapbox.io/files/685aa9e45afa0aec5927ee92.png

衝突判定がAとCにしか当たらなかった場合、Bの衝突判定はしなくてよくなる。

一つ一つのAABBに衝突判定計算していると、計算量は

m*n (m: rayの数, n:オブジェクト数)だが、BVHだとmlog(n)