Bounding volume hierarchy とは

境界ボリューム階層(BVH)は、一連の幾何学的オブジェクト上のツリー構造です。すべての幾何学的オブジェクトは、ツリーのリーフノードを形成する境界ボリュームに包まれています。これらのノードは小さなセットとしてグループ化され、より大きな境界ボリューム内に囲まれます。これらはまた、グループ化され、再帰的な方法で他のより大きな境界ボリューム内に囲まれ、最終的にはツリーの最上部に単一の境界ボリュームを有するツリー構造となる。境界ボリューム階層は、衝突検出や光線追跡など、ジオメトリオブジェクトのセットに対する効率的な操作を効率的にサポートするために使用されます。
オブジェクトのジオメトリ自体をテストする前に、バウンディングボリューム内のオブジェクトをラップし、その上で衝突テストを実行すると、テストが簡素化され、パフォーマンスが大幅に向上する可能性がありますが、バウンディングボリューム間のペアワイズテストと同じ数のテストが実行されます。バウンディングボリュームをバウンディングボリューム階層に配置することによって、時間複雑度(実行されるテストの数)をオブジェクト数の対数に減らすことができる。このような階層を配置すると、衝突テスト中に、子ボリュームは、親ボリュームが交差していない場合に検査する必要がありません。