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 § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 18 and 19 are rejected under 35 U.S.C. 101 because
Regarding claim 18: the claimed invention is directed to non-statutory subject matter. The claim(s) does/do not fall within at least one of the four categories of patent eligible subject matter because applicant’s specification page 45, lines 27-29 states that the term “module” ….may be used herein to generally represent software…Claim 18 has a node processing module, node processing logic, and processing block which are all software/program and are not a process, machine, manufacture or composition of matter.
Regarding claim 19: the claimed invention is directed to non-statutory subject matter. The claim(s) does/do not fall within at least one of the four categories of patent eligible subject matter because applicant’s specification page 45, lines 27-29 states that the term “module” ….may be used herein to generally represent software…Claim 19 has a processing module, a node processing module and processing logic which are all software/program and are not a process, machine, manufacture or composition of matter.
Double Patenting
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 claims at issue 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); and 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 a nonstatutory double patenting ground provided the reference application or patent either is shown to be commonly owned with this application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The USPTO internet Web site contains terminal disclaimer forms which may be used. Please visit http://www.uspto.gov/forms/. The filing date of the application will determine what form 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 http://www.uspto.gov/patents/process/file/efs/guidance/eTD-info-I.jsp.
Claims 1-20 of the present application are rejected on the ground of nonstatutory double patenting as being unpatentable over claims 1-7, 9-17 and 19-20 of the US Patent 11,380,042 (“Pat. ‘042” hereinafter).
The following table shows in detail the correspondence between claim 1 of the present application and claim 1 of Pat. ‘042. The mapping for other claims is also shown, but in less detail for brevity purposes.
Present Application
Pat. ‘042
1. A computer-implemented method for use in a ray tracing system, the method comprising:
inferring, from data representing nodes of a hierarchical acceleration structure, data defining an implicitly represented node of the hierarchal acceleration structure; and
using the inferred data to process the implicitly represented node in the ray tracing system.
1. A computer-implemented method of performing intersection testing in a ray tracing system for use in rendering an image of a scene, the method comprising: receiving data representing at least part of a hierarchical acceleration structure, wherein the hierarchical acceleration structure comprises nodes, each of which represents a region in the scene, wherein the nodes are linked to form the hierarchical acceleration structure, wherein said received data comprises data defining the regions represented by a plurality of the nodes of the hierarchical acceleration structure, and wherein the hierarchical acceleration structure comprises an implicitly represented node, wherein data defining a region represented by the implicitly represented node is not explicitly included as part of said received data but can be inferred from said received data; inferring, from said received data, data defining the region represented by the implicitly represented node; and performing intersection testing on rays in the scene by testing the rays for intersection with regions represented by nodes of the hierarchical acceleration structure, wherein said performing intersection testing on rays in the scene comprises using the inferred data to test the rays for intersection with the region represented by the implicitly represented node of the hierarchical acceleration structure.
2
1
3
1
4
1
5
1
6
2
7
3
8
4
9
5
10
6
11
7
12
9 and 10
13
11
14
12
15
13 and 14
16
15
17
16
18
17
19
19
20
20
Claim Rejections - 35 USC § 102
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 the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claim(s) 1-8, 12, 15 and 18 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Eisemann et al. (“Implicit Object Space Partitioning: The No-Memory BVH”, 2011).
Regarding claim 1, Eisemann discloses a computer-implemented method for use in a ray tracing system, the method comprising:
inferring, from data representing nodes of a hierarchical acceleration structure, data defining an implicitly represented node of the hierarchal acceleration structure (See the Abstract and section 3.1 Overview, 2nd paragraph: “Our No-Memory Hierarchy (NMH) works in very much the same way, only that the bounds of the BVH nodes are derived directly from the primitive information itself. Our main observation here is that each side of the AABB is defined by at least one triangle vertex. Accordingly it is sufficient to find the six vertices and their according triangles that span the AABB to recreate the bounds. These bounding triangles can be computed in advance. An example is given in Figure 2”. In particular, since the bounds of a BVH node can be inferred from a number of triangle vertices, the BVH node could be viewed as an implicitly-represented node. In the example illustrated in Fig. 2, triangles 0-11 constitute data representing nodes of a hierarchical acceleration structure, and triangles 4-7 constitute data defining the blue-colored implicitly-represented node); and
using the inferred data to process the implicitly represented node in the ray tracing system (Section 3.1 Overview, 2nd paragraph: “During traversal the AABB is reconstructed from these bounding triangles only. If the ray intersects with the box these triangles are tested before the traversal continues with the child nodes”).
Regarding claim 2, Eisemann discloses the method of claim 1, wherein the using the inferred data to process the implicitly represented node in the ray tracing system comprises testing a ray for intersection with a region represented by the implicitly represented node of the hierarchical acceleration structure (Section 3.1 Overview, 2nd paragraph: “During traversal the AABB is reconstructed from these bounding triangles only. If the ray intersects with the box these triangles are tested before the traversal continues with the child nodes”).
Regarding claim 3, Eisemann discloses the method of claim 1, further comprising receiving the data representing nodes of the hierarchical acceleration structure (Section 3.1 Overview, 2nd paragraph: “These bounding triangles can be computed in advance... Therefore, a node in our NMH is essentially only a small set of triangles contiguously mapped in memory”).
Regarding claim 4, Eisemann discloses the method of claim 1, wherein data defining a region represented by the implicitly represented node is not explicitly included as part of said data representing nodes of the hierarchical acceleration structure (In Eisemann, the bounds of a BVH node is not explicitly included as part of the data representing nodes of a hierarchical acceleration structure. Rather, the bounds are inferred from triangle vertices).
Regarding claim 5, Eisemann discloses the method of claim 1, wherein the data defining the implicitly represented node comprises data defining a region represented by the implicitly represented node (See Fig. 3 of Eisemann and the associated caption. The bounds of a BVH node defines a region, and these bounds can be derived from triangle vertices).
Regarding claim 6, Eisemann discloses the method of claim 2, wherein a result of testing the ray for intersection with the region represented by the implicitly represented node is used for determining a rendered value (Section 3 Implicit Object Space Partitioning, 1st paragraph: "We propose a simple ray tracing algorithm which offers interactive rendering times for both static and dynamic scenes". It is well known in the art that the color value at the intersection of a ray with a surface is used for determining a rendered value).
Regarding claim 7, Eisemann discloses the method of claim 1, further comprising grouping rays into packets to be tested for intersection with regions represented by nodes of the hierarchical acceleration structure (Abstract: “The implicit acceleration data structure must be constructed only once and can be reused for arbitrary numbers of rays or ray batches without the need to rebuild the hierarchy”) for which data is received in a data block (Section 3.1 Overview, 2nd paragraph: “a node in our NMH is essentially only a small set of triangles contiguously mapped in memory”).
Regarding claim 8, Eisemann discloses the method of claim 5, wherein the data defining the region represented by the implicitly represented node is inferred using data defining regions represented by at least some of the nodes of the hierarchical acceleration structure (Section 3.1 Overview, 2nd paragraph: “The nodes, i.e. the scene triangles, are sorted so that the child nodes can be directly derived from the parent nodes index”. In particular, the bounds of an implicitly-represented child node can be inferred from its parent node index).
Regarding claim 12, Eisemann discloses the method of claim 1, wherein said data representing nodes of the hierarchical acceleration structure comprises one or more data blocks (Fig. 3 shows 6 data blocks in the memory each of which represents a BVH node), wherein a data block comprises data representing a sub-tree within the hierarchical acceleration structure (In Fig. 3, the data block comprising triangles 2 and 3 represents a left sub-tree), wherein the sub-tree comprises one or more nodes at a plurality of levels within the hierarchical acceleration structure (The aforementioned left sub-tree comprises three nodes at two different levels within the hierarchical acceleration structure), wherein the data block comprises: (i) data defining regions represented by the nodes at the lowest level of the sub-tree (In Fig. 3, data blocks 6-7 and 8-9 comprise data defining regions represented by the nodes at the lowest level of the left sub-tree), and (ii) data indicating how the nodes of the sub-tree are linked (In Algorithm 1, the left and right children of a node can be accessed by calling the functions indexForLeftChild() and indexForRightChild(), respectively. This suggests that there is data (e.g. the indices) indicating how the child nodes are linked to their parent node).
Regarding claim 15, Eisemann discloses the method of claim 12, wherein the data block comprises data defining regions which are represented by nodes having a shared ancestor in the hierarchical acceleration structure (In Fig. 3, the data block comprising triangles 2 and 3 comprises data defining regions which are represented by nodes 6-7and 8-9 having a shared ancestor (node 2-3) in the hierarchical acceleration structure), the data block further comprising an indication of a common origin region (In Algorithm 1, the functions indexForLeftChild() and indexForRightChild() both have an argument index, which indicates the index of the current (parent) node. This index value could be viewed as an indication of a common origin region (the parent node region)) and wherein the data in the data block defining the regions which are represented by nodes having a shared ancestor in the hierarchical acceleration structure comprises, for each of the nodes having the shared ancestor, one or more offsets from the common origin region, wherein the common origin region represents the region represented by the shared ancestor (Section 3.2 Representation, 2nd paragraph: “Index zero is the first triangle in the root node. For any other node whose first triangle index is i its children, i.e. the first triangle in the respective nodes, are indexed with ik +2m where k is the branching factor”).
Claim 18 could be rejected using the same rationale set forth in the rejection of claim 1 because Eisemann also discloses the claimed “node processing logic” and “one or more processing blocks” (See Algorithm 1. The code used to compute an AABB from six triangles corresponds to the claimed “node processing logic”, and the code used to test if the AABB is hit corresponds to the claimed “one or more processing blocks”). The algorithm, when run on a processor, makes the processor a node processing module.
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) 9-11 and 13-14 is/are rejected under 35 U.S.C. 103 as being unpatentable over Eisemann, in view of Hazel (Pub. No. 2019/0035147).
Regarding claim 9, Eisemann discloses the method of claim 8
Eisemann, however, does not disclose the above lined-through limitation. In other words, Eisemann does not disclose that the bounds of an implicitly-represented node can be inferred from those of its children.
In the same field of computer graphics, Hazel teaches the above limitation (See par. 136).
It would have been obvious to one skilled in the art before the effective filing date of the claimed invention to modify Eisemann by inferring the bounds of a parent node from those of its children, as taught by Hazel. The motivation would have been to be able to infer the bounds of an implicitly-represented node from either an upper or lower level.
Regarding claim 10, Eisemann in view of Hazel teaches the method of claim 9, wherein either: (i) the descendants of the implicitly represented node at the particular level in the hierarchical acceleration structure are the children of the implicitly represented node in the hierarchical acceleration structure, or (ii) the descendants of the implicitly represented node at the particular level in the hierarchical acceleration structure are the grandchildren of the implicitly represented node in the hierarchical acceleration structure (As disclosed by Hazel in par. 136, the bounds of an implicitly-represented node can be derived from those of its children).
Regarding claim 11, Eisemann in view of Hazel teaches the method of claim 9, wherein the regions represented by the nodes of the hierarchical acceleration structure are axis-aligned bounding boxes in the scene (The term “AABB” used throughout the literature of Eisemann stands for “axis-aligned bounding boxes”, as is well known in the art), and wherein the data defining the region represented by the implicitly represented node is inferred by determining, in each dimension of the scene, a minimum and a maximum component of the components defining the axis-aligned bounding boxes represented by the descendants of the implicitly represented node at the particular level in the hierarchical acceleration structure (Hazel, par. 136: “a bounding volume for the parent node that entirely encompasses all the bounding volumes of the child nodes could be determined (and in an embodiment this is done). In this case, the bounding volume for the parent node could be, and is in an embodiment, generating by taking the minimum and maximum vertex position values along each axis across all of the parent node's child nodes”).
Regarding claim 13, Eisemann discloses the method of claim 12, wherein at least one node of the sub-tree which is at a level above the lowest level of the sub-tree is an implicitly represented node which is implicitly represented by the data in the data block,
In the same field of computer graphics, Hazel teaches the bounds of a node can be derived from those of its child nodes (See par. 136).
It would have been obvious to one skilled in the art before the effective filing date of the claimed invention to modify Eisemann such that the bounds of node 2-3 could be derived from the bounds of its child nodes, 6-7 and 8-9, as taught by Hazel. The motivation would have been to be able to infer the bounds of an implicitly-represented node from either an upper or lower level.
Regarding claim 14, Eisemann in view of Hazel teaches the method of claim 13, wherein the implicitly represented node is the parent node in the sub-tree for said at least some of the nodes at the lowest level of the sub-tree (In Fig. 3 of Eisemann, node 2-3 is the parent node in the left sub-tree for said at least some of the nodes at the lowest level of the sub-tree (i.e. nodes 6-7 and 8-9)).
Claim(s) 16 is/are rejected under 35 U.S.C. 103 as being unpatentable over Eisemann, in view of Asukai et al. (Pub. No. US 2014/0270574).
Regarding claim 16, Eisemann discloses the method of claim 12, wherein said data representing at least part of a hierarchical acceleration structure is received from a memoryof Eisemann implies that data representing at least part of a hierarchical acceleration structure can be loaded from it).
Eisemann, however, does not disclose the above lined-through limitation.
In the same field of image rendering, Asukai teaches that when reading and writing image data on a memory on a pixel-block by pixel-block basis, the time required for data transfer can be reduced if the size of each pixel block is adjusted so as to match the burst length (Par. 6).
In light of the above teaching of Asukai, it would have been obvious to one skilled in the art before the effective filing date of the claimed invention to modify Ozdas by configuring the size of a data block such that it would match the minimum burst size of the memory. The motivation would have been to reduce the time required for data transfer.
Claim(s) 17 and 19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Eisemann, in view of Lee et al. (Pub. No. US 2017/0061674).
Regarding claim 17, Eisemann discloses a method of rendering an image of a scene in a ray tracing system comprising:
generating a hierarchical acceleration structure (The No-Memory Hierarchy (NMH) taught by Eisemann is a hierarchical acceleration structure because it is based on the bounding volume hierarchy (BVH), which is a hierarchical acceleration structure);
performing intersection testing as set forth in claim 2 using at least part of the generated hierarchical acceleration structure (See the rejection of claim 2)
Eisemann does not disclose the above lined-through limitation.
In the same field of ray tracing, Lee teaches executing one or more shader programs to process results of intersection testing to determine rendered values representing an image of a scene (See the abstract and pars. 14-16).
It would have been obvious to one skilled in the art before the effective filing date of the claimed invention to include one or more shader programs in Eisemann such that when executed, the one or more shader programs would process results of the intersection testing to determine rendered values representing the image of the scene, as taught by Lee. The motivation would have been because shader programs in ray tracing offer unmatched realism, flexibility, and performance. They bridge the gap between geometric ray casting and the complex lighting and material calculations needed for photorealistic images, while modern optimizations ensure they remain efficient even in demanding real-time scenarios.
Claim 19 recites similar limitations as claim 17, but is directed to a system. Since the claimed “processing module”, “node processing module”, and “processing logic” could be collectively viewed as a specialized processor when it executes the algorithm 1 of Eisemann, claim 19 could be rejected under the same rationale set forth in the rejection of claim 17.
Claim(s) 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Eisemann, in view of Howson et al. (Pub. No. US 2017/0309059).
Claim 20 recites similar limitations as claim 18, but is directed to a computer readable storage medium having stored thereon an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the integrated circuit manufacturing system to manufacture a node processing module as claimed in claim 18. Although Eisemann does not disclose such a storage medium, Howson does (See par. 104). Therefore, it would have been obvious to one skilled in the art before the effective filing date of the claimed invention to incorporate the teaching of Howson into Eisemann in order to commercialize the technique.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to PHONG X NGUYEN whose telephone number is (571)270-1591. The examiner can normally be reached Mon-Fri 8am - 5pm EST.
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, King Poon can be reached at (571)272-7440. 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.
/PHONG X NGUYEN/ Primary Patent Examiner, Art Unit 2617