US-12620162-B2 - Intersection testing for ray tracing

US12620162B2US 12620162 B2US12620162 B2US 12620162B2US-12620162-B2

Abstract

A system and method for performing intersection testing of rays in a ray tracing system. The ray tracing system uses a hierarchical acceleration structure comprising a plurality of nodes, each identifying one or more elements able to be intersected by a ray. The system makes use of a serial-mode ray intersection process, in which, when a ray intersects a bounding volume, a limited number of new ray requests are generated.

Inventors

Daniel Barnard

Assignees

IMAGINATION TECHNOLOGIES LIMITED

Dates

Publication Date: 20260505
Application Date: 20240108
Priority Date: 20200930

Claims (9)

1 . A computer-implemented method of performing intersection testing between one or more rays and elements by nodes of a hierarchical acceleration structure, wherein: a node identifies one or more elements for intersection testing, wherein at least some of the elements identified by the hierarchical acceleration structure are represented by a further node of the hierarchical acceleration structure; wherein the computer-implemented method comprises iteratively performing a serial-mode ray intersection process of: processing the one or more rays and the hierarchical acceleration structure to identify, for each ray, any intersections between the ray and the elements identified by one or more nodes of the hierarchical acceleration structure; for each ray, in response to identifying that the ray intersects with more than a first predetermined number of elements represented by further nodes: testing the ray against each of no more than the first predetermined number of elements; and generating and storing intersection information for the ray, the intersection information being usable to identify any further node that represents an element that was both identified as intersecting the ray and was not tested against the ray, wherein the intersection information comprises one or more sets of one or more data blocks, each set of data blocks representing a different ray, and wherein each data block identifies: a node that identifies more than the first predetermined number of elements, each of which is represented by a further node, with which the respective ray is determined to intersect; and information identifying against which elements, represented by further nodes, of the node the respective ray has already been tested; wherein the step of processing the stored intersection information comprises: identifying a most recently stored data block for the ray; processing the most recently stored data block to test the ray against an element represented by a node of the hierarchical structure against which the ray has not yet been tested and which was identified as intersecting the ray in the most recently stored data block; and updating the stored intersection information.
2 . The computer-implemented method of claim 1 wherein the first predetermined number is 1.
3 . The computer-implemented method of claim 1 , wherein the intersection information identifies: a node identified as intersecting the ray; and information identifying for which further nodes, associated with elements identified by the node, the ray was tested against.
4 . The computer-implemented method of claim 1 , wherein the serial-mode ray intersection process further comprises, for each ray, in response to the number of intersections between the ray and elements represented by further nodes being zero: determining whether the ray is associated with any stored intersection information; and in response to determining that the ray is associated with stored intersection information, processing the stored intersection information to test the ray against an element represented by a node of the hierarchical structure that was identified, in the stored intersection information as representing an element that intersected the ray and was not tested against the ray.
5 . The computer-implemented method of claim 1 , wherein the intersection information is stored in a memory pool shared by all rays.
6 . The computer-implemented method of claim 1 , wherein the serial-mode ray intersection process comprises, for each ray, in response to the number of intersections between the ray and elements represented by further nodes being between one and the first predetermined number inclusively, testing the ray against each intersected element represented by a further node.
7 . The computer-implemented method of claim 1 , wherein: the serial-mode ray intersection process comprises obtaining one or more ray requests, each ray request identifying a ray and a node of the hierarchical structure identifying elements for which the ray of the ray request will undergo intersection testing; and processing the one or more rays and the hierarchical acceleration structure comprises processing the rays identified in the one or more ray requests to identify, for each ray in the one or more ray requests, any intersections between the ray and the elements identified by one or more nodes of the hierarchical acceleration structure.
8 . An intersection testing system for performing intersection testing between one or more rays and elements identified by nodes of a hierarchical acceleration structure, wherein: a node identifies one or more elements for intersection testing, wherein at least some of the elements identified by the hierarchical acceleration structure are represented by a further node of the hierarchical acceleration structure; wherein the intersection testing system comprises an intersection testing processor configured to iteratively perform a serial-mode ray intersection process comprising: processing the one or more rays and the hierarchical acceleration structure to identify, for each ray, any intersections between the ray and the elements identified by one or more nodes of the hierarchical acceleration structure; and for each ray, in response to identifying that the ray intersects with more than a first predetermined number of elements represented by further nodes: testing the ray against each of no more than the first predetermined number of elements; and generating and storing intersection information for the ray, the intersection information being usable to identify any further node that represents an element that was both identified as intersecting the ray and was not tested against the ray, wherein the intersection information comprises one or more sets of one or more data blocks, each set of data blocks representing a different ray, and wherein each data block identifies: a node that identifies more than the first predetermined number of elements, each of which is represented by a further node, with which the respective ray is determined to intersect; and information identifying against which elements, represented by further nodes, of the node the respective ray has already been tested; wherein the step of processing the stored intersection information comprises: identifying a most recently stored data block for the ray; processing the most recently stored data block to test the ray against an element represented by a node of the hierarchical structure against which the ray has not yet been tested and which was identified as intersecting the ray in the most recently stored data block; and updating the stored intersection information.
9 . A non-transitory computer readable storage medium having encoded thereon computer readable code configured to cause to be performed, when the code is run, a computer-implemented method of performing intersection testing between one or more rays and elements identified by nodes of a hierarchical acceleration structure, wherein: a node identifies one or more elements for intersection testing, wherein at least some of the elements identified by the hierarchical acceleration structure are represented by a further node of the hierarchical acceleration structure; wherein the computer-implemented method comprises iteratively performing a serial-mode ray intersection process of: processing the one or more rays and the hierarchical acceleration structure to identify, for each ray, any intersections between the ray and the elements identified by one or more nodes of the hierarchical acceleration structure; and for each ray, in response to identifying that the ray intersects with more than a first predetermined number of elements represented by further nodes: testing the ray against each of no more than the first predetermined number of elements; and generating and storing intersection information for the ray, the intersection information being usable to identify any further node that represents an element that was both identified as intersecting the ray and was not tested against the ray, wherein the intersection information comprises one or more sets of one or more data blocks, each set of data blocks representing a different ray, and wherein each data block identifies: a node that identifies more than the first predetermined number of elements, each of which is represented by a further node, with which the respective ray is determined to intersect; and information identifying against which elements, represented by further nodes, of the node the respective ray has already been tested; wherein the step of processing the stored intersection information comprises: identifying a most recently stored data block for the ray; processing the most recently stored data block to test the ray against an element represented by a node of the hierarchical structure against which the ray has not yet been tested and which was identified as intersecting the ray in the most recently stored data block; and updating the stored intersection information.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS AND CLAIM OF PRIORITY This application is a continuation under 35 U.S.C. 120 of copending application Ser. No. 17/490,784 filed Sep. 30, 2021, now U.S. Pat. No. 11,869,133, which claims foreign priority under 35 U.S.C. 119 from United Kingdom Application Nos. 2015490.2, 2015495.1 and 2015507.3 all filed Sep. 30, 2020, the contents of which are incorporated by reference herein in their entirety. BACKGROUND Ray tracing systems can simulate the manner in which rays (e.g. rays of light) interact with a scene. For example, ray tracing techniques can be used in graphics rendering systems which are configured to produce images from 3-D scene descriptions. The images can be photorealistic, or achieve other objectives. For example, animated movies can be produced using 3-D rendering techniques. The description of a 3D scene typically comprises data defining geometry in the scene. This geometry data is typically defined in terms of primitives, which are often triangular primitives, but can sometimes be other shapes such as other polygons, lines or points. Ray tracing mimics the natural interaction of light with objects in a scene, and sophisticated rendering features can naturally arise from ray tracing a 3-D scene. Ray tracing can be parallelized relatively easily on a pixel-by-pixel level because pixels generally are independent of each other. However, it is difficult to pipeline the processing involved in ray tracing because of the distributed and disparate positions and directions of travel of the rays in the 3-D scene, in situations such as ambient occlusion, reflections, caustics, and so on. Ray tracing allows for realistic images to be rendered but often requires high levels of processing power and large working memories, such that ray tracing can be difficult to implement for rendering images in real-time (e.g. for use with gaming applications), particularly on devices which may have tight constraints on silicon area, cost and power consumption, such as on mobile devices (e.g. smart phones, tablets, laptops, etc.). At a very broad level, ray tracing involves: (i) intersection testing, to identify intersections between rays and geometry (e.g. primitives) in the scene, and (ii) shading, which comprises performing some processing (e.g. by executing a shader program) in response to identifying an intersection to determine how the intersection contributes to the image being rendered. The execution of a shader program may cause further rays to be emitted into the scene. These further rays may be referred to as “secondary rays”. A lot of processing is involved in identifying intersections between rays and geometry in the scene. In a very naïve approach, every ray could be tested against every primitive in a scene and then when all of the intersection hits have been determined, the closest of the intersections could be identified. This approach is not practical to implement for scenes that may have millions or billions of primitives, where the number of rays to be processed may also be millions. Consequently, ray tracing systems typically use an acceleration structure which characterizes the geometry in the scene in a manner which can reduce the work needed for intersection testing. However, even with current state of the art acceleration structures it is difficult to perform intersection testing at a rate that is suitable for rendering images in real-time (e.g. for use with gaming applications), particularly on devices which have tight constraints on silicon area, cost and power consumption, such as on mobile devices (e.g. smart phones, tablets, laptops, etc.). Modern ray tracing architectures typically use acceleration structures based on bounding volume hierarchies—in particular, bounding box hierarchies. Primitives are grouped together into bounding volumes that enclose them. These bounding volumes are, in turn grouped, together into larger bounding volumes that enclose them. Intersection testing then becomes easier, because, if a ray misses a bounding volume, there is no need to test it against any of the children of that bounding volume. Intersection testing proceeds by traversing the hierarchy. If a given ray “hits” a bounding volume (node), it needs to be tested against each of the children of that bounding volume (node). This continues down through the hierarchy until the ray either misses all children of a node, or hits at least one primitive. Testing a ray against a node requires retrieving from memory (i) a description of the ray (typically defined by ray information including at least an origin and direction) and (ii) a description of the geometry of the node (either bounding volume coordinates or coordinates of the primitive). This information is indicated by a ray request, which identifies the ray and the node. SUMMARY This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. T