Quadtree

A quadtree is a data structure used to calculate ray-traced shadows.

The quadtree represents the scene from the point of view of the light. The root node of the quadtree lists all objects that are visible in that view. If too many objects are visible, the node generates four other nodes, each representing a quarter of the view, each with a list of objects in that portion. This process continues adaptively, until each node has only a small number of objects, or the quadtree's depth limit (which can be set for each light) is reached.

Each shadow-casting light ray needs to test intersection with the objects in only one of the leaf nodes of the quadtree. This helps speed up the ray-tracing process. In general, increasing the maximum quadtree depth can speed up ray-tracing at a cost of memory.

The maximum size of a quadtree is the square of two to the power of the maximum quadtree depth. At a depth of 7, the largest quadtree has 128 x 128 leaf nodes; at a depth of 10, the largest quadtree has a size of 1028 x 1028 leaf nodes, and so on. (On the other hand, because each successive node contains fewer objects, the size of a node's record decreases the deeper it is in the tree.)

Note: An omni light can generate up to ten quadtrees, so omni lights that cast ray-traced shadows use more memory at render time than spotlights do.