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.
Use of indicates a limitation is not explicitly disclosed by the reference alone.
Claim(s) 1-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Luebke (US 2014/0168228) in view of Muthler (US 2020/0050550)
Claim 1
Examiner’s Interpretation:
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art.
Claim Mapping:
Luebke discloses a method of accessing node volume data for use by a graphics processor when rendering a frame that represents a view of a scene comprising one or more objects using a ray tracing process (Luebke, ¶ 2: “The present invention generally relates to three-dimensional (3D) graphics processing, and, more particularly, to fine-grained traversal for ray tracing.”),
wherein the ray tracing process uses a ray tracing acceleration data structure indicative of a distribution of geometry for the scene to be rendered to determine geometry for the scene that may be intersected by a ray being used for a ray tracing operation (Luebke, ¶ 38, 46: “FIG. 3 illustrates an acceleration structure 300 representing a volume traced by a ray using the parallel processing unit 202…As shown, the acceleration structure 300 includes three levels below the root node 310. In one embodiment, each branch of the acceleration structure 300 may include any arbitrary number of levels. The number of levels for any branch within the acceleration structure 300 may be determined by using any number of factors, including, without limitation, the number of graphics objects within a scene, and the number of graphics primitives stored at each leaf node. Typically, when the volume of space represented by a given node includes only a small number of graphics primitives, the volume, and the associated node, are not subdivided further. As a result, the node representing such a volume is not associated with any child nodes. Such a node is called a leaf node, where a leaf node represents a volume of space that includes the small number of graphics objects or graphics primitives, such as a point, line segment, or triangle. In one embodiment, the child nodes of a given node include all nodes at any level below the given node that connect to the given node, either directly or through one or more intermediate nodes.”),
the ray tracing acceleration data structure comprising a plurality of nodes, each node associated with a respective one or more volumes within the scene, and wherein the plurality of nodes includes at least one parent node that is associated with a respective set of plural child nodes (Luebke, ¶ 40: “The level 1 nodes 320 each represent a volume that forms a portion of the volume by the root node 310. The root node 310 is connected to two level 1 nodes 320(0) 320(1), These two level 1 nodes 320(0) 320(1) are called the child nodes of the root node 310, and the root node 310 is the parent node of the two level 1 nodes 320. Taken together, the level 1 child nodes represent the entire volume represented by the root node 310.”),
with a parent node volume encompassing the volumes of its respective child nodes, the ray tracing process comprising testing rays for intersection with the volumes represented by the nodes of the acceleration data structure to determine geometry for the scene to be rendered that may be intersected by the rays (Luebke, ¶ 43-44: “During ray tracing, threads trace paths of light (rays) moving through a geometric scene, where the geometric scene includes one or more graphics objects. In some embodiments, the threads may determine the first graphics object encountered along a ray…During ray traversal, a thread receives a ray or a ray segment and a starting node within the acceleration structure 300, where the node includes a volume of space to be traced by the ray segment. Each ray segment includes a direction, a start point, and an end point. The thread determines whether the ray segment intersects with a graphics object included within any of the child nodes of the starting node”);
the method comprising:
obtaining for a parent node to be tested a set of node volume data indicative of respective volumes of child nodes associated with the parent node (Luebke, ¶ 44: “The thread visits each child node using any technically feasible approach, including, without limitation, in order of distance from the screen surface of the display device 103, or in order of likelihood that the child node contains a graphics object that intersects with the ray segment.”),
Luebke does not explicitly disclose, but Muthler discloses the node volume data comprising, for each child node for which volume data is stored, a respective set of base co-ordinate values, and the node volume data further comprising a set of one or more modifier values that are to be applied to the respective base co-ordinate values for the child nodes in order to determine an associated volume for the child node (Muthler, ¶ 56: “The traversal co-processor also accelerates the transform of each ray from world space into object space to obtain finer and finer bounding box encapsulations of the primitives and reduce the duplication of those primitives across the scene. Objects replicated many times in the scene at different positions, orientations and scales can be represented in the scene as instance nodes which associate a bounding box and leaf node in the world space BVH with a transformation that can be applied to the world-space ray to transform it into an object coordinate space, and a pointer to an object-space BVH.”)
Before the effective filing date of this application, it would have been obvious to one of ordinary skill in the art to consider the base coordinate and modifier as claimed.
One of ordinary skill in the art would have motivation to “This avoids replicating the object space BVH data multiple times in world space, saving memory and associated memory accesses. The instance transform increases efficiency by transforming the ray into object space instead of requiring the geometry or the bounding volume hierarchy to be transformed into world (ray) space and is also compatible with additional, conventional rasterization processes that graphics processing performs to visualize the primitives.”(Muthler, ¶ 56). One of ordinary skill in the art would have had a reasonable expectation of success because both references consider application of acceleration structures in the same context and can benefit from Muthler’s improvement.
Claim 2
Luebke discloses wherein the ray tracing acceleration data structure comprises a tree structure comprising a plurality of branches associated with a respective plurality of leaf nodes (Luebke, ¶ 39: “The acceleration structure 300 is shown in the form of a binary space partitioning tree.”), wherein each non-leaf in the tree structure is a parent node for a respective set of plural child nodes, each non-leaf node thereby being associated with a corresponding plurality of child volumes (Luebke, ¶ 40: “The level 1 nodes 320 each represent a volume that forms a portion of the volume by the root node 310. The root node 310 is connected to two level 1 nodes 320(0) 320(1), These two level 1 nodes 320(0) 320(1) are called the child nodes of the root node 310, and the root node 310 is the parent node of the two level 1 nodes 320. Taken together, the level 1 child nodes represent the entire volume represented by the root node 310.”), and wherein testing rays for intersection with the volume associated with a node comprises testing the rays for intersection with the volumes for each of plural set of child nodes for the node being tested and returning a result of the intersection testing for each of the child nodes of the node being tested (Luebke, ¶ 79: “Returning now to step 704, if the current node is a leaf node, then the method 700 proceeds to step 718, where the PPU 202 tests the ray or ray segment against the geometry objects or the geometry primitives associated with the leaf node. At step 720, the PPU 202 determines whether the ray has hit any geometric objects or primitives inside the leaf node.”).
Claim 3
Luebke does not explicitly disclose, but Muthler discloses wherein the node volume data includes an indication of whether the child node is a non-leaf node (Muthler, ¶ 334: “child pointers are stored in compressed form. [0336] Zero or more instance nodes, which provide a way to connect a leaf of one BVH to the root of another”)
Before the effective filing date of this application, it would have been obvious to one of ordinary skill in the art to consider a leaf indicator.
One of ordinary skill in the art would have motivation to “This avoids replicating the object space BVH data multiple times in world space, saving memory and associated memory accesses. The instance transform increases efficiency by transforming the ray into object space instead of requiring the geometry or the bounding volume hierarchy to be transformed into world (ray) space and is also compatible with additional, conventional rasterization processes that graphics processing performs to visualize the primitives.”(Muthler, ¶ 56). One of ordinary skill in the art would have had a reasonable expectation of success because both references consider application of acceleration structures in the same context and can benefit from Muthler’s improvement.
Claim 4
Luebke does not disclose, but Muthler discloses further comprising: for each child node, applying the set of one or more modifier values to the respective base co-ordinate values for the child node to determine a set of modified co-ordinate values usable to determine an associated volume for the child node (Muthler, ¶ 56: “The traversal co-processor also accelerates the transform of each ray from world space into object space to obtain finer and finer bounding box encapsulations of the primitives and reduce the duplication of those primitives across the scene. Objects replicated many times in the scene at different positions, orientations and scales can be represented in the scene as instance nodes which associate a bounding box and leaf node in the world space BVH with a transformation that can be applied to the world-space ray to transform it into an object coordinate space, and a pointer to an object-space BVH.”)
Before the effective filing date of this application, it would have been obvious to one of ordinary skill in the art to consider the base coordinate and modifier as claimed.
One of ordinary skill in the art would have motivation to “This avoids replicating the object space BVH data multiple times in world space, saving memory and associated memory accesses. The instance transform increases efficiency by transforming the ray into object space instead of requiring the geometry or the bounding volume hierarchy to be transformed into world (ray) space and is also compatible with additional, conventional rasterization processes that graphics processing performs to visualize the primitives.”(Muthler, ¶ 56). One of ordinary skill in the art would have had a reasonable expectation of success because both references consider application of acceleration structures in the same context and can benefit from Muthler’s improvement.
Claim 5
Luebke does not explicitly disclose, but Muthler discloses wherein the node volume data further comprises an origin co-ordinate, wherein the set of modified co-ordinate values are defined with respect to the origin co-ordinate (Muthler, ¶ 334: “Child complets of a given parent are preferably stored contiguously in memory and child pointers are stored in compressed form. [0336] Zero or more instance nodes, which provide a way to connect a leaf of one BVH to the root of another. An instance node may be a data structure that is also aligned. This structure may contain a pointer to the sub-BVH, flags that affect back-face culling behavior in the sub-BVH, and a matrix that corresponds to the first three rows of an arbitrary transformation matrix (in homogeneous coordinates) from the coordinate system of the top-level BVH (commonly “world space”) to that of the sub-BVH (commonly “object space”). The final row of the matrix in some embodiments is in some implementations implicitly (0, 0, 0, 1). [0337] Zero or more triangle or other primitive buffers, containing for example triangles stored either as a triplet of coordinates per vertex or in a lossless compressed format understood by the TTU 700”)
Before the effective filing date of this application, it would have been obvious to one of ordinary skill in the art to an origin.
One of ordinary skill in the art would have motivation to “This avoids replicating the object space BVH data multiple times in world space, saving memory and associated memory accesses. The instance transform increases efficiency by transforming the ray into object space instead of requiring the geometry or the bounding volume hierarchy to be transformed into world (ray) space and is also compatible with additional, conventional rasterization processes that graphics processing performs to visualize the primitives.”(Muthler, ¶ 56). One of ordinary skill in the art would have had a reasonable expectation of success because both references consider application of acceleration structures in the same context and can benefit from Muthler’s improvement.
Claim 6
Luebke does not explicitly disclose, but Muthler discloses wherein the origin co-ordinate comprises a co-ordinate of a vertex of the parent node volume (Muthler, ¶ 334: “Child complets of a given parent are preferably stored contiguously in memory and child pointers are stored in compressed form. [0336] Zero or more instance nodes, which provide a way to connect a leaf of one BVH to the root of another. An instance node may be a data structure that is also aligned. This structure may contain a pointer to the sub-BVH, flags that affect back-face culling behavior in the sub-BVH, and a matrix that corresponds to the first three rows of an arbitrary transformation matrix (in homogeneous coordinates) from the coordinate system of the top-level BVH (commonly “world space”) to that of the sub-BVH (commonly “object space”). The final row of the matrix in some embodiments is in some implementations implicitly (0, 0, 0, 1). [0337] Zero or more triangle or other primitive buffers, containing for example triangles stored either as a triplet of coordinates per vertex or in a lossless compressed format understood by the TTU 700”)
Before the effective filing date of this application, it would have been obvious to one of ordinary skill in the art to an origin.
One of ordinary skill in the art would have motivation to “This avoids replicating the object space BVH data multiple times in world space, saving memory and associated memory accesses. The instance transform increases efficiency by transforming the ray into object space instead of requiring the geometry or the bounding volume hierarchy to be transformed into world (ray) space and is also compatible with additional, conventional rasterization processes that graphics processing performs to visualize the primitives.”(Muthler, ¶ 56). One of ordinary skill in the art would have had a reasonable expectation of success because both references consider application of acceleration structures in the same context and can benefit from Muthler’s improvement.
Claim 7
Luebke does not explicitly disclose, but Muthler discloses wherein the node volume data is stored in a memory 7. and wherein the graphics processor when accessing the memory is configured to read in a certain amount of data in a single memory transaction, and wherein the node volume data for a single parent node to be tested is stored in a single block of data corresponding to the amount of data that can be accessed in a single memory transaction, the method thus comprising obtaining the node volume data for the parent node to be tested by fetching all of the node volume data for the parent node in a single memory transaction (Muthler, ¶ 126: “Retrieved portions of the BVH data structure may be cached in the level-zero (L0) cache 750 within the TTU 700 so the information is available for other time-coherent TTU operations, thereby reducing memory 140 accesses. Portions of the BVH data structure needed for the ray-complet test may be stored in a L0 complet cache 752 and portions of the BVH data structure needed for the ray-primitive test may be stored in an L0 primitive cache 754.”)
Before the effective filing date of this application, it would have been obvious to one of ordinary skill in the art to an origin.
One of ordinary skill in the art would have motivation to “This avoids replicating the object space BVH data multiple times in world space, saving memory and associated memory accesses. The instance transform increases efficiency by transforming the ray into object space instead of requiring the geometry or the bounding volume hierarchy to be transformed into world (ray) space and is also compatible with additional, conventional rasterization processes that graphics processing performs to visualize the primitives.”(Muthler, ¶ 56). One of ordinary skill in the art would have had a reasonable expectation of success because both references consider application of acceleration structures in the same context and can benefit from Muthler’s improvement.
Claim 8
The same teachings and rationales in claim 1 are appliable to claim 8 with Luebke and Muthler both disclosing equivalent graphics processors (See Luebke Fig. 2).
Claim 9
The same teachings and rationales in claim 2 are appliable to claim 9.
Claim 10
The same teachings and rationales in claim 3 are appliable to claim 10.
Claim 11
The same teachings and rationales in claim 4 are appliable to claim 11.
Claim 12
The same teachings and rationales in claim 5 are appliable to claim 12.
Claim 13
The same teachings and rationales in claim 6 are appliable to claim 13.
Claim 14
The same teachings and rationales in claim 7 are appliable to claim 14.
Claim 15
Examiner’s Interpretation:
Machine readable media can encompass forms of signal transmission media that falls outside of the four statutory categories of invention. MPEP 2106; citing In re Nuijten, 500 F.3d 1346, 84 USPQ2d 1495 (Fed. Cir. 2007). A claim whose BRI covers both statutory and non-statutory embodiments embraces subject matter that is not eligible for patent protection and therefore is directed to non-statutory subject matter. MPEP 2106.
Claims 15-20 as drafted recite a non-transitory computer readable storage medium…
Because non-transitory explicitly excludes ineligible subject matter, the broadest reasonable interpretation of the claimed medium in view of Applicant’s specification covers only eligible subject matter.
Claim Mapping:
The same teachings and rationales in claim 1 are appliable to claim 15.
Claim 16
The same teachings and rationales in claim 7 are appliable to claim 16.
Claim 17
The same teachings and rationales in claim 4 are appliable to claim 17.
Claim 18
The same teachings and rationales in claim 5 are appliable to claim 18.
Claim 19
The same teachings and rationales in claim 6 are appliable to claim 19.
Claim 20
The same teachings and rationales in claim 3 (which incorporates parent claim 2) are appliable to claim 20.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to RYAN M GRAY whose telephone number is (571)272-4582. The examiner can normally be reached on Monday through Friday, 9:00am-5:30pm (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, Kee Tung can be reached on (571)272-7794. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see https://ppair-my.uspto.gov/pair/PrivatePair. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/RYAN M GRAY/Primary Examiner, Art Unit 2611