# US 12,008,703 B2 · Methods and systems for constructing ray tracing acceleration structures > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,008,703 B2 - Document ID: US12008703B2 - Status: Granted - Kind: B2 - Application number: 17/375,315 - Filed: 2021-07-14 - Published: 2022-01-20 - Granted: 2024-06-11 - Earliest claimed: 2020-07-14 - Assignees: Imagination Technologies Limited - Applicants: Imagination Technologies Limited - Inventors: Simon Fenney - Web page: https://patentgrep.com/patent/US12008703B2 ## CPC - G06T 15/06: Ray-tracing - G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals} - G06T 15/08: Volume rendering - G06T 15/506: {Illumination models} - G06T 17/005: {Tree description, e.g. octree, quadtree} - G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes - G06T 2210/21: Collision detection, intersection - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A computer-implemented method of creating a bounding volume hierarchy (BVH) for a model defined with respect to a local coordinate system for the model. The method includes defining BVH branch nodes within the model, establishing a plurality of local transformation matrices for the BVH; and for each BVH branch node, determining a first bounding volume and associating the branch node with one of the plurality of local transformation matrices that maps between the first bounding volume and a second bounding volume in the local coordinate system. ## Claims ### Claim 1 A computer-implemented method of creating a bounding volume hierarchy (BVH) for a model defined with respect to a local coordinate system for the model, the method comprising: defining a plurality of BVH nodes within the model; establishing a plurality of local transformation matrices for the BVH, wherein the number of local transformation matrices is fewer than the number of nodes; and for each of the plurality of BVH nodes, determining a first bounding volume in the local coordinate system, and associating the node with one of the plurality of local transformation matrices that maps between the first bounding volume and a second bounding volume in the local coordinate system. ### Claim 2 (depends on 1) The method according to claim 1, wherein the plurality of local transformation matrices are a fixed set of matrices for the model that are predetermined before defining the BVH, or a fixed set of matrices for the model that are determined, at least in part, based on an analysis of the plurality of BVH nodes, wherein optionally the plurality of local transformation matrices each represent a different, optionally affine, mapping. ### Claim 3 (depends on 1) The method according to claim 1, wherein determining a first bounding volume comprises selecting a bounding volume from a set of candidate bounding volumes. ### Claim 4 (depends on 3) The method according to claim 3, wherein each candidate bounding volume is associated with a different one of the plurality of local transformation matrices. ### Claim 5 (depends on 4) The method according to claim 4, wherein selecting comprises comparing the set of candidate bounding volumes and selecting the optimal bounding volume according to a predefined heuristic, and optionally wherein the predefined heuristic is to select the candidate bounding volume with one of: the smallest volume, the smallest surface area, or smallest cross-sectional area in a specified direction. ### Claim 6 (depends on 1) The method according to claim 1, wherein associating the node with one of the plurality of local transformation matrices comprises storing an indication of the respective local transformation matrix for the BVH node, and optionally wherein storing an indication comprises storing an index identifying the particular local transformation matrix. ### Claim 7 (depends on 1) The method according to claim 1, wherein the first bounding volume is an oriented bounding volume, and the second bounding volume is an axis-aligned bounding volume, or wherein the first bounding volume is an oriented bounding box and the second bounding volume is an axis-aligned bounding box, or wherein the first bounding volume is an oriented ellipsoid and the second bounding volume is a sphere or an axis-aligned ellipsoid. ### Claim 8 (depends on 1) The method according to claim 1, further comprising using the BVH for intersection testing in a ray tracing system. ### Claim 9 (depends on 1) The method according to claim 1, wherein the ray tracing system supports model instancing. ### Claim 10 A ray tracing system configured to create a bounding volume hierarchy (BVH) for a model defined with respect to a local coordinate system for the model, the system comprising a module configured to: define a plurality of BVH nodes within the model, establish a plurality of local transformation matrices for the BVH, wherein the number of local transformation matrices is fewer than the number of nodes; for each of the plurality of BVH nodes, determine a first bounding volume in the local coordinate system and associate the node with one of the plurality of local transformation matrices that maps between the first bounding volume and a second bounding volume in the local coordinate system; and store in memory the BVH, including the second bounding volume and the association between the node and the one of the plurality of local transformation matrices. ### Claim 11 (depends on 1, 10) The ray tracing system of claim 10, wherein the module is configured to perform the method as set forth in claim 1. ### Claim 12 (depends on 1) A non-transitory computer readable storage medium having stored thereon computer readable code configured to cause the method of claim 1 to be performed when the code is run on at least one processor.