Dynamically configuring and selecting multiple ray tracing intersection methods

• US 7,773,087 B2
• Filed: 04/19/2007
• Issued: 08/10/2010
• Est. Priority Date: 04/19/2007
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Fowler, David Keith, Shearer, Robert Allen
• Primary Examiner(s): NGUYEN, PHU K
• Application Number:
  US11/737,156
• Publication Number:
  US 20080259075A1
• Time in Patent Office: 1,209 Days
• Field of Search: 345/426, 345/427, 345/419, 345/423
• US Class Current: 345/426
• CPC Class Codes: G06T 15/06 Ray-tracing

Abstract

Embodiments of the invention provide methods and apparatus to determine a coordinate system to use when traversing rays through a portion of a spatial index corresponding to a dynamic object which has a unique object coordinate system. An image processing system may take into consideration a number of factors including, but not limited to, a distance form a viewpoint to the dynamic object, a distance from the origin of the world coordinate system to the object coordinate system, a rate of traversal of the dynamic object, and a number of primitives which make up the object. These factors alone or together may indicate whether it is more efficient to perform ray intersection tests in an object coordinate system or in a world coordinate system. Embodiments of the invention may update a spatial index according to the selected coordinate system.

Claims

1. A method of performing ray tracing image processing using a computer system for a three-dimensional scene, comprising:

providing a spatial index having a first portion and a second portion and having at least one branch from a node in the first portion to a node in the second portion, wherein nodes in the first portion correspond to bounding volumes which partition the three -dimensional scene with respect to a first coordinate system, and wherein nodes in the second portion correspond to bounding volumes which partition the three-dimensional scene with respect to a second coordinate system;

issuing a ray into the three-dimensional scene;

tracing the ray through the three-dimensional scene by taking branches to nodes corresponding to bounding volumes intersected by the ray until the at least one branch from a node in the first portion to a node in the second portion is reached; and

selecting a coordinate system to use when tracing the ray through the portion of the spatial index which partitions the three-dimensional scene with respect to the second coordinate system.

2. The method of claim 1, wherein the second coordinate system partitions a portion of the three-dimensional scene containing a dynamic object. pg,59

3. The method of claim 1, wherein selecting a coordinate system comprises checking a bit stored in a node of the spatial index.

4. The method of claim 1, further comprising:

selecting the first coordinate system; and

tracing the ray through the portion of the spatial index which partitions the three -dimensional scene with respect to the second coordinate system by performing ray-bounding volume intersection tests with coordinates in the first coordinate system.

5. The method of claim 1, further comprising:

selecting the second coordinate system;

converting the trajectory of the ray into a trajectory expressed in the second coordinate system; and

tracing the ray through the portion of the spatial index which partitions the three-dimensional scene with respect to the second coordinate system by performing ray-bounding volume intersection tests with coordinates in the second coordinate system.