Patent ID: 8248416
Filing Date: 2012-08-21
Classification: G06T

Abstract:
1. A method executable in a digital processor operable to simulate light transport in a scene by ray tracing, wherein the digital processor is operable to maintain an object list representing a list of objects associated with a boundary of the scene, the method comprising: executing a ray tracing method that traces r rays through n objects using a memory footprint of only on the order of (n+r) by (1) partitioning the list of objects associated with a boundary of the scene in a recursive manner to generate partitions and (2) culling away the partitions of objects from rays, without using an explicitly stored auxiliary acceleration data structure, and wherein (a) permutations of rays and objects are storable as index arrays, (b) a ray permutation is utilized, following the recursive partitioning and culling of partitions of objects, to enumerate ray-object intersections by spatial proximity in a manner adapted for Markov chain simulation, which can comprise executing shading and scattering computations or employing a path tracing technique, and (c) an order of recursion is determinable by a majority of ray directions of rays associated with the scene.