DETAILED ACTION
This office action is responsive to applicant’s communications filed 02/27/2026.
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 Arguments
Applicant’s arguments with respect to the rejection of claim(s) 1, 8, and 15 under 35 U.S.C. 103 with regard to the parallelization of reduction and sorting operations within individual data clusters 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. Claims 1 and 8 are rejected with the combination of García and Ganestam; claim 15 is rejected with the combination of García, Ganestam, and Harada.
Additionally, with respect to the rejection of claim 15 under 35 U.S.C. 103, applicant argues that the stable sort of Harada is “not tied to hierarchical node generation based on cluster-level spatial reductions”. However, Harada is not relied upon to teach the claim limitations associated with this argument. Ganestam section 5.3 “Mini Tree Construction” (pg. 30) specifies that each mini tree can be generated in parallel with any BVH generation method; therefore, a stable sort operation applied within a single mini tree will necessarily be “tied to hierarchical node generation based on cluster-level spatial reductions”, where the primitives of a single mini tree constitute a cluster; see “Claim Rejections - 35 USC § 103” section for additional explanation.
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.
Claim(s) 1, 4, 5, 7, 8, 11, 12, 14, 15, 18, and 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over García et al. (“Fast parallel construction of stack-less complete LBVH trees with efficient bit-trail traversal for ray tracing”. VRCAI '14: Proceedings of the 13th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and its Applications in Industry (30 Nov 2014), pp. 151-158. https://doi.org/10.1145/2670473.2670488; hereinafter “García”) in view of Ganestam et al. (“Bonsai: Rapid Bounding Volume Hierarchy Generation using Mini Trees”. Journal of Computer Graphics Techniques, vol. 4 no. 3 (2015), pp. 23-42. https://jcgt.org/published/0004/03/02/; hereinafter “Ganestam”).
Regarding claim 1, García teaches: A system comprising:
first processing circuitry (section 1 “Introduction”: “…the splitting method is described and then the fast parallel construction of the acceleration structure on GPU”) configured to perform one or more reduction operations on a plurality of data clusters to generate one or more sorting keys (García fig. 5; pg. 153 section 3.3 “Space Partitioning” teaches that the sorting key is the position along the longest axis of the axis-aligned bounding box; section 3.3.1 “Find the Longest Axis”: “This is determined by doing a parallel reduction… Our function returns the longest axis by calculating the max and min values in x, y, and z of an array of primitives, then the function calculates the distance between the max and min points for each axis and returns the axis that has the longest distance.”);
second processing circuitry configured to iteratively sort, using the one or more sorting keys, a set of geometrical primitives represented in the plurality of data clusters to generate nodes representing a hierarchical acceleration structure (section 3.3.3 “Sort Primitives”: “A fast data parallel radix sort implementation is used to sort the primitives against the split axis in ascending order based on the centroids computed on the pre-build stage.”); and
circuitry configured to perform a rendering operation using the hierarchical acceleration structure (García fig. 9, pg. 155 section 5 “Results” shows examples of 3D models rendered using the bounding volume hierarchy described above, and lists the computational hardware used to perform the rendering).
García is not relied upon to teach the completely parallelized operations happening concurrently and equivalently in multiple clusters, specifically the limitations:
first processing circuitry configured to perform one or more reduction operations on each data cluster of a plurality of data clusters, wherein reduction operations for at least two of the plurality of data clusters are active concurrently, to generate one or more sorting keys, each sorting key being maintained in association with its corresponding data cluster; or
second processing circuitry configured to iteratively sort within each of the at least two of the plurality of data clusters, using the one or more sorting keys, a set of geometrical primitives represented in each data cluster of the plurality of data clusters to generate nodes representing a hierarchical acceleration structure.
Ganestam teaches a method of dividing primitives into initial groups, and generating a mini tree for each group of primitives (fig. 2 pg. 28). Section 5.3 “Mini Tree Construction” (pg. 30) describes how once the primitives for each mini tree are selected, each mini tree may be generated completely independently and in parallel to the others, with a different thread dedicated to each tree. It also teaches that any BVH generating method may be used to generate the mini trees. If the system of García is used to generate the mini trees, then the operations taught by García would be isolated to each mini tree, and would be performed on each mini tree concurrently due to the parallelization taught by Ganestam. Therefore, the combination of García and Ganestam teaches performing reduction operations on each data cluster of a plurality of data clusters, wherein reduction operations for at least two of the plurality of data clusters are active concurrently, generating sorting keys with each sorting key being maintained in association with its corresponding data cluster, and sorting, within each of the at least two of the plurality of data clusters, primitives represented in each data cluster of the plurality of data clusters (where the groups of primitives comprising each mini tree of Ganestam correspond to the claimed “data clusters”).
García and Ganestam are analogous to the claimed invention because they are in the same field of constructing a bounding volume hierarchy to accelerate ray tracing. 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 the invention of García with the teachings of Ganestam to generate the mini trees of Ganestam using the BVH generation system of García. The motivation would have been to further increase efficiency by improving parallelization, which was stated to be one of the goals of both García and Ganestam.
Regarding claim 4, the combination of García in view of Ganestam teaches: The system as claimed in claim 1, wherein the second processing circuitry is configured to re-sort, within each data cluster, the geometrical primitives using a second sort key to generate a second set of data clusters (Ganestam pg. 27 paragraphs 1-3 describe how primitives which are sorted along each axis are further sorted into two partitions based on a splitting plane which is positioned based on the optimized SAH metric; the process is recursive and can generate increasingly smaller sets of partitions. The process is referred to as “partitioning” but is functionally similar to the process described in the specification in which primitives are sorted by cluster; a primitive’s position relative to the splitting plane acts as the sorting key.).
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 the invention of García in view of Ganestam with the additional teachings of Ganestam to implement aspects of the variation of the SweepSAH algorithm taught by Ganestam, which includes the methodology described above. The motivation would have been to improve performance using the SAH metric to partition a tree while also improving efficiency, as Ganestam’s algorithm only requires a full sort to be performed once.
Regarding claim 5, the combination of García in view of Ganestam teaches: The system as claimed in claim 4, wherein the second sort key is generated based at least in part on a cluster identifier associated with each data cluster (Ganestam pg. 27 paragraph 3: primitives are flagged depending on which side of a split plane they are positioned; the flag subsequently acts as a partition identifier when sorting the primitives into two partitions).
The additional teachings of Ganestam are part of the same process referenced in claim 4; therefore, the motivation to combine would have been similar to the motivation described for claim 4.
Regarding claim 7, the combination of García in view of Ganestam teaches: The system as claimed in claim 1, wherein the one or more reduction operations for a given data cluster comprise computing extents along each axis for a set of primitives in the given data cluster, wherein the extents along each axis represent minimum and maximum coordinates of the set of primitives along each axis (García section 3.3.1 “Find the Longest Axis”: “This is determined by doing a parallel reduction… Our function returns the longest axis by calculating the max and min values in x, y, and z of an array of primitives, then the function calculates the distance between the max and min points for each axis and returns the axis that has the longest distance.”).
Regarding claims 8, 11, 12, and 14, their limitations substantially correspond to the limitations of claims 1, 4, 5, and 7 respectively; therefore, they are rejected with the same references, rationale, and motivation to combine as their corresponding claims.
Regarding claim 15, most of its limitations correspond to limitations found in claim 1, along with the additional limitations of: wherein the one or more reduction operations comprise computing one or more spatial properties of primitives within the data cluster (García section 3.3.1 “Find the longest axis” describes a process for performing a parallel reduction involving determining the spatial positioning of primitives; if the reduction process is being performed for a single mini-tree as taught by Ganestam as explained in claim 1, then it is “within the data cluster”); and: wherein the sorting is performed using a stable sort operation (García section 3.3.3 “Sort Primitives”: “A fast data parallel radix sort implementation is used to sort the primitives against the split axis in ascending order based on the centroids computed on the pre-build stage”; the radix sort operation is stable, as clarified by Harada pg. 1 col. 1).
Regarding claims 18 and 20, their limitations substantially correspond to the limitations of claims 5 and 7 respectively; therefore, they are rejected with the same references, rationale, and motivation to combine as their corresponding claims.
Claim(s) 2, 9, and 16 is/are rejected under 35 U.S.C. 103 as being unpatentable over García (“Fast parallel construction of stack-less complete LBVH trees with efficient bit-trail traversal for ray tracing”) in view of Ganestam (“Bonsai: Rapid Bounding Volume Hierarchy Generation using Mini Trees”) as applied to claims 1 and 8 above, and further in view of Wald, Ingo. (“On fast Construction of SAH-based Bounding Volume Hierarchies”. 2007 IEEE Symposium on Interactive Ray Tracing (Sep 2007). https://doi.org/10.1109/RT.2007.4342588; hereinafter “Wald”).
Regarding claim 2, the combination of García in view of Ganestam teaches: The system as claimed in claim 1, but does not explicitly teach: wherein the second processing circuitry is configured to repeatedly sort the set of geometrical primitives within each data cluster until a termination condition is met, the termination condition comprising at least one of reaching a maximum number of geometrical primitives in each data cluster, reaching a minimum number of data clusters, or a size of each data cluster in the first set of data clusters being less than or equal to a threshold.
Wald teaches: wherein the second processing circuitry is configured to repeatedly sort the set of geometrical primitives within each data cluster until a termination condition is met, the termination condition comprising at least one of reaching a maximum number of geometrical primitives in each data cluster, reaching a minimum number of data clusters, or a size of each data cluster in the first set of data clusters being less than or equal to a threshold. (Wald pg. 37 section 3.8 “Termination”: “As usual for SAH-based builds, we terminate the recursion until either a) a certain threshold of triangles is reached (in our case, usually 2 or 4), b) until the centroid bounds becomes too small (in which case binning it would not make sense any more), or c) until the estimated cost is higher than the estimated cost for making a leaf.”).
Wald and the combination of García in view of Ganestam are analogous to the claimed invention because they are in the same field of constructing a bounding volume hierarchy to accelerate ray tracing. 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 the invention of García in view of Ganestam with the teachings of Wald to impose a termination condition on the recursive process of the bounding tree hierarchy construction. The motivation would have been to allow the invention to use a more adaptable partitioning method such as the surface area heuristic (SAH) method of Wald, which does not have a predefined structure like the method of García; this may improve BVH performance.
Regarding claims 9 and 16, their limitations substantially correspond to the limitations of claim 2; therefore, they are rejected with the same references, rationale, and motivation to combine as claim 2.
Claim(s) 3, 10, and 17 is/are rejected under 35 U.S.C. 103 as being unpatentable over García (“Fast parallel construction of stack-less complete LBVH trees with efficient bit-trail traversal for ray tracing”) in view of Ganestam (“Bonsai: Rapid Bounding Volume Hierarchy Generation using Mini Trees”) as applied to claims 1 and 8 above, and further in view of Pantaleoni et al. (“HLBVH: hierarchical LBVH construction for real-time ray tracing of dynamic geometry”. HPG '10: Proceedings of the Conference on High Performance Graphics (25 Jun 2010), pp. 87-95. https://dl.acm.org/doi/10.5555/1921479.1921493; hereinafter “Pantaleoni”).
Regarding claim 3, the combination of García in view of Ganestam teaches: The system as claimed in claim 1, but does not explicitly teach: wherein the second processing circuitry is configured to generate, based at least in part on sorting the set of geometrical primitives by a first sort key, a data cluster leader from the first set of data clusters for at least one data cluster of the plurality of data clusters..
Pantaleoni teaches: wherein the second processing circuitry is configured to generate, based at least in part on sorting the set of geometrical primitives by a first sort key, a data cluster leader from the first set of data clusters for at least one data cluster of the plurality of data clusters. (pg. 89 section 3.1 “Primitive Sorting”: “The top level primitive sorting step starts run-length encoding the codes by their high 3m bits, applying a compaction kernel to extract a list of indices pointing to the beginning of each run, obtaining an array with M ≤ N items called run_heads.” – each of these items is representative of a run of primitives, and can be used to access them more efficiently).
Pantaleoni and the combination of García in view of Ganestam are analogous to the claimed invention because they are in the same field of constructing a bounding volume hierarchy to accelerate ray tracing. 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 the invention of García in view of Ganestam with the teachings of Pantaleoni to implement aspects of the sorting algorithm taught by Pantaleoni, which includes the methodology described above. The invention of García in view of Ganestam uses a radix sorting algorithm, and Pantaleoni teaches several advantages over a global radix sort, any of which may have served as motivation to combine these references, including “reduced work and global memory traffic”, “reduced global synchronization points”, and “greater efficiency” (pg. 89 section 3.1 “Primitive Sorting”).
Regarding claims 10 and 17, their limitations substantially correspond to the limitations of claim 3; therefore, they are rejected with the same references, rationale, and motivation to combine as claim 3.
Claim(s) 6, 13, and 19 is/are rejected under 35 U.S.C. 103 as being unpatentable over García (“Fast parallel construction of stack-less complete LBVH trees with efficient bit-trail traversal for ray tracing”) in view of Ganestam (“Bonsai: Rapid Bounding Volume Hierarchy Generation using Mini Trees”) as applied to claims 1 and 8 above, and further in view of Harada et al. (“Introduction to GPU Radix Sort”. Heterogeneous Computing with OpenCL (2011). https://hgpu.org/?p=5888; hereinafter “Harada”).
Regarding claim 6, the combination of the combination of García in view of Ganestam teaches: The system as claimed in claim 1, but does not explicitly teach: wherein second processing circuitry is configured to sort the set of geometrical primitives by performing one of wave-wide sort operations and group-wide sort operations.
Harada teaches: wherein second processing circuitry is configured to sort the set of geometrical primitives by performing one of wave-wide sort operations and group-wide sort operations (pg. 1 col. 2: “Executing the number of work items equal to the SIMD width is necessary to fully utilize the wide SIMD architecture. Thus we need another level of parallelization in a work group.”; fig. 4 “A SIMD engine reads 256 keys and sorts locally and write them back to memory.”; pg. 3 col. 1 describes how the value of 256 elements is tied to the work group size).
Harada is analogous to the claimed invention because it pertains to the same problem of performing a parallelized sorting operation on a GPU. Furthermore, both García and Harada teach the same parallelized sorting implementation (radix sort: García section 3.3.3, Harada entire paper). 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 the invention of García in view of Ganestam with the teachings of Harada to perform a simultaneous sorting operation using all lanes of a SIMD unit (a “group-wide” operation). The motivation would have been to maximize parallelization, and therefore efficiency, during the sorting operation.
Regarding claims 13 and 19, their limitations substantially correspond to the limitations of claim 6; therefore, they are rejected with the same references, rationale, and motivation to combine as claim 6.
References Cited
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Zhou et al. (US 20100079452 A1) teaches a method of parallelizing the generation of an acceleration structure by dividing primitives into chunks and performing reduction and sorting operations on each chunk separately (see the algorithm described in paragraph [0037]) – relevant to the amended claims 1, 8, and 15.
Meister et al. ("A Survey on Bounding Volume Hierarchies for Ray Tracing". Computer Graphics Forum, vol. 40 no. 2 (04 Jun 2021), pp. 683-712. https://doi.org/10.1111/cgf.142662) provides an overview of the state of the art of bounding volume hierarchy construction as of 2021.
Vijaya et al. ("Leaders–Subleaders: An efficient hierarchical clustering algorithm for large data sets". Pattern Recognition Letters, vol. 25 no. 4 (Mar 2004), pp. 505-513. https://doi.org/10.1016/j.patrec.2003.12.013) describes a hierarchical clustering algorithm which generates cluster leaders each representative of a cluster – relevant to claims 3, 10, and 17.
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 BENJAMIN STATZ whose telephone number is (571)272-6654. The examiner can normally be reached Mon-Fri 8am-5pm.
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, Tammy Goddard can be reached at (571)272-7773. 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.
/BENJAMIN TOM STATZ/ Examiner, Art Unit 2611
/TAMMY PAIGE GODDARD/ Supervisory Patent Examiner, Art Unit 2611
Prosecution Insights