DETAILED ACTION
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 10/22/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 § 102
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 the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1, 3, 4, 6, 10, 12, 13, 15, 17 are rejected under 35 U.S.C. 102(a)(a) as being anticipated by LeGRAND (US 9058677 B1).
RE claim 1, LeGrand is made of record as teaching the art of broad phase collision detection [abstract]. LeGrand teaches a processor comprising: one or more circuits to (Fig. 2, using one or more integrated circuit devices such as programmable processors [4:30-42]):
(a)
map one or more combinations, of a plurality of first polygons identified from a first structure and a plurality of second polygons identified from a second structure, to a grid comprising a plurality of cells;
Fig. 2, 3D object (410) (said structure) is composed of triangles (420) (said plurality of first polygons) [11:19-22]. The 3D object (410) is associated with bounding sphere (430), where the bounding sphere (430) has an associated centroid (510) [Fig. 4, 11:19-30]. Fig. 6A illustrates two bounding spheres within a two-by-two-by-two array of 3D cells (600) [11:31-33]. As taught above, each object (410) is associated with a bounding sphere (430), thus, two bounding spheres discussed in Fig. 6A would corresponding to two objects, i.e. claimed first structure and second structure. Fig. 6B, depicts a projects of the two bounding sphere (620, 630) on a 2x2 array of cells (601) [11:44-46]. Each bounding sphere (620, 630) includes a respective centroid (622, 632). A cell that encompasses a given bounding sphere centroid is the “home cell” for the bounding sphere. Cells surrounding the home cell that also include portions of the bounding sphere are “phantom cells” of the bounding sphere (said map to a grid comprising a plurality of cells) [11:46-51].
(b)
identify one or more occupied cells of the plurality of cells, to which the one or more combinations are mapped; and
Fig. 7 displays how the bounding spheres occupy the cells [11:64-12:16]. Figs. 8A and 8B illustrate the structure of a cell identifier (ID) array entry (800). The cell array entry (800) includes a cell ID (812), an object ID (814), and control bits (816) [12:44-47].
(c)
output a data structure indicative of the plurality of occupied cells.
Figs. 8A and 8B illustrate the structure of a cell identifier (ID) array entry (800). The cell array entry (800) includes a cell ID (812), an object ID (814), and control bits (816) [12:44-47].
RE claim 3, LeGrand teaches wherein
(a)
the one or more circuits comprise a plurality of first circuits to determine the plurality of combinations,
Fig. 2, parallel processing subsystem (112) [3:65-67, 4:30-6:49]. Fig. 2, using one or more integrated circuit devices such as programmable processors [4:30-42]. In conjunction with the teachings of claim 1, Fig. 9B, the bounding spheres (930) are assigned to array of threads or thread block (940) for processing [13:45-53].
(b)
wherein each of the first circuits is communicatively coupled to a second circuit to set a flag of the second circuit, the flag being indicative that a given cell is one of the plurality of occupied cells.
Figs. 8A and 8B illustrate the structure of a cell identifier (ID) array entry (800). The cell array entry (800) includes a cell ID (812), an object ID (814), and control bits (816) [12:44-47]. LeGrand also teaches using control bits (616) indicating whether the given entry is associated with a home cell (said occupied cell) [13:1-6].
RE claim 4, LeGrand teaches wherein
(a)
each of the plurality of occupied cells is bounded by the plurality of combinations.
In further view of the rationale of claim 1, LeGrand provides the example of multiple bounding spheres (600) (said combination) [Fig. 6A, 11:31-33]. As taught in the rationale of claim 1, each object (410) is associated with a bounding sphere (430), thus, two bounding spheres discussed in Fig. 6A would corresponding to two objects. Fig. 6B, depicts a projects of the two bounding sphere (620, 630) on a 2x2 array of cells (601) [11:44-46]. Each bounding sphere (620, 630) includes a respective centroid (622, 632). A cell that encompasses a given bounding sphere centroid is the “home cell” for the bounding sphere. Cells surrounding the home cell that also include portions of the bounding sphere are “phantom cells” of the bounding sphere (said occupied cells bounded by the plurality of combinations) [11:46-51].
RE claim 6, LeGrand teaches wherein
(a)
the one or more circuits comprise a plurality of parallel computing circuits,
Fig. 2, parallel processing subsystem (112) [3:65-67, 4:30-6:49].
(b)
each parallel computing circuit of the plurality of parallel computing circuits to independently determine a corresponding combination of the one or more combinations.
In conjunction with the teachings of claim 1, Fig. 9B, the bounding spheres (930) are assigned to array of threads or thread block (940) for processing [13:45-53].
RE claim 10, LeGrand is made of record as teaching the art of broad phase collision detection [abstract]. LeGrand teaches a system comprising: one or more circuits to (Fig. 1, system (100) [3:54-4:17]; Fig. 2, using one or more integrated circuit devices such as programmable processors [4:30-42]):
(a)
map one or more combinations, of a plurality of first polygons identified from a first structure and a plurality of second polygons identified from a second structure, to a grid comprising a plurality of cells;
Fig. 2, 3D object (410) (said structure) is composed of triangles (420) (said plurality of first polygons) [11:19-22]. The 3D object (410) is associated with bounding sphere (430), where the bounding sphere (430) has an associated centroid (510) [Fig. 4, 11:19-30]. Fig. 6A illustrates two bounding spheres within a two-by-two-by-two array of 3D cells (600) [11:31-33]. As taught above, each object (410) is associated with a bounding sphere (430), thus, two bounding spheres discussed in Fig. 6A would corresponding to two objects, i.e. claimed first structure and second structure. Fig. 6B, depicts a projects of the two bounding sphere (620, 630) on a 2x2 array of cells (601) [11:44-46]. Each bounding sphere (620, 630) includes a respective centroid (622, 632). A cell that encompasses a given bounding sphere centroid is the “home cell” for the bounding sphere. Cells surrounding the home cell that also include portions of the bounding sphere are “phantom cells” of the bounding sphere (said map to a grid comprising a plurality of cells) [11:46-51].
(b)
identify one or more occupied cells of the plurality of cells, to which the one or more combinations are mapped; and
Fig. 7 displays how the bounding spheres occupy the cells [11:64-12:16]. Figs. 8A and 8B illustrate the structure of a cell identifier (ID) array entry (800). The cell array entry (800) includes a cell ID (812), an object ID (814), and control bits (816) [12:44-47].
(c)
output a data structure indicative of the plurality of occupied cells.
Figs. 8A and 8B illustrate the structure of a cell identifier (ID) array entry (800). The cell array entry (800) includes a cell ID (812), an object ID (814), and control bits (816) [12:44-47].
RE claim 12, claim 12 recites similar limitations as claim 3. Therefore, the same rationale used for claim 3 is applied.
RE claim 13, claim 13 recites similar limitations as claim 4. Therefore, the same rationale used for claim 4 is applied.
RE claim 15, claim 15 recites similar limitations as claim 6. Therefore, the same rationale used for claim 6 is applied.
RE claim 17, claim 17 recites similar limitations as claim 1 but in process form. Therefore, the same rationale used for claim 1 is applied.
RE claim 19, claim 19 recites similar limitations as claim 3 but in process form. Therefore, the same rationale used for claim 3 is applied.
RE claim 20, claim 20 recites similar limitations as claim 4 but in process form. Therefore, the same rationale used for claim 4 is applied.
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.
Claims 2, 11, 18 are rejected under 35 U.S.C. 103 as being unpatentable over LeGRAND (US 9058677 B1) in ZHU et al. (US 2013/0138682 A1).
RE claim 2, LeGrand teaches an array of cells but fails to further teach a second grid comprising smaller cells. Zhu is made of record as teaching a plurality of grids being established, where each grid has differently sized cells and items are assigned to grids based on the size of the items [abstract]. LeGrand in view of Zhu teaches wherein:
(a)
the grid is a first grid, the plurality of cells are a plurality of first cells, and the one or more occupied cells are one or more first occupied cells; and
Fig. 6A of LeGrand illustrates two bounding spheres within a two-by-two-by-two array of 3D cells (600) (said grid, plurality of cells) [11:31-33]. Each bounding sphere (620, 630) includes a respective centroid (622, 632). A cell that encompasses a given bounding sphere centroid is the “home cell” for the bounding sphere. Cells surrounding the home cell that also include portions of the bounding sphere are “phantom cells” of the bounding sphere (said occupied cells) [11:46-51].
the one or more circuits are to:
(b)
identify, in at least one second grid comprising a plurality of second cells, at least one region corresponding to the one or more first occupied cells, at least one second cell of the plurality of second cells smaller than at least one first cell of the plurality of first cells;
LeGrand teaches the size of the cell is selected such that the dimension of each uniformly sized cell is at least 1.5 times larger than the radius of the largest bounding sphere [13:36-38]. However, LeGrand is silent to a second grid that is smaller than the first.
Zhu teaches a plurality of grids that has differently sized cells [abstract]. Fig. 1 illustrates how a grid may be used to divide a domain space into cells [0022]. Data items are represented as points and each data item resides in exactly one cell [0022]. Zhu further teaches the size of cells does not have to be even across the entire encompassing searching space [0025]. As shown in Fig.4, a hierarchy of grids may be established for a domain space, where each grid in the hierarchy has different sized cells [0053]. As can be seen, bottom level (402) has a denser grid and smaller cells (said second cells smaller than first cells), than the middle level (404) (said first cells) [0053-0054].
(c)
map the one or more combinations to one or more second cells of the plurality of second cells outside of the at least one region to identify one or more second occupied cells of the plurality of second cells outside of the at least one region; and
In further view of Zhu, Zhu further teaches once a grid hierarchy has been established, items within that domain space may be assigned to grids based on the size of the items, the location of the items, the size of the grid cells, and the maximum allowed MGC for each grid (said identify one or more second occupied cells) [0055]
(d)
determine the data structure according to the plurality of first occupied cells and the plurality of second occupied cells.
As taught by LeGrand, Figs. 8A and 8B illustrate the structure of a cell identifier (ID) array entry (800). The cell array entry (800) includes a cell ID (812), an object ID (814), and control bits (816) [12:44-47]. Thus, the structure includes the cell information. In the combined invention of LeGrand and Zhu, the structure would include all of the occupied cells, i.e., claimed first and second cells.
It would have been obvious before the effective filing date of the claimed invention to utilize the grid hierarchy of Zhu within the grid of LeGrand because the configuration of the grid hierarchy helps with item distribution aiding in spatial query speed, since the majority of items are assigned to the bottom level of the hierarchy, and only few are in the upper level [0069].
RE claim 11, claim 11 recites similar limitations as claim 2. Therefore, the same rationale used for claim 2 is applied.
RE claim 18, claim 18 recites similar limitations as claim 2 but in process form. Therefore, the same rationale used for claim 2 is applied.
Claims 5, 14 are rejected under 35 U.S.C. 103 as being unpatentable over LeGRAND (US 9058677 B1) in view of HERTZMANN et al. (US 2023/0074094 A1).
RE claim 5, LeGrand teaches wherein
(a)
at least one first polygon is a convex polygon, and
LeGrand teaches the 3D object (410) is composed of triangles (420) (said convex polygon) [11:19-26].
(b)
The first structure is a non-convex polygon
LeGrand teaches the 3D object (410) is composed of triangles (420) [11:19-26] however does not discuss the 3D object being a non-convex polygon.
Hertzmann teaches computing accurate smooth occluding contours by projecting a boundary polygon associated with a first region of 3D object to a 2D image plane [abstract]. Hertzmann teaches the input (102) includes 3D object (104) [0034]. Fig. 3 illustrates a diagram of triangulation in a 2D projection [0046]. The object may be non-convex (said first structure is a non-convex polygon) which may have more regions than a convex object however, the non-convex object can be triangulated and stitched together along the contours [0047].
It would have been obvious before the effective filing date of the claimed invention for the 3D object of LeGrand to be any type of object. As taught by Hertzmann, a convex and non-convex 3D object can be triangulated. It would be beneficial to include non-convex objects to further accept all objects within the method/system of LeGrand, therefore not limiting the capabilities of LeGrand.
RE claim 14, claim 14 recites similar limitations as claim 5. Therefore, the same rationale used for claim 5 is applied.
Claims 7 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over LeGRAND (US 9058677 B1) in view of UNSW Sydney (“VOXELS, volumetric pixels” https://web.archive.org/web/20220307112544/https://www.unsw.edu.au/arts-design-architecture/our-schools/built-environment/our-research/clusters-groups/grid/research/voxels-volumetric-pixels).
RE claim 7, LeGrand teaches wherein:
(a)
the grid is a three-dimensional grid; and
Fig. 4 of LeGrand teaches an array of 3D cells (600) [11:31-35].
(b)
each cell is a voxel of the three-dimensional grid.
LeGrand does not term the 3D cells as voxels, however based on the definition from UNSW Sydney, the 3D cells of LeGrand can be considered voxels. UNSW Sydney teaches a voxel representation is a 3D space subdivided into equally sized little cubes [0004]. It would have been obvious before the effective filing date of the claimed invention for the 3D cells of LeGrand to be termed as voxels because LeGrand teaches a 3D object (410) and its associated bounding sphere (430) within a 2x2 array of 3D cells (600) i.e., cubes [11:19-21, 31-35]. Each cell is labeled according to position or “type” [11:37-39]. Furthermore, LeGrand teaches the position of each cell includes an xyz [12:48-67].
RE claim 16, claim 16 recites similar limitations as claim 7. Therefore, the same rationale used for claim 7 is applied.
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over LeGRAND (US 9058677 B1) in view of BURKE et al. (“Irregular Packing Using the Line and Arc No-Fit Polygon”).
RE claim 8, LeGrand teaches the limitations of claim 8 with the exception of disclosing NFP for arranging a plurality of parts. Burke is made of record as teaching wherein
(a)
wherein the data structure represents a no-fit polygon (NFP) for arranging a plurality of parts corresponding to the first structure and the second structure.
In further view of Burke, Burke teaches generating no-fit polygons based on the orbital method [0010]. In the example of two circles (said first structure and second structure), the non-fit polygon of A and B, is defined as the path followed by the reference point of B (the circle’s center point) when circle B orbits circle A [0012]. The no-fit polygon, NFBAB, of two circles is a circle of radius equal to the sum of A and B’s radii sharing the same center point as circle A [0012]. The edges within line-only no-fit polygons are derived from the same edges as the two input shapes A and B and assumes properties from both interacting edges [0013].
It would have been obvious before the effective filing date of the claimed invention to use the no-fit polygon because as Burke teaches, the no-fit polygon is a geometric construct that can offer faster and more efficient handling of geometry between pairs of shapes than traditional line-by-line intersection [0001].
Claim 9 is rejected under 35 U.S.C. 103 as being unpatentable over LeGRAND (US 9058677 B1).
RE claim 9, the language of claim 9 recites, “at least one of”, which limits the claim to needing only one of the limitations. Therefore, LeGrand teaches wherein the processor is comprised in a system for performing simulation operations. It should be noted that since only one limitation is required, the remainder of the limitations listed are mute. LeGrand teaches collision detection is important component of computer-based physics simulation (said system for performing simulation operations) [1:24-28]. Therefore, it would have been obvious before the effective filing date of the claimed invention that the method/system of LeGrand can be applied to a simulation system since LeGrand teaches using collision detection as taught by LeGrand is important in computer-based physics simulation [1:24-28].
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MICHELLE L SAMS:
direct telephone number:
(571) 272-7661
email:
michelle.sams@uspto.gov
The examiner is currently part time and can be reached Mon.-Fri. 5:30am-9:30am.
Examiner interviews are available via telephone 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, Kee M. Tung can be reached on (571)272-7794. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/MICHELLE L SAMS/
Primary Examiner, Art Unit 2611
10 June 2026
Prosecution Insights