Ray tracing image processing system

• US 8,139,060 B2
• Filed: 11/28/2006
• Issued: 03/20/2012
• Est. Priority Date: 11/28/2006
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Brown, Jeffrey Douglas, Hoover, Russell Dean, Mejdrich, Eric Oliver
• Primary Examiner(s): Wu, Xiao M.
• Assistant Examiner(s): Welch, David T
• Application Number:
  US11/563,978
• Publication Number:
  US 20080122841A1
• Time in Patent Office: 1,939 Days
• Field of Search: 345/426, 345/427
• US Class Current: 345/426
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

According to embodiments of the invention, a normally recursive ray tracing algorithm may be partitioned to form an iterative ray tracing algorithm. The resulting portions of the iterative ray tracing algorithm may be executed by a plurality of processing elements. Furthermore, according to embodiments of the invention, a network of inboxes may be used to transfer information which defines original rays and secondary rays (information unlikely to be reused for subsequently issued rays and subsequently rendered frames) between processing elements, and a shared memory cache may store information relating to a three dimensional scene (information likely to be reused for subsequently issued rays and subsequently rendered frames). Using a plurality of processing elements to perform ray tracing and storing information in the shared memory cache which is likely to be reused for subsequent rays and subsequent frames, the performance of a ray tracing image processing system may be improved.

Claims

1. A computer implemented method of performing ray tracing, wherein steps of the computer implemented method are performed by a microprocessor, the computer implemented method comprising:

issuing a ray into a three-dimensional scene;

with a first processing element;

tracing, iteratively, the ray through a spatial index having nodes representing bounding volumes within the three-dimensional scene by taking branches to nodes defining bounding volumes intersected by the ray until a first leaf node is reached, wherein the spatial index partitions the three-dimentional scene into smaller volumes through a use of splitting planes which are parallel to a selected axis; and

sending information defining the ray and the first leaf node to a second processing element, wherein the information defining the ray is sent to the second processing element irrespective of a processing of any previously processed leaf node, and the first processing element begins tracing a subsequent ray upon sending the information;

with the second processing element;

performing ray-primitive intersection tests to determine if the ray intersects a primitive contained within a bounding volume defined by the first leaf node;

generating at least one secondary ray, the secondary ray includes a shadow ray; and

sending the secondary ray to the first processing element,

wherein the first processing element and the second processing element are configured to be controlled by the microprocessor.

2. The computer implemented method of claim 1, further comprising:

if the ray intersects a primitive contained within the bounding volume, with the second processing element, determining a color of the primitive and updating a color value of a pixel through which the ray passed according to the color of the primitive.

3. The computer implemented method of claim 2, further comprising, with the first processing element, tracing the secondary ray through the spatial index by taking branches to nodes defining bounding volumes intersected by the secondary ray until a second leaf node is reached;

and

sending information defining the secondary ray and the second leaf node to the second processing element; and

with the second processing element, performing ray-primitive intersection tests to determine if the secondary ray intersects a primitive contained within a bounding volume defined by the second leaf node.

4. The computer implemented method of claim 3, further comprising if the secondary ray intersects a second primitive contained within the bounding volume defined by the second leaf node, with the second processing element, determining a color of the second primitive and updating the color value of the pixel through which the original ray passed according to the color of the second primitive.

5. The computer implemented method of claim 4, wherein updating the color of the pixel through which the original ray passes comprises writing color information to a frame buffer location corresponding to the pixel.

6. The computer implemented method of claim 1, wherein the spatial index is stored within a memory cache shared between the first processing element and the second processing element.

7. A non-transitory computer readable storage medium containing a program which, when executed, performs an operation, comprising:

issuing a ray into a three-dimensional scene;

with a first processing element;

tracing, iteratively, the ray through a spatial index having nodes representing bounding volumes within the three-dimensional scene by taking branches to nodes defining bounding volumes intersected by the ray until a first leaf node is reached, wherein the spatial index partitions the three-dimentional scene into smaller volumes through a use of splitting planes which are parallel to a selected axis; and

sending information defining the ray and the first leaf node to a second processing element, wherein the information defining the ray is sent to the second processing element irrespective of a processing of any previously processed leaf node and the first processing element begins tracing a subsequent ray upon sending the information defining the ray to the second processing element; and

with the second processing element;

performing ray-primitive intersection tests to determine if the ray intersects a primitive contained within a bounding volume defined by the first leaf node;

generating at least one secondary ray, the secondary ray includes a shadow ray; and

sending the secondary ray to the first processing element,

wherein the first processing element and the second processing element are configured controlled by the microprocessor.

8. The non-transitory computer readable storage medium of claim 7, wherein the operation further comprises:

if the ray intersects a primitive contained within the bounding volume, with the second processing element, determining a color of the primitive and updating a color of a pixel through which the ray passed according to the color of the primitive.

9. The non-transitory computer readable storage medium of claim 8, wherein the operation further comprises:

with the first processing element, tracing the secondary ray through the spatial index by taking branches to nodes defining bounding volumes intersected by the secondary ray until a second leaf node is reached; and

sending information defining the secondary ray and the second leaf node to the second processing element; and

with the second processing element, performing ray-primitive intersection tests to determine if the secondary ray intersects a primitive contained within a bounding volume defined by the second leaf node.

10. The non-transitory computer readable storage medium of claim 9, wherein the operation further comprises:

if the secondary ray intersects a second primitive contained within the bounding volume defined by the second leaf node, with the second processing element, determining a color of the second primitive and updating the color of the pixel through which the original ray passed according to the color of the second primitive.

11. A system, comprising:

a first processing element;

a second processing element;

a spatial index having nodes defining bounding volumes of a three-dimensional scene;

a communication network coupled to the first processing element and the second processing element;

wherein the first processing element is configured to iteratively traverse a ray through the spatial index by taking branches to nodes defining bounding volumes intersected by the ray until a leaf node is reached, and send the ray to the second processing element via the communication network, wherein the spatial index partitions the three-dimentional scene into smaller volumes through a use of splitting planes which are parallel to a selected axis, wherein the ray is sent to the second processing element irrespective of a processing of any previously processed leaf node and the first processing element begins tracing a subsequent ray upon sending the ray to the second processing element; and

wherein the second processing element is configured to determine if the ray intersects a primitive contained within a bounding volume defined by the leaf node, wherein the second processing element is further configured to generate a secondary ray, the secondary ray includes a shadow ray, the second processing element is further configured to send the secondary ray to the first processing element,

wherein the first processing element and the second processing element are configured to be controlled by the microprocessor.

12. The system of claim 11, wherein the second processing element is further configured to:

if the ray intersects a primitive contained within the bounding volume defined by the leaf node, determine a color of the primitive; and

update a color value of a pixel through which the ray passed.

13. The system of claim 12, wherein the second processing element is Further configured to:

generate at least one secondary ray;

send the secondary ray to the first processing element via the communications network.

14. The system of claim 13, wherein the first processing element is further configured to:

traverse the secondary ray through the spatial index by taking branches to nodes intersected by the secondary ray until a second leaf node is reached; and

send the secondary ray to the second processing element via the communications network.

15. The system of claim 14, wherein the second processing element is further configured to determine if the secondary ray intersects a second primitive contained within the second leaf node;

and

if so, update the color value of the pixel through which the ray passed.

16. The system of claim 11, wherein the first processing element and the second processing element are on the same chip.

17. The system of claim 16, further comprising a shared memory cache coupled to the first processing element and the second processing element.

18. The system of claim 17, wherein the spatial index is stored in the shared memory cache.