Efficient and flexible data organization for acceleration data structure nodes

• US 7,719,532 B2
• Filed: 02/09/2007
• Issued: 05/18/2010
• Est. Priority Date: 02/09/2007
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Shearer, Robert Allen, Schardt, Paul Emery
• Primary Examiner(s): NGUYEN, PHU K
• Application Number:
  US11/673,041
• Publication Number:
  US 20080192050A1
• Time in Patent Office: 1,194 Days
• Field of Search: 345/420, 345/427, 707/1, 707/4, 707/5, 707/6, 707/9, 707/100, 707/102, 707/103.R, 707/104.1, 701/207, 701/208, 702/5, 340/990, 382/176, 382/180, 382/305
• US Class Current: 345/420
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 2210/61 Scene description

Abstract

Embodiments of the invention provide an efficient and flexible organization of data for an acceleration data structure (e.g., spatial index). In contrast to storing primitive information within a spatial index, embodiments of the invention may store pointers in the spatial index which point to or link to primitive-defining information in buffers. Storing pointers to primitive-defining information may reduce the size of the spatial index. Additionally, embodiments of the invention enable vertex and triangle sharing. Vertex and triangle sharing may reduce the amount of storage space required to define the primitives within the three-dimensional scene. Furthermore, the data organization provided by the embodiments of the invention allows for easy manipulation of the spatial index and primitive data.

Claims

1. A method for generating a two-dimensional image of a three-dimensional scene containing at least one dynamic object, comprising:

generating a spatial index having a world root node, internal nodes corresponding to bounding volumes with partitioned sub-volumes of the scene, and leaf nodes corresponding to unpartitioned sub-volumes of the scene containing primitive objects;

generating, by operation of a computer processor, a leaf node link from at least one of the leaf nodes to a list of pointers to data objects corresponding to one or more primitive objects that represent the at least one dynamic object; and

in response to a change in at least one of shape and location of the at least one dynamic object, updating one or more of the data objects to reflect the change without updating the leaf node link.

2. The method of claim 1, further comprising:

in response to the at least one dynamic object moving out of an unpartitioned sub-volume corresponding to a leaf node, updating the leaf node link in that leaf node.

3. The method of claim 1, wherein the primitive objects contain a plurality of vertexes, and wherein a data object comprises one or more pointers to vertex data objects corresponding to primitive vertexes.

4. The method of claim 3, wherein two primitive objects share a vertex and data objects corresponding to the two primitive objects contain pointers which point to a single vertex data object.

5. The method of claim 3, wherein the vertex data object comprises the coordinates of the vertex within the three-dimensional scene.

6. The method of claim 1 wherein a data object comprises a pointer to a properties data object corresponding to at least one primitive property.

7. The method of claim 6, wherein two primitive objects have the same properties and data objects corresponding to the two primitive objects point to a single properties data object.

8. The method of claim 6, wherein the properties data object comprises information which identifies at least one:

of a color of the primitive, a texture of the primitive, a coefficient of reflection for the primitive, a coefficient of refraction for the primitive, a coefficient of transparency for the primitive, a coefficient of diffuse reflection for the primitive, a coefficient of specular reflection for the primitive, a coefficient of ambient reflection for the primitive, and a phong exponent for the primitive.

9. The method of claim 1, wherein the primitive objects are triangles and the data objects are triangle data objects, and wherein the triangle data objects comprise one or more pointers to vertex data objects and at least one pointer to a triangle property data object in a triangle property buffer.

10. A method for generating and traversing a spatial index, comprising:

generating a spatial index having a world root node representing a volume which encompasses a three-dimensional scene, internal nodes corresponding to bounding volumes with partitioned sub-volumes, and leaf nodes corresponding to unpartitioned sub-volumes containing primitive objects;

generating links from the internal nodes to nodes corresponding to sub-volumes created by partitioning planes which partition the internal nodes;

generating, by operation of a computer processor, a leaf node link from at least one of the leaf nodes to a list of pointers to data objects corresponding to one or more primitive objects contained within the sub-volume corresponding to the at least one leaf node;

issuing a ray into the three-dimensional scene;

traversing the ray through the spatial index to the at least one leaf node; and

generating a pixel value based on primitive object information retrieved using the leaf node link.

11. The method of claim 10, further comprising:

in order to determine if the ray intersects a primitive, taking the leaf node link from the at least one leaf node to the list of pointers to data objects corresponding to the one or more primitive objects contained within the sub-volume corresponding to the at least one leaf node.

12. The method of claim 11, wherein the primitive objects contain a plurality of vertexes, and wherein a data object comprises one or more pointers to vertex data objects corresponding to primitive vertexes and at least one pointer to a properties data object corresponding to at least one primitive property.

13. An image processing system comprising:

a physics engine to move one or more dynamic objects in an animated scene; and

logic configured to generate a spatial index having a world root node, internal nodes corresponding to bounding volumes with partitioned sub-volumes, and leaf nodes corresponding to unpartitioned sub-volumes containing primitive objects;

generate a leaf node link from at least one of the leaf nodes to a list of pointers to data objects corresponding to one or more primitive objects that represent a dynamic object of the one or more dynamic objects; and

in response to a change in at least one of shape and location of the one or more dynamic objects, update one or more of the data objects without updating the leaf node link.

14. The image processing system of claim 13, wherein the logic is further configured to update the leaf node link from a leaf node in response to the dynamic object moving out of an unpartitioned sub-volume corresponding to the leaf node.

15. The image processing system of claim 13, wherein the primitive objects contain a plurality of vertexes, and wherein a data object comprises one or more pointers to vertex data objects corresponding to primitive vertexes.

16. The image processing system of claim 15, wherein two primitive objects share a vertex and data objects corresponding to the two primitive objects contain pointers which point to a single vertex data object.

17. The image processing system of claim 15, wherein the vertex data object comprises the coordinates of the vertex within the three-dimensional scene.

18. The image processing system of claim 17, wherein two primitive objects have the same properties and data objects corresponding to the two primitive objects point to a single properties data object.

19. The image processing system of claim 15, wherein the properties data object comprises information which identifies at least one of a color of the primitive, a texture of the primitive, a coefficient of reflection for the primitive, a coefficient of refraction for the primitive, a coefficient of transparency for the primitive, a coefficient of diffuse reflection for the primitive, a coefficient of specular reflection for the primitive, a coefficient of ambient reflection for the primitive, and a phong exponent for the primitive.

20. The image processing system of claim 13, wherein a data object comprises a pointer to a properties data object corresponding to at least one primitive property.