Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
DETAILED ACTION
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-4, 10-13, 19-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
Regarding independent claim 1, the claim directs to “a method for generating a bounding volume hierarchy (“BVH”), the method comprising: identifying that a number of uncombined descendants for a node of an initial BVH, is greater than or equal to a threshold; and in response to the identifying, combining the uncombined descendants to form a subtree to add to a new BVH” which is a process and falls within one of the statutory categories of invention.
The claim recites:
The steps of “identifying that a number of uncombined descendants for a node of an initial BVH, is greater than or equal to a threshold” encompasses mathematical relationships that can be performed mentally. The broadest reasonable interpretation, the identifying limitation, as drafted, is process that covers performance of the limitation in human mind with pen and paper to compare between identifying a number with a threshold. The claim covers performance of the limitation in human mind using observation, analyzation and judgment. The limitation falls within the “mental process” and “mathematical relationships” group of abstract idea.
The step of “in response to the identifying, combining the uncombined descendants to form a subtree to add to a new BVH” which encompasses observing a data and performing judgment. That covers performance of the limitation in human mind or by hand with pen and paper. Such mental observation/judgment fall within “mental process” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
This judicial exception is not integrated into a practical application. In particular, the claim recites additional “bounding volume hierarchy (“BVH”), see Figure 4 and paragraph [0036] “The spatial representation 402 of the bounding volume hierarchy is illustrated in the left side of Figure 4 and the tree representation 404 of the bounding volume hierarchy is illustrated in the right side of Figure 4…”. The bounding volume hierarchy is tree structure that a human could mentally perform with a pen and paper. Accordingly, the claim as a whole does not integrate this judicial exception into a practical application because the claim does not prove an improvement to functioning of computers or an improvement to other technology or technical field. The claim is directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to significantly more than the judicial exception. The claim is not patent eligible.
Claim 2 depends from claim 1, recites “wherein each uncombined descendant is a node of the new BVH for which no node of the new BVH is a parent” may be practically performing in human mind with pen and paper. The broadest reasonable interpretation, the identifying limitation, as drafted, is process that covers performance of the limitation in human mind using observation, analyzation and determination. The limitation falls within the “mental process” group of abstract idea.
This judicial exception is not integrated into a practical application because the claim does not recite any additional elements beyond the judicial exception. Accordingly, the claim as a whole does not integrate this judicial exception into a practical application because the claim does not prove an improvement to functioning of computers or an improvement to other technology or technical field. The claim is directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to significantly more than the judicial exception. The claim is not patent eligible.
Claim 3 depends from claim 1 recites “wherein combining the uncombined descendants includes selecting uncombined descendants from the uncombined descendants for the node based on a selection criterion, forming a new node for the BVH, and setting, as parent for the selected uncombined descendants, the new node” may be practically performing in human mind with pen and paper. The broadest reasonable interpretation, the identifying limitation, as drafted, is process that covers performance of the limitation in human mind using analyzation, determination and performing judgment. The limitation falls within the “mental process” group of abstract idea.
This judicial exception is not integrated into a practical application because the claim does not recite any additional elements beyond the judicial exception. Accordingly, the claim as a whole does not integrate this judicial exception into a practical application because the claim does not prove an improvement to functioning of computers or an improvement to other technology or technical field. The claim is directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to significantly more than the judicial exception. The claim is not patent eligible.
Claim 4 depends from claim 3 recites “repeating the combining until the number of uncombined descendants for the node is less than the threshold” encompasses mathematical relationships that can be performed mentally. The broadest reasonable interpretation, the identifying limitation, as drafted, is process that covers performance of the limitation in human mind using observation, analyzation and determination. The limitation falls within the “mental process” and “mathematical relationships” group of abstract idea.
This judicial exception is not integrated into a practical application because the claim does not recite any additional elements beyond the judicial exception. Accordingly, the claim as a whole does not integrate this judicial exception into a practical application because the claim does not prove an improvement to functioning of computers or an improvement to other technology or technical field. The claim is directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to significantly more than the judicial exception. The claim is not patent eligible.
Regarding independent claim 10, the claim directs to “A system for generating a bounding volume hierarchy (“BVH”), the system comprising: a memory configured to store information for a new BVH; and a processor configured to perform operations comprising: identifying that a number of uncombined descendants for a node of an initial BVH, is greater than or equal to a threshold; and in response to the identifying, combining the uncombined descendants to form a subtree to add to the new BVH.” which is machine and falls withing one of the statutory categories of invention. The claim recites:
The step of “store information for a new BVH” is merely gather and keep information. The broadest reasonable interpretation, the identifying limitation, as drafted, is process that covers performance of the limitation in human mind or by hand with a pen and paper. The limitation falls within the “mental process” group of abstract idea.
The steps of “identifying that a number of uncombined descendants for a node of an initial BVH, is greater than or equal to a threshold” encompasses mathematical relationships that can be performed mentally. The broadest reasonable interpretation, the identifying limitation, as drafted, is process that covers performance of the limitation in human mind with pen and paper to compare between identifying a number with a threshold. The limitation falls within the “mental” process” and “mathematical relationships” group of abstract idea.
The step of “in response to the identifying, combining the uncombined descendants to form a subtree to add to a new BVH” which encompasses observing a data and performing judgment. That covers performance of the limitation in human mind or by hand with pen and paper. Such mental observation/judgment fall within “mental process” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
This judicial exception is not integrated into a practical application. In particular, the claim recites additional “bounding volume hierarchy (“BVH”), see Figure 4 and paragraph [0036] “The spatial representation 402 of the bounding volume hierarchy is illustrated in the left side of Figure 4 and the tree representation 404 of the bounding volume hierarchy is illustrated in the right side of Figure 4…”. The bounding volume hierarchy is tree structure that a human could mentally perform with a pen and paper. Further, the claim recites additional elements “a memory”, “a processor” which are considered as components of computer to perform functions/operations steps. Using a generic computer component cannot provide an invention concepts.
Accordingly, the claim as a whole does not integrate this judicial exception into a practical application because the claim does not prove an improvement to functioning of computers or an improvement to other technology or technical field. The claim is directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to significantly more than the judicial exception. The claim is not patent eligible.
Claim 11 depends from claim 10 recites limitations is similar in scope to claim 2 and therefore rejected under the same rationale.
Claim 12 depends from claim 10 recites limitations is similar in scope to claim 3 and therefore rejected under the same rationale.
Claim 13 depends from claim 12 recites limitations is similar in scope to claim 4 and therefore rejected under the same rationale.
Regarding independent claim 19, the claim recites “a non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to perform operations comprising: identifying that a number of uncombined descendants for a node of an initial BVH, is greater than or equal to a threshold; and in response to the identifying, combining the uncombined descendants to form a subtree to add to a new BVH.” Which is a manufacture and falls within one of the statutory categories of invention.
The claim recites:
The step of “store information for a new BVH” is merely gather and keep information. The broadest reasonable interpretation, the identifying limitation, as drafted, is process that covers performance of the limitation in human mind or by hand with a pen and paper. The limitation falls within the “mental process” group of abstract idea.
The steps of “identifying that a number of uncombined descendants for a node of an initial BVH, is greater than or equal to a threshold” encompasses mathematical relationships that can be performed mentally. The broadest reasonable interpretation, the identifying limitation, as drafted, is process that covers performance of the limitation in human mind with pen and paper to compare between identifying a number with a threshold. The limitation falls within the “mental process” and “mathematical relationships” group of abstract idea.
The step of “in response to the identifying, combining the uncombined descendants to form a subtree to add to a new BVH” which encompasses observing a data and performing judgment. That covers performance of the limitation in human mind or by hand with pen and paper. Such mental observation/judgment fall within “mental process” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
This judicial exception is not integrated into a practical application. In particular, the claim recites additional “bounding volume hierarchy (“BVH”), see Figure 4 and paragraph [0036] “The spatial representation 402 of the bounding volume hierarchy is illustrated in the left side of Figure 4 and the tree representation 404 of the bounding volume hierarchy is illustrated in the right side of Figure 4…”. The bounding volume hierarchy is tree structure that a human could mentally perform with a pen and paper. Further, the claim recites additional elements: a non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to perform operations” which is considered as components of computer to perform functions/operations steps. Using a generic computer component cannot provide an invention concepts.
Accordingly, the claim as a whole does not integrate this judicial exception into a practical application because the claim does not prove an improvement to functioning of computers or an improvement to other technology or technical field. The claim is directed to an abstract idea.
The claim does not recite additional elements that are sufficient to amount to significantly more than the judicial exception. The claim is not patent eligible.
Claim 20 depends from claim 19 recites limitations is similar in scope to claim 2 and therefore rejected under the same rationale.
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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
1. Claims 1-4, 10-13 and 19-20 are rejected under 35 U.S.C. 103 as being unpatentable over Alila et al., U.S Patent Application Publication No. 20140365529 (“Aila”) in view of MEISTER, D. & BITTNER, J.; IDS, "Parallel Locally-Ordered Clustering for Bounding Volume Hierarchy Construction", IEEE Transactions on Visualization and Computer Graphics (Preprint), IEEE, 2017, 9 pgs.(“MEISTER”)
Regarding independent claim 1, Aila teaches a method for generating a bounding volume hierarchy (“BVH”) ([0028] FIG. 1 illustrates a flowchart of a method 100 for generating a hierarchical tree data structure, in accordance with one embodiment. At step 105, an initial hierarchical tree data structure is received. In one embodiment, the hierarchical tree data structure may be a BVH.”, Figs 2A-2C, Fig.3), the method comprising:
identifying that a number of uncombined descendants for a node of an initial BVH ([0038] FIG. 2A illustrates a conceptual diagram of a hierarchical data structure represented by a tree 200, in accordance with one embodiment. The tree includes a treelet 260 of 7 treelet leaf nodes and 6 treelet internal nodes, including a root node 210. The nodes 205, 206, 208, and 212 and leaf nodes 207, 209, 215, and 217 are outside of the treelet 260. The leaf nodes of the treelet 260 can either be actual leaf nodes (e.g., 227, 229, 225, and 243) or arbitrary sub-trees (e.g., nodes 232, 244, and 250). The nodes 236, 237, 239, and 233 are descendants of the treelet leaf node 232 and form a subtree that is represented by the treelet leaf node 232. Similarly, the nodes 245 and 247 are descendants of the treelet leaf node 244 and form a subtree that is represented by the treelet leaf node 244. Finally, the nodes 253 and 255 are descendants of the treelet leaf node 250 and form a subtree that is represented by the treelet leaf node 250. Nodes 210, 220, 224, 230, 240, and 242 are the internal nodes of the treelet 260.”; [0054] At step 310, a set of nodes to be used as treelet roots is identified. To identify the roots, the parallel bottom-up traversal algorithm presented by Karras in 2012 may be used. The algorithm works by traversing paths from the hierarchical tree data structure leaf nodes to the root in parallel, using atomic counters to terminate a first execution thread to enter any given node while allowing a second execution thread to proceed. The algorithm guarantees that the nodes are visited in a strict bottom up order: when a particular node is visited during the traversal, all of the node's descendants have already been visited. Therefore, the descendants may be restructured without the danger of other execution threads trying to access the descendants during the restructuring. The bottom-up traversal also provides a very natural way to propagate SAH costs of each node up the tree.” ) is greater than or equal to a threshold ([0085] FIG. 5B illustrates a flowchart of a method 505 for restructuring a treelet, accordance with one embodiment. Although the method 505 is described in the context of a program executed by a processor, the method 505 may also be performed by custom circuitry or by a combination of custom circuitry and a program. At step 507, a set of treelet leaf nodes is received where a treelet leaf node either corresponds to an actual leaf node of the BVH or acts as a representative of an arbitrary subtree within the initial hierarchical tree data structure. In one embodiment, a processing thread may be allocated and launched to process each node in the set. At step 510, the processor determines if more than one node remains in the set of nodes yet to merged, and, if not, the process terminates and the treelet has been restructured.”; [0090] FIG. 5C illustrates example code 535 for restructuring a treelet using agglomerative clustering, in accordance with one embodiment. The example code 535 may be implemented to perform the method 505 shown in FIG. 5B. As previously described in conjunction with step 515, an O(n.sup.2) search is performed over the nodes in the set and the result of the MergeCost evaluation for the node pairs is used to merge as many nodes as possible during each iteration. The set N (line 1) represents the nodes yet to be merged, and the main loop (lines 2-19) is executed until there is only one node remaining. For each iteration, a node pairing having the lowest cost is determined for each node in the set (lines 3-11). For node n, finding the node pairing with the lowest cost is a matter of considering each node p in turn (line 5), calculating the expected cost of merging n and p (line 6), and choosing the pair that gives the lowest cost c.sub.n (line 7). After the lowest cost pairing is determined for each node, the reciprocating node pairs may be identified. To perform the merges, the code loops over the nodes (line 12), identifies the reciprocating node pairs (lines 13), and merges the nodes of reciprocating node pairs (lines 14-16). [0091] In practice, the algorithm can be parallelized over a group of threads by assigning one of the treelet leaf nodes to each thread. Both phases of the algorithm (lines 3-11 and lines 12-19) parallelize naturally over the set N. However, the execution of the threads should be synchronized when transitioning from one phase to the other. When performing a merge (lines 14-16), the newly created internal node r is assigned to the thread that was responsible for n, and the thread that was responsible for P[n] exits the loop. As an additional performance optimization, it is possible to abort the agglomerative merging of nodes when less than a fixed number of nodes remain (i.e. |N|<T on line 2). This will not reduce the quality of the resulting BVH as long as processing of the next treelet in bottom-up order searches all of the T nodes for reciprocating node pairs.” Where abort the agglomerative merging of nodes when less than a fixed number of nodes remains which means the agglomerative merging of nodes when greater or equal to a fixed number of nodes remains (a threshold) );
in response to the identifying, combining the uncombined descendants to form a subtree to BVH ([0083] Generally, agglomerative clustering operates by merging nodes in a bottom-up fashion, maintaining a set of nodes yet to be merged. An agglomerative clustering algorithm starts with the individual treelet leaf nodes, and, in each iteration of processing, out of the set of nodes yet to be merged, the two whose union has the lowest surface area is identified. The two nodes are then merged by creating a new internal node. Repeating the algorithm, the newly created internal nodes will eventually be merged in the same fashion until only one node remains: the root node of the resulting BVH. Walter et al. 2008 "Fast agglomerative clustering for rendering" In Proc. IEEE Symposium on Interactive Ray Tracing, describes using an agglomerative clustering technique to construct a BVH for rendering without restructuring the BVH”; [0085] FIG. 5B illustrates a flowchart of a method 505 for restructuring a treelet, accordance with one embodiment. Although the method 505 is described in the context of a program executed by a processor, the method 505 may also be performed by custom circuitry or by a combination of custom circuitry and a program. At step 507, a set of treelet leaf nodes is received where a treelet leaf node either corresponds to an actual leaf node of the BVH or acts as a representative of an arbitrary subtree within the initial hierarchical tree data structure. In one embodiment, a processing thread may be allocated and launched to process each node in the set. At step 510, the processor determines if more than one node remains in the set of nodes yet to merged, and, if not, the process terminates and the treelet has been restructured.”; [0087] The MERGECOST cost function estimates the difference in the overall SAH cost between two cases: (1) merging the two nodes with each other; and (2) merging the two nodes with some other nodes. A given node i contributes to the overall SAH cost in two ways: (1) descendants of the node contribute C(i); and (2) ancestors of the node contribute some unknown amount that may be estimated to be A(i)*Z. In effect, MERGECOST(a, b) is the total contribution of the newly created internal node minus the total contributions of node a and node b. [0090] FIG. 5C illustrates example code 535 for restructuring a treelet using agglomerative clustering, in accordance with one embodiment. The example code 535 may be implemented to perform the method 505 shown in FIG. 5B. As previously described in conjunction with step 515, an O(n.sup.2) search is performed over the nodes in the set and the result of the MergeCost evaluation for the node pairs is used to merge as many nodes as possible during each iteration. The set N (line 1) represents the nodes yet to be merged, and the main loop (lines 2-19) is executed until there is only one node remaining. For each iteration, a node pairing having the lowest cost is determined for each node in the set (lines 3-11). For node n, finding the node pairing with the lowest cost is a matter of considering each node p in turn (line 5), calculating the expected cost of merging n and p (line 6), and choosing the pair that gives the lowest cost c.sub.n (line 7). After the lowest cost pairing is determined for each node, the reciprocating node pairs may be identified. To perform the merges, the code loops over the nodes (line 12), identifies the reciprocating node pairs (lines 13), and merges the nodes of reciprocating node pairs (lines 14-16). [0091] In practice, the algorithm can be parallelized over a group of threads by assigning one of the treelet leaf nodes to each thread. Both phases of the algorithm (lines 3-11 and lines 12-19) parallelize naturally over the set N. However, the execution of the threads should be synchronized when transitioning from one phase to the other. When performing a merge (lines 14-16), the newly created internal node r is assigned to the thread that was responsible for n, and the thread that was responsible for P[n] exits the loop. As an additional performance optimization, it is possible to abort the agglomerative merging of nodes when less than a fixed number of nodes remain (i.e. |N|<T on line 2). This will not reduce the quality of the resulting BVH as long as processing of the next treelet in bottom-up order searches all of the T nodes for reciprocating node pairs.”; ) Alia is understood to be silent on the remaining limitations of claim 1.
In the same field of endeavor, Meister teaches in response to the identifying, combining the uncombined descendants to form a subtree to add to a new BVH (see whole paper, at least 3 BVH CONSTRUCTION VIA AGGLOMERATIVE CLUSTERING, 3.1 Parallel Locally-Ordered Clustering “The agglomerative clustering algorithm starts with the scene triangles trivially forming n clusters with a single triangle per cluster (n is the number of triangles). These clusters correspond to the leaves of the BVH. Then the algorithm builds the higher levels of the BVH by merging the clusters from the lower levels….3.3 Algorithm Detail, “…The algorithm then enters the main loop that runs through a number of iterations. In each iteration, all cluster pairs that successfully found their mutual nearest neighbor are merged. The main loop consists of three phases: nearest neighbor search, merging, and compaction. After each iteration, the input and output buffers are swapped. The main loop repeats until a single cluster remains. To guarantee that the algorithm always terminates, we prioritize the nearest neighbor with the lower index which solves a potential rare case of completely equidistant clusters (this issue will be discussed in the next section). An illustration of several iterations of the algorithm is depicted in Fig. 3. The pseudocode of the method is given in Algorithm 1. It highlights the three main phases of the algorithm..”; 3.6 Implementation Details, “..In the first pass, we perform a bottom-up traversal that marks each node as leaf or interior depending on the associated BVH cost. We compare the SAH cost of the node as a subtree and the SAH cost of the node being a leaf. If collapsing pays off, we mark the node as a leaf, otherwise as an interior node. In the second pass, we have to determine the roots of the collapsed subtrees. We perform a bottom-up traversal and track the highest leaf found so far. In the third pass, we mark all nodes in the collapsed subtree as invalid. Again we perform a bottom-up traversal until we reach the node identified in the previous pass and mark all visited nodes as invalid. In the fourth pass, we perform a prefix scan on valid nodes to determine the new node indices. We remap the child and parent indices using the values of the prefix scan.)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of modifying a hierarchical tree data structure of Aila with building the BHV iteratively from bottom to top by merging a batch of cluster pairs as seen in Meister because this modification would construct a high-quality BVH faster than previous state of-the-art methods of GPU-based BVH construction (1.INTRODUCTION of Meister)
Thus, the combination of Aila and Meister teaches a method for generating a bounding volume hierarchy (“BVH”), the method comprising: identifying that a number of uncombined descendants for a node of an initial BVH, is greater than or equal to a threshold; and in response to the identifying, combining the uncombined descendants to form a subtree to add to a new BVH.
Regarding claim 2, Aila and Meister teach the method of claim 1, wherein each uncombined descendant is a node of the new BVH for which no node of the new BVH is a parent (see at least [0083][0085] of Aila; whole paper, see at least Fig. 3. Of Meister “Illustration of the proposed algorithm. In each iteration, we merge mutually corresponding nearest neighbors (green nodes connected by a dotted line). New clusters and not merged clusters (red nodes) enter the next iteration. The process is repeated until only one cluster remains.’ 3.6 Implementation Details “…In the merging phase, we perform a warp-wide prefix scan on the number of new clusters using the __ballot function. We deter mine the node indices for a new cluster by atomically adding the number of new clusters within a warp to the node counter. This is done by adding the values of the warp-wide prefix scan and the original value of the node counter returned by the atomic addition…. In the first pass, we perform a bottom-up traversal that marks each node as leaf or interior depending on the associated BVH cost. We compare the SAH cost of the node as a subtree and the SAH cost of the node being a leaf. If collapsing pays off, we mark the node as a leaf, otherwise as an interior node. In the second pass, we have to determine the roots of the collapsed subtrees. We perform a bottom-up traversal and track the highest leaf found so far. In the third pass, we mark all nodes in the collapsed subtree as invalid. Again we perform a bottom-up traversal until we reach the node identified in the previous pass and mark all visited nodes as invalid. In the fourth pass, we perform a prefix scan on valid nodes to determine the new node indices. We remap the child and parent indices using the values of the prefix scan”) In addition, the same motivation is used as the rejection for claim 1.
Regarding claim 3, Aila and Meister teach the method of claim 1, wherein combining the uncombined descendants includes selecting uncombined descendants from the uncombined descendants for the node based on a selection criterion, forming a new node for the BVH, and setting, as parent for the selected uncombined descendants, the new node (see at least Aila: [0083] Generally, agglomerative clustering operates by merging nodes in a bottom-up fashion, maintaining a set of nodes yet to be merged. An agglomerative clustering algorithm starts with the individual treelet leaf nodes, and, in each iteration of processing, out of the set of nodes yet to be merged, the two whose union has the lowest surface area is identified. The two nodes are then merged by creating a new internal node. Repeating the algorithm, the newly created internal nodes will eventually be merged in the same fashion until only one node remains: the root node of the resulting BVH. Walter et al. 2008 "Fast agglomerative clustering for rendering" In Proc. IEEE Symposium on Interactive Ray Tracing, describes using an agglomerative clustering technique to construct a BVH for rendering without restructuring the BVH”; [0085] FIG. 5B illustrates a flowchart of a method 505 for restructuring a treelet, accordance with one embodiment. Although the method 505 is described in the context of a program executed by a processor, the method 505 may also be performed by custom circuitry or by a combination of custom circuitry and a program. At step 507, a set of treelet leaf nodes is received where a treelet leaf node either corresponds to an actual leaf node of the BVH or acts as a representative of an arbitrary subtree within the initial hierarchical tree data structure. In one embodiment, a processing thread may be allocated and launched to process each node in the set. At step 510, the processor determines if more than one node remains in the set of nodes yet to merged, and, if not, the process terminates and the treelet has been restructured.”; [0087] The MERGECOST cost function estimates the difference in the overall SAH cost between two cases: (1) merging the two nodes with each other; and (2) merging the two nodes with some other nodes. A given node i contributes to the overall SAH cost in two ways: (1) descendants of the node contribute C(i); and (2) ancestors of the node contribute some unknown amount that may be estimated to be A(i)*Z. In effect, MERGECOST(a, b) is the total contribution of the newly created internal node minus the total contributions of node a and node b. [0090] FIG. 5C illustrates example code 535 for restructuring a treelet using agglomerative clustering, in accordance with one embodiment. The example code 535 may be implemented to perform the method 505 shown in FIG. 5B. As previously described in conjunction with step 515, an O(n.sup.2) search is performed over the nodes in the set and the result of the MergeCost evaluation for the node pairs is used to merge as many nodes as possible during each iteration. The set N (line 1) represents the nodes yet to be merged, and the main loop (lines 2-19) is executed until there is only one node remaining. For each iteration, a node pairing having the lowest cost is determined for each node in the set (lines 3-11). For node n, finding the node pairing with the lowest cost is a matter of considering each node p in turn (line 5), calculating the expected cost of merging n and p (line 6), and choosing the pair that gives the lowest cost c.sub.n (line 7). After the lowest cost pairing is determined for each node, the reciprocating node pairs may be identified. To perform the merges, the code loops over the nodes (line 12), identifies the reciprocating node pairs (lines 13), and merges the nodes of reciprocating node pairs (lines 14-16). [0091] In practice, the algorithm can be parallelized over a group of threads by assigning one of the treelet leaf nodes to each thread. Both phases of the algorithm (lines 3-11 and lines 12-19) parallelize naturally over the set N. However, the execution of the threads should be synchronized when transitioning from one phase to the other. When performing a merge (lines 14-16), the newly created internal node r is assigned to the thread that was responsible for n, and the thread that was responsible for P[n] exits the loop. As an additional performance optimization, it is possible to abort the agglomerative merging of nodes when less than a fixed number of nodes remain (i.e. |N|<T on line 2). This will not reduce the quality of the resulting BVH as long as processing of the next treelet in bottom-up order searches all of the T nodes for reciprocating node pairs.” [0089] In contrast with the method 505, conventional techniques select a single pair of nodes (e.g. the one having the lowest cost) and merge the selected pair of nodes so that only a single merged node is created during each iteration of the agglomerative clustering process. Thus, the set of nodes decreases by only one node for each iteration.”; whole paper at least 3.1 Parallel Locally-Ordered Clustering of Meister). In addition, the same motivation is used as the rejection for claim 1.
Regarding claim 4, Aila and Meister teach the method of claim 3, further comprising repeating the combining until the number of uncombined descendants for the node is less than the threshold (see at least Aila [0085] FIG. 5B illustrates a flowchart of a method 505 for restructuring a treelet, accordance with one embodiment. Although the method 505 is described in the context of a program executed by a processor, the method 505 may also be performed by custom circuitry or by a combination of custom circuitry and a program. At step 507, a set of treelet leaf nodes is received where a treelet leaf node either corresponds to an actual leaf node of the BVH or acts as a representative of an arbitrary subtree within the initial hierarchical tree data structure. In one embodiment, a processing thread may be allocated and launched to process each node in the set. At step 510, the processor determines if more than one node remains in the set of nodes yet to merged, and, if not, the process terminates and the treelet has been restructured.”; [0090] FIG. 5C illustrates example code 535 for restructuring a treelet using agglomerative clustering, in accordance with one embodiment. The example code 535 may be implemented to perform the method 505 shown in FIG. 5B. As previously described in conjunction with step 515, an O(n.sup.2) search is performed over the nodes in the set and the result of the MergeCost evaluation for the node pairs is used to merge as many nodes as possible during each iteration. The set N (line 1) represents the nodes yet to be merged, and the main loop (lines 2-19) is executed until there is only one node remaining. For each iteration, a node pairing having the lowest cost is determined for each node in the set (lines 3-11). For node n, finding the node pairing with the lowest cost is a matter of considering each node p in turn (line 5), calculating the expected cost of merging n and p (line 6), and choosing the pair that gives the lowest cost c.sub.n (line 7). After the lowest cost pairing is determined for each node, the reciprocating node pairs may be identified. To perform the merges, the code loops over the nodes (line 12), identifies the reciprocating node pairs (lines 13), and merges the nodes of reciprocating node pairs (lines 14-16). [0091] In practice, the algorithm can be parallelized over a group of threads by assigning one of the treelet leaf nodes to each thread. Both phases of the algorithm (lines 3-11 and lines 12-19) parallelize naturally over the set N. However, the execution of the threads should be synchronized when transitioning from one phase to the other. When performing a merge (lines 14-16), the newly created internal node r is assigned to the thread that was responsible for n, and the thread that was responsible for P[n] exits the loop. As an additional performance optimization, it is possible to abort the agglomerative merging of nodes when less than a fixed number of nodes remain (i.e. |N|<T on line 2). This will not reduce the quality of the resulting BVH as long as processing of the next treelet in bottom-up order searches all of the T nodes for reciprocating node pairs.”)
Regarding claim 10, Aila teaches a system for generating a bounding volume hierarchy (“BVH”) (([0028] FIG. 1 illustrates a flowchart of a method 100 for generating a hierarchical tree data structure, in accordance with one embodiment. At step 105, an initial hierarchical tree data structure is received. In one embodiment, the hierarchical tree data structure may be a BVH.”, Figs 2A-2C, Fig.9), the system comprising: a memory ([0136] FIG. 9 illustrates an exemplary system 900 in which the various architecture and/or functionality of the various previous embodiments may be implemented. As shown, a system 900 is provided including at least one central processor 901 that is connected to a communication bus 902. The communication bus 902 may be implemented using any suitable protocol, such as PCI (Peripheral Component Interconnect), PCI-Express, AGP (Accelerated Graphics Port), HyperTransport, or any other bus or point-to-point communication protocol(s). The system 900 also includes a main memory 904. Control logic (software) and data are stored in the main memory 904 which may take the form of random access memory (RAM)”).configured to store information for a new BVH ([0130] Reconstruction of the optimal treelet from p.sub.opt can be performed in a similar manner as formation of the initial treelet, except that the identities of the original internal nodes are reused for the newly created internal nodes. After the reconstruction, new AABBs are calculated for the internal nodes based on their children, the process is repeated in parallel until the results have propagated to the treelet root. Finally, the nodes of the treelet are stored back to memory, bypassing the L1 cache in order to ensure that the results are visible to all SM 750s. As a minor optimization, the output part of the algorithm may be skipped in case it was not possible to improve the SAH cost, i.e., c.sub.opt[2.sup.n-1].gtoreq.C(root).”); and a processor ([0140] Computer programs, or computer control logic algorithms, may be stored in the main memory 904 and/or the secondary storage 910. Such computer programs, when executed, enable the system 900 to perform various functions. For example, a compiler program that is configured to examiner a shader program and enable or disable attribute buffer combining may be stored in the main memory 904. The compiler program may be executed by the central processor 901 or the graphics processor 906. The main memory 904, the storage 910, and/or any other storage are possible examples of computer-readable media.”) configured to perform operations ([0105] In one embodiment, the CPU executes a driver kernel that implements an application programming interface (API) that enables one or more applications executing on the CPU to schedule operations for execution on the PPU 700. An application may include instructions (i.e., API calls) that cause the driver kernel to generate one or more grids for execution. In one embodiment, the PPU 700 implements a SIMD (Single-Instruction, Multiple-Data) architecture where each thread block (i.e., warp) in a grid is concurrently executed on a different data set by different threads in the thread block. The driver kernel defines thread blocks that are comprised of k related threads, such that threads in the same thread block may exchange data through shared memory. In one embodiment, a thread block comprises 32 related threads and a grid is an array of one or more thread blocks that execute the same stream and the different thread blocks may exchange data through global memory. comprising: Remaining limitations of claim 10 is similar scope to claim 1 and therefore rejected under the same rationale.
Regarding claim 11, Aila and Meister teach the system of claim 10, Remaining limitations of claim 11 is similar scope to claim 2 and therefore rejected under the same rationale.
Regarding claim 12, Aila and Meister teach the system of claim 10, Remaining limitations of claim 12 is similar scope to claim 3 and therefore rejected under the same rationale.
Regarding claim 13, Aila and Meister teach the system of claim 12, further comprising Remaining limitations of claim 13 is similar scope to claim 4 and therefore rejected under the same rationale.
Regarding independent claim 19, Aila teaches a non-transitory computer-readable medium storing instructions that, when executed by a processor (see at least Fig.9 (items 904, 910), [0140] Computer programs, or computer control logic algorithms, may be stored in the main memory 904 and/or the secondary storage 910. Such computer programs, when executed, enable the system 900 to perform various functions. For example, a compiler program that is configured to examiner a shader program and enable or disable attribute buffer combining may be stored in the main memory 904. The compiler program may be executed by the central processor 901 or the graphics processor 906. The main memory 904, the storage 910, and/or any other storage are possible examples of computer-readable media.”), cause the processor to perform operations ([0105] In one embodiment, the CPU executes a driver kernel that implements an application programming interface (API) that enables one or more applications executing on the CPU to schedule operations for execution on the PPU 700. An application may include instructions (i.e., API calls) that cause the driver kernel to generate one or more grids for execution. In one embodiment, the PPU 700 implements a SIMD (Single-Instruction, Multiple-Data) architecture where each thread block (i.e., warp) in a grid is concurrently executed on a different data set by different threads in the thread block. The driver kernel defines thread blocks that are comprised of k related threads, such that threads in the same thread block may exchange data through shared memory. In one embodiment, a thread block comprises 32 related threads and a grid is an array of one or more thread blocks that execute the same stream and the different thread blocks may exchange data through global memory. comprising: Remaining limitations of claim 19 is similar scope to claim 1 and therefore rejected under the same rationale.
Regarding claim 20, Aila and Meister teach the non-transitory computer-readable medium of claim 19, Remaining limitations of claim 20 is similar scope to claim 2 and therefore rejected under the same rationale.
2. Claims 5-9, 14-18 are rejected under 35 U.S.C. 103 as being unpatentable over Alila et al., U.S Patent Application Publication No. 20140365529 (“Aila”) in view of MEISTER, D. & BITTNER, J.; IDS, "Parallel Locally-Ordered Clustering for Bounding Volume Hierarchy Construction", IEEE Transactions on Visualization and Computer Graphics (Preprint), IEEE, 2017, 9 pgs.(“MEISTER”) further in view of Tsakok, U.S Patent Application Publication No. 20230351667 (“Tsakok”)
Regarding claim 3, Aila and Meister teaches the method of claim 1, wherein the identifying is part of a parallel analysis operation performed in parallel (see at least [0083][0085] of Aila; whole paper at least 3.1 Parallel Locally-Ordered Clustering of Meister). In addition, the same motivation is used as the rejection for claim 1. Both Aila and Meister are understood to be silent on the remaining limitations of claim 3.
In the same field of endeavor, Tsakok teaches wherein the identifying is part of a parallel analysis operation performed in parallel by multiple work-items of a wavefront (see at least [0022] The basic unit of execution in compute units 132 is a work-item. Each work-item represents a single instantiation of a program that is to be executed in parallel in a particular lane. Work-items can be executed simultaneously as a “wavefront” on a single SIMD processing unit 138. One or more wavefronts are included in a “work group,” which includes a collection of work-items designated to execute the same program. A work group can be executed by executing each of the wavefronts that make up the work group. In alternatives, the wavefronts are executed sequentially on a single SIMD unit 138 or partially or fully in parallel on different SIMD units 138. Wavefronts can be thought of as the largest collection of work-items that can be executed simultaneously on a single SIMD unit 138. Thus, if commands received from the processor 102 indicate that a particular program is to be parallelized to such a degree that the program cannot execute on a single SIMD unit 138 simultaneously, then that program is broken up into wavefronts which are parallelized on two or more SIMD units 138 or serialized on the same SIMD unit 138 (or both parallelized and serialized as needed). A scheduler 136 performs operations related to scheduling various wavefronts on different compute units 132 and SIMD units 138.”;[0055] In some examples, the BVH builder 501 is at least partly parallelized. In an example, wavefronts are spawned to perform each of the iterations 508. In some examples, each work-item of the wavefront performs work for one data item 602—a subject data item 602. In the nearest neighbor search 610, each work-item determines which cluster is the nearest neighbor to the cluster of the subject data item 602 and writes that information into the subject data item 602. In the merge 612, each work-item determines an updated value for the subject data item 602 based on whether the subject data item is to become a merged data item, an invalid data item, or an unmodified data item 602. A merged data item is a data item that is formed based on a nearest neighbor pair as described above. An invalid data item is a data item that is discarded when a merged data item is formed. An unmodified data item is a data item that is not merged or invalid. Each work-item determines which of the above the data item corresponding to that work-item will become. Then, each work-item performs a corresponding action based on the type of the corresponding data item. For a data item that is merged, the work-item also generates and outputs the corresponding node of the BVH. Because each work-item performs these actions for each data items, the operations for the merge occurs in parallel. Compaction occurs in parallel in a similar manner, with each work-item modifying a corresponding data item as necessary.” [0059] The nearest neighbor search, merge, and compaction operations are performed with wavefronts in the following manner. The BVH builder 501 issues a wavefront to process a certain portion of an input to generate an output. The BVH builder 501 issues these wavefronts asynchronously as processing resources become available. In some implementations, the BVH builder 501 issues wavefronts in a particular order, to process the input buffer from beginning to end. For example, the BVH builder 501 issues a first wavefront to process the first N clusters (where N is the number of clusters that can be processed by a wavefront), then the BVH builder 501 issues a second wavefront to process the next N clusters, and so on. Although these wavefronts generally proceed in order, it is possible for later wavefronts to advance ahead of earlier wavefronts (for example, a later issued wavefront can be further along in a particular phase or can be on a subsequent phase as compared with an earlier issued wavefront).)
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to modify the method of modifying a hierarchical tree data structure of Aila and Meister with a parallel analysis operation performed in parallel by multiple work-items of a wavefront as seen in Tsakok because this modification would allow many work-items to execute in parallel on SIMD units ([0022] of Tsakok)
Thus, the combination of Aila, Meister and Tsakok teaches wherein the identifying is part of a parallel analysis operation performed in parallel by multiple work-items of a wavefront.
Regarding claim 6, Aila, Meister and Tsakok teach the method of claim 5, wherein the combining is also performed by the wavefront (see at least [0055] of Tsakok “In some examples, the BVH builder 501 is at least partly parallelized. In an example, wavefronts are spawned to perform each of the iterations 508. In some examples, each work-item of the wavefront performs work for one data item 602—a subject data item 602. In the nearest neighbor search 610, each work-item determines which cluster is the nearest neighbor to the cluster of the subject data item 602 and writes that information into the subject data item 602. In the merge 612, each work-item determines an updated value for the subject data item 602 based on whether the subject data item is to become a merged data item, an invalid data item, or an unmodified data item 602. A merged data item is a data item that is formed based on a nearest neighbor pair as described above. An invalid data item is a data item that is discarded when a merged data item is formed. An unmodified data item is a data item that is not merged or invalid. Each work-item determines which of the above the data item corresponding to that work-item will become. Then, each work-item performs a corresponding action based on the type of the corresponding data item. For a data item that is merged, the work-item also generates and outputs the corresponding node of the BVH. Because each work-item performs these actions for each data items, the operations for the merge occurs in parallel. Compaction occurs in parallel in a similar manner, with each work-item modifying a corresponding data item as necessary. [0056] The parallel algorithm has data dependencies. More specifically, the nearest neighbor search requires that data from other clusters is available to perform the search. The merge requires data for other clusters to merge (e.g., requires the nearest neighbor information from other clusters). The compaction step requires knowing which clusters are valid or invalid. Thus, in one implementation, one or more wavefronts are launched for each “phase” of each iteration, and a global barrier is used to ensure that all wavefronts have reached the end of the phase before launching wavefronts for a subsequent phase. A global barrier is used at the end of each iteration as well. In an example, wavefronts are launched to perform a nearest neighbor search for a set of clusters corresponding to a very large set of input geometry. A global barrier occurs, preventing further work from being performed until all wavefronts have finished the nearest neighbor search. Then, wavefronts are launched to perform the merging for the clusters. A global barrier occurs, preventing further work from occurring until all wavefronts have finished the merging. Then, wavefronts are launched to perform the compaction for the clusters. A global barrier exists at the end of the compaction, causing all wavefronts to wait until compaction is complete before any wavefront begins the nearest neighbor search for the next iteration. In addition to the above, in a “safe” way of performing BVH build, each thread writes the output of a phase (nearest neighbor search, merge, or compaction) to a general memory such as APD memory or another globally available memory. While this is a “safe” way of performing the above operations, efficiency can be gained by not using global barriers and by allowing operations to proceed at different times in different wavefronts. Care must be taken, however, to respect data dependencies. Techniques are provided herein for performing such operations.”; [0059] “The nearest neighbor search, merge, and compaction operations are performed with wavefronts in the following manner. The BVH builder 501 issues a wavefront to process a certain portion of an input to generate an output. The BVH builder 501 issues these wavefronts asynchronously as processing resources become available. In some implementations, the BVH builder 501 issues wavefronts in a particular order, to process the input buffer from beginning to end. For example, the BVH builder 501 issues a first wavefront to process the first N clusters (where N is the number of clusters that can be processed by a wavefront), then the BVH builder 501 issues a second wavefront to process the next N clusters, and so on. Although these wavefronts generally proceed in order, it is possible for later wavefronts to advance ahead of earlier wavefronts (for example, a later issued wavefront can be further along in a particular phase or can be on a subsequent phase as compared with an earlier issued wavefront) In addition, the same motivation is used as the rejection for claim 5.
Regarding claim 7, Aila, Meister and Tsakok teach the method of claim 6, wherein the wavefront performs the combining upon detecting that at least one node of the initial BVH has a number of uncombined descendants below the threshold (see at least Aila [0085] FIG. 5B illustrates a flowchart of a method 505 for restructuring a treelet, accordance with one embodiment. Although the method 505 is described in the context of a program executed by a processor, the method 505 may also be performed by custom circuitry or by a combination of custom circuitry and a program. At step 507, a set of treelet leaf nodes is received where a treelet leaf node either corresponds to an actual leaf node of the BVH or acts as a representative of an arbitrary subtree within the initial hierarchical tree data structure. In one embodiment, a processing thread may be allocated and launched to process each node in the set. At step 510, the processor determines if more than one node remains in the set of nodes yet to merged, and, if not, the process terminates and the treelet has been restructured.”; [0090] FIG. 5C illustrates example code 535 for restructuring a treelet using agglomerative clustering, in accordance with one embodiment. The example code 535 may be implemented to perform the method 505 shown in FIG. 5B. As previously described in conjunction with step 515, an O(n.sup.2) search is performed over the nodes in the set and the result of the MergeCost evaluation for the node pairs is used to merge as many nodes as possible during each iteration. The set N (line 1) represents the nodes yet to be merged, and the main loop (lines 2-19) is executed until there is only one node remaining. For each iteration, a node pairing having the lowest cost is determined for each node in the set (lines 3-11). For node n, finding the node pairing with the lowest cost is a matter of considering each node p in turn (line 5), calculating the expected cost of merging n and p (line 6), and choosing the pair that gives the lowest cost c.sub.n (line 7). After the lowest cost pairing is determined for each node, the reciprocating node pairs may be identified. To perform the merges, the code loops over the nodes (line 12), identifies the reciprocating node pairs (lines 13), and merges the nodes of reciprocating node pairs (lines 14-16). [0091] In practice, the algorithm can be parallelized over a group of threads by assigning one of the treelet leaf nodes to each thread. Both phases of the algorithm (lines 3-11 and lines 12-19) parallelize naturally over the set N. However, the execution of the threads should be synchronized when transitioning from one phase to the other. When performing a merge (lines 14-16), the newly created internal node r is assigned to the thread that was responsible for n, and the thread that was responsible for P[n] exits the loop. As an additional performance optimization, it is possible to abort the agglomerative merging of nodes when less than a fixed number of nodes remain (i.e. |N|<T on line 2). This will not reduce the quality of the resulting BVH as long as processing of the next treelet in bottom-up order searches all of the T nodes for reciprocating node pairs.”; whole paper at least 3.1 Parallel Locally-Ordered Clustering of Meister ;[0059] of Tsakok “The nearest neighbor search, merge, and compaction operations are performed with wavefronts in the following manner. The BVH builder 501 issues a wavefront to process a certain portion of an input to generate an output. The BVH builder 501 issues these wavefronts asynchronously as processing resources become available. In some implementations, the BVH builder 501 issues wavefronts in a particular order, to process the input buffer from beginning to end. For example, the BVH builder 501 issues a first wavefront to process the first N clusters (where N is the number of clusters that can be processed by a wavefront), then the BVH builder 501 issues a second wavefront to process the next N clusters, and so on. Although these wavefronts generally proceed in order, it is possible for later wavefronts to advance ahead of earlier wavefronts (for example, a later issued wavefront can be further along in a particular phase or can be on a subsequent phase as compared with an earlier issued wavefront).In addition, the same motivation is used as the rejection for claim 5.
Regarding claim 8, Aila, Meister and Tsakok teach the method of claim 6, wherein the combining comprises each active work-item of the wavefront being assigned an uncombined descendant for analysis (see at least Aila [0085],[0090]; whole paper at least 3.1 Parallel Locally-Ordered Clustering of Meister; [0055] In some examples, the BVH builder 501 is at least partly parallelized. In an example, wavefronts are spawned to perform each of the iterations 508. In some examples, each work-item of the wavefront performs work for one data item 602—a subject data item 602. In the nearest neighbor search 610, each work-item determines which cluster is the nearest neighbor to the cluster of the subject data item 602 and writes that information into the subject data item 602. In the merge 612, each work-item determines an updated value for the subject data item 602 based on whether the subject data item is to become a merged data item, an invalid data item, or an unmodified data item 602. A merged data item is a data item that is formed based on a nearest neighbor pair as described above. An invalid data item is a data item that is discarded when a merged data item is formed. An unmodified data item is a data item that is not merged or invalid. Each work-item determines which of the above the data item corresponding to that work-item will become. Then, each work-item performs a corresponding action based on the type of the corresponding data item. For a data item that is merged, the work-item also generates and outputs the corresponding node of the BVH. Because each work-item performs these actions for each data items, the operations for the merge occurs in parallel. Compaction occurs in parallel in a similar manner, with each work-item modifying a corresponding data item as necessary.” [0059] The nearest neighbor search, merge, and compaction operations are performed with wavefronts in the following manner. The BVH builder 501 issues a wavefront to process a certain portion of an input to generate an output. The BVH builder 501 issues these wavefronts asynchronously as processing resources become available. In some implementations, the BVH builder 501 issues wavefronts in a particular order, to process the input buffer from beginning to end. For example, the BVH builder 501 issues a first wavefront to process the first N clusters (where N is the number of clusters that can be processed by a wavefront), then the BVH builder 501 issues a second wavefront to process the next N clusters, and so on. Although these wavefronts generally proceed in order, it is possible for later wavefronts to advance ahead of earlier wavefronts (for example, a later issued wavefront can be further along in a particular phase or can be on a subsequent phase as compared with an earlier issued wavefront). In addition, the same motivation is used as the rejection for claim 5.
Regarding claim 9, Aila, Meister and Tsakok teach the method of claim 8, wherein the analysis comprises selecting a set of uncombined descendants to combine (see at least Aila: [0083] Generally, agglomerative clustering operates by merging nodes in a bottom-up fashion, maintaining a set of nodes yet to be merged. An agglomerative clustering algorithm starts with the individual treelet leaf nodes, and, in each iteration of processing, out of the set of nodes yet to be merged, the two whose union has the lowest surface area is identified. The two nodes are then merged by creating a new internal node. Repeating the algorithm, the newly created internal nodes will eventually be merged in the same fashion until only one node remains: the root node of the resulting BVH. Walter et al. 2008 "Fast agglomerative clustering for rendering" In Proc. IEEE Symposium on Interactive Ray Tracing, describes using an agglomerative clustering technique to construct a BVH for rendering without restructuring the BVH”; [0085] FIG. 5B illustrates a flowchart of a method 505 for restructuring a treelet, accordance with one embodiment. Although the method 505 is described in the context of a program executed by a processor, the method 505 may also be performed by custom circuitry or by a combination of custom circuitry and a program. At step 507, a set of treelet leaf nodes is received where a treelet leaf node either corresponds to an actual leaf node of the BVH or acts as a representative of an arbitrary subtree within the initial hierarchical tree data structure. In one embodiment, a processing thread may be allocated and launched to process each node in the set. At step 510, the processor determines if more than one node remains in the set of nodes yet to merged, and, if not, the process terminates and the treelet has been restructured.”; [0087] The MERGECOST cost function estimates the difference in the overall SAH cost between two cases: (1) merging the two nodes with each other; and (2) merging the two nodes with some other nodes. A given node i contributes to the overall SAH cost in two ways: (1) descendants of the node contribute C(i); and (2) ancestors of the node contribute some unknown amount that may be estimated to be A(i)*Z. In effect, MERGECOST(a, b) is the total contribution of the newly created internal node minus the total contributions of node a and node b. [0090] FIG. 5C illustrates example code 535 for restructuring a treelet using agglomerative clustering, in accordance with one embodiment. The example code 535 may be implemented to perform the method 505 shown in FIG. 5B. As previously described in conjunction with step 515, an O(n.sup.2) search is performed over the nodes in the set and the result of the MergeCost evaluation for the node pairs is used to merge as many nodes as possible during each iteration. The set N (line 1) represents the nodes yet to be merged, and the main loop (lines 2-19) is executed until there is only one node remaining. For each iteration, a node pairing having the lowest cost is determined for each node in the set (lines 3-11). For node n, finding the node pairing with the lowest cost is a matter of considering each node p in turn (line 5), calculating the expected cost of merging n and p (line 6), and choosing the pair that gives the lowest cost c.sub.n (line 7). After the lowest cost pairing is determined for each node, the reciprocating node pairs may be identified. To perform the merges, the code loops over the nodes (line 12), identifies the reciprocating node pairs (lines 13), and merges the nodes of reciprocating node pairs (lines 14-16). [0091] In practice, the algorithm can be parallelized over a group of threads by assigning one of the treelet leaf nodes to each thread. Both phases of the algorithm (lines 3-11 and lines 12-19) parallelize naturally over the set N. However, the execution of the threads should be synchronized when transitioning from one phase to the other. When performing a merge (lines 14-16), the newly created internal node r is assigned to the thread that was responsible for n, and the thread that was responsible for P[n] exits the loop. As an additional performance optimization, it is possible to abort the agglomerative merging of nodes when less than a fixed number of nodes remain (i.e. |N|<T on line 2). This will not reduce the quality of the resulting BVH as long as processing of the next treelet in bottom-up order searches all of the T nodes for reciprocating node pairs.” [0089] In contrast with the method 505, conventional techniques select a single pair of nodes (e.g. the one having the lowest cost) and merge the selected pair of nodes so that only a single merged node is created during each iteration of the agglomerative clustering process. Thus, the set of nodes decreases by only one node for each iteration.”; whole paper at least 3.1 Parallel Locally-Ordered Clustering of Meister; [0062] of Tsakok “ After step 802, the wavefront performs step 804, which includes determining the nearest neighbor for each cluster. For any particular work-item, that work-item performs a search within a radius. The radius is the number of clusters to the left and right in the working buffer 620 for which to determine a nearest neighbor. As described above, in some implementations, a work-item determines the nearest neighbor by determining a combined bounding volume surface area for each cluster in the radius. The work-item selects, as the nearest neighbor for the subject cluster, the cluster for which the combined bounding volume surface area is the lowest. [0068] The notion of wavefronts being “prior to” or “subsequent to” other wavefronts may be defined in one of the following ways. In a first way, a first wavefront is considered prior to a second wavefront if the first wavefront processes clusters that are prior to the clusters processed by the second wavefront in the list of input clusters. In some examples, the list of input clusters is ordered in the manner shown throughout the figures. In a second way, a first wavefront is considered prior to a second wavefront in the event that the first wavefront is issued for execution prior to the second wavefront.”) In addition, the same motivation is used as the rejection for claim 5.
Regarding claim 14, Aila, Meister teach the system of claim 10, Remaining limitations of claim 14 is similar scope to claim 5 and therefore rejected under the same rationale.
Regarding claim 15, Aila, Meister and Tsakok teach the system of claim 14, Remaining limitations of claim 15 is similar scope to claim 6 and therefore rejected under the same rationale.
Regarding claim 16, Aila, Meister and Tsakok teach the system of claim 15, Remaining limitations of claim 16 is similar scope to claim 7 and therefore rejected under the same rationale.
Regarding claim 17, Aila, Meister and Tsakok teach the system of claim 15, Remaining limitations of claim 17 is similar scope to claim 8 and therefore rejected under the same rationale.
Regarding claim 18, Aila, Meister and Tsakok teach the system of claim 17, Remaining limitations of claim 18 is similar scope to claim 9 and therefore rejected under the same rationale.
Contact
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SARAH LE whose telephone number is (571)270-7842. The examiner can normally be reached Monday: 8AM-4:30PM EST, Tuesday: 8 AM-3:30PM EST, Wednesday: 8AM-2:30PM EST, Thursday and Friday off.
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, Kent Chang can be reached at (571) 272-7667. 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.
/SARAH LE/Primary Examiner, Art Unit 2614
Prosecution Insights