# US 2019/0318528 A1 · Computer-Graphics Based on Hierarchical Ray Casting > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0318528 A1 - Document ID: US20190318528A1 - Status: Published application - Kind: A1 - Application number: 15/954,513 - Filed: 2018-04-16 - Published: 2019-10-17 - Earliest claimed: 2018-04-16 - Assignees: Oculus VR, LLC - Applicants: Oculus VR, LLC - Inventors: Warren Andrew Hunt; Anton S. Kaplanyan; Michael Mara; Alexander Nankervis - Web page: https://patentgrep.com/patent/US20190318528A1 ## CPC - G06T 15/06: Ray-tracing - G06T 15/08: Volume rendering - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract In one embodiment, a method for determine visibility may perform intersection tests using block beams, tile beams, and rays. First, a computing system may project a block beam to test for intersection with a first bounding volume (BV) in a bounding volume hierarchy. If the beam fully contains BV, the system may test for more granular intersections with the first BV by projecting smaller tile beams contained within the block beam. Upon determining that the first BV partially intersects a tile beam, the system may project the tile beam against a second BV contained within the first BV. If the tile beam fully contains the second BV, the system may test for intersection using rays contained within the tile beam. The system may project procedurally-generated rays to test whether they intersect with objects contained within the second BV. Information associated with intersections may be used to render a computer-generated scene. ## Claims ### Claim 1 A method comprising, by a computing system: accessing a first bounding volume defined within a three-dimensional (3D) space, the first bounding volume containing at least a second bounding volume defined within the 3D space, the second bounding volume containing an object defined in the 3D space; projecting a first beam defined by a first beam footprint into the 3D space to test for intersection with the first bounding volume; determining that the projected first beam fully contains the first bounding volume; testing for intersection using second beams contained within the first beam, wherein each of the second beams is defined by a second beam footprint that is smaller than the first beam footprint, wherein the testing based on one of the second beams comprises: projecting the second beam into the 3D space to test for intersection with the first bounding volume; determining that the first bounding volume partially intersects the projected second beam; based on the determination that the first bounding volume partially intersects the projected second beam, projecting the second beam to test for intersection with the second bounding volume; and determining that the projected second beam fully contains the second bounding volume; testing for intersection using rays contained within the second beam, wherein each of the rays is associated with a ray footprint that is smaller than the second beam footprint, wherein the testing based on one of the rays comprises: projecting the ray into the 3D space to test for intersection with the objected contained within the second bounding volume; determining that the projected ray intersects the object; and storing information associated with the intersection between the ray and the object; and rendering, based on the stored information, a computer-generated scene that includes the object. ### Claim 2 (depends on 1) The method of claim 1, further comprising: projecting the first beam into the 3D space to test for intersection with a third bounding volume that contains the first bounding volume; and determining that the third bounding volume partially intersects the projected first beam; wherein the projecting of the first beam to test for intersection with the first bounding volume is based on the determination that the third bounding volume partially intersects the projected first beam. ### Claim 3 (depends on 1) The method of claim 1, wherein the first bounding volume is contained within a third bounding volume, wherein the testing based on the second beam is initialized to test for intersection with the first bounding volume. ### Claim 4 (depends on 1) The method of claim 1, wherein the ray is procedurally generated for the associated ray footprint. ### Claim 5 (depends on 4) The method of claim 4, wherein generation of the ray comprises: retrieving a footprint center and differentials associated with the ray footprint; transforming the footprint center and the differentials into the 3D space; computing a sample location in the ray footprint using an offset and the transformed footprint center and the differentials; and generating the ray using the sample location. ### Claim 6 (depends on 1) The method of claim 1, wherein based on the determination that the projected first beam fully contains the first bounding volume, the second bounding volume is removed from being a candidate to be tested for intersection with the first beam. ### Claim 7 (depends on 1) The method of claim 1, wherein based on the determination that the projected second beam fully contains the second bounding volume, any additional bounding volume contained within the second bounding volume is removed from being a candidate to be tested for intersection with the second beam. ### Claim 8 (depends on 1) The method of claim 1, wherein definitions of the first bounding volume and the second bounding volume are stored in a hierarchical tree, wherein the first bounding volume is associated with a first node of the hierarchical tree and the second bounding volume is associated with a second node of the hierarchical tree, wherein the second node is within a subtree of the first node. ### Claim 9 (depends on 1) The method of claim 1, wherein the first beam footprint contains a predetermined number of second beam footprints, wherein the second beam footprint contains a predetermined number of ray footprints. ### Claim 10 One or more computer-readable non-transitory storage media embodying software that is operable when executed to cause one or more processors to perform operations comprising: accessing a first bounding volume defined within a three-dimensional (3D) space, the first bounding volume containing at least a second bounding volume defined within the 3D space, the second bounding volume containing an object defined in the 3D space; projecting a first beam defined by a first beam footprint into the 3D space to test for intersection with the first bounding volume; determining that the projected first beam fully contains the first bounding volume; testing for intersection using second beams contained within the first beam, wherein each of the second beams is defined by a second beam footprint that is smaller than the first beam footprint, wherein the testing based on one of the second beams comprises: projecting the second beam into the 3D space to test for intersection with the first bounding volume; determining that the first bounding volume partially intersects the projected second beam; based on the determination that the first bounding volume partially intersects the projected second beam, projecting the second beam to test for intersection with the second bounding volume; and determining that the projected second beam fully contains the second bounding volume; testing for intersection using rays contained within the second beam, wherein each of the rays is associated with a ray footprint that is smaller than the second beam footprint, wherein the testing based on one of the rays comprises: projecting the ray into the 3D space to test for intersection with the objected contained within the second bounding volume; determining that the projected ray intersects the object; and storing information associated with the intersection between the ray and the object; and rendering, based on the stored information, a computer-generated scene that includes the object. ### Claim 11 (depends on 1) The media of claim 1, wherein the software is further operable when executed to cause the one or more processors to perform operations comprising: projecting the first beam into the 3D space to test for intersection with a third bounding volume that contains the first bounding volume; and determining that the third bounding volume partially intersects the projected first beam; wherein the projecting of the first beam to test for intersection with the first bounding volume is based on the determination that the third bounding volume partially intersects the projected first beam. ### Claim 12 (depends on 10) The media of claim 10, wherein the first bounding volume is contained within a third bounding volume, wherein the testing based on the second beam is initialized to test for intersection with the first bounding volume. ### Claim 13 (depends on 10) The media of claim 10, wherein the ray is procedurally generated for the associated ray footprint. ### Claim 14 (depends on 13) The media of claim 13, wherein generation of the ray comprises: retrieving a footprint center and differentials associated with the ray footprint; transforming the footprint center and the differentials into the 3D space; computing a sample location in the ray footprint using an offset and the transformed footprint center and the differentials; and generating the ray using the sample location. ### Claim 15 (depends on 10) The media of claim 10, wherein based on the determination that the projected first beam fully contains the first bounding volume, the second bounding volume is removed from being a candidate to be tested for intersection with the first beam. ### Claim 16 A system comprising: one or more processors and one or more computer-readable non-transitory storage media coupled to one or more of the processors, the one or more computer-readable non-transitory storage media comprising instructions operable when executed by one or more of the processors to cause the system to perform operations comprising: accessing a first bounding volume defined within a three-dimensional (3D) space, the first bounding volume containing at least a second bounding volume defined within the 3D space, the second bounding volume containing an object defined in the 3D space; projecting a first beam defined by a first beam footprint into the 3D space to test for intersection with the first bounding volume; determining that the projected first beam fully contains the first bounding volume; testing for intersection using second beams contained within the first beam, wherein each of the second beams is defined by a second beam footprint that is smaller than the first beam footprint, wherein the testing based on one of the second beams comprises: projecting the second beam into the 3D space to test for intersection with the first bounding volume; determining that the first bounding volume partially intersects the projected second beam; based on the determination that the first bounding volume partially intersects the projected second beam, projecting the second beam to test for intersection with the second bounding volume; and determining that the projected second beam fully contains the second bounding volume; testing for intersection using rays contained within the second beam, wherein each of the rays is associated with a ray footprint that is smaller than the second beam footprint, wherein the testing based on one of the rays comprises: projecting the ray into the 3D space to test for intersection with the objected contained within the second bounding volume; determining that the projected ray intersects the object; and storing information associated with the intersection between the ray and the object; and rendering, based on the stored information, a computer-generated scene that includes the object. ### Claim 17 (depends on 16) The system of claim 16, wherein the processors are further operable when executing the instructions to perform operations comprising: projecting the first beam into the 3D space to test for intersection with a third bounding volume that contains the first bounding volume; and determining that the third bounding volume partially intersects the projected first beam; wherein the projecting of the first beam to test for intersection with the first bounding volume is based on the determination that the third bounding volume partially intersects the projected first beam. ### Claim 18 (depends on 16) The system of claim 16, wherein the first bounding volume is contained within a third bounding volume, wherein the testing based on the second beam is initialized to test for intersection with the first bounding volume. ### Claim 19 (depends on 16) The system of claim 16, wherein the ray is procedurally generated for the associated ray footprint. ### Claim 20 (depends on 19) The system of claim 19, wherein generation of the ray comprises: retrieving a footprint center and differentials associated with the ray footprint; transforming the footprint center and the differentials into the 3D space; computing a sample location in the ray footprint using an offset and the transformed footprint center and the differentials; and generating the ray using the sample location.