クアッドツリーは、レイトレース シャドウを計算するデータ構造です。
クアッドツリーは、ライトの視点からシーンを表します。クアッドツリーのルート ノードには、そのビューで表示されるオブジェクトがすべて含まれています。表示するオブジェクトが多すぎる場合、全ノードを 4 分割したノードが新しく生成され、それぞれに各ノードのオブジェクトが表示されます。各ノードのオブジェクト数が少なくなるまで、またはそれぞれのツリーで設定した(各ライトに対する設定が可能)クアッドツリーの深さになるまで、この操作を繰り返します。
オブジェクトへの影付け用の光線は、クアッドツリーのいずれかの格子ノードで、オブジェクトとの交差部のテストを行う必要があります。このようにするとレイトレースのプロセスを高速化することができます。一般的に、クアッドツリーの最大深度を大きくするとレイトレースの速度は上がりますが、メモリの消費が大きくなります。
クアッドツリーの最大サイズは、2 を最大深度でべき乗し、さらに 2 乗したものです。クアッドツリーの最大深度 7 であれば最大サイズは 128 x 128 のリーフ ノードであり、深度 10 であればサイズは 1028 x 1028 となります。一方、連続ノードでは、含めることのできるオブジェクト数が少なくなるため、ノードの記録サイズはツリーが深くなるほど減少します。