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/21/2024 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
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, 2, 5, 6, 10, 11, 14, 15, 19, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Fenney (EP 3940649 A1), hereinafter referenced as Fenney in view of Kim et al. (US 2012/0131595 A1), hereinafter referenced as Kim.
Regarding Claim 1, Fenney discloses a method (Fenney, [Abs], describes a computer implemented method) comprising:
generating a bounding volume hierarchy for scene geometry (Fenney, [Abs], describes the method including creating a bounding volume hierarchy (BVH) for a model defined with respect to a local coordinate system <reads as scene geometry>);
performing ray tracing operations using the bounding volume hierarchy (Fenney, [0016], teaches the method further compromising using the BVH for intersection testing in a ray tracing system <reads on ray tracing operations>)
Fenney does not disclose
and performing collision detection operations with the bounding volume hierarchy.
However, Kim teaches a method (Kim, [Abs], describes a collision detection method) comprising:
and performing collision detection operations with the bounding volume hierarchy. (Kim, [Abs], describes a collision detection method comprising traversing a BVTT using bounding volume hierarchies and storing collision primitives in a leaf node when the currently traversed node is the leaf node and collision primitives in the leaf node overlap <collision detection method reads on collision detection operations>)
The only difference between the claimed invention and the prior art is that the prior art does not incorporate generating a BVH on scene geometry, performing the ray tracing operations, and performing collision detection operations into a single combined method. 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 also performing collision detections on the BVH as taught by Kim. Each element of the method merely performs the same function separately, no inventive effort would have been required to combine them. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make these modifications to yield predictable results.
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 and Kim disclose the limitations of Claim 1. Additionally, Fenney discloses
A system comprising: a memory configured to store scene geometry; and a processor configured to perform operations (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) including: ….
PNG
media_image1.png
394
452
media_image1.png
Greyscale
A memory would be capable of storing scene geometry, 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 and Kim 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 and Kim 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 (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 and Kim 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 2, 11, and 20, the combination of Fenney and Kim disclose the method, system, and medium of Claims 1, 10, and 19 respectively. They further disclose wherein the bounding volume hierarchy includes
one or more oriented bounding boxes (Kim, [0064], describes that a BVH is a tree structure that includes a bounding volume as a node; Kim, [0067], teaches that an oriented bounding box (OBB) is a bounding volume and describes two OBBs; Figs. 6A-C show collision types between OBBs, illustrating one or more OBBs).
PNG
media_image2.png
508
522
media_image2.png
Greyscale
PNG
media_image3.png
464
490
media_image3.png
Greyscale
PNG
media_image4.png
488
440
media_image4.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 and system disclosed by Fenney and Kim by further including one or more OBBs in the BVH as taught by Kim. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make this modification because an OBB introduces an angle parameter, as opposed to a traditional axis aligned bounding box, this additional parameter reduces background noise and improves detection accuracy.
Regarding Claims 5 and 14, the combination of Fenney and Kim disclose the method and system of Claims 1 and 10 respectively. They further disclose wherein the collision detection operations include
determining whether bounding volumes of the bounding volume hierarchy overlap (Kim, [0067], teaches collision detection between OBBs calculated by separating axis theorem; Fig. 6b illustrates overlapping collision status between 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 and system disclosed by Fenney and Kim by further including determining whether bounding volumes of the BVH overlap as taught by Kim. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make this modification because checking for overlapping OBBs is a computationally inexpensive way to find pairs of objects that could be colliding.
Regarding Claims 6 and 15, the combination of Fenney and Kim disclose the method and system of Claims 1 and 10 respectively. They further disclose wherein the ray tracing operations include
testing one or more rays for intersection against geometry represented in the bounding volume hierarchy. (Fenney, [0022], describes evaluating if a ray intersects a node <reads on bounding volume> of a bounding volume hierarchy).
Claims 3 and 12 are rejected under 35 U.S.C. 103 as being unpatentable over the combination of Fenney and Kim in view of Eberly (Eberly, David. (2001). “Dynamic Collision Detection using Oriented Bounding Boxes.”), hereinafter referenced as Eberly.
Regarding Claims 3 and 12, the combination of Fenney and Kim disclose the method and system of Claims 2 and 11 respectively. They further disclose intersection between two oriented bounding boxes (Kim, [0067], describes contact status between two OBBs, Fig. 6C), but they do not explicitly disclose the limitations of Claims 3 and 12; however, Eberly discloses a dynamic collision detection system using OBBs wherein the collision detection operations comprise,
determining whether two or more oriented bounding boxes intersect(Eberly, [Section 2.1-2.2.1], describes testing for intersection between OBBs using a nonintersection test).
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 and Kim by determining whether two or more oriented bounding boxes intersect as taught by Eberly. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make this modification to minimize the time spent determining if two objects intersect.
Claims 4 and 13 are rejected under 35 U.S.C. 103 as being unpatentable over the combination of Fenney and Kim in view of Ham et al. (“Collision detection and response of multibody systems using a position difference method and non-interpenetration constraint in shipbuilding simulation,” Ocean Engineering, Volume 195, 2020, 106673, ISSN 0029-8018), hereinafter referenced as Ham.
Regarding Claims 4 and 13, the combination of Fenney and Kim disclose the method and system of Claims 1 and 10 respectively. They do not explicitly disclose the limitations of Claims 4 and 13; however, Ham discloses a collision detection method wherein the collision detection operations comprise,
a first phase of a two phase collision detection operation, wherein in the first phase, bounding boxes are tested for intersection and in a second phase of the two phase collision detection operation, meshes bounded by the bounding boxes are tested for intersection (Ham, [Section 2], describes collision detection composed of two stages where one is a broad phase checking collisions between two bounding boxes, and the other is a narrow phase which checks collisions between the meshes; see Fig. 2 showing collision detection between two object meshes; these meshes had been bounded by bounding boxes in the broad phase).
PNG
media_image5.png
518
832
media_image5.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 and system disclosed by Fenney and Kim by a two-phase collision operation as taught by Ham. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make this modification because the well-known technique of broad to narrow two stage collision detection yields high efficiency, precision, and performs better with complex scenes, by starting with a broad phase, it reduces the amount complex calculations computed by the narrow phase by filtering out object pairs that are obviously not colliding.
Claims 7, 8, 16 and 17 are rejected under 35 U.S.C. 103 as being unpatentable over the combination of Fenney and Kim in view of Laine et al. (US 2021/0012552 A1), hereinafter referenced as Laine.
Regarding Claims 7 and 16, the combination of Fenney and Kim disclose the method and system of Claims 1 and 10 respectively. They do not explicitly disclose the limitations of Claims 7 and 16; however, Laine discloses wherein,
the bounding volume hierarchy includes one or more instance nodes (Laine, [0132], teaches an instance node in a BVH; Fig. 8B, reference character N7’).
PNG
media_image6.png
346
424
media_image6.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 and system disclosed by Fenney and Kim by including one or more instance nodes in a BVH as taught by Laine. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to make this modification because instance nodes represent an occurrence of an object, this would simplify the traversal of a BVH if the object is found within different bounding volumes.
Regarding Claims 8 and 17, the combination of Fenney, Kim, and Laine disclose the method and system of Claims 7 and 16 respectively. They further state teach that objects can be represented as instance nodes in a BVH (Laine, [0064]). Additionally, they further disclose, wherein the collision detection operations comprise
determining whether an instance node intersects with another instance node. (Kim, [0022], teaches parallel collision detection <reads on determining intersection> between two boundary volumes <reads on objects>, where nodes are traversed in a BVH).
It would have been obvious for one of 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, Kim, and Laine by collision detection using bounding volumes as taught by Kim. Through broadest reasonable interpretation, both a bounding volume, represented as a node, and an instance node represent an object without recreating the complex geometries of said object. One of ordinary skill in the art before the effective filing of the claimed invention would have recognized this interpretation and would have been motivated to apply this method to instance nodes because this method traverses the BVH efficiently using parallel processing which reduces bottlenecks and latency by distributing computational tasks evenly across processors.
Claims 9 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over the combination of Fenney, Kim, and Laine in view of CD Lecture (See attached, “cdLecture.pdf”), hereinafter referenced as CD Lecture.
Regarding Claims 9 and 18, the combination of Fenney, Kim, and Laine disclose the method and system of Claims 8 and 17 respectively. They do not explicitly disclose the limitations of Claims 9 and 18; however, Rapier Documentation discloses wherein,
one or more instance node is marked as collidable (CD Lecture, [Image 6], this pseudocode shows a method called checkObjectCollision(), this checks to see if the specified object <reads on instance node> collides with any other object, and returns true if there is a collision <reads on marked>).
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, Kim, and Laine by marking objects as collidable by as taught by CD Lecture. One of ordinary skill in the art before the effective filing of the claimed invention would have been motivated to apply this technique on an instance node because marking or identifying collision can trigger an event or an interaction, including stopping movement traversal.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Muthler et al. (US 2021/0390758 A1) discloses enhanced techniques applicable to a ray tracing hardware accelerator for traversing a hierarchical acceleration structure.
Mirtich ("Efficient Algorithms for Two-Phase Collision Detection", Tech. Rep. TR97-23, Mitsubishi Electric Research Laboratories, Cambridge, MA, December 1997.) discloses practical two-phase collision detection algorithms.
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