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 .
Response to Amendment
Applicant’s submission filed 1/14/2026 has been entered. The claims 1, 10, 12 and 20 have been amended. The claims 1-20 are pending in the current application.
Response to Arguments
Applicant’s arguments filed 1/14/2026 with respect to the amended claim 1 and similar claims have been considered but are moot in view of the new ground(s) of rejection set forth in the current Office Action.
Applicant's arguments filed 1/14/2026 have been fully considered but they are not persuasive.
In Remarks, applicant made general allegation by individually attacking the Wald ’30 reference and argued in essence with the new claim limitation “when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive”.
However, Wald ‘030 teaches the new claim limitation: when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (Wald ‘030 teaches at FIGS. 3A-3C and Paragraph 0052-0057 that when a group bounding box 336A does not bound the respective primitive 224F, expanding the group bounding box 336A for the selected group to be an expanded group 352A so as to bound the respective primitive 224F.
Wald ‘030 teaches at FIGS. 3A-3D and Paragraph 0052-0057 when the group bounding box 352B for the selected group does not bound the respective primitive 224C/224D/224E/224F/224G, expanding the group bound box 352B to the group bounding box 330 for the selected group so that the group bounding box 330 may bound the respective primitive 224C/224D/224E/224F/224G).
In Remarks, applicant made general allegation by individually attacking the Kern reference and argued in essence with the new claim limitation “when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive”.
However, Kern teaches the new claim limitation: when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (Kern teaches at FIG. 4 and Paragraph 0032-0035 that when a group bounding box represented by the node N6 does not bound the respective primitive O7/O8, expanding the group bounding box N6 to N3 for the selected group so that N3 bounds the respective primitive O7/O8).
In Remarks, applicant made general allegation by individually attacking the Dietrich reference and argued in essence with the new claim limitation “when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive”.
Dietrich teaches the new claim limitation: when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 that when a group bounding box for the selected group 2 does not bound the respective primitive 210/211, expanding the group bounding box for the selected group as the new group 1 so that the new bounding box 250 bound the respective primitive 210/211).
In Remarks, applicant made general allegation by individually attacking the Benithin reference and argued in essence with the new claim limitation “when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive”.
Benithin teaches the new claim limitation: when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (Benithin teaches at FIGS. 20-21 and Paragraph 0217-0221 that when a group bounding box for the selected group 2002A does not bound the respective primitive 2014/2015/2016/2017, expanding the group bounding box for the selected group as the new group 2000 so that the new bounding box 2000 bound the respective primitive 2014/2015/2016/2017).
Finally, Gupta teaches the new claim limitation: when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (
Gupta teaches at FIGS. 2A-2B and Paragraph 0047-0048 when a group bounding box 256b for the selected group 262b does not bound the respective primitive 252c/252d/252e, expanding the group bounding box 256b for the selected group 262b to be the expanded bounding box 256a so as to bound the respective primitive 252c/252d/252e.
Gupta teaches at FIGS. 2A-2B and Paragraph 0047-0048 constructing bounding boxes 256a-256e by adding primitives 252a-252e to the one or more groups 256a-256e. Gupta teaches that bounding boxes have a minimized area or volume within which all points of the enclosed primitives may lie. Gupta teaches comparing a position of the respective primitive 252a with a position of a group 256b that the bounding box 256b encloses the primitive 252a. Gupta teaches selecting a group 256b to add the respective primitive 252a to based on the comparison of all points of the enclosed primitive and the bounding box 256b and selecting the bounding box 256b to add the primitive 252a to).
See also any of the newly cited references.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
The claim 1 recites “generating, for each group, a group bounding box that bounds the primitives added to the respective group;
wherein the method comprises, for each primitive of the set of primitives,
comparing a position of the respective primitive with a position of any group currently under construction;
Selecting a group to add the respective primitive to based on the comparison;
adding the respective primitive to the selected group; and
when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive.”
The claim 1 recites for each primitive “adding the respective primitive to the selected group” implicitly requires that the group bounding box for the selected group bounds/overlaps the respective primitive (or the primitive bounding box) according to applicant’s specification. Applicant’s specification discloses at Paragraph 0123 each time a primitive is added to a group, a group bounding box for the group may be updated so as to bound the primitive added to the group (as well as any primitives already added to the group). Applicant’s specification discloses at Paragraph 0128 that when it is determined that a primitive bounding box for a primitive overlaps a group bounding box for two or more groups currently under construction, before selecting a group and adding the primitive to the selected group. Nowhere in applicant’s specification discloses that the respective primitive added to the group bounding box would not be enclosed within the group bounding box. Nowhere in the specification discloses that the group bounding box to which the respective primitive is added does not overlap/bound the respective primitive. Applicant may mean a group bounding box for the selected group does not bound another primitive as opposed to the respective primitive. However, the looping for each primitive is meant for the same respective primitive in the instant claim invention.
Additionally, “generating, for each group, a group bounding box that bounds the primitives added to the respective group” requires that the respective primitive added to the selected group is bounded by the group bounding box for the selected group in the adding step positively recited in the claim 1.
According to applicant’s specification, the group bounding box for the selected group is updated to bound the primitive added to the group in the step of adding. After the adding step, the group bounding box for the same selected group cannot be said not to bound the respective primitive while the respective primitive is bounded by the group bounding box in the recited generating and adding steps.
However, the claim 1 then recites the new claim limitation for each primitive “when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive” is contradictory with the adding step. The new claim limitation requires that the group bounding box for the selected group be not bound the respective primitive while the step of adding positively requires that the respective primitive be bounded/overlapped by the group bounding box. In a single claim, the same group bounding box cannot simultaneously bounds the same respective primitive and does not bound the same respective primitive. The new claim limitation is contradictory with the existing claim limitation. Clarification is required.
The claims 2-11 are dependent upon the claim 1 and are rejected due to their dependency on the claim 1. The base claim 12 is subject to the same rationale of rejection as the base claim 1. The claims 13-20 are dependent upon the claim 12 and are rejected due to their dependency on the claim 12.
Claim Rejections - 35 USC § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of the first paragraph of pre-AIA 35 U.S.C. 112:
The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor of carrying out his invention.
Claims 1-20 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. The claim(s) contains subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention.
The claim 1 recites “generating, for each group, a group bounding box that bounds the primitives added to the respective group;
wherein the method comprises, for each primitive of the set of primitives,
comparing a position of the respective primitive with a position of any group currently under construction;
Selecting a group to add the respective primitive to based on the comparison;
adding the respective primitive to the selected group; and
when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive.”
The claim 1 recites for each primitive “adding the respective primitive to the selected group” implicitly requires that the group bounding box for the selected group bounds/overlaps the respective primitive (or the primitive bounding box) according to applicant’s specification. Applicant’s specification discloses at Paragraph 0123 each time a primitive is added to a group, a group bounding box for the group may be updated so as to bound the primitive added to the group (as well as any primitives already added to the group). Applicant’s specification discloses at Paragraph 0128 that when it is determined that a primitive bounding box for a primitive overlaps a group bounding box for two or more groups currently under construction, before selecting a group and adding the primitive to the selected group. Nowhere in applicant’s specification discloses that the respective primitive added to the group bounding box would not be enclosed within the group bounding box. Nowhere in the specification discloses that the group bounding box to which the respective primitive is added does not overlap/bound the respective primitive. Applicant may mean a group bounding box for the selected group does not bound another primitive as opposed to the respective primitive. However, the looping for each primitive is meant for the same respective primitive in the instant claim invention.
Additionally, “generating, for each group, a group bounding box that bounds the primitives added to the respective group” requires that the respective primitive added to the selected group is bounded by the group bounding box for the selected group in the adding step positively recited in the claim 1.
According to applicant’s specification, the group bounding box for the selected group is updated to bound the primitive added to the group in the step of adding. After the adding step, the group bounding box for the same selected group cannot be said not to bound the respective primitive while the respective primitive is bounded by the group bounding box in the recited generating and adding steps.
However, the claim 1 then recites the new claim limitation for each primitive “when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive” is contradictory with the adding step which requires the group bounding box for the selected group bounds the respective primitive as the respective primitive was added to the selected group.
The new claim limitation requires that the group bounding box for the selected group be not bound the respective primitive (which implicitly means that the respective primitive was not added to the selected group) while the step of adding positively requires that the respective primitive be bounded/overlapped by the group bounding box as the respective primitive was added to the selected group. In a single claim, the same group bounding box cannot simultaneously bounds the same respective primitive and does not bound the same respective primitive. The new claim limitation also requires that the respective primitive was not added to the selected group, in contrary to the claimed adding step.
Accordingly, applicant’s specification failed to disclose that the group bounding box does not bound the respective primitive when the respective primitive was added to the selected group.
To comply with the “written description” requirement of 35 U.S.C. § 112, first paragraph, an applicant must convey with reasonable clarity to those skilled in the art that, as of the filing date sought, he or she was in possession of the invention. The invention is, for purposes of the Application/Control Number: 18/461,873 Page 25 Art Unit: 2617 “written description” inquiry, whatever is now claimed. Vas-Cath. Inc, v. Mahurkar. 935 F.2d 1555, 1563-64, 19 USPQ2d 1111, 1117 (Fed. Cir. 1991). For purposes of written description, one shows “possession” by descriptive means such as words, structures, figures, diagrams, and formulas that fully set forth the claimed invention. Lockwood v. American Airlines. Inc.. 107 F.3d 1565, 1572, 41 USPQ2d 1961, 1966 (Fed. Cir. 1997). Such descriptive means is not found in the disclosure for the inventions of claim 1.
The claims 2-11 are dependent upon the claim 1 and are rejected due to their dependency on the claim 1. The base claim 12 is subject to the same rationale of rejection as the base claim 1. The claims 13-20 are dependent upon the claim 12 and are rejected due to their dependency on the claim 12.
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.
Claims 1-9 and 11-19 are rejected under 35 U.S.C. 103 as being unpatentable over Wal US-PGPUB No. 2025/0308030 (hereinafter Wald ‘030) in view of
Benthin et al. US-PGPUB No. 2018/0300939 (hereinafter Benthin);
Dietrich JR. US-PGPUB No. 2025/0104330 (hereinafter Dietrich);
Kern et al. US-PGPUB No. 2025/0200864 (hereinafter Kern);
Oldcorn et al. US-PGPUB No. 2023/0099806 (hereinafter Oldcorn);
Gupta et al. US-PGPUB No. 2024/0104824 (hereinafter Gupta).
Re Claim 1:
Wald ‘030 teaches a method of operating a tile-based graphics processor that is operable to generate a render output by building a hierarchy of bounding boxes to be used to identify primitives to process to generate a rendering tile of the render output; the method comprising
building at least one level of a hierarchy of bounding boxes by:
constructing one or more groups of primitives by adding primitives of a set of primitives to the one or more groups (
Wald ’30 teaches at FIGS. 3A-3B and Paragraph 0052-0054 constructing one or more groups 352A and 352B by adding primitives of a set of primitives {224A-224G} to the one or more groups 352A and 352B); and
generating, for each group, a group bounding box that bounds the primitives added to the respective group (Wald ‘030 teaches at FIGS. 3A-3B and Paragraph 0052-0054 generating for each group 352A/352B, a group bounding box that bounds the primitives added to the respective group. FIG. 3B shows the group bounding box 352B bounds the primitives 224A and 224B and the group bounding box 352A bounds the primitives 224C-224G);
wherein the method comprises, for each primitive of the set of primitives:
comparing a position of the respective primitive with a position of any group currently under construction (
Wald ’30 teaches at FIG. 3C and Paragraph 0053-0057 comparing a position of the respective primitive 224B with a position of any group currently under construction (the bounding shape 336A for the group node 134A, the bounding shape 336B for the group node 134B.
Wald ’30 teaches at FIGS. 3A-3C and Paragraph 0054-0057 that comparing a position of the primitive 224A/224B with a position of the group 352B currently under construction according to the bins information of the primitive 224A/224B corresponding to the node 132B for the bounding shape 352B (a node 132B of the partitioning 120 may include one or more bounding shape coordinates and/or dimensions indicating one or more bounding shapes that encloses one or more spatial elements 224A/224B);
selecting a group to add the respective primitive to based on the comparison;
adding the respective primitive to the selected group (
Wald ’30 teaches at FIG. 3C selecting a group 134D (336D) to add the respective primitive 224B to based on the comparison and adding the respective primitive 224B to the selected group for the bounding box 336D.
Wald ’30 teaches at FIGS. 3A-3C and Paragraph 0054-0057 that comparing a position of the primitive 224A/224B with a position of the group 352B currently under construction according to the bins information of the primitive 224A/224B corresponding to the node 132B for the bounding shape 352B (a node 132B of the partitioning 120 may include one or more bounding shape coordinates and/or dimensions indicating one or more bounding shapes that encloses one or more spatial elements 224A/224B. As shown in FIGS. 3A-3C, the group 352B is selected to add the spatial elements 224A/224B based on the comparison of the coordinates and/or dimensions of the bounding shape 352B with the spatial elements 224A/224B.
Wald ’30 teaches at FIGS. 3A-3E and Paragraph 0054 adding the primitives within the bounding boxes 336C and 336D to the group 352B. Wald ’30 teaches at Paragraph 0063 that the bin assignor 106 ma be used to assign the spatial elements 224C, 224D, 224E and 224F to the bins 122B and the node manager 102 use the assignments to the bins 122B to determine the portion 120B of the partitioning 120.
Wald ‘030 teaches at Paragraph 0075 that the dimensions and/or size for the spatial elements 224C, 224D, 224E, and/or 224F may correspond to the bounding shape 336A and/or bounding shapes 340C, 340D, 340E, and/or 340F); and
when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (Wald ‘030 teaches at FIGS. 3A-3C and Paragraph 0052-0057 that when a group bounding box 336A does not bound the respective primitive 224F, expanding the group bounding box 336A for the selected group to be an expanded group 352A so as to bound the respective primitive 224F.
Wald ‘030 teaches at FIGS. 3A-3D and Paragraph 0052-0057 when the group bounding box 352B for the selected group does not bound the respective primitive 224C/224D/224E/224F/224G, expanding the group bound box 352B to the group bounding box 330 for the selected group so that the group bounding box 330 may bound the respective primitive 224C/224D/224E/224F/224G).
Kern teaches a method of operating a tile-based graphics processor that is operable to generate a render output by building a hierarchy of bounding boxes to be used to identify primitives to process to generate a rendering tile of the render output; the method comprising
building at least one level of a hierarchy of bounding boxes by:
constructing one or more groups of primitives by adding primitives of a set of primitives to the one or more groups (
Kern teaches at FIG. 4 and Paragraph 0032-0035 constructing one or more groups of primitives O5-O6 to the one or more group N6/N3/N1 with the nodes having associated bounding boxes wherein the node N6 represent the N6 bounding box node and N6 corresponds a bounding box in the spatial representation 402.
Kern teaches at FIG. 4 and Paragraph 0032-0035 that the groups N1-N7 of primitives are constructed by adding primitives O1-O8 to the one or more groups N1-N7. For example, a group bounding box N7 is generated by adding the primitives O7 and O8 to the group N7); and
generating, for each group, a group bounding box that bounds the primitives added to the respective group (
Kern teaches at FIG. 4 and Paragraph 0032-0035 generating for each group N1-N7 a group bounding box that bounds the primitives O1-O8 added to the respective group. For example, O5 and O6 are added to the respective groups N1/N3/N6.
Kern teaches at FIG. 4 and Paragraph 0032-0035 that the groups N1-N7 of primitives are constructed by adding primitives O1-O8 to the one or more groups N1-N7. For example, a group bounding box N7 is generated by adding the primitives O7 and O8 to the group N7);
wherein the method comprises, for each primitive of a set of primitives:
comparing a position of the respective primitive with a position of any group currently under construction (
Kern teaches at FIG. 4 and Paragraph 0032-0035 comparing a position of the respective primitive O5/O6 with a position of any group N1/N3/N6 by traversal of a ray intersection.
Kern teaches at FIG. 4 and Paragraph 0032-0035 comparing a position of the primitive O7 with a position of the group N7 currently under construction. Kern teaches at Paragraph 0034 that O5 is intersection-tested again N1 which is determined that O5 is not in N1 and the intersection test continued to determine that O5 is in N6 but not in N7 based on the spatial position of the O5 and the spatial position of N6/N7);
selecting a group to add the respective primitive to based on the comparison; adding the primitive to the selected group (
Kern teaches at FIG. 4 and Paragraph 0032-0035 comparing a position of the respective primitive O5/O6 with a position of any group N1/N3/N6 by traversal of a ray intersection. Kern teaches selecting a group N1/N3/N6 to add the primitive O5/O6 based on the comparison and adding the primitive O5/O6 to the selected group N1/N3/N6.
Kern teaches at FIG. 4 and Paragraph 0032-0035 comparing a position of the primitive O7 with a position of the group N7 currently under construction. Kern teaches at Paragraph 0034 that O5 is intersection-tested again N1 which is determined that O5 is not in N1 and the intersection test continued to determine that O5 is in N6 but not in N7 based on the spatial position of the O5 and the spatial position of N6/N67. Selecting the group N6 to add the primitive O5 to the group N6 based on the comparison (intersection test) and adding the primitive O5 to the selected group N6); and
when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (Kern teaches at FIG. 4 and Paragraph 0032-0035 that when a group bounding box represented by the node N6 does not bound the respective primitive O7/O8, expanding the group bounding box N6 to N3 for the selected group so that N3 bounds the respective primitive O7/O8).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Kern’s intersection test for comparing the position of the primitive with the position of each group to have a group to add the primitive to have been incorporated into Wald ‘030’s construction of bounding box hierarchies to have determined the correspondence between each primitive and each group. One of the ordinary skill in the art would have been motivated to have constructed bounding box hierarchies to have efficiently rendered the scene divided into bounding boxes with a plurality of primitives.
Dietrich teaches a method of operating a tile-based graphics processor that is operable to generate a render output by building a hierarchy of bounding boxes to be used to identify primitives to process to generate a rendering tile of the render output; the method comprising
building at least one level of a hierarchy of bounding boxes by:
constructing one or more groups of primitives by adding primitives of a set of primitives to the one or more groups (
Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 constructing one or more groups of primitives (groups 1/2/3 of FIG. 4) by adding primitives D-F to group 3, adding primitives A and B to group 2 and adding primitives A-F to group 1.
Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 constructing a bounding volume hierarchy for a simple scene 201 by adding primitives 210-215 to the bounding volume 220-225. An aggregated proximity-based bounding volume 230 includes primitives 210 and 211 while a second aggregated proximity-based bounding volume 235 includes primitives 213-215); and
generating, for each group, a group bounding box that bounds the primitives added to the respective group (Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 constructing a bounding volume hierarchy for a simple scene 201 by adding primitives 210-215 to the bounding volume 220-225. An aggregated proximity-based bounding volume 230 includes primitives 210 and 211 while a second aggregated proximity-based bounding volume 235 includes primitives 213-215);
wherein the method comprises, for each primitive of a set of primitives:
comparing a position of the respective primitive with a position of any group currently under construction (
Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 constructing one or more groups of primitives (groups 1/2/3 of FIG. 4) by adding primitives D-F to group 3, adding primitives A and B to group 2 and adding primitives A-F to group 1.
Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 comparing a position of the respective primitive A with a position of any group 1/2/3 currently under construction.
Dietrich teaches at Paragraph 0042 that each node stores a bounding box of the primitives and as a ray traverses through the tree during a ray cast rendering process, any time the ray does not encounter a node’s bounding volume, the subtree beneath that node can be skipped and at Paragraph 0046 that an IAS may be dynamically modified based on a respective quantity of rays in a subset of such rays that are determined to have encountered (or, alternatively, failed to encounter) at least one rendering primitive included within each respective bounding volume during rendering of an earlier frame for that 3D scene.
Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 constructing a bounding volume hierarchy for a simple scene 201 by adding primitives 210-215 to the bounding volume 220-225. An aggregated proximity-based bounding volume 230 includes primitives 210 and 211 while a second aggregated proximity-based bounding volume 235 includes primitives 213-215);
selecting a group to add the respective primitive to based on the comparison; adding the primitive to the selected group (
Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 selecting a group 2 to add the primitive A (primitive 210) to based on the comparison of the position of the primitive bounding box 220 and the group bounding box 230.
Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 constructing a bounding volume hierarchy for a simple scene 201 by adding primitives 210-215 to the bounding volume 220-225. An aggregated proximity-based bounding volume 230 includes primitives 210 and 211 while a second aggregated proximity-based bounding volume 235 includes primitives 213-215);
when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (Dietrich teaches at FIGS. 2-4 and Paragraph 0039-0050 that when a group bounding box for the selected group 2 does not bound the respective primitive 210/211, expanding the group bounding box for the selected group as the new group 1 so that the new bounding box 250 bound the respective primitive 210/211).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Dietrich’s comparing the position of the primitive with the position of each group based on proximity to add the primitive to a group into Wald ‘030’s construction of bounding box hierarchies to have determined the correspondence between each primitive and each group based on proximity aggregation of the bounding boxes of the primitives. One of the ordinary skill in the art would have been motivated to have constructed bounding box hierarchies to have efficiently rendered the scene divided into bounding boxes with a plurality of primitives.
Benthin teaches a method of operating a tile-based graphics processor that is operable to generate a render output by building a hierarchy of bounding boxes to be used to identify primitives to process to generate a rendering tile of the render output; the method comprising
building at least one level of a hierarchy of bounding boxes by:
constructing one or more groups of primitives by adding primitives of a set of primitives to the one or more groups (Benthin teaches at FIG. 20-21 and Paragraph 0217-0221 constructing one or more groups 2000A/2000B of primitives 2010-2017 by adding primitives 2010-2017 to the one or more groups 2002A/2002B.
Benthin teaches at Paragraph 0217 that a first object BVH is represented by boxes with solid lines 2001, a second object BVH is represented by boxes with large dotted lines 2002 and a top-level BVH is represented by boxes with small dotted boxes 2000. The large solid box 2001A bounding primitives 2010-2015 and the large dotted line box 2002A bounding primitives 2012-2017 spatially overlap (i.e., both bound primitives 2012-2015).); and
generating, for each group, a group bounding box that bounds the primitives added to the respective group (Benthin teaches at FIGS. 20-21 and Paragraph 0217-0221 generating a group bounding box 2000A/2000B that bounds the primitives 2010-2017 added to the respective group.
Benthin teaches at Paragraph 0217 that a first object BVH is represented by boxes with solid lines 2001, a second object BVH is represented by boxes with large dotted lines 2002 and a top-level BVH is represented by boxes with small dotted boxes 2000. The large solid box 2001A bounding primitives 2010-2015 and the large dotted line box 2002A bounding primitives 2012-2017 spatially overlap (i.e., both bound primitives 2012-2015));
wherein the method comprises, for each primitive of a set of primitives:
comparing a position of the respective primitive with a position of any group currently under construction (Benthin teaches at FIGS. 20-21 and Paragraph 0217-0221 that comparing a position of the primitive 2010 with a position of any group 2000A/2000B currently under construction);
selecting a group to add the respective primitive to based on the comparison; adding the primitive to the selected group (Benithin teaches at FIGS. 20-21 and Paragraph 0217-0221 selecting a group 2000A to add the primitive 2010 to based on the comparison and adding the primitive 2010 to the selected group 2000A.
Benithin teaches at Paragraph 0218 that new node 2000A is formed around primitives 2010-2013 and new node 2000B is formed around primitives 2014-2017, thereby removing the spatial overlap); and
when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (Benithin teaches at FIGS. 20-21 and Paragraph 0217-0221 that when a group bounding box for the selected group 2002A does not bound the respective primitive 2014/2015/2016/2017, expanding the group bounding box for the selected group as the new group 2000 so that the new bounding box 2000 bound the respective primitive 2014/2015/2016/2017).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Benithin’s determination of spatial overlap between the primitive and each group to have selected a group to add the primitive to have been incorporated into Wald ‘030’s construction of bounding box hierarchies to have determined the correspondence between each primitive and each group. One of the ordinary skill in the art would have been motivated to have constructed bounding box hierarchies to have efficiently rendered the scene divided into bounding boxes with a plurality of primitives.
Gupta teaches a method of operating a tile-based graphics processor that is operable to generate a render output by building a hierarchy of bounding boxes to be used to identify primitives to process to generate a rendering tile of the render output; the method comprising
building at least one level of a hierarchy of bounding boxes by:
constructing one or more groups of primitives by adding primitives of a set of primitives to the one or more groups (
Gupta teaches at FIGS. 2A-2B and Paragraph 0047-0048 constructing bounding boxes 256a-256e by adding primitives 252a-252e to the one or more groups 256a-256e); and
generating, for each group, a group bounding box that bounds the primitives added to the respective group (Gupta teaches at FIGS. 2A-2B and Paragraph 0047-0048 constructing bounding boxes 256a-256e by adding primitives 252a-252e to the one or more groups 256a-256e);
wherein the method comprises, for each primitive of the set of primitives:
comparing a position of the respective primitive with a position of any group currently under construction (
Gupta teaches at FIGS. 2A-2B and Paragraph 0047-0048 constructing bounding boxes 256a-256e by adding primitives 252a-252e to the one or more groups 256a-256e. Gupta teaches that bounding boxes have a minimized area or volume within which all points of the enclosed primitives may lie. Gupta teaches comparing a position of the respective primitive 252a with a position of a group 256b that the bounding box 256b encloses the primitive 252a);
selecting a group to add the respective primitive to based on the comparison;
adding the respective primitive to the selected group (
Gupta teaches at FIGS. 2A-2B and Paragraph 0047-0048 constructing bounding boxes 256a-256e by adding primitives 252a-252e to the one or more groups 256a-256e. Gupta teaches that bounding boxes have a minimized area or volume within which all points of the enclosed primitives may lie. Gupta teaches comparing a position of the respective primitive 252a with a position of a group 256b that the bounding box 256b encloses the primitive 252a. Gupta teaches selecting a group 256b to add the respective primitive 252a to based on the comparison of all points of the enclosed primitive and the bounding box 256b and selecting the bounding box 256b to add the primitive 252a to); and
when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (
Gupta teaches at FIGS. 2A-2B and Paragraph 0047-0048 when a group bounding box 256b for the selected group 262b does not bound the respective primitive 252c/252d/252e, expanding the group bounding box 256b for the selected group 262b to be the expanded bounding box 256a so as to bound the respective primitive 252c/252d/252e.
Gupta teaches at FIGS. 2A-2B and Paragraph 0047-0048 constructing bounding boxes 256a-256e by adding primitives 252a-252e to the one or more groups 256a-256e. Gupta teaches that bounding boxes have a minimized area or volume within which all points of the enclosed primitives may lie. Gupta teaches comparing a position of the respective primitive 252a with a position of a group 256b that the bounding box 256b encloses the primitive 252a. Gupta teaches selecting a group 256b to add the respective primitive 252a to based on the comparison of all points of the enclosed primitive and the bounding box 256b and selecting the bounding box 256b to add the primitive 252a to).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Gupta’s determination of spatial overlap between the primitive and each group to have selected a group to add the primitive to have been incorporated into Wald ‘030’s construction of bounding box hierarchies to have determined the correspondence between each primitive and each group. One of the ordinary skill in the art would have been motivated to have constructed bounding box hierarchies to have efficiently rendered the scene divided into bounding boxes with a plurality of primitives.
Oldcorn teaches a method of operating a tile-based graphics processor that is operable to generate a render output by building a hierarchy of bounding boxes to be used to identify primitives to process to generate a rendering tile of the render output; the method comprising
building at least one level of a hierarchy of bounding boxes by:
constructing one or more groups of primitives by adding primitives of a set of primitives to the one or more groups (
Oldcorn teaches at FIGS 4-6 and Paragraph 0032-0054 constructing groups N1-N7 of primitives O1-O8 such that the bounding boxes are sized to the extents of the triangles enclosed within the bounding boxes); and
generating, for each group, a group bounding box that bounds the primitives added to the respective group (Oldcorn teaches at FIGS. 4-6 and Paragraph 0032-0054 constructing bounding boxes N1-N7 by adding primitives O1-O8 to the one or more groups N1-N7);
wherein the method comprises, for each primitive of the set of primitives:
comparing a position of the respective primitive with a position of any group currently under construction (
Oldcorn teaches at FIGS. 4-6 and Paragraph 0032-0054 constructing bounding boxes N1-N7 by adding primitives O1-O8 to the one or more groups N1-N7 such that the bounding boxes are sized to the extents of the triangles enclosed within the bounding boxes);
selecting a group to add the respective primitive to based on the comparison;
adding the respective primitive to the selected group (
Oldcorn teaches at FIGS. 4-6 and Paragraph 0032-0054 constructing bounding boxes N1-N7 by adding primitives O1-O8 to the one or more groups N1-N7. Oldcorn teaches at Paragraph 0053 that bounding boxes have a minimized area or volume within which all points of the enclosed primitives may lie. Gupta teaches comparing a position of the respective primitive 252a with a position of a group 256b that the bounding box 256b encloses the primitive 252a. Gupta teaches selecting a group N6 to add the respective primitive O5/O6 to based on the comparison of all points of the enclosed primitive and the bounding box N6 and selecting the bounding box N6 to add the primitive O5/O6 to); and
when a group bounding box for the selected group does not bound the respective primitive, expanding the group bounding box for the selected group so as to bound the respective primitive (
Oldcorn teaches at FIGS. 4-6 and Paragraph 0032-0054 when a group bounding box N6 for the selected group {O5, O6} does not bound the respective primitive O7/O8, expanding the group bounding box N6 for the selected group to become the expanded bounding box N3 so as to bound the respective primitive O7/O8).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have incorporated Oldcorn’s determination of spatial overlap between the primitive and each group to have selected a group to add the primitive to have been incorporated into Wald ‘030’s construction of bounding box hierarchies to have determined the correspondence between each primitive and each group. One of the ordinary skill in the art would have been motivated to have constructed bounding box hierarchies to have efficiently rendered the scene divided into bounding boxes with a plurality of primitives.
Re Claim 2:
The claim 2 encompasses the same scope of invention as that of the claim 1 except additional claim limitation that a position of the primitive with a position of a group currently under construction comprises: comparing a primitive bounding box that bounds the primitive with a group bounding box that bounds any primitives already added to the group currently under construction.
However, Kern and Wald ‘030 further teach the claim limitation that a position of the primitive with a position of a group currently under construction comprises: comparing a primitive bounding box that bounds the primitive with a group bounding box that bounds any primitives already added to the group currently under construction (
(Kern teaches at FIG. 4 and Paragraph 0032-0035 comparing a position of the primitive O7 with a position of the group N7 currently under construction. Kern teaches at Paragraph 0034 that O5 is intersection-tested again N1 which is determined that O5 is not in N1 and the intersection test continued to determine that O5 is in N6 but not in N7 based on the spatial position of the O5 and the spatial position of N6/N67.
Wald ‘030 teaches at FIGS. 3A-3E and Paragraph 0063-0075 comparing a primitive bounding box 340C that bounds the primitive with a group bounding box 336A that bounds any primitives already added to the group currently under construction.
Wald ‘030 teaches at Paragraph 0075 that the dimensions and/or size for the spatial elements 224C, 224D, 224E, and/or 224F may correspond to the bounding shape 336A and/or bounding shapes 340C, 340D, 340E, and/or 340F).
Re Claim 3:
The claim 3 encompasses the same scope of invention as that of the claim 2 except additional claim limitation that determining whether the primitive bounding box overlaps a group bounding box for only one group currently under construction; and when it is determined that the primitive bounding box overlaps a group bounding box for only one group currently under construction: adding the primitive to the only one group.
However, Benithin and Wald ‘030 further teach the claim limitation that determining whether the primitive bounding box overlaps a group bounding box for only one group currently under construction; and when it is determined that the primitive bounding box overlaps a group bounding box for only one group currently under construction: adding the primitive to the only one group (
Benithin teaches at FIG. 20 that when it is determined that the primitive bounding box for the primitive 2010 overlaps a group bounding box 2001A currently under construction, adding the primitive 2010 to the only one group 2001A.
Wald ‘030 teaches at FIGS. 3A-3E and Paragraph 0063-0075 comparing a primitive bounding box 340C that bounds the primitive with a group bounding box 330 that bounds any primitives already added to the only one group currently under construction.
Wald ‘030 teaches at Paragraph 0075 that the dimensions and/or size for the spatial elements 224C, 224D, 224E, and/or 224F may correspond to the bounding shape 336A and/or bounding shapes 340C, 340D, 340E, and/or 340F. Wald ‘030 teaches at FIGS. 3A-3E that the bounding shape 336A is inside the bounding shape 352A and the bounding shape 352A is without the only one group 330).
Re Claim 4:
The claim 4 encompasses the same scope of invention as that of the claim 2 except additional claim limitation that determining whether the primitive bounding box overlaps group bounding boxes for two or more groups currently under construction; and when it is determined that the primitive bounding box overlaps group bounding boxes for two or more groups currently under construction:
reducing the number of groups currently under construction for which a group bounding box is overlapped by the primitive bounding box to less than two; and thereafter adding the primitive to a group.
However, Benithin and Wald ‘030 further teach the claim limitation that determining whether the primitive bounding box overlaps group bounding boxes for two or more groups currently under construction; and when it is determined that the primitive bounding box overlaps group bounding boxes for two or more groups currently under construction:
reducing the number of groups currently under construction for which a group bounding box is overlapped by the primitive bounding box to less than two; and thereafter adding the primitive to a group (
Benithin teaches at FIGS. 20-21 that when it is determined that the primitive bounding box for the primitive 2012 overlaps both the group 2001A and 2002A of FIG. 20 for two or more groups current under construction, reducing the number of groups currently under construction for which a group bounding box 2000A in FIG. 21 is the only bounding box overlapping the primitive 2012 and thereafter adding the primitive 2012 to the group bounding box 2000A.
Wald ‘030 teaches at FIGS. 3B-3E and Paragraph 0063-0075 that determining whether the primitive bounding box overlaps group bounding boxes 352A-352B currently under construction; and when it is determined that the primitive bounding box 340C-340F overlaps group bounding boxes 340A and 340B for two or more groups currently under construction: reducing the number of groups currently under construction for which a group bounding box is overlapped by the primitive bounding box 340C-340F to the group bounding box 352A and thereafter adding the primitive to the group 352A.
Wald ‘030 teaches at Paragraph 0075 that the dimensions and/or size for the spatial elements 224C, 224D, 224E, and/or 224F may correspond to the bounding shape 336A and/or bounding shapes 340C, 340D, 340E, and/or 340F. Wald ‘030 teaches at FIGS. 3A-3E that the bounding shape 336A is inside the bounding shape 352A and the bounding shape 352A is without the only one group 330).
Re Claim 5:
The claim 5 encompasses the same scope of invention as that of the claim 4 except additional claim limitation that reducing the number of groups currently under construction by:
merging at least two groups under construction into a single merged group; and/or
completing at least one group under construction.
Benithin and Wald ‘030 further teach the claim limitation that reducing the number of groups currently under construction by:
merging at least two groups under construction into a single merged group; and/or
completing at least one group under construction (
Benithin teaches at FIGS. 20-21 merging at least two groups 2001 and 2002 of FIG. 20 into a single merged group 2000A of FIG. 21 and/or completing at least one group under construction.
Wald ‘030 teaches at FIGS. 3A-3E merging at least two groups 352A and 352B under construction into a single merged group 330 and/or completing at least one group 330 under construction.
Wald ‘030 teaches at FIGS. 3B-3E reducing the number of groups current under construction by merging at least two groups 340A and 340B under construction into a single merged group 352A and/or completing at least one group 352A under construction.
Wald ‘030 teaches at FIGS. 3B-3E and Paragraph 0063-0075 that determining whether the primitive bounding box overlaps group bounding boxes 352A-352B currently under construction; and when it is determined that the primitive bounding box 340C-340F overlaps group bounding boxes 340A and 340B for two or more groups currently under construction: reducing the number of groups currently under construction for which a group bounding box is overlapped by the primitive bounding box 340C-340F to the group bounding box 352A and thereafter adding the primitive to the group 352A.
Wald ‘030 teaches at Paragraph 0075 that the dimensions and/or size for the spatial elements 224C, 224D, 224E, and/or 224F may correspond to the bounding shape 336A and/or bounding shapes 340C, 340D, 340E, and/or 340F. Wald ‘030 teaches at FIGS. 3A-3E that the bounding shape 336A is inside the bounding shape 352A and the bounding shape 352A is without the only one group 330).
Re Claim 6:
The claim 6 encompasses the same scope of invention as that of the claim 5 except additional claim limitation that determining whether a group includes greater than or equal to a minimum number of primitives; and
when it is determined that the group includes greater than or equal to the minimum number of primitives: completing the group.
Benithin and Wald ‘030 further teach the claim limitation that that determining whether a group includes greater than or equal to a minimum number of primitives; and
when it is determined that the group includes greater than or equal to the minimum number of primitives: completing the group (
Benithin teaches at FIGS. 20-21 when it is determined that the group 2000A includes greater than the minimum number of primitives, completing the group 2000A.
Wald ‘030 teaches at FIGS. 3D-3E that when it is determined that the group 340A includes greater than or equal to the minimum number 2 of primitives, completing the group 340A.
Wald ‘030 teaches at FIGS. 3B-3E and Paragraph 0063-0075 that determining whether the primitive bounding box overlaps group bounding boxes 352A-352B currently under construction; and when it is determined that the primitive bounding box 340C-340F overlaps group bounding boxes 340A and 340B for two or more groups currently under construction: reducing the number of groups currently under construction for which a group bounding box is overlapped by the primitive bounding box 340C-340F to the group bounding box 352A and thereafter adding the primitive to the group 352A.
Wald ‘030 teaches at Paragraph 0075 that the dimensions and/or size for the spatial elements 224C, 224D, 224E, and/or 224F may correspond to the bounding shape 336A and/or bounding shapes 340C, 340D, 340E, and/or 340F. Wald ‘030 teaches at FIGS. 3A-3E that the bounding shape 336A is inside the bounding shape 352A and the bounding shape 352A is without the only one group 330).
Re Claim 7:
The claim 7 encompasses the same scope of invention as that of the claim 5 except additional claim limitation that determining whether two groups under construction each include less than a minimum number of primitives; and
when it is determined that two groups under construction each include less than the minimum number of primitives:
merging the two groups under construction into a single merged group.
Kern and Wald ‘030 further teach the claim limitation that determining whether two groups under construction each include less than a minimum number of primitives; and
when it is determined that two groups under construction each include less than the minimum number of primitives:
merging the two groups under construction into a single merged group (
Kern teaches at FIG. 4 determining whether two groups N4 and N5 each include less than a minimum number of primitives, and when it is determined that two groups N4 and N5 each include less than four primitives, merging the two groups N4 and N5 into a single merged group N2.
Wald ‘030 teaches at FIGS. 3D-3E that when it is determined that two groups 340C and 340E each include less than 2 primitives, merging the two groups 340C and 340E into a single merged group 340A).
Re Claim 8:
The claim 8 encompasses the same scope of invention as that of the claim 7 except additional claim limitation that the minimum number of primitives is less than or equal to half of a maximum number of primitives that a group can contain.
Kern and Wald ‘030 further teach the claim limitation that the minimum number of primitives is less than or equal to half of a maximum number of primitives that a group can contain (
Kern teaches at FIG. 4 that the minimum number of primitives is 2 less than half of a maximum number (8) of primitives that a group N1 can contain.
Wald ‘030 teaches at FIGS. 3D-3E that the minimum number of primitives (2) is less than half of a maximum number (7) of primitives that a group can contain).
Re Claim 9:
The claim 9 encompasses the same scope of invention as that of the claim 2 except additional claim limitation that determining whether the primitive bounding box does not overlap a group bounding box for any of a maximum number of groups that are currently under construction; and when it is determined that the primitive bounding box does not overlap a group bounding box for any of a maximum number of groups that are currently under construction:
determining a group currently under construction for which a group bounding box is closest to the primitive bounding box; and adding the primitive to the determined group.
Kern and Wald ‘030 further teach the claim limitation that determining whether the primitive bounding box does not overlap a group bounding box for any of a maximum number of groups that are currently under construction; and when it is determined that the primitive bounding box does not overlap a group bounding box for any of a maximum number of groups that are currently under construction:
determining a group currently under construction for which a group bounding box is closest to the primitive bounding box; and adding the primitive to the determined group (
Kern teaches at FIG. 4 and Paragraph 0032-0035 comparing a position of the primitive O7 with a position of the group N7 currently under construction. Kern teaches at Paragraph 0034 that O5 is intersection-tested again N1 which is determined that O5 is not in N1 and the intersection test continued to determine that O5 is in N6 but not in N7 based on the spatial position of the O5 and the spatial position of N6/N67. Selecting the group N6 to add the primitive O5 to the group N6 based on the comparison (intersection test) and adding the primitive O5 to the selected group N6. Kern teaches that it is determined by the intersection test whether the primitive bounding box for the primitive O5 overlap the group bounding box N1 or N6 or N7 for any of a maximum number of groups N1-N7 and when it is determined that the primitive bounding box for the primitive O5 does not overlap a group bounding box N1 for any of a maximum number of groups N1-N7 that are currently under construction, determining a group N6 which is the closest to the primitive bounding box for the primitive O5, and adding the primitive O5 to the determined group N6.
Wald ’30 teaches at FIGS. 3A-3E that determining whether the primitive bounding box 340C does not overlap a group bounding box 352B for any of a maximum number of groups that are currently under construction, and when it is determined that the primitive bounding box 340C does not overlap a group bounding box 352B for any of a maximum number of groups that are currently under construction, determining a group 352A currently under construction for which a group bounding box 352a is closest to the primitive bounding box 340C and adding the primitive to the determined group 352A).
Re Claim 11:
The claim 11 recites a non-transitory computer readable storage medium storing software code which when executing on a processor performs the method of claim 1.
The claim 11 is subject to the same rationale of rejection as the claim 1.
Moreover, Wald ‘030 further teaches a non-transitory computer readable storage medium storing software code which when executing on a processor performs the method of claim 1 (Wald ‘030 Paragraph 0174 that The memory 1204 may include any of a variety of computer-readable media. The computer-readable media may be any available media that may be accessed by the computing device 1200and at Paragraph [0177] The CPU(s) 1206 may be configured to execute at least some of the computer-readable instructions to control one or more components of the computing device 1200 to perform one or more of the methods and/or processes described herein).
Re Claim 12:
The claim 12 is in parallel with the claim 1 in the form of an apparatus. The claim 12 is subject to the same rationale of rejection as the claim 1.
Moreover, Wald ‘030 further teaches a tile-based graphics processor; the processor comprising:
a bounding box hierarchy building circuit (
Wald ‘030 teaches at Paragraph 0033 that various functions described herein as being performed by entities may be carried out by hardware, firmware, and/or software. For instance, various functions may be carried out by a processor executing instructions stored in memory. In at least one embodiment.
Wald ‘030 teaches at Paragraph 0035 that the node manager 102 may be configured to manage nodes of a partitioning of a space (e.g., a hierarchical partitioning of a scene), such as a partitioning 120 and at Paragraph 0040 that the bin determiner 104 determines and generates multi-dimensional bins that correspond to a spatial partitioning of the space such as the bins 122A and bin 122B and at Paragraph 0050 that The partition determiner 108 may be configured to determine one or more partitions of the spatial elements based at least on one or more assignments between the one or more spatial elements and the one or more bins determined using the bin assignor 106.
Wald ‘030 teaches at Paragraph 0053 that [0053] In the example shown, the node 130A may correspond to a root node of the partitioning 120. In various examples, the node 130A may correspond to a different type of node of the partitioning 120, such as an internal node or a leaf node. In examples where the node 130A corresponds to a root node, the node 130A may refer to a top-level node of the partitioning 120, which may encompass the entire scene 200 or object or region being partitioned. In at least one embodiment (e.g., for top-down approaches), a root node may serve as a starting point for determining the partitioning 120 and indicate the bounding volume or shape 330 that encloses all the spatial elements in the scene 200.
Wald ‘030 teaches at Paragraph [0054] A node of the partitioning 120 may include, for example, one or more values (e.g., one or more bounding shape coordinates and/or dimensions) indicating one or more bounding volumes or shapes that encloses (e.g., tightly encloses) one or more spatial elements that correspond to the node);
a processing circuit (
Wald ‘030 teaches at Paragraph 0033 that various functions described herein as being performed by entities may be carried out by hardware, firmware, and/or software. For instance, various functions may be carried out by a processor executing instructions stored in memory. In at least one embodiment.
Wald ‘030 teaches at Paragraph [0047] In at least one embodiment, the bin assignor 106 is configured to assign a spatial element 224 to a bin based at least on the bin at least partially including the spatial element. For example, the bin assignor 106 may assign each spatial element 224 to a bin based at least on determining at least one portion of the spatial element 224 falls within the bin. In at least one embodiment, the bin assignor 106 may assign a spatial element 224 to a bin based at least on determining a centroid and/or one or more other points of the spatial element 224 (e.g., a barycenter) falls within the bin. For example, FIG. 2 indicates centroids of the spatial elements 224, which are within the bins to which they are assigned, such as a point 232 of the spatial element 224D within a bin 240).
Re Claim 13:
The claim 13 encompasses the same scope of invention as that of the claim 12 except additional claim limitation that the processing circuit is configured to compare a position of a primitive with a position of a group currently under construction by: comparing a primitive bounding box that bounds the primitive with a group bounding box that bounds any primitives already added to the group currently under construction.
The claim 13 is in parallel with the claim 2 in the form of an apparatus. The claim 13 is subject to the same rationale of rejection as the claim 2.
Re Claim 14:
The claim 14 encompasses the same scope of invention as that of the claim 13 except additional claim limitation that the processing circuit is configured to:
determine whether a primitive bounding box for a primitive overlaps a group bounding box for only one group currently under construction; and
when it is determined that the primitive bounding box overlaps a group bounding box for only one group currently under construction:
add the primitive to the only one group.
The claim 14 is in parallel with the claim 3 in the form of an apparatus. The claim 14 is subject to the same rationale of rejection as the claim 3.
Re Claim 15:
The claim 15 encompasses the same scope of invention as that of the claim 13 except additional claim limitation that the processing circuit is configured to: determine whether a primitive bounding box for a primitive overlaps group bounding boxes for two or more groups currently under construction; and when it is determined that the primitive bounding box overlaps group bounding boxes for two or more groups currently under construction: reduce the number of groups currently under construction for which a group bounding box is overlapped by the primitive bounding box to less than two; and thereafter add the primitive to a group.
The claim 15 is in parallel with the claim 4 in the form of an apparatus. The claim 15 is subject to the same rationale of rejection as the claim 4.
Re Claim 16:
The claim 16 encompasses the same scope of invention as that of the claim 15 except additional claim limitation that the processing circuit is configured to reduce the number of groups currently under construction by: merging at least two groups under construction into a single merged group; and/or completing at least one group under construction.
The claim 16 is in parallel with the claim 5 in the form of an apparatus. The claim 16 is subject to the same rationale of rejection as the claim 5.
Re Claim 17:
The claim 17 encompasses the same scope of invention as that of the claim 16 except additional claim limitation that the processing circuit is configured to:
determine whether a group includes greater than or equal to a minimum number of primitives; and
when it is determined that the group includes greater than or equal to the minimum number of primitives:
complete the group.
The claim 17 is in parallel with the claim 6 in the form of an apparatus. The claim 17 is subject to the same rationale of rejection as the claim 6.
Re Claim 18:
The claim 18 encompasses the same scope of invention as that of the claim 16 except additional claim limitation that the processing circuit is configured to:
determine whether two groups under construction each include less than a minimum number of primitives; and
when it is determined that two groups under construction each include less than the minimum number of primitives:
merge the two groups under construction into a single merged group.
The claim 18 is in parallel with the claim 7 in the form of an apparatus. The claim 18 is subject to the same rationale of rejection as the claim 7.
Re Claim 19:
The claim 19 encompasses the same scope of invention as that of the claim 13 except additional claim limitation that the processing circuit is configured to:
determine whether a primitive bounding box for a primitive does not overlap a group bounding box for any of a maximum number of groups that are currently under construction; and
when it is determined that the primitive bounding box does not overlap a group bounding box for any of a maximum number of groups that are currently under construction:
determine a group currently under construction for which a group bounding box is closest to the primitive bounding box; and
add the primitive to the determined group.
The claim 19 is in parallel with the claim 9 in the form of an apparatus. The claim 19 is subject to the same rationale of rejection as the claim 9.
Claims 10 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Wal US-PGPUB No. 2025/0308030 (hereinafter Wald ‘030) in view of Benthin et al. US-PGPUB No. 2018/0300939 (hereinafter Benthin);
Dietrich JR. US-PGPUB No. 2025/0104330 (hereinafter Dietrich);
Kern et al. US-PGPUB No. 2025/0200864 (hereinafter Kern);
Oldcorn et al. US-PGPUB No. 2023/0099806 (hereinafter Oldcorn);
Gupta et al. US-PGPUB No. 2024/0104824 (hereinafter Gupta);
Saleh et al. US-PGPUB No. 2022/0198739 (hereinafter Saleh).
Re Claim 10:
The claim 10 encompasses the same scope of invention as that of the claim 1 except additional claim limitation that that traversing the hierarchy of bounding boxes to identify primitives to rasterize and render to generate a rendering tile; and rasterizing and rendering the identified primitives to generate the rendering tile.
Benithin at least suggests the claim limitation that traversing the hierarchy of bounding boxes to identify primitives to rasterize and render to generate a rendering tile; and rasterizing and rendering the identified primitives to generate the rendering tile (
Benithin teaches at Paragraph 0223 that the traversal/intersection unit 2203 may include a traversal component which performs traversal operations to traverse the BVH 2205 and an intersection component to identify ray/primitive intersections and BVH processing circuitry/logic 2204 generates the BVH 2205 using the techniques described herein. An object BVH generation module 2208 generates a current iteration of a BVH for each object in a scene and a top level BVH generation module 2209 for constructing a top level BVH over the current set of object BVHs.).
Wald ‘030 at least suggests the claim limitation that that traversing the hierarchy of bounding boxes to identify primitives to rasterize and render to generate a rendering tile; and rasterizing and rendering the identified primitives to generate the rendering tile (
Wald ‘030 teaches at [0035] As an overview, the node manager 102 may be configured to manage nodes of a partitioning of a space (e.g., a hierarchical partitioning of a scene), such as a partitioning 120, which may include modifying, creating, and/or deleting one or more nodes. The bin determiner 104 may be configured to determine and/or generate multi-dimensional bins that correspond to a spatial partitioning of the space, such as bins 122A or bins 122B. The bin assignor 106 may be configured to assign one or more spatial elements to one or more of the multi-dimensional bins, such as a spatial element 224A, a spatial element 224B, a spatial element 224C, a spatial element 224D, a spatial element 224E, a spatial element 224F.
Wald ‘030 teaches at Paragraph [0037] A partitioning determined using the process 100 may be used to render an image of a scene using any of a variety of rending techniques. For example, the partitioning 120 may be used to perform any of a variety of light transport simulation operations on graphical data, such as path tracing, ray tracing, ray marching, etc. By way of example, and not limitation, the hierarchical partitioning may correspond to the acceleration structure 1100 of FIG. 11 and may be used in the ray tracing pipeline 1000 of FIG. 10.
Wald ‘030 teaches at Paragraph 0038 that the hierarchical partitioning, such as the partitioning 120, includes a Bounding Volume Hierarchy (BVH). However, the process 100 may be used to determine other types of partitionings of spatial elements. Examples of the spatial elements include one or more primitives, spheres, cubes, triangles, quadrilaterals, tetrahedra, points, lines, curves, polylines, polygons, parametric shapes, polyhedrons, volumetric regions, surfaces, meshes, models, points of a point cloud, voxels, particles, Bezier patches, Non-Uniform Rational B-Spline (NURB) surfaces, implicit surfaces, fractal shapes, textured surfaces, and/or parametric surfaces. However, the partitioning 120 may include other types of data structures and/or may be used to partition other types of data. As various examples, the partitioning 120 may include one or more of an r-tree, a k-d tree, a geohash, a grid index, or a spatial hashing. Further examples of data types for the spatial elements include N-dimensional points, geographic data (e.g., geographic features, geographic coordinates or objects), sensor data (e.g., sensor readings), biological data, database data (e.g., entries, records, or elements), vector data, etc. For example, disclosed hierarchical partitionings may be used to accelerate database operations (e.g., data access) for spatially indexed data elements. While a scene is primarily described herein, the scene may also refer to a space which includes the spatial elements.
Wald ‘030 teaches at Paragraph 0057 that one or more splitting planes that correspond to the node and/or metadata that may be used for traversal and/or modification of the partitioning 120 and at Paragraph 0103 the raster engine 725 includes a setup engine, a coarse raster engine, a culling engine, a clipping engine, a fine raster engine, and a tile coalescing engine. The setup engine receives transformed vertices and generates plane equations associated with the geometric primitive defined by the vertices. The plane equations are transmitted to the coarse raster engine to generate coverage information (e.g., an x,y coverage mask for a tile) for the primitive. ).
Saleh further teaches the claim limitation that that traversing the hierarchy of bounding boxes to identify primitives to rasterize and render to generate a rendering tile; and rasterizing and rendering the identified primitives to generate the rendering tile (
Saleh teaches at FIGS. 3-6 and Paragraph 0031 0037 and 0044-0046 traversing the BVH to identify primitives in the leaf nodes of the BVH to process using the intersection test to generate a rendering tile by the APD 116 and processing the identified primitives in the leaf nodes of the BVH using intersection test to generate the rendering tile in the tile buffer.
Saleh teaches at Paragraph 0031 that the ray tracing test uses a representation of space referred to as a bounding volume hierarchy. This bounding volume hierarchy is the “acceleration structure” described above. In an example bounding volume hierarchy, each non-leaf node represents an axis aligned bounding box that bounds the geometry of all children of that node. In an example, the base node represents the maximal extents of an entire region for which the ray intersection test is being performed. In this example, the base node has two children that each represent different axis aligned bounding boxes that cover different parts of the entire region. Each of those two children has two child nodes that represent axis aligned bounding boxes that subdivide the space of their parents, and so on. Leaf nodes represent a triangle or other primitive against which a ray test can be performed.
Saleh teaches at Paragraph [0032] The bounding volume hierarchy data structure allows the number of ray-triangle intersections (which are complex and thus expensive in terms of processing resources) to be reduced as compared with a scenario in which no such data structure were used and therefore all triangles in a scene would have to be tested against the ray. Specifically, if a ray does not intersect a particular bounding box, and that bounding box bounds a large number of triangles, then all triangles in that box can be eliminated from the test. Thus, a ray intersection test is performed as a sequence of tests of the ray against axis-aligned bounding boxes, and tests against leaf node primitives.
Saleh teaches at Paragraph [0044] The APDs 116 store a copy of the bounding volume hierarchy data 602 for the scene being rendered. In some examples, the bounding volume hierarchy data 602 the is stored in each APD 116 is the same. In some examples, all APDs 116 store all of the bonding volume hierarchy data 602 needed to render a scene. In some examples, the APDs 116 store different bounding volume hierarchy data 602, but each APD 116 has no restriction regarding which bounding volume hierarchy data 602 is to be stored in an APD memory 135 of the APD 116. More specifically, in operation, it is possible for an APD 116 to “page in and out” portions of the BVH 602 if the APD memory 135 is not large enough to store all BVH data 602. In these examples, each APD 116 is permitted to store any of the BVH data 602 in APD memory 135. The bounding volume hierarchy data 602 is a mirrored resource. More specifically, each APD 116 stores its own independent version of the bounding volume hierarchy 602, which allows the APD 116 to access the BVH data 602 with lower latency as compared to data stored in the APD memory 135 of a different APD 116 or a different memory such as the memory 104. The BVH data 602 is not specifically tied to any portion of the render target 500, because the BVH data 602 represents geometry, which is in world space, rather than pixels in screen space. Thus, the BVH data 602 is not subdivided on a per-APD basis. However, because the BVH data 602 is accessed very frequently by the APDs 116 as the APDs 116 perform ray tracing operations, at least some, and in some instances, all, of the BVH data 602 is duplicated across APDs 116 so that each APD 116 has local access to the BVH data 602, to reduce latency of access to the BVH data 602.
Saleh teaches at Paragraph [0045] The APDs 116 store a tile buffer 604. A tile buffer 604 is a buffer that stores the pixel results of ray tracing operations for the tiles 502 assigned to the APD 116 in which the tile buffer 604 is stored. In other words, an APD 116 stores the pixel results of tiles 502 assigned to that APD 116 into the tile buffer 604 stored in the APD memory 135 of that APD 116. In an example, the render target buffer—the buffer into which the pixel results of ray tracing are written—is within the tile buffer 604 of, and thus within the APD memory 135 of, the APD 116 generating those pixel results. Because frequency of access to the tile buffer 604 is high, the APDs 116 maintain independent tile buffers 604 storing tile buffer data for tiles 502 processed in the respective APD 116).
It would have been obvious to one of the ordinary skill in the art before the filing date of the instant application to have traversed the BVH for fetching data (primitives) for box nodes for the render target according to Saleh to have identified the leaf nodes in the BVH to fetch the primitives to process for rendering a tile in the tile buffer. One of the ordinary skill in the art would have been motivated to have provided BVH for efficiently providing primitives to generate the rendering tile.
Re Claim 20:
The claim 20 encompasses the same scope of invention as that of the claim 12 except additional claim limitation that a rendering circuit operable to rasterize and render primitives to generate rendering tiles of the render output; and a primitive providing circuit operable to provide primitives to the rendering circuit for rasterizing and rendering; wherein the primitive providing circuit is configured to traverse a hierarchy of bounding boxes built by the bounding box hierarchy building circuit to determine which primitives to rasterize and render to generate a rendering tile and provide the determined primitives to the rendering circuit; and the rendering circuit is configured to rasterize and render primitives provided by the primitive providing circuit to generate a rendering tile.
The claim 20 is in parallel with the claim 10 in the form of an apparatus. The claim 20 is subject to the same rationale of rejection as the claim 10.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JIN CHENG WANG whose telephone number is (571)272-7665. The examiner can normally be reached Mon-Fri 8:00-5:00.
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-270-0728. 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.
/JIN CHENG WANG/Primary Examiner, Art Unit 2617