| Sonstiges: |
- Nachgewiesen in: USPTO Patent Grants
- Sprachen: English
- Patent Number: 11928,770
- Publication Date: March 12, 2024
- Appl. No: 17/562271
- Application Filed: December 27, 2021
- Assignees: Advanced Micro Devices, Inc. (Santa Clara, CA, US)
- Claim: 1. A method for traversing nodes in a bounding volume hierarchy (BVH) tree by an intersection engine, comprising: receiving a traversal instruction including a tracing-mode, ray data for a ray, and an identifier of a node to be traversed, wherein the tracing-mode comprises a closest hit mode and a first hit mode and the ray data includes a ray origin; in response to a condition where the node to be traversed is an internal node, determining, according to the tracing-mode, an order in which children nodes of the node are to be next traversed based on a respective distance to each respective children node among the children nodes; and outputting identifiers of the children nodes in the determined order for the traversal instruction, wherein the respective distance is calculated by averaging a first distance between the ray origin and a first location at which the ray enters a volume associated with a respective children node and a second distance between the ray origin and a second location at which the ray exits the volume for the traversal instruction.
- Claim: 2. The method of claim 1 , further comprising: in response to a condition where the node to be traversed is an external node, traversing leaves of the node, including searching primitives that are contained within a volume associated with the node for a ray-intersecting primitive.
- Claim: 3. The method of claim 1 , further comprising: receiving another traversal instruction, including the tracing-mode, the ray data, and an identifier of a node to be next traversed, the identifier is a first outputted identifier in the determined order.
- Claim: 4. The method of claim 1 , wherein the ray data further comprises at least one of a length, or an orientation of a ray.
- Claim: 5. The method of claim 1 , wherein the determined order orders the children nodes according to the respective distance in an ascending order.
- Claim: 6. The method of claim 1 , further comprising: receiving another traversal instruction including a tracing-mode, ray data for a ray, and an identifier of another node to be traversed, wherein the tracing-mode of the another traversal instruction comprises a first hit mode; in response to a condition where the another node to be traversed is the internal node, determining, according to the tracing-mode, an order in which children nodes of the another node are to be next traversed based on a second respective distance to each respective children node among the children nodes; and outputting identifiers of the children nodes in a determined order for the another traversal instruction, wherein the second respective distance is computed based on a crossing distance that is an absolute difference between a first location at which the ray enters a volume associated with a respective children node for the another traversal instruction and a second location at which the ray exits the volume for the another traversal instruction and the determined order for the another traversal instruction orders the children nodes according to the respective distance in a descending order.
- Claim: 7. The method of claim 1 , wherein when the first distance is negative, a value of zero is used as the first distance in the averaging.
- Claim: 8. A system for traversing nodes in a bounding volume hierarchy (BVH) tree, comprising: at least one processor; and memory storing instructions that, when executed by the at least one processor, cause the system to: receive a traversal instruction including a tracing-mode, ray data for a ray, and an identifier of a node to be traversed, wherein the tracing-mode comprises a closest hit mode and a first hit mode and the ray data includes a ray origin; in response to a condition where the node to be traversed is an internal node, determine, according to the tracing-mode, an order in which children nodes of the node are to be next traversed based on a respective distance to each respective children node among the children nodes; and output identifiers of the children nodes in the determined order for the traversal instruction, wherein the respective distance is calculated by averaging a first distance between the ray origin and a first location at which the ray enters a volume associated with a respective children node for the traversal instruction and a second distance between the ray origin and a second location at which the ray exits the volume for the traversal instruction.
- Claim: 9. The system of claim 8 , wherein the instructions further cause the system to: in response to a condition where the node to be traversed is an external node, traverse leaves of the node, including searching primitives that are contained within a volume associated with the node for a ray-intersecting primitive.
- Claim: 10. The system of claim 8 , wherein the instructions further cause the system to: receive another traversal instruction, including the tracing-mode, the ray data, and an identifier of a node to be next traversed, wherein the identifier is a first outputted identifier in the determined order.
- Claim: 11. The system of claim 8 , wherein the ray data comprises at least one of a length, or an orientation of a ray.
- Claim: 12. The system of claim 8 , wherein the determined order orders the children nodes according to the respective distance in an ascending order.
- Claim: 13. The system of claim 8 , wherein the instructions further cause the system to: receive another traversal instruction including a tracing-mode, ray data for a ray, and an identifier of another node to be traversed, wherein the tracing-mode of the another traversal instruction comprises a first hit mode; in response to a condition where the another node to be traversed is the internal node, determine, according to the tracing-mode, an order in which children nodes of the another node are to be next traversed based on a second respective distance to each respective children node among the children nodes; and output identifiers of the children nodes in a determined order for the another traversal instruction, wherein the second respective distance is computed based on a crossing distance that is an absolute difference between a first location at which the ray enters a volume associated with a respective children node for the another traversal instruction and a second location at which the ray exits the volume for the another traversal instruction and the determined order for the another traversal instruction orders the children nodes according to the respective distance in a descending order.
- Claim: 14. The system of claim 8 , wherein when the first distance is negative, a value of zero is used as the first distance in the averaging.
- Claim: 15. A non-transitory computer-readable medium comprising instructions executable by at least one processor to perform a method for traversing nodes in a bounding volume hierarchy (BVH) tree by an intersection engine, the method comprising: receiving a traversal instruction, including a tracing-mode, ray data for a ray, and an identifier of a node to be traversed, wherein the tracing-mode of the traversal instruction comprises a closest hit mode and the ray data includes a ray origin; in response to a condition where the node to be traversed is an internal node, determining, according to the tracing-mode, an order in which children nodes of the node are to be next traversed based on an average distance to each respective children node among the children nodes; and outputting identifiers of the children nodes in the determined order, wherein the average distance is calculated by averaging a first distance between the rav origin and a first location at which the ray enters a volume associated with a respective children node for the traversal instruction and a second distance between the ray origin and a second location at which the ray exits the volume for the traversal instruction.
- Claim: 16. The non-transitory medium of claim 15 , further comprising: in response to a condition where the node to be traversed is an external node, traversing leaves of the node, including searching primitives that are contained within a volume associated with the node for a ray-intersecting primitive.
- Claim: 17. The non-transitory medium of claim 15 , further comprising: receiving another traversal instruction, including the tracing-mode, the ray data, and an identifier of a node to be next traversed, wherein the identifier is a first outputted identifier in the determined order.
- Claim: 18. The non-transitory medium of claim 15 , wherein the determined order orders the children nodes according to the respective distance in an ascending order.
- Claim: 19. The non-transitory medium of claim 15 , further comprising: receiving another traversal instruction, including a tracing-mode, ray data for a ray, and an identifier of another node to be traversed, wherein the tracing-mode of the another traversal instruction comprises a first hit mode, in response to a condition where the another node to be traversed is the internal node, determining, according to the tracing-mode, an order in which children nodes of the another node are to be next traversed based on a second respective distance to each respective children node among the children nodes; and outputting identifiers of the children nodes in a determined order for the another traversal instruction, wherein the second respective distance is computed based on a crossing distance that is an absolute difference between a first location at which the ray enters a volume associated with a respective children node for the another traversal instruction and a second location at which the ray exits the volume for the another traversal instruction and a determined order for the another traversal instruction orders the children nodes according to the respective distance in a descending order.
- Claim: 20. The non-transitory medium of claim 15 , wherein when the first distance is negative, a value of zero is used as the first distance in the averaging.
- Claim: 21. A method for traversing nodes in a bounding volume hierarchy (BVH) tree by an intersection engine, comprising: receiving a traversal instruction, including a tracing-mode, ray data for a ray, and an identifier of a node to be traversed, wherein the tracing-mode of the traversal instruction comprises a first hit mode; in response to a condition where the node to be traversed is an internal node, determining, according to the tracing-mode, an order in which children nodes of the node are to be next traversed based on a respective distance to each respective children node among the children node; and outputting identifiers of the children nodes in the determined order, wherein the respective distance is computed based on a crossing distance that is an absolute difference between a first location at which the ray enters a volume associated with a respective children node and a second location at which the ray exits the volume for the traversal instruction and the determined order for the traversal instruction orders the children nodes according to the respective distance in a descending order.
- Claim: 22. The method of claim 21 , further comprising: receiving another traversal instruction, including a tracing-mode, ray data for a ray, and an identifier of another node to be traversed, wherein the tracing-mode of the another traversal instruction a closest hit mode and the ray data includes a ray origin, in response to a condition where the another node to be traversed is the internal node, determining, according to the tracing-mode, an order in which children nodes of the another node are to be next traversed based on a second respective distance to each respective children node among the children nodes; and outputting identifiers of the children nodes in a determined order for the another traversal instruction, wherein the second respective distance is computed based on a crossing distance that is an absolute difference between a first location at which the ray enters a volume associated with a respective children node and a second location at which the ray exits the volume for the another traversal instruction and the determined order for the another traversal instruction orders the children nodes according to the respective distance in a descending order.
- Claim: 23. A system for traversing nodes in a bounding volume hierarchy (BVH) tree, comprising: at least one processor; and memory storing instructions that, when executed by the at least one processor, cause the system to: receive a traversal instruction, including a tracing-mode, ray data for a ray, and an identifier of a node to be traversed, wherein the tracing-mode of the traversal instruction comprises a first hit mode, in response to a condition where the node to be traversed is an internal node, determine, according to the tracing-mode, an order in which children nodes of the node are to be next traversed based on a respective distance to each respective children node among the children nodes, and output identifiers of the children nodes in the determined order for the traversal instruction, wherein the respective distance is computed based on a crossing distance that is an absolute difference between a first location at which the ray enters a volume associated with a respective children node and a second location at which the ray exits the volume for the traversal instruction and the determined order for the traversal instruction orders the children nodes according to the respective distance in a descending order.
- Claim: 24. The system of claim 23 , wherein the instructions further cause the system to: receive another traversal instruction, including a tracing-mode, ray data for a ray, and an identifier of another node to be traversed, wherein the tracing-mode of the another traversal instruction comprises a closest hit mode and the ray data includes a ray origin, in response to a condition where the another node to be traversed is the internal node, determining, according to the tracing-mode, an order in which children nodes of the another node are to be next traversed based on a second respective distance to each respective children node among the children nodes; and output identifiers of the children nodes in a determined order for the another traversal instruction, wherein the second respective distance is calculated by averaging a first distance between the ray origin and a first location at which the ray enters a volume associated with a respective children node for the another traversal instruction and a second distance between the ray origin and a second location at which the ray exits the volume for the another traversal instruction.
- Patent References Cited: 11087522 August 2021 Surti et al. ; 20160260245 September 2016 DeCell ; 20170116760 April 2017 Laine et al. ; 20200051315 February 2020 Laine ; 20200193681 June 2020 Saleh ; 20210049808 February 2021 Janus et al. ; 20210209832 July 2021 Saleh et al. ; 20210327118 October 2021 Varadarajan ; 20210390758 December 2021 Muthler et al.
- Other References: Ylitie, H., et al., “Efficient Incoherent Ray Traversal on GPUs Through Compressed Wide BVHs”, HPG '17: Proceedings of High Performance Graphics, Article No. 4, Jul. 2017, 13 pgs. cited by applicant
- Primary Examiner: Yang, Andrew G
- Attorney, Agent or Firm: Volpe Koenig
|
