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
The Amendment filed February 27th, 2026 has been entered and made of record. Claims 1, 7-9, 11-13, 15 and 17-21 have been amended. Claims 1-21 remain pending and rejected in the application. Applicant’s amendments to the Specifications and Drawings have overcome each and every objection previously set forth in the Non-Final Office Action mailed December 1st, 2025 and have therefore been withdrawn. Additionally, applicant’s reasoning and explanation regarding the previous 35 U.S.C. 112(f) interpretation appear to present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function and avoid being interpreted under, 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph and thus will no longer be interpreted under 35 U.S.C. 112(f).
Response to Arguments
Applicant’s arguments with respect to independent claims 1 and 11 have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument. The newly added prior art of Fenney, along with previous prior art of Doyle, have been incorporated into the rejection of the independent claims and therefore teaches that newly amended claim language (see claims 1 and 11 below).
Applicant’s argument to independent claim 20 that there is no teaching, suggestion, or motivation to combine the references, the examiner recognizes that obviousness may be established by combining or modifying the teachings of the prior art to produce the claimed invention where there is some teaching, suggestion, or motivation to do so found either in the references themselves or in the knowledge generally available to one of ordinary skill in the art. See In re Fine, 837 F.2d 1071, 5 USPQ2d 1596 (Fed. Cir. 1988), In re Jones, 958 F.2d 347, 21 USPQ2d 1941 (Fed. Cir. 1992), and KSR International Co. v. Teleflex, Inc., 550 U.S. 398, 82 USPQ2d 1385 (2007). In this case, since Jesus and Doyle are both related to the field of sorting and processing bounding boxes and tiles in relation to different primitives related to hierarchical data structuring, it would appear to be obvious to one skilled in the art at the time of the claimed invention, to have considered both methods of hierarchical traversal through bounding boxes and tiles for graphic processing and therefore, combine the functionalities together.
Applicant’s arguments with respect to independent claim 21 has been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument. The newly added prior art of Fenney has been incorporated into the rejection of the independent claim and therefore teaches the newly amended claim language (see claims 21 below).
In regards to any additional arguments regarding the dependent claims 2-10 and 12-19 for the virtue of their dependency are moot because the independent claims are not allowable, in addition, newly added prior art of Barczak and Fenney, along with Doyle, have been incorporated into the rejection of claim 7 and 17 and therefore teach the newly amended claim language (see claims 7 and 17 below).
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-19 and 21 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.
Regarding claim 1, in the newly amended claim portion, the very last step being presented is “determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds”, however this statement is considered to be indefinite because it does not explain what to do with that information once it is done determining. This causes confusion on whether it is an actual necessary step that needs to be performed or not because the claim just ends after determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds and does not explain any purpose on what to then do with that information afterwards.
Regarding claim 8, in the newly amended claim portion, the very last step being presented is “and determining whether the rendering tile overlaps a lower level bounding box of the hierarchy of bounding boxes that is stored in the packet”, however similar to claim 1, this statement is considered to be indefinite because it does not explain what to do with that information once it has done determining. This causes confusion on whether it is an actual necessary step that needs to be performed or not because the claim just ends after determining whether the rendering tile overlaps a lower level bounding box of the hierarchy of bounding boxes that is stored in the packet and does not explain any purpose on what to then do with that information afterwards.
Regarding claim 11, in the newly amended claim portion, the very last step being presented is “determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds”, however this statement is considered to be indefinite because it does not explain what to do with that information once it is done determining. This causes confusion on whether it is an actual necessary step that needs to be performed or not because the claim just ends after determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds and does not explain any purpose on what to then do with that information afterwards.
Regarding claim 21, in the newly amended claim portion, the very last step being presented is “determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds”, however this statement is considered to be indefinite because it does not explain what to do with that information once it is done determining. This causes confusion on whether it is an actual necessary step that needs to be performed or not because the claim just ends after determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds and does not explain any purpose on what to then do with that information afterwards.
Regarding dependent claims 2-7, 9, 10 and 12-19, they are rejected under 35 U.S.C. 112(b) because they depend on a claim that is also rejected under 35 U.S.C. 112(b).
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 (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim 20 is rejected under 35 U.S.C. 103 as being unpatentable over Jesus et al. (U.S. Patent: #11,922,555 B2), hereinafter Jesus, in view of Doyle et al. (U.S. Patent #11,727,528 B2), hereinafter Doyle.
Regarding claim 20, Jesus discloses a tile-based graphics processor that is operable to generate a render output to identify primitives to process to generate a rendering tile of the render output (Col. 47, Lines 14-17 teach that a reference is now made to FIG. 27 which illustrates an example tile-based graphics processing system 2700 which comprises the tiling engine 2300 of FIG. 23 and the control stream decoder 2500 of FIG. 25 and Col. 41, Lines 54-60 teach that a reference is now made to FIG. 25 which illustrates an example control stream decoder 2500 which is configured to identify, from the control streams stored in memory, the primitives that are relevant for rendering a current tile. The example control stream decoder 2500 of FIG. 25 comprises control stream fetch logic 2502 and a control stream analyzer 2504.) However, Jesus fails to disclose to generate a render output by traversing a hierarchy of bounding boxes.
Doyle discloses to generate a render output by traversing a hierarchy of bounding boxes (Col. 26, Lines 34-41 teach that the graphics processor 1340 includes an inter-core task manager 1345, which acts as a thread dispatcher to dispatch execution threads to one or more shader cores 1355A-1355N and a tiling unit 1358 to accelerate tiling operations for tile-based rendering, in which rendering operations for a scene are subdivided in image space, for example to exploit local spatial coherence within a scene or to optimize use of internal caches. Additionally, Col. 59, Lines 6-14 teach that in one embodiment, BVH processing circuitry/logic 4504 generates the BVH 4505 and refits the nodes of the BVH using the techniques described herein. In particular, a BVH construction unit 4508 generates a current BVH 4505 based on the current set of input primitives 4506. As mentioned, the BVH 4505 comprises a hierarchical tree of nodes where each “parent” node encloses multiple “child” nodes, which are located beneath the parent node in the hierarchy.). Since Jesus teaches a tile-based graphics processor system with the capabilities to identify primitives to generate a rendering tile for output from the use of bounding boxes and Doyle teaches a tile-based graphics processor system with the functionality to generate and construct a hierarchy of bounding boxes (BVH), it would have been obvious to a person having ordinary skill in the art to combine the functions together so that a set or hierarchy of bounding boxes could be incorporated into the system for utilization in identifying primitives to generate a rendering tile for output.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to have modified Jesus to incorporate the teachings of Doyle so that by utilizing and building additional bounding boxes, this would help improve and reduce overall processing times by incorporating parallel processing for help in rendering the identified primitives.
Additionally, Jesus in view of Doyle disclose the processor (Col. 48, Lines 37-46 of Jesus teaches that a processor, computer, or computer system may be any kind of device, machine or dedicated circuit, or collection or portion thereof, with processing capability such that it can execute instructions. A processor may be any kind of general purpose or dedicated processor, such as a CPU, GPU, System-on-chip, state machine, media processor, an application-specific integrated circuit (ASIC), a programmable logic array, a field-programmable gate array (FPGA), or the like. A computer or computer system may comprise one or more processors.) comprising:
a bounding box generating circuit (Col. 37, Lines 55-58 of Jesus teach that the tiling engine 2300 may further comprise a bounding box generator 2306 which is configured to receive a primitive block and generate a bounding box therefor.) configured to build a hierarchy of bounding boxes, wherein each bounding box of the hierarchy of bounding boxes bounds one or more primitives of a set of primitives to be processed to generate a render output (Col. 60, Lines 5-17 of Doyle teach that at 4600 an initial BVH is constructed based on the primitives of the current scene. For example, each primitive may be surrounded by its own bounding box to create the leaf bounding boxes which are then merged to form the first level of inner nodes. Inner nodes are then merged to form the second level, and so on. BVHs may also be constructed from the top down, where the top node in the hierarchy is defined first as the bounding box surrounding all primitives. This top level BVH is then subdivided into smaller sets of primitives to define the next level of nodes, which are then subdivided, and so on, until leaf nodes are reached. Regardless of how the BVH nodes are built, they are stored in memory in DFS order at 4600.);
a supplementary information generating circuit (Col. 10, Lines 53-58 of Jesus teach that the control stream 502 comprises a primitive block entry 504.sub.0, 504.sub.1 for each primitive block that is valid for at least one tile in the tile group. Each primitive block entry 504.sub.0, 504.sub.1 comprises a primitive block header 506 and a primitive block pointer 508. A primitive block entry 504.sub.0, 504.sub.1 may optionally comprise primitive mask data 510.) configured to generate, for at least one bounding box of a hierarchy of bounding boxes generated by the bounding box generating circuit, supplementary information that indicates, for each region of plural regions that the bounding box overlaps, whether or not the respective region contains at least one of the one or more primitives that the bounding box bounds (Col. 11, Lines 16-29 of Jesus teach that the primitive mask data 510 comprises one or more primitive masks that identify the primitives of the primitive block that fall, at least partially, within the bounds of each of the valid tiles. Each primitive mask may comprise a bit for each primitive in the primitive block that indicates whether that primitive falls, at least partially, within the bounds of the corresponding tile(s). In some cases (e.g. when each valid tile has a different primitive mask), the primitive mask data 510 may comprise a primitive mask for each valid tile. In other cases (e.g. when all the valid tiles have the same primitive mask), the primitive mask data 510 may comprise only one mask which applies to all of the valid tiles. Each primitive mask may be in a compressed or uncompressed form. Additionally, Col. 33, Lines 44-51 of Jesus teach that returning to FIG. 21, in some cases, determining whether at least one primitive of the primitive block falls, at least partially, within the bounds of the selected quadrant may comprise generating a primitive mask for the selected quadrant. A primitive mask comprises a bit for each primitive in the primitive block which indicates whether or not that primitive falls, at least partially, within the bounds of the quadrant.).
Claims 1-5, 9-15, 19 and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Jesus, in view of Doyle and further in view of Fenney et al (Pub. No.: US 2023/0252718 A1), hereinafter Fenney.
Regarding claim 1, Jesus discloses a method of operating a tile-based graphics processor (FIG. 6 and Col. 7, Lines 46-47 teach that FIG. 6 is a flow diagram of an example multi-level hierarchical method of tiling primitives;); the method comprising:
generating a bounding box, wherein each bounding box of the bounding box bounds one or more primitives of a set of primitives to be processed to generate a render output (Col. 37, Lines 53-63 teach that where the tile group selector logic 2302 uses the bounding box of a primitive block to determine which tile groups to associate with the primitive block, the tiling engine 2300 may further comprise a bounding box generator 2306 which is configured to receive a primitive block and generate a bounding box therefor. Several example methods for generating or identifying the bounding for a primitive block were described above with respect to FIG. 6. The bounding box may be generated at any granularity. For example, the bounding box may be at X or Y co-ordinate granularity or at tile granularity and Col. 14, Lines 7-18 teach that at step 604, information identifying a primitive block to be tiled is received. A primitive block comprises one or more primitives. In some cases, the information identifying a primitive block may be the location of the primitive block in memory and/or the position data for the primitives in the primitive block. The position data of a primitive may define the position of the primitive in the rendering space. For example, the position data for a primitive may comprise X, Y, and Z co-ordinates in the rendering space for the primitive (although the Z co-ordinates may not be needed for tiling). Once a primitive block has been identified the method proceeds to step 606.). However, Jesus fails to disclose a hierarchy of bounding boxes.
Doyle discloses a hierarchy of bounding boxes (Col. 60, Lines 5-17 teach that at 4600 an initial BVH is constructed based on the primitives of the current scene. For example, each primitive may be surrounded by its own bounding box to create the leaf bounding boxes which are then merged to form the first level of inner nodes. Inner nodes are then merged to form the second level, and so on. BVHs may also be constructed from the top down, where the top node in the hierarchy is defined first as the bounding box surrounding all primitives. This top level BVH is then subdivided into smaller sets of primitives to define the next level of nodes, which are then subdivided, and so on, until leaf nodes are reached. Regardless of how the BVH nodes are built, they are stored in memory in DFS order at 4600.). Since Jesus teaches a tile-based graphics processor system with the capabilities to identify primitives to generate a rendering tile for output from the use of a bounding box and groups of tiles and Doyle teaches a tile-based graphics processor system with the functionality to generate and construct a hierarchy of bounding boxes (BVH), it would have been obvious to a person having ordinary skill in the art to combine the functions together so that a set or hierarchy of bounding boxes could be incorporated into the system for utilization in identifying primitives to generate a rendering tile for output.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to have modified Jesus to incorporate the teachings of Doyle so that by utilizing and building additional bounding boxes, this would help improve and reduce overall processing times by incorporating parallel processing for help in rendering the identified primitives.
Furthermore, Jesus in view of Doyle disclose generating, for at least one bounding box of the hierarchy of bounding boxes, supplementary information that indicates, for each region of plural regions that the bounding box is overlaps, whether or not the respective region contains at least one of the one or more primitives that the bounding box bounds (Col. 2, Line 64 through Col. 3, Line 13 of Jesus teach that the primitives may be grouped into primitive blocks based on their location in the render space so that spatially similar primitives are in the same primitive block. For example, the rendering space may be divided into macro regions which may encompass multiple tiles (e.g. a 1024×1024 rendering space that is divided into one thousand twenty-four 32×32 tiles may have sixteen 256×256 macro regions) and the primitive block generator 210 may be configured to maintain a primitive block for each macro region. Then when the primitive block generator 210 receives a primitive it determines which macro region(s) the primitive, at least partially, falls within. If the primitive block generator 210 determines that the primitive falls, at least partially, within only one macro region, then the primitive block generator 210 may place the primitive (i.e. the transformed geometry data related to that primitive) in the primitive block for that macro region. Additionally, FIG. 49 and Col. 64, Lines 38-53 of Doyle teach that FIG. 49 illustrates different examples including the common case 4901, a box-BVH node test 4902, a sphere-BVH node test 4903, a frustum-BVH node test 4904, and a point-BVH node test 4905. Various other queries may be designed to determine overlap between the different shapes and the BVH and Col. 65, Lines 3-13 of Doyle teach that in addition, in one embodiment, the ray tracing engine 5010 offloads certain types of queries to the programmable execution units (EUs) 5051-5053, N. In particular, certain queries which can be processed efficiently by the EUs are sent to the scheduler 5060 which schedules the work on the EUs 5051-5053, N. This may include, for example, queries to return all primitives contained within a box/sphere/frustum whenever the ray tracing engine 5010 reaches a BVH leaf. The EUs 5051-5053, N may then execute program code which processes the geometry contained within the specified shape.);
using the hierarchy of bounding boxes and the supplementary information to identify primitives of the set of primitives to process to generate a rendering tile of the render output (Col. 26, Lines 52-63 of Jesus teach that the primitive mask section 1810 comprises information identifying the primitives of the corresponding primitive block that are relevant for rendering one or more sets of one or more tiles in the tile group. A primitive may be relevant for rendering a set of one or more tiles if that primitive falls, at least partially, within the area of the rendering space covered by the set of tiles. The information identifying the primitives that are relevant for rendering a set of one or more tiles may comprise a primitive mask that comprises a bit for each primitive in the primitive block which indicates whether that primitive is relevant for rendering the set of tiles. Additionally, Col. 46, Lines 44-51 of Doyle teach that in one embodiment, the ray tracing cores 3150 accelerate ray tracing operations for both real-time ray tracing and non-real-time ray tracing implementations. In particular, the ray tracing cores 3150 include ray traversal/intersection circuitry for performing ray traversal using bounding volume hierarchies (BVHs) and identifying intersections between rays and primitives enclosed within the BVH volumes.);
and processing the identified primitives to generate the rendering tile of the render output (Col. 41, Lines 28-38 of Jesus teach that in the rasterization phase each tile is rendered based on the primitives that are relevant for rendering that tile (e.g. the primitives that fall, at least partially, within the bounds of the tile). So, in the rasterization phase when the rasterization logic is ready to render a tile it analyses the control streams stored in memory to identify the primitives that are relevant to rendering that tile. The relevant primitives are then fetched from memory and used to render the tile. In the examples described herein, the control streams that identify the primitives which are relevant to rendering a tile are the control streams for the tile groups that the tile forms part of.);
wherein using the hierarchy of bounding boxes and the supplementary information to identify primitives of the set of primitives to process to generate a rendering tile of the render output comprises:
traversing the hierarchy of bounding boxes by testing the rendering tile against one or more bounding boxes of the hierarchy of bounding boxes to determine whether the rendering tile overlaps the one or more bounding boxes (FIG. 49 and Col. 64, Lines 38-53 of Doyle teach that FIG. 49 illustrates different examples including the common case 4901, a box-BVH node test 4902, a sphere-BVH node test 4903, a frustum-BVH node test 4904, and a point-BVH node test 4905. Various other queries may be designed to determine overlap between the different shapes and the BVH. In this embodiment, the nodes of the BVH 4900A-J are traversed by comparing coordinate data of the various shapes with the coordinates and bounds of each of the BVH nodes, ultimately arriving at leaf node 4900J. The traversal here is indicated by the dotted arrows moving through node 4900A, node 4900B, node 4900E, node 49001, and leaf node 4900J. Assuming that this traversal/query is performed with a box, the coordinates of the box (e.g., min/max values for x, y, and z) may be compared with the bounding coordinates of each of the BVH nodes, to filter down to the smallest-sized node intersected by the box.). However, Jesus in view of Doyle fail to disclose and when it is determined that the rendering tile overlaps a bounding box of the hierarchy of bounding boxes for which supplementary information is generated: determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds.
Fenney discloses and when it is determined that the rendering tile overlaps a bounding box of the hierarchy of bounding boxes for which supplementary information is generated: determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds (FIG. 2a and paragraph 98 teaches that the method comprises determining a first region 6 and a further region 8 within the 3D scene 2. The first region 6 comprises one or more primitives 4 in the 3D scene. In the example of FIG. 2a, first region 6 contains primitives 4a and 4b. The further region 8 also comprises one or more primitives 4 in the 3D scene. In the example of FIG. 2a, the further region 8 contains primitives 4a and 4c. The primitives 4 in FIG. 2a are shown as identical sized triangles, however other shapes and sizes of primitives 4 may be used. The first region 6 and further region 8 shown in FIG. 2a are boxes, however any shape and size of region may be used. Additionally, paragraph 130 teaches that if the partition P1 is used then the method determines a set of two bounding regions 6a, 6b for the voxel 38b. Bounding region 6a covers primitives 4 for the top half portion, which in this example is only one primitive 4, which is the leaf node AABB 50a. Bounding region 6b covers primitives 4 for the bottom half portion, which in this example are the two primitives 4 captured by respective leaf node bounding AABBs 50b and 50c. If the partition P2 is used then the method determines a set of two bounding regions 8a, 8b for the voxel 38b. Bounding region 8a covers primitives 4 for the left half portion, which in this example are two primitives 4 captured by respective leaf node bounding AABBs 50a and 50b. Bounding region 8b covers primitives 4 for the right half portion, which in this example is the single primitive 4 captured by leaf node AABB 50c. In other words, for a given portion of the image scene 2 represented in this case by voxel 38b, the method uses a first partition P1 in FIG. 7d defining a first sub portion and second sub portion, whilst in FIG. 7e the method uses a second partition P2 defining a third sub portion and a fourth sub portion. Each of the first, second, third and fourth sub portions occupy a different volume of the image scene portion of voxel 38b.). Since Jesus in view of Doyle teach a tile-based graphics processor system with the capabilities to traverse through a hierarchy of bounding boxes (BVH) and determine if overlap exists between other shapes and bounding boxes and Fenney teaches a traversal technique that can be used to determine whether or not particular overlapping regions of bounding boxes contain multiple primitives within their regions, it would have been obvious to a person having ordinary skill in the art to combine the functions together so that when traversing through a hierarchy of bounding boxes to determining if any overlaps of different primitive shapes and boxes exist, it could also be determined if any of the boxes existed in a region that contained multiple primitives as well.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to have modified Jesus in view of Doyle to incorporate the teachings of Fenney, so that while determining if any overlap exists during the traversal, checking the regions for primitives as well would improve and reduce overall processing time by potentially eliminating the need to traverse through regions that did not contain any primitives.
Regarding claim 2, Jesus in view of Doyle and Fenney disclose everything claimed as applied above (see claim 1), in addition, Jesus in view of Doyle and Fenney disclose wherein each region of the plural regions corresponds to a respective set of one or more contiguous rendering tiles of the render output that the bounding box overlaps (Col. 26, Lines 32-41 of Jesus teach that the coverage mask section 1808 comprises information indicating which tiles in the tile group that overlap with, or intersect, the bounding box of the primitive block are valid for the corresponding primitive block. As described above, a tile is valid for a primitive block if at least one primitive in the primitive block falls, at least partially, within the bounds of the tile. The information indicating which tiles in the tile group that overlap with the bounding box of the primitive block are valid for the primitive block may be in the form of a coverage mask.).
Regarding claim 3, Jesus in view of Doyle and Fenney disclose everything claimed as applied above (see claim 1), in addition, Jesus in view of Doyle and Fenney disclose wherein the supplementary information comprises an array of elements, wherein each element of the array indicates whether or not a corresponding region of the plural regions contains at least one of the one or more primitives that the bounding box bounds (Col. 10, Line 53 through Col. 11, Line 10 of Jesus teach that the control stream 502 comprises a primitive block entry 504.sub.0, 504.sub.1 for each primitive block that is valid for at least one tile in the tile group. Each primitive block entry 504.sub.0, 504.sub.1 comprises a primitive block header 506 and a primitive block pointer 508. A primitive block entry 504.sub.0, 504.sub.1 may optionally comprise primitive mask data 510. The primitive block header 506 comprises information identifying which tiles in the tile group are valid for the primitive block. For example, as shown in FIG. 5, the primitive block header 506 may comprise a primitive mask format field 512, 514, 516 and 518 for each tile in the tile group that indicates whether or not the tile is valid for the primitive block. For example, each primitive mask format field 512, 514, 516, 518 may comprise two bits and ‘00’ may indicate that the tile is invalid for the primitive block; ‘01’ may indicate that the tile has a full primitive mask (i.e. all primitives in the primitive block are valid for the tile); ‘10’ may indicate that the primitive mask is compressed; and ‘11’ may indicate that the primitive mask is uncompressed. The primitive block header 506 may also comprise other information 520 such as, but not limited to, the number of vertices in the primitive block, whether or not all the tiles in the tile group are valid and have the full primitive mask (i.e. all the primitives in the primitive block are valid for the tile), and whether or not all of the tiles have the same primitive mask.).
Regarding claim 4, Jesus in view of Doyle and Fenney disclose everything claimed as applied above (see claim 3), in addition, Jesus in view of Doyle and Fenney disclose wherein the array is a bitmask (Col. 26, Lines 58-63 of Jesus teach that the information identifying the primitives that are relevant for rendering a set of one or more tiles may comprise a primitive mask that comprises a bit for each primitive in the primitive block which indicates whether that primitive is relevant for rendering the set of tiles.).
Regarding claim 5, Jesus in view of Doyle and Fenney disclose everything claimed as applied above (see claim 3), in addition, Jesus in view of Doyle and Fenney disclose wherein the array has a predetermined number of elements (Col. 12, Lines 5-21 of Jesus teach that the inventors have identified that while the number of primitives/primitive blocks per tile cannot be accurately determined in advance, the number of primitives/primitive blocks can be accurately estimated in advance, and thus if the maximum number of different control streams/display lists that a primitive block forms part of is predetermined or fixed the maximum size of the tiling information can be determined in advance. The inventors have identified that this can be achieved using a multi-level hierarchical tiling structure. Specifically, a multi-level hierarchy of the tiles is generated wherein each level of the hierarchy comprises tile groups comprising one or more tiles, and a higher level comprises tile groups with more tiles than a lower level. A control stream is generated for each tile group which lists primitive blocks relevant to rendering at least one tile in the tile group. Any primitive block can only form part of a fixed or predetermined number of control streams.),
and the method comprises basing a size of the plural regions on a size of the bounding box (Col. 36, Line 60 through Col. 37, Line 11 of Jesus teach that a reference is now made to FIG. 23 which illustrates an example tiling engine 2300 which is configured to generate information, which is referred to here as tiling information, which indicates which primitives in a render fall within each tile of the rendering space. The tiling engine 2300 may be configured to implement the method 600 of FIG. 6. For example, the rendering space may be divided into a plurality of tiles (e.g. as described with respect to FIGS. 1 and 2) and a multi-level hierarchy of tile groups may be generated wherein each level in the hierarchy comprises non-overlapping groups of tiles of a particular size, and higher level groups comprise more tiles than lower level groups (e.g. as described with respect to FIGS. 6 and 7). Additionally, Col. 27, Lines 59-65 teach that in some cases, the coverage mask may comprise a bit for each tile in a block of relevant tiles that indicates whether or not the tile is valid for the primitive block, wherein the block of relevant tiles is based on the bounding box for the primitive block. The block of relevant tiles comprises the tiles in the tile group that intersect the bounding box for the primitive block, but may also include other tiles.).
Regarding claim 9, Jesus in view of Doyle and Fenney disclose everything claimed as applied above (see claim 3), in addition, Jesus in view of Doyle and Fenney disclose wherein using the one or more bounding boxes and the supplementary information to identify primitives of the set of primitives to process to generate a rendering tile comprises:
identifying, based on a size of the bounding box for which supplementary information is generated, an element of the array that corresponds to the rendering tile (Col. 33, Lines 48-54 of Jesus teach that a primitive mask comprises a bit for each primitive in the primitive block which indicates whether or not that primitive falls, at least partially, within the bounds of the quadrant. For example, a ‘1’ may indicate that the corresponding primitive falls, at least partially, within the bounds of the quadrant and a ‘0’ may indicate that the corresponding primitive does not fall within the bounds of the quadrant. Additionally, Col. 37, Lines 25-39 of Jesus teach that the tile group selector logic 2302 is configured to associate a primitive block with one or more tile groups of the hierarchy so that the primitive block is not associated with more than a maximum number of tile groups, but that if the primitive block is relevant for rendering a tile the primitive block is associated with at least one tile group comprising that tile. The tile group selector logic 2302 may use any suitable method for selecting the tile groups to be associated with a primitive block. For example, where a primitive block may only be associated with a single tile group then the tile group selector logic 2302 may select the tile group to be associated with a primitive block using the method 900 of FIG. 9 where the primitive block is associated with the smallest tile group in the hierarchy of tile groups that encompasses a bounding box for the primitive block.);
and using the identified element of the array to determine whether the rendering tile contains any of the primitives that the bounding box bounds (Col. 29, Lines 12-33 of Jesus teach that the tile granularity/resolution bounding box 1906 for the primitive block comprising primitives 1902 and 1904 is a 5×3 block of tiles. In this example, the L3-0 tile group completely encompasses the bounding box 1906 and so the block of relevant tiles is the 5×3 block of tiles that fall within the bounding box 1906. The smallest s×s block of tiles (wherein s is a power of 2) that includes the block of relevant tiles is an 8×8 block of tiles. Therefore, the expanded block of relevant tiles 1908 for the primitive block is an 8×8 block of tiles. The 8×8 expanded block of relevant tiles 1908 is divided into four quadrants (i.e. four 4×4 blocks of tiles) which are referred to herein as the Level 2 (L2) quadrants. In this example, quadrant 1 (Q1) is the top left quadrant of 4×4 tiles, quadrant 2 (Q2) is the top right quadrant of 4×4 tiles, quadrant three 3 (Q3) is the bottom left quadrant of 4×4 tiles, and quadrant 4 (Q4) is the bottom right quadrant of 4×4 tiles. As shown in FIG. 19, at least one primitive 1902, 1904 falls, at least partially, within the area of the rendering space covered by L2-Q1, L2-Q2 and L2-Q4 so each bit corresponding to these quadrants is set to ‘1’. Neither of the primitives 1902 and 1904 fall within L2-Q3 so the bit corresponding to Q3 is set to ‘0’.).
Regarding claim 10, Jesus in view of Doyle and Fenney disclose everything claimed as applied above (see claim 1), in addition, Jesus in view of Doyle and Fenney disclose a non-transitory computer readable storage medium storing software code which when executing on a processor performs the method of claim 1 (Col. 8, Lines 1-9 of Jesus teach that there may be provided a non-transitory computer readable storage medium having stored there-on a computer readable description of a tiling engine, a control stream decoder or a graphics processing system described herein that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture an integrated circuit embodying the tiling engine, the control stream decoder or the graphics processing system.).
Regarding claim 11, Jesus discloses a tile-based graphics processor (Col. 47, Lines 14-17 teach that reference is now made to FIG. 27 which illustrates an example tile-based graphics processing system 2700 which comprises the tiling engine 2300 of FIG. 23 and the control stream decoder 2500 of FIG. 25.) comprising:
a bounding box generating circuit (Col. 37, Lines 55-58 teach that the tiling engine 2300 may further comprise a bounding box generator 2306 which is configured to receive a primitive block and generate a bounding box therefor.) configured to generate a bounding box, wherein each bounding box bounds one or more primitives of a set of primitives to be processed to generate a render output (Col. 37, Lines 53-63 teach that where the tile group selector logic 2302 uses the bounding box of a primitive block to determine which tile groups to associate with the primitive block, the tiling engine 2300 may further comprise a bounding box generator 2306 which is configured to receive a primitive block and generate a bounding box therefor. Several example methods for generating or identifying the bounding for a primitive block were described above with respect to FIG. 6. The bounding box may be generated at any granularity. For example, the bounding box may be at X or Y co-ordinate granularity or at tile granularity.). However, Jesus fails to disclose a hierarchy of bounding boxes.
Doyle discloses a hierarchy of bounding boxes (Col. 60, Lines 5-17 teach that at 4600 an initial BVH is constructed based on the primitives of the current scene. For example, each primitive may be surrounded by its own bounding box to create the leaf bounding boxes which are then merged to form the first level of inner nodes. Inner nodes are then merged to form the second level, and so on. BVHs may also be constructed from the top down, where the top node in the hierarchy is defined first as the bounding box surrounding all primitives. This top level BVH is then subdivided into smaller sets of primitives to define the next level of nodes, which are then subdivided, and so on, until leaf nodes are reached. Regardless of how the BVH nodes are built, they are stored in memory in DFS order at 4600.). Since Jesus teaches a tile-based graphics processor system with the capabilities to identify primitives to generate a rendering tile for output from the use of a bounding box and groups of tiles and Doyle teaches a tile-based graphics processor system with the functionality to generate and construct a hierarchy of bounding boxes (BVH), it would have been obvious to a person having ordinary skill in the art to combine the functions together so that a set or hierarchy of bounding boxes could be incorporated into the system for utilization in identifying primitives to generate a rendering tile for output.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to have modified Jesus to incorporate the teachings of Doyle so that by utilizing and building additional bounding boxes, this would help improve and reduce overall processing times by incorporating parallel processing for help in rendering the identified primitives.
Furthermore, Jesus in view of Doyle disclose a supplementary information generating circuit (Col. 10, Lines 53-58 of Jesus teach that the control stream 502 comprises a primitive block entry 504.sub.0, 504.sub.1 for each primitive block that is valid for at least one tile in the tile group. Each primitive block entry 504.sub.0, 504.sub.1 comprises a primitive block header 506 and a primitive block pointer 508. A primitive block entry 504.sub.0, 504.sub.1 may optionally comprise primitive mask data 510.) configured to generate, for at least one bounding box of a hierarchy of bounding boxes generated by the bounding box generating circuit, supplementary information that indicates, for each region of plural regions that the bounding box overlaps, whether or not the respective region contains at least one of the one or more primitives that the bounding box bounds (Col. 2, Line 64 through Col. 3, Line 13 of Jesus teach that the primitives may be grouped into primitive blocks based on their location in the render space so that spatially similar primitives are in the same primitive block. For example, the rendering space may be divided into macro regions which may encompass multiple tiles (e.g. a 1024×1024 rendering space that is divided into one thousand twenty-four 32×32 tiles may have sixteen 256×256 macro regions) and the primitive block generator 210 may be configured to maintain a primitive block for each macro region. Then when the primitive block generator 210 receives a primitive it determines which macro region(s) the primitive, at least partially, falls within. If the primitive block generator 210 determines that the primitive falls, at least partially, within only one macro region, then the primitive block generator 210 may place the primitive (i.e. the transformed geometry data related to that primitive) in the primitive block for that macro region. Additionally, FIG. 49 and Col. 64, Lines 38-53 of Doyle teach that FIG. 49 illustrates different examples including the common case 4901, a box-BVH node test 4902, a sphere-BVH node test 4903, a frustum-BVH node test 4904, and a point-BVH node test 4905. Various other queries may be designed to determine overlap between the different shapes and the BVH and Col. 65, Lines 3-13 of Doyle teach that in addition, in one embodiment, the ray tracing engine 5010 offloads certain types of queries to the programmable execution units (EUs) 5051-5053, N. In particular, certain queries which can be processed efficiently by the EUs are sent to the scheduler 5060 which schedules the work on the EUs 5051-5053, N. This may include, for example, queries to return all primitives contained within a box/sphere/frustum whenever the ray tracing engine 5010 reaches a BVH leaf. The EUs 5051-5053, N may then execute program code which processes the geometry contained within the specified shape.);
a primitive identifying circuit (Col. 38, Lines 1-16 of Jesus teach that the control stream generator 2304 is configured to generate a control stream for each tile group that is associated with at least one primitive block. The control stream for a tile group comprises a primitive block entry for each primitive block associated with that tile group. In some cases, the control stream generator 2304 is configured to receive a primitive block and information identifying the one or more tile groups that the primitive block is associated with (e.g. the information output by the tile group selector logic 2302). The control stream generator is then configured to, for each tile group that the primitive block is associated with: (i) generate a primitive block entry that comprises information that identifies that primitive block; and (ii) add the primitive block entry to the control stream for the corresponding tile group (e.g. store the primitive block entry in memory as part of the control stream for the corresponding tile group).) configured to use one or more bounding boxes generated by the bounding box generating circuit and supplementary information generated by the supplementary information generating circuit to identify primitives of a set of primitives to process to generate a rendering tile of a render output (Col. 26, Lines 52-63 of Jesus teach that the primitive mask section 1810 comprises information identifying the primitives of the corresponding primitive block that are relevant for rendering one or more sets of one or more tiles in the tile group. A primitive may be relevant for rendering a set of one or more tiles if that primitive falls, at least partially, within the area of the rendering space covered by the set of tiles. The information identifying the primitives that are relevant for rendering a set of one or more tiles may comprise a primitive mask that comprises a bit for each primitive in the primitive block which indicates whether that primitive is relevant for rendering the set of tiles. Additionally, Col. 46, Lines 44-51 of Doyle teach that in one embodiment, the ray tracing cores 3150 accelerate ray tracing operations for both real-time ray tracing and non-real-time ray tracing implementations. In particular, the ray tracing cores 3150 include ray traversal/intersection circuitry for performing ray traversal using bounding volume hierarchies (BVHs) and identifying intersections between rays and primitives enclosed within the BVH volumes.);
and a rendering circuit (Col. 47, Lines 17-27 of Jesus teach that the graphics processing system 2700 of FIG. 27 is similar to the graphics processing system 200 of FIG. 2 in that it comprises geometry processing logic 2704 and rasterization logic 2706; the geometry processing logic 2704 comprises transformation logic 2708 and a primitive block generator 2710 (each of which function as the corresponding components of FIG. 2); and the rasterization logic 2706 comprises a rasterizer 2714, HSR logic 2716 and texturing/shading logic 2718 (each of which function as the corresponding components of FIG. 2 described above).) configured to generate a rendering tile of a render output by processing primitives identified by the primitive identifying circuit (Col. 41, Lines 28-38 of Jesus teach that in the rasterization phase each tile is rendered based on the primitives that are relevant for rendering that tile (e.g. the primitives that fall, at least partially, within the bounds of the tile). So, in the rasterization phase when the rasterization logic is ready to render a tile it analyses the control streams stored in memory to identify the primitives that are relevant to rendering that tile. The relevant primitives are then fetched from memory and used to render the tile. In the examples described herein, the control streams that identify the primitives which are relevant to rendering a tile are the control streams for the tile groups that the tile forms part of.);
wherein the primitive identifying circuit is configured to use a hierarchy of bounding boxes and supplementary information to identify primitives of a set of primitives to process to generate a rendering tile of a render output by:
traversing the hierarchy of bounding boxes by testing the rendering tile against one or more bounding boxes of the hierarchy of bounding boxes to determine whether the rendering tile overlaps the one or more bounding boxes (FIG. 49 and Col. 64, Lines 38-53 of Doyle teach that FIG. 49 illustrates different examples including the common case 4901, a box-BVH node test 4902, a sphere-BVH node test 4903, a frustum-BVH node test 4904, and a point-BVH node test 4905. Various other queries may be designed to determine overlap between the different shapes and the BVH. In this embodiment, the nodes of the BVH 4900A-J are traversed by comparing coordinate data of the various shapes with the coordinates and bounds of each of the BVH nodes, ultimately arriving at leaf node 4900J. The traversal here is indicated by the dotted arrows moving through node 4900A, node 4900B, node 4900E, node 49001, and leaf node 4900J. Assuming that this traversal/query is performed with a box, the coordinates of the box (e.g., min/max values for x, y, and z) may be compared with the bounding coordinates of each of the BVH nodes, to filter down to the smallest-sized node intersected by the box.). However, Jesus in view of Doyle fail to disclose and when it is determined that the rendering tile overlaps a bounding box of the hierarchy of bounding boxes for which supplementary information is generated: determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds.
Fenney discloses and when it is determined that the rendering tile overlaps a bounding box of the hierarchy of bounding boxes for which supplementary information is generated: determining whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds (FIG. 2a and paragraph 98 teaches that the method comprises determining a first region 6 and a further region 8 within the 3D scene 2. The first region 6 comprises one or more primitives 4 in the 3D scene. In the example of FIG. 2a, first region 6 contains primitives 4a and 4b. The further region 8 also comprises one or more primitives 4 in the 3D scene. In the example of FIG. 2a, the further region 8 contains primitives 4a and 4c. The primitives 4 in FIG. 2a are shown as identical sized triangles, however other shapes and sizes of primitives 4 may be used. The first region 6 and further region 8 shown in FIG. 2a are boxes, however any shape and size of region may be used. Additionally, paragraph 130 teaches that if the partition P1 is used then the method determines a set of two bounding regions 6a, 6b for the voxel 38b. Bounding region 6a covers primitives 4 for the top half portion, which in this example is only one primitive 4, which is the leaf node AABB 50a. Bounding region 6b covers primitives 4 for the bottom half portion, which in this example are the two primitives 4 captured by respective leaf node bounding AABBs 50b and 50c. If the partition P2 is used then the method determines a set of two bounding regions 8a, 8b for the voxel 38b. Bounding region 8a covers primitives 4 for the left half portion, which in this example are two primitives 4 captured by respective leaf node bounding AABBs 50a and 50b. Bounding region 8b covers primitives 4 for the right half portion, which in this example is the single primitive 4 captured by leaf node AABB 50c. In other words, for a given portion of the image scene 2 represented in this case by voxel 38b, the method uses a first partition P1 in FIG. 7d defining a first sub portion and second sub portion, whilst in FIG. 7e the method uses a second partition P2 defining a third sub portion and a fourth sub portion. Each of the first, second, third and fourth sub portions occupy a different volume of the image scene portion of voxel 38b.). Since Jesus in view of Doyle teach a tile-based graphics processor system with the capabilities to traverse through a hierarchy of bounding boxes (BVH) and determine if overlap exists between other shapes and bounding boxes and Fenney teaches a traversal technique that can be used to determine whether or not particular overlapping regions of bounding boxes contain multiple primitives within their regions, it would have been obvious to a person having ordinary skill in the art to combine the functions together so that when traversing through a hierarchy of bounding boxes to determining if any overlaps of different primitive shapes and boxes exist, it could also be determined if any of the boxes existed in a region that contained multiple primitives as well.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to have modified Jesus in view of Doyle to incorporate the teachings of Fenney, so that while determining if any overlap exists during the traversal, checking the regions for primitives as well would improve and reduce overall processing time by potentially eliminating the need to traverse through regions that did not contain any primitives.
Regarding claim 12, the system steps correlate to and are rejected similarly to method steps from claim 2 (see claim 2 above).
Regarding claim 13, the system steps correlate to and are rejected similarly to method steps from claim 3 (see claim 3 above).
Regarding claim 14, the system steps correlate to and are rejected similarly to method steps from claim 4 (see claim 4 above).
Regarding claim 15, the system steps correlate to and are rejected similarly to method steps from claim 5 (see claim 5 above).
Regarding claim 19, the system steps correlate to and are rejected similarly to method steps from claim 9 (see claim 9 above).
Regarding claim 21, Jesus discloses a tile-based graphics processor that is operable to generate a render output to identify primitives to process to generate a rendering tile of the render output (Col. 47, Lines 14-17 teach that a reference is now made to FIG. 27 which illustrates an example tile-based graphics processing system 2700 which comprises the tiling engine 2300 of FIG. 23 and the control stream decoder 2500 of FIG. 25 and Col. 41, Lines 54-60 teach that a reference is now made to FIG. 25 which illustrates an example control stream decoder 2500 which is configured to identify, from the control streams stored in memory, the primitives that are relevant for rendering a current tile. The example control stream decoder 2500 of FIG. 25 comprises control stream fetch logic 2502 and a control stream analyzer 2504.). However, Jesus fails to disclose to generate a render output by traversing a hierarchy of bounding boxes.
Doyle discloses to generate a render output by traversing a hierarchy of bounding boxes (Col. 64, Lines 21-24 teach that in one embodiment of the invention, the traversal/intersection circuitry 4503 includes circuitry and/or logic for performing more extended node-intersection variants when traversing the BVH 4505.). Since Jesus teaches a tile-based graphics processor system with the capabilities to identify primitives to generate a rendering tile for output from the use of bounding boxes and Doyle teaches a tile-based graphics processor system with the functionality to traverse through a hierarchy of bounding boxes (BVH), it would have been obvious to a person having ordinary skill in the art to combine the functions together so that the functionality of being able to traverse through a set of bounding boxes could be implemented for use in helping to identify primitives that need to be generated for output.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Jesus to incorporate the teachings of Doyle so that the functionality of traversing through a hierarchy of bounding boxes would help improve and allow for more optimized rendering by potentially culling primitives that do not contribute to a specific tile, which would help in reducing processing time and memory usage.
Additionally, Jesus in view of Doyle disclose the processor (Col. 48, Lines 37-46 of Jesus teaches that a processor, computer, or computer system may be any kind of device, machine or dedicated circuit, or collection or portion thereof, with processing capability such that it can execute instructions. A processor may be any kind of general purpose or dedicated processor, such as a CPU, GPU, System-on-chip, state machine, media processor, an application-specific integrated circuit (ASIC), a programmable logic array, a field-programmable gate array (FPGA), or the like. A computer or computer system may comprise one or more processors.) comprising:
a primitive identifying circuit (Col. 38, Lines 1-16 of Jesus teach that the control stream generator 2304 is configured to generate a control stream for each tile group that is associated with at least one primitive block. The control stream for a tile group comprises a primitive block entry for each primitive block associated with that tile group. In some cases, the control stream generator 2304 is configured to receive a primitive block and information identifying the one or more tile groups that the primitive block is associated with (e.g. the information output by the tile group selector logic 2302). The control stream generator is then configured to, for each tile group that the primitive block is associated with: (i) generate a primitive block entry that comprises information that identifies that primitive block; and (ii) add the primitive block entry to the control stream for the corresponding tile group (e.g. store the primitive block entry in memory as part of the control stream for the corresponding tile group).) configured to identify primitives of a set of primitives to process to generate a rendering tile of a render output (Col. 26, Lines 52-63 of Jesus teach that the primitive mask section 1810 comprises information identifying the primitives of the corresponding primitive block that are relevant for rendering one or more sets of one or more tiles in the tile group. A primitive may be relevant for rendering a set of one or more tiles if that primitive falls, at least partially, within the area of the rendering space covered by the set of tiles. The information identifying the primitives that are relevant for rendering a set of one or more tiles may comprise a primitive mask that comprises a bit for each primitive in the primitive block which indicates whether that primitive is relevant for rendering the set of tiles.);
a rendering circuit (Col. 47, Lines 17-27 of Jesus teach that the graphics processing system 2700 of FIG. 27 is similar to the graphics processing system 200 of FIG. 2 in that it comprises geometry processing logic 2704 and rasterization logic 2706; the geometry processing logic 2704 comprises transformation logic 2708 and a primitive block generator 2710 (each of which function as the corresponding components of FIG. 2); and the rasterization logic 2706 comprises a rasterizer 2714, HSR logic 2716 and texturing/shading logic 2718 (each of which function as the corresponding components of FIG. 2 described above).) configured to generate a rendering tile of a render output by processing primitives identified by the primitive identifying circuit (Col. 41, Lines 28-38 of Jesus teach that in the rasterization phase each tile is rendered based on the primitives that are relevant for rendering that tile (e.g. the primitives that fall, at least partially, within the bounds of the tile). So, in the rasterization phase when the rasterization logic is ready to render a tile it analyses the control streams stored in memory to identify the primitives that are relevant to rendering that tile. The relevant primitives are then fetched from memory and used to render the tile. In the examples described herein, the control streams that identify the primitives which are relevant to rendering a tile are the control streams for the tile groups that the tile forms part of.);
wherein the primitive identifying circuit is configured to identify primitives of a set of primitives to process to generate a rendering tile by:
traversing a hierarchy of bounding boxes by testing the rendering tile against one or more bounding boxes of the hierarchy of bounding boxes to determine whether the rendering tile overlaps the one or more bounding boxes (FIG. 49 and Col. 64, Lines 38-53 of Doyle teach that FIG. 49 illustrates different examples including the common case 4901, a box-BVH node test 4902, a sphere-BVH node test 4903, a frustum-BVH node test 4904, and a point-BVH node test 4905. Various other queries may be designed to determine overlap between the different shapes and the BVH. In this embodiment, the nodes of the BVH 4900A-J are traversed by comparing coordinate data of the various shapes with the coordinates and bounds of each of the BVH nodes, ultimately arriving at leaf node 4900J. The traversal here is indicated by the dotted arrows moving through node 4900A, node 4900B, node 4900E, node 49001, and leaf node 4900J. Assuming that this traversal/query is performed with a box, the coordinates of the box (e.g., min/max values for x, y, and z) may be compared with the bounding coordinates of each of the BVH nodes, to filter down to the smallest-sized node intersected by the box.),
wherein each bounding box of the hierarchy of bounding boxes bounds one or more primitives of the set of primitives, and wherein at least one bounding box of the hierarchy of bounding boxes is associated with supplementary information that indicates, for each region of plural regions that the bounding box overlaps, whether or not the respective region contains at least one of the one or more primitives that the bounding box bounds (Col. 11, Lines 16-29 of Jesus teach that the primitive mask data 510 comprises one or more primitive masks that identify the primitives of the primitive block that fall, at least partially, within the bounds of each of the valid tiles. Each primitive mask may comprise a bit for each primitive in the primitive block that indicates whether that primitive falls, at least partially, within the bounds of the corresponding tile(s). In some cases (e.g. when each valid tile has a different primitive mask), the primitive mask data 510 may comprise a primitive mask for each valid tile. In other cases (e.g. when all the valid tiles have the same primitive mask), the primitive mask data 510 may comprise only one mask which applies to all of the valid tiles. Each primitive mask may be in a compressed or uncompressed form. Additionally, Col. 33, Lines 44-51 of Jesus teach that returning to FIG. 21, in some cases, determining whether at least one primitive of the primitive block falls, at least partially, within the bounds of the selected quadrant may comprise generating a primitive mask for the selected quadrant. A primitive mask comprises a bit for each primitive in the primitive block which indicates whether or not that primitive falls, at least partially, within the bounds of the quadrant.). However, Jesus in view of Doyle fail to disclose and when it is determined that the rendering tile overlaps a bounding box of the hierarchy of bounding boxes that is associated with supplementary information: determine whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds.
Fenney discloses and when it is determined that the rendering tile overlaps a bounding box of the hierarchy of bounding boxes that is associated with supplementary information: determine whether the supplementary information indicates that a region of plural regions that the bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the bounding box bounds (FIG. 2a and paragraph 98 teaches that the method comprises determining a first region 6 and a further region 8 within the 3D scene 2. The first region 6 comprises one or more primitives 4 in the 3D scene. In the example of FIG. 2a, first region 6 contains primitives 4a and 4b. The further region 8 also comprises one or more primitives 4 in the 3D scene. In the example of FIG. 2a, the further region 8 contains primitives 4a and 4c. The primitives 4 in FIG. 2a are shown as identical sized triangles, however other shapes and sizes of primitives 4 may be used. The first region 6 and further region 8 shown in FIG. 2a are boxes, however any shape and size of region may be used. Additionally, paragraph 130 teaches that if the partition P1 is used then the method determines a set of two bounding regions 6a, 6b for the voxel 38b. Bounding region 6a covers primitives 4 for the top half portion, which in this example is only one primitive 4, which is the leaf node AABB 50a. Bounding region 6b covers primitives 4 for the bottom half portion, which in this example are the two primitives 4 captured by respective leaf node bounding AABBs 50b and 50c. If the partition P2 is used then the method determines a set of two bounding regions 8a, 8b for the voxel 38b. Bounding region 8a covers primitives 4 for the left half portion, which in this example are two primitives 4 captured by respective leaf node bounding AABBs 50a and 50b. Bounding region 8b covers primitives 4 for the right half portion, which in this example is the single primitive 4 captured by leaf node AABB 50c. In other words, for a given portion of the image scene 2 represented in this case by voxel 38b, the method uses a first partition P1 in FIG. 7d defining a first sub portion and second sub portion, whilst in FIG. 7e the method uses a second partition P2 defining a third sub portion and a fourth sub portion. Each of the first, second, third and fourth sub portions occupy a different volume of the image scene portion of voxel 38b.). Since Jesus in view of Doyle teach a tile-based graphics processor system with the capabilities to traverse through a hierarchy of bounding boxes (BVH) and determine if overlap exists between other shapes and bounding boxes and Fenney teaches a traversal technique that can be used to determine whether or not particular overlapping regions of bounding boxes contain multiple primitives within their regions, it would have been obvious to a person having ordinary skill in the art to combine the functions together so that when traversing through a hierarchy of bounding boxes to determining if any overlaps of different primitive shapes and boxes exist, it could also be determined if any of the boxes existed in a region that contained multiple primitives as well.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to have modified Jesus in view of Doyle to incorporate the teachings of Fenney, so that while determining if any overlap exists during the traversal, checking the regions for primitives as well would improve and reduce overall processing time by potentially eliminating the need to traverse through regions that did not contain any primitives.
Claims 7 and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Jesus in view of Doyle and Fenney and further in view of Barczak et al. (Pub. No.: US 2025/0131639 A1), hereinafter Barczak.
Regarding claim 7, Jesus in view of Doyle and Fenney disclose everything claimed as applied above (see claim 1), in addition, Jesus in view of Doyle and Fenney disclose wherein the bounding box of the hierarchy of bounding boxes for which supplementary information is generated is a higher level bounding box of the hierarchy of bounding boxes that encompasses one or more lower level bounding boxes of the hierarchy of bounding boxes (FIG. 43 and Col. 55, Line 64 through Col. 56, Line 3 of Doyle teach that FIG. 43 shows an acceleration structure which may be used for hybrid traversal, which is a two-level tree with a single top level BVH 4300 and several bottom level BVHs 4301 and 4302. Graphical elements are shown to the right to indicate inner traversal paths 4303, outer traversal paths 4304, traversal nodes 4305, leaf nodes with triangles 4306, and leaf nodes with custom primitives 4307.);
However, Jesus in view of Doyle and Fenney fail to disclose when it is determined that the supplementary information indicates that a region of plural regions that the higher level bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the higher level bounding box bounds: testing the rendering tile against the one or more lower level bounding boxes of the hierarchy of bounding boxes that are encompassed by the higher level bounding box.
Barczak discloses when it is determined that the supplementary information indicates that a region of plural regions that the higher level bounding box overlaps that corresponds to the rendering tile contains at least one of the one or more primitives that the higher level bounding box bounds: testing the rendering tile against the one or more lower level bounding boxes of the hierarchy of bounding boxes that are encompassed by the higher level bounding box (Paragraph 49 teaches that in order to perform ray tracing for a scene, a processing unit (e.g., ray tracing circuitry 280 of FIG. 2) performs a ray intersection test by traversing through the tree 304, and, for each bounding box tested (i.e., by traversing respective internal nodes N), eliminating branches below a traversed node if the test for that node fails.). Since Jesus in view of Doyle and Fenney teach a method for traversing through overlapping hierarchical bounding boxes with associating levels and Barczak teaches a bounding box traversal technique that can test and check if overlapping bounding boxes contain lower level boxes that even need to be traversed through, it would have been obvious to a person having ordinary skill in the art to combine the functions together so that while traversing through the hierarchy of bounding boxes, lower level boxes could be checked and tested for potential overlapping shapes and primitives before actually needing to traverse to the lower box if the higher box does not contain any primitives or overlapping shapes.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to have modified Jesus in view of Doyle and Fenney to incorporate the teachings of Barczak so that lower level boxes could be tested and checked at higher levels to determine if the overlapping bounding boxes at a lower level actually contain any primitives, which would help improve processing speed and eliminate unnecessary traversal time by not needing to travel to any of the lower bounding boxes that do not contain any primitives.
Furthermore, Jesus in view of Doyle, Fenney and Barczak disclose and when it is determined that the supplementary information indicates that a region of plural regions that the higher level bounding box overlaps that corresponds to the rendering tile does not contain at least one of the one or more primitives that the higher level bounding box bounds:
not testing the rendering tile against the one or more lower level bounding boxes of the hierarchy of bounding boxes that are encompassed by the higher level bounding box (Paragraph 49 of Barczak teaches that in one example, it is assumed that ray 1 intersects triangle T5 as the closest hit. The processing unit would test against bounding box N1 and then after returning a hit, fetch the resulting child node, which contains bounding boxes for the next level of hierarchy below N1 (nodes N2 and N3). When this node data returns from memory, bounding boxes for N2 and N3 are tested. The processing unit returns a failure or miss result against bounding box N2 (since ray 1 does not interact with the bounding box). The processing unit eliminates all sub-nodes of node N2. Since ray 1 does interact with bounding box N3, it would return a hit and then subsequently fetch N3 from memory, which contains bounding boxes for N6 and N7. Tests are then performed against bounding boxes N6 and N7, by traversing through their respective representative nodes N6 and N7, noting that the test for node N6 succeeds but for node N7 fails. The processing unit would then test triangles T5 and T6 by traversing through representative leaf nodes T5 and T6, noting that test determines that T5 is the closest hit for the ray, and therefore the test for T5 succeeds, but T6 fails (even though the ray might hit T6, however it is not the closest hit).).
Regarding claim 17, the system steps correlate to and are rejected similarly to method steps from claim 7 (see claim 7 above).
Claims 8 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Jesus in view of Doyle and Fenney and further in view of Morrical (Pub. No.: US 2023/0206378 A1).
Regarding claim 8, Jesus in view of Doyle and Fenney disclose everything claimed as applied above (see claim 7), in addition, Jesus in view of Doyle and Fenney disclose wherein the bounding box of the hierarchy of bounding boxes for which supplementary information is generated is a bounding box that bounds all of the primitives of a packet of primitives (Col. 14, Lines 41-51 of Jesus teach that where a primitive block may only be associated with a single tile group, then the tile group associated with the primitive block may be selected, for example, in accordance with the method 900 described with reference to FIG. 9. This method 900 begins at step 902 where the smallest axis-aligned bounding box encompassing or enclosing all of the primitives in the primitive block is defined. A bounding box may be considered to encompass or enclose all the primitives in a primitive block if the bounding box encompasses or encloses all of the vertices of each primitive in the primitive block.). However, Jesus in view of Doyle and Fenney fail to disclose a packet bounding box.
Morrical discloses a packet bounding box (FIG. 6 and paragraph 82 teach that FIG. 6 illustrates an example of a process that, as a result of being performed by a processing device, determine a bounding box around a primitive, in accordance with at least one embodiment. In at least one embodiment, a processing device performing a KNN query calculates a set of bounding boxes around a set of primitives. Primitives can be points, lines, triangles, or polygons. Bounding boxes around primitives are determined by a processing device as part of performing the query. The processing device may include a graphics processing unit which may be utilized to determine bounding boxes for the primitives.). Since Jesus in view of Doyle and Fenney teach the initial method steps for using a tile-based graphics processor with the capabilities to generate a bounding box that would bound all of a set of primitives and Morrical teaches a method step for a tile-based graphics processor with the capabilities to generate a set of different bounding boxes that can bound a set of primitives, it would have been obvious to a person having ordinary skill in the art to combine the features together so that in addition to being able to create one bounding box that can bound all of the primitives, the ability to create a set of bounding boxes to bound all of the primitives would also be capable as well.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to have modified Jesus in view of Doyle and Fenney to incorporate the teachings of Morrical so that additional bounding boxes could be incorporated into the method which would help improve overall processing times by incorporating parallel processing for help in generating data.
Additionally, Jesus in view of Doyle, Fenney and Morrical disclose when it is determined that the supplementary information indicates that a region of plural regions that the packet bounding box overlaps that corresponds to the rendering tile contains at least one of the primitives that the packet bounding box bounds:
loading the packet (Paragraph 238 of Morrical teaches that in at least one embodiment, pipeline manager 2602 is configured to route packets received from a work distribution unit to appropriate logical units within GPC 2600 and, in at least one embodiment, some packets may be routed to fixed function hardware units in PROP 2604 and/or raster engine 2608 while other packets may be routed to DPCs 2606 for processing by a primitive engine 2612 or SM 2614. Additionally, paragraph 240 of Morrical teaches that in at least one embodiment, packets associated with a vertex are routed to primitive engine 2612, which is configured to fetch vertex attributes associated with vertex from memory.);
and determining whether the rendering tile overlaps a lower level bounding box of the hierarchy of bounding boxes that is stored in the packet (Col. 39, Lines 16-23 of Jesus teach that in some cases, a primitive block entry may additionally or alternatively comprise a coverage mask that indicates, which tiles that overlap with the bounding box for the primitive block, are valid for the primitive block. As described above, in some cases the coverage mask may be implemented as a hierarchical coverage mask that is generated by dividing a block of relevant tiles into successively smaller areas and storing information in the coverage mask for each area.).
Regarding claim 18, the system steps correlate to and are rejected similarly to method steps from claim 8 (see claim 8 above).
Claims 6 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Jesus in view of Doyle and Fenney, as applied to claim 5 above, and further in view Goswami et al. (Pub. No.: US 2023/0334736 A1), hereinafter Goswami.
Regarding claim 6, Jesus in view of Doyle and Fenney disclose everything claimed as applied above (see claim 5), in addition, Jesus in view of Doyle and Fenney disclose comprising generating the array by, for each primitive that the bounding box bounds:
expanding a bounding box to bound the respective primitive (FIG. 8 and Col. 8, Lines 50-52 of Jesus teach that FIG. 8 is a schematic diagram illustrating expanding the tiles in a render space to a square set of tiles with power of two sides. Additionally, Col. 59, Lines 32-33 of Doyle teach that each inner node 4610 corresponds to a bounding volume which is typically an axis-aligned bounding box and Col. 63, Lines 55-63 of Doyle teach that at 4850 a BVH refit operation is initiated. At 4851 the first/next BVH node is evaluated based on data for its child nodes. As mentioned, this data may indicate whether the child nodes have been enlarged, reduced or moved. As determined at 4852, if the current BVH node needs to be enlarged because it's child nodes have moved outside of its current boundaries (e.g., either through movement or enlargement), then the BVH refit is not terminated and is allowed to proceed at 4856. ). However, Jesus in view of Doyle and Fenney fail to disclose determining whether a size of the expanded bounding box is greater than a size that the array can currently accommodate.
Goswami discloses determining whether a size of the expanded bounding box is greater than a size that the array can currently accommodate (Paragraph 58 teaches that in particular embodiments, a shape walker 130 may be configured to examine, prior to determining coverage weights of pixels that are fully outside or inside a primitive and prior to flagging pixels that are intersecting with an edge of a primitive, whether the tile bounding box is bigger than a minimal threshold size. If the bounding box is smaller than a minimal threshold size (such as 1×1 pixel or 2×2 pixels), a shape walker 130 may be configured to send all of the pixels within the bounding box to an integrator 140 to determine their respective coverage weight, rather than going through the steps described in the preceding paragraphs. In an embodiment, determining whether the bounding box is bigger than a threshold size may be implemented for a trapezoid but not for a quadratic curve.). Since Jesus in view of Doyle and Fenney teach the initial method steps for determining the array and its size and the ability to expand a bounding box and Goswami teaches the capability of determining whether the size of a bounding box is greater than a minimal threshold size, it would have been obvious to a person having ordinary skill in the art to combine the features together so that by determining if the size of the bounding box is greater than a certain size, then that data and functionality could be used to determine if the size of the expanded bounding box is greater than a certain size that the array can accommodate.
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing data of the claimed invention to have modified Jesus in view of Doyle and Fenney to incorporate the teachings of Goswami so that by combining the features and functionality together, the size threshold for the expanded bounding box could be tested against the maximum accommodating size of the array and by ensuring that the bounding box could fit within the array, the resulting data can then be loaded and processed more efficiently within a tile based graphics processing system.
Additionally, Jesus in view of Doyle, Fenney and Goswami disclose when it is determined that a size of the expanded bounding box is greater than a size that the array can currently accommodate:
increasing a size of the plural regions (Col. 13, Line 57 Through Col. 14, Line 3 of Jesus teach that in some cases, where each level k tile group comprises a h.sup.k×h.sup.k block of tiles, and the tiles forming the render space do not form a w×q block of tiles wherein both w and q are a power of h then rows and/or columns of phantom tiles may be added to the tiles in the rendering space to generate a w×q block of tiles wherein w and q are a power of h before a multi-level hierarchy of tile groups is generated. The term phantom tile or empty tile is used herein to mean a tile that does not form part of the rendering space. For example, as shown in FIG. 8, if h=2, and the tiles forming the rendering space 802 form a 5×7 block of tiles, three columns 804.sub.0, 804.sub.1, 804.sub.2 and one row 806 of phantom tiles may be added to the tiles forming the rendering space to form an 8×8 block of tiles.).
Regarding claim 16, the system steps correlate to and are rejected similarly to method steps from claim 6 (see claim 6 above).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Rhoades et al. (U.S. Patent: #9,536,341 B1) teaches distributing primitives to multiple Rasterizers
Boudier (U.S. Patent: #9,905,037 B2) teaches a system and method for rejecting small primitives.
13. 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.
14. Any inquiry concerning this communication or earlier communications from the examiner should be directed to George Renze whose telephone number is (703)756-5811. The examiner can normally be reached Monday-Friday 9:00am - 6:00pm EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Xiao Wu can be reached at (571) 272-7761. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/G.R./Examiner, Art Unit 2613
/XIAO M WU/Supervisory Patent Examiner, Art Unit 2613
Prosecution Insights