RAY TRACING ALGORITHM WITH RECORDING OF THE INDEX TRAVERSAL HISTORY

摘要

Embodiments of the invention provide methods and apparatus for recording the traversal history of a ray through a spatial index structure and utilizing the recorded traversal history. An image processing system may initially determine which nodes a ray intersects as it traverses through a spatial index. Results of the node intersection determinations may be recorded as the ray traverses the spatial index, and the recorded determinations may be associated with the ray. Furthermore, the image processing system may decide upon a traversal path based upon some probability of striking primitives corresponding to the nodes which make up the spatial index. This traversal path may also be recorded and associated with the ray. If the image processing system needs to re-traverse the spatial index at a later time, the recorded traversal history may be used to eliminate the need to recalculate ray-node intersections, and eliminate incorrect traversal path determinations.