Efficient and flexible data organization for acceleration data structure nodes

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.

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.