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.
Claims 1, 4, 6-7, 9-11, 14, 16-17, and 19-21 are rejected under 35 U.S.C. 103 as being unpatentable over Yoon (Yoon, Sung-Eui, Sean Curtis, and Dinesh Manocha. "Ray tracing dynamic scenes using selective restructuring." Eurographics Symposium on Rendering 2007 (EGSR 2007). EGSR, 2007.) and Gu (Gu, Yan, Yong He, and Guy E. Blelloch. "Ray specialized contraction on bounding volume hierarchies." Computer Graphics Forum. Vol. 34. No. 7. 2015.).
Regarding claim 1, Yoon teaches a system, comprising:
one or more processors; one or more memories coupled to the one or more processors, the one or more memories storing instructions that, when executed by the one or more processors, cause the one or more processors to: (Yoon; pg. 8, Section 6.1, describes implementation using a laptop with CPU and memory) render a frame of a three-dimensional (3D) scene via a first set of ray casting operations performed in accordance with a first intersection acceleration structure (IAS), the first IAS including a plurality of bounding volumes that each includes a respective portion of the 3D scene (Section 5.4, describes Bounding Volume Hierarchy (BVH) based ray tracing where rays are cast for pixels and intersection queries are accelerated using a BVH of bounding volumes (AABBs) during traversal. Section 3 Bounding Volume Hierarchies, describes that BVH nodes each have an associated bounding volume and that leaf nodes contain scene primitives within the node’s bounding volume. This teaches rendering a frame via ray casting operations performed in accordance with an IAS (the BVH), where the IAS includes multiple bounding volumes each enclosing a respective portion of the 3D scene.)
However, Yoon does not explicitly disclose to determine, for each bounding volume of the plurality of bounding volumes, a subset of virtual light rays associated with the first set of ray casting operations that encounter the bounding volume during the rendering of the frame.
Gu (pgs. 4-5 Section 4.2.2) describes collecting per-node ray traversal statistics by tracing a sample set of rays and maintaining for each BVH node a counter (visitCount) that is incremented when that node is traversed/visited during ray traversal. Gu (Section 4.2.3) further describes integrating the sampling into the rendering pipeline by pre-rendering a small sample of pixels and tracking the counters for each node. This teaches determining for each bounding volume/BVH node the subset of rays that encounter that node during rendering (via sampling/pre-render pass) shown by the per-node visitCount statistics.
generate a modified second IAS for the 3D scene based on the determined subset of virtual light rays for each of the bounding volumes (Yoon; Sections 3.2 and 5.1, describes modifying the BVH acceleration structure by selectively restructuring localized portions (sub-BVHs) including combining primitives from selected subtrees and repartitioning them into new BVH nodes to improve ray tracing performance. Gu; Section 4.2.2, describes generating a modified BVH structure based on the per-node ray traversal statistics by using visitCount-derived traversal probabilities (RDTC) to decide when to contract nodes and restructure the BVH, implemented by the BVHContract procedure (Algorithm 3). Together, the BVH modification/restructuring of Yoon is performed using Gu’s per-node visitCount-derived traversal statistics/probabilities as the basis for deciding which BVH portions to modify and whether to apply contraction/restructuring operations. The system may render a frame using the first IAS, collect per-node ray traversal statistics during a sampling/pre-render pass for that rendering and generate the modified second IAS for use in rendering the remainder of the frame and a subsequent frame. This reads on generating a modified second IAS based on the determined subset of virtual light rays for each bounding volume.) It would have been obvious to one of ordinary skill in the art, before the effective filing date, to modify Yoon’s selective restructuring framework with Gu’s ray-distribution-guided statistics and contraction approach to improve efficiency and overall ray tracing performance.
Claim 11, has similar limitations as of claim 1, therefore it is rejected under the same rationale as claim 1.
Claim 21, has similar limitations as of claim 1, therefore it is rejected under the same rationale as claim 1.
Regarding claim 4, Yoon in view of Gu teaches the system of claim 1, wherein the instructions further cause the one or more processors to render a subsequent frame of the 3D scene via a second set of ray casting operations performed in accordance with the modified second IAS (Yoon; pg. 6, Section 5.1, describes the selective restructuring algorithm is performed at the beginning of each fram, generating a modified BVH, and then BVH-based ray tracing is performed using the modified structure. This teaches rendering a subsequent frame using the modified second IAS because Yoon updates/restructures the BVH at the beginning of a frame and then uses that updated BVH for ray tracing).
Claim 14, has similar limitations as of claim 4, therefore it is rejected under the same rationale as claim 4.
Regarding claim 6, Yoon in view of Gu teaches the system of claim 1, wherein the instructions further cause the one or more processors to generate a model of the bounding volumes included by the first IAS based at least in part on a quantity of virtual light rays associated with the determined subset for each bounding volume (Gu; Section 4.2.2, describes collecting ray statistics by storing, in each BVH node, a counter (visitCount) indicating the number of times the node is traversed by sample rays and estimating a traversal probability model, where:
PNG
media_image1.png
40
188
media_image1.png
Greyscale
. This teaches generating a model of the bounding volumes based on a quantity of rays for each bounding volume as visitCound and aN correspond to a per-node model based on ray quantities.)
It would have been obvious to one of ordinary skill in the art, before the effective filing date, to modify the combination to generate a model of the bounding volumes based on ray quantity as further taught by Gu to identify inefficient bounding volumes and improve optimization.
Claim 16, has similar limitations as of claim 6, therefore it is rejected under the same rationale as claim 6.
Regarding claim 7, Yoon in view of Gu teaches the system of claim 1, wherein the modified second IAS is based at least in part on a surface area heuristic (Yoon; Section 5.4, describes using a surface area heuristic within the selective restructuring operations. This teaches that the modified second IAS is based at least in part on a SAH.) and wherein the instructions further cause the one or more processors to generate a set of weights for use with the surface area heuristic based at least in part on a normalized quantity of virtual light rays associated with the determined subset for each bounding volume (Gu; Section 4.2.2, generating per-node traversal probabilities,
PNG
media_image1.png
40
188
media_image1.png
Greyscale
, from ray counts. Gu, pg. 6, section 4.4, further describes using aN that is either SA or the vistCount ratio based on the ray-count (
PNG
media_image2.png
60
294
media_image2.png
Greyscale
). This teaches generating weights (aN) for each node for a surface-area-guided heuristic based at least in part on normalized ray quantities for each bounding volume.).
Claim 17, has similar limitations as of claim 7, therefore it is rejected under the same rationale as claim 7.
Regarding claim 9, Yoon in view of Gu teaches the system of claim 1, wherein the first IAS is a bounding volume hierarchy (BVH), and wherein to generate the modified second IAS for the 3D scene includes to generate a modified second BVH (Yoon; pg. 8 Section 5.4, describes BVH-based ray tracing using a BVH of bounding volumes and, Section 5.1, selectively restructuring the BVH to produce an updated BVH for ray tracing. This teaches that the first IAS is a BVH and generating the modified second IAS includes generating a modified second BVH).
Claim 19, has similar limitations as of claim 9, therefore it is rejected under the same rationale as claim 9.
Regarding claim 10, Yoon in view of Gu teaches the system of claim 1, wherein to generate the modified second IAS for the 3D scene includes to generate a modified second IAS that includes a distinct other plurality of bounding volumes (Yoon; pg. 4, Fig. 4 and Section 3.2, describes selectively restructuring a BVH by taking the union of primitives from sub-BVH’s and re-partitioning the primitives into new nodes recursively, producing an updated BVH having different nodes and bounding volumes than the previous BVH. Gu; pg. 3, Definition 1 and pg. 4, 4.2.1 Algorithm 3, describes BVH contraction that removes an interior node and hoists its children to the parent to form a multi-way BVH, producing a modified BVH with a different set of BVH nodes and associated bounding volumes than the original. This teaches generating a modified second IAS having a distinct other plurality of bounding volumes relative to the first IAS.).
Claim 20, has similar limitations as of claim 10, therefore it is rejected under the same rationale as claim 10.
Claims 2, 5, 8, 12, 15, and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Yoon (Yoon, Sung-Eui, Sean Curtis, and Dinesh Manocha. "Ray tracing dynamic scenes using selective restructuring." Eurographics Symposium on Rendering 2007 (EGSR 2007). EGSR, 2007.), Gu (Gu, Yan, Yong He, and Guy E. Blelloch. "Ray specialized contraction on bounding volume hierarchies." Computer Graphics Forum. Vol. 34. No. 7. 2015.), and Muthler (US20210390760A1).
Regarding claim 2, Yoon in view of Gu teaches the system of claim 1, but does not explicitly disclose to determine the subset of virtual light rays includes to determine a subset of virtual light rays that encounter the bounding volume but that do not encounter any rendering primitives included by the bounding volume.
Muthler, ¶0189, describes that leaf nodes found to be intersected by a ray enclose primitives within those intersected leaf nodes to determine which primitives are actually intersected. ¶0073, describes that enlarged bounding volumes for motion can lead to “false hits” where a ray hits the bounding box without intersecting the underlying geometry. This teaches determining rays that encounter a bounding volume, but do not encounter any rendering primitives included by that bounding volume because the system identifies leaf bounding volumes intersected by a ray and performs ray-primitive testing for primitives within those nodes, which allows determining cases where no enclosed primitives are intersected (false hits). It would have been obvious to one of ordinary skill in the art, before the effective filing date, to modify the ray traversal and BVH optimization of Yoon in view of Gu to determine and use Muthler’s false-hit information to improve traversal performance.
Claim 12, has similar limitations as of claim 2, therefore it is rejected under the same rationale as claim 2.
Regarding claim 5, Yoon in view of Gu teaches the system of claim 1,
and wherein to determine the subset of associated virtual light rays and the generation of the modified second IAS for the 3D scene is performed in real- time for each of multiple frames rendered during the session.
Yoon describes (Yoon; pg. 6, Section 5.1) that the selective restructuring is performed at the beginning of each frame and, after computing the BVH at each frame, BVH-based ray tracing is performed using that BVH. Gu describes (Gu; pg. 5, Section 4.2.3) collecting ray-distribution statistics and modifying the BVH via a sampling-and-contraction pipeline. However, they do not explicitly disclose wherein the frame is rendered as part of a gaming session,
Muthler describes, ¶0161, accelerating ray tracing operations to enable ray tracing in real-time graphics applications including games. This teaches rendering the frame as part of a gaming session. Together with Muthler’s teaching of ray tracing used for games, the combination teaches that determining the subset of rays and generating the modified second IAS is performed in real-time and for each of multiple frames rendered during the gaming session.
It would have been obvious to one of ordinary skill in the art, before the effective filing date, to modify Yoon and Gu’s ray-distribution-based BVH optimization in Muthler’s real-time gaming context in order to reduce overhead and improve frame rendering performance.
Claim 15, has similar limitations as of claim 5, therefore it is rejected under the same rationale as claim 5.
Regarding claim 8, Yoon in view of Gu teaches the system of claim 1, but does not explicitly disclose wherein the frame is rendered as part of a gaming session, and wherein the instructions further cause the one or more processors to generate rendering instructions for rendering the 3D scene based on the modified second IAS as part of initiating the gaming session.
Muthler, ¶0161, describes real-time ray tracing for games. This teaches rendering the fram as part of a gaming session. Muthler, ¶0306, further describes ray tracing work is initiated by issuing ray queries to the TTU including providing stack initializers for “traversal starting from a complet” when beginning a new query and, ¶0283, that the SM presents rays with traversal parameters to the TTU. These query parameters correspond to rendering instructions that initiate ray traversal against the acceleration structure. In the combination the traversal starting point (complet) corresponds to the modified second IAS from Yoon and Gu (see claim 1), so the system generates rendering instructions based on the modified IAS as part of initiating gameplay rendering at the start of the gaming session.
It would have been obvious to one of ordinary skill in the art, before the effective filing date, to modify Yoon and Gu’s ray-distribution-based BVH optimization with Muthler’s real time gaming context to improve efficiency and rendering performance during gaming.
Claim 18, has similar limitations as of claim 8, therefore it is rejected under the same rationale as claim 8.
Claims 3 and 13 are rejected under 35 U.S.C. 103 as being unpatentable over Yoon (Yoon, Sung-Eui, Sean Curtis, and Dinesh Manocha. "Ray tracing dynamic scenes using selective restructuring." Eurographics Symposium on Rendering 2007 (EGSR 2007). EGSR, 2007.), Gu (Gu, Yan, Yong He, and Guy E. Blelloch. "Ray specialized contraction on bounding volume hierarchies." Computer Graphics Forum. Vol. 34. No. 7. 2015.), and Laine (US20160071312A1).
Regarding claim 3, Yoon in view of Gu teaches the system of claim 1, but does not explicitly disclose wherein to determine the subset of virtual light rays includes to track a subset of virtual light rays that encounter each respective border of the bounding volume.
Laine, ¶0162, describes that a ray intersects an AABB if any point on the ray lies inside the volume defined by the six planes that comprise the AABB. Determining whether a ray lies inside the AABB involves evaluating the ray with respect to the six planes and a system can track encounters of each plane by incrementing separate counters for rays that cross (evaluated against) each plane. As previously discussed in claim 1, Gu; Sections 4.2.2 and 4.2.3, teaches maintaining per-node visitCount counters to track rays that traverse each node. Together this teaches tracking a subset of rays that encounter each respective border.
It would have been obvious to one of ordinary skill, before the effective filing date, to modify the system of Yoon and Gu by extending Gu’s per-node ray tracking to per-plane tracking as taught by Laine because tracking which borders are encountered by rays enables more targeted volume adjustments and improved optimization.
Claim 13, has similar limitations as of claim 3, therefore it is rejected under the same rationale as claim 3.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to DAN F KALHORI whose telephone number is (571)272-5475. The examiner can normally be reached Mon-Fri 8:30-5:30 ET.
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, Devona Faulk can be reached at (571) 272-7515. 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.
/DAN F KALHORI/Examiner, Art Unit 2618
/DEVONA E FAULK/Supervisory Patent Examiner, Art Unit 2618