Method for reducing network bandwidth by delaying shadow ray generation

• US 7,782,318 B2
• Filed: 11/22/2006
• Issued: 08/24/2010
• Est. Priority Date: 11/22/2006
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Shearer, Robert Allen
• Primary Examiner(s): Nguyen, Kimbinh T
• Application Number:
  US11/562,629
• Publication Number:
  US 20100060637A1
• Time in Patent Office: 1,371 Days
• Field of Search: 345/419, 345/421, 345/426, 345/427, 345/619, 345/502, 345/420, 348/E5.086, 359/630, 382/294, 378/98.12
• US Class Current: 345/426
• CPC Class Codes: G06T 15/06 Ray-tracing

Abstract

The present invention provides methods and apparatus in a ray tracing image processing system to reduce the amount of information passed between processing elements. According to embodiments of the invention, in response to a ray-primitive intersection, a first processing element in the image processing system may generate a portion of secondary rays and a second processing element may generate a second portion of secondary rays. The first processing element may generate reflected and refracted rays and the second processing element may generate shadow rays. The first processing element may send a ray-primitive intersection point to the second processing element so that the second processing element may generate the shadow rays. By only sending the intersection point to the second processing element, in contrast to sending a plurality of shadow rays, the amount of information communicated between the two processing elements may be reduced.

Claims

1. A method of performing ray tracing, comprising:

configuring one or more processors to perform an operation, comprising;

issuing a ray into a three-dimensional scene;

with a first processor;

tracing 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; and

, after a leaf node is reached, sending information defining the ray and the first leaf node to a second processor;

with the second processor;

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 a first set of secondary rays;

sending, information defining the first set of secondary rays to the first processor; and

sending a ray-primitive intersection point to the first processor; and

with the first processor, generating a second set of secondary rays based on at least the ray-primitive intersection point.

2. The method of claim 1, wherein the first set of secondary rays comprises at least one of a reflected or is refracted ray.

3. The method of claim 1, wherein the second set of secondary rays comprises shadow rays.

4. The method of claim 3, thither comprising:

with the first processor, generating shadow rays using the ray-primitive intersection point and locations of light sources within the three dimensional scene.

5. The method of claim 4, wherein the locations of light sources are stored within a memory cache shared between the first processor and the second processor.

6. The method of claim 1, further comprising:

with the first processor, traversing the first and second set of secondary rays through the spatial index by taking branches to nodes defining bounding volumes intersected by the ray until leaf nodes are reached.

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

issuing a ray into a three-dimensional scene;

initiating on a first processor;

tracing 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;

after the leaf node is reached, sending information defining the ray and the first leaf node to a second processor;

receiving information defining a first set of secondary rays and information defining a ray-primitive intersection point from the second processor; and

generating a second set of secondary rays based on at least the information defining the ray-primitive intersection point.

8. The computer readable storage medium of claim 7, wherein the first set of secondary rays comprises at least one of a reflected or a refracted ray.

9. The computer readable storage medium of claim 7, wherein the second set of secondary rays comprises shadow rays.

10. The computer readable storage medium of claim 9, wherein the operations further comprise:

with the first processor, generating shadow rays using the ray-primitive intersection point and locations of light sources within the three dimensional scene.

11. The computer readable storage medium of claim 10, wherein the locations of light sources are stored within a memory cache shared between the first processor and the second processor.

12. The computer readable storage medium of claim 7, wherein the operations further comprise:

with the first processor, traversing the first and second set of secondary rays through the spatial index by taking brandies to nodes defining bounding volumes intersected by the ray until leaf nodes are reached.

13. A system, comprising:

a first processor;

a second processor;

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

a communication network coupled to the first processor and the second processor;

wherein the first processor is configured to 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 information defining the ray and the leaf node to the second processor via the communication network;

wherein the second processor is configured to determine if the ray intersects a primitive contained within a bounding volume defined by the leaf node;

generate a first set of secondary rays;

send information defining the first set of secondary rays to the first processor; and

send information defining a ray-primitive intersection point to the first processor; and

wherein the first processor is further configured to generate a second set of secondary rays based on at least the ray-primitive intersection point.

14. The system of claim 13, wherein the first set of secondary rays comprises at least one of a reflected or a refracted ray.

15. The system of claim 13, wherein the second set of secondary rays comprises shadow rays.

16. The system of claim 15, wherein the first processor is further configured to generate shadow rays using the ray-primitive intersection point and locations of light sources within the three dimensional scene.

17. The system of claim 16, further comprising a memory cache accessible by the first processor, wherein the locations of light sources are stored within the memory cache.

18. The system of claim 15, wherein the first processor is further configured to:

traverse the first and second set of secondary rays through the spatial index by taking branches to nodes intersected by the secondary rays until leaf nodes are reached; and

send the secondary rays to the second processor via the communications network.

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

20. The system of claim 13, wherein the first processor and the second processor are on the same chip.