Patent ID: 8780112

Claim:
A computer-enabled method of shading a scene, the scene comprising a shading location on a surface element of an object in the scene, the method performed by a computing system having an in-core memory and coupled to one or more out-of-core storage devices, the method comprising: generating a point cloud representation of the scene, wherein the point cloud representation of the scene is generated by dividing the surface of the object in the scene into one or more micropolygons and storing information for each micropolygon into a point of one or more points in the point cloud; generating an octree data structure based on the point cloud representation of the scene, wherein the octree structure comprises leaf nodes and parent nodes, and wherein the octree structure stores the one or more points in the point cloud representation of the scene as leaf nodes, and wherein the octree data structure stores cluster data in parent nodes, and wherein generating the octree data structure comprises: computing Morton codes for each point in the point cloud representation of the scene, sorting the points based on a Morton order based on the computed Morton codes, recursively subdividing the points to find at most a threshold number of points, wherein the points are to be stored in nodes, and writing the nodes to the one or more out-of-core storage devices; and shading the shading location based on the nodes written to the one or more out-of-core storage devices.