International Business Machines Corporation

David Keith Fowler

Robert Allen Shearer

Paul E Schardt

Eric Oliver Mejdrich

Zachary Adam Garbow

Eric Michael Radzikowski

A circuit arrangement, program product and method are provided for resetting a dynamically grown Accelerated Data Structure (ADS) used in image processing in which an ADS is initialized by reusing the root node of a prior ADS and resetting at least one node in the prior ADS to break a link between the reset node and a linked-to node in the prior ADS. By doing so, the memory allocated to the prior ADS may be reused for the new ADS, without having to clear or wipe out all of the allocated memory. In addition, in some instances, given the similarity of many image frames, often some or all of the node structure of a prior ADS may be reused for a new ADS, requiring only the contents of nodes to be cleared, instead of having to clear out all of the nodes in the prior ADS. As a result, the processing overhead associated with initializing a new ADS can be significantly reduced.

Resetting of dynamically grown accelerated data structure

A circuit arrangement, program product and circuit arrangement utilize the known view orientation for an image frame to be rendered to reposition an Accelerated Data Structure (ADS) used during rendering to optimize the generation and/or use of the ADS, e.g., by transforming a scene from which an image frame is rendered to orient the scene relative to the view orientation prior to generating the ADS. A scene may be transformed, for example, to orient the view orientation within a single octant of the scene, with additional processing resources assigned to that octant to ensure sufficient processing resources are devoted to processing the primitives within the view orientation.

Accelerated data structure positioning based upon view orientation

Embodiments of the invention provide techniques for commercial transactions for the sale of images carried out over short-range wireless transmissions. In one embodiment, the transaction may be initiated by a vendor (e.g., a professional photographer), who transmits a wireless signal including an offer for sale of an image. A customer wishing to purchase the image responds by sending a wireless signal including an acceptance of the offer. In another embodiment, the transaction may be initiated by a customer, who transmits a wireless signal including a request for an image to be fulfilled by a vendor. A vendor agreeing to supply the image responds by sending a wireless signal including an acceptance of the request. By offering the images to customers who are in close proximity to the image capture, the vendor may increase the likelihood that the images will be purchased.

Fee-based distribution of media based on device proximity

Embodiments of the invention provide techniques for controlling access to digital images based physical and temporal proximity to the image capture event. In one embodiment, an imaging device capturing a digital image broadcasts an invitation to wireless devices in the surrounding area. The wireless devices respond with an acceptance, including the email address (or some other network address) of the device owner. The digital image is made available at a network location with restricted access. Access to the image is controlled with an access list based on the acceptances received by the imaging device.

Controlling access to digital images based on device proximity

A circuit arrangement, program product and method utilize the known view orientation for an image frame to be rendered to optimize the generation and/or use of an Accelerated Data Structure (ADS) used in physical rendering-based image processing. In particular, it has been found that while geometry primitives that are not within a view orientation generally cannot be culled from a scene when a physical rendering technique such as ray tracing is performed, those primitives nonetheless have a smaller impact on the resulting image frame, and as a result, less processing resources can be applied to such primitives, leaving greater processing resources available for processing those primitives that are located within the view orientation, and thereby improving overall rendering performance.

Accelerated data structure optimization based upon view orientation

A circuit arrangement, program product and circuit arrangement utilize a textured bounding volume to reduce the overhead associated with generating and using an Accelerated Data Structure (ADS) in connection with physical rendering. In particular, a subset of the primitives in a scene may be mapped to surfaces of a bounding volume to generate textures on such surfaces that can be used during physical rendering. By doing so, the primitives that are mapped to the bounding volume surfaces may be omitted from the ADS to reduce the processing overhead associated with both generating the ADS and using the ADS during physical rendering, and furthermore, in many instances the size of the ADS may be reduced, thus reducing the memory footprint of the ADS, and often improving cache hit rates and reducing memory bandwidth.

Physical rendering with textured bounding volume primitive mapping

Embodiments of the invention provide methods and apparatus to reduce the number of intersection tests required to determine if an object moving within a three-dimensional scene collides with any other objects. According to one embodiment of the invention, a physics engine may cast a velocity box into the scene and traverse the velocity box through an integrated acceleration data structure. By traversing the velocity box through an integrated acceleration data structure, a physics engine may determine which objects are in the same area of the scene and are likely intersect the velocity box. The physics engine may use the objects when performing intersection tests to reduce the number of intersection tests which are necessary to determine which objects intersect the velocity box. A reduction in the number of intersection tests may reduce the amount of time necessary to determine if a moving object collides with any other objects.

Box casting using an integrated acceleration data structure

Embodiments of the invention provide methods and apparatus to defer the optimization an acceleration data structure (e.g., a kd-tree) in response to movements of objects within a three-dimensional scene. According to one embodiment of the invention, an image processing system may determine portions of an acceleration data structure affected by the movement of an object within a three-dimensional scene. The image processing system may store the affected portion of the ADS in an optimization queue. If the image processing system does not have sufficient processing bandwidth available to optimize the ADS, the image processing system may defer the ADS optimization until sufficient processing bandwidth becomes available. Once sufficient processing bandwidth becomes available, the image processing system may optimize the ADS according to the information stored in the optimization queue.

Deferred acceleration data structure optimization for improved performance

Embodiments of the invention create links or branches from a static spatial index which partitions a three-dimensional scene based on the position of static objects to a dynamic object spatial index which partitions a three-dimensional scene based on the position of dynamic objects in a three-dimensional scene. By branching from the static spatial index to the dynamic object spatial index, the image processing system may create a single combined spatial index or a combined acceleration data structure. The combined spatial index may contain information which partitions the three-dimensional scene with respect to both static objects and dynamic objects within the three-dimensional scene. When performing ray tracing, the image processing system may only need to traverse rays issued into the three-dimensional scene through the combined spatial index to determine if the ray intersects either static objects or dynamic objects within the three-dimensional scene.

Combined spatial index for static and dynamic objects within a three-dimensional scene

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.

Growing community of inventors

Hastings, MN, United States of America

David Keith Fowler