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 .
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP § 2146 et seq. for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The filing of a terminal disclaimer by itself is not a complete reply to a nonstatutory double patenting (NSDP) rejection. A complete reply requires that the terminal disclaimer be accompanied by a reply requesting reconsideration of the prior Office action. Even where the NSDP rejection is provisional the reply must be complete. See MPEP § 804, subsection I.B.1. For a reply to a non-final Office action, see 37 CFR 1.111(a). For a reply to final Office action, see 37 CFR 1.113(c). A request for reconsideration while not provided for in 37 CFR 1.113(c) may be filed after final for consideration. See MPEP §§ 706.07(e) and 714.13.
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The actual filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/apply/applying-online/eterminal-disclaimer.
Claims 1, 17, 20 are rejected on the ground of nonstatutory double patenting as being unpatentable over claim 1 of U.S. Patent No. 11810239. Although the claims at issue are not identical, they are not patentably distinct from each other because the claimed invention of the US patent teaches all features of the claims 1, 17, and 20 of the application.
The application 19/021070
The US patent 11810239
Claim 1. A computer-implemented method of processing rays in a ray bundle in a graphics processing system, the method comprising
using data determined by executing an instance of a shader program corresponding to a first ray of the ray bundle in the execution of an instance of the shader program for a further ray of the ray bundle.
Claim 1. A computer-implemented method of processing rays in a graphics processing system for rendering a scene, the method comprising: grouping a plurality of rays together into a ray bundle; performing intersection testing on the rays of the ray bundle in the scene; using results of the intersection testing for the rays of the ray bundle to determine whether the rays are to be maintained in the ray bundle; and executing one or more shader programs on the rays in the ray bundle, wherein the execution of at least one of the shader programs comprises determining differential data for a particular ray of the ray bundle using data for another ray of the ray bundle.
Claims 17 and 20 claim a graphics processing unit and a non-transitory computer readable storage medium based on the method of claim 1.
Claims 2-16, and 18-19 are rejected on the ground of nonstatutory double patenting as being unpatentable over claim 1 of U.S. Patent No. 11810239 in view of WALD et al (Interactive Rendering with Coherent Ray Tracing) and SPORING et al. (Spatial and Temporal Ray Differentials). The ground of obviousness of claims 2-16, 18-19 are provided similarly in the obviousness rejection of the claimed invention in view of Wald and Sporring.
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1-9, 12-13, 16-20 are rejected under 35 U.S.C. 103 as being unpatentable over HOBEROCK et al (Stream Compaction for Deferred Shading) in view of WALD et al (Interactive Rendering with Coherent Ray Tracing).
As per claim 1, Hoberock teaches the claimed “computer-implemented method of processing rays in a ray bundle in a graphics processing system” (Hoberock, page 2, column 2, 3rd paragraph - SIMD Ray Tracing Interest in SIMD machines as a platform for ray tracing has generated considerable research activity in recent years. The “ray packet” concept originally designed to reorganize rays into coherent bundles is also effective for reducing SIMD divergence in ray-geometry intersection), the method comprising “calculating data determined by executing an instance of a shader program corresponding to a first ray of the ray bundle in the execution of an instance of the shader program for a further ray of the ray bundle” (Hoberock, page 2, 1st column - SIMD Ray Tracing Interest in SIMD machines as a platform for ray tracing has generated considerable research activity in recent years. The “ray packet” concept originally designed to reorganize rays into coherent bundles is also effective for reducing SIMD divergence in ray-geometry intersection; see also Wald, 2.4. Coherence through Packets of Rays – Our main approach is to exploit coherence of primary and shadow rays by traversing, intersecting, and shading packets of rays in parallel. Using this approach we can reduce the compute time of the algorithm by using SIMD instructions on multiple rays in parallel, reduce memory bandwidth by requesting data only once per packet, and increase cache utilization at the same time; 4.1. Traversal Algorithm - The algorithm for tracing four different rays is essentially the same: For each node, we use SSE operations to compute the four distances to the splitting plane and to compare these to the four respective ray segments, all in parallel. If all rays require traversal of the same child, we immediately proceed to that child without having to change the ray segments). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by using calculated data corresponding to a first ray of the ray bundle in the execution of an instance of the shader program for a further ray of the ray bundle. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 2 adds into claim 1 “emitting a secondary ray from each of two or more instances of the shader program; and grouping the secondary rays into another ray bundle” (Wald, 2.4. Coherence through Packets of Rays – Our main approach is to exploit coherence of primary and shadow rays by traversing, intersecting, and shading packets of rays in parallel. Using this approach we can reduce the compute time of the algorithm by using SIMD instructions on multiple rays in parallel, reduce memory bandwidth by requesting data only once per packet, and increase cache utilization at the same time). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by processing different ray bundles of the coherent rays. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 3 adds into claim 2 “wherein said two or more instances of the shader program correspond to rays of the ray bundle” (Wald, 2.4. Coherence through Packets of Rays – Our main approach is to exploit coherence of primary and shadow rays by traversing, intersecting, and shading packets of rays in parallel. Using this approach we can reduce the compute time of the algorithm by using SIMD instructions on multiple rays in parallel, reduce memory bandwidth by requesting data only once per packet, and increase cache utilization at the same time). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by processing different ray bundles of the coherent rays. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 4 adds into claim 1 “performing intersection testing on the rays of the ray bundle” (Wald, 2.5. Parallelism through SIMD Extensions - In the following three sections we discuss in more detail how coherent computations with packets of rays and SIMD operations can be used together to speed up the core of a ray tracer, namely triangle intersection, ray traversal and shading). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by performing intersection test for coherent rays on the ray bundles. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 5 adds into claim 4 “executing a plurality of instances of a shader program, an instance corresponding to a ray of the ray bundle, in response to results of said performing intersection testing on the rays of the ray bundle” (Wald, 3.3. SIMD Barycentric Coordinate Test - In contrast it is much simpler to bundle four rays together and intersect them with a single triangle; 4.3. Traversal Overhead - Most important is the fact that the effective memory bandwidth has been reduced essentially by a factor of four through the new SIMD traversal and intersection algorithms as triangles and BSP nodes need not be loaded separately for each ray). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by performing intersection test for coherent rays on the ray bundles. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 6 adds into claim 1 “receiving an indication via an API to indicate that a plurality of rays are intended to be coherent, wherein the method further comprises grouping said plurality of rays together into the ray bundle on the basis of the received indication” (Wald, 2.4. Coherence through Packets of Rays – Our main approach is to exploit coherence of primary and shadow rays by traversing, intersecting, and shading packets of rays in parallel. Using this approach we can reduce the compute time of the algorithm by using SIMD instructions on multiple rays in parallel, reduce memory bandwidth by requesting data only once per packet, and increase cache utilization at the same time). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by processing different ray bundles of the coherent rays. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 7 adds into claim 1 “constructing a data structure representing the rays in the ray bundle, wherein full precision ray data is stored in the data structure, and wherein difference data is stored in the data structure for one or more of the rays of the ray bundle representing differences in the ray data compared to the full precision ray data stored in the data structure” (Wald, 4.1. Traversal Algorithm - The algorithm for tracing four different rays is essentially the same: For each node, we use SSE operations to compute the four distances to the splitting plane and to compare
these to the four respective ray segments, all in parallel. If all rays require traversal of the same child, we immediately proceed to that child without having to change the ray
segments. Otherwise, we traverse both children, with each ray segments updated to [near, min(far, d)] for the closer, respectively [max (near, d), far] for the distant child. When traversing several rays at the same time, the order of traversal can be ambiguous, since different rays might require a different traversal order. Since the order is based only on the sign of the respective direction, this can happen only if the signs of the four direction vectors do not match, which is a rare case if we assume the rays to be coherent. Additionally, it can be shown that no two rays with the same origin can require different traversal orders. This completely resolves this problem for pinhole cameras and point light sources. If rays are allowed to start in different locations, a straightforward solution is to only allow rays with matching direction signs in the same packet, and tracing the few special cases separately; 4.2. Memory Layout for Better Caching - For best performance we use one float for the split coordinate and squeeze the two flag bits into the 2 low order bits of the pointer, which results in 8 bytes per node or 4 nodes per cache line. By aligning the two children of a node on half a cache line we make sure that both children are fetched together since they are likely to be traversed together. The additional computations to extract these two bits from the pointer are negligible as the traversal code performs very few computations anyway compared to the amount of memory it accesses. For leaf nodes the pointer addresses the list of objects, and the other fields can be used to store the number of objects in the list). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by storing full precision of ray data including the differential data in the data structure. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 8 adds into claim 7 “wherein said full precision ray data is stored in the data structure for one of the rays of the ray bundle, and wherein said difference data is stored in the data structure for the other rays of the ray bundle” (Wald, 4.2. Memory Layout for Better Caching - For best performance we use one float for the split coordinate and squeeze the two flag bits into the 2 low order bits of the pointer, which results in 8 bytes per node or 4 nodes per cache line. By aligning the two children of a node on half a cache line we make sure that both children are fetched together since they are likely to be traversed together. The additional computations to extract these two bits from the pointer are negligible as the traversal code performs very few computations anyway compared to the amount of memory it accesses. For leaf nodes the pointer addresses the list of objects, and the other fields can be used to store the number of objects in the list). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by storing full precision of ray data including the differential data in the data structure. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 9 adds into claim 4 “using results of the intersection testing for the rays of the ray bundle to determine whether the rays are to be maintained in the ray bundle, wherein rays are maintained in the ray bundle if they have matching intersection testing results, wherein rays are considered to have matching intersection testing results if: the rays intersect with the same primitive; the rays intersect with the same mesh; the rays intersect with the same object; the intersections invoke the same one or more shader programs to be executed” (Wald, 2.4. Coherence through Packets of Rays – Our main approach is to exploit coherence of primary and shadow rays by traversing, intersecting, and shading packets of rays in parallel. Using this approach we can reduce the compute time of the algorithm by using SIMD instructions on multiple rays in parallel, reduce memory bandwidth by requesting data only once per packet, and increase cache utilization at the same time); “the difference between surface normals at the intersection points is below an angular threshold; or the difference between the ray depths in the intersection points is below a depth threshold” (Wald, 3.3. SIMD Barycentric Coordinate Test - In contrast it is much simpler to bundle four rays together and intersect them with a single triangle). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by performing intersection test for coherent rays on the ray bundles. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 12 adds into claim 1 “wherein instances of the shader program are executed in parallel for different rays of the ray bundle” (Wald, 2.4. Coherence through Packets of Rays – Our main approach is to exploit coherence of primary and shadow rays by traversing, intersecting, and shading packets of rays in parallel). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by performing ray tracing in parallel for coherent rays on the ray bundles. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 13 adds into claim 1 “splitting a ray from the ray bundle if the ray does not have matching intersection testing results with other rays in the ray bundle” (Wald, 4.1. Traversal Algorithm - The algorithm for tracing four different rays is essentially the same: For each node, we use SSE operations to compute the four distances to the splitting plane and to compare these to the four respective ray segments, all in parallel. If all rays require traversal of the same child, we immediately proceed to that child without having to change the ray segments. Otherwise, we traverse both children, with each ray segments updated to [near, min(far, d)] for the closer, respectively [max (near, d), far] for the distant child. When traversing several rays at the same time, the order of traversal can be ambiguous, since different rays might require a different traversal order. Since the order is based only on the sign of the respective direction, this can happen only if the signs of the four direction vectors do not match, which is a rare case if we assume the rays to be coherent. Additionally, it can be shown that no two rays with the same origin can require different traversal orders. This completely resolves this problem for pinhole cameras and point light sources. If rays are allowed to start in different locations, a straightforward solution is to only allow rays with matching direction signs in the same packet, and tracing the few special cases separately). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by performing intersection test for coherent rays on the ray bundles. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 15 adds into claim 1 “wherein the rays to be grouped together are emitted due to the execution of a shader program, wherein a decision as to which rays to group together into a ray bundle is defined in the shader program causing the rays to be emitted” (Wald, 2.4. Coherence through Packets of Rays – Our main approach is to exploit coherence of primary and shadow rays by traversing, intersecting, and shading packets of rays in parallel. Using this approach we can reduce the compute time of the algorithm by using SIMD instructions on multiple rays in parallel, reduce memory bandwidth by requesting data only once per packet, and increase cache utilization at the same time). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by performing ray tracing in parallel for coherent rays on the ray bundles. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 16 adds into claim 1 “wherein a ray bundle comprises: four rays corresponding to a 2×2 block of fragments; or sixteen rays corresponding to a 4×4 block of fragments, wherein only a 3×3 block of the rays are valid rays and the remaining rays are tracker rays” (Wald, 4.3. Traversal Overhead - As can be seen from this experiment, overhead is in the order of a few percent for 2x2 packets of rays, but goes up for larger packets; Table 2 - Table 2 shows the overhead in additional BSP node traversals for different packet sizes). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by performing ray tracing in parallel for coherent rays on the ray bundles in form of a 2×2 block of fragments. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claims 17 and 20 claim a graphics processing unit and a non-transitory computer readable storage medium based on the method of claim 1; therefore, they are rejected under a similar rationale.
Claim 18 adds into claim 17 “full precision ray data for one of the rays of the ray bundle; and difference data for the other rays of the ray bundle representing differences in the ray data compared to the full precision ray data stored in the data structure” (Wald, 4.1. Traversal Algorithm - The algorithm for tracing four different rays is essentially the same: For each node, we use SSE operations to compute the four distances to the splitting plane and to compare these to the four respective ray segments, all in parallel. If all rays require traversal of the same child, we immediately proceed to that child without having to change the ray segments. Otherwise, we traverse both children, with each ray segments updated to [near, min(far, d)] for the closer, respectively [max (near, d), far] for the distant child. When traversing several rays at the same time, the order of traversal can be ambiguous, since different rays might require a different traversal order. Since the order is based only on the sign of the respective direction, this can happen only if the signs of the four direction vectors do not match, which is a rare case if we assume the rays to be coherent. Additionally, it can be shown that no two rays with the same origin can require different traversal orders. This completely resolves this problem for pinhole cameras and point light sources. If rays are allowed to start in different locations, a straightforward solution is to only allow rays with matching direction signs in the same packet, and tracing the few special cases separately; 4.2. Memory Layout for Better Caching - For best performance we use one float for the split coordinate and squeeze the two flag bits into the 2 low order bits of the pointer, which results in 8 bytes per node or 4 nodes per cache line. By aligning the two children of a node on half a cache line we make sure that both children are fetched together since they are likely to be traversed together. The additional computations to extract these two bits from the pointer are negligible as the traversal code performs very few computations anyway compared to the amount of memory it accesses. For leaf nodes the pointer addresses the list of objects, and the other fields can be used to store the number of objects in the list). Thus, it would have been obvious, in view of Wald, to configure Hoberock’s method as claimed by storing full precision of ray data including the differential data in the data structure. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 19 adds into claim 17 “wherein the full precision ray data comprises: (i) a floating point 3-component vector to represent a ray origin, and (ii) a floating point 3-component vector to represent a ray direction; and wherein the difference data comprises, for each of said one or more of the rays of the ray bundle: (i) three limited precision delta vectors for a ray origin, and (ii) three limited precision delta vectors for a ray direction” which is obvious as the origin position and the ray direction are vectors of 3-componenets in the ray tracing in 3D space.
Claims 10-11 and 14 are rejected under 35 U.S.C. 103 as being unpatentable over HOBEROCK et al (Stream Compaction for Deferred Shading) in view of WALD et al (Interactive Rendering with Coherent Ray Tracing) and SPORING et al. (Spatial and Temporal Ray Differentials).
Claim 10 adds into claim 1 “wherein the execution of an instance of the shader program for said further ray of the ray bundle comprises determining differential data for said further ray of the ray bundle using data for said first ray of the ray bundle” (Sporring, 1 Ray differential - Differentials are rooted in Taylor series, i.e. consider an analytical function f : R → R, and write its Taylor series as, f(x+Δx) = f(x)+f’(x).Δx+O(Δx2), where O is the remainder in Landau notation, and f’ is the first order derivative of f… The differential embodies the full first order structure of a function, and is obtained by replacing the infinitesimals with finite values, i.e. dx with Δx). Thus, it would have been obvious, in view of Wald and Sporring, to configure Hoberock’s method as claimed by calculating differential data for the ray bundles of the coherent rays. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 11 adds into claim 10 “wherein the differential data is indicative of a gradient for the further ray” (Sporring, 2 Transfer, Reflection, and Refraction - We require that the surface unit normal, N, exists at Q, and when F is smooth, then N is parallel to the spatial gradient of F). Thus, it would have been obvious, in view of Wald and Sporring, to configure Hoberock’s method as claimed by calculating differential data or gradient data for the ray bundles of the coherent rays. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Claim 14 adds into claim 1 “if a ray of the ray bundle does not have matching intersection testing results with other rays in the ray bundle, marking the ray as a tracker ray in the ray bundle, wherein tracker rays are used to determine differential data for other rays in the bundle” (Sporring, page 4, 2 Transfer, Reflection, and Refraction and 3 Examples: Triangular Surface Models - A number of differentials described above depend on the surface of intersection. We will now evaluate the differentials to full depth for two popular and practical surface models based on triangles; 3 Examples: Triangular Surface Models - number of differentials described above depend on the surface of intersection). Thus, it would have been obvious, in view of Wald and Sporring, to configure Hoberock’s method as claimed by calculating differential data or gradient data for the ray bundles of the coherent rays. The motivation is improving the efficiency of ray tracing by utilizing the coherence of rays in process.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to PHU K NGUYEN whose telephone number is (571)272-7645. The examiner can normally be reached M-F 8-5pm.
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, Daniel F. Hajnik can be reached at (571) 272-7642. 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.
/PHU K NGUYEN/Primary Examiner, Art Unit 2616
Prosecution Insights