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 .
DETAILED ACTION
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 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.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-5, 7-15, 17-19 are rejected under 35 U.S.C. 102 (a)(1) as being anticipated by Tsakok et al. (US Pub 2023/0206539 A1).
As to claim 1, Tsakok discloses a method of operating a graphics processing system that is operable to perform ray tracing using a ray tracing acceleration data structure that comprises a plurality of nodes, wherein each node of the plurality of nodes represents a respective volume, and the plurality of nodes includes at least one parent node that is associated with a respective set of child nodes (¶0029, “FIG. 2 demonstrates a traversing operation through an example BVH acceleration structure 200, based on which one or more features of the disclosure can be implemented. The BVH tree 200 demonstrates nodes connected in a quad-tree hierarchy. Each node in the tree is associated with a volume that spatially encloses on the primitives located within its boundaries. For example, the root node 210 is associated with a volume 240 that spatially encloses on all the primitives that represent the scene, while its children nodes 210.1-4 are associated with respective volumes 240.1-4, each of which spatially encloses on a part of the primitives that are enclosed by the volume 240 associated with the parent node 210. Note that two nodes may be associated with respective volumes that enclose on the same primitives, that is, the respective volumes overlap. Assuming the scene is represented by N primitives (16 of which are shown in FIG. 2 as primitives 230.1-16) in order to find a ray-intersecting primitive, the straightforward way is to exhaustively search (namely, traverse) across all the N primitives. However, to conform to real-time system requirements, only a part of the primitives is traversed”);
wherein the graphics processing system is operable to trace a ray by traversing the ray tracing acceleration data structure and testing the ray against nodes of the ray tracing acceleration data structure to determine whether the ray intersects volumes represented by the nodes, and when it is determined that the ray intersects a volume represented by a parent node, testing the ray against child nodes of the parent node (¶0031, “Traversing an internal node—namely, an internal node traversal operation—involves, first, determining which of the volumes associated with the children nodes (of the internal node) intersects with the ray”);
the method comprising, for at least one parent node of the ray tracing acceleration data structure:
selecting an ordering strategy for determining an order in which to test rays against child nodes of the parent node (¶0031, “second, determining an order in which those ray-intersecting children nodes will be traversed. The determined order can be provided in a list of ordered node identifiers (e.g., pointers) that may be maintained in a stack.”); and
storing, in association with the parent node, ordering information indicative of the selected ordering strategy (¶0031, “The determined order can be provided in a list of ordered node identifiers (e.g., pointers) that may be maintained in a stack. Thus, pointers to the children nodes can be pushed into a last in first out (LIFO) stack in the determined order, so that a children node whose pointer was pushed last into the stack will be popped out first, and so, will be the one to be traversed next.”);
the method further comprising, when tracing a ray:
traversing the ray tracing acceleration data structure, and when it is determined that the ray intersects a volume represented by a parent node for which ordering information is stored (¶0031-0032, “Traversing the BVH tree 200 with respect to a given ray, starts with traversing the root node, internal node 210. Thus, an internal node traversal operation is applied to first determine which of the volumes associated with nodes 210.1-4 intersects with the ray, and, then, to push pointers to those ray-intersecting nodes into a LIFO stack in a certain order. For example, assuming the ray first intersects with the volume associated with internal node 210.1 and then with the volume associated with external node 210.2. In this case, a pointer to node 210.2 is pushed first into the stack and a pointer to node 210.1 is pushed second into the stack. Thus, the next node to be traversed is the node that is next popped from the stack, that is, internal node 210.1. Accordingly, an internal node traversal operation is applied to first determine which of the volumes associated with node 210.1's children nodes 220.1-4 intersects with the ray, and, then, to insert pointers to those ray-intersecting nodes into the LIFO stack in a certain order.”):
determining, using the stored ordering information, an order in which to test the ray against child nodes of the parent node (¶0031-0032, “Traversing the BVH tree 200 with respect to a given ray, starts with traversing the root node, internal node 210. Thus, an internal node traversal operation is applied to first determine which of the volumes associated with nodes 210.1-4 intersects with the ray, and, then, to push pointers to those ray-intersecting nodes into a LIFO stack in a certain order. For example, assuming the ray first intersects with the volume associated with internal node 210.1 and then with the volume associated with external node 210.2. In this case, a pointer to node 210.2 is pushed first into the stack and a pointer to node 210.1 is pushed second into the stack. Thus, the next node to be traversed is the node that is next popped from the stack, that is, internal node 210.1. Accordingly, an internal node traversal operation is applied to first determine which of the volumes associated with node 210.1's children nodes 220.1-4 intersects with the ray, and, then, to insert pointers to those ray-intersecting nodes into the LIFO stack in a certain order.”); and
causing the ray to be tested against child nodes of the parent node in accordance with the determined order (¶0032, “assuming the ray first intersects with the volume associated with internal node 210.1 and then with the volume associated with external node 210.2. In this case, a pointer to node 210.2 is pushed first into the stack and a pointer to node 210.1 is pushed second into the stack. Thus, the next node to be traversed is the node that is next popped from the stack, that is, internal node 210.1.”).
As to claim 2, claim 1 is incorporated and Tsakok discloses selecting an ordering strategy comprises selecting an ordering strategy for determining an order in which to test rays of a particular type; and wherein determining an order comprises determining, using the stored ordering information, an order in which to test a ray of the particular type (¶0038, “FIGS. 6-7 demonstrate ordering that is performed under different tracing modes—that is, the closest hit mode is used when the sought-after primitive is the closest ray-intersecting primitive (as discussed in reference to FIG. 6) and the first hit mode is set when the sought-after primitive is any ray-intersecting primitive (as discussed in reference to FIG. 7).”).
As to claim 3, claim 2 is incorporated and Tsakok discloses not using the stored ordering information to determine an order in which to test rays of a different type (¶0050, “it is possible for software to explicitly specify the manner in which the children nodes are to be ordered for traversal. More specifically, software, such as a shader executing on a workgroup processor 132, or other software, such as software executing on the processor 102 or on another processor, requests an intersection test be performed for a ray against scene geometry. Software (such as the same or different software) also requests that the intersection test be performed with a particular child node ordering mode. This request specifies one of the criteria described herein, including the closest intersection point ordering mode (FIG. 5), the closest midpoint ordering mode (FIG. 6), or the longest intersection span ordering mode (FIG. 7). As a result of this request, the acceleration structure traversal stage 304 performs the intersection test using the specified sorting criterion.”).
As to claim 4, claim 2 is incorporated and Tsakok discloses the particular ray type is visibility ray (¶0002, “Typically, the rendered scene is represented by a large number of primitives that represent graphical elements (e.g., triangles) and their associated geometrical and physical attributes. Rendering effects, performed through ray tracing, requires, for each ray, searching through these large number of primitives to find out any primitive or the closest primitive that intersects the ray, that is, a ray-intersecting primitive. For example, when a shadow effect is to be rendered, ray tracing involves searching for any primitive that may block the ray's path to a source of light. On the other hand, when a reflection effect is to be rendered, ray tracing involves searching for the closest primitive from which a light may be reflected.”).
As to claim 5, claim 1 is incorporated and Tsakok discloses selecting an ordering strategy for determining an order in which to test rays against child nodes of the parent node comprises:
selecting an ordering strategy that is expected to result in child nodes of the parent node that are more likely to contain any intersecting geometry being tested before child nodes of the parent node that are less likely to contain any intersecting geometry (¶0039, “To further speed up the time a ray-intersecting primitive can be found, C1 410 and C2 420 are ordered according to a presumed respective likelihood that a volume contains the sought-after ray-intersecting primitive.”).
As to claim 7, claim 1 is incorporated and Tsakok discloses determining a child node order based on one or more of: (i) child node position; (ii) child node size; and (iii) child node visit/intersection frequency (¶0039, “when the sought-after ray-intersecting primitive is the one that is located closest to the ray's origin (i.e., closest ray-intersecting primitive) then, the closest volume to the ray origin is most likely to contain that primitive. Accordingly, C1 410 and C2 420 can be ordered according to their respective distances between the origin of the ray and the respective locations at which the ray intersects with (enters) these volumes. For example, a first distance associated with C1 410 is the distance between the origin 460 and location 470.1 and a second distance associated with C2 420 is the distance between the origin 460 and location 470.2. Since, the first distance is shorter than the second distance, these volumes can be ordered so that C1 410 is first and C2 420 is second—that is, nodes and leaves that branch out from the node associated with C1 410 will be traversed before nodes and leaves that branch out from the node associated with C2 420.”).
As to claim 8, claim 1 is incorporated and Tsakok discloses causing the ray to be tested in accordance with the determined order comprises adding stack entries to a stack for the ray in an order that will cause the stack entries to be processed in accordance with the determined order (¶0031, “The determined order can be provided in a list of ordered node identifiers (e.g., pointers) that may be maintained in a stack. Thus, pointers to the children nodes can be pushed into a last in first out (LIFO) stack in the determined order, so that a children node whose pointer was pushed last into the stack will be popped out first, and so, will be the one to be traversed next.”).
As to claim 9, Tsakok discloses a method of generating a ray tracing acceleration data structure for use by a graphics processor; the method comprising: generating and storing a ray tracing acceleration data structure that comprises a plurality of nodes, wherein each node of the plurality of nodes represents a respective volume, and the plurality of nodes includes at least one parent node that is associated with a respective set of child nodes; and for at least one parent node of the ray tracing acceleration data structure: selecting an ordering strategy for determining an order in which to test rays against child nodes of the parent node; and storing, in association with the parent node, ordering information indicative of the selected ordering strategy (See claim 1 for detailed analysis.).
As to claim 10, Tsakok discloses a non-transitory computer readable storage medium storing software code which when executing on a processor performs the method of claim 9 (See claim 1 for detailed analysis.).
As to claim 11, Tsakok discloses a graphics processing system that is operable to perform ray tracing using a ray tracing acceleration data structure that comprises a plurality of nodes, wherein each node of the plurality of nodes represents a respective volume, and the plurality of nodes includes at least one parent node that is associated with a respective set of child nodes; the graphics processing system comprising: a ray tracing circuit operable to trace a ray by traversing a ray tracing acceleration data structure and testing the ray against nodes of the ray tracing acceleration data structure to determine whether the ray intersects volumes represented by the nodes, and when it is determined that the ray intersects a volume represented by a parent node, testing the ray against child nodes of the parent node; and a processing circuit operable to, for at least one parent node of a ray tracing acceleration data structure: select an ordering strategy for determining an order in which to test rays against child nodes of the parent node; and store, in association with the parent node, ordering information indicative of the selected ordering strategy; wherein the ray tracing circuit is operable to, when tracing a ray: traverse a ray tracing acceleration data structure, and when it is determined that the ray intersects a volume represented by a parent node for which ordering information has been stored by the processing circuit: determine, using the stored ordering information, an order in which to test the ray against child nodes of the parent node; and cause the ray to be tested against child nodes of the parent node in accordance with the determined order (See claim 1 for detailed analysis.).
As to claim 12, claim 11 is incorporated and Tsakok discloses the processing circuit is operable to select an ordering strategy for determining an order in which to test rays of a particular type; and wherein the ray tracing circuit is operable to determine, using the stored ordering information, an order in which to test a ray of the particular type (See claim 2 for detailed analysis.).
As to claim 13, claim 12 is incorporated and Tsakok discloses the ray tracing circuit is operable to not use the stored ordering information to determine an order in which to test rays of a different type (See claim 3 for detailed analysis.).
As to claim 14, claim 12 is incorporated and Tsakok discloses the particular ray type is visibility ray (See claim 4 for detailed analysis.).
As to claim 15, claim 11 is incorporated and Tsakok discloses the processing circuit is operable to select an ordering strategy for determining an order in which to test rays against child nodes of a parent node by: selecting an ordering strategy that is expected to result in child nodes of the parent node that are more likely to contain any intersecting geometry being tested before child nodes of the parent node that are less likely to contain any intersecting geometry (See claim 5 for detailed analysis.).
As to claim 17, claim 11 is incorporated and Tsakok discloses the system is operable to determine a child node order based on one or more of: (i) child node position; (ii) child node size; and (iii) child node visit/intersection frequency (See claim 7 for detailed analysis.).
As to claim 18, claim 11 is incorporated and Tsakok discloses the ray tracing circuit is operable to cause a ray to be tested in accordance with a determined order by adding stack entries to a stack for the ray in an order that will cause the stack entries to be processed in accordance with the determined order (See claim 8 for detailed analysis.).
As to claim 19, Tsakok discloses a graphics processor that is operable to perform ray tracing using a ray tracing acceleration data structure that comprises a plurality of nodes, wherein each node of the plurality of nodes represents a respective volume, and the plurality of nodes includes at least one parent node in association with which ordering information is stored that is indicative of a selected ordering strategy for determining an order in which to test rays against child nodes of the parent node; the graphics processor comprising: a ray tracing circuit operable to trace a ray by traversing a ray tracing acceleration data structure and testing the ray against nodes of the ray tracing acceleration data structure to determine whether the ray intersects volumes represented by the nodes; and an ordering circuit operable to, when it is determined by the ray tracing circuit that a ray intersects a volume represented by a parent node for which ordering information is stored: determine, using the stored ordering information, an order in which to test the ray against child nodes of the parent node; and cause the ray to be tested against child nodes of the parent node in accordance with the determined order (See claim 1 for detailed analysis.).
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 of this title, 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.
The factual inquiries set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 6 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Tsakok et al. (US Pub 2023/0206539 A1) in view of Dietrich (US Pub 2025/0104330 A1).
As to claim 6, claim 1 is incorporated and Tsakok discloses selecting an ordering strategy based on whether the ordering strategy will be used to determine an order in which to test rays against child nodes when (¶0037, “if a ray-intersecting primitive was found, the engine 330 communicates back 340 to the workgroup processor 310 the found ray-intersecting primitive. When any ray-intersecting primitive is sought, the ray tracing operation is completed. Otherwise, when the closest ray-intersecting primitive is sought, then if the provided ray-intersecting primitive is closer to the ray's origin than a stored candidate, the workgroup processor 310 updates the stored candidate with the provided ray-intersecting primitive and also updates the ray length (in the ray data) based on the location of the updated candidate. Then, again, the workgroup processor 310 pops out of the stack a pointer to the next node to be traversed and sends another traversal instruction to the intersection engine 330, including the tracing-mode, the ray data, and a pointer to that next node to be traversed. This process in which 1) the workgroup processor 310 sends a traversal instruction to the intersection engine 330 with a pointer to a node to be traversed (popped from the stack) and 2) the intersection engine 330 pushes into the stack internal nodes to be next traversed (and/or returns a ray-intersecting primitive to be compared against the stored candidate for ray-intersecting primitive) recursively continues until there are no more pointers in the stack to be traversed. At this point the stored candidate is the result for the closest ray-intersecting primitive.”).
Tsakok does not explicitly discloses selecting an ordering strategy based on whether the ordering strategy will be used to determine an order in which to test rays against child nodes when generating the ray tracing acceleration data structure.
Dietrich discloses selecting an ordering strategy based on whether the ordering strategy will be used to determine an order in which to test rays against child nodes when generating the ray tracing acceleration data structure (Dietrich, ¶0047, “a DRA system may perform various modifications to an existing IAS in order to generate a new and/or modified IAS. As non-limiting examples, the DRA system may modify one or more respective weights for a bounding volume, such as to compensate for a SAH that otherwise would treat all ray directions as equally likely; may determine a modified orientation for an axis used to orient some or all bounding volumes in the IAS (e.g., to select between local x/y/z coordinate axes, an axis of an existing bounding volume, or an axis based on a variance or other characteristic of the axis, such as to utilize a dimension with the greatest variance in order to minimize a size of child volumes); may modify the partitioning of the objects in a scene, arriving at a plurality of bounding volumes that is distinct from that which was used to accelerate rendering of one or more previous frames (e.g., to split one or more objects at a median or mean, to reduce a sum of volumes or surface areas of one or more bounding volumes, to reduce a volume of intersection of one or more bounding volumes, and/or to increase or decrease a separation between child bounding volumes); may modify a shape or other characteristic of one or more bounding volumes (e.g., to select between cubic, cuboid, spherical, or other BV shape); may modify a sequence of traversal through the IAS (e.g., to select breadth-first or depth-first traversal); etc.”).
Tsakok and Dietrich are considered to be analogous art because all pertain to ray tracing. It would have been obvious before the effective filing date of the claimed invention to have modified Tsakok with the features of “selecting an ordering strategy based on whether the ordering strategy will be used to determine an order in which to test rays against child nodes when generating the ray tracing acceleration data structure” as taught by Dietrich. The suggestion/motivation would have been in order to dynamically modifying an intersection acceleration structure (Dietrich, ¶0046.)
As to claim 16, claim 11 is incorporated and the combination of Tsakok and Dietrich discloses the processing circuit is operable to select an ordering strategy based on whether the ordering strategy will be used to determine an order in which to test rays against child nodes when generating the ray tracing acceleration data structure or when traversing the ray tracing acceleration data structure (See claim 6 for detailed analysis.).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Mcallister (US Pub 2023/0252726 A1) discloses generate a stack entry for the node ID of each of the set of child nodes, where the stack entry for the node ID of each of the set of child nodes is generated prior to being stored.
Muthler et al. (US Pub 2021/0390758 A1) discloses determining a particular ordering in which a set of child nodes of the node are to be traversed.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to YU CHEN whose telephone number is (571)270-7951. The examiner can normally be reached on M-F 8-5 PST Mid-day flex.
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, Xiao Wu can be reached on 571-272-7761. 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.
/YU CHEN/Primary Examiner, Art Unit 2613
Prosecution Insights