DETAILED ACTION
1. Claims 1-19 have been presented for examination.
Notice of Pre-AIA or AIA Status
2. The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
PRIORITY
3. Acknowledgment is made that this application is a 371 of PCT/US2021/072805 filed 12/08/2021.
Response to Arguments
4. A request for continued examination under 37 CFR 1.114, including the fee set forth in 37 CFR 1.17(e), was filed in this application after final rejection. Since this application is eligible for continued examination under 37 CFR 1.114, and the fee set forth in 37 CFR 1.17(e) has been timely paid, the finality of the previous Office action has been withdrawn pursuant to 37 CFR 1.114. Applicant's submission filed on 9/29/26 has been entered.
i) Applicants argue that the prior art Mason does not recite “second intersection between a vertex of the mesh with an interior of that voxel.” It is first noted that Applicants appear to concede that a first intersection is determined by Mason but a “second intersection… with an interior of that voxel” is not. The Examiner notes that Mason recites in at least “[0109] In some examples, the silhouette volume may be computed in approximate, discretized form within a voxel grid. In these examples, filled voxels may represent regions of space comprising the silhouette volume. Such a method may begin by initially assuming that all voxels are inside the silhouette volume, and then classifying specific voxels as outside the silhouette volume, that is those voxels which do not lie within the silhouette volume. This classification may proceed iteratively, repeatedly computing multiple planar cross-sections on a number of different axes and then using the 2D convex hulls of the resulting projected intersection loops to reject voxels that lie on the intersection planes, but outside the respective hulls in that plane, as also outside the silhouette volume. Within each intersecting plane, the hulled intersection loops serve to classify all points that lie in the plane, but not within any of the hulls in that plane, as also outside the silhouette volume of the 3D shape. In cases where the number of planes is small, voxels may be projected onto their nearest plane, and the hulls within that plane used for rejection.” This appears to read on multiple intersections determined and then classifying interior and exterior intersections which reads on the claimed amendment. Therefore, the prior art rejection is MAINTAINED.
Claim Rejections - 35 USC § 102
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.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
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 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.
5. Claims 1-19 are rejected under 35 U.S.C. 102(a)(1) as being clearly anticipated by U.S. Patent Publication No. 20190221034.
Regarding Claim 1: The reference discloses A method comprising:
receiving data representing a mesh for a three-dimensional object; (“[0003] In computer games and other areas, such as computer-aided manufacturing (CAM) processes, polygonal meshes may be used. A polygonal mesh may be a collection of vertices, edges, and faces that define the shape and/or boundary of an object. The faces may consist of various polygonal shapes such as triangles, quadrilaterals, convex polygons, concave polygons, regular polygons (e.g. polygons which may have equal length sides and may have equal angles) and/or irregular polygons (e.g. polygons which may not have equal length sides and may not have equal angles).”)
determining a first set of points from a first intersection between a first voxel of a grid of voxels overlaid on the mesh and the mesh, the first intersection including an intersection of a boundary of the first voxel and the mesh; (“[0024] Determining the silhouette volume of the object may comprise representing the object as a volumetric grid, and filling any unfilled regions of the volumetric grid that are completely enclosed by filled regions with filled voxels to produce a solid voxel volume; extracting the boundary of the voxel volume as a closed mesh; intersecting the boundary of the voxel volume with a plurality of 2D planes to form a plurality of intersection loops; computing the convex hulls of the intersection loops; determining the voxels which lie near a plane yet outside its convex hulls; determining that the remaining voxels are within or on the boundary of the silhouette volume of the object.” “[0086] Forming such a mesh for the purposes of intersecting it with a plane may, in some examples, be done by rasterizing the original mesh into a volumetric grid, also known as a voxel representation. That is, the mesh may be represented by this voxel representation. For example, FIG. 6 illustrates the object of FIG. 3, that is, the sink, in a voxel representation. The resulting voxel representation may comprise filled voxels representing areas covered by mesh faces, and unfilled voxels representing areas not covered by mesh faces. The boundary of this voxel volume may be readily extracted to form a closed, well-formed manifold polygonal mesh that is suitable for intersection with a plane.”)
determining a second set of points from a second intersection between a second voxel of the grid of voxels and the mesh, the second intersection including an intersection between a vertex of the mesh with an interior of the first voxel; (“[0109] In some examples, the silhouette volume may be computed in approximate, discretized form within a voxel grid. In these examples, filled voxels may represent regions of space comprising the silhouette volume. Such a method may begin by initially assuming that all voxels are inside the silhouette volume, and then classifying specific voxels as outside the silhouette volume, that is those voxels which do not lie within the silhouette volume. This classification may proceed iteratively, repeatedly computing multiple planar cross-sections on a number of different axes and then using the 2D convex hulls of the resulting projected intersection loops to reject voxels that lie on the intersection planes, but outside the respective hulls in that plane, as also outside the silhouette volume. Within each intersecting plane, the hulled intersection loops serve to classify all points that lie in the plane, but not within any of the hulls in that plane, as also outside the silhouette volume of the 3D shape. In cases where the number of planes is small, voxels may be projected onto their nearest plane, and the hulls within that plane used for rejection.”)
generating a first convex hull from the first set of points and a second convex hull from the second set of points; and (“[0024] Determining the silhouette volume of the object may comprise representing the object as a volumetric grid, and filling any unfilled regions of the volumetric grid that are completely enclosed by filled regions with filled voxels to produce a solid voxel volume; extracting the boundary of the voxel volume as a closed mesh; intersecting the boundary of the voxel volume with a plurality of 2D planes to form a plurality of intersection loops; computing the convex hulls of the intersection loops; determining the voxels which lie near a plane yet outside its convex hulls; determining that the remaining voxels are within or on the boundary of the silhouette volume of the object.
[0025] A second aspect of this specification discloses apparatus comprising one or more processors and a memory, the memory comprising instructions that, when executed by the one or more processors, cause the apparatus to perform: receiving a computer representation of a 3D object; determining a silhouette volume of the object, wherein the silhouette volume is the maximal volume of space having a silhouette from every viewing direction which is identical to the silhouette of the object from the same viewing direction, and wherein points of the object which lie on the boundary of the silhouette volume also lie on the boundary of the object's projected silhouette from at least one viewing direction; and determining, based on the silhouette volume, the extent to which features of the object are silhouette features.
[0026] The instructions, when executed by the one or more processors, may cause the apparatus to perform: determining, for a plurality of planes and for a plurality of different axes, at least one intersection loop, wherein each intersection loop corresponds to a planar cross-section of the boundary of the object in its respective plane; and determining the convex hull of each intersection loop.”)
producing a proxy mesh of the three-dimensional object by combining the first convex hull and the second convex hull. (“[0027] The instructions, when executed by the one or more processors, may cause the apparatus to perform: classifying any 3D points which are located in or near a given plane, yet outside the convex hulls of the intersection loops formed within that plane, as being outside the silhouette volume; and determining that any points not classified as outside the silhouette volume form part of the silhouette volume.
[0028] This specification also discloses a non-transitory computer readable storage medium having instructions that, when executed by a processing device, cause the processing device to perform operations comprising: receiving a computer representation of a 3D object; determining a silhouette volume of the object, wherein the silhouette volume is the maximal volume of space having a silhouette from every viewing direction which is identical to the silhouette of the object from the same viewing direction, and wherein points of the object which lie on the boundary of the silhouette volume also lie on the boundary of the object's projected silhouette from at least one viewing direction; and determining, based on the silhouette volume, the extent to which features of the object are silhouette features.”)
Regarding Claim 2: The reference discloses The method as in claim 1, wherein the mesh includes a plurality of vertices and a plurality of edges, and wherein determining the first set of points includes: identifying a point on the boundary of the first voxel through which an edge of the plurality of edges or a vertex of the plurality of vertices of the mesh intersect the boundary of the first voxel. (“[0024] Determining the silhouette volume of the object may comprise representing the object as a volumetric grid, and filling any unfilled regions of the volumetric grid that are completely enclosed by filled regions with filled voxels to produce a solid voxel volume; extracting the boundary of the voxel volume as a closed mesh; intersecting the boundary of the voxel volume with a plurality of 2D planes to form a plurality of intersection loops; computing the convex hulls of the intersection loops; determining the voxels which lie near a plane yet outside its convex hulls; determining that the remaining voxels are within or on the boundary of the silhouette volume of the object.)
Regarding Claim 3: The reference discloses The method as in claim 1, the vertex is included in the second set of points. (“[0100] The intersection loops can be projected from 3D to 2D along the axis that is the normal of the intersecting plane, without losing any information, as the points of the intersection loop all lie in the plane. Therefore, subsequent processing of the intersection loops can be performed entirely in 2D. This can be advantageous as calculations are simpler and utilize less processing resource in 2D than do corresponding calculations in 3D, and it is mathematically simpler to describe regions of an object as being convex, and points in the 2D plane as being inside or outside the convex hull of the shape.
[0101] The loops may be used to determine whether to reject points (where the points may correspond to voxels, for example) as outside the silhouette volume. A given point can be tested to determine whether it lies inside any of the hulled loops (e.g. the hulled loops of FIG. 9). This may be done, for example, using a 2D point-inside-convex-hull test, which exploits the fact that the hulls are convex. The 2D point-inside-convex-bull test is implemented as a software routine.”)
Regarding Claim 4: The reference discloses The method as in claim 1, wherein the first convex hull includes a triangle separating an interior volume of the proxy mesh from an exterior volume of the proxy mesh, and wherein combining the first convex hull and the second convex hull includes: adding the triangle to the proxy mesh. (“[0066] In step S201, the method comprises receiving a computer representation of an object. The computer representation of the object may comprise a polygonal mesh. The polygonal mesh may be formed of polygons of any suitable size and shape. In some examples, the mesh may be formed of triangles. In other examples, the mesh may be formed of quadrilaterals. In other examples, the mesh may be formed of polygons having any suitable number of vertices and edges. However, it will be recognized that the computer representation of the object may be any suitable representation, and is not limited to being a polygonal mesh.
[0067] In step S202, the method may comprise identifying features of the polygonal mesh. This step may be performed by identifying mesh features such as vertices, edges, or faces, if the object is a polygonal mesh. In this case, the features may be recorded as a list of vertices of the object which may be stored in a memory as part of the computer representation of the object.
[0068] In step S203, the method may comprise determining the extent to which features are silhouette features, i.e. which are located on the boundary of silhouette of the object when viewed from one or more angles. If the object is a polygonal mesh, then the vertices, edges and/or faces may be the features of the mesh analyzed to determine the extent to which they are silhouette. An example of how the vertices located on the silhouette are identified is described in more detail below. An example of silhouette vertices and non-silhouette vertices is described in more detail below with reference to FIG. 3.
[0069] In some embodiments according to the present disclosure, in order to identify the silhouette features of the object, a silhouette volume is determined. Determining the silhouette volume of the object may comprise forming a large number of planar cross-sections of the boundary of the object. Each planar cross-section captures the extracted cross-section of the boundary of the object in that plane.
[0070] Once intersection loops characterizing the intersection of a plane with the boundary of the object have been computed, they form a set of closed loops projected in 2D in the intersecting plane. The loops may then be replaced with corresponding computed 2D convex hulls. These convex hulls may then be used to categorize areas of space within the plane that lie outside all convex hulls as outside the silhouette volume of the object.”)
Regarding Claim 5: The reference discloses The method as in claim 1, wherein the mesh includes a plurality of vertices and a plurality of edges, and wherein combining the first convex hull and the second convex hull includes: deleting duplicate vertices of the plurality of vertices and duplicate edges of the plurality of edges. (“[0058] During simplification, the processor is configured to select the edge candidate at the front of the queue at each simplification step. The selected edge candidate is collapsed. The collapse changes the mesh locally around the collapsed edges. Following collapse of the selected edge, the processor is configured to update the queue by removing any candidates which are no longer available, and by adding any new available edge collapse candidates. In addition, the costs of the available edge collapses are recomputed for any changes to the cost.” See also “[0055] In general, object simplification, including mesh simplification can be performed in a number of ways and according to a number of different algorithms. As described above, simplification is performed to reduce a resource cost of the object, where, for the case of mesh simplification, a greater number of polygons in the mesh corresponds to a greater resource cost. When mesh simplification is performed, the number of faces, edges, and vertices in the polygonal mesh are reduced” and the end of [0056] “For meshes formed of a plurality of quadrilateral faces, collapsing multiple edges at once, in a single operation, helps to preserve the quadrilateral structure of the mesh.”)
Regarding Claim 6: The reference discloses The method as in claim 1, wherein the first convex hull includes a set of triangles, and wherein combining the first convex hull and the second convex hull includes: identifying a triangle of the set of triangles not embedded in the boundary of the first voxel; and adding the triangle to the proxy mesh. (“[0066] In step S201, the method comprises receiving a computer representation of an object. The computer representation of the object may comprise a polygonal mesh. The polygonal mesh may be formed of polygons of any suitable size and shape. In some examples, the mesh may be formed of triangles. In other examples, the mesh may be formed of quadrilaterals. In other examples, the mesh may be formed of polygons having any suitable number of vertices and edges. However, it will be recognized that the computer representation of the object may be any suitable representation, and is not limited to being a polygonal mesh.
[0067] In step S202, the method may comprise identifying features of the polygonal mesh. This step may be performed by identifying mesh features such as vertices, edges, or faces, if the object is a polygonal mesh. In this case, the features may be recorded as a list of vertices of the object which may be stored in a memory as part of the computer representation of the object.
[0068] In step S203, the method may comprise determining the extent to which features are silhouette features, i.e. which are located on the boundary of silhouette of the object when viewed from one or more angles. If the object is a polygonal mesh, then the vertices, edges and/or faces may be the features of the mesh analyzed to determine the extent to which they are silhouette. An example of how the vertices located on the silhouette are identified is described in more detail below. An example of silhouette vertices and non-silhouette vertices is described in more detail below with reference to FIG. 3.
[0069] In some embodiments according to the present disclosure, in order to identify the silhouette features of the object, a silhouette volume is determined. Determining the silhouette volume of the object may comprise forming a large number of planar cross-sections of the boundary of the object. Each planar cross-section captures the extracted cross-section of the boundary of the object in that plane.
[0070] Once intersection loops characterizing the intersection of a plane with the boundary of the object have been computed, they form a set of closed loops projected in 2D in the intersecting plane. The loops may then be replaced with corresponding computed 2D convex hulls. These convex hulls may then be used to categorize areas of space within the plane that lie outside all convex hulls as outside the silhouette volume of the object.”)
Regarding Claim 7: (See rejection for claim 1)
Regarding Claim 8: (See rejection for claim 2)
Regarding Claim 9: (See rejection for claim 3)
Regarding Claim 10: (See rejection for claim 4)
Regarding Claim 11: (See rejection for claim 5)
Regarding Claim 12: (See rejection for claim 6)
Regarding Claim 13: (See rejection for claim 1)
Regarding Claim 14: (See rejection for claim 2)
Regarding Claim 15: (See rejection for claim 3)
Regarding Claim 16: (See rejection for claim 4)
Regarding Claim 17: (See rejection for claim 5)
Regarding Claim 18: (See rejection for claim 6)
Regarding Claim 19: The reference discloses The apparatus as in claim 13, wherein the controlling circuitry is further configured to: display the proxy mesh on a display device. (Figure 3)
Conclusion
6. All Claims are rejected.
7. The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
i) Reveillès, Jean-Pierre. "The geometry of the intersection of voxel spaces." Electronic Notes in Theoretical Computer Science 46 (2001): 285-308.
ii) Zimmer, Henrik, Marcel Campen, and Leif Kobbelt. "Efficient computation of shortest path-concavity for 3D meshes." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2013.
iii) U.S. Patent 6405151
8. Any inquiry concerning this communication or earlier communications from the examiner should be directed to Saif A. Alhija whose telephone number is (571) 272-8635. The examiner can normally be reached on M-F, 10:00-6:00.
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, Renee Chavez, can be reached at (571) 270-1104. The fax phone number for the organization where this application or proceeding is assigned is (571) 273-8300. Informal or draft communication, please label PROPOSED or DRAFT, can be additionally sent to the Examiners fax phone number, (571) 273-8635.
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).
SAA
/SAIF A ALHIJA/Primary Examiner, Art Unit 2186