# US 2019/0318445 A1 · Apparatus and method for compressing leaf nodes of a bounding volume hierarchy (bvh) > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0318445 A1 - Document ID: US20190318445A1 - Status: Published application - Kind: A1 - Application number: 16/236,185 - Filed: 2018-12-28 - Published: 2019-10-17 - Earliest claimed: 2018-04-11 - Assignees: Intel Corporation - Applicants: Intel Corporation - Inventors: CARSTEN BENTHIN; SVEN WOOP; INGO WALD - Web page: https://patentgrep.com/patent/US20190318445A1 ## CPC - G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining - G06F 9/3877: {using a secondary processor, e.g. coprocessor (peripheral processor G06F13/12)} - G06T 9/40: Tree coding, e.g. quadtree, octree - G06T 15/005: {General purpose rendering architectures} - G06T 15/06: Ray-tracing - G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes - G06T 2210/12: Bounding box - G06T 2210/52: Parallel processing - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Apparatus and method for compressing an acceleration data structure such as a bounding volume hierarchy (BVH). For example, one embodiment of a graphics processing apparatus comprises: one or more cores to execute graphics instructions including instructions to perform ray tracing operations; and compression circuitry to compress lowest level nodes of a hierarchical acceleration data structure comprising a plurality of hierarchically arranged nodes, each of the lowest level nodes comprising pointers to leaf data; the compression circuitry to quantize the lowest level nodes to generate quantized lowest level nodes and to store each quantized lowest level node and associated leaf data without the pointers to the leaf data. ## Claims ### Claim 1 A graphics processing apparatus comprising: one or more cores to execute graphics instructions including instructions to perform ray tracing operations with a hierarchical acceleration data structure comprising a plurality of hierarchically arranged nodes including lowest level nodes, each of the lowest level nodes comprising pointers to leaf data; and compression circuitry to compress the lowest level nodes of the hierarchical acceleration data structure, wherein to compress the lowest level nodes, the compression circuitry is configured to: quantize the lowest level nodes to generate quantized lowest level nodes, and store each quantized lowest level node and associated leaf data without the pointers to the leaf data. ### Claim 2 (depends on 1) The graphics processing apparatus of claim 1 wherein each quantized lowest level node is to be stored contiguously with its associated leaf data and wherein a location of each portion of the leaf data is to be determined based on its contiguously-stored relation to the associated quantized lowest level node. ### Claim 3 (depends on 2) The graphics processing apparatus of claim 2 further comprising: ray traversal circuitry to traverse one or more rays through the hierarchically arranged nodes; and ray intersection circuitry to determine one or more intersections of the one or more rays with one or more primitives associated with the one or more hierarchically arranged nodes. ### Claim 4 (depends on 3) The graphics processing apparatus of claim 3 wherein the one or more primitives are associated with the one or more hierarchically arranged nodes by being enclosed by one or more bounding boxes of the one or more hierarchically arranged nodes. ### Claim 5 (depends on 3) The graphics processing apparatus of claim 3 wherein the ray traversal circuitry and/or the ray intersection circuitry comprises a plurality of execution units to execute a set of instructions to traverse the one or more rays through the hierarchically arranged nodes and determine the one or more intersections. ### Claim 6 (depends on 1) The graphics processing apparatus of claim 1 wherein the hierarchical acceleration data structure comprises a bounding volume hierarchy (BVH) or an oriented bounding box (OBB). ### Claim 7 (depends on 1) The graphics processing apparatus of claim 1 wherein the compression circuitry is to determine common properties of primitives shared by at least one of the lowest level nodes and to cause data related to the common properties to be stored only once and shared by multiple primitives. ### Claim 8 (depends on 7) The graphics processing apparatus of claim 7 wherein the common properties comprise an objectID and/or one or more vertices of the primitives. ### Claim 9 (depends on 3) The graphics processing apparatus of claim 3 wherein the one or more primitives comprise hair primitives and wherein the quantized lowest level nodes comprises oriented bounding boxes (OBBs), wherein the compression circuitry is to perform the additional operations of: determining an oriented coordinate space which is aligned to a hair direction of a first hair primitive; bounding the hair primitive with an axis-aligned bounding box (AABB); and compressing the oriented coordinate space and bounding box for the first hair primitive and one or more other hair primitive that are spatially close together. ### Claim 10 (depends on 9) The graphics processing apparatus of claim 9 the oriented coordinate space is expressed by thee vectors vx, vy, and vz that are orthogonal to each other and wherein transforming a point p into that space works by projecting it onto the axes: px=dot(vx, p), py=dot(vy, p), and pz=dot(vz, p), wherein compressing the oriented coordinate space further comprises: quantizing the vectors vx, vy, and vz using 8-bit signed fixed point numbers to generate quantized vectors vx′, vy′, and vy′. ### Claim 11 A method comprising: executing graphics instructions including instructions to perform ray tracing operations with a hierarchical acceleration data structure comprising a plurality of hierarchically arranged nodes including lowest level nodes, each of the lowest level nodes comprising pointers to leaf data; compressing the lowest level nodes by: quantizing the lowest level nodes to generate quantized lowest level nodes; and storing each quantized lowest level node and associated leaf data without the pointers to the leaf data. ### Claim 12 (depends on 11) The method of claim 11 wherein each quantized lowest level node is to be stored contiguously with its associated leaf data and wherein a location of each portion of the leaf data is to be determined based on its contiguously-stored relation to the associated quantized lowest level node. ### Claim 13 (depends on 12) The method of claim 12 further comprising: traversing one or more rays through the hierarchically arranged nodes; and determining one or more intersections of the one or more rays with one or more primitives associated with the one or more hierarchically arranged nodes. ### Claim 14 (depends on 13) The method of claim 13 wherein the one or more primitives are associated with the one or more hierarchically arranged nodes by being enclosed by one or more bounding boxes of the one or more hierarchically arranged nodes. ### Claim 15 (depends on 13) The method of claim 13 wherein the operations of traversing and determining are performed by a plurality of execution units which execute a set of instructions to traverse the one or more rays through the hierarchically arranged nodes and determine the one or more intersections. ### Claim 16 (depends on 11) The method of claim 11 wherein the hierarchical acceleration data structure comprises a bounding volume hierarchy (BVH) or oriented bounding boxes (OBB). ### Claim 17 (depends on 11) The method of claim 11 further comprising: determining common properties of primitives shared by at least one of the lowest level nodes; and causing data related to the common properties to be stored only once and shared by multiple primitives. ### Claim 18 (depends on 17) The method of claim 17 wherein the common properties comprise an objectID and/or one or more vertices of the primitives. ### Claim 19 (depends on 13) The method of claim 13 wherein the one or more primitives comprise hair primitives and wherein the quantized lowest level nodes comprises oriented bounding boxes (OBBs), wherein the compression circuitry is to perform the additional operations of: determining an oriented coordinate space which is aligned to a hair direction of a first hair primitive; bounding the hair primitive with an axis-aligned bounding box (AABB); and compressing the oriented coordinate space and bounding box for the first hair primitive and one or more other hair primitive that are spatially close together. ### Claim 20 (depends on 19) The method of claim 19 the oriented coordinate space is expressed by thee vectors, vx, vy, and vz, that are orthogonal to each other and wherein transforming a point p into that space works by projecting it onto the axes: px=dot(vx, p), py=dot(vy, p), and pz=dot(vz, p), wherein compressing the oriented coordinate space further comprises: quantizing the vectors vx, vy, and vz using 8-bit signed fixed point numbers to generate quantized vectors vx′, vy′, and vy′. ### Claim 21 A machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform the operations of: executing graphics instructions including instructions to perform ray tracing operations with a hierarchical acceleration data structure comprising a plurality of hierarchically arranged nodes including lowest level nodes, each of the lowest level nodes comprising pointers to leaf data; compressing the lowest level nodes by: quantizing the lowest level nodes to generate quantized lowest level nodes; and storing each quantized lowest level node and associated leaf data without the pointers to the leaf data. ### Claim 22 (depends on 21) The machine-readable medium of claim 21 wherein each quantized lowest level node is to be stored contiguously with its associated leaf data and wherein a location of each portion of the leaf data is to be determined based on its contiguously-stored relation to the associated quantized lowest level node. ### Claim 23 (depends on 22) The machine-readable medium of claim 22 further comprising: traversing one or more rays through the hierarchically arranged nodes; and determining one or more intersections of the one or more rays with one or more primitives associated with the one or more hierarchically arranged nodes. ### Claim 24 (depends on 23) The machine-readable medium of claim 23 wherein the one or more primitives are associated with the one or more hierarchically arranged nodes by being enclosed by one or more bounding boxes of the one or more hierarchically arranged nodes. ### Claim 25 (depends on 23) The machine-readable medium of claim 23 wherein the operations of traversing and determining are performed by a plurality of execution units which execute a set of instructions to traverse the one or more rays through the hierarchically arranged nodes and determine the one or more intersections. ### Claim 26 (depends on 21) The machine-readable medium of claim 21 wherein the hierarchical acceleration data structure comprises a bounding volume hierarchy (BVH) or oriented bounding boxes (OBB). ### Claim 27 (depends on 21) The machine-readable medium of claim 21 further comprising: determining common properties of primitives shared by at least one of the lowest level nodes; and causing data related to the common properties to be stored only once and shared by multiple primitives. ### Claim 28 (depends on 27) The machine-readable medium of claim 27 wherein the common properties comprise an objectID and/or one or more vertices of the primitives. ### Claim 29 (depends on 23) The machine-readable medium of claim 23 wherein the one or more primitives comprise hair primitives and wherein the quantized lowest level nodes comprises oriented bounding boxes (OBBs), wherein the compression circuitry is to perform the additional operations of: determining an oriented coordinate space which is aligned to a hair direction of a first hair primitive; bounding the hair primitive with an axis-aligned bounding box (AABB); and compressing the oriented coordinate space and bounding box for the first hair primitive and one or more other hair primitive that are spatially close together. ### Claim 30 (depends on 19) The machine-readable medium of claim 19 the oriented coordinate space is expressed by thee vectors, vx, vy, and vz, that are orthogonal to each other and wherein transforming a point p into that space works by projecting it onto the axes: px=dot(vx, p), py=dot(vy, p), and pz=dot(vz, p), wherein compressing the oriented coordinate space further comprises: quantizing the vectors vx, vy, and vz using 8-bit signed fixed point numbers to generate quantized vectors vx′, vy′, and vy′.