In its most basic form, the intersect test operation takes as input some object in an environment and some ray traversing that environment, and outputs whether the ray intersects the object, and if so, where. Furthermore, since the dominant method of representing an “object” in computer graphics is as a mesh of many flat polygons, the intersect test operation condenses to ray-triangle intersection testing.
While attractive in its simplicity, condensing intersect testing in ray tracing to iterated ray-triangle intersection is problematic vis-à-vis implementation performance. Let us say that we have an object composed of 10,000 polygons (in modern terms, this is a very modest size). And let us say that our ray tracing system is programmed to fire 1,000 rays. In this case, we have to perform 10,000 × 1,000 = 10,000,000 intersections. In general, the asymptotic complexity of a ray tracing system that fires R rays into an environment whose objects comprise n polygons is O(n) = Rn. Now, when one considers that systems that fire tens-of-thousands rays into environments of millions of polygons are common, then O(n) = Rn complexity becomes a performance handicap.
As a result, various acceleration techniques have been devised to improve ray tracing performance. Almost all such schemes work by transforming the asymptotic complexity of ray-object intersect testing from O(n) = Rn to O(n) = R log n for most objects. They work by progressively sub-dividing (or “partitioning”) the virtual 3D environment and the objects in it. Examples of such partitioning schemes include binary space partitioning trees and bounding volume hierarchies.
To see how acceleration works, consider the figure below. Here, several inbound rays are about to be intersect-tested against a 3D object (in this case, a low-complexity version of the classic Stanford Bunny). The triangular faces that comprise the surface mesh of the bunny are clearly visible. In a naïve ray tracer, each inbound ray would be intersect-tested against each polygon in the bunny, yielding a per-ray time complexity linear in the number of polygons.
