Editing Ray tracing (graphics) (section)

==Bounding volumes==
Enclosing groups of objects in sets of [[Bounding volume hierarchy|bounding volume hierarchies]] (BVH) decreases the amount of computations required for ray tracing. A cast ray is first tested for an intersection with the [[bounding volume]], and then if there is an intersection, the volume is recursively divided until the ray hits the object. The best type of bounding volume will be determined by the shape of the underlying object or objects. For example, if the objects are long and thin, then a sphere will enclose mainly empty space compared to a box. Boxes are also easier to generate hierarchical bounding volumes.

Note that using a hierarchical system like this (assuming it is done carefully) changes the intersection computational time from a linear dependence on the number of objects to something between linear and a logarithmic dependence. This is because, for a perfect case, each intersection test would divide the possibilities by two, and result in a binary tree type structure. Spatial subdivision methods, discussed below, try to achieve this.  Furthermore,  this acceleration structure makes the ray-tracing computation [[Output-sensitive algorithm|output-sensitive]]. I.e. the complexity of the ray intersection calculations depends on the number of objects that actually intersect the rays and not (only) on the number of objects in the scene.

Kay & Kajiya give a list of desired properties for hierarchical bounding volumes:

* Subtrees should contain objects that are near each other and the further down the tree the closer should be the objects.
* The volume of each node should be minimal.
* The sum of the volumes of all bounding volumes should be minimal.
* Greater attention should be placed on the nodes near the root since pruning a branch near the root will remove more potential objects than one farther down the tree.
* The time spent constructing the hierarchy should be much less than the time saved by using it.