Raytracing is one of the main rendering methods used to generate 2D images from 3D scenes. When used with other techniques, like texture mapping and photon mapping, it can produce photorealistic images. While raytracing is relatively easy to implement, its main drawback is the high computational cost of finding intersections between a ray in 3D and objects in the scene [1, p. 203]. There are many techniques for tackling the complexity of raytracing; one of the most used is to split the scene using a kd-tree and minimize the number of intersections using a heuristic cost estimate called the surface area heuristic (SAH) [2].

SAH calculates the cost of intersections between rays and space; according to this paper, this causes an overestimation of the probabilities of intersections. To alleviate this problem, the authors propose a new heuristic cost estimate, the grid-based ray distribution heuristic (GRDH), which instead evaluates the probability of ray-primitive intersection. They also introduce a novel raytracing pipeline with an on-demand kd-tree construction algorithm. The on-demand GRDH algorithm was implemented in a multi-core platform and presents significant speedups, both in construction time and traversal time, compared with a traditional SAH-based algorithm.