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 .
Claim Objections
Claim 12 recites “wherein the identified transformation matrix”. There is insufficient antecedent basis for this limitation, and it appears that it refers to the “instance transformation matrix” identified earlier. Therefore, the examiner suggests the following amendment: “wherein the identified instance transformation matrix”.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: “a module configured to...” in claim 15.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
A review of the specification shows that the following appears to be the corresponding structure(s) described in the specification for the 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph limitation: the GPU 1210 in Fig. 12, which is a specialized GPU when it executes the algorithm illustrated in Fig. 8.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-11 and 13-17 is/are rejected under 35 U.S.C. 103 as being unpatentable over Woop et al. ("Exploiting Local Orientation Similarity for Efficient Ray Traversal of Hair and Fur", 2014), in view of Wald et al. (Pub. No. 2017/0287202).
Regarding claim 1, Woop discloses a computer-implemented method of constructing a ray tracing acceleration structure for a scene defined with respect to an overall coordinate system (Section 3.1, 2nd paragraph: “we utilize a bounding volume hierarchy that combines both axis-aligned and oriented bounding boxes, and spatial and object splits. This mixed BVH is able to adapt to the local orientation of individual hairs, and exploit similarity in the orientation of neighboring hairs to minimize overlap between bounding boxes, while reducing the memory and compute overhead associated with a BVH built solely from OBBs”. Section AABB and OBB tests further discloses: “we test if the node is a leaf or an OBB node; in the latter case we use the respective node’s four affine transformation matrices - already stored in SIMD-friendly structure-of-array layout - and use SIMD instructions to transform the ray’s origin and direction into the respective four spaces (in parallel)”. This suggests that an initial ray in the overall coordinate system can be transformed into a local coordinate system), the scene comprising a model defined with respect to a local coordinate system for the model (See section 3.3.1. The hair space could be viewed as a local coordinate system for hair strands),
accessing a plurality of local transformation matrices for a bounding volume hierarchy (BVH) for the model, wherein each node of the BVH is associated with a first bounding volume, and one of the plurality of local transformation matrices that maps between the first bounding volume and a second bounding volume, in the local coordinate system (Page 4, column 2, 3rd par: “OBB nodes. For nodes with non-axis aligned bounds we store, for each node, the affine transformation matrix that transforms the respective OBB to the unit AABB ((0,0,0); (1,1,1))”. See also sections 3.3.1 and 3.3.2. The transformation from an OBB node to an AABB node is performed in the hair space, which is a local coordinate system)
.
Woop, however, does not disclose the above lined-through limitations. That is, Woop does not disclose object instancing and updating the plurality of local transformation matrices to become a set of instance transformation matrices.
In the same field of ray tracing, Wald teaches object instancing where each instance of a base model is associated with a transformation matrix (See par. 24. In particular, the transformation that transforms an instance of a base model from the model space into world space could be viewed as a model transformation matrix (also known as object-to-world transformation matrix in the art)).
In light of Wald’s teaching of object instancing for ray tracing, it would have been obvious to one skilled in the art before the effective filing date of the claimed invention to incorporating Wald’s object-instancing technique into Woop by updating the plurality of local transformation matrices of the BVH to become a set of instance transformation matrices by combining each individual local transformation matrix with the model transformation matrix, such that the plurality of nodes of the instance of the model each become associated with one of the instance transformation matrices. The motivation would have been to allow for storage of a model (e.g. a hair strand) only once, with multiple (e.g., transformed) references being used for placing the model(s) at different positions in a scene hierarchy (Wald, par. 23).
Regarding claim 2, Woop in view of Wald teaches the method according to claim 1, wherein the BVH comprises a plurality of nodes, each associated with one of the plurality of local transformation matrices by an index referencing one of the one of the local transformation matrices, and wherein the index is preserved when the plurality of local transformation matrices is updated to become a set of instance transformation matrices (Wald, par. 32: “each leaf-primitive in the top-level BVH would be a pair of (instance ID (Identifier), subtree ID), where the instance ID allows for determining the transformation that the object BVH should undergo, as well as the object BVH to which the second parameter (the sub-tree ID) refers”. The instance ID could be interpreted as an index. When modified by Wald, the local transformation matrices become the instance transformation matrices).
Regarding claim 3, Woop in view of Wald teaches the method according to claim 1, wherein the model is instanced in the scene multiple times, each time by applying a different model transformation matrix for positioning that respective instance of the model in the overall coordinate system, wherein the updating of each of the local transformation matrices is performed for each instance to produce a different set of instance transformation matrices (See Wald, par. 23).
Regarding claim 4, Woop in view of Wald teaches the method according to claim 1, wherein the plurality of local transformation matrices are a fixed set of matrices for the model that are predetermined before defining the BVH, or a fixed set of matrices for the model that are determined, at least in part, based on an analysis of the plurality of BVH nodes, wherein optionally the plurality of local transformation matrices each represent a different, optionally affine, mapping (Woop, page 6, col. 2, 3rd par: “we use the respective node’s four affine transformation matrices — already stored in SIMD-friendly structure-of-array layout — and use SIMD instructions to transform the ray’s origin and direction into the respective four spaces (in parallel)).
Regarding claim 5, Woop in view of Wald teaches the method according to claim 1, wherein each first bounding volume is selected from a set of candidate bounding volumes (Woop, page 4, col. 1, last par: “BVH Data Layout. To eventually allow for fast single-ray SIMD traversal we follow the data layouts of the original Embree kernels as closely as possible. In particular, we use a BVH with a branching factor of four that will allow for always intersecting four child-bounds in parallel (Section 3.4). This data-parallel intersection in particular requires that every group of four sibling nodes have to be of the same type: If only one prefers OBBs, all four nodes have to be OBB nodes”).
Regarding claim 6, Woop in view of Wald teaches the method according to claim 5, wherein each candidate bounding volume is associated with a different one of the plurality of local transformation matrices (Woop, page 4, column 2, 3rd par: “OBB nodes. For nodes with non-axis aligned bounds we store, for each node, the affine transformation matrix that transforms the respective OBB to the unit AABB ((0,0,0); (1,1,1))).
Regarding claim 7, Woop in view of Wald teaches the method according to claim 6, wherein selecting comprises comparing the set of candidate bounding volumes and selecting the optimal bounding volume according to a predefined heuristic, and optionally wherein the predefined heuristic is to select the candidate bounding volume with one of: the smallest volume, the smallest surface area, or smallest cross-sectional area in a specified direction (Woop, page 5, col. 1, last par: “To construct the tree we use a top-down surface area heuristic (SAH) based approach that automatically selects the proper node type based on the lowest cost. In particular, the cost function we use has different cost factors for both AABB and OBB splits to properly reflect the higher cost of traversing OBB nodes”).
Regarding claim 8, Woop in view of Wald teaches the method according to claim 1, wherein associating each node with one of the plurality of local transformations matrices comprises storing an indication of the respective local transformation matrix for the node, and optionally wherein storing an indication comprises storing an index identifying the particular local transformation matrix (Woop, page 4, col. 2, 3rd par: “The four OBB nodes’ transformations are stored in a SIMD friendly SOA layout, requiring a total of 192 bytes. Together with the 4 node references this makes a total of 224 bytes for an OBB node”).
Regarding claim 9, Woop in view of Wald teaches the method according to claim 1, wherein the first bounding volume is an oriented bounding volume, and the second bounding volume is an axis-aligned bounding volume, or wherein the first bounding volume is an oriented bounding box and the second bounding volume is an axis-aligned bounding box, or wherein the first bounding volume is an oriented ellipsoid and the second bounding volume is a sphere or an axis-aligned ellipsoid (Woop, page 4, col. 2, 3rd par: “OBB nodes. For nodes with non-axis aligned bounds we store, for each node, the affine transformation matrix that transforms the respective OBB to the unit AABB ((0,0,0); (1,1,1))).
Regarding claim 10, Woop in view of Wald teaches the method according to claim 1, wherein the ray tracing system supports model instancing (As pointed out in the rejection of claim 1, Wald teaches a ray tracing system that supports model instancing).
Regarding claim 11, Woop in view of Wald teaches the method according to claim 1, wherein the number of local transformation matrices is fewer than the number of nodes (In Woop, only OBB nodes have transformation matrices associated with them while AABB nodes do not. Thus, the number of local transformation matrices could be fewer than the number of nodes).
Claim 13 recites similar limitations as claim 1, and therefore could be rejected using the same rationale set forth in the rejection of claim 1.
Regarding claim 14, Woop in view of Wald and Chen teaches the method according to claim 13, wherein the model comprises one or more instances of another model (Wald, par. 31: “In an embodiment, in the case of spatially overlapping instances, the overlap is significantly reduced. Rather than sequentially traversing entire hierarchies, such braided top-level BVH is able to skip (all or most) nodes in instances that would have previously overlapped, and to directly traverse to appropriate sub-trees that do not overlap (or at least, significantly less). This yields significantly higher performance in particular for models that heavily use instancing, such as when many such instances overlap”).
Claims 15 and 16 recite similar limitations as claim 1, but are directed to a ray tracing system comprising a module configured to execute the steps recited in claim 1. Since Woop in view of Wald also teaches such a system (See Fig. 1 of Wald as an example), claims 15 and 16 could be rejected under the same rationale set forth in the rejection of claim 1.
Claim 17 recites similar limitations as claim 1, but is directed to a computer readable storage medium storing computer readable code programmed to execute the steps recited in claim 1. Since Woop in view of Wald also teaches such a computer readable storage medium (See claims 23-25 of Wald as an example), claim 17 could be rejected under the same rationale set forth in the rejection of claim 1.
Claim(s) 12 is/are rejected under 35 U.S.C. 103 as being unpatentable over Woop, in view of Wald, and further in view of Chen ("Enable Ray Tracing: Ray Traversal", April 8, 2020; available online at https://handmade.network/p/75/monter/blog/p/7256-enable_ray_tracing__ray_traversal. A PDF version of this literature is being included for convenience).
Claim 12 can be rejected using the same rationale set forth in the rejection of claim 1. Furthermore, Chen teaches using an inverse of a model transformation matrix to transform a ray from a world space into model space (See section Two-Level Ray Traversal).
It would have been obvious to one skilled in the art before the effective filing date of the claimed invention to further modify Woop by representing an instance transformation matrix by combining an inverse model transformation matrix with a local transformation matrix that maps between a first bounding volume for a node and a second bounding volume in the local coordinate system. The motivation would have been because a transformation from world space to model space is known to be an inverse of the transformation from model space to world space.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to PHONG X NGUYEN whose telephone number is (571)270-1591. The examiner can normally be reached Mon-Fri 8am - 5pm EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, King Poon can be reached at (571)272-7440. 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.
/PHONG X NGUYEN/ Primary Patent Examiner, Art Unit 2617