Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1, 3-7, 10, 12-16, 19, and 21-23 is/are rejected under 35 U.S.C. 103 as being unpatentable over Muthler et al. (U.S. PGPUB 20210390756) in view of Woop et al. (U.S. PGPUB 20220051467), Schmidt et al. (U.S PGPUB 20040139080), Barnard et al. (U.S. PGPUB 20220114780), and further in view of Obert (U.S. PGPUB 20160292908).
With respect to claim 1, Muthler et al. disclose a method for performing ray tracing operations, the method comprising:
traversing through a bounding volume hierarchy for a ray (paragraph 127, The TTU 138 traverses (FIG. 10 block 920) the acceleration data structure to determine intersections or potential intersections between the ray and the volumetric subdivisions and associated triangles the acceleration data structure represents) to arrive at a well-fit bounding volume for a first node (paragraph 129, The TTU 138 determines which bounding volumes of a BVH data structure the ray intersects (the “ray-complet” test 512)), and wherein the well-fit bounding volume comprises geometry other than a single axis-aligned bounding box for the first node (paragraph 65, an AABB acceleration structure is constructed using compressed treelets (“complets”) that are wide, allowing multiple (e.g., up to 12 in some embodiments) bounding volume children to be tested simultaneously),
evaluating the ray for intersection with the well-fit bounding volume (paragraph 130, If the bounding box test determines that the bounding volume is not intersected by the ray (“No” in step 514), then there is no need to perform any further testing for visualization and the TTU 138 can return this result to the requesting SM 132, paragraph 131, If the bounding box test performed by the TTU 138 reveals that the bounding volume is intersected by the ray (“Yes” in Step 514), then the TTU determines if the bounding volume can be subdivided into smaller bounding volumes (step 518). If there are further subdivisions of the bounding volume (“Yes” in step 518), then those further subdivisions of the bounding volume are accessed and the bounding box test is performed for each of the resulting subdivided bounding volumes to determine which subdivided bounding volumes are intersected by the ray and which are not). However, Muthler et al. do not expressly disclose the first node is one of a traversal node or a procedural node, wherein the well-fit bounding volume comprises a voxel grid that bounds geometry of the first node, wherein the well-fit bounding volume is included within a dedicated filter node that is a parent to the first node, and wherein the voxel-grid is application-defined to bound procedurally defined geometry of the traversal node or the procedural node; and executing or not executing the first shader program based on the evaluating, wherein the first shader program comprises a traversal shader program or a procedural shader program.
Woop et al., who also deal with ray tracing, disclose a method wherein the first node is one of a traversal node or a procedural node (paragraph 428, Graphical elements are shown to the right to indicate inner traversal paths 4303, outer traversal paths 4304, traversal nodes 4305) and executing or not executing the first shader program based on the evaluating, wherein the first shader program comprises a traversal shader program or a procedural shader program (paragraph 432, When a ray intersects a traversal node during an inner traversal, a traversal shader may be spawned, paragraph 434, These spawned shaders may be grouped by the sorting circuitry 4008 to create SIMD batches for execution).
Muthler et al. and Woop et al. are in the same field of endeavor, namely computer graphics.
Before the effective filing date of the claimed invention, it would have been obvious to apply the method wherein the first node is one of a traversal node or a procedural node and executing or not executing the first shader program based on a decision of whether to execute a first shader program associated with the first node based on the evaluating, wherein the first shader program comprises a traversal shader program or a procedural shader program, as taught by Woop et al., to the Muthler et al. system, because this would enable programmable shading and ray traversal control using user-defined functions that can execute with greater SIMD efficiency on existing and future GPU processors. Programmable control of ray traversal enables several important features such as procedural instancing, stochastic level-of-detail selection, custom primitive intersection and lazy BVH updates (paragraph 442 of Woop et al.).
Schmidt et al., who also deal with acceleration structures, disclose a method wherein the bounding volume is included within a dedicated filter node that is a parent to the first node (paragraph 45, The branch nodes may represent the spatial partitioning of the bounded area 110 [bounding volumes I, II, III, and IV in Fig. 4a], paragraph 47, the branch node associated with the first quadrant I, i.e. branch node 142, may be "loaded" while the other branch nodes, i.e. branch nodes 141, 143, and 144, may be "pruned" and subsequently need not be visited). Pruned branch node 141 corresponds to a filter node in that it filters out traversals through objects 104 and 105.
Muthler et al., Woop et al., and Schmidt et al. are in the same field of endeavor, namely computer graphics.
Before the effective filing date of the claimed invention, it would have been obvious to apply the method wherein the bounding volume is included within a dedicated filter node that is a parent to the first node, as taught by Schmidt et al., to the well-fit bounding volume of the Muthler et al. as modified by Woop et al. system, because the hierarchical arrangement of the tree-like structure 150 may permit loading of the actual data (landmark objects or Points of Interests POI) on-demand as a function of the present view or request of the user (paragraph 47 of Schmidt et al.), thus reduce loading of unneeded data.
Barnard et al., who also deal with ray tracing, disclose a method wherein the geometry is application-defined to bound procedurally defined geometry of the traversal node or the procedural node (paragraph 74, The application that submits the geometry to the ray tracing system defines the bounding volume (a box or other simple bounding geometric shape) for the procedural primitive).
Muthler et al., Woop et al., Schmidt et al., and Barnard et al. are in the same field of endeavor, namely computer graphics.
Before the effective filing date of the claimed invention, it would have been obvious to apply the method wherein the geometry is application-defined to bound procedurally defined geometry of the traversal node or the procedural node, as taught by Barnard et al., to the Muthler et al. as modified by Woop et al. and Schmidt et al. system, because a programmer can define how to find intersections with a procedural primitive having a particular shape by writing a suitable intersection shader, rather than having to define that particular shape of the procedural primitive purely with simple primitive shapes (e.g. triangles) that the intersection testing module is configured to process (paragraph 74 of Barnard et al.).
Obert, who also deals with ray tracing, disclose a method wherein the well-fit bounding volume comprises a voxel grid that bounds geometry of the first node (paragraph 138, The numbers 163 and 323 correspond to the resolution of the voxel grid).
Muthler et al., Woop et al., Schmidt et al., Barnard et al., and Obert are in the same field of endeavor, namely computer graphics.
Before the effective filing date of the claimed invention, it would have been obvious to apply the method wherein the well-fit bounding volume comprises a voxel grid that bounds geometry of the first node, as taught by Obert, to the Muthler et al. as modified by Woop et al., Schmidt et al., and Barnard et al. system, because acceleration data structure traversal algorithms may be optimized via more efficient tree structures, by exploiting ray coherency, or by organizing nodes into cache-friendly layouts. These approaches may be applied to BVH trees, KD-trees, or other grid or tree structures (paragraph 46 of Obert).
With respect to claim 3, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the method of claim 1, wherein a shape of the voxel grid is specified by an application (Obert: paragraph 137, Example results were measured on a commodity laptop computer, running an Intel Core i5-2540M CPU and an NVIDIA GeForce 4200M GPU using a ray tracer running on the GPU, paragraph 138, The numbers 163 and 323 correspond to the resolution of the voxel grid. For example, 163 correspond to a voxel grid containing 16×16×16=4096 voxels. Similarly, 323 correspond to a voxel grid containing 32×32×32=32,768 voxels, as specified by the application running the ray tracer).
With respect to claim 4, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the method of claim 1, wherein evaluating the ray for intersection with the well-fit bounding volume includes determining whether at least a portion of the ray is within the well-fit bounding volume (Muthler et al.: paragraph 130, If the bounding box test determines that the bounding volume is not intersected by the ray (“No” in step 514), then there is no need to perform any further testing for visualization and the TTU 138 can return this result to the requesting SM 132. This is because if a ray misses a bounding volume (as in FIG. 1A with respect to bounding volume 310), then the ray will miss all other smaller bounding volumes inside the bounding volume being tested and any primitives that bounding volume contains, Muthler et al.: paragraph 131, If the bounding box test performed by the TTU 138 reveals that the bounding volume is intersected by the ray (“Yes” in Step 514), then the TTU determines if the bounding volume can be subdivided into smaller bounding volumes (step 518). When a ray processes a node using TTU 138, it is testing itself against the bounding volumes of the node's children. The ray only pushes stack entries onto its stack for those branches or leaves whose representative bounding volumes were hit).
With respect to claim 5, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the method of claim 1, wherein the well-fit bounding volume includes a smaller amount of space that is unoccupied by underlying geometry of the first node than a single axis aligned bounding box that tightly fits all underlying geometry of the first node (Muthler et al.: paragraph 72, In each case, an original AABB bounding box represented by the dotted lines can be used to encompass the geometry but would also encompass large amounts of empty space. As FIGS. 2A-2C, 2B1, 2C1 show, in each case the particular geometry can be more tightly fit with multiple (e.g., 4) smaller boxes represented by the solid-line boxes).
With respect to claim 6, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the method of claim 1, wherein executing or not executing the first shader program comprises determining to execute the first shader program in response to the ray intersecting (Woop et al.: paragraph 432, When a ray intersects a traversal node during an inner traversal, a traversal shader may be spawned, paragraph 434, These spawned shaders may be grouped by the sorting circuitry 4008 to create SIMD batches for execution) the well-fit bounding volume (Muthler et al.: paragraph 129, The TTU 138 determines which bounding volumes of a BVH data structure the ray intersects (the “ray-complet” test 512)).
With respect to claim 7, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the method of claim 1, wherein executing or not executing the first shader program comprises determining not to execute the first shader program in response to the ray not intersecting the well-fit bounding volume (Muthler et al.: paragraph 127, Potential intersections can be identified by finding bounding volumes in the acceleration data structure that are intersected by the ray. Descendants of non-intersected bounding volumes need not be examined). As shown in Fig. 10, non-intersected bounding volumes in step 960 forego additional operations.
With respect to claim 10, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose a device (Muthler et al.: paragraph 110, FIG. 9 illustrates an example real time ray interactive tracing graphics system 100) for performing ray tracing operations, the device comprising: a memory configured to store a bounding volume hierarchy (Muthler et al.: paragraph 110, memory 140); and a processor (Muthler et al.: paragraph 111, processor(s) 120) configured to execute the method of claim 1; see rationale for rejection of claim 1.
With respect to claim 12, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the device of claim 10 for executing the method of claim 3; see rationale for rejection of claim 3.
With respect to claim 13, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the device of claim 10 for executing the method of claim 4; see rationale for rejection of claim 4.
With respect to claim 14, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the device of claim 10 for executing the method of claim 5; see rationale for rejection of claim 5.
With respect to claim 15, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the device of claim 10 for executing the method of claim 6; see rationale for rejection of claim 6.
With respect to claim 16, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the device of claim 10 for executing the method of claim 7; see rationale for rejection of claim 7.
With respect to claim 19, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose a non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to perform operations (Muthler et al.: paragraph 211, The SM's can also implement any desired image generation or other functionality in software depending on the application to provide any desired programmable functionality that is not bound to the hardware acceleration features provided by texture mapping hardware, tree traversal hardware or other graphics pipeline hardware) comprising the method of claim 1; see rationale for rejection of claim 1.
With respect to claim 21, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the non-transitory computer-readable medium of claim 19 for implementing the method of claim 3; see rationale for rejection of claim 3.
With respect to claim 22, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the non-transitory computer-readable medium of claim 21, wherein evaluating the ray for intersection with the well-fit bounding volume includes determining whether at least a portion of the ray is within the well-fit bounding volume (Muthler et al.: paragraph 129, The TTU 138 determines which bounding volumes of a BVH data structure the ray intersects (the “ray-complet” test 512)). If the ray intersects the bounding volume, it determines whether a portion of the ray is within the well-fit bounding volume.
With respect to claim 23, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the non-transitory computer-readable medium of claim 21, wherein the well-fit bounding volume includes a smaller amount of space that is unoccupied by underlying geometry of the first node than a single axis aligned bounding box that tightly fits all underlying geometry of the first node (Obert: paragraph 138, For example, the fruit bowl scene with 163 voxels, at a depth of 10, has an 11.2% reduction in the number of ray/AABB intersection tests, to 353 million. The same fruit bowl scene with 323 voxels, at a depth of 10, has a 19.1% reduction in the number of ray/AABB intersection tests, to 321 million). The lesser number of tests infers a smaller amount of space for the bounding volume.
Claim(s) 8 and 17 is/are rejected under 35 U.S.C. 103 as being unpatentable over Muthler et al. (U.S. PGPUB 20210390756) in view of Woop et al. (U.S. PGPUB 20220051467), Schmidt et al. (U.S. PGPUB 20040139080), Barnard et al. (U.S. PGPUB 20220114780), Obert (U.S. PGPUB 20160292908), and further in view of Benthin et al. (U.S. PGPUB 20180300939).
With respect to claim 8 Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the method of claim 1. However, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert do not expressly disclose the traversal shader program comprises a shader program that performs one of constructing an additional portion of the bounding volume hierarchy, or passing a pointer to pre-constructed geometry.
Benthin et al., who also deal with ray tracing, disclose a method wherein the traversal shader program comprises a shader program (paragraph 107, 3D graphics application 1010 contains one or more shader programs including shader instructions 1012, paragraph 223, Each of the components shown in FIG. 22 may be implemented in hardware (e.g., circuitry), software) that performs one of constructing an additional portion of the bounding volume hierarchy (paragraph 223, an object BVH generation module 2208 generates a current iteration of a BVH for each object in a scene and a top level BVH generation module 2209 for constructing a top level BVH over the current set of object BVHs), or passing a pointer to pre-constructed geometry.
Muthler et al., Woop et al., Schmidt et al., Barnard et al., Obert, and Benthin et al. are in the same field of endeavor, namely computer graphics.
Before the effective filing date of the claimed invention, it would have been obvious to apply the method wherein the traversal shader program comprises a shader program that performs one of constructing an additional portion of the bounding volume hierarchy, or passing a pointer to pre-constructed geometry, as taught by Benthin et al., to the Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert system, because each of the object BVHs are initially assumed to have good quality. These object BVHs are either rebuilt per frame for dynamic objects or may be re-used over multiple frames for static objects (paragraph 224 of Benthin et al.), thus maintain good quality bounding volumes.
With respect to claim 17, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., Obert, and Benthin et al. disclose the device of claim 10 for executing the method of claim 8; see rationale for rejection of claim 8.
Claim(s) 9 and 18 is/are rejected under 35 U.S.C. 103 as being unpatentable over Muthler et al. (U.S. PGPUB 20210390756) in view of Woop et al. (U.S. PGPUB 20220051467), Schmidt et al. (U.S. PGPUB 20040139080), Barnard et al. (U.S. PGPUB 20220114789), Obert (U.S. PGPUB 20160292908), and further in view of Saleh et al. (U.S. PGPUB 20210407175).
With respect to claim 9, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert disclose the method of claim 1. However, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert do not expressly disclose the procedural shader program comprises a shader program that procedurally determines whether the ray intersects custom geometry of a leaf node.
Saleh et al., who also deal with ray tracing, disclose a method wherein the procedural shader program comprises a shader program that procedurally determines whether the ray intersects custom geometry of a leaf node (paragraph 37, In the process of traversing a bounding volume hierarchy, in response to the ray tracing pipeline 300 encountering a leaf node that has associated procedural geometry, the ray tracing pipeline 300 triggers execution of a procedure, such as one specified in a shader program (or through other means), to determine whether the ray intersects that procedural geometry. Thus the test for intersection with a procedure is defined procedurally).
Muthler et al., Woop et al., Schmidt et al., Barnard et al., Obert, and Saleh et al. are in the same field of endeavor, namely computer graphics.
Before the effective filing date of the claimed invention, it would have been obvious to apply the method wherein the procedural shader program comprises a shader program that procedurally determines whether the ray intersects custom geometry of a leaf node, as taught by Saleh et al., to the Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., and Obert system, because some example geometry types for leaf nodes are triangles and procedural geometry, although this is not an exhaustive list (paragraph 37 of Saleh et al.), thus this would implement intersection tests on procedural geometry in addition to standard geometry.
With respect to claim 18, Muthler et al. as modified by Woop et al., Schmidt et al., Barnard et al., Obert, and Saleh et al. disclose the device of claim 10 for executing the method of claim 9; see rationale for rejection of claim 9.
Response to Arguments
Applicant’s arguments with respect to claim(s) 1, 10, and 19 have been considered but are moot in view of the new ground(s) of rejection.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
U.S. PGPUB 20210343089 to Halen et al. for a method of using a voxel grid acceleration structure
U.S. PGPUB 20060256112 to Heirich et al. for a method of including a voxel grid as a type of bounding volume hierarchy.
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ANDREW GUS YANG whose telephone number is (571)272-5514. The examiner can normally be reached M-F 9 AM - 5:30 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Kent Chang can be reached at (571)272-7667. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/ANDREW G YANG/Primary Examiner, Art Unit 2614
1/23/26