Patent ID: 8400447

Claim:
A computer-implemented method, comprising: performing, by a computer: partitioning a scene comprising a plurality of objects into a plurality of sub-regions, wherein the plurality of sub-regions are divided by a plurality of planes having orientations selected from a discrete set of orientations, wherein the discrete set of orientations comprises at least one spatial orientation that is not parallel to an x axis, a y axis, or a z axis and is at a nonzero angle with respect to the x axis, the y axis, or the z axis; storing the partitioned scene in a binary tree comprising a plurality of nodes, wherein each node of the plurality of nodes corresponds to one of the plurality of sub-regions, wherein the binary tree is stored in a memory of a computer system; and solving a ray tracing query for a ray, wherein solving the ray tracing query comprises traversing the binary tree to identify a first object of the plurality of objects intersected by the ray.