Patent ID: 9679351
Date: 2017-06-13
CPC Classifications: G06F,G06T

Claim:
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.