Early termination in bottom-up acceleration data structure refit

Patent metadata

Field	Value
Publication number	US-11900523-B2
Application number	US-202117505387-A
Country	US
Kind code	B2
Filing date	Oct 19, 2021
Priority date	Dec 28, 2018
Publication date	Feb 13, 2024
Grant date	Feb 13, 2024

Abstract

Apparatus and method for bottom-up BVH refit. For example, one embodiment of an apparatus comprises: a hierarchical acceleration data structure generator to construct an acceleration data structure comprising a plurality of hierarchically arranged nodes; traversal hardware logic to traverse one or more rays through the acceleration data structure; intersection hardware logic to determine intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure; a node unit comprising circuitry and/or logic to perform refit operations on nodes of the hierarchical acceleration data structure, the refit operations to adjust spatial dimensions of one or more of the nodes; and an early termination evaluator to determine whether to proceed with refit operations or to terminate refit operations for a current node based on refit data associated with one or more child nodes of the current node.

First claim

What is claimed is:

1. An apparatus comprising:
a hierarchical acceleration data structure generator to construct an acceleration data structure comprising a plurality of hierarchically arranged nodes;
traversal hardware logic to traverse one or more rays through the hierarchical acceleration data structure;
intersection hardware logic to determine intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure; and
a node refit unit comprising circuitry and/or logic to perform refit operations on nodes of the hierarchical acceleration data structure to adjust spatial dimensions of one or more of the nodes,
wherein the node refit unit is to receive refit data associated with refitting one or more child nodes of a current node and to skip refitting the current node responsive to that the refit data indicates that space occupancy of the one or more child nodes has shrunk but the one or more child nodes are still bounded by the current node.

2. The apparatus of claim 1 , wherein the refit data comprises results of refit decisions, adjustments to node coordinates, and/or adjustments to node sizes.

3. The apparatus of claim 2 , wherein the node refit unit is to refit the current node when the refit data indicates that the one or more child nodes are no longer bounded by the current node.

4. The apparatus of claim 3 , wherein the refit data further comprises one or more threshold values and the node refit unit is to refit the current node when one or more threshold values are reached.

5. The apparatus of claim 4 , wherein one of the threshold values comprises a ratio of volume occupancy of the one or more child nodes over the volume of the current node.

6. The apparatus of claim 4 , wherein one of the threshold values comprises degraded performance over a threshold period of time or number of processing cycles.

7. The apparatus of claim 4 , wherein one of the threshold values comprises a number of times the one or more child nodes have been refitted.

8. The apparatus of claim 1 , wherein the hierarchical acceleration data structure comprises a bounding volume hierarchy (BVH).

9. The apparatus of claim 1 , wherein refit operations include adjusting dimensions of the current node based on changes to dimensions or locations of the one or more child nodes.

10. A method comprising:
constructing a hierarchical acceleration data structure comprising a plurality of hierarchically arranged nodes;
traversing one or more rays through the hierarchical acceleration data structure;
determining intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure;
performing refit operations on nodes of the hierarchical acceleration data structure to adjust spatial dimensions of one or more of the nodes;
receiving refit data associated with refitting one or more child nodes of a current node; and
skipping performing refit operations on the current node responsive to that the refit data indicates that space occupancy of the one or more child nodes has shrunk but the one or more child nodes are still bounded by the current node.

11. The method of claim 10 , wherein the refit data comprises results of refit decisions, adjustments to node coordinates, and/or adjustments to node sizes.

12. The method of claim 11 , further comprising:
performing refit operations on the current node when the refit data indicates that the one or more child nodes are no longer bounded by the current node.

13. The method of claim 12 , wherein the refit data further comprises one or more threshold values and method further comprises:
performing refit operations on the current node when one or more threshold values are reached.

14. The method of claim 13 , wherein one of the threshold values comprises a ratio of volume occupancy of the one or more child nodes over the volume of the current node.

15. The method of claim 13 , wherein one of the threshold values comprises degraded performance over a threshold period of time or number of processing cycles.

16. The method of claim 13 , wherein one of the threshold values comprises a number of times the one or more child nodes have been refitted.

17. The method of claim 10 , wherein the hierarchical acceleration data structure comprises a bounding volume hierarchy (BVH).

18. The method of claim 10 , further comprising:
adjusting dimensions of the current node based on changes to dimensions or locations of the one or more child nodes.

19. A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform operations of:
constructing a hierarchical acceleration data structure comprising a plurality of hierarchically arranged nodes;
traversing one or more rays through the hierarchical acceleration data structure;
determining intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure;
performing refit operations on nodes of the hierarchical acceleration data structure to adjust spatial dimensions of one or more of the nodes;
receiving refit data associated with refitting one or more child nodes of a current node; and
skipping performing refit operations on the current node responsive to that the refit data indicates that space occupancy of the one or more child nodes has shrunk but the one or more child nodes are still bounded by the current node.

20. The non-transitory machine-readable medium of claim 19 , wherein the refit data comprises results of refit decisions, adjustments to node coordinates, and/or adjustments to node sizes.

21. The non-transitory machine-readable medium of claim 20 , wherein the operations further comprise:
performing refit operations on the current node when the refit data indicates that the one or more child nodes are no longer bounded by the current node.

22. The non-transitory machine-readable medium of claim 20 , wherein the refit data further comprises one or more threshold values and operations further comprise:
performing refit operations on the current node when one or more threshold values are reached.

23. The non-transitory machine-readable medium of claim 22 , wherein one of the threshold values comprises a ratio of volume occupancy of the one or more child nodes over the volume of the current node.

24. The non-transitory machine-readable medium of claim 22 , wherein one of the threshold values comprises degraded performance over a threshold period of time or number of processing cycles.

25. The non-transitory machine-readable medium of claim 22 , wherein one of the threshold values comprises a number of times the one or more child nodes have been refitted.

Assignees

• Intel Corp

Inventors

• Xiao Kai
• Apodaca Michael
• Brownlee Carson
• Raoux Thomas
• Barczak Joshua
• Liktor Gabor

Classifications

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T1/20

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G06T2200/04

  involving 3D image data · CPC title

• G06T15/205 Primary

  Image-based rendering · CPC title