Patent ID: 8188997
Filing Date: 2012-05-29
Classification: G06T

Abstract:
1. A method executable in a digital processor, the digital processor being operable to generate pixel values for pixels in an image using a ray-tracing methodology and to generate an electrical output in response to the generated pixel values, the method comprising: accelerating ray tracing in the digital processor by configuring, in the digital processor, hierarchical acceleration data structures with high arity to enable processing of rays using streaming SIMD (Single Instruction, Multiple Data) instructions with reduced memory requirements, and wherein processing of rays comprises at least one of: processing pluralities of rays, processing single rays, and processing single, incoherent rays, and further comprising: executing tree construction by flattening binary trees, wherein flattening binary trees comprises collapsing a classical binary tree, and wherein collapsing a classical binary tree comprises keeping each k-th level of a given tree, and discarding intermediate levels; utilizing streaming SIMD instructions in tree traversal and construction of hierarchical acceleration data structures, including bounding volume hierarchies; utilizing per-ray ordered, sorted tree traversal; applying streaming SIMD instruction processing to leaf intersection, using a cache storing recently used triangles in SIMD-compatible form; and executing a numerically robust triangle subdivision technique that subdivides triangles only when required, and wherein a degree of subdivision is automatically selected; wherein the triangle subdivision technique comprises an edge volume technique that evaluates the tightness of the bounding box of each triangle edge and subdivides the triangle until a selected threshold value is met; wherein the edge volume technique further comprises: (a) determining, for each edge of a given triangle, its axis-aligned bounding box; and (b) comparing, for a given triangle, the volume of the largest of the three boxes to a volume threshold, and if the volume is larger than the threshold, subdividing the triangle in the middle of the corresponding edge, and repeating the procedure for the two new triangles until the process is complete; and wherein the edge volume threshold is determined as a fraction of the volume of the scene bounding box, thus controlling the number of triangles generated by subdivision.