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 .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 06/25/2024 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Drawings
The drawings are objected to under 37 CFR 1.83(a) because they fail to show graphics pipeline 134 in Fig. 2 as described in the specification in [0029] and [0030]. Any structural detail that is essential for a proper understanding of the disclosed invention should be shown in the drawing. MPEP § 608.02(d). Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
The drawings are objected to under 37 CFR 1.83(a). The drawings must show every feature of the invention specified in the claims. Therefore, the method of Claim 4, wherein the subcubes differ in size and the method of Claim 7, wherein the subcubes closer to a middle of a cube for the lattice are smaller than subcubes on an outside of the cube must be shown or the feature(s) canceled from the claim(s). No new matter should be entered.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
The drawings are objected to because
Fig. 11, step 1130 states “LUT”, it is unclear that this acronym is associated with a lookup table.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Claim Objections
Claims 2, 7, 8, 11, 16, 17, and 20 are objected to because of the following informalities:
In Claim 2, “selecting an index into a lookup table” should read “selecting an index in a lookup table”.
In Claim 7, “wherein the subcubes in differ in size” should read “wherein the subcubes differ in size”.
In Claim 8, “wherein subcubes” should read “wherein the subcubes”.
In Claim 8, “than subcubes” should read “than the subcubes”.
In Claim 11, “selecting an index into a lookup table” should read “selecting an index in a lookup table”.
In Claim 16, “wherein the subcubes in differ in size” should read “wherein the subcubes differ in size”.
In Claim 17, “wherein subcubes” should read “wherein the subcubes”.
In Claim 17, “than subcubes” should read “than the subcubes”.
In Claim 20, “selecting an index into a lookup table” should read “selecting an index in a lookup table”.
Appropriate correction is required.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1, 9, 10, 18, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Fenney (GB 2597089 A), hereinafter referenced as Fenney in view of Bartol (“Deep learning vs. physics-informed grid search”, 2022), hereinafter referenced as Bartol in further view of Gottschalk (“Collision Queries using Oriented Bounding Boxes”, 2000), hereinafter referenced as Gottschalk.
Regarding Claim 1, Fenney discloses a method (Fenney, [0009], describes a computer-implemented method) comprising:
determining a characteristic orientation for a node based on an underlying geometry of triangles of the node (Fenney, [0065], teaches an oriented bounding box (OBB) <where the orientation of the OBB implicitly reads on characteristic orientation> bounding underlying geometry; Fenney, [0001], teaches geometry data <reads on underlying geometry> is often made up of triangular primitives; Fenney, [0063], teaches a bounding volume <reads on OBB> associated with a node);
and building a BVH using the node having the characteristic orientation (Fenney, [0009], describes building a BVH by defining a plurality of nodes and associating each node with one of a plurality of transformation matrices <reads on characteristic orientation>; Fenney, [0087], teaches an indication of a transformation matrix associated with a node; Fenney, [0085], teaches an AABB mapped to an OBB using the transformation matrix <the only difference between an AABB and an OBB is an orientation, so while there are different types of transformation matrices, the transformation matrix in this case must be a rotation matrix, and the indication of such reads on orientation>).
Fenney further teaches but does not explicitly disclose
assigning a candidate orientation to the node, based on Euclidean coordinates representative of the characteristic orientation (Fenney, [0012], describes selecting a bounding volume from a set of candidate bounding volumes where each candidate bounding volume is associate with a different transformation matrix <reads on candidate orientation> based on a predetermined heuristic; Fenney, [0087], teaches an indication of a transformation matrix associated with a node; Fenney, [0085], teaches an AABB mapped to an OBB using the transformation matrix <the only difference between an AABB and an OBB is an orientation, so while there are different types of transformation matrices, the transformation matrix in this case must be a rotation matrix, and the indication of such reads on orientation>);
However, Bartol teaches
assigning a candidate orientation, based on Euclidean coordinates (Bartol, [Image 3], teaches selecting a rotation by selecting a pre-computed rotation matrix, from a space SO(3) <reads on Euclidean> of rotations, with maximal cross-correlation based on the coordinates of the center of the voxel with the maximal cross correlation );
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method disclosed by Fenney by selecting a rotation based on Euclidean coordinates as taught by Bartol. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make these modifications to reduce time complexity and optimize construction of OBBs.
The combination of Fenney and Bartol do not teach
Euclidean coordinates representative of the characteristic orientation
However, Gottschalk teaches
Euclidean coordinates representative of the characteristic orientation (Gottschalk, [Section 3.3.0], teaches methods of OBBs can be extended to all simplicities in a finite dimensional Euclidean space; Gottschalk, [2.2.3], teaches an OBB’s orientation is represented as 3 unit-vectors that make up columns of a rotation matrix <a rotation matrix is a type of transformation matrix>)
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method disclosed by Fenney and Bartol by Euclidean coordinates representing an orientation of a bounding volume by Gottschalk. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make these modifications to optimize construction of OBBs using linear operations.
Regarding Claim 10, it recites limitations similar in scope to Claim 1, but as a system. As shown in the rejection, the combination of Fenney, Bartol, and Gottschalk disclose the limitations of Claim 1. Additionally, they disclose
A system comprising: a memory configured to store a BVH; and a processor configured to perform operations comprising (Fenney, [0093], describes a computer system as shown in Figure 12, where the system comprises a memory, reference character 1206, a GPU, reference character 1210, and a CPU, reference character 1202 <both GPU and CPU read on processor>; Fig. 12): …
PNG
media_image1.png
318
396
media_image1.png
Greyscale
A memory would be capable of storing a BVH, and a processor would be capable of performing operations. It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention that the structure elements mentioned above are capable of their intended function. It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method disclosed by Fenney, Bartol, and Gottschalk by developing it as a system as taught by Fenney. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make this application of a system including a memory and a processor because the combination of a memory and a processor is an efficient way to store and execute instructions of a method in one space.
Regarding Claim 19, it recites limitations similar in scope to Claims 1 and 10, but as a non-transitory computer-readable medium. As shown in the rejection, the combination of Fenney, Bartol, and Gottschalk disclose the limitations of Claims 1 and 10. Additionally, they disclose…
A non-transitory computer-readable medium storing instructions that, when executed by a processor, cause the processor to perform operations comprising: (Fenney, [0041], describes a non-transitory computer readable medium having stored thereon computer readable instructions, that when executed by a computer system cause the computer to perform any of the methods herein; Fenney, [0093] details the computer system including a GPU and a CPU, <these units read on processor>) comprising: …
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method and system disclosed by Fenney, Bartol, and Gottschalk by storing instructions on a non-transitory computer-readable medium that, when executed by a processor, cause the processor to perform operations of the previously disclosed method as taught by Fenney. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to apply this because a non-transitory computer-readable medium provides tangible, persistent storage for instructions that remain available to a processor without needing internet connection.
Regarding Claims 9 and 18, the combination of Fenney, Bartol, and Gottschalk disclose the method and system of Claims 1 and 10 respectively. They further disclose
wherein the candidate orientation is provided without labeled axes (Gottschalk, [2.2.3], teaches a rotation matrix is made up of 3 mutually orthogonal unit vectors <where rotation matrix reads on candidate orientation and unit vectors do not have labelled axes, the orientation is stored as numeric directions with no semantic axis labels>).
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method and system disclosed by Fenney, Bartol, and Gottschalk by providing an orientation without labeled axes as taught by Gottschalk. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make this modification to map three values to six potential rotations, therefore saving memory.
Claims 2, 11, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Fenney, Bartol, and Gottschalk in view of Wiki Analog (“Index Lookup Table”, 2016), hereinafter referenced as Wiki Analog in further view of Migge (“Tetris Rotations”, 2017), hereinafter referenced as Migge.
Regarding Claims 2, 11, and 20, the combination of Fenney, Bartol, and Gottschalk disclose the method, system, and medium of Claims 1, 10, and 19 respectively. They do not disclose the contents of Claims 2, 11, and 20. However, Wiki Analog discloses
selecting an index into a lookup table for the candidate orientation (Wiki Analog, [Image 1], teaches selecting an index to access corresponding entry in a LUT).
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method, system, and medium disclosed by Fenney, Bartol, and Gottschalk by selecting an index into a lookup table as taught by Wiki Analog. One of ordinary skill in the art before the effective filing of the claimed invention would have known a lookup table is capable of storing a candidate orientation been motivated to use this data structure to access candidate orientations for efficient data retrieval.
The combination of Fenney, Bartol, and Gottschalk in view of Wiki Analog does not explicitly teach storing a candidate orientation in a lookup table. However, Migge discloses
a lookup table for the candidate orientation (Migge, [Image 2], teaches precomputing rotations <reads on candidate orientation> and storing them in a lookup table).
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method, system, and medium disclosed by Fenney, Bartol, and Gottschalk in view of Wiki Analog by storing precomputed rotations in a lookup table as taught by Migge. One of ordinary skill in the art before the effective filing of the claimed invention would have known a lookup table is capable of storing a candidate orientation been motivated to use this data structure to store candidate orientations for quick execution and reduced latency.
Claims 3 and 12 are rejected under 35 U.S.C. 103 as being unpatentable over Fenney, Bartol, Gottschalk, Wiki Analog, and Migge in view of Eberly (“Dynamic Collision Detection using Oriented Bounding Boxes”, 2008), hereinafter referenced as Eberly.
Regarding Claims 3 and 12, the combination of Fenney, Bartol, Gottschalk, Wiki Analog, and Migge disclose the method and system of Claims 2 and 11 respectively. They further disclose
retrieving a precomputed rotation matrix from the lookup table based on the index (Migge, [Image 2], teaches precomputing rotations and storing them in a lookup table; Migge, [Image 2], further teaches precomputed rotations derived from rotation matrices; Wiki Analog, [Image 1], teaches accessing data in a lookup table based on an index),
applying the precomputed rotation matrix to a bounding box for the node to form a rotated bounding box (Gottschalk, [2.2.3], teaches an OBB is like an AABB, except it has an arbitrary rotation matrix. So that applying this rotation matrix to the axis aligned bounding box <reads on bounding box>, one will have created an OBB, also known as a rotated bounding box),
They do not disclose
performing an intersection test on the node by retrieving…
and testing the rotated bounded box for an intersection.
However, Eberly discloses
performing an intersection test on the node by retrieving (Eberly, [Section 7.1], teaches testing nodes associated with OBBs for intersection by retrieving whether or not a node is associated with an OBB (hasOBB()))…
PNG
media_image2.png
256
534
media_image2.png
Greyscale
and testing the rotated bounded box for an intersection (Eberly, [Section 2.2-3], teaches testing intersection of OBBs).
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method, system, and medium disclosed by Fenney, Bartol, Gottschalk, Wiki Analog, and Migge by performing an intersection test on the node by retrieving node data and testing oriented bounding boxes for intersection as taught by Eberly. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to use this more complex, but more accurate technique to precisely determine if the rotated bounding box intersects.
Claims 4 and 13 are rejected under 35 U.S.C. 103 as being unpatentable over Fenney, Bartol, and Gottschalk in view of X et al. (US 2019/0272665 A1), hereinafter referenced as X in view of Houdini 19.5 Documentation (“Matrix Field”, 2022), hereinafter referenced as Houdini.
Regarding Claims 4 and 13, the combination of Fenney, Bartol, and Gottschalk disclose the method and system of Claims 1, 10 respectively. They do not disclose the contents of Claims 4 and 13, however, X discloses
identifying which subcube of a lattice the Euclidean coordinates are within (X, [0013], teaches voxels <reads on subcubes> can be mapped to <reads on identify> a location (x, y, z) <reads as Euclidean coordinates> in a 3D grid of voxels for a 3D space <read on lattice>)
and selecting (X, [0059], describes obtaining data from a voxel <reads on subcube>)
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method and system disclosed by Fenney, Bartol, and Gottschalk by identifying voxels based on coordinates as taught by X. One of ordinary skill in the art before the effective filing of the claimed invention would have known been motivated to make this modification to impart precise mapping and identification of subcubes.
X does not disclose
a candidate orientation of the subcube as the candidate orientation.
However, Houdini discloses
a candidate orientation of the subcube as the candidate orientation (Houdini, [Image 1], teaches a voxels <reads on subcube> storing a transformation 3d matrix, such as a rotation transformation).
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method and system disclosed by Fenney, Bartol, Gottschalk, and X by storing a transformation matrix in a voxel as taught by Houdini. One of ordinary skill in the art before the effective filing of the claimed invention would have known been motivated to make this modification to impart functional mapping. Because Houdini discloses three types of transformation matrices, one of ordinary skill in the art before the effective filing date of the claimed invention would have found it obvious in light of the reference to use a rotation matrix, choosing from a finite number of identified, predictable solutions.
Claims 5, 6, 14 and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Fenney, Bartol, Gottschalk, X, and Houdini in view of Chang et al. (“Fast oriented bounding box optimization on the rotation group”, 2011), hereinafter referenced as Chang.
Regarding Claims 5 and 14, the combination of Fenney, Bartol, Gottschalk, X and Houdini disclose the method and system of Claims 4 and 13 respectively. They do not disclose the contents of Claims 5 and 14, however, Chang discloses
coordinates in a Euclidean space whose magnitude is equal to magnitudes of spherical coordinates defining the characteristic orientation (Chang, [Section 3], teaches minimizing the volume of an OBB in a 3-dimensional Euclidean space; Chang, [Section 3.3], discloses an a Euclidean space (SO(3, R)) parameterized by the triplet (φ, cosθ, α) <which are spherical coordinates in a Euclidean space, the magnitude of the coordinates are equal to the magnitudes of the spherical coordinates because the values are the same as the azimuth value corresponds with x, the elevation value corresponds with y and the rotation value corresponds with z; further, when an orientation is defined in this space, it would be defined by said coordinates>).
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method, system, and medium disclosed by Fenney, Bartol, Gottschalk, X, and Houdini by having Euclidean coordinates whose magnitude is equal to magnitudes of spherical coordinates as taught by Chang. One of ordinary skill in the art before the effective filing of the claimed invention would have known been motivated to make this modification to simplify complex 3D problems with radial symmetry.
Regarding Claims 6 and 15, the combination of Fenney, Bartol, Gottschalk, X, Houdini, and Chang disclose the method and system of Claims 5 and 14 respectively. They further disclose
the spherical coordinates correspond to an azimuth, an elevation, and an angle (Chang, [Section 3.3], states “the triplet (φ, cosθ, α), i.e., the azimuth angle, the cosine of the zenith angle and the angle of rotation around the axis defined by φ and θ, respectively.” <where the cosine of the zenith angle reads on an elevation>).
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method, system, and medium disclosed by Fenney, Bartol, Gottschalk, X, and Houdini by having the spherical coordinates correspond to an azimuth, an elevation, and an angle as taught by Chang. One of ordinary skill in the art before the effective filing of the claimed invention would have known been motivated to make this modification to simplify neighbor searches and provide intuitive 3D positioning for spatial lattices.
Claims 7, 8, 16, and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Fenney, Bartol, Gottschalk, X, and Houdini in view of Young et al. (US 9754405 B1), hereinafter referenced as Young.
Regarding Claims 7 and 16, the combination of Fenney, Bartol, Gottschalk, X and Houdini disclose the method and system of Claims 4 and 13 respectively. They do not disclose the contents of Claims 7 and 16, however, Young discloses wherein
the subcubes in differ in size (Young, [Fig. 1], illustrates subcubes of different levels or sizes).
PNG
media_image3.png
560
488
media_image3.png
Greyscale
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method, system, and medium disclosed by Fenney, Bartol, Gottschalk, X, and Houdini by having subcubes of different sizes as taught by Chang. One of ordinary skill in the art before the effective filing of the claimed invention would have known been motivated to make this modification to attempt to equalize the number of rotations captured by the volume of each subcube when certain areas are denser than others.
Regarding Claims 8 and 17, the combination of Fenney, Bartol, Gottschalk, X, Houdini, and Young disclose the method and system of Claims 7 and 16 respectively. They further disclose wherein
subcubes closer to a middle of a cube for the lattice are smaller than subcubes on an outside of the cube (Young, [Fig. 1], illustrates subcubes closer to a middle of a cube smaller than the Level-3 subcubes on the outer parts of the cube).
It would have been obvious for one having ordinary skill in the art before the effective filing date of the claimed invention to apply and/or modify the method, system, and medium disclosed by Fenney, Bartol, Gottschalk, X, Houdini, and Young by having subcubes closer to a middle of a cube for the lattice are smaller than subcubes on an outside of the cube as taught by Young. One of ordinary skill in the art before the effective filing of the claimed invention would have known been motivated to make this modification to attempt to equalize the number of rotations captured by the volume of each subcube when certain areas are denser than others.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Eriksson et al. (“Lattice-Based Quantization”, 1996) teaches vector quantization based on lattices.
Kim et al. (US 2012/0131595 A1) teaches a parallel collision detection method.
Chen (“Fast Volume Rendering and Deformation Algorithms”, 2001) teaches irregular lattice grids.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ISABELLA OCHSNER whose telephone number is (571)272-9322. The examiner can normally be reached 7:30 - 5:00 PM.
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, Devona Faulk can be reached at (571) 272-7515. 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.
/I.O./Examiner, Art Unit 2618
/DEVONA E FAULK/Supervisory Patent Examiner, Art Unit 2618