# US 12,217,353 B2 · Quantized ray intersection testing with definitive hit detection > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,217,353 B2 - Document ID: US12217353B2 - Status: Granted - Kind: B2 - Application number: 18/490,548 - Filed: 2023-10-19 - Published: 2024-02-08 - Granted: 2025-02-04 - Earliest claimed: 2021-09-24 - Assignees: Apple Inc. - Applicants: Apple Inc. - Inventors: Christopher A. Burns - Web page: https://patentgrep.com/patent/US12217353B2 ## CPC - G06T 15/06: Ray-tracing - G06T 15/506: {Illumination models} - G06T 2215/12: Shadow map, environment map - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract Techniques are disclosed relating to intersection tests for ray tracing in graphics processors. In some embodiments, test circuitry is configured to perform an intersection test based on traversal of an acceleration data structure that includes hierarchically-arranged bounding volumes for a graphics scene, where the test operates on: reduced-precision representations of rays that are quantized versions of initial representations of the rays and reduced-representatives of primitives that are quantized versions of initial representations of the primitives. The test may generate a first result for a first ray and a first primitive that indicates that a line coincident with the first ray definitively intersects the first primitive. The graphics processor may record an intersection for the first ray with the first primitive, based on the first result, without performing an intersection test for the first ray using the initial representation of the first ray and the first primitive. ## Claims ### Claim 1 An apparatus, comprising: test circuitry configured to: perform an intersection test based on traversal of an acceleration data structure that includes hierarchically-arranged bounding volumes for a graphics scene, wherein: the intersection test operates on: reduced-precision representations of rays that are quantized versions of initial representations of the rays; and reduced-precision representations of primitives that are quantized versions of initial representations of the primitives; and the intersection test generates a first result for a first ray and a first primitive that indicates that a line coincident with the first ray definitively intersects the first primitive; and graphics processing circuitry configured to record an intersection for the first ray with the first primitive, based on the first result, without performing an intersection test for the first ray using the initial representation of the first ray and the first primitive. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the graphics processing circuitry is further configured to record the intersection based on a determination that there is at least one bounding volume in the acceleration data structure that encloses the entirety of the first primitive and for which the entirety of an enclosed portion of the first ray is active. ### Claim 3 (depends on 2) The apparatus of claim 2, wherein the graphics processing circuitry is further configured to record the intersection based on a determination that the first primitive is opaque. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein the graphics processing circuitry is further configured to record the intersection based on a determination that a query for the first ray is an any-hit query. ### Claim 5 (depends on 1) The apparatus of claim 1, wherein the test circuitry is further configured to output a result for a given ray and a given primitive that indicates either: the given ray missed the given primitive, according to their initial representations; or it is inconclusive whether the given ray missed the given primitive. ### Claim 6 (depends on 1) The apparatus of claim 1, further comprising: traversal circuitry configured to traverse the acceleration data structure including to: perform a depth-first search of the acceleration data structure; and for a set of child nodes of a first node in the acceleration data structure, select a next node for the depth-first search according to an ordering of intersected bounding regions for the set of child nodes, wherein the ordering begins with a bounding volume that is closer to a mid-point of a ray being tested than one or more front bounding volumes and one or more back bounding volumes. ### Claim 7 (depends on 6) The apparatus of claim 6, wherein the traversal circuitry is configured to determine, prior to determination of the ordering, the number of nodes in the set of child nodes that are intersected by the ray being tested. ### Claim 8 (depends on 7) The apparatus of claim 7, wherein, to determine the ordering, the traversal circuitry is configured to sort the set of child nodes by distance from an origin of the first ray and then re-sort the sorted set of child nodes to a middle-out ordering based on a lookup table. ### Claim 9 (depends on 6) The apparatus of claim 6, wherein the ray being tested is an any-hit, secondary ray and traversal for the ray being tested ends in response to detection of an intersection. ### Claim 10 (depends on 6) The apparatus of claim 6, wherein, relative to a starting node at a median of a distance-sorted list of nodes, the ordering alternates between nodes in a front direction and nodes in a back direction. ### Claim 11 (depends on 1) The apparatus of claim 1, further comprising: traversal circuitry configured to traverse the acceleration data structure including to: perform a depth-first search of the acceleration data structure, wherein at least a portion of the acceleration data structure is a binary tree; and alternate between front-to-back and back-to-front orderings when searching child nodes of different levels of the binary tree. ### Claim 12 (depends on 1) The apparatus of claim 1, wherein the intersection tests further generate a second result for a second ray and the first primitive wherein the second result indicates that it is inconclusive whether the second ray intersects the first primitive; and wherein the graphics processing circuitry is further configured to perform an intersection test for the second ray using the initial representation of the second ray and the first primitive. ### Claim 13 (depends on 1) The apparatus of claim 1, wherein the test circuitry includes six modified interval product circuits, six comparators, and combinational logic configured to generate the first result. ### Claim 14 (depends on 1) The apparatus of claim 1, wherein the apparatus is a computing device that further includes: a central processing unit; a display; and network interface circuitry. ### Claim 15 A method, comprising: performing, by a computing system, an intersection test based on traversal of an acceleration data structure that includes hierarchically-arranged bounding volumes for a graphics scene, wherein: the intersection test operates on: reduced-precision representations of rays that are quantized versions of initial representations of the rays; and reduced-precision representations of primitives that are quantized versions of initial representations of the primitives; and the intersection test generates a first result for a first ray and a first primitive that indicates that a line coincident with the first ray definitively intersects the first primitive; and recording, by the computing system, an intersection for the first ray with the first primitive, based on the first result, without performing an intersection test for the first ray using the initial representation of the first ray and the first primitive. ### Claim 16 (depends on 15) The method of claim 15, wherein the recording is further based on determining that there is at least one bounding volume in the acceleration data structure that encloses the entirety of the first primitive and for which the entirety of an enclosed portion of the first ray is active. ### Claim 17 (depends on 15) The method of claim 15, further comprising: performing, by the computing system, a depth-first search of the acceleration data structure; and for a set of child nodes of a first node in the acceleration data structure, selecting a next node for the depth-first search according to an ordering of intersected bounding regions for the set of child nodes, wherein the ordering begins with a bounding volume that is closer to a mid-point of a ray being tested than one or more front bounding volumes and one or more back bounding volumes. ### Claim 18 (depends on 17) The method of claim 17, further comprising determining the ordering by sorting the set of child nodes by distance from an origin of the first ray and then re-sorting the sorted set of child nodes to a middle-out ordering. ### Claim 19 A non-transitory computer readable storage medium having stored thereon design information that specifies a design of at least a portion of a hardware integrated circuit in a format recognized by a semiconductor fabrication system that is configured to use the design information to produce the circuit according to the design, wherein the design information specifies that the circuit includes: test circuitry configured to: perform an intersection test based on traversal of an acceleration data structure that includes hierarchically-arranged bounding volumes for a graphics scene, wherein: the intersection test operates on: reduced-precision representations of rays that are quantized versions of initial representations of the rays; and reduced-precision representations of primitives that are quantized versions of initial representations of the primitives; and the intersection test generates a first result for a first ray and a first primitive that indicates that a line coincident with the first ray definitively intersects the first primitive; and graphics processing circuitry configured to record an intersection for the first ray with the first primitive, based on the first result, without performing an intersection test for the first ray using the initial representation of the first ray and the first primitive. ### Claim 20 (depends on 19) The non-transitory computer readable storage medium of claim 19, wherein design information specifies that graphics processing circuitry is further configured to record the intersection based on a determination that there is at least one bounding volume in the acceleration data structure that encloses the entirety of the first primitive and for which the entirety of an enclosed portion of the first ray is active.