四元树

四元树是一种用于计算光线跟踪阴影的数据结构。        

四元树从灯光的角度表现场景。四元树的根节点列出了在视图中可见的所有对象。如果可视对象过多，节点会生成另外四个节点，均代表视图的四分之一，并分别列出所在部分的对象。该过程以自适应方式持续进行，直到每个节点都只有少量对象，或者四元树达到其深度限制（可以为每个灯光分别设置）。        

每条阴影投射光线都需要测试与对象的相交性，这只在四元树的一个叶节点上进行。这有助于加速光线追踪过程。通常来说，增加四元树的最大深度可以在占用一定内存的情况下加速光线追踪。        

四元树的最大大小是 2 到四元树最大深度次幂的平方。深度为 7 时，四元树最多拥有 128 x 128 个叶节点；深度为 10 时，四元树最多拥有 1028 x 1028 个叶节点，以此类推。（另一方面，因为每个后续节点都含有更少的对象，所以节点记录的数目随着树的加深而减少。）