DETAILED ACTION
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 .
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 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 §§ 706.02(l)(1) - 706.02(l)(3) 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 USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The 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/process/file/efs/guidance/eTD-info-I.jsp.
Instant Application 19031051
Patent 12249021
1. A method of ray tracing, the method comprising:
obtaining a hierarchical acceleration data structure, the hierarchical acceleration data structure including a plurality of primitives of a scene object;
obtaining, using an Application Programming Interface (API), an information value associated with each primitive in the plurality of primitives;
determining, using a functional computation,
a plurality of
sorting parameter values for a plurality of nodes in the hierarchical acceleration data structure, the plurality of sorting parameter values including a sorting parameter value for each node of the plurality of nodes,
wherein the sorting parameter value for a node
is based on information values
associated with primitives
in a sub-tree of the node; and
traversing the hierarchical acceleration data structure in association with the plurality of sorting parameter values for the plurality of nodes in the hierarchical acceleration data structure.
1. A method of ray tracing, the method comprising:
obtaining a hierarchical acceleration data structure, the hierarchical acceleration data structure including a plurality of primitives of a scene object;
obtaining a respective
information value associated with each primitive included in the plurality of primitives;
determining
a sort order for two or more nodes associated with sorting the two or more nodes included in a same level of the hierarchical acceleration data structure based on a respective
sorting parameter value determined for each respective node of the two or more nodes,
wherein each respective sorting parameter value
is based on at least one information value associated with one or more primitives included
in a sub-tree of each respective node of the two or more nodes; generating an updated hierarchical acceleration data structure based on the sort order, wherein a plurality of primitives included in the updated hierarchical acceleration data structure is the same as the plurality of primitives included in the hierarchical acceleration data structure; and
traversing the updated hierarchical acceleration data structure.
5. The method of claim 1, wherein each respective information value associated with each primitive is obtained as an input to a ray tracing Application Programming Interface (API).
8. The method of claim 6, wherein the calculated value is determined based on a functional computation specified as an input to a ray tracing Application Programming Interface (API).
7. The method of claim 1, wherein the information value associated with each primitive includes at least one of a Surface Area Heuristic (SAH) value, an opaqueness value, or a density value.
2. The method of claim 1, wherein each respective information value associated with each primitive includes at least one of a Surface Area Heuristic (SAH) value, an opaqueness value, or a density value.
8. The method of claim 1, wherein each respective information value associated with each primitive includes at least one of an area value, a distance value between each respective primitive and a camera associated with the scene object, or a level-of-detail (LOD) value.
3. The method of claim 1, wherein each respective information value associated with each primitive includes at least one of an area value, a distance value between each respective primitive and a camera associated with the scene object, or a level-of-detail (LOD) value.
9. The method of claim 1, wherein each respective information value associated with each primitive is included as an entry in a render list associated with the scene object.
4. The method of claim 1, wherein each respective information value associated with each primitive is included as an entry in a render list associated with the scene object.
10. The method of claim 1, wherein a
sort order based on the plurality of sorting parameter values is a decreasing order based on the sorting parameter value associated with each node.
12. The method of claim 1, wherein the sort order is a decreasing order based on each respective sorting parameter value associated with each respective node of the two or more nodes.
Each bracket of method claims 1, 7-10, and apparatus claims 11, 17-20 are rejected on the ground of nonstatutory double patenting as being unpatentable over claims 5+8, 5+8+2, 5+8+3, 5+8+4, 5+8+12 of U.S. Patent No. 12,249,021. Although the claims at issue are not identical, they are not patentably distinct from each other because the claims of the instant application are obvious variant of the corresponding ones of the US Patent No. 12,249,021. Furthermore, the scopes of the claims on the instant application are also met and encompassed by the corresponding ones of the Patent No. 12,249,021.
The apparent difference between the conflicting claims mainly arise from the style of limitation recitation and relative placement of conflicting elements within the claims’ body. The conflicting claims are furnished above in a table with similar terms arranged side-by-side as much as possible. Limitations not found in the instant application are e.g., using an Application Programming Interface (API), and determining, using a functional computation as highlighted above. However, such apparent extraneous limitations recited in claim 1 of the instant application are found in claims 5 and 8 respectively.
Other limitations like, “sorting parameter values for a plurality of nodes in the hierarchical acceleration data structure, the plurality of sorting parameter values including a sorting parameter value for each node of the plurality of nodes,” in the instant applicant is met and encompassed in scope by limitation, “sorting parameter value determined for each respective node of the two or more nodes” as an obvious variant, since, the recitation in the instant Applicant is written in a verbose format with respect to the Patent.
Apparatus claims 11, 17-20, of the instant application is shown conflicting to respective method claims of the Patent. This is considered an obvious analysis to one of ordinary skill in the art before the effective filing date of the claimed invention (AIA ), because, apparatus performs the method in question and thus they are considered substantively similar.
Claim Rejections - 35 USC § 103
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 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.
Claim(s) 1, 3-8, and 10-11, 13-18, 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Thiago et al. (Ize, Thiago, and Charles Hansen. "RTSAH traversal order for occlusion rays." Computer Graphics Forum. Vol. 30. No. 2. Oxford, UK: Blackwell Publishing Ltd, 2011, hereinafter Thiago. Document is part of IDS provided by applicant) in view of Broome et al (US 20220254088 A1, hereinafter Broome).
Regarding claim 1, Thiago discloses a method of ray tracing (Abstract, Introduction), the method comprising:
obtaining a hierarchical acceleration data structure, the hierarchical acceleration data structure including a plurality of primitives of a scene object (We accelerate the finding of occluders in tree based acceleration, Abstract. Occlusion rays can make up a significant contribution of the ray budget of complex scenes, Introduction. The expected cost of intersecting a ray with a scene using a tree based acceleration structure such as a general BSP tree (and by extension a kd-tree), or BVH can be approximately computed as the cost of all the primitive-ray intersection tests performed plus the cost of all the tree traversal steps performed by the ray, page 298. Col. 1, section 2.1, ¶1);
obtaining, We derive the Ray Termination SAH (RTSAH) by extending the SAH to assume that each node has a continuous visibility function, V., Page 298, Col. 2, 3. RTSAH, ¶1);
determining, using a functional computation, a plurality of sorting parameter values for a plurality of nodes in the hierarchical acceleration data structure, the plurality of sorting parameter values including a sorting parameter value for each node of the plurality of nodes (…using the RTSAH to determine which child node a ray should traverse first instead of the traditional choice of traversing the near node before the far node, Abstract.
We derive the Ray Termination SAH (RTSAH) by extending the SAH to assume that each node has a continuous visibility function, V- See detailed algorithm in §3 RTSAH, eqns. 3-8, page 298),
wherein the sorting parameter value for a node is based on information values associated with primitives in a sub-tree of the node (Determining first node implies determining order of traversal amongst child nodes. Child nodes are located in the same hierarchical level. See sections 2.1, 3, 4.1 for sorting order of nodes based on RTSAH and opacity of the primitives (section 4.1). Information value could be SAH and/or opacity, while parameters could be understood as Vnode and it’s constituents which are eventually derived from SAH and opacity values. See eqns. 3-8.
We accomplish this by developing a novel cost metric for occlusion-ray traversal through a tree, similar to the surface area heuristic (SAH), that gives the expected cost for terminating traversal if a ray enters that node, Introduction ¶3); and
traversing the hierarchical acceleration data structure in association with the plurality of sorting parameter values for the plurality of nodes in the hierarchical acceleration data structure(Title, abstract, section §3 RTSAH).
Thiago is not found disclosing expressly that information value associated with each primitive are obtained using an Application Programming Interface (API).
However, Broome discloses, graphics processing system 600 comprising a modified tiling engine 602 receiving inputs from a primitive block generator 604 and an application program interface (API) 612 (¶0089).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention (AIA ) to modify the invention of Thiago with the teaching of Broome of tiling engine receiving input from a primitive block generator and an API such that, information value in terms of Probabilities Pij, cost Cl, Cr, Cnode, transparency value V, etc., can be provided to the RTSAH traversal order engine of Thiago through an API so that eventual Vnode and Cnode values can be calculated according to equations 7 & 8, to obtain, information value associated with each primitive are obtained using an Application Programming Interface (API), because, combining prior art elements ready to be improved according to known method to yield predictable results is obvious.
Regarding claim 3, Thiago in view of Broome discloses the method of claim 1, wherein traversing the hierarchical acceleration data structure in association with the plurality of sorting parameter values comprises determining an updated hierarchical acceleration data structure that includes the same nodes but reordered based on the plurality of sorting parameter values (determining traversal order using RTSAH is understood as determining an updated hierarchical acceleration data structure that includes the same nodes but reordered based on the plurality of sorting parameter values – such as parameters like Probabilities Pij, cost Cl, Cr, Cnode, transparency value V, etc.
Also, updating nodes based on low pre-processing time is implemented according to section §5.1, ¶2-3).
Regarding claim 4, Thiago in view of Broome discloses the method of claim 3, except, wherein the traversing is based on a predetermined traversal technique without using the plurality of sorting parameter values.
However, in the background section (§2 Background) Thiago discloses – for radiance rays it is well understood that traversing nodes in a front to back order is ideal. For occlusion rays it is not as clear with researchers differing on the appropriate strategy.
Smits claims that the front to back ordering did not matter for occlusion rays and to simply traverse it in a depth first order where the left subtree is always traversed first and then followed by the right subtree [Smi98]. Boulos on the other hand disagreed and claims that nodes should be traversed front to back just as with radiance rays [BH10] [section §2, last ¶]. In section §6 Limitations, Thiago discloses, Any optimized traversal
ordering can only accelerate completely occluded occlusion rays. For areas or scenes that are predominantly radiance rays or unoccluded occlusion rays, there is little work that can be accelerated and so of course our method will see only a minor speedup [see page 303, Col. 1, ¶1].
Based on the disclosures of Smits and/or Boulos, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention (AIA ) to perform a default, predetermined, font-to-back depth first search traversal of the hierarchical acceleration data structure at the beginning of ray tracing operation when parameters of RTSAH algorithm is yet to be calculated and/or also when rays in question to be processed are radiance rays, to obtain, wherein the traversing is based on a predetermined traversal technique without using the plurality of sorting parameter values, because, Thiago discloses that for radiance rays front to back depth first search is ideal and provides better results, and also in many occlusion rays as well [especially when opacity value V is neither 0 or 1, see section §3 RTSAH, ¶1], per Smits’ disclosure, occlusion rays also does not necessarily perform better than default front to back DFS algorithm.
Regarding claim 5, Thiago in view of Broome discloses the method of claim 4, wherein the predetermined traversal technique is a depth-first search (DFS) traversal (Thiago, section §2, last ¶).
Regarding claim 6, Thiago in view of Broome discloses the method of claim 1, wherein traversing the hierarchical acceleration data structure in association with the plurality of sorting parameter values comprises prioritizing visits to nodes of the hierarchical acceleration data structure based on the plurality of sorting parameter values (Thiago teaches deriving the Ray Termination Surface Area Heuristic (RTSAH) cost model for traversing an occlusion ray through a tree and “using the RTSAH to determine which child node a ray should traverse first instead of the traditional choice of traversing the near node before the far node” (Abstract). Thiago further teaches traversing the child having the lowest calculated RTSAH cost first – Introduction; §3, RTSAH. See other parameters for prioritizing which node to traverse first based on Cnode in eqn. 5, LeftFirst and rightFirst of eqns. 3-4. Also Vnode in eqn. 7 indicates for inner nodes which node should be prioritize for first traversal [or sorting order]).
Regarding claim 7, Thiago in view of Broome discloses the method of claim 1, wherein the information value associated with each primitive includes at least one of a Surface Area Heuristic (SAH) value (Title Abstract, RTSAH), an opaqueness value (section §3, ¶1, page 298), or a density value.
Regarding claim 8, Thiago in view of Broome discloses the method of claim 1, wherein each respective information value associated with each primitive includes at least one of an area value (We accomplish this by developing a novel cost metric for occlusion-ray traversal through a tree, similar to the surface area heuristic (SAH), that gives the expected cost for terminating traversal if a ray enters that node, Introduction ¶3), a distance value between each respective primitive and a camera associated with the scene object, or a level-of-detail (LOD) value (RTSAH could likely be modified to work with these LOD methods and would of course directly handle the geometry that does not use the LOD optimization, 2. Background, ¶2).
Regarding claim 10, Thiago in view of Broome discloses the method of claim 1, wherein a sort order based on the plurality of sorting parameter values is a decreasing order based on the sorting parameter value associated with each node (Since we now have an expected cost for traversing the left child node or right child node first, we can lower the expected cost of occlusion rays by first entering the child node that gives a lower overall cost. We use the costs from Equations 3 and 4 to determine which to traverse first. Note that this can be simplified to only comparing the values in the Min
statement of Equation 6, which in the case of the BSP tree, can be a much simpler comparison as seen in Equation 8. – section §4, ¶1).
Regarding claim 11, Thiago discloses an apparatus for ray tracing (Title, Abstract), the apparatus comprising:
obtain a hierarchical acceleration data structure, the hierarchical acceleration data structure including a plurality of primitives of a scene object; obtain, using an Application Programming Interface (API), an information value associated with each primitive in the plurality of primitives; determine, using a functional computation, a plurality of sorting parameter values for a plurality of nodes in the hierarchical acceleration data structure, the plurality of sorting parameter values including a sorting parameter value for each node of the plurality of nodes, wherein the sorting parameter value for a node is based on information values associated with primitives in a sub-tree of the node; and traverse the hierarchical acceleration data structure in association with the plurality of sorting parameter values for the plurality of nodes in the hierarchical acceleration data structure (see substantively similar claim 1 rejection above).
Although likely implicit, Thiago is not found disclosing explicitly the limitation of,
at least one memory; and at least one processor coupled to the at least one memory, the at least one processor configured to perform the aforementioned operations.
However, Broome in another aspect discloses that a ray tracing apparatus comprises at least one memory; and at least one processor coupled to the at least one memory, the at least one processor configured to perform ray tracing operations (¶0033 -0036, ¶0041-0043, ¶0160-0163, claim 19).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention (AIA ) to implement the apparatus for ray tracing of Thiago that comprises, at least one memory; and at least one processor coupled to the at least one memory, the at least one processor configured to perform the ray tracing operations described in Thiago, as disclosed in Broome, because, implementing computer implemented operations using a processor-memory system is a widely used, yielding predictable results.
Regarding CRM claim(s) 13-18, and 20 although wording is different, the material is considered substantively equivalent to the method claim(s) 3-8, and 10 respectively as described above.
Claims 9, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Thiago in view of Worcester et al (US 20170221177 A1, hereinafter Worcester).
Regarding claim 9, Thiago in view of Broome discloses the method of claim 1, except, wherein each respective information value associated with each primitive is included as an entry in a render list associated with the scene object.
However, Worcester discloses in a graphics processing system comprising: a tiling unit configured to tile a first view of a scene into a plurality of tiles and generate a list of primitives associated with each tile; a processing unit configured to identify a first subset of the tiles that are each associated with at least a predetermined number of primitives in dependence on the list; and a rendering unit configured to render to a render target each of the identified tiles (abstract). The subset is associated with parts of the scene that are visible in a second view (¶0014).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention (AIA ) to modify the invention of Thiago with the teaching of Worcester of generating rendering list of primitives according to visibility information associated with the scene object, because, combining prior art elements ready to be improved according to known method to yield predictable results is obvious.
Regarding CRM claim(s) 19 although wording is different, the material is considered substantively equivalent to the method claim(s) 9 as described above.
Allowable Subject Matter
Claim(s) 2, and 12 is/are objected to as being dependent upon a rejected base claim but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter:
Regarding claims 2 & 12, prior arts of record taken alone or in combination fails to reasonably disclose or suggest,
obtain(ing), using the API, an indication of the functional computation, wherein the functional computation is selected, from a plurality of functional computations, to determine the plurality of sorting parameter values based on obtaining the indication.
Conclusion
The prior and/or pertinent art(s) made of record and not relied upon is considered pertinent to applicant's disclosure, are:
Apodaca et al. (US 11501484 B2) discloses, apparatus and method for acceleration data structure refit. For example, one embodiment of an apparatus comprises: a ray generator to generate a plurality of rays in a first graphics scene; a hierarchical acceleration data structure generator to construct an acceleration data structure comprising a plurality of hierarchically arranged nodes including inner nodes and leaf nodes stored in a memory in a depth-first search (DFS) order; traversal hardware logic to traverse one or more of the rays through the acceleration data structure; intersection hardware logic to determine intersections between the one or more rays and one or more primitives within the hierarchical acceleration data structure; a node refit unit comprising circuitry and/or logic to read consecutively through at least the inner nodes in the memory in reverse DFS order to perform a bottom-up refit operation on the hierarchical acceleration data structure.
DOYLE et al. (US 20200211147 A1) discloses an apparatus comprising a sorting unit to sort primitives of a graphics image, the primitives to be grouped, each group to form a first level node of a hierarchical acceleration structure; a parallel reconfigurable clustering array to construct the hierarchical acceleration structure, the parallel reconfigurable clustering array comprising a plurality of processing clusters, each cluster comprising: parallel efficiency analysis circuitry to evaluate different groupings of the first level nodes for a next level of the hierarchical acceleration structure to determine efficiency values for the different groupings; and node merge circuitry to merge the first level nodes based on the efficiency values to form second level nodes.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NURUN FLORA whose telephone number is (571)272-5742. The examiner can normally be reached M-F 9:30 am -5:00 pm.
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, Jason Chan can be reached at (571) 272-3022. 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.
/NURUN FLORA/Primary Examiner, Art Unit 2619
