Out-of-core ray tracing with memory-efficient page generation

1. A method, comprising:

constructing by a processor a hierarchical spatial index organizing primitives that comprise a scene using a limited memory block;

segmenting by the processor the scene into plural chunks of the primitives, where each chunk data fits in the limited memory block;

for each of the plural chunks constructing by the processor a hierarchical spatial index organizing the primitives that comprise the current chunk wherein each node of the spatial index of the chunk is stopped subdividing into more nodes and represent a group once it has less or equal than M primitives wherein M is an integer number;

assembling all the groups of up to M primitives generated for all of the plural chunks of the scene and constructing a top-level spatial index organizing the groups wherein the number of groups is less than the number of scene primitives; and

using a surface area heuristic in the process of creating the plurality of groups comprising up to M primitives by constructing the hierarchical spatial index for each chunk, wherein the surface area heuristic is modified with a coefficient based on modulo operation that favors those splits of one node into several nodes that would result in less number of groups of up to M primitives for the same number of input primitives, wherein the surface area heuristic is used to decrease the spatial volume bounding the primitives of the spatial hierarchy node while the coefficient based on modulo operation is used to increase the number of primitives per limited group on average for the plurality of all groups of primitives.

2. A method, comprising:

constructing by a graphics processing unit (GPU) a spatial index organizing primitives that comprise a scene using a limited memory block available in the GPU wherein the spatial index comprises a plurality of pages each comprising a subset of the scene primitives; and

performing a ray-primitive intersection search for one or more of rays in parallel by the GPU for a scene containing more data than the GPU can allocate in its own physical memory; and

organizing a ray-primitive intersection search process using several iterations of at least the following operations executed in each iteration:

compute ray-primitive intersections for one or more rays in parallel by the GPU using portions of scene data available in GPU memory and request for portions of scene data that are not currently in GPU memory but are necessary for ray-primitive intersection search; and

deliver requested portions of scene data to GPU memory excluding those portions of scene data that have already been loaded to GPU memory within one of the previous iterations of ray-primitive intersection search process; and

wherein the ray-primitive intersection search is based on the spatial index that organizes the scene data and uses the plurality of pages to determine the portions of scene data that can be delivered to the GPU memory on request.